Simplex method max:P=x₁+x₂

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 P = x₁ + x₂
subject to
  2x₁ + x₂ + s₁ = 16
  x₁ + s₂ = 6
  x₂ + s₃ = 10

Step 2: Initial basic feasible solution. Put x₁, x₂ = 0, so the slack variables are the basic variables: s₁ = 16, s₂ = 6, s₃ = 10. Then P = 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  1  1  0  0  0         
Basis     CB x₁ x₂ s₁ s₂ s₃  b Ratio
------------------------------------
s₁         0  2  1  1  0  0 16     8
s₂         0  1  0  0  1  0  6     6
s₃         0  0  1  0  0  1 10     -
------------------------------------
          Zj  0  0  0  0  0  0      
       Cj-Zj  1  1  0  0  0         
Entering: x₁   Leaving: s₂   Pivot = 1

Table 2

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

Table 3

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

Table 4

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

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

Answer: x₁ = 3, x₂ = 10, and Maximum P = 13.