last day (15 days later) » 

evinda
evinda
22:20
Hi @Erwin Kalvelagen !!!
Could I ask you something about the simplex method?
Erwin Kalvelagen
Erwin Kalvelagen
Sure.
evinda
evinda
@ErwinKalvelagen I want to solve the following linear programming problem:
$$\min (3x_1-x_2+2x_3) \\ 3x_1+2x_2-x_3 \leq 9 \\ 5x_2-x_3 \leq 1 \\ 4x_1-x_2 \geq 1 \\ x_1+x_2+x_3 \leq 3 \\ x_1, x_2, x_3 \geq 0$$
I wrote it in its canonical form as follows:
$$- \max (-3x_1+x_2-2x_3) \\ 3x_1+2x_2-x_3+x_4 = 9 \\ 5x_2-x_3+x_5 =1 \\ 4x_1-x_2-x_6=1 \\ x_1+x_2+x_3+x_7= 3 \\ x_i \geq 0, i=1, \dots, 7$$
The matrix A that corresponds to the above equations is the following:
$A=\begin{bmatrix}
3 & 2 &-1 & 1 & 0 & 0 & 0\\
0 & 5 & -1 & 0 & 1 & 0 & 0\\
4 & -1 & 0 & 0 & 0 & -1 &0 \\
1 & 1 &1 & 0 & 0 & 0 & 1
\end{bmatrix}$
How can we find an initial basic feasible non-degenerate solution so that we can apply the simplex method now that we have -1 at the P_6 column? @ErwinKalvelagen
Erwin Kalvelagen
Erwin Kalvelagen
In practice software will do this for you, so you don't have to worry about that. But assuming you want to solve this using a textbook "tableau" method, you need to look up in your book a technique called "artificial variables". (Note that practical revised simplex methods don't use artificials it is merely used to keep students busy).
evinda
evinda
Ok, I will look at it... But in class we didn't fo this... @ErwinKalvelagen
So if we want to find an initial solution do we have to make gauss elimination or something similar? @ErwinKalvelagen
Erwin Kalvelagen
Erwin Kalvelagen
22:37
No Gauss elimination needed yet. To find an initial basic feasible solution most textbooks will augment the problem using these artificials and then start a "phase 1" simplex method. Again in practice simplex methods work very differently.
evinda
evinda
Could you explain to me what we do in "phase 1" simplex method ? @ErwinKalvelagen
Erwin Kalvelagen
Erwin Kalvelagen
It will solve the augmented problem using standard simplex (small wrinkle: we need to pivot out the artificials before terminating). Then remove the articifials and start Phase II. You book should have a chapter on this.
evinda
evinda
@ErwinKalvelagen Ah I found it in my textbook... I will read it now and I'll tell you if I got it... :)
@ErwinKalvelagen So do we write this equation : $ 4x_1-x_2-x_6=1$ as $ 4x_1-x_2-x_6+x_8=1$, then apply the simplex method using the following matrix
$A=\begin{bmatrix}
3 & 2 &-1 & 1 & 0 & 0 & 0 & 0\\
0 & 5 & -1 & 0 & 1 & 0 & 0 & 0\\
4 & -1 & 0 & 0 & 0 & -1 &0 & 1 \\
1 & 1 &1 & 0 & 0 & 0 & 1 & 0
\end{bmatrix}$

and then at the optimal solution that we find we just ignore the last component?

Or have I understood it wrong?

  last day (15 days later) »