کد گمز مسئله مکان یابی محور با الگوریتم بندرز

کد گمز مسئله مکان یابی محور با استفاده از الگوریتم تجزیه بندرز

از این الگوریتم برای مسائلی که شامل متغیرهای سخت (باینری و عدد صحیح) می­باشند استفاده می­شود که مسئله را به دو زیر مسئله تقسیم می­ نماید.

problem شامل متغیرهای سخت می­باشد و sub problem شامل متغیرهای پیوسته می­باشد. ابتدا مسئله master حل شده و چون یک مسئله آزادسازی شده از مسئله اصلی می­باشد یک حد پایین می­دهد سپس مسئله دوگان sub حل شده و چون یک جواب شدنی می­دهد حد بالا برای مسئله اصلی است. سپس از جواب­های دوگانی که از sub بدست آمده برای اضافه کردن برش بهینگی در مسئله master استفاده می­شود. این رویه تا جایی ادامه پیدا می­کند که میزان اختلاف حد بالا و پایین از یک مقدار اپسیلون کمتر شود یا به عبارتی الگوریتم همگرا شود.

مسئله مکان یابی محور زیر را در نظر بگیرید:

تابع هدف به دنبال کمینه کردن هزینه های ثابت راه اندازی هاب و هزینه های حمل و نقل می باشد.

محدودیت ۲ باعث می شود که تمام تقاضا ها انتقال داده شوند و محدودیت ۳ نیز از ارتباط بین گره های غیر هاب جلوگیری می کند. پس می توان این مسئله را با الگوریتم تجزیه بندرز حل نمود چون تصمیم مربوط به راه اندازی هاب ها باینری و تصمیم مربوط به حمل و نقل پیوسته می باشد.

پس در قسمت مسئله master متغیرهای باینری مربوط به راه اندازی هاب ها قرار دارند و در قسمت sub نیز متغیرهای مربوط به حمل و نقل. که بایستی از دوگان مسئله sub برای اضافه کردن برش بهینگی به مسئله master استفاده نمود.

این محصول شامل پیاده سازی الگوریتم تجزیه بندرز در مسئله مکان یابی هاب می باشد که در نرم افزار گمز کدنویسی شده است.