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

Abstract

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