Big-M method max:P=2x₁+5x₂

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

• Constraint 1 is ≤: add slack variable s₁.
• 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 P = 2x₁ + 5x₂ − M·A₁ − M·A₂
subject to
  x₁ + 2x₂ + s₁ = 18
  2x₁ + x₂ − s₂ + A₁ = 21
  x₁ + x₂ − s₃ + A₂ = 10

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    2    5  0  0 -M  0 -M           
Basis     CB   x₁   x₂ s₁ s₂ A₁ s₃ A₂    b Ratio
------------------------------------------------
s₁         0    1    2  1  0  0  0  0   18    18
A₁        -M    2    1  0 -1  1  0  0   21  21/2
A₂        -M    1    1  0  0  0 -1  1   10    10
------------------------------------------------
          Zj  -3M  -2M  0  M -M  M -M -31M      
       Cj-Zj 2+3M 5+2M  0 -M  0 -M  0           
Entering: x₁   Leaving: A₂   Pivot = 1

Table 2

          Cj  2   5  0  0 -M     0           
Basis     CB x₁  x₂ s₁ s₂ A₁    s₃    b Ratio
---------------------------------------------
s₁         0  0   1  1  0  0     1    8     8
A₁        -M  0  -1  0 -1  1     2    1   1/2
x₁         2  1   1  0  0  0    -1   10     -
---------------------------------------------
          Zj  2 2+M  0  M -M -2-2M 20-M      
       Cj-Zj  0 3-M  0 -M  0  2+2M           
Entering: s₃   Leaving: A₁   Pivot = 2

Table 3

          Cj  2    5  0    0  0           
Basis     CB x₁   x₂ s₁   s₂ s₃    b Ratio
------------------------------------------
s₁         0  0  3/2  1  1/2  0 15/2     5
s₃         0  0 -1/2  0 -1/2  1  1/2     -
x₁         2  1  1/2  0 -1/2  0 21/2    21
------------------------------------------
          Zj  2    1  0   -1  0   21      
       Cj-Zj  0    4  0    1  0           
Entering: x₂   Leaving: s₁   Pivot = 3/2

Table 4

          Cj  2  5    0    0  0   
Basis     CB x₁ x₂   s₁   s₂ s₃  b
----------------------------------
x₂         5  0  1  2/3  1/3  0  5
s₃         0  0  0  1/3 -1/3  1  3
x₁         2  1  0 -1/3 -2/3  0  8
----------------------------------
          Zj  2  5  8/3  1/3  0 41
       Cj-Zj  0  0 -8/3 -1/3  0   

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

Answer: x₁ = 8, x₂ = 5, and Maximum P = 41.