بخشی از مقاله
چکیده
مسئله چندهدفه هندسی، یکی از مسائل مهم چندهدفه هست. در مسائل چندهدفه هندسی توابع هدف و قیود بهصورت هندسی هستند. در این مقاله ما روشی ارائه میدهیم که در آن تشخیص داده میشود که یک نقطه شدنی از ناحیه شدنی مسئله چندهدفه هندسی، کارا یا ناکارا است و همچنین در آن از یک نقطه شدنی ناکارا به یک جواب کارا دست پیدا خواهیم کرد.
واژه های کلیدی: مسئله چندهدفه هندسی، جواب کارا، دوال لاگرانژ.
-1 مقدمه
برنامهریزی چندهدفه - - MOP یکی از شاخههای مهم تحقیق در عملیات میباشد که مسائل آن شامل چندین تابع هدف میباشند. روشهای متعددی برای حل اینگونه مسائل پبشنهاد شده است. مسائل چندهدفه هندسی - MOGP - یکی از مسائل مهم چندهدفه با ساختار توابع هدف و قیود غیرخطی و هندسی میباشد. محققان روشهای متعددی برای حل اینگونه مسائل ارائه دادند. پترسون و زندر[2]، کان و همکارش [1]، کانترویچ [ 5]، ویلس ون [7] و ایوانس [3] مقالاتی در خصوص حل مسئله هندسی تک هدفه ارائه دادند. همچنین محققان دیگری در مورد حل مسئله چند هدفه هندسی روش هایی ارائه دادند از قبیل هوانگ و همکارش [4] و جورج موراتاس [6] مسئله چند هدفه هندسی را با استفاده از روش حدی حل کردند. در این مقاله ما روشی ارائه می دهیم که در آن تشخیص داده می شود که یک نقطه شدنی از مسئله چند هدفه هندسی کارا است یا خیر. در این روش با استفاده از یک نقطه شدنی به یک جواب کارا برای مسئله چند هدفه هندسی دست پیدا خواهیم کرد. در این روش برای توابع هدف وزن در نظر گرفته شده است.
-2 تعاریف و مفاهیم اولیه
یک مسئله چند هدفه، به طور کلی به صورت زیر تعریف می شود:که در آن بردار یا متغیر تصمیم است و - - ، امین تابع هدف بوده و X مجموعه ی جوابهای قابل قبول می باشد.
-1-2 تعریف: ̅ ∈ یک جواب کارا از مسئله - 1 - است، اگر∈ X وجود نداشته باشد به طوری که
-2-2 تعریف: ̅∈ یک جواب کارای ضعیف مسئله - 1 - است، هرگاه ی در ناحیه شدنی وجود نداشته باشد که ملاحظه -1-2 تعاریف 1-2 و 2-2 نشان می دهد که هر جواب کارا، جواب کارای ضعیف است. اما برعکس آن در حالت کلی برقرار نیست.روش های متعددی برای پیدا کردن جواب کارا مسائل چند هدفه وجود دارد. در این مقاله ما به بیان یک روش برای تشخیص وضعیت کارایی یک نقطه شدنی از ناحیه شدنی مسئله - 1 - ، می پردازیم . در این الگوریتم با حل یک مسئله فرعی سعی می کنیم که جواب قابل قبول دیگری پیدا کنیم که مقدار حداقل یک تابع هدف را کاهش داده در حالی که دیگر توابع هدف افزایش پیدا نکنند. اگر چنین جوابی پیدا شود جواب فعلی یک جواب غیر کارا است و اگر پیدا نشود، جواب فعلی یک جواب کارا خواهد بود. اگر جواب فعلی 1 باشد می خواهیم یک جواب پیدا کنیم که برای = 1, 2, … , ، - - ⩽ - 1 - و به ازای حداقل یک رابطه فوق به صورت مطلق کوچکتر باشد.حال، مسئله برنامه ریزی خطی زیر را در نظر بگیرید
که در آن ناحیه شدنی مسئله چند هدفه - 1 - می باشد و ≥ 0 ضرایب وزنی توابع - - می باشد. قضیه -1-2 اگر ∗ جواب بهینه مسئله - 2 - باشد، آنگاه ∗ جواب کارا مسئله - 1 - می باشد.
اثبات. فرض کنیم ∗ جواب کارای مساله - 1 - نباشد، بنابراین وجود دارد ̅ به طوری که برای همه k ها - ∗ - - - ̅ ≤و - ̅ - ≠ - ∗ - . حال با توجه به قیود مساله - 2 - خواهیم داشت. در نتیجه ̅ یک جواب شدنی برای مساله - 2 - و جواب بهینه آن خواهد بود که با فرض مساله در تناقض است.نتیجه – 2-2 اگر مقدار بهینه مساله - 2 - برابر با ∑ =1 - 1 - باشد، آنگاه جواب شدنی 1 یک جواب کارا مسئله - 1 - خواهد بود.
-3 روش پیشنهادی برای حل مسائل چند هدفه هندسی
مسئله چند هدفه ی هندسی - MOGP - به صورت زیر فرموله می شود. که در آن برای = 1, 2, … , و = 1, 2, … , ، ضرایب و برای = 1, 2, … , و = 1, 2, … , ، ضرایب مقادیر مثبت می باشند. برای = 1, 2, … , ، 1, 2, … , = و 1, … , = ، توان های و برای = 1, 2, … , ، = 1, 2, … , و 1, … , = ، توان های اعداد حقیقی هستند. در ادامه فرض کنید 1 یک جواب شدنی از مسئله - 3 - باشد و برای اینکه تشخیص دهیم این نقطه کارا یا ناکار است از مدل - 2 - استفاده می کنیم. مدل - 2 - ، برای مسئله - 3 - به صورت زیر خواهد بود.
