The Simplex Algorithm

Chapter 3

1
 Overview of the Simplex Method

Steps Leading to the Simplex Method

Formulate Put In Put In Execute

Problem Standard Tableau Simplex
as LP Form Form Method

2
 How to convert an LP model to standard form model
◼ An LP is in standard form when:
• All variables are non-negative
• All constraints are equalities

◼ Putting an LP formulation into standard form involves:

• Adding slack variables to “≤“ constraints (A slack variable is the
amount of the resources unused in the ith constraint).
• Subtracting surplus variables from “≥” constraints. (A surplus
variable is the amount by which ith constraint is over satisfied).
• Slack and surplus variables represent the difference between the
left and right sides of the constraints.
• Slack and surplus variables have objective function coefficients
equal to 0.
((see page 8 in chapter 2))
3
 Tableau Form

◼ A set of equations is in tableau form if for each equation:

◼ its right hand side (RHS) is non-negative, and

◼ there is a basic variable (+S OR +a).

((A basic variable for an equation is a variable whose

coefficient in the equation is +1 and whose coefficient in
all other equations of the problem is 0)).
◼ To generate an initial tableau form:
◼ An artificial variable must be added to each constraint
that does not have a basic variable.

4
 Example

Convert the following LP problem into tableau form

Max 20x1 + 15x2

s. t. x1 < 100
x2 < 60
50x1 + 35x2 < 6000
20x1 + 15x2 > 2000
x1, x2 > 0

© 2003 ThomsonTM/South-Western Slide 5

 Example: Standard Form
Problem in Standard Form

Max 20x1 + 15x2

s. t. X1 + S1 = 100

x2 + S2 = 60
50x1 + 35x2 + S3 = 6000
20x1 + 15x2 – S4 + a4 = 2000
x1, x2 ,S1 ,S2 ,S3 ,a4 > 0

© 2003 ThomsonTM/South-Western Slide 6

 Example: Initial Formulation

A Minimization Problem

MIN 2x1 - 3x2 - 4x3

s. t. x1 + x2 + x3 < 30
2x1 + x2 + 3x3 > 60
x1 - x2 + 2x3 = 20

x1, x2, x3 > 0

© 2003 ThomsonTM/South-Western Slide 7

 Example: Standard Form
Problem in Standard Form

MIN 2x1 - 3x2 - 4x3 +0s1+0s2+0a2+0a3

s. t. x1 + x2 + x3 + s1 = 30
2x1 + x2 + 3x3 - s2 + a2 = 60
x1 - x2 + 2x3 + a3 = 20

x1, x2, x3, s1, s2,a2,a3 > 0

© 2003 ThomsonTM/South-Western Slide 8

 How to find the basic feasible solution (bfs) using
algebraic properties:

Whenever we have simultaneous linear equations has more

variables (n) than equations (m), we can expect that an
infinite number of solutions some of them will be basic
solution. These basic solutions may group into two
categories: some of them feasible (b.f.s) and others
infeasible solution.

9
 How to find the basic feasible solution (bfs) using algebraic properties
EX1: Consider the following linear programming model:
◼ Max 5X1+9X2

S.t. 0.5X1+ X2 ≤8
X1+ X2 ≥ 10
0.25X1+ 1.5X2 ≥ 6
X1 , X 2 ≥ 0
a) Write the problem in a standard form.
b) How many variables will be set to zero in a basic solution to this problem?
c) Find the basic solution that corresponds to S1and S2 equal to zero.
d) Find the basic solution that corresponds to Xl and S3 equal to zero.
e) Are your solutions for parts (c) and part (d) basic feasible solutions?
Extreme-point solutions? Explain
f) Use the graphical approach to identify the solutions found in parts (c) and
part (d). Do the graphical results agree with your answer to part (e)?
Explain.
10
 Example (1)

◼ Solution:
◼ a-
Max 5X1 +9X2+0S1+0S2+0S3
s.t.
½ X1 + X2 + 1S1 =8
X1 + X 2 -1S2 =10
¼ X1 + 3/2 X2 -1S3 =6
X1,X2,S1,S2,S3 ≥ 0

11
 Example (1)
b- Number of variables set to zero =
number of variables (=5=X1,X2,Sl,S2,S3) - number of constraints(3)
= (5-3)=2
(The No. of variables must be set equal to zero in each basic
solution.)

c- Substituting S1,S2=0 (Constrains 1 & 2)in the constraints and solve

equation 1&2, you get X1=4, X2=6 then substitute these values to solve
third constraint, S3=4

d- Substituting X1,S3=0 in the constraints (3) ,you get from equation 3 that
X2=4 and substitute X2 in equation 1&2 you get S1=4, S2= - 6

12
 Example (1)
e) The answer to part c is a basic feasible solution and an
extreme point solution. The answer to part d is not a basic
feasible solution because S2 is negative.
f) The graph below shows that part c represent extreme
point, whereas, part d is not:

13
 Example (2)
Consider the following LP:
Max Z= Xl +2X2
s.t.
Xl +5X2 ≤ 10
2X1+6X2 ≤ 16
X1, X2 ≥ 0
a) Write the problem in standard form.
b) How many variables will be set equal to zero in a basic solution
for this problem?
c) Find all the basic solutions, and indicate which are also feasible.
d) Find the optimal solution by computing the value of each basic
feasible solution.
14
 Example (2)
◼ Solution:
a- Standard Form:
Max Z= X1 + 2X2
s.t.
X1+ 5X2 + S1 = 10
2X1+ 6 X2 + S2 = 16
X1, X2, S1, S2 > 0

B- We have n (number of variables) = 4 , and m (number of constraints)

= 2 in standard form.
So n - m = 4 - 2 = 2 variables must be set equal to zero in each
basic solution.
15
 Example (2)
There are 6 combinations (4C2) of the two variables that may be set equal
to zero and hence 6 possible basic solutions. (Every time we select 2 vars.
and make them equal to zero)

1- X1= 0, X2 = 0 (substitute them in the constraints, we get :)

S1 = 10
S2 = 16
This is a basic feasible solution. (Because all values are positives)

2- X1 = 0, S1 = 0
5 X2 = 10 X2 = 2. And substituting for X2 in equation (2) yields 6(2) + S2
= 16
S2 = 16 - 12 = 4
This is a basic feasible solution. (Because all values are positives)
16
 Example (2)
3- Xl = 0, S2 = 0
5X2 + S1 = 10 ………(1)
6X2 = 16 ……... (2)
From (2), we have X2= 8/3. Substituting for X2 in (1) yields 5(8/3) + S1=
10
S1 = 10 - 40/3 = -10/3
This is not a basic feasible solution. (Because S1 value is negative)
4- X2 = 0, S1= 0
X1= 10 ……. (1)
2 X1 + S2 = 16 ……. (2)
From (1) we have X1 = 10. And substituting for Xl in (2) yields
2(10) + S2 = 16
S2 = 16 - 20 = -4
This is not a basic feasible solution. (Because S2 value is negative)
17
 Example (2)

5- X2= 0, S2 = 0
Xl + S1 = 10 …….(1)
2Xl = 16 …….(2)
From (2) we find Xl, = 8. And substituting for Xl in (l) yields
8 + S1 + = 10 S1 =2
This is a basic feasible solution

18
 Example (2)
6- S1 = 0, S2= 0
Xl + 5X2 = 10 …… (1)
2X1 +6X2= 16 ………(2)
From (1) we have X1 = 10 - 5X2. Substituting for Xl in (2) yields
2(10 - 5X2) + 6 X2 = 16
20 -10X2 + 6 X2 = 16
- 4 X2 = 16 - 20
- 4 X2 = - 4
X2 = 1
Then, X1 = 10 - 5(1) = 5
This is a basic feasible solution.
19
 Example (2)
d- The optimal solution is the basic feasible solution with the
largest value of the objective function.

There are 4 basic feasible solutions from part (c) to evaluate in the
objective function. Max Z= X1 + 2X2

X1 = 0, X2 = 0, S1= 10, S2 = 16, Z-Value = 1(0) + 2(0) = 0

X1 = 0, X2 = 2, S1 = 0, S2 = 4, Z-Value = 1(0) + 2(2) = 4
X1 = 8, X2 = 0, S1= 2, S2 = 0, Z-Value = 1(8) + 2(0) = 8
X1 = 5, X2 = 1, S1= 0, S2 = 0, Z-Value = 1(5) + 2(1) = 7

The optimal solution (Maximum Z) is X1 = 8, X2= 0 with value = 8.

20
 The Simplex Algorithm
◼ The Simplex algorithm (method) is used to solve LPs in which the
goal is to Maximize the objective function.
Step 1 Convert the LP to standard form. (All constraints with equal sign)

Step 2 Define an equivalent linear program by performing the following

operations:
Generally to solve the problem, we keep it as it is and use the 2 phase-
simplex method or Big M simples method.

Step 3 Set up the Standard form of the linear program by adding

appropriate slack and surplus variable.

Step 4 To obtain an initial basic feasible solution, we set up the

tableau form of a linear program.
21
 The Simplex Algorithm

◼ Step 5 The initial simplex tableau must be set up to keep track of

the calculations required by the simplex method.

◼ Step 6 Choose the non-basic variable with the biggest positive

c-z (for Max. Problem) to enter it in the basis column. The
column associated with that variable is the pivot column.
Minimization problem will be discussed at later stage using
2-phase method.

22
 The Simplex Algorithm
◼ Step 7 Choose as the pivot row that row with the smallest
ratio/positive values of pivot column. This ratio is used to determine
which variable will leave the basis when new variable j enters the
basis. This ratio also indicates how many units of variable j can be
introduced into solution before the basic variable in the ith row equals
zero. The intersection of the pivot column and pivot row is called
pivot element.

◼ Step 8 Perform the necessary elementary row operation (ERO) to

convert the pivot to a unit column.
a) Divide each value in the pivot row by the pivot element value. The
result is a new pivot row containing a 1 in the pivot column.
b) Obtain zeroes in all other positions of pivot column by adding or
subtracting an appropriate multiple of the new pivot row.

23
 The Simplex Algorithm

◼ Step 9 Test for optimality. If c-z ≤ 0 for all columns,

we have the optimal solution. If not, return to step 6.

24
 Example: Simplex Method
Solve the following problem by the simplex method:
Max z = 60X1 + 30X2 + 20X3
S.t.
8X1 + 6X2 + X3 ≤ 48 (Lumber Constraint)
4X1 + 2X2 +1.5X3 ≤ 20 (Finishing Constraint)
2X1 + 1.5X2 +0.5X3 ≤8 (Carpentry Constraint)
X2 ≤5 (Table Demand Constraint)
X1, X2, X3 ≥ 0.

25
Solve the following problem by the simplex method:

Max z = 60X1 + 30X2 + 20X3

Solution
Max z = 60X1 + 30X2 + 20X3 +0S1+0S2+0S3+0S4

S.t.
8X1 + 6X2 + X3 +S1 = 48 (Lumber Constraint)
4X1 + 2X2 +1.5X3 +S2 = 20 (Finishing Constraint)
2X1 + 1.5X2 +0.5X3 +S3 = 8 (Carpentry Constraint)
X2 +S4 = 5 (Table Demand Constraint)

X1, X2, X3 ,S1,S2,S3,S4 ≥ 0.

26
 Example: Simplex Method
◼ Begin the simplex algorithm by converting the constraints of the LP to standard form.
◼ Canonical Form 0 (Initial Tableau)
Basis Cij 60X1 30X2 20X3 0S1 0S2 0S3 0S4 RHS Ratio
S1 0 8 6 1 1 0 0 0 48 48/8=6
S2 0 4 2 1.5 0 1 0 0 20 20/4=5
S3 0 2 1.5 0.5 0 0 1 0 8 8/2=4
S4 0 0 1 0 0 0 0 1 5 N.A
Z 0 0 0 0 0 0 0 0
C-Z 60 30 20 0 0 0 0

As Max Problem, select the biggest positive coefficient of the objective

function (i.e. 60 for X1) (for non-basic variable)).therefore, we enter X1 to the
basis column, for this reason; X1 is called the entering variable. Observe that X1
has the most positive coefficient in (row c-z) row 0.
* ( c-z net evaluation row)

27
 Example: Simplex Method
◼ Always make the entering variable a basic variable in a row that wins
the ratio test.
◼ To make X1 a basic variable in row 3, we use elementary row
operations (EROs) to make X1 have a coefficient of 1 in row 3 and
a coefficient of 0 in all other rows.
This procedure is called pivoting on row 3; and row 3 is called the
pivot row. The result is Canonical form 1 as follows:
X1 = [1 3/4 1/4 0 0 1/2 0 4]

S1= −8 [ 1 ¾ ¼ 0 0 ½ 0 4 ]
+[8 6 1 1 0 0 0 48 ]
S1= 0 0 −1 1 0 −4 0 16

S2= -4 [ 1 ¾ ¼ 0 0 ½ 0 4 ]
+ [ 4 2 1.5 0 1 0 0 20 ]
S2= 0 -1 0.5 0 1 -2 0 4 S4= same (intersection =0)28
 Example: Simplex Method

Basis Cij 60X1 30X2 20X3 S1 S2 S3 S4 RHS ratio

S1 0 0 0 -1 1 0 -4 0 16 -
S2 0 0 -1 0.5 0 1 -2 0 4 8
X1 60 1 0.75 0.25 0 0 0.5 0 4 16
S4 0 0 1 0 0 0 0 1 5 -
Z 60 45 15 0 0 30 0 240
C-Z 0 -15 5 0 0 -30 0

◼ The procedure used to go from one b.f.s to a better adjacent

(neighboring) b.f.s is called an iteration of the simplex algorithm.
◼ The current b.f.s is not optimal because increasing X3 by 1 unit (while
holding the other nonbasic variable to zero) will increase the value of Z.
◼ Making either X2 or S3 basic will cause the value of Z to decrease.
◼ Once we have obtained a b.f.s, we need to determine whether it is optimal.
◼ Since X3 is the only variable with a positive coefficient, X3 should be
entered into the basis.
29
 Example: Simplex Method
◼ the largest we can make X1 is min {8, 16} = 8. So, row 2 becomes the
pivot row.
◼ The result of using EROs is to make X3 a basic variable in row 2.

X3 = [0 -2 1 0 2 -4 0 8]

S1= +1 [ 0 -2 1 0 2 -4 0 8 ]
+ [ 0 0 -1 1 0 -4 0 16 ]
S1= 0 -2 0 1 2 -8 0 24

X1= -1/4 [ 0 -2 1 0 2 -4 0 8 ]
+ [ 1 3/4 1/4 0 0 ½ 0 4]
X1= 1 5/4 0 0 -1/2 3/2 0 2
S4= same row (intersection =0)
30
 Basis Cij 60X1 30X2 20X3 S1 S2 S3 S4 RHS
S1 0 0 -2 0 1 2 -8 0 24
X3 20 0 -2 1 0 2 -4 0 8
X1 60 1 1.25 0 0 -0.5 1.5 0 2
S4 0 0 1 0 0 0 0 1 5
Z 60 35 20 0 10 10 0 280
C-Z 0 -5 0 0 -10 -10 0

◼ Basic Variables = {S1 ,X3, X1, S4}

◼ NBV = {S3, S2, X2}
◼ Yielding the b.f.s Z=280, S1= 24, X3=8, X1= 2, S4=5.
◼ We can see that increasing X2 , S2 , or S3 (while holding the other
NBVs to zero) will cause the value of Z to decrease.
◼ The solution at the end of iteration 2 is therefore optimal.
◼ A canonical form is optimal (for a max problem) if each non basic
variable has a negative coefficient in the canonical form's row c-z
31
 The 2-Phase Method

◼ The simplex method algorithm requires a starting b.f.s.

◼ If an LP has (≥) or (=) constraints, however, a starting
b.f.s may not be readily (easily) apparent.
◼ In such a case, the 2-phase method may be used to solve
the problem.

32
 Example Min Problem
◼ Min Z = 2X1 + 3X2
◼ S.t
0.5X1 + 0.25X2 ≤ 4 (sugar constraint)
X1 + 3X2 ≥ 20 (Vitamin C constraint)
X1 + X 2 = 10 (10 oz in 1 bottle of Orange)
X1, X2 ≥0

◼ The LP in standard form has Z and S1 which could be used

for BVs but row 2 would violate (break) sign restrictions
and row 3 no readily apparent basic variable.

33
 Example Min Problem

Row 1: Z =2X1 + 3X2

Row 2: 0.5X1 + 0.25X2 + S1 =4
Row 3: X1 + 3X2 - S2 = 20
Row 4: X 1 + X2 = 10

The above form is called standard form. It gives a basic solution

but it is infeasible as the value of X1 = 0, X2=0, S1=4 and S2= -20,
Z=0
In order to use the simplex method, a bfs is needed.
To remedy the predicament, artificial variables are created.
The variables will be labeled according to the row in which they are
used.
34
 Example Min Problem

Row 1: Min Z= 2Xl + 3X2 + 0S1 + 0S2

Row 2: 0.5Xl + 0.25X2 + S1 =4
Row 3: X1 + 3X2 - S2 + a2 = 20
Row 4: X1 + X 2 +a3 = 10

X1, X2,S1,S2, a2, a3 ≥ 0.

35
 Description of the 2-phase Method
1- Modify the constraints so that the RHS of each constraint
is nonnegative.
2- Identify each constraint that is now an = or ≥ constraint.
3. Convert each inequality constraint to standard form. (adds a
slack variable for ≤ constraints, add an excess (surplus) variable
for ≥ constraints).
4. For each ≥ or = constraint, add artificial variables. Add
sign restriction ai ≥ 0.
5. Since each artificial variable will be in the starting basis, all
artificial variables must be eliminated from c-z row (objective
function row) before beginning the simplex phase l).
36
 Description of the 2-phase Method
6- find a basic solution of the resulting equations that
minimizes the sum of the artificial variables. i.e –
(a1+a2+a3…+ak) by selecting the most negative value in this
row. This procedure will be same whether the problem is Max.
or Min. problem as long as we are in phase l.
7-If all artificial variables in the optimal solution equal zero,
the solution is optimal.

◼ If any artificial variables are positive in the optimal

solution, the problem is infeasible.
◼ The variable with the positive coefficient in row 0 should
enter the basis since this is a Min problem.

37
 Example Min Problem-Solution
We assign 0 values to all artificial variables in the Cij column, and create
objective function (OF) row that represents the total of all artificial
variables in the problem preceded by a negative sign as follows:

Basis Cij 2X1 3X2 S1 S2 RHS Ratio

S1 0 0.5 0.25 1 0 4 16
a2 0 1 3 0 -1 20 6.67
a3 0 1 1 0 0 10 10
- (a2 + a3) -2 -4 0 1
◼ Now we pick up the Most Negative coefficient in the objective
function row regardless whether our problem Maximization or
Minimization.
◼ X2 is the entering variable as its coefficient has the most negative
value (- 4) in (OF) row. a2 is the leaving variable as it has the lowest
nonnegative ratio. Pivot Raw (X2): Pivot element must be equal to 1,
38
thus:
 Example Min Problem-Solution
X2= 1/3 1 0 -1/3 20/3

S1= - 0.25 [1/3 1 0 -1/3 20/3 ]

+ [0.5 0.25 1 0 4 ]
S1= 5/12 0 1 1/12 7/3

a3= -1[1/3 1 0 -1/3 20/3 ]

+[1 1 0 0 10 ]
a3= 2/3 0 0 1/3 10/3

39
 Example Min Problem-Solution
Basis Cij 2X1 3X2 S1 S2 RHS ratio

S1 0 5/12 0 1 1/12 7/3 5.6

X2 3 1/3 1 0 -1/3 20/3 20

a3 0 2/3 0 0 1/3 10/3 5

- (a3) -2/3 0 0 -1/3 -10/3

X1 is the entering variable X1= 1 0 0 ½ 5 pivot raw

a3 is the leaving variable
S1= -5/12 [1 0 0 ½ 5 ]
+ [5/12 0 1 1/12 7/3 ]
S1= 5/12 0 1 -1/8 0.25

X2= -1/3 [1 0 0 ½ 5 ]
+ [1/3 1 0 -1/3 20/3 ]
X2= 0 1 0 -1/2 5
40
 Example Min Problem-Solution
Basis Cij 2X1 3X2 S1 S2 RHS

S1 0 0 0 1 -1/8 0.25

X2 3 0 1 0 -1/2 5

X1 2 1 0 0 1/2 5

As we notice that at this stage all artificial had left the solution
and this is the end of phase 1.
Start phase 2 in the normal manner (method), i.e create Z and
C-Z rows. For next step (phase 2), we need to work on the
solution according to normal logic, i.e if we have Maximization
problem we look for the Most positive coefficient in c-z row,
whereas if the problem Min. we look for the Most negative
coefficient as follows: 41
 Example Min Problem-Solution
Basis Cij 2X1 3X2 S1 S2 RHS
S1 0 0 0 1 -1/8 0.25
X2 3 0 1 0 -1/2 5
X1 2 1 0 0 1/2 5
Z 2 3 0 -1/2 25
C-Z 0 0 0 1/2

◼ As we do not have any negative coefficient in c-z, this implies

that we have reached to an optimal solution. Where:
X1 =5 , X2= 5 , Z =25
◼ This means that Bevco can hold the cost of producing a 10-oz
bottle of Orange to $25 by mixing 5 oz of orange soda and 5 oz
of orange juice.
◼ If any artificial variable is positive in the optimal tableau, then
the original LP has no feasible solution.
42
 Example
Min Z= 2X1+3X2 → Min =2X1 +3X2
S.t
X1 ≥ 125 → X1 – S1 + a1 = 125
X1 + X2 ≥ 350 → X1+X2 – S2 + a2 = 350
2X1 + X2 ≤ 600 → 2X1+X2 + S3 = 600
X 1 , X2 ≥ 0 → X1, X2 , S1, S2 , S3 ,a1, a2 ≥ 0

Basis Cij 2X1 3X2 0S1 0S2 0S3 RHS Ratio

a1 0 1 0 -1 0 0 125 125

a2 0 1 1 0 -1 0 350 350

S3 0 2 1 0 0 1 600 300

- (a1 + a2) -2 -1 1 1 0
43
 Example

X1 is the entering variable X1= 1 0 -1 0 0 125 pivot row

a2= -1 [1 0 -1 0 0 125 ]
+ [1 1 0 -1 0 350 ]
a2 = 0 1 1 -1 0 225

S3= -1 [1 0 -1 0 0 125 ]
+ [2 1 0 0 1 300 ]
S3 = 0 1 2 0 1 350

44
 Example
Basis Cij 2X1 3X2 0S1 0S2 0S3 RHS Ratio

X1 2 1 0 -1 0 0 125 -

a2 0 0 1 1 -1 0 225 225

S3 0 0 1 2 0 1 350 350

-a2 0 -1 -1 1 0 -225

X2 is the entering variable X2= 0 1 1 -1 0 225 pivot row

X1= [1 0 -1 0 0 125]

S3= -1 [0 1 1 -1 0 225 ]
+ [0 1 2 0 1 350 ]
S3 = 0 0 1 1 1 125
45
 Example
Basis Cij 2X1 3X2 0S1 0S2 0S3 R.H.S Ratio

X1 2 1 0 -1 0 0 125 -
X2 3 0 1 1 -1 0 225 225
S3 0 0 0 1 1 1 125 125
Z 2 3 1 -3 0 925
C-Z 0 0 -1 3 0

S1 is the entering variable S1= 0 0 1 1 1 125 pivot row

X1= 1 [0 0 1 1 1 125 ]
+ [1 0 -1 0 0 125 ]
X1 = 1 0 0 1 1 250

X2= -1 [0 0 1 1 1 125 ]
+ [0 1 1 -1 0 225 ]
X2 = 0 1 0 -2 -1 100 46
 Example

Basis Cij 2X1 3X2 S1 S2 S3 R.H.S

X1 2 1 0 0 0 1 250
X2 3 0 1 0 -2 -1 100
S1 0 0 0 1 1 1 125
Z 2 3 0 -4 -1 800
C-Z 0 0 0 +4 +1

Optimal Solution is: X1=250, X2=100, Z=800

47
 Special Cases-Alternate Optimal Solutions

◼ For some LPs, more than one extreme point is optimal. If an LP has
more than one optimal solution, it has multiple optimal solutions or
alternative optimal solutions.

◼ If there is No non-basic variable (NBV) with a zero coefficient in

row 0 of the optimal tableau, the LP has a unique optimal solution.

◼ Even if there is a non-basic variable with a zero coefficient in row 0

of the optimal tableau, it is possible that the LP will have alternative
optimal solutions.

EX: Max Problem as follows:

48
 Special Cases-Alternate Optimal Solutions

Ex: the optimal solution for Max problem

49
 Special Cases-Unbounded LPs

◼ For some LPs, there exist points in the feasible region for which Z
assumes arbitrarily (randomly) large (in Max problems) or arbitrarily
small (in Min problems) values. When this occurs, we say the LP is
unbounded.

◼ An unbounded LP occurs in a Max problem if there is a non-

basic variable with a positive coefficient in row c-z and there is
no positive value in the pivot column (entering variable column).

◼ Specifically, an unbounded LP for a Max problem occurs when a

variable with a positive coefficient in row 0 has a non positive
coefficient in each constraint. (pivot column all ≤ 0)

50
 Special Cases-Unbounded LPs

EX: Max Problem as follows:

Basic Cij 20X1 10X2 S1 S2 R.H.S Ratio

X1 20 1 0 -1 0 2 -

S2 0 0 1 0 1 5 -

Z 20 0 -20 0 40 -

C-Z 0 10 20 0

51
 Special Cases-Infeasibility
◼ Infeasibility is detected in the simplex method whenever no solution to
linear programmer can be found that satisfies all the constraints,
including the non-negativity constraint. In the following example, we
notice the solution has reached the optimality since we have all non-
artificial variables are positives. But we still have a4 in the basis and this
represents the infeasibility.

Basic Cij 50X1 40X2 S1 S2 S3 S4 a4 RHS

X2 40 0 1 0.32 0 0 0 0 12

S2 0 0 0 -0.32 1 -0.12 0 0 8

X1 50 1 0 -0.20 0 0.12 0 0 30

a4 0 0 0 -0.12 0 -0.05 -1 1 8

-a4 0 0 +0.12 0 +0.05 +1 -1 -8

52
Special Cases-Degeneracy and the Cycling of the
Simplex Algorithm
◼ Theoretically, the simplex algorithm can fail to find an optimal
solution to an LP. A degenerate solution to linear program is
when at least one of the basic variables equals 0. This can
occur at formulation or if there is a tie for the minimizing value
in the ratio test to determine the leaving variable.
◼ Assume that in each of the LP's basic feasible solutions (in RHS)
all basic variables are positive. An LP with this property is a
non-degenerate LP.
◼ Any bfs that has at least one basic variable equal to zero is a
degenerate bfs.
◼ When the same bfs is encountered twice it is called cycling.

53
Special Cases-Degeneracy and the Cycling of the
Simplex Algorithm
◼ If cycling occurs, then we will loop, or cycle, forever among a set
of basic feasible solutions and never get to an optimal solution.
◼ Some degenerate LPs have a special structure that enables us to
solve them by methods other than the simplex.

Basic Cij 50X1 40X2 S1 S2 S3 RHS

X2 40 0 1 8/25 0 -3/25 20
S2 0 0 0 -8/25 1 3/25 0
X1 50 1 0 -5/25 0 5/25 5
Z 50 40 70/25 0 130/25 2050
C-Z 0 0 -70/25 0 -130/25
54
End of Chapter 3

55