بخشی از مقاله
چکیده
در این مقاله روش حل برنامه ریزی خطی چندهدفه مختلط صفر و یک با الگوریتم شاخه و کران ماوروتاس و دایکولایکی مورد بررسی قرار گرفته است.. از آن جایی که در این الگوریتم ممکن است در انتها برخی از جواب ها به طور اشتباه بهینه محسوب شوند، تصحیحی روی این روش انجام شده است. به این صورت که یک تست صافی پیشنهاد و پیاده سازی شده است و باز به دلیل نواقص موجود در این تست، در نهایت راهکاری برای نمایش مجموعه ی جواب ها برای مسئله دو هدفه به طور خاص مطرح شده است. ارائه مدل اصلاح شده روی چند مثال عددی در برنامه نویسی متلب درستی این ادعا را نشان می دهد.
-1 مقدمه
بهینه سازی علمی است برای یافتن بهترین پاسخ برای مسئله ای که به صورت ریاضی تعریف شده است. در این علم تابع یا توابع معیار بهینگی و قیدهای موجود در مسئله مطالعه می گردد و روش هایی مدون برای حل آنها تعیین می شود. مدل های بهینه سازی از دوران انقلاب صنعتی در جهان و به خصوص از زمان جنگ جهانی دوم همواره مورد توجه ریاضیدانان و دست اندرکاران صنعت بوده است.
اما توجه محققین در دهه های اخیر معطوف به مدل های چندهدفه می باشد.در این تصمیم گیری ها به جای استفاده از یک هدف سنجش بهینگی از چندین هدف سنجش ممکن است استفاده گردد. بهینه سازی چندهدفه یکی از زمینه ها ی بسیار فعال و پرکاربرد تحقیقاتی درمیان مباحث بهینه سازی است. برنامه ریزی خطی چندهدفه مختلط صفر و یک بخش جالبی از برنامه ریزی ریاضی می باشد که در آن متغیرهای صحیح دودویی - 0-1 - می باشد. در این مقاله روش حل برنامه ریزی خطی چندهدفه مختلط صفر و یک با الگوریتم شاخه و کران چندهدفه بررسی و به طور خاص برای حالت دو هدفه راهکاری ارائه شده است.
-3 الگوریتم شاخه و کران
ماوروتاس و دایکولایکی الگوریتم شاخه و کران یک هدفه را برای برنامه ریزی چندهدفه خطی مختلط صفر و یک گسترش دادند2]،.[ 1 نمایش روند انشعاب و کران به صورت مجموعه ای متشکل از گره ها و قوس ها منجر به ایجاد درخت انشعاب و کران می گردد - شکل . - 1 در هر گره از درخت، یک متغیر دودویی را متغیرآزاد - - FV می نامیم، اگر این متغیر به وسیله ی هیچ شاخه ای که به این گره می رسد در سطحی از صفر ویک تثبیت نشده باشد. هرگرهی از درخت زیر مسئله ای با برخی متغیرهای دودویی ثابت را نشان می دهد. گره ریشه ی P0 متناظر با مسئله اصلی است که تمامی متغیر های دودویی در آن آزاد هستند.[ 3]
-4 حل برنامه ریزی چند هدفه خطی مختلط صفر و یک با الگوریتم شاخه و کران تعریف نقطه ی ایده آل : نقطه ای که از بهینه سازی تمام توابع هدف به طور جداگانه حاصل می شود، نقطه ی ایده آل نامیده می شود که به صورت بردار می باشد.[1]
قدم یکم - یکی از متغیرھ ای دودویی را در گره یک و دو به مقادیر صفر و یک اختصاص می دهیم که منجر به ایجاد دو شاخه می شود. ابتدا یکی از شاخه ها را تا انتها بررسی می کنیم.
قدم دوم- هر گره میانی Pj یک زیر مسئله با بعضی متغیرهای دودویی تثبیت شده را نشان می دهد که آزادسازی خطی - یعنی مسئله ای که در آن بعضی متغیرهای دودویی تثبیت شده اند و سایر متغیرهای دودویی به صورت یک نامساوی FV ≤ 1 به قیدهای مسئله اضافه می شوند - آن بررسی می شود. اگر نشدنی باشد، گره مورد نظر قطع می گردد.[2]
قدم سوم- در غیر این صورت نقطه ی ایده آل آن محاسبه می شود.
قدم چهارم- در هر گره پایانی از درخت جواب هایی حاصل می شود که در مجموعه ای با عنوان Dex ذخیره می شوندکه Dex در ابتدا تهی می باشند. زیر مسئله ھای متناظر با گره های پایانی یک MOLP می باشد زیرا تمامی متغیرهای دودویی آن تثبیت شده اند. مجموعه جواب های متناظر با MOLP در هر گره پایانی در مجموعه ای با عنوان E ذخیره می گردد. در پایان این روند مجموعه های متناظر Dex و E با هم ادغام می شوند و یک مقایسه ی دو به دو بین آنها صورت می گیرد و تمامی نقاط مغلوب حذف می شوند یعنی هر گرهی که به انتها می رسد Dex بروزرسانی می شود.[3]
قدم پنجم- اگر نقطه ایده آل محاسبه شده در گره های میانی به وسیله ی نقاط موجود در Dex مغلوب شود گره مورد نظر قطع می گردد. در موارد دیگر زیرگره های P2 j 1 و P2 j 2 تولید می شوند و زیرمسئله های متناظر با آن ها بررسی می شود.[3]
قدم ششم- تمامی موارد ذکر شده را برای شاخه ی دیگر نیز بررسی می کنیم.
