Linear Programming Simplex method -I

Introduction:
The geometric method of solving linear programming problems presented before.

The graphical method is useful only for problems involving two decision
variables and relatively few problem constraints.

Simplex method is the most popular method used for the solution of Linear
Programming Problems (LPP).

What happens when we need more decision variables and more problem constraints?

We use an algebraic method called the simplex method, which was developed by
George B. DANTZIG (1914-2005) in 1947 while on assignment with the U.S.
Department of the air force.
 Linear Programming Simplex method -I
Motivation of Simplex method
 Solution of a LPP, if exists, lies at one of the vertices of the
feasible region.
 All the basic solutions can be investigated one-by-one to
pick up the optimal solution.
For 10 equations with 15 variables there exists
15
C10  3003 basic feasible solutions!
Too large number to investigate one-by-one.
This can be overcome by simplex method
General procedure of simplex method

Simplex method involves following steps

1.General form of given LPP is transformed to its
canonical form.
2.Find a basic feasible solution of the LPP .
3.Move to an adjacent basic feasible solution which is
closest to the optimal solution among all other adjacent
vertices.
4.Repeat until optimum solution is achieved.
Step three involves ‘ Simplex Algorithm’
 SIMPLEX METHOD

Step-1
Write the Step 4
Step 2 Step-5
standard Are there
Are there Select the
maximization any Step-3 any positive
pivot
problem in Select elements in
negative element
canonical form, the the pivot
indicators and
introduce slack column
in the pivot perform
variables to form above the
bottom/top column dashed line? the pivot
the initial system, row?
operation
and write the
initial tableau.

STOP
STOP The linear programming problem has
The optimal solution has been found. no optimal solution

Simplex algorithm for standard maximization problems

To solve a linear programming problem in standard form, use the following steps.

1- Convert each inequality in the set of constraints to an equation by adding slack

variables.
2- Create the initial simplex tableau.
3- Select the pivot column. ( The column with the “most negative value” element
in the first/last row.)
4- Select the pivot row. (The row with the smallest non-negative result when the
last element in the row is divided by the corresponding in the pivot column.)
5-Use elementary row operations calculate new values for the pivot row so that
the pivot is 1 (Divide every number in the row by the pivot number.)
6- Use elementary row operations to make all numbers in the pivot column equal
to 0 except for the pivot number.
If all entries in the first/bottom row are zero or positive, this the final tableau.
If not, go back to step 3.
7- If you obtain a final tableau, then the linear programming problem has a
maximum solution, which is given by the entry in the lower-right corner of the
tableau.
 Simplex Algorithm
Let us consider the following LPP

Maximize Z  4 x1  x 2  2 x3
Subject to 2 x1  x 2  2 x3  6
x1  4 x 2  2 x3  0
5 x1  2 x 2  2 x3  4
x1 , x 2 , x3  0
 Simplex Algorithm…contd.
LPP is transformed to its standard form
Maximize Z  4 x1  x 2  2 x3
Subject to 2 x1  x 2  2 x3  x 4  6
x1  4 x 2  2 x3  x5  0
5 x1  2 x 2  2 x3  x 6  4
x1 , x 2 , x3 , x 4 , x5 , x6  0

Note that x4, x5, x6 are slack variables.

 Simplex Algorithm …contd.

Set of equations, including the objective function is

transformed to canonical form
 4 x1  x 2  2 x3  0 x 4  0 x5  0 x6  Z  0
2 x1  x 2  2 x3  1x 4  0 x5  0 x6  6
x1  4 x 2  2 x3  0 x 4  1x5  0 x6  0
5 x1  2 x 2  2 x3  0 x 4  0 x5  1x6  4
Basic feasible solution of above canonical form is
x4 = 6, x5= 0, x6= 4, x1= x2= x3= 0 and Z = 0
x4, x5, x6 : Basic Variables ; x1, x2, x3 : Non-basic Variables
 Simplex Algorithm …contd.
Symbolized form
Z c1 x1  c 2 x 2  c3 x3  c 4 x 4  c5 x5  c6 x6  Z  b
 x4  c 41 x1  c 42 x 2  c 43 x3  c 44 x 4  c 45 x5  c 46 x6  b4
 x5  c51 x1  c52 x 2  c53 x3  c54 x 4  c55 x5  c56 x6  b5
 x6  c61 x1  c62 x 2  c63 x3  c64 x 4  c65 x5  c66 x6  b6
The left-most column is known as basis as this is consisting of
basic variables
The coefficients in the first row (c1,…..c6) are known as cost
coefficients.
 Simplex Algorithm …contd.

This completes first step of algorithm.

 After completing each step (iteration) of algorithm,
following three points are to be examined:

1.Is there any possibility of further improvement?

2.Which non basic variable is to be entered into the basis?
3.Which basic variable is to be exited from the basis?
 Simplex Algorithm …contd.
Is there any possibility of further improvement?
If any one of the cost coefficients is negative further
improvement is possible.
Which non basic variable is to be entered?
Entering variable is decided such that the unit change of
this variable should have maximum effect on the objective
function. Thus the variable having the coefficient which is
minimum among all cost coefficients is to be entered, i.e.,
xs is to be entered if cost coefficient cs is minimum.
 Simplex Algorithm …contd.
Which basic variable is to be exited ?
After deciding the entering variable xs , xr (from the set of
basic variables) is decided to be the exiting variable if br
cr s
is minimum for all possible r, provided crs is positive. crs
is considered as pivotal element to obtain the next
canonical form.
 Simplex Algorithm …contd.
Entering variable
c1is minimum (-4), thus, x1is the entering variable for the next step of
calculation.
 Exiting variable
r may take any value from 4, 5 and 6. It is found that ,
b4 6 b5 0 b6 4 b5
  3,   0,   0.8As,
c 41 2 c51 1 c61 5 c51

is minimum, r is 5. Thus, x5 is to be exited.c51 ( = 1) is considered as

pivotal element and x5 is replaced by x1 in the basis.
Thus a new canonical form is obtained through pivotal operation.
 Simplex Algorithm …contd.
After the pivotal operation, the canonical form obtained as
follows
Z 0 x1  15 x 2  6 x3  0 x 4  4 x5  0 x6  Z  0
 x4  0 x1  9 x 2  2 x3  1x 4  2 x5  0 x6  6
 x1  1x1  4 x 2  2 x3  0 x 4  1x5  0 x6  0
 x6  0 x1  18 x 2  12 x3  0 x 4  5 x5  1x6  4

The Basic feasible solution of above canonical form is

x1 = 0, x4 = 6, x6= 4, x2= x3= x5 = 0 and Z = 0
Note that cost coefficient c2 is negative. Thus optimum solution
is not yet achieved. Further improvement is possible.
 Simplex Algorithm …contd.
Entering variable
c2is minimum (-15), thus, x2 is the entering variable for the next
step of calculation.
 Exiting variable
r may take any value from 4, 1 and 6. However, c 12is negative (-
4). Thus, r may be either 4 or 6. It is found that,b
b4 6 b6 4 6
  0.667,   0.222
c 42 9 c62 18 As,
c 62

is minimum, r is 6. Thus, x6 is to be exited.c62 ( = 18) is considered

as pivotal element and x6 is replaced by x2 in the basis.
Thus another canonical form is obtained.
 Simplex Algorithm …contd.
After the pivotal operation, the canonical form
obtained as follows
1 5 10
Z 0 x1  0 x 2  4 x3  0 x 4  x5  x6  Z 
6 6 3
1 1
 x4  0 x1  0 x 2  4 x3  1x 4  x5  x6  4
2 2
2 1 2 8
 x1  1x1  0 x 2  x3  0 x 4  x5  x6 
3 9 9 9
2 5 1 2
 x2  0 x1  1x 2  x3  0 x 4  x5  x 6 
3 18 18 9
 Simplex Algorithm …contd.
The Basic feasible solution of above canonical form is
8 2 10
x1  , x 2  , x 4  4, x3  0, x5  0, x6  0, and Z 
9 9 3
Note that cost coefficient c3 is negative. Thus optimum solution
is not yet achieved. Further improvement is possible.
 Simplex Algorithm …contd.
Entering variable
x3 is the entering variable for the next step of calculation.

 Exiting variable
x4 is the exiting variable.c43 ( = 4) is considered as pivotal
element and x4 is replaced by x3 in the basis.
Thus another canonical form is obtained.
 Simplex Algorithm …contd.
After the pivotal operation, the canonical form obtained as
follows
1 1 22
Z 0 x1  0 x 2  0 x3  1x 4  x5  x 6  Z 
3 3 3
1 1 1
 x3  0 x1  0 x 2  1x3  x 4  x5  x 6  1
4 8 8
1 1 5 14
 x1  1x1  0 x 2  0 x3  x 4  x5  x6 
6 36 36 9
1 7 1 8
 x2  0 x1  1x 2  0 x3  x 4  x5  x6 
6 36 36 9
 Simplex Algorithm …contd.
The basic solution of above canonical form is

14 8 22
x1  , x 2  , x3  1, x 4  0, x5  0, x6  0, and Z 
9 9 3
Note that all the cost coefficients are nonnegative. Thus
the optimum solution is achieved.
Optimum solution is

22 14 8
Z , x1  , x 2  , x3  1
3 9 9
 Construction of Simplex Table:
General notes

Calculations shown till now can be presented in a tabular

form, known as simplex table.
After preparing the canonical form of the given LPP, first
simplex table is constructed.
After completing each simplex table (iteration), few steps
(somewhat mechanical and easy to remember) are
followed.
Logically, these steps are exactly similar to the procedure
described earlier.
 Construction of Simplex Table:
Basic steps

Check for optimum solution:

1.Investigate whether all the elements (coefficients of the

variables headed by that column) in the first row (i.e., Z
row) are nonnegative or not. If all such coefficients are
nonnegative, optimum solution is obtained and no need of
further iterations.
2. If any element in this row is negative follow next steps to
obtain the simplex table for next iteration.
 Construction of Simplex Table:
Basic steps

Operations to obtain next simplex table:

2.Identify the entering variable (described earlier) and mark
that column as Pivotal Column.
3.Identify the exiting variable from the basis as described
earlier and mark that row as Pivotal Row.
4.Mark the coefficient at the intersection of Pivotal Row
and Pivotal Column as Pivotal Element.
 Construction of Simplex Table:
Basic steps
Operations to obtained simplex tableau…contd.:
5.In the basis, replace the exiting variable by entering
variable.
6.Divide all the elements in the pivotal row by pivotal
element.
7.For any other row, identify the elementary operation such
that the coefficient in the pivotal column, in that row,
becomes zero. Apply the same operation for all other
elements in that row and change the coefficients.
Follow similar procedure for all other rows.
 Construction of Simplex Table: example
Consider the same problem discussed before.
Canonical form of this LPP is

 4 x1  x 2  2 x3  0 x 4  0 x5  0 x6  Z  0
2 x1  x 2  2 x3  1x 4  0 x5  0 x6  6
x1  4 x 2  2 x3  0 x 4  1x5  0 x 6  0
5 x1  2 x 2  2 x3  0 x 4  0 x5  1x6  4
Least negative Cost Coefficient
In first row

Least Ratio

Elementary operations
1. X4-2X5
2. X6-5X5
3. Z+4X4
 Final results
Simplex Table
All the elements in the first row (i.e., Z row), at iteration
4, are nonnegative. Thus, optimum solution is achieved.
Optimum solution is

22 14 8
Z , x1  , x 2  , x3  1
3 9 9
 Construction of Simplex Table:
A note
It can be noted that at any iteration the following two
points must be satisfied:
1.All the basic variables (other than Z) have a coefficient
of zero in the Z row.
2.Coefficients of basic variables in other rows constitute a
unit matrix.

Violation of any of these points at any iteration indicates a

wrong calculation. However, reverse is not true.
THANK YOU