Engineering Optimization (ME F344 and ME F

Department of Mechanical
Engineering
BITS Pilani K. K. Birla Goa campus
Instructor in charge: Dr. Biswajit Das

Dr. Manoj Kumar Pandey

BITS Pilani Goa campus
 Simplex algorithm, is a popular algorithm used for numerically
solving linear programming problems.

 The algorithm was introduced by the American Mathematician

George B. Dantzig in 1947.

 The technique first published in the journal “Computing in

Science and Engineering”

 Listed as one of the top 10 algorithms of the century.

 The method uses the concept of a simplex, which is a polytope

(such as polygon, polyhedron etc.,) with finite number of vertices.

 A polytope is a geometric object with flat sides, and may exist in

any general number of dimensions n as an n-dimensional polytope
or n-polytope Manoj Kumar Pandey, OPTIMIZATION 2
2-dimensional Polytope

Dr. Manoj Kumar Pandey

How to Solve an LPP of higher dimension ?
 The constraints of a Linear Programming Problem give
rise to a polytope with finite number of vertices.

 If we can determine all the vertices of the polytope, then

we can calculate the value of the objective function at
these points and take the best one as our optimal
solution.

 The Simplex Method is an iterative method which

moves from one vertex to another vertex (in the
direction of optimum improvement) until the optimal
solution is reached
Dr. Manoj Kumar Pandey
Dr. Manoj Kumar Pandey
Simplex Method

An iterative Initialization
procedure (Find initial BFS)

Is the current Stop

BFS optimal?

Move to a better
adjacent BFS

Manoj Kumar Pandey, OPTIMIZATION 6

Initial Assumptions

• All constraints are of ≤ type

• All right-hand-side values (bj, j=1, …,m) must

be non-negative

Manoj Kumar Pandey, OPTIMIZATION 7

Initialization

• Find an initial basic feasible solution

“If possible, use the origin as the initial BFS”

• Equivalent to:

Choose original variables to be non basic (xi=0, i=1,…n) and

let the slack variables be basic (sj=bj, j=1,…m)

Manoj Kumar Pandey, OPTIMIZATION 8

Optimality Test

• Are any adjacent BFS better than the current one?

• Rewrite Z in terms of nonbasic variables and investigate
rate of improvement
• Current nonbasic variables: x1 , x2
• Corresponding Z: Z = 3x1 + 5x2

Manoj Kumar Pandey, OPTIMIZATION 9

Direction of Movement

• Which edge to move on?

• Determine the direction of movement by selecting the
entering variable (variable ‘entering’ the basis)
• Choose the direction of steepest ascent
– x1: Rate of improvement in Z = 3
– x2: Rate of improvement in Z = 5

• Entering basic variable = x2

Manoj Kumar Pandey, OPTIMIZATION 10

The nonbasic variable that will become basic is referred to as
“entering” variable.

The basic variable that will become nonbasic is referred to as

“leaving” variable.

Criterion for “entering” variable

Choose that variable as the “entering” variable which has the
most –ve coefficient in the z-row in case it is a maximization
problem (most +ve coefficient in the z-row in case it is a
minimization problem) while writing it as an equation CX=0.

Manoj Kumar Pandey, OPTIMIZATION 11

Criterion for “leaving” variable (Feasibility Condition)

Let bi be the RHS of the ith row.

Let aij be the coefficient of the entering variable xj in the ith row.

The following “minimum ratio test” decides the leaving variable

Choose xk as the leaving variable where k is given as that row
index i for which the ratio

 bi 
 , aij  0  is Minimum
 aij 

Manoj Kumar Pandey, OPTIMIZATION 12

Simplex Method in Tabular form

Let us consider the following problem

Maximize Z= 3x1+ 5x2

subject to
x1 ≤4
2x2 ≤ 12
3x1+ 2x2 ≤18
x1, x2 ≥ 0

Manoj Kumar Pandey, OPTIMIZATION 13

Write as system of equations

Z - 3x1 - 5x2 =0
x1 +s1 =4
2x2 +s2 = 12
3x1+ 2x2 +s3 = 18

Manoj Kumar Pandey, OPTIMIZATION 14

 Basic
variable
Z x1 x2 s1 s2 s3 Solution

s1

s2

s3

Manoj Kumar Pandey, OPTIMIZATION 15

 Z-row is the objective equation row.

 The remaining 3 rows are the basic variable rows.

 Each row corresponds to a basic variable

Manoj Kumar Pandey, OPTIMIZATION 16

Iteration 1 :

Basic x1 x2 s1 s2 s3
Z Solution
variable

Z 1 -3 -5 0 0 0 0

s1 0 1 0 1 0 0 4

s2 0 0 2 0 1 0 12

s3 0 3 2 0 0 1 18

Manoj Kumar Pandey, OPTIMIZATION 17

Choose that variable as the “entering” variable which has the most –ve
coefficient in the z-row in case it is a maximization
x2 enters the basis
Basic Min.
Z x1 x2 s1 s2 s3 Solution Ratio
variable
0/-5=No Ratio
Z 1 -3 -5 0 0 0 0
4/0= ---------
s1 0 1 0 1 0 0 4
12/2 =6
s2 0 0 2 0 1 0 12
18/2 =9
s3 0 3 2 0 0 1 18

Minimum Ratio is corresponding to S2

S2 leaves the basis

Manoj Kumar Pandey, OPTIMIZATION 18

 The entering variable column is called the pivot column.

The leaving variable row is called the pivot row.

The coefficient in the intersection of the two is referred to as

the pivot element.

Apply elementary row operations to modify the simplex tableau so that

the pivot column has 1 at the pivot element and zero in all other
places.

Pivot row
New pivot row= Current pivot row/ pivot element

All other rows (Z also)

New row=(current row)-(pivot column coefficient)×(new pivot
row) Manoj Kumar Pandey, OPTIMIZATION 19
Iteration 2 :
Min.
Basic Ratio
Z x1 x2 s1 s2 s3 Solution
variable

Z 1 -3 0 0 5/2 0 30 No Ratio
4/1 = 4
s1 0 1 0 1 0 0 4
x2 0 0 1 0 1/2 0 6 -------
6/3 =2
s3 0 3 0 0 -1 1 6

Stop: If all the entries in the Z-row are ≥ 0 ( or ≤ 0 )

in Max. (or Min.) then stop else repeat the iteration.

Manoj Kumar Pandey, OPTIMIZATION 20

 Basic x1 x2 s1 s2 s3
Z Solution
variable

Z 1 0 0 0 3/2 1 36

s1 0 0 0 1 1/3 -1/3 2

x2 0 0 1 0 1/2 0 6

x1 0 1 0 0 -1/3 1/3 2

All the entries in the Z-row are ≥ 0, hence we have reached

the optimal solution.

Optimal Solution: x1 = 2, x2 = 6, Z=36

Manoj Kumar Pandey, OPTIMIZATION 21

 Optimal
Solution
(0, 6) (2, 6)

Feasible (4, 3)
Region

(0, 0) (4, 0)

Manoj Kumar Pandey, OPTIMIZATION 22

Example 2:

Min Z = x1 -2x2 + x3
subject to
x1 + 2x2 -2x3 ≤4
x1 -x3 ≤3
2x1 -x2 +2x3 ≤ 2
x1 , x2 , x3 ≥0

Manoj Kumar Pandey, OPTIMIZATION 23

Standard Form

Min Z = x1 -2x2 + x3
subject to
x1 + 2x2 -2x3 + s1 =4
x1 -x3 + s2 =3
2x1 -x2 +2x3 + s3 = 2
x 1 , x 2 , x 3 , s1 , s2 , s3 ≥ 0

Manoj Kumar Pandey, OPTIMIZATION 24

System of equations

Z - x1 + 2x2 - x3 =0
x1 + 2x2 -2x3 + s1 =4
x1 - x3 + s2 =3
2x1 - x2 + 2x3 + s3 = 2

Manoj Kumar Pandey, OPTIMIZATION 25

BV Z x1 x2 x3 S1 S2 S3 Solution Ratio

Z 1 -1 2 -1 0 0 0 0 ---

S1 0 1 2 -2 1 0 0 4 4/2=2
S2 0 1 0 -1 0 1 0 3 -----
S3 0 2 -1 2 0 0 1 2 -----
Z 1 -2 0 1 -1 0 0 -4 ---

x2 0 1/2 1 -1 ½ 0 0 2 -----

S2 0 1 0 -1 0 1 0 3 -----
S3 0 5/2 0 1 ½ 0 1 4 4/1=1

Manoj Kumar Pandey, OPTIMIZATION 26

BV Z x1 x2 x3 S1 S2 S3 Solution Ratio

Z 1 -9/2 0 0 -3/2 0 -1 -8 ---

x2 0 3 1 0 1 0 1 6 -----
S2 0 7/2 0 0 ½ 1 1 7 -----
x3 0 5/2 0 1 ½ 0 1 4 -----

The table is Optimal, since all the coefficient in

Z-row are ≤ 0 (Minimization Problem).
Optimal solution : x1= 0, x2 = 6, x3 = 4, Z = -8
Manoj Kumar Pandey, OPTIMIZATION 27
Example 3:

Max Z = -x1 +3x2 -3x3

subject to
3x1 -x2 +x3 ≤ 7
-x1 +2x2 ≤6
-4x1 +3x2 +8x3 ≤ 10
x1 , x2 , x3 ≥0

Manoj Kumar Pandey, OPTIMIZATION 28

 Points to Remember in Simplex Algorithm

 All the constraints should be ≤ type.

 All variables should be ≥ 0.

 Coefficients of basic variables in z-row should be zero.

 The coefficients matrix corresponding to initial basic

variables forms an identity matrix.

 The entering variable will be the one which has most

negative (most positive) z-row coefficient in case of max.
(min.) problem.

Manoj Kumar Pandey, OPTIMIZATION 29

 Points to Remember …..

 Leaving variable should follow the minimum ratio test.

 When all the z-row coefficients are ≥ 0 (or ≤ 0) in case of

max. (or min.) problem the optimality is reached and we
will stop the simplex iteration.

Manoj Kumar Pandey, OPTIMIZATION 30