How to move from one BFS to another
adjacent better BFS??
1
How to move from one BFS to another adjacent better
BFS??
Make one of the basic variable non-basic and
conversely.
(As adjacent corner points differ in only one basic (non-
basic) variable)
Which basic variable should be dropped from the
basis (i.e. to be made non-basic)??
Which non-basic variable should enter to the basis
(i.e. to be made basic)??
How to ensure the feasibility of new basic solution??
How to ensure that the new BFS is better??
2
Simplex table
Initial Simplex Table:
1 2 0 0 0
CB Var in B Value (XB) Yx1 Yx2 Ys1 Ys2 Ys3
0 s1 4 0 1 1 0 0
0 8 1 1 0 1 0
s2
0 10 2 -1 0 0 1
s3
Z=0 -1 -2 0 0 0
(zj – cj) 3
1 2 0 0 0
CB Var in B Value Yx1 Yx2 Ys1 Ys2 Ys3
0 s1 4 0 1 1 0 0
0 8 1 1 0 1 0
s2
0 10 2 -1 0 0 1
s3
Z=0 -1 -2 0 0 0
2 x2 4 0 1 1 0 0
0 4 1 0 -1 1 0
s2
0 0 0 1
14 2 1
s3
8 -1 0 2 0 0
2 x2 4 0 1 1 0 0
1 4 1 0 -1 1 0
x1
0 0 0 3 -2 1
6
s3
12 0 0 1 1 0
4
Maximize Z = 3x1 + 2x2
Subject to: 2x1 + x2 6
x1 + 2x2 6
x1 , x 2 0
3 2 0 0
CB Var in B Val Yx1 Yx2 Ys1 Ys2
0 s1 6 2 1 1 0
0 s2 6 1 2 0 1
Z=0 -3 -2 0 0
3 x1 3 1 1/2 1/2 0
0 s2 3 0 3/2 -1/2 1
9 0 -1/2 3/2 0
3 x1 2 1 0 2/3 -1/3
2 x2 2 0 1 -1/3 2/3
10 0 0 4/3 1/3
5
Summary of Simplex Algorithm
Step (0):
Find an initial basic feasible solution, (How?) and set up the
simplex tableau accordingly.
Step (1):
Pick the variable with most negative (positive) relative cost
coefficient as the incoming variable. If all variables have non-
negative (non-positive) relative cost coefficients, the current
solution is optimal, STOP. Otherwise, go to step 2.
Step (2):
Perform the min ratio test to determine the outgoing variable.
Step (3):
Perform the necessary row operations to obtain the new
simplex tableau corresponding to new basic feasible solution.
Go to step 1.
6
What happens whenever there is a column in the
simplex tableau with all non-positive entries and the
corresponding relative cost coefficient is also
negative??
Consider a simplex tableau having a non-basic
variable with:
i. relative cost coefficient is negative (eligible to enter)
(maximization case)
ii. column does not contain any strictly positive value (only
negatives and/or zeros)
What happens in such a case??
what would happen when such a variable is selected to
enter??
7
2 1 0 0
CB B XB Yx1 Yx2 Ys1 Ys2
0 s1 1 -1 1 1 0
0 s2 2 1 -2 0 1
0 -2 -1 0 0
0 s1 3 0 -1 1 1
2 x1 2 1 -2 0 1
4 0 -5 0 2
We have an incoming variable, but no variable to depart
Whenever there is a column in the simplex tableau with all the entries
less than or equal to 0 then if the corresponding relative cost coefficient
is also negative, LP is Unbounded.
8
What happens when in the optimal tableau, one or
more non-basic variables have relative cost
coefficient 0??
Suppose a non-basic variable with above said property is
chosen to enter the basis.
What would be the new objective value?
Same as previous (Why?)
But it is a new BFS.
Consider:
9
2 1 0 0 0
CB B XB Yx1 Yx2 Ys1 Ys2 Ys3
0 s1 2 -1 1 1 0 0
0 s2 12 4 2 0 1 0
0 s3 5 2 0 0 0 1
0 -2 -1 0 0 0
0 s1 9/2 0 1 1 0 1/2
0 s2 2 0 2 0 1 -2
2 x1 5/2 1 0 0 0 1/2
5 0 -1 0 0 1
0 s1 7/2 0 0 1 -1/2 3/2
1 x2 1 0 1 0 1/2 -1
2 x1 5/2 1 0 0 0 1/2
6 0 0 0 1/2 0
Whenever one or more non-basic variables have relative cost coefficient 0 in the
optimal tableau, Alternate Optima exist !!
10
What happens when in a simplex table min
ratio is not attained uniquely ??
• Whenever there is a tie in outgoing variable, any one
can be chosen as the outgoing variable.
– But the next BFS will be degenerate BFS.
• Example:
Maximize Z = 2x1 + x2
Subject to: 4x1 + 3x2 12
4x1 + x2 8
4x1 - x2 8
x1 , x 2 0
11
2 1 0 0 0
CB Var in B Value Yx1 Yx2 Ys1 Ys2 Ys3
0 s1 12 4 3 1 0 0
0 8 4 1 0 1 0
s2
0 8 4 -1 0 0 1
s3
Z=0 -2 -1 0 0 0
0 s1 4 0 2 1 -1 0
2 2 1 1/4 0 1/4 0
x1
0 -2 -1 1
0 0 0
Deg BFS s3
4 0 -1/2 0 0 0
1 x2 2 0 1 1/2 -1/2 0
2 3/2 1 0 -1/8 3/8 0
x1
0 0 0 1 -2 1
4
s3
5 0 0 1/4 1/4 0
12