Simplex method max:P=30x₁+x₂

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 = 30x₁ + x₂
subject to
  2x₁ + x₂ + s₁ = 10
  x₁ + 3x₂ + s₂ = 10

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

Table 2

          Cj 30   1    0  0    
Basis     CB x₁  x₂   s₁ s₂   b
-------------------------------
x₁        30  1 1/2  1/2  0   5
s₂         0  0 5/2 -1/2  1   5
-------------------------------
          Zj 30  15   15  0 150
       Cj-Zj  0 -14  -15  0    

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

Answer: x₁ = 5, x₂ = 0, and Maximum P = 150.