چکیده:
در این مقاله برای نخستین بار معکوس مسئله بهینهسازی 2- میانه پشتیبان بررسی شده است. در این مسئله تعدادی نقطه، مشتری در نظر گرفته میشوند و هدف این است که با تغییر پارامترهای مسئله، دو نقطه از پیش تعیین شده بهسمت 2- میانه پشتیبان شدن برود. ابتدا مسائل معکوس (نوع محدودیت بودجهای و نوع حداقل هزینه) 2- میانه پشتیبان درحالت گسسته برای گرافهای عمومی مدلسازی ریاضی میشود. سپس درحالتیکه گراف مدنظر درخت باشد، آنها به مسئله برنامهریزی خطی تبدیل میشوند. همچنین درحالت پیوسته برای مسئله معکوس نوع محدودیت بودجهای 2- میانه پشتیبان (با تغییر در مختصات نقاط) مدل ریاضی ارائه میشود. باتوجهبه NP-سختبودن مسئله، مسئله با الگوریتمهای فرا ابتکاری ازدحام ذرات(PSO) و الگوریتم بهبودیافته ازدحام ذرات(IPSP)، حل میشود. در نهات نتایج در حالات مختلف بررسی میشود.
خلاصه ماشینی:
مسائل معکوس مکان یابی تسهیلات ٢- میانه پشتیبان با تغییر طول یال ها و وزن رئوس روی درخت و تغییر مختصات نقاط در صفحه مرتضی نظری ١، جعفر فتحعلی *٢ ، مصطفی نظری ٣، سید مجتبی واردی کولایی ٤ ١- دانشجوی دکتری، دانشکده ریاضی، دانشگاه صنعتی شاهرود، شاهرود، ایران ، mnazari_math@shahroodut.
گلوی ٢٣ (٢٠٠٨)، مسئلۀ ١- میانه معکوس نوع حداقل هزینه را با تغییـرات وزن رأسـی روی درخـت (کـه قـبلا بورکارد و همکارانش در مقاله بورکارد و همکاران ٢٤ (٢٠٠٤)ارائه داده بودند) به صورت مدل کوله پشتی مـدل سـازی کرد و نشان داد که این مسئله در زمان خطی حل شدنی است .
درادامه در قسمت ٥ مقاله ، معکوس نوع محـدودیت بودجـه ای مسـئلۀ ٢-میانـه پشـتیبان درفضای پیوسته و با تغییر در مختصات نقاط ، مدل سازی ریاضی میشـود و بـاتوجـه بـه NP- سـخت بـودن مسـئلۀ مذکور، روش های فرا ابتکاری ازدحام ذرات (PSO) و الگـوریتم بهبودیافتـۀ ازدحـام ذرات (IPSO)، بـرای حـل آن پیشنهاد شده است .
مسئلۀ بهینه سازی بالا، روی گراف هـای کلـی از نوع مسائل NP- سخت است ؛ بنابراین این مسئله برای گراف های خاصی مانند درخت ها بررسی شده اند.
در این مسئله هدف این است که با کمتـرین n هزینۀ ممکن از تغییر طول یال های گـراف (یعنـی حـداقل کـردن ) ( )cixi c xeدو رأس دلخـواه m١ و m٢، _ _ i1 تبدیل به ٢-میانه پشتیبان شوند؛ بنابراین مسئلۀ BIMP٢ با تغییر در طول یال به صورت زیر مدل میشود.
همچنین درحالت پیوسته نیز برای مسئلۀ معکوس نوع محدودیت بودجـه ای ٢- میانه پشتیبان (با تغییر در مختصات نقاط ) مدل ریاضی ارائه میشود.