0

enter image description here

Applying simplex, I found out the optimal solution to be $z^*=16$ and $x^{*} = (8,0,0,0,12)$ where $x_4,x_5$ are slack variables.

Now, suppose we add constraint $x_2+2x_3 = 3$

So, If I were to add this constraint to the optimal tableau, we see that this does ${\bf not}$ affect the values of $z_j-c_j$ and so optimality is not changed. This suggests that we have to consider $x_2+2x_3 \leq 3 $ and $x_2+2x_3 \geq 3$ which is same as $-x_2-2x_3 \leq -3$ and so after adding slack variables $x_6,x_7$,then we see that the feasibility is changed (primal feasibility). In this situation, do we run the dual simplex?

or the way to handle this situation is different than the way I thought?

Mikey Spivak
  • 871

1 Answers1

2

$(8,0,0)$ doesn't satisfy $x_2+2x_3=3.$ The value on the LHS is less than the $RHS$.

$$\max 2x_1+x_2-x_3-Mx_6$$ subject to $$x_1+2x_2+x_3+x_4=8$$

$$-x_1+x_2-2x_3 + x_5=4$$

$$x_2+2x_3+x_6=3$$

$$x \ge 0$$

At $(x_1, x_2, x_3, x_4, x_5, x_6)=(8,0,0,0,12,3)$, we have $x_1, x_5, x_6$ being basic variables and we can run primal simplex.

If the previous basis matrix is $B$, now, our basis matrix is $\begin{bmatrix} B & 0 \\ 0 & 1\end{bmatrix}$ with its inverse being $\begin{bmatrix} B^{-1} & 0 \\ 0 & 1\end{bmatrix}.$ The main entries of the simplex tables are $$\begin{bmatrix} B^{-1} & 0 \\ 0 & 1\end{bmatrix}\begin{bmatrix} A & 0\\ a_3^T & 1\end{bmatrix}=\begin{bmatrix} B^{-1}A & 0\\ a_3^T & 1\end{bmatrix}$$

$$\begin{bmatrix} B^{-1} & 0 \\ 0 & 1\end{bmatrix}\begin{bmatrix} b \\ b_3\end{bmatrix}=\begin{bmatrix} B^{-1}b \\ b_3 \end{bmatrix}$$

Siong Thye Goh
  • 149,520
  • 20
  • 88
  • 149
  • Why did you add slack to the new constraint if it was already an equiality? – Mikey Spivak Nov 22 '18 at 16:04
  • so that we can move on from the current position in our simplex implementation. – Siong Thye Goh Nov 22 '18 at 16:16
  • Is it possible to add constraint to the optimal tableau of the “old” problem and take it from there? Maybe using dual simple? – Mikey Spivak Nov 22 '18 at 16:28
  • Sure. I added a constraint and the variable $x_6$. With $x_1, x_5, x_6$ as the basis, most entries are identical with the old problem. – Siong Thye Goh Nov 22 '18 at 16:36
  • I have added an explanation why most entries are the same. – Siong Thye Goh Nov 22 '18 at 16:43
  • its very nice! I have another question, in the same LP, We know ${ \bf b} = (8,4)^T$, the RHS of the constraint. IF we were to to change the RHS of the constraints, as long as it is not negative, we are still feasible. But, if I were to change RHS of either first or second constraint, is there one that would change the optimal value of the function more? – James Nov 22 '18 at 20:13
  • I would look at the dual value. – Siong Thye Goh Nov 23 '18 at 01:13