بخشی از مقاله
چکیده
حالت خاصی از برنامه}ر یزی چندترازه، ١برنامه}ر یزی^های دوترازه٢ است که بعلت سهولت در نشان دادن تاثیر روش، بیشتر دو ترازه درنظر گرفته می_شود. همچنین یکی از انواع مهم و اساسی سیستم^های دو ترازه مسائل برنامه}ر یزی خطیدوترازه - Blpp - است.هرچند که توابع هدف و قیود سطوح بالا و پایین این نوع مسائل همگی خطی هستند اما از طرفی این نوع برنامه}ر یزی برای توابع هدف مسائل تراز بالا در همه_حا پیوسته و محدب نیستند و مهم هستند. جوابی از مسائل پایین_تر را بدستآورند که بطور کلی خطی و مشتق_پذیر نباشند.در این مقاله قصد دار یم طرحی از الگور یتم ژنتیک را برای حل - Blpp - با ساختن تابع برازندگی تراز بالای یک برنامه}ر یزی خطی برپایه تعریف درجه شدنی بودن ارائه دهیم. الگور یتم ژنتیکی که در اینجا بکار گرفته میÁشود از روش تابع جریمه قیود استفاده نمی»کند بلکه با تغییر تصادفی نسل آغازین جمعیت به جای یک نسل آغازین صادق در قیود به منظور بهبود بخشیدن توانایی الگور یتم، جواب بهینه را بدست می_آورد و سرانجام با نتایج عددی به دست آمده و تعدادمثال حل شده با این روش، توانایی و کارا بودن آن را نشان می_دهد.
واژههای کلیدی:برنامه}ر یزی خطی دو ترازه، تصمیم_گیری نا متمرکز٣، جواب بهینه۴، الگور یتم ژنتیک۵.
١مقدمه
یک سیستم تصمیم نامتمرکز و غیر مشارکتی را در یک وضعیت تعادلی که یک رهبر و چندین پیرو با هم در ارتباط هستند در نظر میNگیریم، فرض _کنیم که رهبر و پیروها هر کدام متغیرهای تصمیم مربوط به خودشان را داشته باشند؛ رهبر می]تواند از طریق متغیرهای تصمیم خودش به عکسالعمل پیروها تأثیر بگذارد، - امرکند - در مقابل، پیروها در این_که کار بردهای عینی خود را در قبال تصمیمات رهبر و پیروهای دیگر بهبود بخشند و به حدا کثر برسانندI، اختیار تام دارندI، لذا ابزار نیرومند سیستم^های تعیین نامتمرکز »برنامه}ر یزی چند ترازه« است، لازم به ذکر است که فرمول^های برنامه}ر یزی خطی ممکن است، بهÁطور قابلملاحظه_ای از یک مقاله تا مقاله دیگر تغییر کند.بیالاس و کاروان در سال - ۴١٩٨ - نامحدب بودن مسائل تراز بالا را با مثال^های عددی اثبات نمودند ]١.[همچنین باردوبن-آید اثبات نمودند که هر - Blpp - یک مسأله NP-hard است. ]١[ علاوه بر این در سالهای اخیر و بینسنت و ساوارد - ٢٠٠١ - اذعان داشتند که هر مسأله NP-hardمی]تواند جواب بهینه کلی مسأله - Blpp - را پیدا کند]١.[در حال حاضر الگور یتم^های منطقی برای حل برنامه}ر یزی خطی دوترازه ارائه شده است که می_توان آنها را بطور خلاصه بصورت زیر دسته_بندی نمود:
١- روش پیدا کردن نقطه رأسی: این روش اساساً برگرفته از الگور یتم -K ام بهترین است ]١.[
٢- روش تبدیلات: این روش برگرفته از الگور یتم مکمل خطی و الگور یتم شاخه و کران و روش کار بردی تابع جریمه میباشد.
٣- روش تکاملی: این روش براساس حل ژنتیکی معادله تعادل Nash و الگور یتم ژنتیک است.
٢ مدل ریاضی برنامه}ریزی خطی دو ترازه - Blpp -
انواع مختلفی از مدلهای برنامه}ر یزی خطی و غیرخطی دو ترازه وجود دارد که در این مقاله مدل زیر را به عنوان مدل برنامه}ر یزی خطی معرفی می_کنیم ]١:[
بطور یکه:که ا گر x ثابت فرض شود، جمله ctxدر تابع هدف تراز پایین ثابت می_شود. بنابراین تابع هدف مسأله تراز پایین بصورت زیر درمی_آید:حال فرض کنید ناحیه قیدی مسأله برنامه}ر یزی دوترازه خطی بصورتباشد که این ناحیه ناتهی و کراندار است سپس مجموعه ناتهی و کرانداررا درنظر بگیرید و فرض کنید Y - x - مجموعه جوابهای بهینه مسأله max f = dtyباشد. عضو منحصربفردی از مجموعه Y - x - موجود است بطور یکه:
بنابراین مسأله ١Pمی]تواند به فرم زیر درآید:
حال ا گر نقطه - x; y - یک جواب مسأله زیر باشد:
بنابراین - x; y - جواب مسأله - ١ - P نیز هست.
تعریف ٢.١. نقطه - x; y - را شدنی گوییم: - feasibility point - ا گر:
تعریف ٢.٢. نقطه شدنی - x_; y _ - 2 f - s - را جواب بهینه مسأله - Blpp - میºدانیم ا گروفقط ا گر برای هر نقطه - x; y - 2 f - s - داشته باشیم:
این مقاله روش عددی - Blpp - را براساس این تعار یف بحث می_کند.
٣ طرح الگوریتم ژنتیک برای - Blpp -
شناخت تابع هدف تراز بالا در برنامه}ر یزی خطی دوترازه کار آسانی نیست و نمی _توان فرمول آشکار و واضحی برای آن بدست آورد چون حل اینگونه توابع از حل توابع تراز پایینی ناشی میÁشود که خود نیز فرمول_بندی مشخصی ندارد، بنابراین به کار بردن تعریف مشتق کار آسانی نبوده و لذا بحث روی وجود جوابهای بهینه با توجه به شرایط ذکر شده در الگور یتم^ های مذکور و همچنین الگور یتم ژنتیک در مسائل بهینه_سازی با روشهای عددی کار بسیار مشکلی است. لذا در این نوشتار سعی دار یم برنامه}ر یزی خطی دوترازه را با استفاده از الگور یتم ژنتیک که روشی کارا در بدست آوردن جواب بهینه است بکار ببریم.
۴ ایده اصلی الگوریتم - GA - ارائه شده برای حل - Blpp -
ابتدا یک جمعیت آغازین صادق در قیود انتخاب میNکنیم، سپس متغیر تصمیم تراز پایین را متناظر با وا کنش بهینه تراز بالا می^سازیم و افراد را با محاسبه تابع برازندگی^شان برمبنای درجه شدنی بودن، تا زمانیکه جواب بهینه توسط عملگر ژنتیکبیشتر و بیشتر و بهتر جستجو شود ارزیابی میNکنیم.
