A systematic extreme point enumeration procedure for fixed charge problem
Tóm tắt
In this paper the fixed charge problem viz: Min
$$\sum\limits_{j = 1}^n {(c_j x_j + F_j \delta _j )} $$
subject toAX=b, X>-0
$$\delta _j = \left\{ \begin{gathered} 0 if x_j = 0 \hfill \\ 1 if x_j > 0 \hfill \\ \end{gathered} \right.$$
is solved by systematically enumerating extreme points of a linear programming problem viz:
$$Min \sum\limits_{j = 1}^n {(c_j x_j + F_j \delta _j )} $$
subject toAX= b, x
j−dj °j≤0, X≥0 °≥0 where ° is an extreme point ofI
n °≤1. The technique provides an exact solution of the problem. The theory is supported by a numerical example.
Tài liệu tham khảo
G. Hadley: “Linear Programming”, Addison-Wesley Publishing Company, Inc. Reading, Mass, U.S.A.
G. Hadley: “Non-Linear and Dynamic Programming,” Addison-Wesley Publishing Company, Inc. Reading, Mass. Palo Alto. London.
Hirsch, W. M., and G. B. Dantzig: “The Fixed Charge Problem,” RM-1383, The Rand Corp. 1954.
M. C. Puri & Kanti Swarup: “An Algorithm for A Fixed Charge Problem”. Presented at 5th Annual Conference of O.R. Society of India held at Kharagpur, India 1972.
M. C. Puri & Kanti Swarup: “Simple Enumerative Method For Fixed Charge Problem.” To appear in INSA, India.
Dantzig, G. B.: “On the significance of Solving Linear Programming, Problems with some Integer Variables,” Econometrics, 28, 1960, pp. 30–44.
M. J. L. Kirby, H. R. Love and Kanti Swarup: “Extreme Point Mathematical Programming Problems”, ‘Management Science’, U.S.S., 1973.
M. J. L. Kirby, H. R. Love and Kanti Swarup: “Enumeration Technique for Extreme Point Mathematical Programming Problems”, Research report, Dalhousie University, May, 1970.
H. Kuhn and W. Baumol: “An approximate Algorithm for the Fixrd Charge Transportation Problem,” Naval Research Logistics Quarterly, 9, 1962, pp. 1–15.
Murty, K. G.: “Solving the fixed charge problem by Ranking the extreme points”. Operations Research Centre Report 66–7, University of California-Berkeley, Operations Research Centre (March 1966).
Murty K. G.: “Solving the Fixed Charge Transportation Problem by Ranking the Extreme Points.” Operations Research, Vol. 16, 1968, Nr. 2, pp. 268–279.
Gray, P.: “Exact Solution of the Fixed Charge Transportation Problem”. Paper presented at the 1968 joint ORSA/TIMS meeting at San Francisco, California, May 2, 1968.