منبع پایان نامه ارشد درمورد نقطه مرجع، محدودیت ها، تصمیم گیری چند معیاره

دانلود پایان نامه ارشد

می نمایند. ویژگی اصلی روش های تولید کننده، سعی در یافتن تمامی یا بخشی از مجموعه جواب های غیرمسلط می باشد و ویژگی روش های تعاملی وجود فازهای تعامل با تصمیم گیرنده بین فازهای محاسباتی الگوریتمشان می باشد. روش های تولید کننده ای که سعی در یافتن تمامی یا زیر مجموعه بزرگی از جواب های غیر مسلط را دارند ممکن است نیازمند حجم محاسبات بالایی باشند که می تواند در مسائل بزرگ مشکل ساز باشد. علاوه بر آن، اگر مجموعه بزرگی از گزینه های مختلف به تصمیم گیرنده ارائه شود، تصمیم گیری برای وی مشکل خواهد بود. با وجود این، رویکرد هایی وجود دارد که سعی بر یافتن بخش کوچکی از مجموعه جواب های غیر مسلط می نماید. می توان یک روش تولید کننده را به سادگی به یک روش تعاملی تبدیل نمود. برای مثال روش تولید کننده ابتدا یک مجموعه از جواب های غیر مسلط پراکنده به تصمیم گیرنده ارائه می دهد. تصمیم گیرنده می تواند حدودی برای توابع هدف در نظر بگیرد و باوارد کردن آن محدودیت ها در مساله، یک مساله جدید حاصل خواهد شد که برای آن بار دیگر یک روش تولید کننده استفاده خواهد شد. برخی محققان ترجیحات تصمیم گیرندگان را به شکل توابع مطلوبیت ضمنی109 در نظر می گیرند. سپس فرایند تعاملی سعی می کند تا بهنیه ( یا تقریبی از آن ) را در تابع مطلوبیت ضمنی پیدا نماید. لازمه همگرائی به این مقدار بهینه عموماً عدم تناقض در پاسخ های تصمیم گیرنده در طول فرایند تعاملی می باشد.
از آغاز دهه هشتاد، محققان توجه بیشتری به توسعه روش های تعاملی برای حل مسائل MODM نموده اند تا بر مشکلات حاصل از روش های تولید کننده فائق آیند.روش های تعاملی باعث کاهش حجم محاسبات گشته و به تصمیم گیرنده در فرایند تصمیم گیری کمک می نماید. در روش های تعاملی، مجموعه پاسخ های موثر توسط دخیل کردن ترجیحات تصمیم گیرنده بررسی می گردد. این ویژگی اصلی تمامی روش های تعاملی می باشد. روش های تعاملی به یادگیری مستمر و انتخاب شده مجموعه جواب های موثر می پردازد در این روش ها هدف رسیدن به “بهترین” جواب نیست بلکه هدف عمده شان کمک به تصمیم گیرنده برای اجتناب از جستجو کردن بردارهای اهداف غیرمسلطی است که علاقه ای به آنها ندارد و منظور یافتن جواب های غیرمسلط و ارضا کننده می باشد. هیچ جواب غیر قابل برگشتی در کل پروسه وجود ندارد و تصمیم گیرنده همواره مجاز به برگشت به تکرار های قبلی می باشد. در نتیجه از تصمیم گیرنده تنها خواسته می شود تا مشخص کند که جستجوی پاسخ های موثر در کدام جهت جلو برود ویا گاها چند محدودیت به مدل اضافه نماید.فرایند وقتی پایان می یابد که تصمیم گیرنده به جواب حاصل رضایت دهد.
3-4- مفاهیم اولیه
1-3-4-مساله تصمیم گیری چند معیاره
برای درک بهتر برخی مفاهیم اصلی و اولیه را از مرجع (کولئو کولئو و همکاران 110، 2005) گزارش می دهیم. خوانندگان علاقه مند برای آشنایی بیشتر می توانند به این مرجع مراجعه نمایند.
مساله بهینه سازی زیر را در نظر بگیرید

در این مساله فضای تصمیم شدنی و غیر محدب تعریف شده توسط محدودیت های مدل، بردار مجموعه متغیرهای مساله است که می تواند عدد صحیح ( صفر و یک یا حالت عمومی) ویا عدد حقیقی متعلق به باشد. K تعداد توابع هدف مساله، zi مقادیر معیارها و فرض بر این است که بسته و محدود و غیرتهی می باشد. این مساله یک MOIP است اگر تمام متغیرها عدد صحیح بوده و یک MOMIP است اگر برخی متغیرها عدد صحیح و برخی دیگر اعداد حقیقی باشند. در مسائل خطی MOILP و MOMILP محدودیت ها را می توان به شکل و توابع هدف را به شکل نمایش داد که در آن یک ماتریس و b یک برداری ستونی با m مولفه و بردار های سطری با n مولفه می باشند. توابع محدودیت ها و اهداف اینگونه مسائل خطی بوده و برای مثال ضرب دو متغیر در یکدیگر مجاز نمی باشد.
2-3-4- فضای اهداف در برابر فضای تصمیم

معمولا برنامه ریزی تک هدفه در فضای تصمیم111 و برنامه ریزی چند هدفه در فضای اهداف112 مورد بررسی قرار می گیرد. برای نشان دادن تفاوت ایندو، برنامه دوهدفه در شکل1-4 را در نظر بگیرید که در آن c1=(3،1،-2) و c2=(-1،2،0) ضرائب توابع هدف می باشند. X فضای شدنی در فضای تصمیم می باشد که توسط بردار واحد در فضای R3 نشان داده شده است. شکل 2-4- نشان دهنده ناحیه شدنی Z در فضای اهداف می باشد که در آن هشت zi نگاشت هایی از هشت نقطه حدی فضای X می باشد. توجه شود که :
• نگاشت تمامی نقاط حدی X به فضای اهداف ، یک نقطه حدی در آن فضا ایجاد نمی کند.
• ابعاد Z حداکثر به اندازه k می باشد.
• لزوما Z در فضای غیر منفی اهداف قرار نمی گیرد.

شکل 1-4: فضای تصمیم

شکل 2-4- فضای اهداف
فرض کنید نشان دهنده محدوده شدنی در فضای اهداف باشد. یک نقطه متعلق به محدوده شدنی فضای اهداف می باشد اگر باشد و داریم.

3-3-4- بردار اهداف غیرمسلط

بردار در فضای اهداف، غیرمسلط می باشد اگر و تنها اگر دیگری وجود نداشته باشد به قسمی که برای تمامی اهداف داشته باشیم و برای حداقل یک هدف داشته باشیم . مجموعه تمامی بردارهای هدف غیرمسلط را با N نشان داده و مجموعه غیرمسلط می نامیم.
4-3-4- جواب موثر
در فضای تصمیم، بردار جواب یک پاسخ موثر113 برای مساله (P) می باشد اگر و تنها اگر وجود نداشته باشد به قسمی که برای همه توابع هدف داشته باشیم و حداقل برای یک تابع هدف این نامعادله به شکل اکید صدق کند. تعریف معادل آن این است که موثر است اگر و تنها اگر بردار اهداف آن ، ، غیرمسلط باشد. مجموعه تمام پاسخ های موثر را با E نشان داده و مجموعه موثر می نامیم.
5-3-4- جواب موثر ضعیف
بردار جواب یک پاسخ موثرضعیف114 برای مساله (P) می باشد اگر و تنها اگر وجود نداشته باشد به قسمی که برای همه توابع هدف داشته باشیم .
6-3-4- بردار غیرمسلط ضعیف
بردار در فضای اهداف، غیرمسلط ضعیف115 می باشد اگر و تنها اگر دیگری وجود نداشته باشد به قسمی که برای تمامی اهداف داشته باشیم. در حقیقت یک نقطه غیر مسلط ضعیف در فضای اهداف، نگاشت یک نقطه غیر موثر ضعیف در فضای تصمیم می باشد.
7-3-4- پاسخ پشتیبانی نشده
یک نقطه غیرمسلط را پشتیبانی نشده می نامیم اگر زیر سلطه یک ترکیب محدب از دو نقطه غیرمسلط متعلق به فضای شدنی اهداف مساله باشند. برای واضح شدن مطلب به شکل زیر دقت نمائید

شکل3-4- مجموعه نقاط غیر مسلط
از آنجائی که فضای شدنی مساله(p) غیر محدب است ممکن است جواب های پشتیبانی نشده نیز وجود داشته باشند. در شکل 3-4 می توان به خوبی به تفاوت این نقاط پی برد. تمامی نقاط روی مرز نقطه چین که تحت عنوان نقاط موثر ضعیف نشان داده شده اند، تحت تسلط ضعیف نقطه سمت راست خود می باشند. مجموعه نقاط موثر پشتیبانی نشده تحت تسلط ترکیب محدب دو نقطه موثر پررنگ شده از ناحیه عملی قرار دارند. مجموعه نقاط موثر قوی ناحیه عملی با خط پررنگ نشان داده شده است.در ادامه به تفصیل راجع به نحوه یافتن نقاط موثر از روی شکل توضیح داده خواهد شد.
4-4- تشخیص بردار های اهداف غیر مسلط از روی شکل

فضای R+ را زیر فضای غیرمنفی فضای Rk در نظر بگیرید.برای اینکه از روی شکل مشخص نمائیم که آیا یک مسلط است یا غیر مسلط، R+ را بر روی برگردانید. با این کار مجموعه ای به نام زیرفضای غیرمنفی برگردانده شده116 روی به وجود می آوریم و آنرا با نشان می دهیم که علامت جمع کراندار نشان دهنده جمع مجموعه ها در نظر گرفته شده است. بردار اهداف غیر مسلط است اگر و تنها اگر اشتراک و فضای شدنی اهداف Z ، تنها شامل نقطه باشد. .
در برنامه چند هدفه عدد صحیح نشان داده شده در شکل 4-4 داریم و . برای مثال، z3 غیر مسلط است زیرا اگر یک داشتیم که بر این جواب مسلط بود، می بایست داخل زیرفضای غیرمنفی برگردانده شده روی z3 قرار می گرفت. از طرف دیگر، z5 تحت تسلط است زیرا z6 درزیرفضای غیرمنفی برگردانده شده روی آن واقع شده است.

شکل 4-4- فضای اهداف گسسته

در شکل 5-4 ، مجموعه غیر مسلط را با نمایش می دهیم که منظور از bls پاره خط مرزی117 در جهت گردش عقربه های ساعت از نقطه z1 به نقطه z2 می باشد. در شکل z4 غیرمسلط است و z3 تحت تسلط می باشد.

شکل 5-4- یافتن نقاط غیر مسلط در فضای اهداف پیوسته

در شکل 6-4 که یک فضای غیر خطی را نشان می دهد ، مجموعه غیرمسلط برابر است با:

که پرانتز های باز نشان دهنده این است که نقاط حدی مربوطه در داخل مجموعه نیستند.

شکل 6-4- یافتن نقاط غیر مسلط در فضای اهداف غیر خطی

5-4-روش های پایه یافتن مجموعه جواب غیرمسلط در مسائل مختلط عدد صحیح

همانطور که بیان شد،از آنجا که فضای تصمیم یک مساله بهینه سازی مختلط عدد صحیح غیر محدب است صلاح نیست از روش های مبتنی بر جمع موزون اهداف به شکل استفاده نمود زیرا از یافتن پاسخ های غیر مسلط پشتیبانی نشده عاجز می باشند. محققین از سال های دور به این مطلب پی برده اند و به طور کلی دو روش پایه جهت یافتن مموعه جواب غیر مسلط در مسائل مختلط عدد صحیح پیشنهاد شده است (آلوس و کلیماکو، 2004)

1-5-4- برنامه ریزی مجموع موزون با محدودیت های اضافی

در این روش محدودیت هایی به مساله اضافه می شود. این محدودیت ها حدودی را روی مقادیر تابع هدف تحمیل می کنند. این امر باعث می شود برنامه مجموع موزون پاسخ های موثر پشتیبانی نشده را نیز بدست بیاورند. این برنامه مدرج شده را می توان به شکل زیر نمایش داد:

که در آن بوده و g یک بردار سطری از حدود اهداف می باشد.
علاوه بر این که هر جوابی که از حل به دست می آید موثر است، همواره یک وجود دارد که به ازای آن یک جواب موثر خاص تولید می کند.
2-5-4- برنامه ریزی بر مبنای نقطه مرجع
تئوری چبیشف ارائه شده توسط بومن118 (1976) می تواند رویکرد دیگری برای حل در اختیار ما بگذارد .با استفاده از این تئوری می توان به تولید یک مجموعه جواب غیر مسلط ( پشتیبانی شده یا نشده) در فضای اهداف پرداخت.
1-2-5-4- نقطه مرجع
فرض کنید K=1،…،k و یک بردار معیار مرجع باشد که المان های آن برابر است با :

و در آن می بایست اپسیلون مقدار کوچکی انتخاب شود. برای راحتی می توان اپسیلون را کوچکترین عددی انتخاب نمود که به اضافه آن عدد، برابر یک عدد صحیح می شود. منطقه قسمت پائین و چپ نقطه مرجع را دامنه مساله می نامیم. در شکل 7-4 منطقه داخل خط چین ها دامنه مساله می باشد.
2-2-5-4-فاصله چبیشف
برای محاسبه فاصله بین و، می توان از معیار چبیشف موزون استفاده نمود

که در آن اولا داریم و ثانیا به همراه هر معیار چبیشف موزون یک اشعه کاوشگر119 که از در جهت پائین با ضرائب ساطع می شود وجود دارد. خطوط تراز 120 معیار چبیشف موزون یک دسته مستطیل به مرکز نقطه مرجع شکل می دهند. علاوه بر این، در دامنه مساله، قطرهای تمامی مستطیل ها همان اشعه کاوشگر می باشد. در شکل 7-4 که اشعه کاوشگر در جهت می باشد، مستطیل ها همان خطوط تراز معیار چبیشف موزون با بردار وزنی هستند که از نقطه مرجع ساطع می شوند. با این معیارz1 نزدیک ترین گزینه به نقطه مرجع است زیرا در کوچکترین مستطیل قرار می گیرد. توجه شود که با تغییر بردار وزنی، جهت اشعه کاوشگر را تغییر داده در نتیجه شکل مستطیل های تراز نیز تغییر می کند .

شکل 7-4- فاصله چبیشف و خطوط تراز
3-2-5-4- بردارهای λ-موزون راس-T 121

توجه کنید که در برخی موردها، چندین بردار وزن λ می توانند در برنامه موزون چبیشف نقطه غیرمسلط یکسانی را حاصل نمایند. با وجود این، یکی از همه این بردارهای وزنی به نام بردار وزنی راس-T ویژگی خاصی دارد. این بردار وزنی برداریست که موجب میشود راس کوچکترین خط تراز تداخل کننده به نقطه ای خاص برخورد نماید. برای یک نقطه خاص و نقطه مرجع، این بردار وزنی از رابطه زیر حاصل می شود

4-2-5-4- نقاط روی کوچکترین خطوط تراز

تا زمانی که نقطه روی کوچکترین خط تراز مماس یکتا باشد،

پایان نامه
Previous Entries منبع پایان نامه ارشد درمورد زنجیره تامین، محدودیت ها، تصمیم گیری چند معیاره Next Entries منبع پایان نامه ارشد درمورد نقطه مرجع، نمونه برداری، بهینه سازی چند هدفه