توسعه یک الگوریتم نقطه مرزی برای حل مسائل برنامه‌ریزی خطی با جواب اولیه موجه

نوع مقاله : مقاله صنایع

نویسندگان

1 دانشگاه آزاداسلامی واحد اندیمشک

2 دانشچاه صنعتی جندی شاپور دزفول

چکیده

در این تحقیق برای حل مسائل برنامه ریزی خطی، الگوریتم SALCHOW توسعه داده شده است که در هرگام در جهت گرادیان مقید تابع هدف حرکت می‌کند به‌نوعی که همواره روی مرز ناحیه موجه باقی می‌ماند. این نوع حرکت بر روی مرز ناحیه موجه متفاوت با رفتار الگوریتم سیمپلکس است که روی گوشه های فضای موجه حرکت میکند. از سوی دیگر با رفتار الگوریتم های نقاط درونی هم که از روی مرز فضای موجه جدا شده و وارد آن می شوند، نیز متفاوت است. در واقع SALCHOW با یافتن تدریجی ضرایب وزنی برای مجموعه ای از قیدها و افزودن این جمع وزن‌دار به گرادیان تابع هدف، گرادیان مقید تابع هدف را بروزرسانی می‌کند؛ تا در نهایت ضرایب لاگرانژ قیود فعال در نقطه بهینه مسئله برنامه ریزی خطی را محاسبه کند. نتایج محاسباتی بر روی مجموعه ای از مسائل نمونه تصادفی تولید شده و چند مسئله استاندارد از پایگاه کتابخانه تحقیق در عملیات با اندازه کوچک نشان دهنده برتری زمانی SALCHOW نسبت به سیمپلکس در این مثالهای محدود است. به این معنی که متوسط زمان حل الگوریتم توسعه داده شده برای مسائل نمونه تابعی از تعداد متغیرهای تصمیم مسئله است. این امر بر خلاف رفتار سیمپلکس است که زمان اجرای آن در حالت متوسط، تابعی از تعداد قیدهای مسئله است. وجود خطای محاسباتی ناشی از گردکردن اعداد در محیط برنامه نویسی MATLAB امکان قضاوت در مورد برتری قاطع SALCHOW بر سیمپلکس را در حل مسائل کوچک سلب می نمود.

کلیدواژه‌ها

موضوعات

عنوان مقاله [English]

Developing a Boundary Point Method Algorithm for Solving Linear Programming Problems with Feasible Initial Solution

نویسندگان [English]

  • Mohamad Nekufar 1
  • Mohamad Ali Movafaghpour 2
چکیده [English]

In this research, SALCHOW algorithm has been developed to solve linear programming problems. In each step SLACHOW moves towards the constrained gradient of the objective function, so that it always remains within the feasible region. This type of generating sequence of feasible solutions on the boundary of the feasible region differs from the behavior of the simplex. Simplex moves on the corners of the feasible region. On the other hand, SALCHOW is also different from interior point methods; because interior point methods generate solutions that are not on the corner points or even borders of feasible region. SALCHOW assigns a set of coefficients to some active constraints for appending to objective function and updating constrained gradient of objective function. Finally at the optimal point, the Lagrange coefficients of the active constraints are found. Computational results are generated by using a set of randomly generated instance problems and a few standard ones from OR-Library. These results show the superiority of SALCHOW over the simplex in these small instances. In other words, the mean time of solving an instance with SALCHOW is a function of the number of decision variables in contrast with Simplex. Runtime of simplex in the average is a function of the number of constraints. The computational errors caused by round off errors in developed code in MATLAB exhibits that our developed code for SALCHOW suffers from cumulative errors; and it obstructs the possibility of judging the definite superiority of SALCHOW over the simplex in solving small instance problems.

کلیدواژه‌ها [English]

  • Linear Programming
  • Active Set Methods
  • Polynomial Time Order
  • Feasible Direction Method

مراجع

[1] G.B. Dantzig, Linear Programming and Extensions, Princeton Univ. Press, Princeton, N.J., 1963.
[2] N. Karmarkar, "A new polynomial-time algorithm for linear programming", Combinatorica Vol. 4, Issue 4, 1984, pp. 373–395.
[3] V. Klee, G.J. Minty, how good is the simplex algorithm in Inequalities III (Ed. O. Shisha), pp. 159-175, Academic Press, New York, 1972.
[4] G. Strang, the simplex method and Karmarkar's method, In Introduction to Applied Mathematics pp. 673-691. Wellesley-Cambridge Press, Wellesley, Mass, 1986.
[5] M. Zeleny, "An external reconstruction approach to linear programming", Computers and Operations Research, Vol. 13, Issue 1, 1986, pp. 95–100.
[6] G. Mitra, M. Tamiz, J. Yadegar, "Experimental investigation of an interior search method within a simplex framework", Commans ACM, Vol. 31, No. 12, 1988, pp. 1474–1482.
[7] J.A. Snyman, "An Interior Feasible Direction Method with Constraint Projections for Linear Programming", Computers & Mathematics with Applications, Vol. 20, Issue 12, 1990, pp. 43–54.
[8] G. Zoutendijk, Methods of Feasible Directions: A Study in Linear and Nonlinear Programming, Elsevier, Amsterdam and D Van Nostrand, Princeton, N.J., 1960.
[9] J.B. Rosen, "The gradient projection method for nonlinear programming, Part I, Linear constraints", SIAM J. Appl. Math, Vol. 8, No. 1, 1960, pp. 181–217.
[10] P. Wolfe, Methods of nonlinear programming. In Nonlinear Programming (Ed. J. Abadie), pp. 97–131. North-Holland, Amsterdam, 1967.
[11] W.I. Zangwill, "The Convex Simplex Method", Management Science, Vol. 14, No. 3, 1967, pp. 221–238.
[12] M.A. Diniz-Ehrhardt, M.A. Gomes-Ruggiero, J.M. Martinez, S.A. Santos, "Augmented Lagrangian Algorithms Based on the Spectral Projected Gradient Method for Solving Nonlinear Programming Problems", Journal of optimization theory and applications, Vol. 123, Issue 3, 2004, pp. 497–517.
[13] P.H. Calamai, J.J. Mori. "Projected Gradient Methods for Linearly Constrained Problems", Mathematical Programming, Vol. 39, Issue 1, 1987, pp. 93–116.
[14] D.P. Bertsekas, "Projected Newton Methods for Optimization Problems with Simple Constraints", Siam J. Control and Optimization, Vol. 20. No. 2, 1982, pp. 221–246.
[15] J.P. Dussault, G. Fournier, "Technical Note on the Convergence of the Projected Gradient Method", Journal of Optimization Theory and Applications, Vol. 77, No. 1, 1993, pp. 197–208.
[16] J.B. Rosen, "The Gradient Projection Method for Nonlinear Programming. Part II. Nonlinear Constraints", J. Soc. Indust. Appl. Math., Vol. 9, No. 4, 1961, pp. 514–532.
[ 11 ] ح. نورمحمدی، "بررسی روش زوتندیک در مسایل برنامه ریزی خطی"، مجله ریاضیات کاربردی، سال ششم، شماره 23 ، 1388، صفحه69-12 .
[18] M. Hintermuller, K. Ito, K. Kunisch, "The Primal-Dual Active Set Strategy as a Semismooth Newton Method", Siam J. Optim., Vol. 13, No. 3, 2003, pp. 865–888.
[19] R. Andreani, J.J. Júdice, J.M. Martínez, J. Patrício, "A projected–gradient interior–point algorithm for complementarity problems", Numerical Algorithms, Vol. 57, Issue 4, 2011, pp. 457–485.
[20] L.M. Grana Drummond, "A Projected Gradient Method for Vector Optimization Problems", Computational Optimization and Applications, Vol. 28, Issue 1, 2004, pp. 5–29.
[21] F.A. Potra, S.J. Wright, "Interior-Point Methods", Journal of Computational and Applied Mathematics, Vol. 124, Issues 1–2, 2000, pp. 281–302.
[22] J. Gondzio, "Interior Point Methods 25 Years Later", European Journal of Operational Research, Vol. 218, Issue 3, 2012, pp. 587–601.
[23] Y-H. Xiao, Q-J. Hu, Z. Wei, "Modified Active Set Projected Spectral Gradient Method for Bound Constrained Optimization", Applied Mathematical Modeling, Vol. 35, Issue 7, 2011, pp. 3117–3127
[24] A. Deza, E. Nematollahi, R. Peyghami, T. Terlaky, "The Central Path Visits All the Vertices of the Klee–Minty Cube", Optimization Methods and Software, Vol. 21, No. 5, 2006, pp. 851–865.
[25] A. Deza, E. Nematollahi, T. Terlaky, "How Good Are Interior Point Methods? Klee–Minty Cubes Tighten Iteration-Complexity Bounds", Mathematical Programming, Vol. 113, No. 1, 2008, pp. 1–14.
[26] F.S. Hillier, G.J. Lieberman, Introduction to Operations Research, 9th Edition, McGraw-Hill, New York, United States, 2010, pp. 142–143.
[27] E.G. Birgin, J.M. Martinez, "Large-Scale Active-Set Box-Constrained Optimization Method with Spectral Projected Gradients", Computational Optimization and Applications, Vol. 23, Issue 1, 2002, pp. 101–125.
[28] M. Andretta, E.G. Birgin, J.M. Martinez, "Partial spectral projected gradient method with active-set strategy for linearly constrained optimization", Numerical Algorithms, Vol. 53, No. 1, 2010, pp. 23–52.
مدل سازی در مهندسی
دوره 17، شماره 56
اردیبهشت 1398
صفحه 85-99

فایل ها

سابقه مقاله

  • تاریخ دریافت: 18 مرداد 1394
  • تاریخ بازنگری: 30 فروردین 1397
  • تاریخ پذیرش: 09 خرداد 1397
  • تاریخ اولین انتشار: 01 اردیبهشت 1398

اشتراک گذاری

ارجاع به این مقاله

آمار