توسعه روش‌های حل مساله برنامه‌ریزی دوسطحی خطی بر اساس روش شمارش ضمنی و روش دوگان

نخعی, عیسی; حسینی, اقبال; فتحی, محمد

توسعه روش‌های حل مساله برنامه‌ریزی دوسطحی خطی بر اساس روش شمارش ضمنی و روش دوگان

نوع مقاله : مقاله پژوهشی

نویسندگان

عیسی نخعی ¹

اقبال حسینی ²

محمد فتحی ³

¹ گروه صنایع، دانشگاه تربیت مدرس و دانشگاه کردستان

² گروه ریاضی، دانشگاه پیام نور تهران

³ گروه مهندسی برق، دانشگاه کردستان

چکیده

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

کلیدواژه‌ها

مساله برنامه‌ریزی دوسطحی

شرایط بهینگی کاروش – کاهن – تاکر

روش شمارش ضمنی

مساله دوگان

موضوعات

عنوان مقاله English

Enhancing the solution method of linear Bi – level programming problem based on enumeration method and dual method

نویسندگان English

Isa Nakhai Kamalabadi ¹

Eghbal Hosseini ²

Mohammad Fathi ³

¹ Department of Industrial Engineering, University of Kurdistan

² Payamenur University of Tehran, Department of Mathematics

³ Department of Power Engineering, University of Kurdistan

چکیده English

In the recent years, the bi-level programming problem (BLPP) is known as an appropriate approach for solving the real problems in applicable areas such as traffic, transportation, economics and supply chain management. There are several known algorithms to solve BLPP as an NP-hard problem. Almost all proposed algorithms in references have been used the Karush-Kuhn–Tucker to convert the BLPP into the single level problem which the obtained problem is complicated. In this paper, we attempt to develop two effective approaches, one based on enumeration method and the other based on duality characteristic for solving the linear BLPP. In these approaches, the BLPP is solved without using the Karush-Kuhn–Tucker conditions. The presented approaches achieve an efficient and feasible solution in an appropriate time which has been evaluated by comparing to references and test problems.

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

Bi-level programming problem

KKT conditions

Enumeration method

Dual problem

Download Full Text

[1] Bard, J.F. (1991). Some properties of the bi-level linear programming, Journal of Optimization Theory and Applications, 68, 371–378. [2] Mathieu, R., Pittard, L. and Anandalingam, G. (1994). Genetic algorithm based approach to bi-level Linear Programming, Operations Research, 28, 1–21. [3] L. Vicente, L., Savard, G. and Judice, J. (1994). Descent approaches for

quadratic bi-level programming, Journal of Optimization Theory and Applications, 81, 379–399. [4] Wang, G., Jiang, B. and Zhu, K. (2010). Global convergent algorithm for the bi-level linear fractional-linear programming based on modified convex simplex method, Journal of Systems Engineering and Electronics, 21, 239–243. [5] Yibing, Lv., Tiesong, Hu., Guangmin, Wang. and

Zhongping, Wan (2007). A penalty function method Based on Kuhn–Tucker condition for solving linear bi-level programming,

Applied Mathematics and Computation, 188, 808–813. [6] Zhongping, W. and Guangmin, W. (2011). A Dual-Relax Penalty Function Approach for Solving Non- Linear Bi-Level Programming with Linear Lower Level Problem, Acta Mathematica Scientia, 31, 652–660. [7] Allende, G. B. and Still, G. (2012). Solving bi-level programs with the KKT-approach, Springer and Mathematical

Programming Society, 131, 37–48. [8] Dempe, S. and Zemkoho, A.B. (2012). On the Karush–Kuhn–Tucker reformulation of the bi-level optimization problem, Nonlinear Analysis, 75, 1202–1218. [9] Arora, S.R. and Gupta, R. (2007). Interactive fuzzy goal

programming approach for bi-level programming problem, European Journal of Operational Research, 176, 1151–1166.