Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Giới thiệu về lập trình tuyến tính: từ Fourier đến Karmarkar
Tóm tắt
Câu chuyện về lập trình tuyến tính là một bi kịch lịch sử lớn lao. Ý tưởng nguyên thủy về việc kiểm tra xem một đa diện có phải là không rỗng bằng cách sử dụng loại bỏ biến để chiếu xuống một chiều mỗi lần cho đến khi một luật đồng nhất xuất hiện bắt nguồn từ một bài báo của Fourier vào năm 1823. Ý tưởng này được tái phát minh vào những năm 1930 bởi Motzkin. Sự quan tâm thực sự đối với lập trình tuyến tính xảy ra trong Thế chiến II khi các nhà toán học suy nghĩ về những cách tốt nhất để sử dụng tài nguyên trong khi chúng bị hạn chế. Bài toán tối ưu hóa một hàm tuyến tính dựa trên một tập hợp các bất đẳng thức tuyến tính trở thành trung tâm của nỗ lực. Phương pháp Simplex của Dantzig được công bố và Tập đoàn Rand trở thành nơi phát triển mạnh mẽ của toán học tính toán. Phạm vi ứng dụng của cách tiếp cận mô hình này ngày càng mở rộng và các công cụ mạnh mẽ của phân tích số và đại số tuyến tính số trở thành động lực chính cho sự phát triển của máy tính. Vào những năm 1970, các cấu trúc của khoa học máy tính lý thuyết chỉ ra rằng lập trình tuyến tính thực sự có thể định nghĩa ranh giới của những bài toán có thể giải được một cách hiệu quả trên các trường hợp lớn. Điều này đặt ra một loạt câu hỏi và lời đáp: Phương pháp Simplex có phải là phương pháp chạy trong thời gian đa thức hay không, và nếu không, liệu chúng ta có thể xây dựng các phương pháp thời gian đa thức mới mẻ hay không, v.v. Và đó là cách mà Phương pháp Ellipsoid từ Liên Xô và Phương pháp Điểm Nội từ Bell Labs xuất hiện trong câu chuyện này như những anh hùng Khachiyan và Karmarkar. Chúng tôi đã gọi bài báo này là một hướng dẫn về lập trình tuyến tính vì nó chỉ cung cấp cho người đọc một câu chuyện nhanh chóng về bi kịch lịch sử lớn lao. Hy vọng nó sẽ thúc đẩy người đọc trẻ tìm hiểu sâu hơn và thêm một chương nữa.
Từ khóa
#lập trình tuyến tính #phương pháp Simplex #tối ưu hóa #bất đẳng thức tuyến tính #toán học tính toán #Ellipsoid Method #Interior Point MethodTài liệu tham khảo
Adler, I., & Cosares, S. (1991). A strongly polynomial algorithm for a special class of linear programs. Operations Research, 39, 955–960.
Bixby, R. E. (1994). Progress in linear programming. ORSA Journal on Computing, 6(1), 15–22.
Borgwardt, K. H. (1987). The simplex method: A probabilistic analysis. Berlin: Springer.
Cerkinov, R. N. (1961). The solution of linear programming problems by elimination of unknowns. Doklady Akademii Nauk, 139, 1314–1317.
Chandru, V., & Kochar, B. S. (1985). A class of algorithms for linear programming, Research Memorandum No. 85-14, Purdue University.
Chandru, V., & Kochar, B. S. (1986). Exploiting special structures using a variant of Karmarkar’s algorithm, Research Memorandum No. 86-10, School of Industrial Engineering, Purdue University.
Chandru, V. (1993). Variable elimination in linear constraints. The Computer Journal, 36(5), 463–472.
Charnes, A. (1952). Optimality and degeneracy in linear programming. Econometrica, 20, 160–170.
Cohen, E., & Megiddo, N. (1991). Improved algorithms for linear inequalities with two variables per inequality. In Proceedings of the twenty third symposium on theory of computing, New Orleans (pp. 145–155).
Cohen, E., & Megiddo, N. (1993). New algorithms for generalized network flows, Revised. In D. Dolev, Z. Galil, & M. Rodeh (Eds.), Proceedings of the 1st Israeli symposium on the theory of computing and systems (pp. 103–114).
Cohen, E., & Megiddo, N. (1994). Improved algorithms for linear inequalities with two variables per inequality, Extended Abstract. SIAM Journal of Computing, 23, 1313–1347.
Cottle, R. W., & Veinott, A. F, Jr. (1972). Polyhedral sets having a least element. Mathematical Programming, 3, 238–249.
Dantzig, G. B. (1951). Maximization of a linear function of variables subject to linear inequalities. In C. Koopmans (Ed.), Activity analysis of production and allocation (pp. 339–347). New York: Wiley.
Dantzig, G. B. (1963). Linear programming and extensions. Princeton: Princeton University Press.
Dantzig, G. B., & Eaves, B. C. (1973). Fourier–Motzkin elimination and its dual. Journal of Combinatorial Theory (A), 14, 288–297.
Dantzig, G. B., Orden, A., & Wolfe, P. (1955). The generalized simplex method for minimizing a linear form under linear inequality restraints. Pacific Journal of Mathematics, 5, 183–195.
Fourier, L. B. J. (1826). Reported in: Analyse des travaux de l’Academic Royale des Sciences. pendant l’annee (1823), Partie mathematique, Histoire de l’Academie Royale des Sciences de l’Institut de France (Vol. 6, pp. xxix–xli).
Fourier, L. B. J. (1827). Reported in: Analyse des travaux de l’Academic Royale des Sciences. pendant l’annee (1824), Partie mathematique, Histoire de l’Academie Royale des Sciences de l’Institut de France (Vol. 7, pp. xlviii–lv) (Partial English Translation in: D.A. Kohler, Translation of a report by Fourier on his work on linear inequalities. Opsearch, Vol. 10, pp. 38–42, 1973)
Grötschel, M., Lovász, L., & Schrijver, A. (1982). The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1, 169–197.
Grötschel, M., Lovász, L., & Schrijver, A. (1988). Geometric algorithms and combinatorial optimization. Berlin: Springer.
Haĉijan, L. G. (1979). A polynomial algorithm in linear programming. Soviet Mathematics Doklady, 20, 191–194.
Haimovich, M. (1983). The simplex method is very good! On the expected number of pivot steps and related properties of random linear programs. Unpublished Manuscript.
Hochbaum, D. S., & Naor, J. (1994). Simple and Fast Algorithms for Linear and Integer Programs with two variables per inequality. SIAM Journal on Computing, 23(6), 1179–1192.
Karmarkar, N. K. (1984). A new polynomial-time algorithm for linear programming. Combinatorica, 4, 373–395.
Karp, R. M., & Papadimitriou, C. H. (1982). On linear characterizations of combinatorial optimization problems. SIAM Journal on Computing, 11, 620–632.
Klee, V., & Minty, G. J. (1972). How good is the simplex algorithm? In O. Shisha (Ed.), Inequalities III. Cambridge: Academic Press.
Lassez, J.-L. (1991). From LP to LP: Programming with constraints. In Proceedings of theoretical aspects of computer software, Sendai.
Lassez, J.-L., & Maher, M. J. (1988). On Fourier’s algorithm for linear arithmetic constraints, IBM Research Report, T Watson Research Center.
Megiddo, N. (1983). Towards a genuinely polynomial algorithm for linear programming. SIAM Journal on Computing, 12(2), 347–353.
Megiddo, N. (1991). On finding primal- and dual-optimal bases. ORSA Journal on Computing, 3, 63–65.
Motzkin, T. S. (1936). Beitrage zur theorie der linearen Ungleichungen. Doctoral thesis, University of Base.
Padberg, M. W., & Rao, M. R. (1981). The Russian method for linear inequalities, Part III, Bounded integer programming. New York: New York University. (preprint).
Saigal, R. (1995). Linear programming: A modern integrated analysis. Alphen aan den Rijn: Kluwer Press.
Schrijver, A. (1986). Theory of linear and integer programming. Hoboken: Wiley.
Shor, N. Z. (1970). Convergence rate of the gradient descent method with dilation of the space. Cybernetics, 6, 102–108.
Stone, Richard E., & Tovey, Craig A. (1991). The simplex and projective scaling algorithms as iteratively reweighted least squares methods. SIAM Review, 33(2), 220–237.
Todd, M. J. (1986). Exploiting special structure in Karmarkar’s algorithm for linear programming. Technical Report 707, School of Operations Research and Industrial Engineering, Cornell University.
Todd, M. J. (1994). Theory and practice for interior-point methods. ORSA Journal on Computing, 6(1), 28–31.
Vaidya, P. M. (1989). Speeding-up linear programming using fast matrix multiplication. In Proceedings of the 30th IEEE annual symposium on foundations of computer science (pp. 332–337).
Vanderbei, R. J. (2015). Linear programming: Foundations and extensions (4th ed.). Berlin: Springer.
Williams, H. P. (1986). Fourier’s method of linear programming and its dual. The America Mathematical Monthly, 93, 681–695.
Wolfe, P. (1963). A technique for resolving degeneracy in linear programming. SIAM Journal on Applied Mathematics, 11(205), 211.
Wright, S. J. (1997). Primal-dual interior-point methods. Cambridge: SIAM Press.
Ziegler, M. (1995). Convex polytopes. Berlin: Springer.