Summary
In linear programming applications the economic meaning of shadow prices is important. In the case primal degeneracy occurs in the optimal solution, the values of the dual real variables are not, in general, identical with the corresponding shadow prices, or, in other words, these values have not the usual meaning in comparison with LP optimal solutions without primal degeneracy. Several proposals on how to interpret such values or how to find the “true” shadow prices have been made and terms like “many-sided-” or “two-sided-shadowprices” have been coined. Also, when performing sensitivity analysis in the case primal degeneracy occurs, the so called critical ranges of the right hand side or of the objective function coefficients cannot be determined in the usual way. In this paper, a state-of-the-art-survey on these questions is given.
Zusammenfassung
Bei den Anwendungen der linearen Optimierung ist der ökonomische Inhalt der Schattenpreise von Bedeutung. Falls eine optimale Lösung primal entartet ist, sind die Werte der dualen Strukturvariablen im allgemeinen nicht identisch mit den entsprechenden Schattenpreisen, oder — anders ausgedrückt — diese Werte kann man nicht so interpretieren wie bei nichtentarteten optimalen Lösungen eines linearen Optimierungsproblems. Es gibt in der Literatur verschiedene Vorschläge, wie diese Werte interpretiert werden sollen oder wie der „richtige“ Schattenpreis bestimmt werden soll. Dabei werden Bezeichnungen wie „vielseitige“ bzw. „zweiseitige Schattenpreise“ eingeführt. Auch bei der Durchführung einer Sensitivitätsanalyse können im Falle einer primalen Entartung die kritischen Bereiche für Parameter in der rechten Seite oder in den Zielkoeffizienten nicht auf die übliche Weise bestimmt werden. In diesem Artikel ist eine Übersicht des gegenwärtigen Standes zu den obigen Problemen gegeben.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Akgül M (1984) A note on shadow prices in linear programming. J Oper Res 35:425–431
Aucamp DC, Steinberg DI (1982) The computation of shadow prices in linear programming. J Oper Res Soc 33: 557–565
Aucamp DC, Steinberg DI (1978) On the nonequivalence of shadow prices and dual variables. Presented at The TIMS/ ORSA meeting, Los Angeles, Nov. 1978; Techn. Rep. WUCS-79-11, Washington University Department of Computer Sciences, St. Luis Missouri
Bank B, Guddat J, Klatte D, Kummer B, Tammer K (1982) Non-linear parametric optimization. Akademie Verlag, Berlin
Ben-Israel A, Flåm SD (1985) Canonical Bases and Sensitivity Analysis in linear programming. Research Report, Department of Mathematical Science, University of Delaware, Newark, and Department of Science and Technology, Chr. Michelsen Institut, Fantoft, Norway
Bland RG (1977) New finite pivoting rules for the simplex method. Math OR 2:103–107
Chang Y-Y, Cottle RW (1978) Least index resolution of degeneracy in quadratic programming. Techn. Rep. 78-3, Stanford University Department of OR, California
Charnes A (1952) Optimality and degeneracy in linear programming. Econometrica 20:150–170
Cook TG, Russel RH (1977) Introduction to management science. Prentice Hall, Englewood Cliffs, NJ
Dantzig GB (1963) Linear programming and extensions. Princeton University Press, Princeton
Dantzig GB, Orden A, Wolfe P (1955) Generalized simplex method for minimizing a linear form under linear inequality restraints. Pac J Math 5:183–195
Eilon A, Flavell R (1974) Note on “many-sided shadow prices”. OMEGA 2:821–823
Evans JR, Baker NR (1982) Degeneracy and the (mis) interpretation of sensitivity analysis in linear programming. Decision Sci 13:348–154
Gal T (1979) Postoptimal analyses, parametric programming and related topics. McGraw Hill, New York Berlin
Gal T (1985) On the structure of the set bases of a degenerate point. JOTA 45:577–589
Gass SI (1969) Linear programming — Methods and applications, 3rd edn. McGraw Hill, New York
Hadley G (1960) Linear algebra. Addison-Wesley, Reading, Mass
Karwan MH, Lotfi V, Teigen J, Zionts S (1983) Redundancy in mathematical programming. Lecture Notes in Economics and Mathematical Systems, vol 206. Springer, Berlin Heidelberg New York
Knolmayer G (1976) How many-sided are shadow prices at degenerate primal optima? OMEGA 4:493–494
Knolmayer G (1980) Programmierungsmodelle für die Produktionsprogrammplanung. Birkhäuser, Basel Boston Stuttgart
Knolmayer G (1984) The effect of degeneracy on cost-coefficient ranges and an algorithm to resolve interpretation problems. Decision Sci 15:14–21
Kruse H-J (1986) Degeneracy graphs and the neighbourhood problem. Lecture Notes in Economics and Mathematical Systems, vol 3. Springer, Berlin Heidelberg New York
Menger C (1871) Grundsätze der Volkswirtschaftslehre. Wien
Müller-Merbach H (1973) Operations research, 3rd edn. Franz Vahlen, München
Panne C van de (1975) Methods for linear and quadratic programming. North Holland, Amsterdam
Saaty TL (1959) Coefficient perturbation of a constrained extremum. Oper Res 7:294–302
Samuelson PA (1950) Frank Knight's theorem in linear programming. D-782, The RAND Corporation
Shapiro JF (1979) Mathematical programming: Structures and algorithms, chap 2.4. J. Wiley, New York
Stigler GJ (1941) Production and distribution theories, chap VI–VII. New York
Strum JE (1969) Note on two-sided shadow prices. J Account Res 7:160–162
Uzawa H (1958) A note on the Menger-Wieser-Theory of imputation. Nationalökonomie 18:318–334
Wagner H (1969) Principles of operations research. Prentice Hall, Englewood Cliffs, NJ
Wieser F von (1889) Der natürliche Wert
Williams AC (1963) Marginal values in linear programming. J Soc Indust Appl Math 11:82–94
Wolfe P (1963) A technique for resolving degeneracy in linear programming. J Soc Indust Appl Math 11:205–211
Wright FK (1968) Measuring asset services: a linear programming approach. J Account Res 6:222–236
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Gal, T. Shadow prices and sensitivity analysis in linear programming under degeneracy. OR Spektrum 8, 59–71 (1986). https://doi.org/10.1007/BF01719736
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF01719736