The Simplex Method

Ganesh Thapa
Simplex Method
• The graphical approach can be used for two-variable LP problems

• Unfortunately, most real-life LPs problems require a method to find

optimal solutions capable of dealing with several variables: the
simplex algorithm
Simplex Method
Formulation
 Simplex Method - Formulation
In LP problem, the decision maker
usually wants to:
 maximize (usually revenue or profit)
 minimize (usually costs) LP Problem

the objective function (Z) is

expressed by a set of decision Max: Z = 90 x1 + 120 x2
variables
Certain limitations are often Subject to:
imposed to these decision variables x1 ≤ 40
(expressed in the form of ≤, = or
≥). x2 ≤ 50
These restrictions are called 2x1 + 3x2 ≤ 180
constraints and x1 ≥ 0; x2 ≥ 0
Simplex Method - Formulation
The Simplex algorithm is an algebraic procedure to solve LP problems based on geometric
concepts that requires LP problems to be presented in the standard form:

• 1) Objective function is maximized Max: Z = 90 x1 + 120 x2

• 2) Constraints in the form of ≤ inequalities Subject to:

x1 ≤ 40
x2 ≤ 50
• 3) All values on the right handside are ≥0 2x1 + 3x2 ≤ 180
• 4) All variables are nonnegative (≥) and x1 ≥ 0; x2 ≥ 0
Simplex Method - Formulation
The Simplex algorithm is an algebraic procedure to solve LP problems based on geometric
concepts that must be translated into algebraic language to allow solving systems of equations.

1st - transform all the constraints to equality by introducing slack, surplus, and
artificial variables as follows:

Constraint type Variable to be added

≥ + slack (s)

≤ - Surplus (s) + artificial (A)

= + Artificial (A)
Simplex Method - Formulation
The Simplex algorithm is an algebraic procedure to solve LP problems based on geometric
concepts that must be translated into algebraic language to allow solving systems of equations.

1st - transform all inequalities into equalities by introducing one additional variable to
each constraint (the slack variables: S1, S2, S3).

Original form: Standard or augmented form:

Max: Z = 90 x1 + 120 x2 Max: Z = 90 x1 + 120 x2

Subject to: Subject to:

x1 + S1 ≤ 40 x1 + S1 = 40
x2 + S2 ≤ 50 x2 + S2 = 50
2x1 + 3x2 + S3 ≤ 180 2x1 + 3x2 + S3 = 180

and x1 x2 S1 S2 S3 ≥ 0 and x1 x2 S1 S2 S3 ≥ 0
Try for it
Max: Z = 3 x1 + 5 x2
Max: Z = 3 x1 + 5 x2 Subject to:
Subject to: x1 +S1 = 4
x1 ≤ 4 2 x2 + S2 = 12
2 x2 ≤ 12 3x1 + 2x2 + S3 = 18
3x1 + 2x2 ≤ 18 and x1 , x2 ,S1,S2 ≥ 0
and x1 , x2 ≥ 0

Min Z =2 X1 + 3 X2 …..
Min Z =2 X1 + 3 X2
S.t.
S.t.
½ X1 + ¼ X2 + S1 = 4
½ X1 + ¼ X2 ≤ 4
X1 + 3X2 –S2 + A1 = 20
X1 + 3X2  20
X1 + X2 +A2 = 10
X1 + X2 = 10
X1, X2  0
X1, X2  0
 Simplex Method - Formulation
The Simplex algorithm is an algebraic procedure to solve LP problems based on geometric
concepts that must be translated into algebraic language to allow solving systems of equations.

1st - transform all inequalities into equalities by introducing one additional variable to each
constraint (the slack variables: S1, S2, S3).
2nd - build the Simplex tabular form where only the essential information is recorded.

Coeff Basic Cj Max: Z = 90 x1 + 120 x2

of Varia
BV ble Subject to:
CB XB b X1 X2 S1 S2 S3 Ratio x1 + S1 = 40
x2 + S2 = 50
2x1 + 3x2 + S3 = 180
Zj and x1 x2 S1 S2 S3 ≥ 0
Zj - Cj
 Simplex Method - Formulation
The Simplex algorithm is an algebraic procedure to solve LP problems based on geometric
concepts that must be translated into algebraic language to allow solving systems of equations.

1st - transform all inequalities into equalities by introducing one additional variable to each
constraint (the slack variables: S1, S2, S3).
2nd - build the Simplex tabular form where only the essential information is recorded.

Coeff Basic Cj 90 120 0 0 0 Max: Z = 90 x1 + 120 x2

. Of Varia
BV ble Subject to:
CB XB b X1 X2 S1 S2 S3 Ratio x1 + S1 = 40
40 1 0 1 0 0 x2 + S2 = 50
50 0 1 0 1 0
2x1 + 3x2 + S3 = 180
180 2 3 0 0 1
Zj and x1 x2 S1 S2 S3 ≥ 0
Zj - Cj
 Simplex Method - Formulation
The Simplex algorithm is an algebraic procedure to solve LP problems based on geometric
concepts that must be translated into algebraic language to allow solving systems of equations.

1st - transform all inequalities into equalities by introducing one additional variable to
each constraint (the slack variables: S1, S2, S3).
2nd - build the Simplex tabular form where only the essential information is recorded

Coff. BV Cj 90 120 0 0 0
BV Each basic feasible solution has basic or non-
basic variables
CB XB b X1 X2 S1 S2 S3 Ratio
0 S1 40 1 0 1 0 0 - non-basic variables are set to ZERO
0 S2 50 0 1 0 1 0 - basic variables are directly obtained from
0 S3 180 2 3 0 0 1 the table having coefficient 0 or 1
Zj
Zj - Cj initialize the procedure setting x1 = x2 = 0
Non-basic Basic
variables variables (X1, X2, S1, S2, S3 ) =( 0, 0, 40, 50, 180)
Simplex Method - Graphical analysis
• The Simplex algorithm is a search procedure that:
- shifts through the set of basic feasible solutions, one at a time, until the optimal
basic feasible solution (whenever it exists) is identified.
- the method is an efficient implementation the Corner Points Procedure.

Corner point feasible solutions –

B= (0,50)
C= (15,50) vertices of the feasible region
Optimal solution(s) – vertices(s) of
D= (40,33) the feasible region that maximize Z,
i.e. solution that gives the best
A= (0,0)
E= (40,0) favorable value to the objective
function
Simplex Method - Graphical analysis
• The Simplex algorithm is a search procedure that:
- shifts through the set of basic feasible solutions, one at a time, until the optimal basic
feasible solution (whenever it exists) is identified.
- the method is an efficient implementation the Corner Points Procedure.
Replacing X1 and X2 by the values of A, B, C, D
B= (0,50) C= (15,50)
and E in the objective function:
ZA= 0
D= (40,33)
ZB= 6000
ZC= 7350
A= (0,0) E= (40,0) ZD= 7600 Z = 90 x1 + 120 x2
ZE = 3600
Simplex Method - Graphical analysis
• The Simplex algorithm is a search procedure that:
- shifts through the set of basic feasible solutions, one at a time, until the optimal
basic feasible solution (whenever it exists) is identified.
- the method is an efficient implementation the Corner Points Procedure.

Feasible solutions – within or on the

B= (0,50) C= (15,50) border of the feasible region ie
solutions for which the constraints are
satisfied
D= (40,33)

Infeasible solution – outside the

A= (0,0) E= (40,0) feasible region, ie solution for which
at least one constraint is violated
Simplex Method
Procedure
 Simplex Method - Procedure
Bring the LP problem to the standard form -> obtain a BFS ie set (x1, x2) = (0, 0)

Optimality check:
The current BFS is optimal (in a No Find another feasible solution
max LP) if every coefficient in
Row Zj - Cj is ≥ 0. Entering variable: Choose the entering variable (in a max problem) to be
the NBV with the most negative coefficient in Row Zj - Cj .
Yes
Leaving BV: apply minimum ratio test - identify the row with the smallest
+ve ratio RHS /aij (the most restrictive Row); the BV for this row is the
leaving BV (it becomes nonbasic).
Apply Gauss-Jordan elimination procedure to solve the system of linear
equations.

Optimal feasible solution found – STOP SIMPLEX

 Simplex Method - Procedure
Coff. BV Cj 90 120 0 0 0 Step 1: Calculate Zj in Column of X1 =
BV Σ CB* X1
=0 * 1 + 0 * 0 + 0 * 2
CB XB b X1 X2 S1 S2 S3 Ratio =0
0 S1 * 40 1 + 0 1 0 0 Step 2: Complete same process for the
0 S2 * 50 0 + 1 0 1 0 column of X2, S1,S2 and S3
0 S3 * 180 2 3 0 0 1 Step 3: Calculate Zj - Cj
Zj 0 0 0 0 0
Zj - Cj -90 -120 0 0 0
Max: Z = 90 x1 + 120 x2
Max: Z = 90 x1 + 120 x2 Subject to:
Subject to: x1 + S1 = 40
x1 + S1 ≤ 40 x2 + S2 = 50
x2 + S2 ≤ 50 2x1 + 3x2 + S3 = 180
2x1 + 3x2 + S3 ≤ 180 and x1 x2 S1 S2 S3 ≥ 0
and x1 , x2, S1 , S2, S3 ≥0
 Simplex Method - Procedure
Coff.B BV Cj 90 120 0 0 0 Optimality check: Every coefficient in
V Row Zj - Cj is not ≥ 0.

CB XB b X1 X2 S1 S2 S3 Ratio
0 S1 40 1 0 1 0 0 Undefined Find another feasible solution
0 S2 50 0 1 0 1 0 50
0 S3 180 2 3 0 0 1 60
Zj 0 0 0 0 0 Entering variable: variable (in a max problem)
Zj - Cj -90 -120 0 0 0 to be the NBV with the most negative
coefficient in Row Zj - Cj . = X2 (aij )
Leaving BV: apply minimum ratio test - identify the row with
the smallest +ve ratio b/aij (the most restrictive Row); = S 2

Apply Gauss-Jordan elimination procedure to solve the system

of linear equations.
 Simplex Method - Procedure
Coff.B BV Cj 90 120 0 0 0
V
CB XB b X1 X2 S1 S2 S3 Ratio
0 S1 40 1 0 1 0 0 Make X2 In the form Such that X2 is 1
Undefined
0 S2 50 0 1 0 1 0 50
in the row of leaving variable and 0
0 S3 180 2 3 0 0 1 60 in remaining Rows
Zj 0 0 0 0
Zj - Cj -90 0-120 0 0 0

Coff.B BV Cj 90 120 0 0 0 Replace S2 by X2 in the column of BV

V and also update its coefficients.
CB XB b X1 X2 S1 S2 S3 Ratio
0 S1 40 1 0 1 0 0
120 X2 50 0 1 0 1 0 R3 = R3 – 3 * R2
0 S3 30 2 0 0 -3 1 Calculate New Zj and Zi- Cj
Zj 0 120 0 120 0
Zj - Cj -90 0 0 120 0
 Simplex Method - Procedure
Coff.B BV Cj 90 120 0 0 0 Optimality check: Every coefficient in Row
V Zj - Cj is not ≥ 0.
Find another feasible solution
CB XB b X1 X2 S1 S2 S3 Ratio
0 S1 40 1 0 1 0 0 40

120 X2 50 0 1 0 1 0 Undefined Entering variable: variable (in a max problem)

0 S3 30 2 0 0 -3 1 15 to be the NBV with the most negative
Zj 0 120 0 120 0 coefficient in Row Zj - Cj . = X1 (aij )
Zj - Cj -90 0 0 120 0
Leaving BV: apply minimum ratio test -
Coff.B BV Cj 90 120 0 0 0 identify the row with the smallest +ve
V
ratio b/aij (the most restrictive Row); = S 3
CB XB b X1 X2 S1 S2 S3 Ratio
0 S1 25 0 0 1 3/2 -1/2 Apply Gauss-Jordan elimination
120 X2 50 0 1 0 1 0 procedure
New R3 = R3 * ½
90 X1 15 1 0 0 -3/2 1/2
R1 = R1 – New R3
Zj 90 120 0 -15 45 Recalculate Zj and Zj - Cj
Zj - Cj 0 0 0 -15 45
 Simplex Method - Procedure
Coff.B BV Cj 90 120 0 0 0 Optimality check: Every coefficient in Row Zj -
V Cj is not ≥ 0.
Find another feasible solution
CB XB b X1 X2 S1 S2 S3 Ratio
0 S1 25 0 0 0 3/2 -1/2 50/3
120 X2 50 0 1 0 1 0 50 Entering variable: variable (in a max problem)
90 X1 15 1 0 0 -3/2 1/2 -10 to be the NBV with the most negative
Zj 90 120 0 -15 45 coefficient in Row Zj - Cj . = S2 (aij )
Zj - Cj 0 0 0 -15 45
Leaving BV: apply minimum ratio test - identify the
Coff.B BV Cj 90 120 0 0 0 row with the smallest positive ratio b/aij (the
V
most restrictive Row); = S 1
CB XB b X1 X2 S1 S2 S3 Ratio Apply Gauss-Jordan elimination
0 S2 50/3 0 0 0 1 -1/3 procedure
120 X2 100/3 0 1 0 0 1/6 New R1 = 2/3 * R1
90 X1 40 1 0 0 0 0 R2 =R2- NewR1
Zj 90 120 0 0 20 R3 = R3+(3/2)*R1
Recalculate Zj and Zj - Cj
Zj - Cj 0 0 0 0 20
 Simplex Method - Procedure
Coff.B BV Cj 90 120 0 0 0 Optimality check: Every coefficient in Row Zj -
V Cj is ≥ 0.

CB XB b X1 X2 S1 S2 S3 Ratio
0 S2 50/3 0 0 0 1 -1/3
120 X2 100/3 0 1 0 0 1/6 Optimal feasible solution found – STOP
90 X1 40 1 0 0 0 0 SIMPLEX
Zj 90 120 0 0 20
Zj - Cj 0 0 0 0 20

Max: Z = 90 x1 + 120 x2
X1 = 40
Subject to: 100/3
X2 =
x1 + S1 ≤ 40 0
S1 =
x2 + S2 ≤ 50 S2 = 16.67
2x1 + 3x2 + S3 ≤ 180 S3 = 0
and x1 x2 S1 S2 S3 ≥0 Z= 7600
Simplex Method –Example 2
• Max: Z = 3 x1 + 5 x2 • Max: Z = 3 x1 + 5 x2
Subject to: Subject to:
x1 ≤ 4 x1 + S1 = 4
2 x2 ≤ 12 2 x2 + S2 = 12
3x1 + 2x2 ≤ 18 3x1 + 2x2 + S3 = 18
and x 1 , x2 ≥ 0 and x1 , x2, S1 , S2, S3 ≥ 0

Coff.B BV Cj 3 5 0 0 0
V
CB XB b X1 X2 S1 S2 S3 Ratio
0 S1 4 1 0 1 0 0
0 S2 12 0 2 0 1 0
0 S3 18 3 2 0 0 1
Zj 0 0 0 0 0
Zj - Cj -3 -5 0 0 0