Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Giá bóng và phân tích độ nhạy trong lập trình tuyến tính dưới tình trạng suy biến
Tóm tắt
Trong các ứng dụng lập trình tuyến tính, ý nghĩa kinh tế của giá bóng là rất quan trọng. Trong trường hợp suy biến nguyên thủy xảy ra trong nghiệm tối ưu, các giá trị của các biến thực đối ngẫu thường không giống nhau với các giá bóng tương ứng, hay nói cách khác, những giá trị này không có ý nghĩa như thường lệ khi so sánh với các nghiệm tối ưu LP mà không có tình trạng suy biến nguyên thủy. Một số đề xuất về cách diễn giải các giá trị này hoặc cách tìm giá bóng "thực sự" đã được đưa ra và các thuật ngữ như "giá bóng nhiều mặt" hoặc "giá bóng hai mặt" đã được đặt ra. Ngoài ra, khi thực hiện phân tích độ nhạy trong trường hợp suy biến nguyên thủy xảy ra, các khoảng giới hạn quan trọng của phần bên phải hoặc của hệ số hàm mục tiêu không thể được xác định theo cách thông thường. Trong bài báo này, một khảo sát về các vấn đề này được trình bày.
Từ khóa
#lập trình tuyến tính #giá bóng #phân tích độ nhạy #suy biến nguyên thủyTài liệu tham khảo
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