Simplex method max:P=−x₁+2x₂

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₁ + 2x₂
subject to
  −x₁ + x₂ + s₁ = 2
  −x₁ + 3x₂ + s₂ = 12
  x₁ − 4x₂ + s₃ = 4

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

Table 2

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

Table 3

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

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

Answer: x₁ = 3, x₂ = 5, and Maximum P = 7.