Solving Linear Programming Problems: The Simplex method
(Introduction to Operations Research by Hillier Frederick, Lieberman Gerld J.)
The simplex method was developed by the brilliant George Dantzig in 1947
that proved to be a remarkably efficient method that is used routinely to solve
huge problems on today’s computers.
The simplex method is an algebraic procedure. However its underlying
concept are geometric. Before delving intro algebraic details, we focus in this
section on the big picture from a geometric viewpoint
Consider the Example
The Wyndor Glass Co. Produces high-quality products, including windows and
glass doors. It has three plants. Aluminum frames and hardware are made in
PLant I, wood frames are made in Plant 2 and Plant 3 produces the glass and
assembles the products.
Because of declining earnings, top management has decide to revamp the
company’s product line. Unprofitable products are being discontinued,
releasing production capacity to launch two products having large sales
potential:
Product 1: An 8-foot glass door with aluminum framing
Product 2: A 4 x 6 foot double-hung wood-framed window
Product 1 requires some of the production capacity in Plants 1 and 3, but none
in Plant 2. Product 2 needs only Plants 2 and 3. The marketing division has
concluded that the company could sell as much of either product as could be
produced by these plants. However, because both products would be
competing for the same production capacity in Plant 3, it is not clear which mix
of the two products would be most profitable.
Data for the Wyndor Glass Co. Problem
Production Time per Batch, Hours
Product
Plant 1 2 Production Time
Available per
week, Hours
1 1 0 4
2 0 2 12
3 3 2 18
Profit per Batch $3000 $5,000
Hence
Maximize Z = 3x1 + 5x2
Constraints
�1 ≤ 4
2x2 ≤ 12
3x1 + 2x2 ≤ 18
And
�1 ≥ 0 �2 ≥ 0
x1 = 0
(0,9) 3x1 + 2x2 = 18
(4,6)
(0,6) 2x2 = 12
x2 = 0
(0,0) (4,0) (6,0)
Here, each constraint boundary is a line that forms the boundary of what is permitted
by the corresponding constraint. The point of intersection are the corner-point
solutions of the problem. The five that lie on the corners of the feasible
region- (0,0), (0,6), (2,6), (4,3) and (4,0) are corner-point feasible solutions
(CPF solutions). [The other three-(0,9),(4,6) and (6,0) are called corner point
infeasible solution].
Each CPF solution has two adjacent CPF solutions(each lying at the other end of one
of the two edges) as enumerated in table. One reason for our interest in adjacent CPF
solution is the following general property about such solutions, which provides a very
useful way of checking whether a CPF solution is an optimal solution
Adjacent CPF solutions for each CPF solution of the wyndor Glass Co. problem
CPF Solution Its Adjacent CPF Solutions
(0,0) (0,6) and (4,0)
(0,6) (2,6) and (0,0)
(2,6) (4,3) and (0,6)
(4,3) (4,0) and (2,6)
(4,0) (0,0) and (4,3)
Optimality test: Consider any linear programming problem that possesses at least one
optimal solution. If a CPF solution has no adjacent solutions that are better(as
measured by Z), then it must be an optimal solution
Outline of simplex method from a geometric viewpoint
Initialization: Choose (0,0) as the initial CPF solution to examine. (this is a
convenient choice because no calculations are required to identify this CPF
solution)
Optimality Test: Conclude that (0,0) is not an optimal solution. (Adjacent CPF
solutions are better)
Iteration 1: Move to a better adjacent CPF solution, (0,6) by performing the
following three steps
1. Considering the two edges of the feasible region that emanate from (0,0), choose
to move along the edge that leads up to �2 axis. (With an objective function Z =
3x1 + 5x2 moving up the �2 axis increases Z at a faster rate than moving along the
x − axis)
2. Stop at the first new constraint boundary: 2x2 =
12. ( Moving farther in the direction selected in step 1leaves the feasible region;
e.g, moving to the second region new constraint boundary hit when moving that
direction gives (0,9) which is a corner-point infeasible solution
3. Solve for the intersection of the new set of constraint boundaries:(0,6). (The
equations for these constraint boundaries �1 = 0 and 2x2 = 12 immediately yield
this solution)
Optimality Test: Conclude that (0,6) is not an optimal solution. (An adjacent CPF
solution is better.)
Iteration 2: Move to a better adjacent CPF solution, (2,6)by performing the following
three steps
1. Considering the two edges of the feasible region that emanate from (0,6), choose
to move along the edge that leads to the right.(Moving along this edge increases Z,
whereas backtracking to move back down the �2 axis decreases Z)
2. Stop at the first new constraint boundary encountered when moving in that
direction: 3x1 + 2x2 = 12( Moving farther in that direction selected in step 1 leaves
the feasible region.)
3. Solve for the intersection of the new set of constraint boundaries: (2,6). (The
equation for these constraint boundaries, 3x1 + 2x2 ≤ 18 and 2x2 ≤ 12
immediately yield this solution.)
Optimality Test: Conclude that (2,6) is an optimal solution, so stop. (None of the
adjacent CPF solutions are better)
Setting up the simplex method
The algebraic procedure is based on solving systems of equations. Therefore,
the first step in setting up the simlex method is to convert the functional
inequality constraints to equivalent equality constraints.( the nonnegativity
constraints are left as inequalities because they are treated separately). This
conversion is accomplished by introducing slack variables.
Considering the functional constraint x1 ≤ 4 The slack variable for this
constraint is defined to be x3 = 4 − x1 which is the amount of slack in the
left-hand side of the inequality. Thus x1 + x3 = 4 . Therefore the original
constraint x1 ≤ 4 is entirely equivalent to the pair of constraint
x1 + x3 = 4 and x3 ≥ 0
Upon the introduction of slack variables for the other functional constraints, the
original linear programming model for the example (shown below on the
left)can now be replaced by the equivalent model(called the augmented form
of the model)shown on the right
Original Form of the model Augmented form of the model
Maximize Z = 3x1 + 5x2 Maximize Z = 3x1 + 5x2
Subject to Subject to
�1 ≤ 4 (1) �1 + �3 = 4
2x2 ≤ 12 (2) 2x2 + x4 = 12
3x1 + 2x2 ≤ 18 (3) 3�1 + 2�2 + �5 = 18
And And
�1 ≥ 0 �2 ≥ 0 �� ≥ 0 for j = 1,2,3,4,5
If a slack variable equals 0 in the current solution, then this solution lies on the
constraint boundary for the corresponding functional constraint. A value
greater than 0 means that the solution lies on the feasible side of the constraint
boundary , whereas a value less than 0 means that the solution lies on the
infeasible side of this constraint boundary
An Augmented solution is a solution for the original variables( the decision
variables) that has been augmented by the corresponding values of the slack
variables are
For example, augmenting the solution (3,2) in the example yields the
augmented solution (3,2,1,8,5) because the corresponding values of the slack
variables are �3 = 1 �4 = 8 �5 = 5
A basic solution is an augmented corner-point solution
The fact that corner-point solution(and so basic solutions) can be either
feasible or infeasible implies the following definition
A basic feasible solution(BF) is an augmented CPF solution
Thus, the CPF solution (0,6) in the example is equivalent to the BF solution
(0,6,4,0,6) for the problem in augmented form.
A basic solution has the following properties:
1. Each variable is designated as either a nonbasic variable or basic variable
2. The number of basic variables equals the number of functional
constraints(now equations). Therefore, the number of nonbasic variables
equals the total of variables minus the number of functional constraints
3. The nonbasic variables are set equal to zero
4. The values of the basic variables are obtained as the simultaneous solution
of the system of equation(functional constraints in augmented form). (The set
of basic variables is often referred to as the basis)
5. If the basic variables satisfy the nonnegativity constraints, the basic solution
is a BF solution
To illustrate these definition, consider again the BF Solution(0,6,4,0,6). This
solution was obtained before by augmenting the CPF solution(0,6). However,
another way to obtain this same solution is to choose �1 and �4 to be the two
nonbasic variables and so the two variables are set equal to zero. The three
equations then yield, respectively �3 = 4, �2 = 6 ��� �5 = 6 as the solution for
the three basic variables
Because all three of these basic variables are nonnegative, this basic solution
0,6,4,0,6) is indeed BF solution.
To illustrate adjacent BF solution, consider one pair of adjacent CPF solution
in the figure: (0,0) and (0,6). Their augmented solutions (0,0,4,12,18) and
(0,6,4,0,6) automatically are adjacent BF soluton. Another signpost is that their
nonbasic variable ( �1 , �2 ) and (x1 , x4) are the same with just one
exception- �2 has been replaced by �4 .Consequently moving from
(0,0,4,12,18) to (0,6,4,0,6) involves switching �2 from nonbasic to basic and
vice verssa for �4 .
When we deal with with the problem in augmented form, it is convinient to
consider and manipulate the objective function equation at the same time as
the new constraint equations.
Hence maximize Z
(0) Z − 3x1 − 5x2 = 0
(1) �1 + �3 = 4
(2) 2x2 + x4 = 12
(3) 3�1 + 2�2 + �5 = 18
And
�1 ≥ 0 �2 ≥ 0
Therefore, when using Eq.(1) to (3) to obtain a basic solution, we use Eq. (0) to solve
for Z at the same time
Geometric and Algebraic Interpretations of how the simplex method solves the
Wyndor Glass Co. Problem
Method Sequence Geometric Algebraic Interpretation
Interptretation
Initialization Choose (0,0) to be the Choose �1 and �2 to
initial CPF solution be the nonbasic
variables(=0) for the
initial BF
solution:(0,0,4,12,18)
Optimality test Not optimal, because Not optimal, because
moving along either increasing either
edge from (0,0) nonbasic variable
increases Z (x1 or x2 ) increases Z
Iteration 1 Move up the edge lying Increase �2 while
Step 1 on the �2 axis. adjusting other variable
values to satisfy the
system of equations
Step 2 Stop when the first new Stop when the first basic
constraint boundary variable (x3 , x4 , x5 ) drops
(2x2 = 12) is reached. to zero (x4 )
Step 3 Find the intersection of With �2 now a basic
the new pair of variable and �4 now a
constraint boundaries: nonbasic variable, solve
(0,6) is the new CPF the system of equations:
solution (0,6,4,0,6) is the new BF
solution.
Optomality Test Not optimal, because Not optimal , because
moving along the edge increasing one nonbasic
from (0,6) to the right variable (x1 ) increases Z
increases Z
Iteration 2 Move along this edge to Increase x1 while
Step 1 the right adjusting other variable
values to satisfy the
system of equations
Step 2 Stop when the first new Stop when the first basic
constraint boundary variable with
(3x1 + 2x2 = 18) is (�2 , �3 �� �5 ) drops to
reached zero (�5 )
Step 3 Find the intersection of With �1 now a basic
the new pair of variable and �5 now a
constraint boundaries: nonbasic variable, solve
(2,6) is the new CPF the system of equations:
solution (2,6,2,0,0) is the new BF
solution
Optimality test (2,6) is optimal because (2,6,2,0,0) is optimal,
moving along either because increasing
edge from (2,6) either nonbasic variable
decrease Z (x4 or x5 ) decrease Z.
Initialization
Whenever possible, the initialization of the simplex method chooses the origin( all decision
variable equal to zero) to be the initial CPF solution. This choice eliminates the work
required to solve for the basic variables (�3 , �4 , �5 ) from the following system of equations.
�1 + �3 = 4
2x2 + x4 = 12
3�1 + 2�2 + �5 = 18
Since �1 = 0 and �2 = 0
�1 = 0 �2 = 0
�3 = 4
�4 = 12
x5 = 18
Thus, the initial BF solution(0,0,4,12,18)
Optimality Test
The objective function is Z = 3x1 + 5x2 substituting the values of nonbasic variables
Z = 0 for the initial BF solution. We can adjust the values based on the objective function
Determining the direction of movement
Z = 3x1 + 5x2
Increase �1 Rate of improvement is Z = 3
Increase x2 Rate of improvement in Z = 5
5 > 3 so choose �2 to increase
�2 is the entering basic variable
Determining where to Stop
We want to go as far as possible without leaving the feasible region
�1 = 0 so
(1) �1 + �3 = 4 �3 = 4
(2) 2x2 + x4 = 12 x4 = 12 − 2x2
(3) 3�1 + 2�2 + �5 = 18 �5 = 18 − 2�2
The other requirement for feasibility is that all the variables be nonnegative.
�3 = 4 ≥ 0 → �� ����� ��������
12
x4 = 12 − 2x2 ≥ 0 → x2 ≤ 2 = 6 minimum
18
�5 = 18 − 2�2 ≥ 0 → �2 = =9
2
Thus �2 can be increased just to 6 at which x4 has dropped to 0. Increasing �2 beyond 6
would cause x4 to become negative, which would violate feasibility. These calculations is
referred to as the minimum ratio test
Solving for the new BF Solution
Initial BF solution New BF solution
Nonbasic variables �1 = 0 �2 = 0 �1 = 0 �4 = 0
Basic variables �3 = 4 �4 = 12 �5 = 18 �3 = ? �2 = 6 �5 = ?
The coefficients of �4 (0,0,1,0) will be the new coefficients of �2
(2) 2x2 + x4 = 12
1
x2 + x4 = 6
2
Z = 3x1 + 5x2
(0) Z − 3x1 − 5x2 = 0
(1) Z − 3x1 − 5x2 = 0
1
Z − 3x1 − 5x2 + 5(x2 + x4 ) = 6(5)
2
5
(0)Z − 3x1 + 2 x4 = 30
(1) �1 + �3 = 4
2x2 + x4 = 12
1
(2) x2 + 2 x4 = 6
1
3�1 + 2�2 + �5 − 2(x2 + 2 x4 ) = 18 − 6(2)
(3) 3�1 − x4 + �5 = 6
With x1 = 0 and x4 = 0 the equations will yield new BF solution (x1 , x2 , x3 , x4 , x5 , ) =
(0,6,4,0,6). This procedure is called Gauss-Jordan method of elimination
Optimality Test
5
Z = 30 + 3x1 − 2 x4 x1 has positive coefficient increasing would lead lead to higher z
Iteration 2
x1 be the entering basic variable
4
�1 + � 3 = 4 �3 =− �1 + 4 ≥ 0 → �1 ≤ 1 = 4
x2 = 6 ≥ 0 no upper bound
6
3�1 − x4 + �5 = 6 �1 = 6 − 3�1 ≥ 0 �1 ≤ 3 = 2 �������
The minimum ratio test indicates �5 is the leaving basic variable
The coefficients of �5 (0,0,0,1) is now the coefficient of �1
Hence
3
(0)z + 2 x4 + x5 = 36
1 1
(1) �3 + 3 �4 − 3 �5 = 2
1
(2) �2 + 2 �4 = 6
1 1
(3) �1 − 3 �4 + 3 �5 = 2
Therefore the next BF solution is (x1 , x2 , x3 , x4 , x5 , ) = (2,6,2,0,0) yielding Z = 36
With the objective function
3
Z = 36 − 2 x4 − x5 increasing x4 or x5 would decrease Z. Therefore the current Basic
feasible solution must be the optimal.
From the 1st example on solving linear programming with the graph of inequalities
Z = 500x + 350y objective function
constraints
3x + 2y ≤24
x + 2y ≤ 16
x+y ≤ 9
Z − 500x − 350y = 0 (0)
P = 24 − 3x − 2y
p + 3x + 2y = 24 (1)
q = 16 − x − 2y
q + x + 2y = 1 (2)
r=9−x−y
r+x+y = 9 (3)
x≥0
y≥0
Initialization x = 0 and y = 0
(x, y, p, q, r, )
p = 24
q = 16
r=9
(0,0,24,16,9)
From Z = 500x + 350y increasing value of x leads to a higher value of Z
p + 3x = 24 24 − 3x ≥ 0 x ≤8 minimum
q + x = 16 16 − x ≥ 0 x ≤ 16
r+x = 9 9−x≥0 x≤9
X can be increased to 8 and p = 0
x=8 y=0 p=0 q=? r=?
Hence (0,1,0,0) will be the coefficient of x
Z − 10x − 7y = 0
10
(P + 3x + 2y = 24)
3
10 1
Z+ 3
p − 3 y = 80 (0)
P + 3x + 2y = 24 (1)
q + x + 2y = 16
1
(p + 3x + 2y = 24)
3
1 4
q − 3p+ 3y = 8 (2)
r+x+y = 9
1
(p + 3x + 2y = 24)
3
1 1
r − 3p+ 3y = 1 (3)
Hence q = 8 and r = 1
The values now are (8,0,0,8,1)
Increasing y lead higher value of Z
p + 3x + 2y = 24
p is 0
3x + 2y = 24
3x = 24 − 2y ≥ 0
24 ≥ 2y
y ≤ 12
4
q+ y=8
3
4
8− y≥0
3
4
�≤8
3
y≤6
1
r+ y= 1
3
1
1− y≥0
3
1
y≤1
3
y ≤ 3 minimum
Hence y = 3 p=0 r=0 x=? q=?
Coefficient of y is (0,0,0,1)
10 1
Z+ p − y = 80
3 3
1 1
r− p+ y= 1
3 3
Z + r + 3p = 81 (0)
p + 3x + 2y = 24
1 1
6(r − p + y = 1)
3 3
3x+3p−6r=18 (1)
1 4
q− p+ y = 8
3 3
4 4
4(r − p + ) = 1
3 3
1 4
q− p+ y = 8
3 3
4 4
4r − p + y = 4
3 3
q − 4r + p = 4 (2)
1 1
r − 3 p + 3 y = 1 (3)
3x + 3p − 6r = 18 p = 0 and r = 0
3x = 18
x=6
q − 4r + p = 4
q=4
(6,3,0,4,0)
Z + r + 3p = 81
With p = 0 and r = 0 z = 81(50) = 4050
increasing either r or p decreases the value of Z
Thus the optimum number of unit produced for product x is 6 while 3 for product y
with the maximum profit of $4050