Simplex method max:P=20x₂−5x₁

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

Maximize P = −5x₁ + 20x₂
subject to
  −2x₁ + 10x₂ + s₁ = 5
  2x₁ + 5x₂ + s₂ = 10

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

Table 2

          Cj   -5 20    0  0     
Basis     CB   x₁ x₂   s₁ s₂    b
---------------------------------
x₂        20 -1/5  1 1/10  0  1/2
s₂         0    3  0 -1/2  1 15/2
---------------------------------
          Zj   -4 20    2  0   10
       Cj-Zj   -1  0   -2  0     

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

Answer: x₁ = 0, x₂ = 1/2, and Maximum P = 10.