Question

Solve the following linear programming model using the simplex method:

maximize Z = 100x1 + 20x2 + 60x3

subject to

x3 smaller than or equal to 40

2x1 + 2x2 + 2x3 smaller than or equal to 100

3x1 + 5x2 smaller than or equal to 60

x1, x2, x3 bigger than or equal to 0

Answer 1

Solution:

$\operatorname{Max} Z=100 x_{1}+20 x_{2}+60 x_{3}$

subject to

$\begin{aligned} x_{3} & \leq 40 \\ 2 x_{1}+2 x_{2}+2 x_{3} & \leq 100 \end{aligned}$

$3 x_{1}+5 x_{2} \quad \geq 60\\ and\ x_{1}, x_{2}, x_{3} \geq 0$

The problem is converted to canonical form by adding slack, surplus, and artificial variables as appropriate

1. As the constraint-1 is of type '≤' we should add slack variable $S_1$

2. As the constraint-2 is of type '≤' we should add slack variable $S_2$

3. As the constraint-3 is of type '≥' we should subtract surplus variable $S_3$  and add artificial variable $A_1$

After introducing slack, surplus, artificial variables

$\operatorname{Max} Z=100 x_{1}+20 x_{2}+60 x_{3}+0 S_{1}+0 S_{2}+0 S_{3}-M A_{1}$

subject to

$x_{3}+S_{1} =40\\ 2 x_{1}+2 x_{2}+2 x_{3} S =100\\ 3 x_{1}+5 x_{2} \quad-S_{3}+A_{1}=60\\ and\ x_{1}, x_{2}, x_{3}, S_{1}, S_{2}, S_{3}, A_{1} \geq 0$

Negative minimum $Z_{j}-C_{j}$ is $-5 M-20$ and its column index is 2 . So, the entering variable is $x_{2}$

The minimum ratio is 12 and its row index is 3. So, the leaving basis variable is $A_{1}$ .

Therefore, the pivot element is 5 .

Entering $=x_{2}$ , Departing $=A_{1}$ , Key Element =5

$R_{3}(\mathrm{new})=R_{3}(\mathrm{old}) \div 5$

$R_{1}( new )=R_{1}( old )$

$R_2(new)=R_2(old)-2R_3(new)$

Similarly, we have iteration 2, 3, 4, and 5 as follows:

Since all $Z_j-C_j≥0$

Hence, optimal solution is arrived with value of variables as :

$x_1=50,x_2=0,x_3=0$

Max Z=5000