Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Phương pháp chiếu cho bài toán định vị cơ sở không giới hạn công suất
Tóm tắt
Nhiều thuật toán đã tồn tại để giải quyết bài toán xác định vị trí cơ sở không giới hạn công suất. Những thuật toán hiệu quả nhất dựa trên việc giải quyết sự nới lỏng lập trình tuyến tính mạnh. Đối ngẫu của sự nới lỏng này có dạng cô đọng, bao gồm việc tối thiểu hóa một hàm lồi tuyến tính theo từng đoạn nhất định. Bài báo này trình bày một phương pháp mới để giải quyết bài toán xác định vị trí cơ sở không giới hạn công suất dựa trên việc tìm ra giải pháp chính xác cho đối ngẫu cô đọng thông qua các phép chiếu vuông góc. Khối lượng công việc mỗi lần lặp lại có cùng bậc với một lần lặp của phương pháp đơn hình cho một chương trình tuyến tính có m biến và ràng buộc, trong đó m là số lượng khách hàng. Để so sánh, đối ngẫu của lập trình tuyến tính có mn + m + n biến và mn + n ràng buộc, trong đó n là số lượng vị trí tiềm năng cho các cơ sở. Phương pháp này rất linh hoạt vì nó có thể xử lý các ràng buộc bên. Đặc biệt, khi có khoảng cách đối ngẫu, mô hình lập trình tuyến tính có thể được củng cố bằng cách thêm các cắt. Kết quả số liệu cho một số bài toán kiểm tra cổ điển được đưa vào.
Từ khóa
#bài toán định vị cơ sở #lập trình tuyến tính #đối ngẫu #phép chiếu vuông góc #hàm lồiTài liệu tham khảo
S. Ahn, C. Cooper, G. Cornuejols and A. Frieze, “Probabilistic analysis of a relaxation for thek-median problem,”Mathematics of Operations Research 13 (1988) 1–31.
S. Busovaca, “Handling degeneracy in a nonlinearl 1 algorithm,” Technical Report CS-85-34, Department of Computer Science, University of Waterloo (Waterloo, Ont., 1985).
P.H. Calamai and A.R. Conn, “A projected Newton method forl p norm location problems,”Mathematical Programming 38 (1987) 75–109.
D.C. Cho, M.W. Padberg and M.R. Rao, “On the uncapacitated plant location problem II: Facets and lifting theorems,”Mathematics of Operations Research 8 (1983) 590–612.
A.R. Conn, “Nonlinear programming, exact penalty functions and projection techniques for nonsmooth functions,” in: P.T. Boggs, R.H. Byrd and R.B. Schnabel, eds.,Numerical Optimization 1984 (SIAM, Philadelphia, 1985) pp. 1–25.
G. Cornuejols, M.L. Fisher and G.L. Nemhauser, “Location of bank accounts to optimize float: An analytic study of exact and approximate algorithms,”Management Science 23 (1977) 789–810.
G. Cornuejols, G.L. Nemhauser and L.A. Wolsey, “The uncapacitated facility location problem,” to appear in: R.L. Francis and P. Mirchandani, eds.,Discrete Location Theory (Wiley, New York, 1989).
G. Cornuejols and J.-M. Thizy, “Some facets of the simple plant location polytope,”Mathematical Programming 23 (1982) 50–74.
M.A. Efroymson and T.L. Ray, “A branch and bound algorithm for plant location,”Operations Research 14 (1966) 361–368.
D. Erlenkotter, “A dual-based procedure for uncapacitated facility location,”Operations Research 26 (1978) 992–1009.
R.S. Garfinkel, A.W. Neebe and M.R. Rao, “An algorithm for the M-median plant location problem,”Transportation Science 8 (1974) 217–236.
M. Grötschel and M.W. Padberg, “Polyhedral theory and polyhedral computations,” in: E. L. Lawler, J. K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys, eds.,The Traveling Salesman Problem (Wiley, New York, 1985) pp. 251–360.
M. Guignard, “Fractional vertices, cuts and facets of the simple plant location problem,”Mathematical Programming Study 12 (1980) 150–162.
M. Guignard and K. Spielberg, “Algorithms for exploiting the structure of the simple plant location problem,”Annals of Discrete Mathematics 1 (1977) 247–271.
R.L. Karg and G.L. Thompson, “A heuristic approach to solving traveling salesman problems,”Management Science 10 (1964) 225–248.
M. Körkel, “On the exact solution of large-scale simple plant location problems,” Technical Report 032TB22e, Forschungsinstitute beim FTZ (Darmstadt, 1987).
P. Krolak, W. Felts and G. Marble, “A man-machine approach towards solving the traveling salesman problem,”Communications of the ACM 14 (1971) 327–334.
J.G. Morris, “On the extent to which certain fixed-charge depot location problems can be solved by LP,”Journal of the Operational Research Society 29 (1978) 71–76.
J.M. Mulvey and H.L. Crowder, “Cluster analysis: An application of Lagrangian relaxation,”Management Science 25 (1979) 329–340.
S.C. Narula, U.I. Ogbu and H.M. Samuelsson, “An algorithm for thep-median problem,”Operations Research 25 (1977) 709–713.
C.S. ReVelle and R.S. Swain, “Central facility location,”Geographical Analysis 2 (1970) 30–42.
L. Schrage, “Implicit representation of variable upper bounds in linear programming,”Mathematical Programming Study 4 (1975) 118–132.
K. Spielberg, “Algorithms for the simple plant-location problem with some side conditions,”Operations Research 17 (1969) 85–111.