CLICK HERE TO DOWNLOAD PPT ON Four Special Cases in Simplex
Four Special Cases in Simplex Presentation Transcript
1.Four Special cases in Simplex
2.Simplex Algorithm – Special cases
There are four special cases arise in the use of the simplex method.
Degeneracy
Alternative optima
Unbounded solution
Nonexisting ( infeasible ) solution
There are four special cases arise in the use of the simplex method.
Degeneracy
Alternative optima
Unbounded solution
Nonexisting ( infeasible ) solution
3.Simplex Algorithm – Special cases
Degeneracy ( no improve in objective)
It typically occurs in a simplex iteration when in the minimum ratio test more than one basic variable determine 0, hence two or more variables go to 0, whereas only one of them will be leaving the basis.
Model has at least one Redundant Constraint.
This is in itself not a problem, but making simplex iterations from a degenerate solution may give rise to cycling, meaning that after a certain number of iterations without improvement in objective value the method may turn back to the point where it started.
Degeneracy ( no improve in objective)
It typically occurs in a simplex iteration when in the minimum ratio test more than one basic variable determine 0, hence two or more variables go to 0, whereas only one of them will be leaving the basis.
Model has at least one Redundant Constraint.
This is in itself not a problem, but making simplex iterations from a degenerate solution may give rise to cycling, meaning that after a certain number of iterations without improvement in objective value the method may turn back to the point where it started.
4.Degenearcy – Special cases (cont.)
5.Simplex Algorithm – Special cases
6.It is possible to have no improve and no termination for computation.
7.Temporarily Degenerate
8.Alternative optima
If the z-row value for one or more nonbasic variables is 0 in the optimal tubule, alternate optimal solution exists.
When the objective function is parallel to a binding constraint objective function will assume same optimal value.
We have infinite number of such points
If the z-row value for one or more nonbasic variables is 0 in the optimal tubule, alternate optimal solution exists.
When the objective function is parallel to a binding constraint objective function will assume same optimal value.
We have infinite number of such points
9.Any point on BC represents an alternate optimum with z=10
In practice alternate optima are useful as they allow us to choose from many solutions experiencing deterioration in the objective value.
In a product-mix problem C(3,1) would be more appealing.
In practice alternate optima are useful as they allow us to choose from many solutions experiencing deterioration in the objective value.
In a product-mix problem C(3,1) would be more appealing.
10.3.Unbounded solution:
It occurs when nonbasic variables are zero or negative in all constraints coefficient (max) and variable coefficient in objective is negative
11.We can conclude that after 3rd iteration if we increase the value of x2 ,value of z will increase correspondingly up to infinite. Hence we can conclude that solution is unbounded.
It occurs when nonbasic variables are zero or negative in all constraints coefficient (max) and variable coefficient in objective is negative
11.We can conclude that after 3rd iteration if we increase the value of x2 ,value of z will increase correspondingly up to infinite. Hence we can conclude that solution is unbounded.
12.Infeasible Solution:
This situation can never occur if all the constraints are of the type “=” with non-negative RHS because slack provide feasible solution.
High penalty is provided with R in objective function to reduce them to ‘0’ at optimum.
Artificial variable R coefficient at end ? 0
if solution is infeasible.
This situation can never occur if all the constraints are of the type “=” with non-negative RHS because slack provide feasible solution.
High penalty is provided with R in objective function to reduce them to ‘0’ at optimum.
Artificial variable R coefficient at end ? 0
if solution is infeasible.
13.REFERENCES
Operations Research an introduction, seventh edition ,Hamdy A. Taha
TORA
Operations Research an introduction, seventh edition ,Hamdy A. Taha
TORA
Posts
0 comments