s.t:
(4-18)
(4-19)
(4-20)
(4-21)
در این مدل معادله (4-17) نشاندهنده تابع هدف مسأله اصلی بندرز است، معادله (4-18) برشهای بهینگی هستند که پس از رسیدن به حل بهینه زیر مسأله به مسأله اصلی اضافه میشوند، پارامترهای ، ، و مقادیر متغیرهای دوگان حاصل از حل زیر مسأله بندرز هستند، این مقادیر در محدودیتهای برش به عنوان مقدار ثابت در نظر گرفته میشوند. معادله (4-19) برشهای شدنی بودن هستند که در صورتی که زیر مسأله شدنی نباشد به مسأله اصلی اضافه میشود. پارامترهای ، ، و مقادیر متغیرهای دوگان حاصل از حل زیر مسأله بندرز هستند، این مقادیر در محدودیتهای برش به عنوان مقدار ثابت در نظر گرفته میشوند.
4-3-4- روند کلی الگوریتم تجزیه بندرز
شبه کد روند کلی الگوریتم تجزیه بندرز به شکل زیر است:
همانطور که از این شبه کد مشخص است، ابتدا باید یک جواب شدنی برای مسأله اصلی پیدا کنیم، این کار با استفاده از حل مسأله اصلی بدون هیچ نوع برشی انجام میشود، سپس جوابهای بدست آمده توسط مسأله اصلی به زیر مسأله داده شده، زیر مسأله حل میشود، در صورتی که زیر مسأله شدنی نباشد و جواب دوگان زیر مسأله بینهایت باشد، یک جهت بینهایت از دوگان گرفته با استفاده از این جهت یک برش شدنی بودن تولید شده این برش به مسأله اصلی اضافه میشود، در صورتی که زیر مسأله شدنی بوده و دارای جواب بهینه باشد، با استفاده از جوابهای بهینه زیر مسأله دوگان یک برش بهینگی تولید شده به مسأله اصلی اضافه میشود، در صورتی که جواب بدست آمده حد بالای بهتری بدست میدهد، حد بالا به روز میشود. سپس مسأله اصلی با استفاده از برش جدید دوباره حل شده حد پایین به روز میشود. این کار تا زمانی تکرار میشود که فاصله بین حد بالا و حد پایین از یک مقدار مشخصی کمتر شود.
این الگوریتم با استفاده از نرم افزار GAMS.23 توسعه داده شده نتایج اجرای آن برای حل مثالی که در فصل قبل ذکر شد، در جدول 4-3 گزارش شده است. همانطور که میدانیم حل مستقیم این مسأله توسط نرم افزار GAMS.23 نیاز به 109.118 ثانیه زمان داشت. همانطور که از این جدول برمیآید حل مسأله با استفاده از روش تجزیه بندرز نسبت به حل مستقیم مدل نیاز به مدل برنامه ریزی عدد صحیح مختلط در زمان کمتری انجام میشود. این موضوع نشان دهنده کارایی روش تجزیه بندرز است.
شکل 4-2 حدود بالا و پایین بدست آمده توسط روش تجزیه بندرز در طول تکرارهای مختلف را نمایش میدهد، همانطور که از این شکل برمیآید این روش پس از 17 تکرار به همگرایی میرسد.
جدول 4-3 نتایج حاصل از حل مثال عددی توسط روش تجزیه بندرز
مدل
تعداد کل متغیرها
تعداد کل محدودیتها
زمان اجرا (s)
مقدار تابع هدف
احتمالی
286786
31758
78.698
37235.000