Linear programming problem

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.