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

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

• Constraint 1 is ≥: subtract surplus variable s₁ and add artificial variable A₁.
• Constraint 2 is ≤: add slack variable s₂.
• Constraint 3 is ≤: add slack variable s₃.

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 F = 2x₁ + x₂ − M·A₁
subject to
  2x₁ − x₂ − s₁ + A₁ = 2
  x₁ − x₂ + s₂ = 2
  x₁ + x₂ + s₃ = 4

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

Table 2

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

Table 3

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

Table 4

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

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

Answer: x₁ = 3, x₂ = 1, and Maximum F = 7.