Answer to Question #185367 in Operations Research for Maha

Question

Minimize Z = 0.2x1+ O.lx2 + 0.3x3

Subject to constraint

0. Sx1+ 0.2x2 + 0.7x3 = 0.420

0. 3x1+ 0.2x2 + O.Sx3 ;:::: 0.280

Xv Xz, X3 ;:::: 0.

(i) W1ite second initial basic solution of the p1imal problem using M-Method.

(ii) Solve the dual from optimal Primal table calculated in (i).

Answer 1

(i) $Minimize\ \ Z=0.2x_1+0.1x_2+0.3x_3\\$

Subject to constraint

$0. 5x_1+ 0.2x_2 + 0.7x_3 = 0.420\\ 0. 3x_1+ 0.2x_2 + 0.5x_3 \geq 0.280\\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 artificial variable A1

2. As the constraint-2 is of type '≥' we should subtract surplus variable S1 and add artificial variable A2

$\text{After introducing surplus, artificial variables}\\ Min\ Z = 0.2 x_1 + 0.1 x_2 + 0.3 x_3 + 0 S_1 + M A_1 + M A_2\\ subject \ to\\ 0.5 x_1 + 0.2 x_2 + 0.7 x_3 + A_1 = 0.42\\ 0.3 x_1 + 0.2 x_2 + 0.5 x_3 - S_1 + A_2 = 0.28\\ and\ \ x_1,x_2,x_3,S_1,A_1,A_2≥0$

Positive maximum $Z_j-C_j$  is 1.2M-0.3 and its column index is 3. So, the entering variable is x3.

Minimum ratio is 0.56 and its row index is 2. So, the leaving basis variable is A2.

∴ The pivot element is 0.5.

Entering =x3, Departing =A2, Key Element =0.5

Positive maximum Zj-Cj is 1.4M-0.6 and its column index is 4. So, the entering variable is S1.

Minimum ratio is 0.02 and its row index is 1. So, the leaving basis variable is A1.

∴ The pivot element is 1.4.

Entering =S1, Departing =A1, Key Element =1.4

Positive maximum Zj-Cj is 0.0143 and its column index is 1. So, the entering variable is x1.

Minimum ratio is 0.35 and its row index is 1. So, the leaving basis variable is S1.

∴ The pivot element is 0.0571.

Entering =x1, Departing =S1, Key Element =0.0571

Since all Zj-Cj≤0

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

x1=0.35,x2=0,x3=0.35

Min Z=0.175

(ii) Dual is :

$Max\ Z = 0.42 y _1 + 0.28 y_2\\ subject\ to\ \\ 0.5 y _1 + 0.3 y_2 ≤ 0.2\\ 0.2 y_1 + 0.2 y_2 ≤ 0.1\\ 0.7 y_1 + 0.5 y_2 ≤ 0.3\\\\ and\ y _2≥0;\ y _1\ \ \ \text{ unrestricted in sign}\\ Since \ y _1 \ is \ unrestricted\ in\ sign, introduce\ the\ non-negative\ variables\ y_1′,y_1′′\\ so \ that\ y_1=y_1′-y_1′′;\ y_1′,y_1′′≥0.$

The standard form of the LP problem becomes

$Max\ Z = 0.42 y _1′ - 0.42 y_1′′ + 0.28 y_2\\ subject\ to\\ 0.5 y_1′ - 0.5 y_1′′ + 0.3 y_2 ≤ 0.2\\ 0.2 y_1′ - 0.2 y_1′′ + 0.2 y_2 ≤ 0.1\\ 0.7 y_1′ - 0.7 y_1′′ + 0.5 y_2 ≤ 0.3\\ and \ \ y_1′,y_1′′,y_2≥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 S1

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

3. As the constraint-3 is of type '≤' we should add slack variable S3

After introducing slack variables

$Max \ Z = 0.42 y_1′ - 0.42 y_1′′ + 0.28 y_2 + 0 S_1 + 0 S_2 + 0 S_3\\ subject\ to\\ 0.5 y_1′ - 0.5 y_1′′ + 0.3 y_2 + S_1 = 0.2\\ 0.2 y_1′ - 0.2 y_1′′ + 0.2 y_2 + S_2 = 0.1\\ 0.7 y_1′ - 0.7 y_1′′ + 0.5 y_2 + S_3 = 0.3\\ and\ \ y_1′,y_1′′,y_2,S_1,S_2,S_3≥0$

Negative minimum Zj-Cj is -0.42 and its column index is 1. So, the entering variable is y1′.

Minimum ratio is 0.4 and its row index is 1. So, the leaving basis variable is S1.

∴ The pivot element is 0.5.

Entering =y1′, Departing =S1, Key Element =0.5

Negative minimum Zj-Cj is -0.028 and its column index is 3. So, the entering variable is y2.

 Minimum ratio is 0.25 and its row index is 2. So, the leaving basis variable is S2.

∴ The pivot element is 0.08.

Entering = y2, Departing =S2, Key Element =0.08

Since all $Z_j-C_j≥0$

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

$y_1′=0.25,y_1′′=0,y_2=0.25$

Max Z=0.175