can I get help in solving this equation using simplex method big-M method

Question

Objective:

$\max Z= 100x_1+300x_2+400x_3$

s.t. $10x_1+20x_2+30x_3≤1600$

$\;\,\quad10x_1+15x_2+20x_3≤1500$

$\;\,\quad x_2+x_3≤50$

$\;\,\quad x_1+x_2+x_3=70$

$\;\,\quad x_1,x_2,x_3≥0$

Answer 1

$\max Z= 100x_1+300x_2+400x_3$

s.t. $10x_1+20x_2+30x_3≤1600$

$\;\,\quad10x_1+15x_2+20x_3≤1500$

$\;\,\quad x_2+x_3≤50$

$\;\,\quad x_1+x_2+x_3=70$

$\;\,\quad x_1,x_2,x_3≥0$

You have to convert it into the standard form by adding slack variables. So it becomes: $\max Z= 100x_1+300x_2+400x_3$

s.t. $10x_1+20x_2+30x_3 +s_1 = 600$

$\;\,\quad10x_1+15x_2+20x_3 +s_2 =1500$

$\;\,\quad x_2+x_3+s_3=50$

$\;\,\quad x_1+x_2+x_3=70$

$\;\,\quad x_1,x_2,x_3,s_1,s_2,s_3≥0$

$c^T=[100, 300, 400, 0, 0, 0], b=[1600, 1500, 50, 70]$

$$A=\begin{bmatrix} 10 & 20 & 30 & 1 & 0 & 0\\ 10 & 15 & 20 & 0 & 1 & 0\\ 0 & 1 & 1 & 0 & 0 & 1\\ 1 & 1 & 1 & 0 & 0 & 0 \end{bmatrix}$$ The basics columns are these that construct the identity matrix, the columns $4,5,6$ of the matrix $A$, are the three first columns of the identity matrix $I_{4 \times 4}$. So you have to add the last column: $$A=\begin{bmatrix} 10 & 20 & 30 & 1 & 0 & 0 & 0\\ 10 & 15 & 20 & 0 & 1 & 0 & 0\\ 0 & 1 & 1 & 0 & 0 & 1 & 0\\ 1 & 1 & 1 & 0 & 0 & 0 & 1 \end{bmatrix}$$ So $c^T=[100, 300, 400, 0, 0, 0, M], b=[1600, 1500, 50, 70]$

Base: $B=[P_4 P_5 P_6 P_7]$

The tableau is:

$$\begin{matrix} B & c_B & b & P_1 & P_2 & P_3 & P_4 & P_5 & P_6 & P_7 & \Theta \\ P_4 & 0 & 1600 & 10 & 20 &30 & 1 & 0 & 0 & 0 & \frac{1600}{30} & L_1\\ P_5 & 0 & 1500 & 10 & 15 & 20 & 0 & 1 & 0 & 0 & \frac{1500}{20} & L_2\\ P_6 & 0 & 50 & 0& 1 & 1 & 0 & 0 & 1 & 0 & 50 & L_3\\ P_7 & M & 70 & 1& 1 & 1 & 0 & 0 & 0 & 1 & 70 & L_4\\ & z & 70M &M-100 & M-300 & M-400 & 0 & 0 & 0&0 & & L_5 \end{matrix}$$

$M$ is a negative number.

To complete the column $\Theta$: you have to find the smallest number of the line $z$. Let $P_i$ is the column which number at the last line is the smallest, and then $\Theta=\frac{b}{P_i}$.

The smallest number at the last line is: $M-400$, so $\Theta=\frac{b}{P_3}$

The smallest number at the column $\Theta$ is $50$. So the smallest number of the last line($z$) is the column $P_3$ and the smallest number of the column $\Theta$ is the line $L_3$ that correspond to the line $P_6$, so the column $P_6$ gets out of the base and the column $P_3$ gets in.

The pivot is the element at the column $P_3$ and at the line $L_3$

So $L_3'=L_3/1$, $L_1'=L_1-30 L_3'$, $L_2'=L_2-20 L_3'$, $L_4'=L_4-L_3'$

$\begin{matrix} B & c_B & b & P_1 & P_2 & P_3 & P_4 & P_5 & P_6 & P_7 & \Theta \\ P_4 & 0 &100& 10 & -10 & 0 & 1 & 0 & -30 & 0 & &L_1'\\ P_5 & 0 &500&10 &-5 & 0 & 0 & 1 &-20 &0 & &L_2'\\ P_3 & 400 & 50& 0 & 1 & 1 & 0 & 0 & 1 & 0 & &L_3'\\ P_7 & M & 20&1 & 0 & 0 &0 & 0 & -1 & 1 & &L_4'\\ & z & 400 \cdot 50+M \cdot 20 & M-100 & 400-300 & 400-400 &0 &0 &400-M & M-M & &L_5' \end{matrix}$

So it becomes: $$\begin{matrix} B & c_B & b & P_1 & P_2 & P_3 & P_4 & P_5 & P_6 & P_7 & \Theta \\ P_4 & 0 &100& 10 & -10 & 0 & 1 & 0 & -30 & 0 & 10 &L_1'\\ P_5 & 0 &500&10 &-5 & 0 & 0 & 1 &-20 &0 & 50 &L_2'\\ P_3 & 400 & 50& 0 & 1 & 1 & 0 & 0 & 1 & 0 & - &L_3'\\ P_7 & M & 20&1 & 0 & 0 &0 & 0 & -1 & 1 & 20 &L_4'\\ & z & 20000+20M & M-100 & 100 & 0 &0 &0 &400-M & 0 & &L_5' \end{matrix}$$

(The smallest number at the last line is $M-100$, so $\Theta=\frac{b}{P_1}$) The smallest number at the column $\Theta$ is $10$ that corresponds to $P_4$, so the column $P_4$ gets out of the base and the base $P_1$ gets in.

$L_1''=L_1'/10$, $L_2''=L_2'-10L_1''$, $L_3''=L_3'$, $L_4''=L_4'-L_1''$

So the tableau is: $$\begin{matrix} B & c_B & b & P_1 & P_2 & P_3 & P_4 & P_5 & P_6 & P_7 & \Theta=\frac{b}{P_6} \\ P_1 & 100 &10& 1 & -1 & 0 & 1/10 & 0 & -3 & 0 & -&L_1''\\ P_5 & 0 &400&0 &5 & 0 & -1 & 1 &10 &0 & 40 &L_2''\\ P_3 & 400 & 50& 0 & 1 & 1 & 0 & 0 & 1 & 0 & 50 &L_3''\\ P_7 & M & 10&0 & 1 & 0 &-1/10 & 0 & 2 & 1 & 5 &L_4''\\ & z & 21000+10M & 0 & M & 0 &10-\frac{M}{10} &0 &100+2M & 0 & &L_5'' \end{matrix}$$ The column $P_7$ gets out of the base and the column $P_6$ gets in.

$L_4'''=L_4''/2$, $L_1'''=L_1''+3L_4'''$, $L_2'''=L_2''-10L_4'''$, $L_3'''=L_3''-L_4'''$

So the next tableau is the following (Since there is no more column in the base with the coeffient $M$ ($P_7$) you don't have to fill this column): $$\begin{matrix} B & c_B & b & P_1 & P_2 & P_3 & P_4 & P_5 & P_6 & P_7 & \Theta=\frac{b}{P_6} \\ P_1 & 100 &25& 1 & 1/2 & 0 & -1/20 & 0 & 0 & & 50&L_1'''\\ P_5 & 0 &350&0 &0 & 0 & -1/2 & 1 &0 & & - &L_2'''\\ P_3 & 400 & 45& 0 & 1/2 & 1 & 1/20 & 0 & 0 & & 90 &L_3'''\\ P_6 & 0 & 5&0 & 1/2 & 0 &-1/20 & 0 & 1 & & 5/2 &L_4'''\\ & z & 2500+45 \cdot 400 & 0 & -50 & 0 &15 &0 &0 & & &L_5''' \end{matrix}$$

Now at the last line you have a negative element. You apply one more time the Simplex method so that you have only elements $\geq 0$.

$L_4''''=2L_4'''$, $L_1''''=L_1'''-\frac{1}{2}L_4''''$, $L_2''''=L_2'''$, $L_3''''=L_3'''-\frac{1}{2}L_4''''$

The last tableau is:

$$\begin{matrix} B & c_B & b & P_1 & P_2 & P_3 & P_4 & P_5 & P_6 & P_7 & \Theta=\frac{b}{P_6} \\ P_1 & 100 &20& 1 & 0 & 0 & 0 & 0 & -1 & & &L_1''''\\ P_5 & 0 &350&0 &0 & 0 & -1/2 & 1 &0 & & &L_2''''\\ P_3 & 400 & 40& 0 & 0 & 1 & 1/10 & 0 & -1 & & &L_3''''\\ P_2 & 300 & 10&0 & 1 & 0 &-1/10 & 0 & 2 & & &L_4''''\\ & z & 21000 & 0 & 0 & 0 &10 &0 &100 & & &L_5'''' \end{matrix}$$

Now we have finished. At the last line all the elements are $\geq 0$, and it is only $=0$ at those columns that are in the base.

So which is now the solution? Which is the maximum? Can you find these?