Các vấn đề tương đương bổ sung tuyến tính và lập trình mục tiêu đa dạng

Michael M. Kostreva1, Malgorzata M. Wiecek1
1Department of Mathematical Sciences, Clemson University, Clemson, USA

Tóm tắt

Một sự tương đương được chứng minh giữa việc giải quyết một vấn đề tương đương bổ sung tuyến tính với dữ liệu tổng quát và việc tìm kiếm một tập con nhất định của các điểm hiệu quả trong một bài toán lập trình mục tiêu nhiều mục tiêu. Một phương pháp mới dựa trên lập trình mục tiêu nhiều mục tiêu để giải quyết các vấn đề tương đương bổ sung tuyến tính được trình bày. Các kết quả về sự tồn tại, tính duy nhất và độ phức tạp tính toán cũng được đưa vào.

Từ khóa

#vấn đề tương đương bổ sung tuyến tính #lập trình mục tiêu đa dạng #tồn tại #tính duy nhất #độ phức tạp tính toán

Tài liệu tham khảo

H.P. Benson, “Existence of efficient solutions for vector maximization problems,”Journal of Optimization Theory and Applications 26 (1978) 569–580. V. Chankong and Y.Y. Haimes,Multiobjective Decision Making—Theory and Methodology (North-Holland, New York, 1983). A. Charnes and W.W. Cooper, “Goal programming and multiple objective optimization—part 1,”European Journal of Operational Research 1 (1977) 39–54. S.J. Chung, “NP-completeness of the linear complementarity problem,”Journal of Optimization Theory and Applications 60 (1989) 393–399. R.W. Cottle and J.S. Pang, “On solving linear complementarity problems as linear programs,”Mathematical Programming Studies 7 (1978) 88–107. B.C. Eaves, “On quadratic programming,”Management Science 17 (1971a) 698–711. B.C. Eaves, “The linear complementarity problem,”Management Science 17 (1971b) 612–634. J.G. Ecker and I.A. Kouada, “Finding efficient points for linear multiple objective programs,”Mathematical Programming 8 (1975) 375–377. T. Gal, “On efficient sets in vector maximum problems—a brief survey,”European Journal of Operational Research 24 (1986) 253–264. C.B. Garcia, “Some classes of matrices in linear complementarity theory,”Mathematical Programming 5 (1973) 299–310. A.M. Geoffrion, “Proper efficiency and the theory of vector maximization,”Journal of Mathematical Analysis and Applications 22 (1968) 618–630. C.-L. Hwang and A.S.M. Masud,Multiple Objective Decision Making—Methods and Applications (Springer, Berlin, 1979). J.P. Ignizio,Goal Programming and Extensions (Lexington Books, Lexington, MA, 1976). M.M. Kostreva, “Block pivot methods for solving the complementarity problem,”Linear Algebra and its Applications 21 (1978) 207–215. M.M. Kostreva, “Nonconvexity in noncooperative game theory,”International Journal of Game Theory 18 (1989) 247–259. M.M. Kostreva, T.J. Ordoyne and M. Wiecek, “Multiple objective programming with polynomial objectives and constraints,”European Journal of Operational Research 57 (1992) 381–394. C.E. Lemke, “Bimatrix equilibrium points and mathematical programming,”Management Science 11 (1965) 681–689. D.G. Luenberger,Linear and Nonlinear Programming (Addison-Wesley, Reading, MA, 1984). O.L. Mangasarian, “Linear complementarity problems solvable by a single linear program,”Mathematical Programming 10 (1976) 263–270. L. Martein, “Lagrange multipliers and generalized differentiable functions in vector extremum problems,”Journal of Optimization Theory and Applications 63 (1989) 281–297. E.Q.V. Martins, “On a particular quadratic network problem,”European Journal of Operational Research 29 (1987) 317–327. K.G. Murty,Linear Complementarity, Linear and Nonlinear Programming (Heldermann Verlag, Berlin, 1988). P.M. Pardalos and J.B. Rosen, “Global optimization approach to the linear complementarity problem,”SIAM Journal of Scientific and Statistical Computing 9 (1988) 341–353. P.M. Pardalos, “Parallel search algorithms in global optimization,”Applied Mathematics and Computation 29 (1989) 219–229. R. Rhode and R. Weber, “The range of the efficient frontier in multiple objective linear programming,”Mathematical Programming 28 (1984) 84–95. D. Solow and P. Sengupta, “A finite descent theory for linear programming, piecewise linear minimization and the linear complementarity problem,”Naval Research Logistics Quarterly 32 (1985) 417–431. F. Szidarovszky, M.E. Gershon and L. Duckstein,Techniques for Multiobjective Decision Making in Systems Management (Elsevier, Amsterdam, 1986). R.E. Wendell and D.N. Lee, “Efficiency in multiple objective optimization problems,”Mathematical Programming 12 (1977) 406–414. L.A. Zadeh, “Optimality and nonscalar-valued performance criteria,”IEEE Transactions on Automatic Control AC-8-1 (1963) 59–60.