Simplex method max:Z=4x+3y

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

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

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

Table 2

          Cj 4   3  0  0  0   0        
Basis     CB x   y s₁ s₂ s₃  s₄ b Ratio
---------------------------------------
s₁         0 0   2  1  0  0  -1 2     1
s₂         0 0 5/2  0  1  0 1/2 5     2
s₃         0 0   2  0  0  1   0 5   5/2
x          4 1 1/2  0  0  0 1/2 2     4
---------------------------------------
          Zj 4   2  0  0  0   2 8      
       Cj-Zj 0   1  0  0  0  -2        
Entering: y   Leaving: s₁   Pivot = 2

Table 3

          Cj 4 3    0  0  0    0    
Basis     CB x y   s₁ s₂ s₃   s₄   b
------------------------------------
y          3 0 1  1/2  0  0 -1/2   1
s₂         0 0 0 -5/4  1  0  7/4 5/2
s₃         0 0 0   -1  0  1    1   3
x          4 1 0 -1/4  0  0  3/4 3/2
------------------------------------
          Zj 4 3  1/2  0  0  3/2   9
       Cj-Zj 0 0 -1/2  0  0 -3/2    

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

Answer: x = 3/2, y = 1, and Maximum Z = 9.