Safari S, Zaferanieh M, Abareshi M, Rahimi E L. The Lagrangian Relaxation Method for the Shortest Path Problem Considering Transportation Plans and Budgetary Constraint. jor 2019; 16 (2) :39-57
URL:
http://jamlu.liau.ac.ir/article-1-1631-fa.html
صفری سکینه، زعفرانیه مهدی، ابارشی مریم، لعل رحیمی ابراهیم. روش دوگان لاگرانژی برای مسأله کوتاهترین مسیر با درنظرگرفتن طرحهای عمرانی همراه با محدودیت بودجه. تحقیق در عملیات در کاربردهای آن. 1398; 16 (2) :39-57
URL: http://jamlu.liau.ac.ir/article-1-1631-fa.html
دانشگاه حکیم سبزواری، دانشکده ریاضی و علوم کامپیوتر، گروه ریاضی کاربردی، سبزوار
چکیده: (2693 مشاهده)
در این مقاله یک مساله کوتاهترین مسیر مقید مورد بررسی قرار میگیرد که در آن برای هر یک از یالهای شبکه طرحهای عمرانی مختلف با هزینه اجرای مشخص و نیز میزان کاهش مشخص برای زمان (طول) یال درنظر گرفته شدهاست. هدف مساله تعیین مسیر بین یک زوج مبدأ و مقصد و انتخاب طرحهای بهینه بر روی یالهای این مسیر است، به گونهای که زمان تغییر یافته مسیر، کمترین مقدار ممکن بوده و هزینه اجرایی طرحهای انتخابی از میزان بودجه در دسترس تجاوز نکند. با استفاده از روش دوگان لاگرانژی دستهای از محدودیتهای مساله آزاد شده و مساله دوگان لاگرانژی به دو زیر مساله کوچکتر تبدیل میشود. سپس با استفاده از الگوریتم زیرگرادیان یک جواب نزدیک به بهینه برای مساله اولیه حاصل میشود. در انتها با بررسی مدل پیشنهاد شده بر روی یک شبکه کوچک و نیز بر روی شبکه خراسان، جواب مساله برای زوجهای مبدأ و مقصد مختلف و با درنظرگرفتن پارامترهای متفاوت تعیین میشود.
نوع مطالعه:
پژوهشي |
موضوع مقاله:
تخصصي دریافت: 1396/11/14 | پذیرش: 1397/12/17 | انتشار: 1398/4/24