Duality LPP min:Z=8x₁+9x₂

Duality. Every linear programming problem (the primal) has an associated problem (the dual) built from the same data: the rows of one are the columns of the other. For a minimisation primal with ≥ constraints, the dual is a maximisation with ≤ constraints; each primal constraint gives one dual variable and each primal variable gives one dual constraint. The duality theorem states that if one problem has an optimal solution, so has the other, and their optimal objective values are equal. The primal solution can be read from the Cj − Zj row of the final dual table.

Step 1: Write the dual. For the primal (minimisation, all constraints ≥), the dual is:

Primal: Minimize Z = 8x₁ + 9x₂
  subject to  x₁ + 3x₂ ≥ 4
              2x₁ + x₂ ≥ 5
              x₁, x₂ ≥ 0

Dual:   Maximize W = 4y₁ + 5y₂
  subject to  y₁ + 2y₂ ≤ 8
              3y₁ + y₂ ≤ 9
              y₁, y₂ ≥ 0

Here y₁, y₂ are the dual variables, one for each primal constraint.

Step 2: Standard form of the dual. Add slack variables s₁, s₂ (one per dual constraint). Since all right sides are positive, the slack variables give the starting basis.

Maximize W = 4y₁ + 5y₂
subject to
  y₁ + 2y₂ + s₁ = 8
  3y₁ + y₂ + s₂ = 9

Step 3: Simplex tables for the dual

Table 1

          Cj  4  5  0  0        
Basis     CB y₁ y₂ s₁ s₂ b Ratio
--------------------------------
s₁         0  1  2  1  0 8     4
s₂         0  3  1  0  1 9     9
--------------------------------
          Zj  0  0  0  0 0      
       Cj-Zj  4  5  0  0        
Entering: y₂   Leaving: s₁   Pivot = 2

Table 2

          Cj   4  5    0  0         
Basis     CB  y₁ y₂   s₁ s₂  b Ratio
------------------------------------
y₂         5 1/2  1  1/2  0  4     8
s₂         0 5/2  0 -1/2  1  5     2
------------------------------------
          Zj 5/2  5  5/2  0 20      
       Cj-Zj 3/2  0 -5/2  0         
Entering: y₁   Leaving: s₂   Pivot = 5/2

Table 3

          Cj  4  5     0    0   
Basis     CB y₁ y₂    s₁   s₂  b
--------------------------------
y₂         5  0  1   3/5 -1/5  3
y₁         4  1  0  -1/5  2/5  2
--------------------------------
          Zj  4  5  11/5  3/5 23
       Cj-Zj  0  0 -11/5 -3/5   

Step 4: Read the answer. All Cj − Zj ≤ 0, so the dual is solved: y₁ = 2, y₂ = 3, Max W = 23.

By the duality theorem, Min Z = Max W. The values of the primal variables are the numbers (without sign) in the Cj − Zj row under the slack columns: x₁ = 11/5 (under s₁), x₂ = 3/5 (under s₂).

Check: Z = 8(11/5) + 9(3/5) = 23.

Answer: x₁ = 11/5, x₂ = 3/5, Minimum Z = 23.