تخمین جواب مدل برنامه‌ریزی غیرخطی روش بهترین-بدترین با استفاده از حل مدل‌های برنامه‌ریزی خطی مختلط

محورهای موضوعی : آمار

محمدرضا دهقانی ¹ (گروه مهندسی صنایع، دانشکده فنی و مهندسی، واحد شیراز، دانشگاه آزاد اسلامی، شیراز، ایران.)
مهدی عباسی ² (گروه مهندسی صنایع، دانشکده فنی و مهندسی، واحد شیراز، دانشگاه آزاد اسلامی، شیراز، ایران)

تاریخ دریافت : 1399/06/16 تاریخ پذیرش : 1400/02/07 تاریخ انتشار : 1401/06/01

کلید واژه: Special Ordered Sets (SOS), Best-Worst method (BWM), Piecewise Linear Approximation (PLA), Mixed-Integer Linear Programming Model (MILPM),

چکیده مقاله :

روش بهترین - بدترین یکی از روش‌های جدید در مسائل تصمیم‌گیری چند شاخصه می‌باشد. روش مزبور با تشکیل و حل یک مدل برنامه‌ریزی غیرخطی، جواب بهینه مسأله را تعیین می‌کند. با توجه به مشکلات حل مدل برنامه‌ریزی غیرخطی مربوطه، تلاش‌هایی جهت ارائه مدل‌های برنامه‌ریزی خطی یا مدل‌های برنامه‌ریزی خطی مختلط معادل صورت پذیرفته است. اما بر هر یک از مدل‌های ارائه شده، ایراداتی وارد است. در این مقاله با رفع ایرادات مزبور، الگوریتمی جهت تخمین جواب مدل برنامه‌ریزی غیرخطی روش مزبور با میزان خطای قابل قبول با استفاده از مدلسازی و حل مسائل برنامه‌ریزی خطی مختلط پیشنهاد شده است. در الگوریتم پیشنهادی ابتدا مدل برنامه‌ریزی غیرخطی معادل مدل اصلی تشکیل می‌شود. سپس با تقریب تکه‌ای خطی جملات غیرخطی مدل توسط روش SOS2، اولین مدل برنامه‌ریزی خطی مختلط متناظر تشکیل و حل می‌شود. اگر خطای جواب حاصله قابل قبول نباشد، بهبود تقریب تکه‌ای خطی جملات غیرخطی و همچنین تشکیل و حل مدل‌های جدید برنامه‌ریزی خطی مختلط تا حصول جواب با میزان خطای قابل قبول ادامه می‌یابد. به منظور بررسی اعتبار الگوریتم، روشی جهت تولید نمونه‌های پوشش دهنده حالت‌های مختلف یک مسأله پیشنهاد شد. سپس با استفاده از روش مزبور، تعداد 128 نمونه‌ی سه و پنج شاخصه تولید شد. نتایج حاصل از پیاده‌سازی الگوریتم پیشنهادی برای حل نمونه‌های تولید شده، عملکرد مناسب الگوریتم پیشنهادی را نشان می‌دهد. در این خصوص با حل حداکثر سه مدل برنامه‌ریزی خطی مختلط جهت حل نمونه‌ها، تخمین جواب با حداکثر 1% خطا به دست می‌آید.

چکیده انگلیسی:

The Best-Worst Method (BWM) is one of the latest methods in Multiple Attribute Decision Making (MADM) problems. The mentioned method determines the optimal solution by forming and solving a Non-Linear Programming Model (NLPM). In respect to the difficulties of solving the relevant NLPM, some attempts have been made to provide Linear Programming Models (LPM) or Equivalent Mixed Linear Programming Models. But there are some deficiencies in each of the proposed models. In this paper, by removing the mentioned deficiencies, an algorithm was proposed to estimate the solution of BWM NLPM with an acceptable error by forming and solving Mixed Integer Linear Programming Models (MILPMs). In the suggested algorithm, first, the equivalent model of NLPM (ENLPM) was formed. Then by Piecewise Linear Approximation (PLA) using the SOS2 method, the non-linear sentences of ENLPM were approximated and the first MILP model was formed and solved. If the error of solution is not acceptable, improving the PLA of the ENLPM nonlinear sentences, the forming of new MILPMs, and its solving continues until a solution with acceptable error obtained. To investigate the reliability of the algorithm, a new method for generating samples was proposed. Then using this method, 128 samples with three and five attributes were generated. The results of implementing the proposed algorithm to solve generated samples showed the performance and efficiency of the proposed algorithm. In this regard by forming and solving a maximum of three MILPMs of the samples, an estimation of the solution with 1% error was obtained.

منابع و مأخذ:

• اصغرپور، محمدجواد. تصمیم‌گیری‌های چند معیاره، چاپ هفدهم، انتشارات دانشگاه تهران. (1398).


• Rezaei, J. (2015). Best-worst multi-criteria decision-making method. Omega, 53, 49-57.


• Rezaei, J. (2016). Best-worst multi-criteria decision-making method: Some properties and a linear model. Omega, 64, 126-130.


• Beemsterboer, D. J. C., Hendrix, E. M. T., & Claassen, G. D. H. (2018). On solving the best-worst method in multi-criteria decision-making. IFAC-PapersOnLine, 51(11), 1660-1665.


• Beale, E. M. L., & Tomlin, J. A. (1970). Special facilities in a general mathematical programming system for non-convex problems using ordered sets of variables. OR, 69(447-454), 99.


• Aboutorab, H., Saberi, M., Asadabadi, M. R., Hussain, O., & Chang, E. (2018). ZBWM: The Z-number extension of Best Worst Method and its application for supplier development. Expert Systems with Applications, 107, 115-125.


• Liang, F., Brunelli, M., & Rezaei, J. (2019). Consistency issues in the best worst method: Measurements and thresholds. Omega, 102175.


• Mohammadi, M., & Rezaei, J. (2019). Bayesian best-worst method: A probabilistic group decision making model. Omega, 102075


• AMIRI, M., & EMAMAT, M. S. M. M. (2020). A Goal Programming Model for BWM. INFORMATICA, 31(1), 21-34.


• Vafadarnikjoo, A., Tavana, M., Botelho, T., & Chalvatzis, K. (2020). A neutrosophic enhanced best–worst method for considering decision-makers’ confidence in the best and worst criteria. Annals of Operations Research, 1-28.


• Leyffer, S., Sartenaer, A., & Wanufelle, E. (2008). Branch-and-refine for mixed-integer nonconvex global optimization. Preprint ANL/MCS-P1547-0908, Mathematics and Computer Science Division, Argonne National Laboratory, 39, 40-78.


• انصاری, محمدرضا, حسنی‌فرد, فاطمه. (1396). حل یک مسئله بهینه‌سازی غیرخطی، عدد صحیح و غیرمحدب با استفاده از روش‌های محدب‌سازی مبتنی بر مجموعه منظم خاص. فصلنامه سیستم‌های مختلط و غیرخطی, 1(1), 71-85.


• Kang, C., Guo, M., & Wang, J. (2017). Short-term hydrothermal scheduling using a two-stage linear programming with special ordered sets method. Water Resources Management, 31(11), 3329-3341.


• Hua, H., Hovestadt, L., Tang, P., & Li, B. (2019). Integer programming for urban design. European Journal of Operational Research, 274(3), 1125-1137.


• Huchette, J., & Vielma, J. P. (2019). A combinatorial approach for small and strong formulations of disjunctive constraints. Mathematics of Operations Research, 44(3), 793-820.


• Epelle, E. I., & Gerogiorgis, D. I. (2020). A Computational Performance Comparison of MILP vs. MINLP Formulations for Oil Production Computers & Chemical Engineering, 106903.


• Akbari-Dibavar, A.,Mohammadi-Ivatloo, B., & Zare, K. (2020). Optimal stochastic bilevel scheduling of pumped hydro storage systems in a pay-as-bid energy market environment. Journal of Energy Storage, 31, 101608.


• MirHassani, S. A., &Hooshmand, F. (2019). Methods and Models in Mathematical Programming. Springer International Publishing.