The basic simplex solution of typical maximization and minimization problems has been shown in this module. However, there are several special types of atypical linear programming problems. Although these special cases do not occur frequently, they will be described within the simplex framework so that you can recognize them when they arise. For irregular problems the general simplex procedure does not always apply. These special types include problems with more than one optimal solution, infeasible problems, problems with unbounded solutions, problems with ties for the pivot column or ties for the pivot row, and problems with constraints with negative quantity values. ## Multiple Optimal SolutionsConsider the Beaver Creek Pottery Company example with the objective function changed as follows .
The graph of this model is shown in Figure A-5. The slight change in the objective function makes it now parallel to the constraint line, 4 x ## Figure A-5. Graph of the Beaver Creek Pottery Company example with multiple optimal solutions
Alternate optimal solutions have the same Z value but different variable values. The optimal simplex tableau for this problem is shown in Table A-25. This corresponds to point C in Figure A-5. ## Table A-25. The Optimal Simplex Tableau## (This item is displayed on page A-25 in the print version)
For a multiple optimal solution the c The fact that this problem contains multiple optimal solutions can be determined from the c To determine the alternate endpoint solution, let x ## Table A-26. The Alternative Optimal Tableau
An alternate optimal solution is determined by selecting the nonbasic variable with c ## An Infeasible ProblemAnother linear programming irregularity is the case where a problem has no feasible solution area; thus, there is no basic feasible solution to the problem. An infeasible problem does not have a feasible solution space. An example of an infeasible problem is formulated next and depicted graphically in Figure A-6.
## Figure A-6. Graph of an infeasible problem## (This item is displayed on page A-26 in the print version)
The three constraints do not overlap to form a feasible solution area. Because no point satisfies all three constraints simultaneously , there is no solution to the problem. The final simplex tableau for this problem is shown in Table A-27. ## Table A-27. The Final Simplex Tableau for an Infeasible Problem## (This item is displayed on page A-26 in the print version)
An infeasible problem has an artificial variable in the final simplex tableau. The tableau in Table A-27 has all zero or negative values in the c ## An Unbounded ProblemIn some problems the feasible solution area formed by the model constraints is not closed. In these cases it is possible for the objective function to increase indefinitely without ever reaching a maximum value because it never reaches the boundary of the feasible solution area. In an unbounded problem the objective function can increase indefinitely because the solution space is not closed. An example of this type of problem is formulated next and shown graphically in Figure A-7.
## Figure A-7. An unbounded problem
In Figure A-7 the objective function is shown to increase without bound; thus, a solution is never reached. A pivot row cannot be selected for an unbounded problem. The second tableau for this problem is shown in Table A-28. In this simplex tableau, s ## Table A-28. The Second Simplex TableauUnlimited profits are not possible in the real world; an unbounded solution, like an infeasible solution, typically reflects an error in defining the problem or in formulating the model. ## Tie for the Pivot Column Sometimes when selecting the pivot column, you may notice that the greatest positive c A tie for the pivot column is broken arbitrarily. ## Tie for the Pivot RowDegeneracyIt is also possible to have a tie for the pivot row (i.e., two rows may have identical lowest nonnegative values). Like a tie for a pivot column, a tie for a pivot row should be broken arbitrarily. However, after the tie is broken, the basic variable that was the other choice for the leaving basic variable will have a quantity value of zero in the next tableau. This condition is commonly referred to as degeneracy because theoretically it is possible for subsequent simplex tableau solutions to degenerate so that the objective function value never improves and optimality never results. This occurs infrequently, however. A tie for the pivot row is broken arbitrarily and can lead to In general, tableaus with ties for the pivot row should be treated normally. If the simplex steps are carried out as usual, the solution will evolve normally. The following is an example of a problem containing a tie for the pivot row.
For the sake of brevity we will skip the initial simplex tableau for this problem and go directly to the second simplex tableau in Table A-29, which shows a tie for the pivot row between the s ## Table A-29. The Second Simplex Tableau with a Tie for the Pivot Row
The s ## Table A-30. The Third Simplex Tableau with Degeneracy
Note that in Table A-30 a quantity value of zero now appears in the s ## Table A-31. The Optimal Simplex Tableau for a Degenerate Problem
Notice that the optimal solution did not change from the third to the optimal simplex tableau. The graphical analysis of this problem shown in Figure A-8 reveals the reason for this. ## Figure A-8. Graph of a degenerate solution
Notice that in the third tableau (Table A-30) the simplex process went to point B , where all three constraint lines intersect. This is, in fact, what caused the tie for the pivot row and the degeneracy. Subsequently, the simplex process stayed at point B in the optimal tableau (Table A-31). The two tableaus represent two different basic feasible solutions corresponding to two different sets of model constraint equations. Degeneracy occurs in a simplex problem when a problem continually loops back to the same solution or tableau. ## Negative Quantity ValuesOccasionally a model constraint is formulated with a negative quantity value on the right side of the inequality signfor example, 6 x Standard form for simplex solution requires positive right-hand-side values. This is an improper condition for the simplex method, because for the method to work, all quantity values must be positive or zero. This difficulty can be alleviated by multiplying the inequality by 1, which also changes the direction of the inequality.
A negative right-hand-side value is changed to a positive by multiplying the constraint by -1, which changes the inequality sign. Now the model constraint is in proper form to be transformed into an equation and solved by the simplex method. ## Summary of Simplex Irregularities Multiple optimal solutions are identified by c An infeasible problem is identified in the simplex procedure when an optimal solution is achieved (i.e., when all c An unbounded problem is identified in the simplex procedure when it is not possible to select a pivot rowthat is, when the values obtained by dividing the quantity values by the corresponding pivot column values are negative or undefined. |

Introduction to Management Science (10th Edition)

ISBN: 0136064361

EAN: 2147483647

EAN: 2147483647

Year: 2006

Pages: 358

Pages: 358

Authors: Bernard W. Taylor

Similar book on Amazon

flylib.com © 2008-2017.

If you may any questions please contact us: flylib@qtcs.net

If you may any questions please contact us: flylib@qtcs.net