1
$\begingroup$

My books says to choose the smallest positive ratio between the RHS value and its corresponding coefficient in the pivot column.

Apologies for the screenshots but I'm showing the exact results of a Simplex Calculator online.

The Objective function and constraints:

enter image description here

The solution (+ tableau steps):

enter image description here

In the first Table the pivot column is chosen correctly.. i.e - the most negative column in the last row (the objective function).

However as you can see leading into the second table that the Pivot row that was chosen was the top row. Which doesn't make sense to me since $\frac{1}{1}=1$ but $\frac{-1}{-4}=\frac{1}{4}<1$.

Can someone explain why they chose that pivot?

EDIT - Original Question

enter image description here

$\endgroup$
  • $\begingroup$ The given solution is wrong: optimal solution is (0,1,0), but the 2nd constraint reads $-y_1-2y_3 \le -2$. IMHO, the cause of the problem is that the program assumes positive variables (in particular, $s_3$.), but there's a negative value on the RHS of the initial tableau. Therefore, it's infeasible as first. It's better to first find a BFS by either the two-phase method or the $M$-method. $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Feb 17 '17 at 0:17
  • $\begingroup$ Thanks for the response. See my edit above. It may have been an issue with me converting a minimization to a maximization problem. Though I can't see the issue, can you help me out? $\endgroup$ – Gregory Peck Feb 17 '17 at 20:29
  • $\begingroup$ Your conversion from to the max problem is right, but then you've applied the wrong tool to solve this problem. Surplus/slack variables $s_i$ are non-negative. In the initial tableau, $s_2,s_3 < 0$. (Feasibility condition must be satisfied in a simplex tableau, unless for dual simplex method.) To start with, you always need a basic feasible solution to the LP. That's why I suggest you to find it first either by two-phase method or big-$M$ method. I can do this, but I appreciate your response to my answer to your other question. $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Feb 17 '17 at 21:11
  • $\begingroup$ Would it be possible to get the dual of this problem and solve that? If not, this means there is no way to solve using standard simplex method, right? $\endgroup$ – Gregory Peck Feb 17 '17 at 21:34
  • $\begingroup$ In the dual simplex method, we use get feasibility to get optimality, while in the simplex method, we use feasibility to get optimality. Now we've none of them, but we're still using simplex method to solve it. $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Feb 17 '17 at 21:43
3
$\begingroup$

Part I: Find a BFS

OP has transformed the LP to this max problem.

\begin{array}{rrr} \max z &= -3y_1 + y_2 - 2y_3 & \\ \text{s.t.} & -2y_1 + y_2 - y_3 \le& 1 \\ & -y_1 \phantom{-y_2} - 2y_3 \le& -2 \\ & 7y_1-4y_2+6y_3 \le& -1 \\ & y_1,y_2,y_3 \ge 0 \end{array}

In the given initial tableau, the problem is actually

$$ \begin{array}{rrrr} \max z =& -3y_1 + y_2 - 2y_3 & & \\ \text{s.t.} & -2y_1 + y_2 - y_3 &+ s_1 =& 1 \\ & -y_1 \phantom{-y_2} - 2y_3 &+ s_2 =& -2 \\ & 7y_1-4y_2+6y_3 &+ s_3 =& -1 \\ & y_1,y_2,y_3,s_1,s_2,s_3 \ge 0 \end{array} \tag{1}\label{1} $$

The computer program handles positive variables, but the RHS shows that the current BFS is $s_1 = 1$, $s_2 = -2$ and $s_3 = -1$. This is the cause of error.

In fact, we should make RHS non-negative.

$$ \begin{array}{rrrr} \max z =& -3y_1 + y_2 - 2y_3 & & \\ \text{s.t.} & -2y_1 + y_2 - y_3 &+ s_1 =& 1 \\ & y_1 \phantom{+y_2} + 2y_3 &- s_2 =& 2 \\ & -7y_1+4y_2-6y_3 &- s_3 =& 1 \\ & y_1,y_2,y_3,s_1,s_2,s_3 \ge 0 \end{array} \tag{2}\label{2} $$

We need to find feasible solution first, so we add two more artificial non-negative variables $u_1$ and $u_2$ to the LP. (To apply simplex method, we can't have negative variables.) Since $u_1$ and $u_2$ aren't in the BFS of the actual problem \eqref{2}, we eliminate them by minimizing $u_1 + u_2$.

\begin{array}{rrrr} \max z= & -u_1 - u_2 & & \\ \text{s.t.} & -2y_1 + y_2 - y_3 &+ s_1 \phantom{+u_1} =& 1 \\ & y_1 \phantom{+y_2} + 2y_3 &- s_2 + u_1 =& 2 \\ & -7y_1+4y_2-6y_3 &- s_3 + u_2 =& 1 \\ & y_1,y_2,y_3,s_1,s_2,s_3,u_1,u_2 \ge 0 \end{array}

The actual intial simplex tableau

    y_1 y_2 y_3 s_1 s_2 s_3 u_1 u_2 RHS
s_1  -2   1  -1   1   0   0   0   0   1
u_1   1   0   2   0  -1   0   1   0   2
u_2  -7   4  -6   0   0  -1   0   1   1
---------------------------------------
      0   0   0   0   0   0   1   1   0

    y_1 y_2 y_3 s_1 s_2 s_3 u_1 u_2 RHS
s_1  -2   1  -1   1   0   0   0   0   1
u_1   1   0   2   0  -1   0   1   0   2
u_2  -7  4*  -6   0   0  -1   0   1   1
---------------------------------------
      6  -4   4   0   1   1   0   0  -3

      y_1 y_2  y_3 s_1 s_2  s_3 u_1  u_2 RHS
s_1  -1/4   0  1/2   1   0  1/4   0 -1/4 3/4
u_1     1   0   2*   0  -1    0   1    0   2
y_2  -7/4   1 -3/2   0   0 -1/4   0  1/4 1/4
--------------------------------------------
       -1   0   -2   0   1    0   0    1  -2

     y_1 y_2 y_3 s_1  s_2  s_3  u_1  u_2 RHS
s_1 -1/2   0   0   1  1/4  1/4 -1/4 -1/4 1/4
y_3  1/2   0   1   0 -1/2    0  1/2    0   1
y_2   -1   1   0   0 -3/4 -1/4  3/4  1/4 7/4
--------------------------------------------
       0   0   0   0    0    0    1    1   0

Now we've a BFS $y_2 = \frac74$, $y_3 = 1$ and $s_1 = \frac14$.

Part II: Find an optimal BFS

Return to \eqref{2}.

     y_1 y_2 y_3 s_1  s_2  s_3 RHS
s_1 -1/2   0   0   1  1/4  1/4 1/4
y_3  1/2   0   1   0 -1/2    0   1
y_2   -1   1   0   0 -3/4 -1/4 7/4
----------------------------------
       3  -1   2   0    0    0   0

     y_1 y_2 y_3 s_1  s_2  s_3  RHS
s_1 -1/2   0   0   1  1/4 1/4*  1/4
y_3  1/2   0   1   0 -1/2    0    1
y_2   -1   1   0   0 -3/4 -1/4  7/4
-----------------------------------
       1   0   0   0  1/4 -1/4 -1/4

     y_1 y_2 y_3 s_1  s_2 s_3 RHS
s_3   -2   0   0   4    1   1   1
y_3  1/2   0   1   0 -1/2   0   1
y_2 -3/2   1   0   1 -1/2   0   2
---------------------------------
     1/2   0   0   1  1/2   0   0

Hence, the optimal solution to \eqref{2} (thus the original LP) is $(y_1,y_2,y_3,s_1,s_2,s_3) = (0,2,1,0,0,1)$ with optimal value 0.

$\endgroup$
  • $\begingroup$ Of course. It seems obvious when you explain it. Thanks a lot for taking the time to answer !! $\endgroup$ – Gregory Peck Feb 18 '17 at 19:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.