Module 1
Linear Programming Problems
Part 3 – Simplex Method
Course Instructor: Dr. Sahaya Jenifer A
Standard form of LPP
(i) All variables are non-negative
(ii) All the constraints are expressed as
equations
(iii) RHS of each constraint is non-negative
That is,
Min/Max 𝑍 = 𝑐 𝑥 + 𝑐 𝑥 + ⋯ + 𝑐 𝑥
subject to
𝑎 𝑥 + 𝑎 𝑥 + ⋯+ 𝑎 𝑥 = 𝑏
𝑎 𝑥 + 𝑎 𝑥 + ⋯+ 𝑎 𝑥 =
…………..
𝑎 𝑥 + 𝑎 𝑥 + ⋯+ 𝑎 𝑥 = 𝑏
𝑥 ≥ 0, 𝑏 ≥ 0
In matrix form,
Min/Max 𝑍 = 𝐶𝑥
subject to
𝐴𝑥 = 𝑏
𝑥 ,𝑏 ≥ 0
Slack variable
- represents the amount by which the LHS
falls short of the RHS of the constraint.
- added to the LHS of a " ≤ “ type constraint
𝑎 𝑥 +𝑎 𝑥 +𝑎 𝑥 ≤𝑏
⇒𝑎 𝑥 +𝑎 𝑥 +𝑎 𝑥 +𝑆 =𝑏
Surplus variable
- represents the amount by which the LHS
exceeds the RHS of the constraint.
- subtracted from the LHS of a " ≥ " type
constraint
𝑎 𝑥 +𝑎 𝑥 +𝑎 𝑥 ≥𝑏
⇒𝑎 𝑥 +𝑎 𝑥 +𝑎 𝑥 −𝑆 =𝑏
Note:
(i) If the RHS is ‘-ve’, multiply both sides by -1.
(ii) If the constraint is of " ≤ " type, add slack
variable to LHS.
(iii) If the constraint is of " ≥ " type, add
surplus variable to LHS.
(iv) If 𝑥 is unrestricted, define
𝑥 =𝑥 −𝑥
where 𝑥 , 𝑥 ≥ 0.
Example 15:
Write the standard
form of
Max 𝑍 = 3𝑥 + 9𝑥
Subject to
𝑥 + 4𝑥 ≤ 8
𝑥 + 2𝑥 ≤ 4
𝑥 ,𝑥 ≥ 0
Example 16:
Write the standard
form of
Min 𝑍 = 𝑥 + 𝑥
Subject to
𝑥 +𝑥 ≤6
3𝑥 + 2𝑥 ≤ −9
𝑥 + 5𝑥 ≥ 7
𝑥 ,𝑥 ≥ 0
Example 17:
Write the standard form
of
Min 𝑍 = 𝑥 − 2𝑥 + 𝑥
Subject to
2𝑥 + 3𝑥 + 4𝑥 ≥ −4
3𝑥 + 5𝑥 + 2𝑥 ≥ 7
𝑥 , 𝑥 ≥ 0;
𝑥 unrestricted
Example 18:
Write the standard form
of
Max 𝑍 = 3𝑥 + 𝑥 + 5𝑥
Subject to
4𝑥 + 𝑥 ≤ 1
𝑥 + 7𝑥 + 𝑥 ≥ −8
𝑥 + 9𝑥 = 2
𝑥 ,𝑥 ,𝑥 ≥ 0
DIY:
Write the standard form of
Min 𝑍 = −3𝑥 + 𝑥 + 𝑥 + 𝑥
Subject to
𝑥 − 2𝑥 + 𝑥 ≤ 11
−4𝑥 + 𝑥 + 2𝑥 + 3𝑥 ≥ 3
2𝑥 − 𝑥 = −1
𝑥 ,𝑥 ,𝑥 ≥ 0
Definitions
(i) Given a system of 𝑚 linear equations with 𝑛
variables with 𝑚 < 𝑛. The solution obtained by
setting (𝑛 − 𝑚) variables equal to 0 and solving
for the remaining 𝑚 variables is called Basic
solution.
The 𝑚 variables are called Basic variables and
the (𝑛 − 𝑚) variables which are put to 0 are
called as Non-basic variables.
!
No. of basic solutions: 𝑛𝐶 =
! !
(ii) A basic solution is said to be non-
degenerate if none of the basic variables is
zero.
A basic solution is said to be degenerate if
one or more of the basic variables are zero.
(iii) A feasible solution which is also basic is
called basic feasible solution.
Algebraic method Example:
Maximize 𝑍 = 40𝑥 + 50𝑥
subject to 𝑥 + 2𝑥 ≤ 40
4𝑥 + 3𝑥 ≤ 120
𝑥 ,𝑥 ≥ 0
Standard form:
Maximize 𝑍 = 40𝑥 + 50𝑥 + 0𝑠 + 0𝑠
subject to 𝑥 + 2𝑥 + 𝑠 = 40
4𝑥 + 3𝑥 + 𝑠 = 120
𝑥 ,𝑥 ,𝑠 ,𝑠 ≥ 0
Here, 𝑛 = 4, 𝑚 = 2 ⇒ 𝑛 − 𝑚 = 2
Non-basic Basic variables Basic Objective value
variables solution 𝑍
type
𝑥 = 0, 𝑥 = 0 𝑠 = 40, 𝑠 = 120 Feasible 0
𝑥 = 0, 𝑠 = 0 𝑥 = 20, 𝑠 = 60 Feasible 1000
𝑥 = 0, 𝑠 = 0 𝑥 = 40, 𝑠 = −40 Infeasible -
𝑥 = 0, 𝑠 = 0 𝑥 = 40, 𝑠 = −40 Infeasible -
𝑥 = 0, 𝑠 = 0 𝑥 = 30, 𝑠 = 10 Feasible 1200
𝑠 = 0, 𝑠 = 0 𝑥 = 24, 𝑥 = 8 Feasible 1360
The Simplex Method
- developed by George B. Dantzig during war
time research
- provides an iterative algorithm which consists
in moving from one vertex of the feasible region to
another vertex in such a way that the value of the
objective function is more (for max type) than at the
preceding vertex
- useful for complex LPPs with large number of
variables
How
simplex
method
works?
Simplex
Algorithm
Example 19:
Maximize 𝑍 = 3𝑥 + 4𝑥
subject to 𝑥 + 𝑥 ≤ 450
2𝑥 + 𝑥 ≤ 600
𝑥 ,𝑥 ≥ 0
Standard form:
Initial basic feasible solution:
Iteration 1:
Basic 𝑥 𝑥 𝑠 𝑠 RHS
𝑠
𝑠
𝑍
Optimal condition is satisfied?
Optimality condition:
For maximization problem, all the value of
𝑍 −row must be ≥ 0.
Here,
Entering variable:
𝑍-row values represent increase per unit of
entering a non-basic variable into the basic
solution ⇒ make as much money as possible.
Here,
Leaving variable:
The ratios give the intercepts of the
constraint lines with the entering variable axis. We
look for the minimum distance to travel in the
entering variable direction.
So, Leaving basic variable is the one with minimum
non-negative ratio.
Here,
How to pivot: Gauss-Jordan operation
(i) New pivot row = current pivot row/ pivot
element
(ii) Other rows = current row – (new pivot row
x pivot column coeff.)
Iteration 2:
Basic 𝑥 𝑥 𝑠 𝑠 RHS
Optimal condition is satisfied?
Example 20:
Min 𝑍 = 𝑥 − 3𝑥 + 2𝑥
subject to 3𝑥 − 𝑥 + 2𝑥 ≤ 7
−2𝑥 + 4𝑥 ≤ 12
−4𝑥 + 3𝑥 + 8𝑥 ≤ 10
𝑥 ,𝑥 ,𝑥 ≥ 0
Standard form:
Initial basic feasible solution:
Iteration 1:
Basic 𝑥 𝑥 𝑥 𝑠 𝑠 𝑠 RHS
𝑠
𝑠
𝑠
𝑍
Optimal condition is satisfied?
Iteration 2:
Basic 𝑥 𝑥 𝑥 𝑠 𝑠 𝑠 RHS
Optimal condition is satisfied?
Iteration 3:
Basic 𝑥 𝑥 𝑥 𝑠 𝑠 𝑠 RHS
𝑍
Optimal condition is satisfied?
Example 21:
Max 𝑍 = 𝑥 + 4𝑥 + 5𝑥
subject to 3𝑥 + 6𝑥 + 3𝑥 ≤ 22
𝑥 + 2𝑥 + 3𝑥 ≤ 14
3𝑥 + 2𝑥 ≤ 14
𝑥 ,𝑥 ,𝑥 ≥ 0
Standard form:
Initial basic feasible solution:
Iteration 1:
Basic 𝑥 𝑥 𝑥 𝑠 𝑠 𝑠 RHS
𝑠
𝑠
𝑠
𝑍
Optimal condition is satisfied?
Iteration 2:
Basic 𝑥 𝑥 𝑥 𝑠 𝑠 𝑠 RHS
Optimal condition is satisfied?
Iteration 3:
Basic 𝑥 𝑥 𝑥 𝑠 𝑠 𝑠 RHS
𝑍
Optimal condition is satisfied?
DIY:
Max 𝑍 = 3𝑥 + 2𝑥 + 5𝑥
subject to
𝑥 + 4𝑥 ≤ 420
3𝑥 + 2𝑥 ≤ 460
𝑥 + 2𝑥 + 𝑥 ≤ 430
𝑥 ,𝑥 ,𝑥 ≥ 0
DIY:
Max 𝑍 = 15𝑥 + 6𝑥 + 9𝑥 + 2𝑥
subject to
2𝑥 + 𝑥 + 5𝑥 + 6𝑥 ≤ 20
3𝑥 + 𝑥 + 3𝑥 + 25𝑥 ≤ 24
7𝑥 + 𝑥 ≤ 70
𝑥 ,𝑥 ,𝑥 ,𝑥 ≥ 0
