Question

Solve the following LPP by the two-phase simplex method:
Maximise Z=x_1+2x_2+3x_3
Subject to
x_1+2x_2+3x_3=15
2x_1+x_2+5x_3=20
x_1+2x_2+x_3+x_4=10
x_1,x_2,x_3,x_4≥0

Answer 1

1) Introduce slack variables $x_5, x_6, x_7,$ for the first, the second, and the third equation. then write the function in the form

$$Z = - Mx_5 - Mx_6 - Mx_7 → max ,$$

express the slack variables:

$$x_5 = 15-x_1-2x_2-3x_3$$ $$x_6 = 20-2x_1-x_2-5x_3$$ $$x_7 = 10-x_1-2x_2-x_3-x_4$$

Substitute them to the function:

$$Z= 4Mx_1+5Mx_2+9Mx_3+Mx_4-45M→ max ,$$

After the first phase (common simplex-method with optimal solution) has ended at the following matrix:

$$\begin{matrix} 0 & -1 & 0 & 0& 0 \\ 15/7 & -1/7 & 0 & 0& 0 \\ 25/7 & 3/7& 0 & 0 & 0 \\ 15/7 & 6/7 & 0 & 0 & 0\\ 0 & 0 & -1 & 0 &0 \\ 0 & 0 & 0 & -1 & 0 \\ 0 & 0 & 0 & 0 & -1 \\ 0 & 0 & 0 & 0 & 0 \\ \end{matrix}$$

Express the basic variables:

$$x_2 = 15/7+1/7x_1, \\ x_3 = 25/7-3/7x_1.$$

Substitute them to the function:

$$Z=x_1 + 2(15/7+1/7x_1) + 3(25/7-3/7x_1)=15.$$

Finally we get the correct matrix after removing the rows with slack variables (Phase II):

$$\begin{matrix} 0 & -1 & 0 & 0& 0 \\ 15/7 & -1/7 & 0 & 0& 0 \\ 25/7 & 3/7& 0 & 0 & 0 \\ 15/7 & 6/7 & 0 & 0 & 0\\ 15 & 0 & 0 & 0 &0 \end{matrix}$$

The two-phase simplex method gives:

$$x_1 = 0 \\ x_2 = 15/7 \\ x_3 = 25/7 \\ Z = 2•15/7 + 3•25/7 + 0•15/7 = 15.$$