Simplex method max:Z=3x₁+5x₂

Slack variables. A slack variable is a non-negative variable added to the left side of a ≤ constraint to convert it into an equation. It measures the unused amount of the resource. For example, 3x₁ + 2x₂ ≤ 18 becomes 3x₁ + 2x₂ + s₁ = 18 with s₁ ≥ 0. Slack variables have zero coefficient in the objective function and provide the starting basic feasible solution (all original variables = 0).

Step 1: Standard form. Every constraint is of the ≤ type, so add one slack variable to each (s₁, s₂, s₃ ≥ 0) to turn it into an equation. Slack variables have zero cost.

Maximize Z = 3x₁ + 5x₂
subject to
  3x₁ + 2x₂ + s₁ = 18
  x₁ + s₂ = 4
  x₂ + s₃ = 6

Step 2: Initial basic feasible solution. Put x₁, x₂ = 0, so the slack variables are the basic variables: s₁ = 18, s₂ = 4, s₃ = 6. Then Z = 0.

Rules used: the entering variable is the one with the largest positive Cj − Zj; the leaving variable is the one with the smallest non-negative ratio b/column; the solution is optimal when every Cj − Zj ≤ 0.

Step 3: Simplex tables

Table 1

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

Table 2

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

Table 3

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

Step 4: Optimality test. In the last table every Cj − Zj is ≤ 0, so the solution is optimal.

Answer: x₁ = 2, x₂ = 6, and Maximum Z = 36.