بردار در فضای اهداف، غیرمسلط می باشد اگر و تنها اگر دیگری وجود نداشته باشد به قسمی که برای تمامی اهداف داشته باشیم و برای حداقل یک هدف داشته باشیم . مجموعه تمامی بردارهای هدف غیرمسلط را با N نشان داده و مجموعه غیرمسلط می نامیم.
( اینجا فقط تکه ای از متن فایل پایان نامه درج شده است. برای خرید متن کامل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )
۴-۳-۴- جواب موثر
در فضای تصمیم، بردار جواب یک پاسخ موثر[۱۱۳] برای مساله (P) می باشد اگر و تنها اگر وجود نداشته باشد به قسمی که برای همه توابع هدف داشته باشیم و حداقل برای یک تابع هدف این نامعادله به شکل اکید صدق کند. تعریف معادل آن این است که موثر است اگر و تنها اگر بردار اهداف آن ، ، غیرمسلط باشد. مجموعه تمام پاسخ های موثر را با E نشان داده و مجموعه موثر می نامیم.
۵-۳-۴- جواب موثر ضعیف
بردار جواب یک پاسخ موثرضعیف[۱۱۴] برای مساله (P) می باشد اگر و تنها اگر وجود نداشته باشد به قسمی که برای همه توابع هدف داشته باشیم .
۶-۳-۴- بردار غیرمسلط ضعیف
بردار در فضای اهداف، غیرمسلط ضعیف[۱۱۵] می باشد اگر و تنها اگر دیگری وجود نداشته باشد به قسمی که برای تمامی اهداف داشته باشیم . در حقیقت یک نقطه غیر مسلط ضعیف در فضای اهداف، نگاشت یک نقطه غیر موثر ضعیف در فضای تصمیم می باشد.
۷-۳-۴- پاسخ پشتیبانی نشده
یک نقطه غیرمسلط را پشتیبانی نشده می نامیم اگر زیر سلطه یک ترکیب محدب از دو نقطه غیرمسلط متعلق به فضای شدنی اهداف مساله باشند. برای واضح شدن مطلب به شکل زیر دقت نمائید
شکل۳-۴- مجموعه نقاط غیر مسلط
از آنجائی که فضای شدنی مساله(p) غیر محدب است ممکن است جواب های پشتیبانی نشده نیز وجود داشته باشند. در شکل ۳-۴ می توان به خوبی به تفاوت این نقاط پی برد. تمامی نقاط روی مرز نقطه چین که تحت عنوان نقاط موثر ضعیف نشان داده شده اند، تحت تسلط ضعیف نقطه سمت راست خود می باشند. مجموعه نقاط موثر پشتیبانی نشده تحت تسلط ترکیب محدب دو نقطه موثر پررنگ شده از ناحیه عملی قرار دارند. مجموعه نقاط موثر قوی ناحیه عملی با خط پررنگ نشان داده شده است.در ادامه به تفصیل راجع به نحوه یافتن نقاط موثر از روی شکل توضیح داده خواهد شد.
۴-۴- تشخیص بردار های اهداف غیر مسلط از روی شکل
فضای R+ را زیر فضای غیرمنفی فضای Rk در نظر بگیرید.برای اینکه از روی شکل مشخص نمائیم که آیا یک مسلط است یا غیر مسلط، R+ را بر روی برگردانید. با این کار مجموعه ای به نام زیرفضای غیرمنفی برگردانده شده[۱۱۶] روی به وجود می آوریم و آنرا با نشان می دهیم که علامت جمع کراندار نشان دهنده جمع مجموعه ها در نظر گرفته شده است. بردار اهداف غیر مسلط است اگر و تنها اگر اشتراک و فضای شدنی اهداف Z ، تنها شامل نقطه باشد. .
در برنامه چند هدفه عدد صحیح نشان داده شده در شکل ۴-۴ داریم و . برای مثال، z3 غیر مسلط است زیرا اگر یک داشتیم که بر این جواب مسلط بود، می بایست داخل زیرفضای غیرمنفی برگردانده شده روی z3 قرار می گرفت. از طرف دیگر، z5 تحت تسلط است زیرا z6 درزیرفضای غیرمنفی برگردانده شده روی آن واقع شده است.
شکل ۴-۴- فضای اهداف گسسته
در شکل ۵-۴ ، مجموعه غیر مسلط را با نمایش می دهیم که منظور از bls پاره خط مرزی[۱۱۷] در جهت گردش عقربه های ساعت از نقطه z1 به نقطه z2 می باشد. در شکل z4 غیرمسلط است و z3 تحت تسلط می باشد.
شکل ۵-۴- یافتن نقاط غیر مسلط در فضای اهداف پیوسته
در شکل ۶-۴ که یک فضای غیر خطی را نشان می دهد ، مجموعه غیرمسلط برابر است با:
که پرانتز های باز نشان دهنده این است که نقاط حدی مربوطه در داخل مجموعه نیستند.
شکل ۶-۴- یافتن نقاط غیر مسلط در فضای اهداف غیر خطی
۵-۴-روش های پایه یافتن مجموعه جواب غیرمسلط در مسائل مختلط عدد صحیح
همانطور که بیان شد،از آنجا که فضای تصمیم یک مساله بهینه سازی مختلط عدد صحیح غیر محدب است صلاح نیست از روش های مبتنی بر جمع موزون اهداف به شکل استفاده نمود زیرا از یافتن پاسخ های غیر مسلط پشتیبانی نشده عاجز می باشند. محققین از سال های دور به این مطلب پی برده اند و به طور کلی دو روش پایه جهت یافتن مموعه جواب غیر مسلط در مسائل مختلط عدد صحیح پیشنهاد شده است (آلوس و کلیماکو، ۲۰۰۴)
۱-۵-۴- برنامه ریزی مجموع موزون با محدودیت های اضافی
در این روش محدودیت هایی به مساله اضافه می شود. این محدودیت ها حدودی را روی مقادیر تابع هدف تحمیل می کنند. این امر باعث می شود برنامه مجموع موزون پاسخ های موثر پشتیبانی نشده را نیز بدست بیاورند. این برنامه مدرج شده را می توان به شکل زیر نمایش داد:
که در آن بوده و g یک بردار سطری از حدود اهداف می باشد.
علاوه بر این که هر جوابی که از حل به دست می آید موثر است، همواره یک وجود دارد که به ازای آن یک جواب موثر خاص تولید می کند.
۲-۵-۴- برنامه ریزی بر مبنای نقطه مرجع
تئوری چبیشف ارائه شده توسط بومن[۱۱۸] (۱۹۷۶) می تواند رویکرد دیگری برای حل در اختیار ما بگذارد .با بهره گرفتن از این تئوری می توان به تولید یک مجموعه جواب غیر مسلط ( پشتیبانی شده یا نشده) در فضای اهداف پرداخت.
۱-۲-۵-۴- نقطه مرجع
فرض کنید K=1،…،k و یک بردار معیار مرجع باشد که المان های آن برابر است با :
و در آن می بایست اپسیلون مقدار کوچکی انتخاب شود. برای راحتی می توان اپسیلون را کوچکترین عددی انتخاب نمود که به اضافه آن عدد، برابر یک عدد صحیح می شود. منطقه قسمت پائین و چپ نقطه مرجع را دامنه مساله می نامیم. در شکل ۷-۴ منطقه داخل خط چین ها دامنه مساله می باشد.
۲-۲-۵-۴-فاصله چبیشف
برای محاسبه فاصله بین و ، می توان از معیار چبیشف موزون استفاده نمود
که در آن اولا داریم و ثانیا به همراه هر معیار چبیشف موزون یک اشعه کاوشگر[۱۱۹] که از در جهت پائین با ضرایب ساطع می شود وجود دارد. خطوط تراز [۱۲۰] معیار چبیشف موزون یک دسته مستطیل به مرکز نقطه مرجع شکل می دهند. علاوه بر این، در دامنه مساله، قطرهای تمامی مستطیل ها همان اشعه کاوشگر می باشد. در شکل ۷-۴ که اشعه کاوشگر در جهت می باشد، مستطیل ها همان خطوط تراز معیار چبیشف موزون با بردار وزنی هستند که از نقطه مرجع ساطع می شوند. با این معیارz1 نزدیک ترین گزینه به نقطه مرجع است زیرا در کوچکترین مستطیل قرار می گیرد. توجه شود که با تغییر بردار وزنی، جهت اشعه کاوشگر را تغییر داده در نتیجه شکل مستطیل های تراز نیز تغییر می کند .
شکل ۷-۴- فاصله چبیشف و خطوط تراز
۳-۲-۵-۴- بردارهای Λ-موزون راس-T [۱۲۱]
توجه کنید که در برخی موردها، چندین بردار وزن λ می توانند در برنامه موزون چبیشف نقطه غیرمسلط یکسانی را حاصل نمایند. با وجود این، یکی از همه این بردارهای وزنی به نام بردار وزنی راس-T ویژگی خاصی دارد. این بردار وزنی برداریست که موجب میشود راس کوچکترین خط تراز تداخل کننده به نقطه ای خاص برخورد نماید. برای یک نقطه خاص و نقطه مرجع، این بردار وزنی از رابطه زیر حاصل می شود
۴-۲-۵-۴- نقاط روی کوچکترین خطوط تراز
تا زمانی که نقطه روی کوچکترین خط تراز مماس یکتا باشد، نقطه غیرمسلط است. اگر و تابع قطر زیرفضای غیرمنفی برگردانده شده باشد به قسمی که . آنگاه غیر مسلط است. به شکل ۸-۴ دقت نمائید.
فرم در حال بارگذاری ...