Question

Consider the following primal problem;

minimize x₀=20x₁+30x₂+50x₃+40x₄

subject to:

4x₁+6x₂+x₃+2x₄≥12

2x₁+x₂+6x₃+5x₄≥14

x₁+2x₂+4x₃+3x₄≥8

x_i≥0,i=1,2,3,4

Use simplex method to solve the dual of the above primal problem

Answer 1

$MIN \ Z_x = 20 x_1 + 30 x_2 + 50 x_3 + 40 x_4\\ Subject \ to:\\ 4 x_1 + 6 x_2 + x_3 + 2 x_4 ≥ 12\\ 2 x_1 + x_2 + 6 x_3 + 5 x_4 ≥ 14\\ x_1 + 2 x_2 + 4 x_3 + 3 x_4 ≥ 8\\ and \ x_1,x_2,x_3,x_4≥0;$

$Dual \ is \ (Solution \ steps \ of \ Dual\ by\ BigM \ method)\\ MAX\ Z_y = 12 y_1 + 14 y_2 + 8 y_3\\ Subject\ to:\\ 4 y_1 + 2 y_2 + y_3 ≤ 20\\ 6 y_1 + y_2 + 2 y_3 ≤ 30\\ y_1 + 6 y_2 + 4 y_3 ≤ 50\\ 2 y_1 + 5 y_2 + 3 y_3 ≤ 40\\ and\ y_1,y_2,y_3≥0;\\$

$Max: Z=12 y_{1}+14 y_{2}+8 y_{3} \\subject \ to: 4 y_{1}+2 y_{2}+y_{3} \leq 20 \\ 6 y_{1}+y_{2}+2 y_{3} \leq 30 \\y_{1}+6 y_{2}+4 y_{3} \leq 50 \\ 2 y_{1}+5 y_{2}+3 y_{3} \leq 40 \\ and \ y_{1}, y_{2}, y_{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 add slack variable $S_3$

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

After introducing slack variables

$\operatorname{Max} Z=12 y_{1}+14 y_{2}+8 y_{3}+0 S_{1}+0 S_{2}+0 S_{3}+0 S_{4} \\ subject \ to:\\ \begin{aligned} 4 y_{1}+2 y_{2}+y_{3}+S_{1} =20 \\ 6 y_{1}+y_{2}+2 y_{3}+S_{2} =30 \\ y_{1}+6 y_{2}+4 y_{3} +S_3=50 \\ 2 y_{1}+5 y_{2}+3 y_{3} +S_{4} =40\\ \end{aligned}\\ \text { and } y_{1}, y_{2}, y_{3}, S_{1}, S_{2}, S_{3}, S_{4} \geq 0$

The negative minimum Zj-Cj is -14 and its column index is 2. So, the entering variable is $y_2$ .

The minimum ratio is 8 and its row index is 4. So, the leaving basis variable is $S_4$ .

∴ The pivot element is 5.

Entering =$y_2$ , Departing =$S_4$ , Key Element =5

The negative minimum Zj-Cj is -6.4 and its column index is 1. So, the entering variable is y1.

The minimum ratio is 1.25 and its row index is 1. So, the leaving basis variable is S1.

 ∴ The pivot element is 3.2.

Entering =y1, Departing =S1, Key Element =3.2

Since all Zj-Cj≥0

Hence, the optimal solution arrives with value of variables as :

$y_1=1.25,y_2=7.5,y_3=0$

Max Z=120