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₁.

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₁
subject to
  x₁ + 2x₂ + s₁ = 18
  2x₁ + x₂ − s₂ + A₁ = 21

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

Table 2

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

Table 3

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

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.