Answer to Question #243653 in Operations Research for Akki

Question

Solve the following question through simplex method
Max Z= 4X1 + 3X2
S+C
2X1 +X2 < 1000
X1 + X2 < 800
X1< 400
X2< 700
X1, X2 >0

Answer 1

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 add slack variable $S_3$

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

After introducing slack variables

$\text{Max } z=4x_1+3x_2+0S_1+0S_2+0S_3+0S_4\\ \text{Subject to }\\ ~~2x_1+x_2+S_1~~~~~~~~~~~~~~~~~~~~~~~~=1000\\ ~~~~x_1+x_2~~~~~~~~+S_2~~~~~~~~~~~~~~~~=800\\ ~~~~x_1~~~~~~~~~~~~~~~~~~~~~~~~~+S_3~~~~~~~~=400\\ ~~~~~~~~~~~~~x_2~~~~~~~~~~~~~~~~~~~~~~~~+S_4=700\\ \text{All variables nonnegative}$

Negative minimum $z_j-c_j$  is -4 and its column index is 1. So, the entering variable is $x_1$ .

Minimum ratio is 400 and its row index is 3. So, the leaving basis variable is $S_3$ .

∴ The pivot element is 1.

$R_3(new)=R_3(old), R_1(new)=R_1(old)-2R_3(new)\\ R_2(new)=R_2(old)-R_3(new), R_4(new)=R_4(old)$

Negative minimum $z_j-c_j$  is -3 and its column index is 2. So, the entering variable is $x_2$ .

Minimum ratio is 200 and its row index is 1. So, the leaving basis variable is $S_1$ .

∴ The pivot element is 1.

$R_1(new)=R_1(old), R_2(new)=R_2(old)-R_1(new)\\ R_3(new)=R_3(old), R_4(new)=R_4(old)-R_1(new)$

Negative minimum $z_j-c_j$  is -2 and its column index is 5. So, the entering variable is $S_3$ .

Minimum ratio is 200 and its row index is 2. So, the leaving basis variable is $S_2$ .

∴ The pivot element is 1.

$R_2(new)=R_2(old), R_1(new)=R_1(old)+2R_2(new)\\ R_3(new)=R_3(old)-R_2(new), R_4(new)=R_4(old)-2R_2(new)$

Since all $z_j-c_j\geq0$

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

$x_1=200,x_2=600$

$Max~z=2600$