Big-M method min:Z=4x₁+2x₂

Step 1: Make the problem ready for the simplex method.

• The problem is a minimisation, so maximise Z* = −Z = −4x₁ − 2x₂. Then Min Z = −(Max Z*).
• Constraint 2 has a negative right side, so multiply by −1: x₁ + x₂ ≥ 21.
• Constraint 1 is ≥: subtract surplus variable s₁ and add artificial variable A₁.
• Constraint 2 is ≥: subtract surplus variable s₂ and add artificial variable A₂.
• Constraint 3 is ≥: subtract surplus variable s₃ and add artificial variable A₃.

Artificial variables carry a cost of −M in the objective, where M is a very large positive number, so that the simplex method drives them out of the basis.

Maximize Z* = −4x₁ − 2x₂ − M·A₁ − M·A₂ − M·A₃
subject to
  3x₁ + x₂ − s₁ + A₁ = 27
  x₁ + x₂ − s₂ + A₂ = 21
  x₁ + 2x₂ − s₃ + A₃ = 30

Step 2: Initial solution. Basic variables: the slack variables (for ≤ rows) and the artificial variables (for ≥ and = rows).

Step 3: Simplex tables. An artificial variable's column is dropped as soon as it leaves the basis. Cj − Zj entries contain M, and the large-M part decides which variable enters.

Table 1

          Cj    -4    -2  0 -M  0 -M  0 -M           
Basis     CB    x₁    x₂ s₁ A₁ s₂ A₂ s₃ A₃    b Ratio
-----------------------------------------------------
A₁        -M     3     1 -1  1  0  0  0  0   27     9
A₂        -M     1     1  0  0 -1  1  0  0   21    21
A₃        -M     1     2  0  0  0  0 -1  1   30    30
-----------------------------------------------------
          Zj   -5M   -4M  M -M  M -M  M -M -78M      
       Cj-Zj -4+5M -2+4M -M  0 -M  0 -M  0           
Entering: x₁   Leaving: A₁   Pivot = 3

Table 2

          Cj -4        -2         0  0 -M  0 -M              
Basis     CB x₁        x₂        s₁ s₂ A₂ s₃ A₃       b Ratio
-------------------------------------------------------------
x₁        -4  1       1/3      -1/3  0  0  0  0       9    27
A₂        -M  0       2/3       1/3 -1  1  0  0      12    18
A₃        -M  0       5/3       1/3  0  0 -1  1      21  63/5
-------------------------------------------------------------
          Zj -4 -4/3-7/3M  4/3-2/3M  M -M  M -M -36-33M      
       Cj-Zj  0 -2/3+7/3M -4/3+2/3M -M  0 -M  0              
Entering: x₂   Leaving: A₃   Pivot = 5/3

Table 3

          Cj -4 -2         0  0 -M         0                   
Basis     CB x₁ x₂        s₁ s₂ A₂        s₃            b Ratio
---------------------------------------------------------------
x₁        -4  1  0      -2/5  0  0       1/5         24/5    24
A₂        -M  0  0       1/5 -1  1       2/5         18/5     9
x₂        -2  0  1       1/5  0  0      -3/5         63/5     -
---------------------------------------------------------------
          Zj -4 -2  6/5-1/5M  M -M  2/5-2/5M -222/5-18/5M      
       Cj-Zj  0  0 -6/5+1/5M -M  0 -2/5+2/5M                   
Entering: s₃   Leaving: A₂   Pivot = 2/5

Table 4

          Cj -4 -2    0    0  0    
Basis     CB x₁ x₂   s₁   s₂ s₃   b
-----------------------------------
x₁        -4  1  0 -1/2  1/2  0   3
s₃         0  0  0  1/2 -5/2  1   9
x₂        -2  0  1  1/2 -3/2  0  18
-----------------------------------
          Zj -4 -2    1    1  0 -48
       Cj-Zj  0  0   -1   -1  0    

Step 4: Optimality. All Cj − Zj ≤ 0 and no artificial variable remains in the basis, so the solution is optimal and feasible.

Max Z* = −48, hence Min Z = 48.

Answer: x₁ = 3, x₂ = 18, and Minimum Z = 48.