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

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

Keywords:

مساله برنامه ریزی دوسطحی , شرایط بهینگی کاروش – کاهن – تاکر , روش شمارش ضمنی , مساله دوگان