Duality & Sensitivity Testing

Dual Simplex Method

Example

Minimize z = 80x₁ + 100x₂

subject to

80x₁ + 60x₂ ³ 1500
20x₁ + 90x₂ ³ 1200

x₁, x₂ ³ 0

Solution.

Minimize z = 80x₁ + 100x₂

Multiplying the constraints by -1 on both sides
-80x₁ - 60x₂ £ -1500
-20x₁ - 90x₂ £ -1200

After adding slack variables, the constraints are
-80x₁ - 60x₂ + x₃ = -1500
-20x₁ - 90x₂ + x₄ = -1200

Where x₃ and x₄ are slack variables.

Initial basic feasible solution

Substituting x₁ = 0, x₂ = 0, z = 0

This gives the solution values as
x₃ = -1500, x₄ = -1200

The initial simplex table is exhibited below.

Table 1

Key Row :
Min { X_B1, X_B2} = Min ( -1500, -1200) = -1500
So x₃ row is the key row.

Key Column:

Min

z1 - c1 -------- a11

,

z2 - c2 -------- a12

Min

-80 ------- -80

,

-100 -------- -60

Min(1, 5/3) = 1
So column under x₁ becomes the key column.
Pivot element = - 80.
Therefore, x₃ departs & x₁ enters.

Table 2

Key row = x₄ row as it has the only negative value under the X_B column.
Key column = x₂ column.
Pivot element = -75.
x₄ departs & x₂ enters.

Table 3

The values for x₁ & x₂ are 21/2 & 11 respectively.
The associated objective function value is
z = 80 X 21/2 + 100 X 11 = 1940.