Linear programming
Chapter IV: The Simplex Method
Najeh Aissaoui Fehri, Doctor
Tunis Business School
1
Content
• Terminologies
• The Simplex algorithm
• Illustrations
• Special cases
2
Simplex Method
The most frequently used method to
solve LP problems
3
Simplex Method: terminology
Standard Form
A linear program in which all the constraints are
written as equalities
Slack Variable
A variable added to the LHS of “Less than or equal to”
constraint to convert it into an equality
Surplus Variable
A variable subtracted from the LHS of “More than or
equal to” constraint to convert it into an equality
4
Simplex Method: terminology
Consider a system of m linear equations in n variables (n>m)
Basic Solution
It has (n-m) variables equal to zero and solves the system of equations for
the remaining m variables
Basic Feasible Solution(BFS)
If all the variables in basic solution are non negative
Optimum Solution
Any BFS which optimizes(maximizes or minimizes) the objective function
5
Simplex Method: terminology
Simplex Tableau
Net Evaluation
Tableau Form A table which is Row(Cj-Zj )
When a LP is used to keep track
The row containing
written in a tabular of the calculations
net profit or loss.
form prior to setting made at each
The numbers in this
up the Initial iteration when the
row are also known
Simplex Tableau simplex method is
as shadow prices
employed
6
Simplex Method: terminology
• Pivot Column: The column having largest positive
(or negative) value in the Net Evaluation Row for a
maximization(or minimization) problem
• Pivot Row: The row corresponding to variable that
will leave the table in order to make room for another
variable
• Pivot Element: The intersection of pivotal row and
pivotal column
7
Example
Maximize Z = 7X1+5X2
s.t. X1+2X2 ≤ 6
4X1+3X2 ≤ 12
X1; X2 ≥0
8
Step1: Convert the LP into a system of
linear equations
assign them zero
coefficients
add new slack
(profits) in the
variables
objective function
as shown below
9
Example
X1 + 2X2 +S1 =6
4X1 +3X2 +S2 = 12
• The Objective Function would be
Z = 7X1 + 5X2 + 0S1 + 0S2
10
Step 2: Obtain a Basic Solution to
the problem
These are the initial
values of slack
Put the decision variables
variables X1=X2=0 so
that S1=6 and S2=12 It corresponds to the
solution of “doing
nothing”
11
Step 3: Form the Initial Tableau
Initial Tableau
Cj 7 5 0 0
[Link]
Basic
Basic (XB/Pivotal
CB Variable X1 X2 S1 S2
Soln(XB) Col.)
(B)
0 S1 6 1 2 1 0 6/1=6
0 S2 12 4 3 0 1 12/4=3
Zj 0 0 0 0
(Net Evaluation)Cj - Zj 7 5 0 0
12
Step 4: Find (Cj-Zj) having highest
positive value
In the previous table,
the column
corresponding to X1 is
The corresponding the pivot column
column: Pivot
Column
X1 will be entering the
basis
13
Step 5: Ratio-test
Divide XB The row
values by the corresponding The variable of
corresponding to the minimum the pivot row
values of Pivot positive value is leaves the table
Column the Pivot Row
In the previous
table, the row
corresponding to
the slack variable
S2 is the pivot
row
14
Step 6: First Iteration
In the new table,
the entering
variable(X1)
substitutes the
leaving variable(S2)
New values of this row have to be obtained in the
following way
• R2(New)=R2(Old)/Pivot Element = R2(Old)/4
• R1(New)=R1(Old) - (Intersecting value of R1(Old) & Pivot Col)*R2(New)
• =R1(Old)-1*R2(New)
15
Cj 7 5 0 0
[Link]
Basic
Basic (XB/Pivotal
CB Variable X1 X2 S1 S2
Soln(XB) Col.)
(B)
0 S1 3 0 54 1 - 1/4
7 X1 3 1 3/4 0 1/4
Zj 7 21 4 0 74
(Net Evaluation)Cj - Zj 0 - 1/4 0 -74
16
Step 7: Optimality test
If all the (Cj-Zj) ≤
0: an optimum
solution is
reached
Else, repeat the
X1=3, X2=0 and process as given
Z=21 in Steps 4,5 & 6
•In the example, it is
the case where
optimality is reached:
17
Pivoting
Given an LP in computational form and suppose that ark 0.
Pivoting on ark consists of the following operations:
1
i) Multiplying the rth row by ;
ark
ck
ii) Multiplying the rth row by − and adding it to the 0th row;
ark
ai k
iii) Multiplying the rth row by − and adding it to the
ark
ith row (i 0, r );
The row Ar . is called the pivot row, the column A.k is called the
pivot column, and ark is called the pivot element.
18
Effect of Pivoting
Pivoting transforms a system of equations into an equivalent system.
The coefficient of the new system are:
ck ck
Row 0 : cj '=cj − arj , b0 ' = b0 − br
ark ark
arj br
Row r : arj ' = , br ' =
ark ark
aik aik
Row i : aij ' = aij − arj bi ' = bi − br
ark ark
Remember
Pivot row is divided by the pivot element. Then elements of pivot column
become zeros except the pivot element which become 1. The rest are
19
obtained as follows:
Effect of Pivoting
Suppose that we want to get aij’. Enclose aij in a circle, aik and arj
In triangles, and the pivot element ark in a square. The pivot formula
is shown below it.
20
Important Note
Pivoting is an algebraic This algorithm moves from
process of moving from a corner to corner of the feasible
basic solution to another basic set in such a way that each
solution of the feasible set. new basic feasible solution is
This is the algebraic basis of at least as good as the
the Simplex Algorithm. previous one
21
Example
Max Z = 100X1 + 200X2
X1 + X2 ≤ 150
4X1 + 2X2 ≤ 440
X1 + 4X2 ≤ 480
X1 ≤ 90
X1 ≥ 0, X2 ≥ 0
22
Example
The standard form is written as:
Max Z = 100X1 + 200X2
X1 + X2 + S1 = 150
4X1 + 2X2 + S2 = 440
X1 + 4X2 + S3 = 480
X1 + S4 = 90
X1, X2, S1, S2, S3, S4 ≥ 0
Slack variables’ coefficients take the value zero in the OF
23
➢ In order to determine analytically the BFS of a LP, we start
by solving the system of binding constraints written in
standard form.
In our example, this system is formed by 4 equations and
six unknowns :
X1 + X2 + S1 = 150
4X1 + 2X2 + S2 = 440
X1 + 4X2 + S3 = 480
X1 + S4 = 90
24
✓ A basic solution is formed through a system for which the
number of equations is equal to the number of variables.
✓ In the previous example, to determine the BS, we let 2
variables vanish among 6. There are
6 6!
= = 15 ways to do that.
2 2!4!
25
G
(2)
(4)
F
H
A I
B
C J (3)
D (1)
O E K L M
26
The first simplex tableau of the previous example is given by:
100 200 0 0 0 0
X1 X2 S1 S2 S3 S4
0 S1 1 1 1 0 0 0 150
0 S2 4 2 0 1 0 0 440
0 S3 1 4 0 0 1 0 480
0 S4 1 0 0 0 0 1 90
The variables S1, S2, S3 & S4 are BV. The remaining variables,
X1 and X2, are NBV. 27
In order to move from a
BFS to an adjacent one, we
We can easily check that
need to switch from a BV
this solution is not optimal.
to a NBV.
It is sufficient to set X1 or X2
The entering variable (to
equal to 1 to obtain a better
the basis) is chosen so that
value of Z.
it may improve the best the
Z-value.
28
100 200 0 0 0 0
X1 X2 S1 S2 S3 S4
0 S1 1 1 1 0 0 0 150
0 S2 4 2 0 1 0 0 440
0 S3 1 4 0 0 1 0 480
0 S4 1 0 0 0 0 1 90
Zj 0 0 0 0 0 0
Cj - Zj 100 200 0 0 0 0
29
The coefficients of the BV in the matrix for which the rows and
columns are the Si’s form the identity matrix.
100 200 0 0 0 0
VB X1 X2 S1 S2 S3 S4 bi
0 S1 1 1 1 0 0 0 150
0 S2 4 2 0 1 0 0 440
0 S3 1 4 0 0 1 0 480
0 S4 1 0 0 0 0 1 90
Zj 0 0 0 0 0 0 0
Cj - Zj 100 200 0 0 0 0 30
Line Cj-Zj shows that if we increase
❖ The value of X1 by 1, then Z increases by 100 dinars
❖ The value of X2 by 1, then Z increases by 200 dinars
We increase the value of X2. We say that X2 is the entering
variable .
Since X1 keeps NBV, then :
X2 + S1 = 150
2X2 + S2 = 440
4X2 + S3 = 480
S4 = 90
31
Till what level can we
increase X2?
The value of the
EV must be the
minimum of This method of
The ratios are
positive ratios determining the
represented in a
obtained when level of the EV
column on the
dividing the is called the
right of the
RHS by the ratio test. It also
coefficients of identifies the LV simplex tableau
the EV in matrix
A
32
100 200 0 0 0 0
VB X1 X2 S1 S2 S3 S4 bi Ratio Test
0 S1 1 1 1 0 0 0 150 150/1=150
0 S2 4 2 0 1 0 0 440 440/2=220
0 S3 1 4 0 0 1 0 480 480/4=120
0 S4 1 0 0 0 0 1 90 -
Zj 0 0 0 0 0 0 0
Cj - Zj 100 200 0 0 0 0
33
• If X2 increases up to 120, S3 vanishes.
• S3 will leave the basis. S3 is called leaving variable
• The row of S3 is called pivot row
• The column of EV X2 is called pivot column
• The element 4, which is the intersection of the pivot
row and pivot column is called the pivot number
34
100 200 0 0 0 0
X1 X2 S1 S2 S3 S4 bi RT
0 S1 1 1 1 0 0 0 100 150
0 S2 4 2 0 1 0 0 440 220
0 S3 1 4 0 0 1 0 480 120
0 S4 1 0 0 0 0 1 90 -
Zj 0 0 0 0 0 0 0
Cj - Zj 100 200 0 0 0 0
35
We replace the leaving
variableS3 by the
entering variable X2
We divide the pivot row
by the pivot number
We subtract in the
other rows a multiple of
the new pivot row in a
way to obtain the
(scattered) identity
matrix for the new BV.
36
We obtain the following tableau:
100 200 0 0 0 0
X1 X2 S1 S2 S3 S4 bi
0 S1 1
3/4 10 1 0 -1/4
0 0 30
150
0 S2 4
7/2 20 0 1 -1/2
0 0 200
440
200
0 X
S32 1
1/4 41 0 0 1
1/4 0 120
480
0 S4 1 0 0 0 0 1 90
Zj 50 200 0 0 50 0 24000
Cj–Zj 50 0 0 0 -50 0 Z
37
100 200 0 0 0 0
X1 X2 S1 S2 S3 S4 bi
0 S1 3/4 0 1 0 -1/4 0 30
0 S2 7/2 0 0 1 -1/2 0 200
200 X2 1/4 1 0 0 1/4 0 120
0 S4 1 0 0 0 0 1 90
Zj 50 200 0 0 50 0 24000
Cj - Zj 50 0 0 0 -50 0
38
The obtained solution by a tableau is obtained by letting the
NBV vanish and solving the system consisting of binding
constraints written in standard form
39
➢ The BFS given by the last simplex tableau is:
X1=0, X2=120, S1=30, S2=200 ; S3=0 ; S4=90.
➢ This BFS corresponds to point A on the figure.
➢ The value of Z jumped from 0 to 24000.
➢ From row Cj–Zj, this new solution is not optimal.
➢ It suffices to enter variable X1 to the basis to improve Z.
40
We do the same to get the new tableau:
100 200 0 0 0 0
X1 X2 S1 S2 S3 S4 bi RT
0 S1 3/4 0 1 0 -1/4 0 30 40
0 S2 7/2 0 0 1 -1/2 0 200 400/7
200 X2 1/4 1 0 0 1/4 0 120 480
0 S4 1 0 0 0 0 1 90 90
Zj 50 200 0 0 50 0 24000
Cj – Zj 50 0 0 0 -50 0
41
100 200 0 0 0 0
X1 X2 S1 S2 S3 S4 bi
100 X1 1 0 4/3 0 -1/3 0 40
0 S2 0 0 -14/3 1 2/3 0 60
200 X2 0 1 -1/3 0 1/3 0 110
0 S4 0 0 -4/3 0 1/3 1 50
Zj 100 200 200/3 0 100/3 0 26000
Cj - Zj 0 0 -200/3 0 -100/3 0
42
Case of a Minimization Problem
• Consider the LP:
Min: Z = cx
s.t. Ax ≤ b
x≥0
43
Apply the same steps of the
simplex method as in the
the solution of LP is the same maximization problem, except
as that the optimality test and the
pivot column selection are
changed as follows:
Max: Z’ = - cx If all variables of the
s.t. Ax ≤ b last row ≥ 0, then
stop: the tableau is
x≥0 optimal
Else, select the
pivot column as the
one with the most
negative coefficient
in the last row
44
Special cases
Unbounded LP Multiple solutions
Optimal tableau has zero
The pivot column has only
entries for non-basic
negative or zero entries
solutions in the Cj–Zj row
The ratio test fails and hence
By pivoting on those rows
the relevant entering variable
we obtain new solutions with
can improve the objective
the same (optimal) value of Z
function with no stop
45