How to apply the simplex method

[evinda]

Hello! (Wave)

I want to solve the following linear programming problem:

$$\min (3y_1-y_2+2y_3) \\ 3y_1+2y_2-y_3 \leq 9 \\ 5y_2-y_3 \leq 1 \\ 4y_1-y_2 \geq 1 \\ y_1+y_2+y_3 \leq 3 \\ y_1, y_2, y_3 \geq 0$$

In this case we use the $M$-method.The canonical form of the problem is the following:$$-\max (-3y_1+y_2-2y_3) \\ 3y_1+2y_2-y_3 +y_4= 9 \\ 5y_2-y_3 +y_5= 1 \\ 4y_1-y_2 -y_6= 1 \\ y_1+y_2+y_3 +y_7= 3 \\ y_i \geq 0, i=1,2, \dots, 7$$The matrix $A$ ($Ax=b$) 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}$It doesn't contain the $4 \times 4$ identity matrix, that's why we introduce an artificial variable $y_8 \geq 0$ at the third equation and we have the new system of restrictions:

$$ 3y_1+2y_2-y_3 +y_4= 9 \\ 5y_2-y_3 +y_5= 1 \\ 4y_1-y_2 -y_6+y_8= 1 \\ y_1+y_2+y_3 +y_7= 3 \\ y_i \geq 0, i=1,2, \dots, 7,8$$Now we will solve the problem with the $M-$method , i.e. we will solve the linear programming problem $\max(-3y_1+y_2-2y_3+MY-8), M<<0$ under the new system of restrictions.I tried to apply the simplex method and I got the following:$$\begin{matrix}
B & c_B & b & P_1 & P_2 & P_3 & P_4 & P_5 & P_6 & P_7 & \theta & \\
P_4 & 0 & 160 & 2 & 3 & 4 & 1 & 0 & 0 & 0 & 80 & L_1\\
P_5 & 0 & 180 & 3 & 2 & 3 & 0& 1 & 0 & 0 & 60 & L_2\\
P_6 & 0 & 200 & 4 & 3 & 2& 0 & 0 & 1 & 0 & 50 & L_3\\
P_7 & 0 & 120 & 1 & 2 & 1 &0 & 0 & 0 & 1 & 120 & L_4 \\
& z & 0 & -30 & -26 & -28 & 0 & 0& 0& 0 & & L_5
\end{matrix}$$

$P_1$ gets in the basis, while $P_6$ gets out of the basis.$\begin{matrix}
B & c_B & b & P_1 & P_2 & P_3 & P_4 & P_5 & P_6 & P_7 & \theta & \\
P_4 & 0 & 60 & 0 & \frac{1}{2} & 3 & 1 & 0 & -\frac{1}{2} & 0 & 20 & L_1'=L_1-2L_3'\\
P_5 & 0 & 30 & 0 & -\frac{1}{4} & \frac{3}{2} & 0& 1 & -\frac{3}{4} & 0 & 20 & L_2'=L_2-3L_3'\\
P_1 & 30 & 50 & 1 & \frac{3}{4} & \frac{1}{2}& 0 & 0 & \frac{1}{4} & 0 & 100 & L_3'=\frac{L_3}{4}\\
P_7 & 0 & 120 & 1 & 2 & 1 & 0 & 0 & 0 & 1 & 120 & L_4'=L_4 \\
& z & 1500 & 0 & -\frac{7}{2} & -13 & 0 & 0&\frac{15}{2} & 0 & & L_5'=L_5+30L_3'
\end{matrix}$And then $P_3$ would get in the basis and $P_4$ would go out of the basis.
But I found that the initial tableau should be the following:

View attachment 5130So could you explain how we apply the Simplex method in such a case? (Thinking)

 

[Valkarie]

Yes, of course. To apply the Simplex method in this case, we start by constructing the initial tableau. This includes writing down our objective function and the constraints in a standard form, with slack/surplus variables added if necessary. Then, you will find the basic feasible solution by assigning a value of 0 to all the artificial and slack variables, and then solving for the other variables. Once you have the basic feasible solution, the next step is to use the simplex algorithm to solve the problem. This involves selecting an entering variable, which is the variable that you want to add to the basis, and a leaving variable, which is the variable that you want to remove from the basis. You can determine which variables should enter or leave the basis by finding the maximum ratio between the right-hand side of a constraint and the coefficient of the entering variable. Once you have chosen an entering and leaving variable, you can compute the values of the other variables in the basis by solving the equations formed by those two variables. Each time you make a new iteration, you need to update your tableau. Then, you repeat the process until you reach the optimal solution.