Simplex Examples

BAU-INE 3201 - ORII

Linear Programming Case Study (Simplex Method)
Example 1:

• Maximize: Z = 3x₁ + 5x₂

Subject to:
2x₁ + 3x₂ ≤ 8
4x₁ + x₂ ≤ 7
x₁, x₂ ≥ 0

2
 Standard Form
• Add slack variables s₁ and s₂:
2x₁ + 3x₂ + s₁ = 8
4x₁ + x₂ + s₂ = 7
Objective: Max Z - 3x₁ - 5x₂ - 0·s₁ - 0·s₂ = 0
Initial z-row shows negative coefficients of objective
function.

3
Initial Simplex Tableau (Textbook Start)
Basic x₁ x₂ s₁ s₂ RHS

z -3 -5 0 0 0

s₁ 2 3 1 0 8

s₂ 4 1 0 1 7

4
After Pivot (x₂ enters, s₁ leaves)
Basic x₁ x₂ s₁ s₂ RHS

z 3.33 5 1.67 0

x₂ 0.67 1 0.33 0 2.67

s₂ 3.33 0 -0.33 1 4.33

5
 Final Simplex Tableau
Basic x₁ x₂ s₁ s₂ RHS

z 0.33 0 1.67 0 13.33

x₂ 0.67 1 0.33 0 2.67

s₂ 3.33 0 -0.33 1 4.33

6
 Detailed Solution Summary
• Optimal solution
• • Decision variables: x₁ = 0.00, x₂ = 2.67
– • Objective value: Z = 13.33
– • Slack variables: s₁ = 0.00 (binding), s₂ = 4.33 (non-binding)
– • Initial z-row: shows negative objective coefficients
– • Later z rows: calculated normally
– • Interpretation: Only x₂ is produced; resource A is binding; resource B
has unused capacity.

7
Linear Programming Case Study (Simplex Method)
Example 2:
• Maximize Z = 5x₁ + 4x₂

Subject to:
2x₁ + 1x₂ ≤ 10 (machine A)
1x₁ + 3x₂ ≤ 15 (machine B)
1x₁ + 1x₂ ≤ 7 (shipping)
1x₁ + 0x₂ ≤ 4 (contract limit on x₁)

Add slack variables s₁, s₂, s₃, s₄ to convert to equalities.

8
 Initial Simplex Tableau (textbook z-
row)
Basic x1 x2 s1 s2 s3 s4 RHS
z -5 -4 0 0 0 0 0
s1 2 1 1 0 0 0 10
s2 1 3 0 1 0 0 15
s3 1 1 0 0 1 0 7
s4 1 0 0 0 0 1 4

9
 Pivot 1: x1 enters, s4 leaves (integer
arithmetic)
Basic x1 x2 s1 s2 s3 s4 RHS
z 0 -4 0 0 0 5 20
s1 0 1 1 0 0 -2 2
s2 0 3 0 1 0 -1 11
s3 0 1 0 0 1 -1 3
x1 1 0 0 0 0 1 4

10
 Ratio Test for Pivot 1
• Ratios for x1 column (RHS / coeff):
s1: 10/2 = 5
s2: 15/1 = 15
s3: 7/1 = 7
s4: 4/1 = 4 (smallest → s4 leaves)

Pivot on s4 row, x1 column (pivot = 1).

11
 Pivot 2: x2 enters, s1 leaves (integer
arithmetic)
Basic x1 x2 s1 s2 s3 s4 RHS
z 0 0 4 0 0 -3 28
x2 0 1 1 0 0 -2 2
s2 0 0 -3 1 0 5 5
s3 0 0 -1 0 1 1 1
x1 1 0 0 0 0 1 4

12
 Ratio Test for Pivot 2
• Ratios for x2 column (RHS / coeff where coeff>0):
x1: coeff 0 → ignore
s1: 2/1 = 2 (smallest → s1 leaves)
s2: 11/3 = 3 (integer division not used; take floor if needed)
s3: 3/1 = 3

Pivot on s1 row, x2 column (pivot = 1).

13
 Final Tableau & Optimal Integer
Solution
Basic x1 x2 s1 s2 s3 s4 RHS
z 0 0 4 0 0 -3 28
x2 0 1 1 0 0 -2 2
s2 0 0 -3 1 0 5 5
s3 0 0 -1 0 1 1 1
x1 1 0 0 0 0 1 4

14
 Detailed Solution Summary
• Optimal integer solution:
– • Decision variables: x1 = 4, x2 = 2
– • Slack variables: s1 = 0, s2 = 5, s3 = 1, s4 = 0
– • Objective value: Z = 5*4 + 4*2 = 28
– • Interpretation: Produce 4 chairs and 2 tables to maximize
profit.

15
Linear Programming Case Study (Simplex Method)
Example 3:

• Maximize Z = 3x1 + 5x2 + 4x3

Subject to:
2x1 + x2 + x3 ≤ 10
x1 + 3x2 + 2x3 ≤ 18
x1 + x2 + 2x3 ≤ 14
x1,x2,x3 ≥ 0

16
Standard form (add slacks s1,s2,s3)
• Objective: Max Z - 3x1 -5x2 -4x3 = 0
2x1 + x2 + x3 + s1 = 10
x1 +3x2 +2x3 + s2 =18
x1 + x2 +2x3 + s3 =14
x1,x2,x3,s1,s2,s3 ≥ 0

17
 Initial tableau
x1 x2 x3 s1 s2 s3 RHS

z -3 -5 -4 0 0 0 0

s1 2 1 1 1 0 0 10

s2 1 3 2 0 1 0 18

s3 1 1 2 0 0 1 14

18
 After Pivot 1 (enter col 2)
x1 x2 x3 s1 s2 s3 RHS

z -1.33 0 -0.67 0 1.67 0 30

s1 1.67 0 0.33 1 -0.33 0 4

x2 0.33 1 0.67 0 0.33 0 6

s3 0.67 0 1.33 0 -0.33 1 8

19
 After Pivot 2 (enter col 1)
x1 x2 x3 s1 s2 s3 RHS

z 0 0 -0.40 0.80 1.40 0 33.20

x1 1 0 0.20 0.60 -0.20 0 2.40

x2 0 1 0.60 -0.20 0.40 0 5.20

s3 0 0 1.20 -0.40 -0.20 1 6.40

20
 After Pivot 3 (enter col 3)
x1 x2 x3 s1 s2 s3 RHS

z 0 0 0 0.67 1.33 0.33 35.33

x1 1 0 0 0.67 -0.17 -0.17 1.33

x2 0 1 0 0.00 0.50 -0.50 2.00

x3 0 0 1 -0.33 -0.17 0.83 5.33

21
 Final tableau (optimal)
x1 x2 x3 s1 s2 s3 RHS

z 0 0 0 0.67 1.33 0.33 35.33

x1 1 0 0 0.67 -0.17 -0.17 1.33

x2 0 1 0 0 0.50 -0.50 2

x3 0 0 1 -0.33 -0.17 0.83 5.33

22
 Detailed solution summary
• Detailed solution (rounded to 2 dp):
s1 = 0
s2 = 0
s3 = 0
x1 = 1.33
x2 = 2
x3 = 5.33
Objective Z = 35.33

Interpretation:
- Basic variables shown in tableaux are the current BFS.
- All z-row coefficients under x-variables are non-negative ⇒
optimal.

23
Linear Programming Case Study (Simplex Method)
Example 4:

• Maximize: Z = x₁ + x₂
Subject to:
x₁ + x₂ ≤ 4
x₁ ≤ 3
x₂ ≤ 3
x₁, x₂ ≥ 0

(There will be multiple optimal solutions along a

segment.)

24
 Standard Form
• Add slack variables s₁, s₂, s₃:
x₁ + x₂ + s₁ = 4
x₁ + s₂ = 3
x₂ + s₃ = 3
Objective: Max Z - x₁ - x₂ - 0·s₁ - 0·s₂ - 0·s₃ = 0
Initial tableau uses textbook z-row (negative
coefficients).

25
 Initial Simplex Tableau (textbook z-
row)
Basic x₁ x₂ s₁ s₂ s₃ RHS
z -1 -1 0 0 0 0
s₁ 1 1 1 0 0 4
s₂ 1 0 0 1 0 3
s₃ 0 1 0 0 1.00 3

26
 Pivot Step (enter x₁, leave s₂)
Basic x₁ x₂ s₁ s₂ s₃ RHS
z 0 -1 0 1 0 3
s₁ 0 1 1 -1 0 1
x₁ 1 0 0 1 0 3
s₃ 0 1 0 0 1 3

27
 Detection of Alternative Optimal
Solutions
• After the pivot we obtain one basic feasible solution x₁=3, x₂=0 with Z=3.

Check x₂ entering: its z value equals its objective coefficient (both 1),
so the reduced cost c- z = 0 for x₂. That means moving x₂ into basis
does not change the objective value — multiple optimal solutions exist.

Geometrically, the line x₁ + x₂ = 4 intersects the feasible region between

(1,3) and (3,1) (due to bounds x₁≤3, x₂≤3). Any point on that segment gives
Z=4,
so there is an infinite set of optimal solutions.

28
 Final Tableau (example BFS with
alternative opt)
Basic x₁ x₂ s₁ s₂ s₃ RHS
z 1 1 0 0 0 4
x₁ 1 0 0 1 0 3
s₁ 0 1 1 -1 0 1
s₃ 0 1 0 0 1 3

29
 Detailed Solution Summary
• Alternative optimal solutions — summary:
– • Example LP: Max Z = x₁ + x₂ s.t. x₁ + x₂ ≤ 4, x₁ ≤ 3, x₂ ≤ 3.
– • Multiple optimal solutions exist on the segment x₁ + x₂ = 4 with 1 ≤ x₁
≤ 3 (and x₂ = 4 − x₁).
– • Simplex detects alternative optimality when a nonbasic variable has
zero reduced cost (c − z = 0).
– • One BFS: (x₁,x₂) = (3,1) or (1,3) or any convex combination between
them — all give Z = 4.
– • If you need one specific solution, apply secondary objective or
choose pivoting rule to obtain integer preferences.

30
Linear Programming Case Study (Simplex Method)
Example 5:

• Maximize: Z = x₁ + x₂
Subject to:
x₁ − x₂ ≤ 1
x₁, x₂ ≥ 0

(This problem is unbounded — objective can grow

without bound.)

31
 Standard Form
• Add slack variable s₁:
x₁ − x₂ + s₁ = 1
Objective: Max Z - x₁ - x₂ - 0·s₁ = 0
Initial tableau will use the textbook z-row (negative
objective coefficients).

32
Initial Simplex Tableau (Textbook Start)
Basic x₁ x₂ s₁ RHS

z -1 -1 0 0

s₁ 1 -1 1 1

33
 Attempted Pivot — x₂ Enters
• Select entering variable: x₂ (z-row has -1.00 under x₂; a candidate to
enter).

Perform ratio test: For each basic row with a positive coefficient in x₂
column, compute RHS / coeff.
Row s₁: coefficient for x₂ = -1.00 (≤ 0) → cannot form a positive ratio.

No basic row has a positive coefficient for x₂ ⇒ no leaving variable exists

⇒
The objective can increase indefinitely by increasing x₂ (and setting x₁ = x₂
+ 1 to satisfy constraint),
so the LP is UNBOUNDED.

34
 Algebraic Explanation of
Unboundedness
• From constraint: x₁ − x₂ = 1 − s₁ with s₁ ≥ 0 ⇒ x₁ = x₂ + 1 − s₁ ≤ x₂
+ 1.

Pick s₁ = 0 and let x₂ = t → x₁ = t + 1 for any t ≥ 0.

Then Z = x₁ + x₂ = (t + 1) + t = 2t + 1 which → ∞ as t → ∞.

Therefore there is no finite maximum; simplex detects this

because the entering variable x₂
has no valid leaving variable (no positive pivot coefficients), so
the problem is unbounded.

35
 Detailed Solution Summary
• Unbounded LP — summary:
– • Problem: Max Z = x₁ + x₂ s.t. x₁ − x₂ ≤ 1, x ≥ 0.
– • Converted to standard form with slack s₁: x₁ − x₂ + s₁ = 1.
– • Initial tableau (textbook z-row): z has -1 under x₁ and x₂.
– • Entering variable x₂ has no positive coefficients in
constraint rows → no leaving variable.
– • Conclusion: LP is unbounded; objective can increase
without bound (Z → ∞).

36
Linear Programming Case Study (Simplex Method)
Example 6:
• Minimize: Z = 2x₁ + 3x₂
Subject to:
2x₁ + x₂ ≤ 8
x₁ + 3x₂ ≤ 9
x₁, x₂ ≥ 0
(We convert to maximization by taking Z' = -Z.)
Standard form
• Let Z' = -Z ⇒ Maximize Z' + 2x₁ + 3x₂
Add slack variables s₁, s₂:
2x₁ + x₂ + s₁ = 8
x₁ + 3x₂ + s₂ = 9
37
 Initial Simplex Tableau
Basic x₁ x₂ s₁ s₂ RHS

z 2 3 0 0 0

s₁ 2 1 1 0 8

s₂ 1 3 0 1 9

38
 After Pivot (x₂ enters, s₂ leaves)
Basic x₁ x₂ s₁ s₂ RHS

z -1 -3 0 -1 -9

s₁ 1.67 0 1 -0.33 5

x₂ 0.33 1 0 0.33 3

39
 Interpretation & Final Solution
• Reading the final tableau (for Z'):
Basic variables: x₂ = 3, s₁ = 5, x₁ = 0 (nonbasic)
Value of Z' = -9 so original Z = -Z' = 9

Therefore the minimization solution is:

x₁ = 0, x₂ = 3, Z_min = 9
Notes:
• We solved the minimization by converting to a maximization
of -Z.
• Initial z-row showed 2 and 3 (since -c' = -(-2) = 2 etc.).
• After one pivot, optimality is reached for Z' (no positive z to
increase z').

40
 Detailed Solution Summary
• Summary (Minimization example):
– • Problem: Min Z = 2x₁ + 3x₂ s.t. 2x₁ + x₂ ≤ 8, x₁ + 3x₂ ≤ 9.
– • Converted to Max Z' = -2x₁ - 3x₂ and applied simplex.
– • Initial tableau (textbook z-row) displayed z = 2.00, 3.00.
– • Pivot: x₂ entered, s₂ left; resulting BFS x₂=3, x₁=0.
– • Original objective value: Z = 9.00 (minimum).

41