Skip to main content

Big-M method max:Z=4x₁+5x₂

Short answer

Using the Big-M method, the optimal solution is obtained after introducing artificial variable A1 for the ≥ constraint. The maximum Z is 25, achieved at x1 = 0, x2 = 5.

Solve the following linear programming problem by using the Big-M method: Maximize Z = 4x₁ + 5x₂ subject to x₁ + x₂ ≤ 5, 3x₁ + 10x₂ ≥ 30, x₁, x₂ ≥ 0.

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 Z = 4x₁ + 5x₂ − M·A₁
subject to
  x₁ + x₂ + s₁ = 5
  3x₁ + 10x₂ − 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     5  0  0 -M           
Basis     CB   x₁    x₂ s₁ s₂ A₁    b Ratio
-------------------------------------------
s₁         0    1     1  1  0  0    5     5
A₁        -M    3    10  0 -1  1   30     3
-------------------------------------------
          Zj  -3M  -10M  0  M -M -30M      
       Cj-Zj 4+3M 5+10M  0 -M  0           
Entering: x₂   Leaving: A₁   Pivot = 10

Table 2

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

Table 3

          Cj  4  5     0    0            
Basis     CB x₁ x₂    s₁   s₂     b Ratio
-----------------------------------------
x₁         4  1  0  10/7  1/7  20/7    20
x₂         5  0  1  -3/7 -1/7  15/7     -
-----------------------------------------
          Zj  4  5  25/7 -1/7 155/7      
       Cj-Zj  0  0 -25/7  1/7            
Entering: s₂   Leaving: x₁   Pivot = 1/7

Table 4

          Cj  4  5  0  0   
Basis     CB x₁ x₂ s₁ s₂  b
---------------------------
s₂         0  7  0 10  1 20
x₂         5  1  1  1  0  5
---------------------------
          Zj  5  5  5  0 25
       Cj-Zj -1  0 -5  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₁ = 0, x₂ = 5, and Maximum Z = 25.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Mathematics III chapter 5 questions →