عنوان پایان‌نامه
رویه های کارای ماکسیمال در برنامه ریزیخطی چند هدفه
- رشته تحصیلی
- ریاضی کاربردی
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس علوم شماره ثبت: ۴۱۳۲;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 46143
- تاریخ دفاع
- ۰۳ آبان ۱۳۸۹
- دانشجو
- کلثوم احمدی
- استاد راهنما
- مجید سلیمانی دامنه
- چکیده
- یکی از سوال های مهمی که در مسائل برنامه ریزی خطی چندهدفه (MOLP) مطرح می شود این است که چگونه مجموعه جواب های کارای این مسائل را بدست آوریم. در این پایان نامه به بررسی روش هایی برای یافتن مجموعه جواب های کارای یک MOLP می پردازیم. روش سیمپلکس چندهدفه از جمله اولین روش هایی است که با بررسی نقاط راسی مجاور، جواب های کارای یک MOLP را بدست میآورد. این روش ممکن است در حضور تباهیدگی دچار مشکل شود. برای رفع این مشکل و همچنین برای اینکه نمایش کاملی از مجموعه جواب های کارای یک MOLP ارائه دهیم، الگوریتم یان را توضیح می دهیم. این الگوریتم تعداد متناهی از وزن ها را تعیین و متناظر با هریک از این وزن ها یک مسالهی مجموع وزندار را حل میکند و در نهایت همه ی جواب های کارای ضعیف و همچنین همه ی جواب های کارای یک MOLP را بدست می آورد. چنانچه حداقل یکی از مسائل مجموع وزندار جواب بهینه متناهی نداشته باشد الگوریتم یان موثر نخواهد بود. برای رفع این نقص یک روش اصلاح شده را که توسط جعفری و فروغی ارائه شده است، شرح می دهیم. هدف دیگر این پایان نامه تعیین رویه های کارای ماکسیمال یک MOLP است. این رویه ها یک تجزیه محدب از مجموعه جواب های کارا هستند و نسبت به سایر تجزیه ها کمترین تعداد عناصر را دارند. چون برای بدست آوردن رویه های کارای ماکسیمال یک MOLP به نقاط کارای راسی و جهات کارای راسی نیاز داریم، روشی را برای تعیین همه ی نقاط کارای راسی و جهات کارای راسی یک MOLP نیز شرح می دهیم. واژه های کلیدی: برنامه ریزی خطی چندهدفه، کارایی، مجموعه جواب های کارا، ساختار جواب ها، رویه های کارای ماکسیمال، مجموعه اندیس مینیمال.
- Abstract
- An important question arising in MultiObjective linear Programming (MOLP) is the determination of the efficient set. In this thesis we investigate some methods for finding efficient set of a MOLP. Multiple criteria simplex is one of the earliest methods which finds efficient solutions of an MOLP by examining the adjacent extreme points. This method is not a suitable method in the presence of degeneracy. To overcome this problem and also to give a complete representation of the efficient set, we explain Yan's algorithm. This algorithm determines a finite number of weights and obtains all weak efficient and efficient solutions of an MOLP, by solving some weighted sum problems. If at least one of these weighted sum problems has not a finite optimal value, Yan's algorithm will fail. To overcome this problem, the algorithm has been modified by Foroughi and Jafari. We will discuss this modification, as well. Another purpose of this study is determining the maximal efficient faces in MOLP. These faces provide a convex decomposition of the efficient set with the least number of elements. Since we need efficient extreme points and efficient extreme rays for determining maximal efficient faces, a method for finding all efficient extreme points and efficient extreme rays of an MOLP is explained. Keywords: Multiobjective linear programming, Efficiency, Efiicient solutions set, Solutions structure, Maximal efficient faces, Minimal index set
