The original minimization problem
\begin{align}
\min z = 5y_1-10y_2+7y_3-3y_4 & \\
y_1+y_2+7y_3+2y_4 &= 3 \\
y_2+17y_3+7y_4 &= 8 \\
6y_3+3y_4 &= 2 \\
y_i &\geq 0, i \in \{ 1, \dots, 4 \}
\end{align}
We try to find a basic feasible solution to the original LPP by the two-pha...
To use the simplex method we firstly write the linear programming problem in its canonical form , so $\min z=y_5+y_6$ becommes $- \max (-z=-y_5-y_6)$. $$$$ $-1$ is the smallest value at the last row, so do deduce that $P_5$ gets in the basis and $P_6$ gets out of the basis. This can't be true. $$$$ Or am I wrong?
@Evinda You may see the following table [my answer for another question][1] for a detailed description. \begin{array}{rr|l} & \text{a non-basic variable} & \text{RHS} \\ \hline \text{a basic variable} & \heartsuit > 0 & \spadesuit \ge 0 \\ \hline z & \clubsuit & \text{obj. fct. val.} \end{array} After each pivot operation, you have \begin{equation*} \text{new obj. fct. val.} = \text{obj. fct. val.} - \frac{\spadesuit\clubsuit}{\heartsuit} \end{equation*} [1]: math.stackexchange.com/a/1594962/290189
@Evinda "$-1$ is smallest, so $P_5$ gets out of the basis" is true when (1) we are doing a max-type LPP, and (2) it is a simplex tableau The problem is, in the first tableau of my answer, it is not a simplex tableau. The two $-1$ in the last row is in the column $P_5$ and $P_6$, which is in the basis. Therefore, to make it a simplex tableau, we do some row operations.
Directly using $\min z = y_5+y_6$ and remembering to choose the largest $z_j - c_j$ instead of converting it to a max-type and choosing the smallest $z_j - c_j$ LPP saves you one step.
I think that $L_4'=L_1+L_2+L_3+L_4$ isn't true, otherwise it should hold that $z_5'-c_5=2$. Or am I wrong? $$$$ Also could you explain me further how we get -9? Do we find the sum of the elements of the b-row and then take the minus of that? If so why do we do it like that?
Also I added my post since I do not get the same tableaus and thus the same solution as in my textbook. Have I done something wrong at the calculations?
@Evinda Sorry. I've made 3 mistakes: (1) $L_4'=-L_1-L_2-L_3+L_4$ to ensure that if $P_j$ is a basic variable, $z_j - c_j$ must be zero. This step is very important. (2) In the 3rd and 4th (i.e. last) objective function values $z$, I made a mistake. I've corrected them. Your book is correct. However, I don't think that these mistakes will affect the conclusion that the LPP is infeasible because (1) the rightmost column $L_1 = \dots$ is unnecessary, especially in test/exams. Without that column, everyone still knows what you're doing. (pivot operation)
@Evinda (2) The optimality only depends on the $z_j - c_j$ of decision variables $P_j$, while the feasibility only depends on whether the entries in the $b$ column in the constraints row is non-negative. (i.e. whether $B^{-1} b \ge 0$) Neither the optimality nor the feasibility has anything to do with the value of $z$. We deduce that the LPP is infeasible from the entries in the $z$ row and in the $b$ column but excluding the objective function value, so that doesn't hurt.
@Evinda Btw, your book's tableau format is very clumsy. You may use a better format with fewer to save time in tests/exams. \begin{array}{crrrrrrr|l} & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 & \\ \hline x_4 & 0 & -3 & 7 & 1 & 0 & 0 & 2 & 2M -4 \\ x_5 & 0 & -9 & 0 & 0 & 1 & 0 & -1 & -M -3 \\ x_6 & 0 & 6 & -1 & 0 & 0 & 1 & -4^* & -4M +8 \\ x_1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & M \\ \hline & 0 & 1 & 1 & 0 & 0 & 0 & 2 & 2M \\ \end{array}
@Evinda That is, you don't need to write the coefficients of $c_B$ in each step. You can just do pivot operations normally to calculate the value of $z$. Therefore, I get $-9$ in the second step (out of four steps) by $0 - 3 - 2 - 4$. The above tableau is for the dual simplex algorithm, but I hope you know what I mean.
@Evinda I *won't* say that the values are wrong. I will say that the last row of that tableau doesn't contain entries in the form $z_j - c_j$. Just proceed with this to get a simplex one is find. Change \begin{array}{cc|c} A & I & b \\ \hline -c^T & 0 & 0 \end{array} to \begin{array}{cc|c} B^{-1}A & B^{-1} & B^{-1}b \\ \hline c_B^T B^{-1}A-c^T & c_B^T B^{-1} & c_B^T B^{-1}b \tag{*} \end{array}
Even though the form of simplex tableau your textbook is so clumsy that I *don't* want to use, I'll still use it for you, and I see one advantage of using this form (but I *don't* enjoy this advantage): **You can calculate the scalar product of the two leftmost columns $c_B^T B^{-1} b$ and see whether it matches the lower left-hand corner of your tableaux $z$. If they don't match, you'll need to spot out the mistake.**
I should have said this earlier. In your 1st tableau, $-3-2-4 = -9$, so it's OK.
1st question: You mean to apply $L_4'=L_4+18 L_1'$ to all $z_k-c_k$ with $k \ge 1$? This is a row operation, so we apply this to every column (including the $b$ and $z$)
2nd question: yes, you may check it using a "computer"
Discussion between GNU Supporter and …
Discussion between GNU Supporter and …