کد GAMS مسئله تحلیل پوششی داده (DEA).
این کد روی یک مثال عددی هم پیاده شده برای اینکه براتون قابل درک باشه.
تقدیم به دوستان خوبم در گروه🌺❤️🌺

کد GAMS مسئله تحلیل پوششی داده (DEA).
این کد روی یک مثال عددی هم پیاده شده برای اینکه براتون قابل درک باشه.

لازم به توضیح است که مثال عددی 10 واحد تصمیم گیری (DMU) رو دربرمیگره که بر اساس دو پارامتر ورودی و دو پارامتر خروجی (از جنس مثب) ارزیابی میشن و کارایی اونا و ضرایب بهینه وردی (v) , خروجی (u) محاسبه و گزارش میشن. موفق باشید.

در این روش که از روش های حل مسائل MODM به صورت تک جواب هستش، ابتدا مقدار بهینه هر هدف به دست میاد (یعنی چند بار مسئله تک هدفه حل میکنید). بعدش مجموع فاصله اهداف از مقدار بهینه شون رو به عنوان یک هدف جدید تعریف میکنید که میخواید کمینه کنید مقدارش رو. بسته به اینکه شما فاصله رو چطوری تعریف کنید (نرم p چند باشه)، مدلهای مختلفی بدست میاد. در حالت p=1 روش مجموع وزنی سادست و مدل خطی میشه. در p=2 مدل درجه دوم میشه و فاصله اقلیدسی مد نظره (در این حالت میشه مجذور فاصله رو در نظر گرفت که مسئله بهتر حل شه). در p=بینهایت، مسئله minimax میشه یعنی بیشنه انحراف از بهینگی کمینه میشه (در این حالت هم مدل خطی میشه). به طور کلی، هرچی مقدار p افزایش پیدا میکنه حساسیت نسبت به انحرافات بزرگ بیشتر میشه و معمولا مجموع انحرافات افزایش پیدا کنه.

روش Lp-متریک

در این روش که از روش های حل مسائل MODM به صورت تک جواب هستش، ابتدا مقدار بهینه هر هدف به دست میاد (یعنی چند بار مسئله تک هدفه حل میکنید). بعدش مجموع فاصله اهداف از مقدار بهینه شون رو به عنوان یک هدف جدید تعریف میکنید که میخواید کمینه کنید مقدارش رو. بسته به اینکه شما فاصله رو چطوری تعریف کنید (نرم p چند باشه)، مدلهای مختلفی بدست میاد. در حالت p=1 روش مجموع وزنی سادست و مدل خطی میشه. در p=2 مدل درجه دوم میشه و فاصله اقلیدسی مد نظره (در این حالت میشه مجذور فاصله رو در نظر گرفت که مسئله بهتر حل شه). در p=بینهایت، مسئله minimax میشه یعنی بیشنه انحراف از بهینگی کمینه میشه (در این حالت هم مدل خطی میشه). به طور کلی، هرچی مقدار p افزایش پیدا میکنه حساسیت نسبت به انحرافات بزرگ بیشتر میشه و معمولا مجموع انحرافات افزایش پیدا کنه.

پاسخ سوال 3 کنکور دکتری مهندسی صنایع سال 98

سلام دوستان. دو سوال داشتم
یکی اینکه آخرین روش‌های حل مسائل چند هدفه با استفاده از روش حل دقیق رو اطلاع دارید؟
جز روش اپسیلون کانستریت و روش لکسیکوگراف، آیا روش حل دقیق دیگه‌ای هست که جبهه پارتو بده؟
ممنون میشم راهنمایی بفرمایید.

دقیق بودن یک رویکرد حل در مسائل MODM به این معناست که جواب یا جوابهای اون روی جبهه پارتو سراسری قرار میگیره و یا اصطلاحا نامغلوب (nondominated) هستن و پاسخ کارا (Efficient) برای مسئله به حساب میاد.

روش هایی مثل مجموع وزنی، اپسیلون محدودیتو امثالهم رو در ادبیات گرچه دقیق میگن، ولی این زیاد درست نیست و تضمینی نیست که لزوما جواب اونا کارا و نامغلوب باشه (البته کارای ضعیف هست که اثبات داره) .

روش اپسلون محدودیت تکامل یافته عملکرد خوبی داره و معمولا جبهه پارتو اون سراسری هست.
روش مجموع وزنی گرچه جبهه پارتو میده ولی امکان داره سراسری نباشه و مغلوب باشن. مثل روش اپسیلون محدودیت کلاسیک

نرم بینهایت LP متریک یک تک جواب همواره نامغلوب هست

لکسیکوگرافیک تک جواب میده و همیشه نامغلوب هست. لکسیکوگرافیک وزنی گرچه چندین جواب داره ولی تضمینی بر نامغلوب بودن اون نیست


روش TH ترکیب نرم 1 و نرم بینهایت در روش LP متریک هست و بنظر بند نتایج خوبی میده و پیاده سازی ساده ای هم داره

برنامه ریزی آرمانی ، و یا آرمانی فازی هم تقریبا شبیه LP متریک کار میکنن که نرمال شده باشه

#MODM

تبدیل عدد صحیح به باینری
کاربرد: خطی سازی ضرب متغیر عددصحیح در پیوسته
محدودیت: اگر کران بالا متغییر عددصحیح زیاد باشد، انگاه این رویکرد متغیرهای باینری زیادی نیازی دارد و باعث سخت شدن مسئله خطی میشود

خطی سازی ضرب دو متغیر
"اين خطي سازي تقربي هست و بعضا نتايج خوبي حاصل نمي شود"
#Linearization

Outer Approximation

سلام وقت شما بخیر
رویکرد حل لاگرانژ رو چطور باید متوجه بشیم که برای مدلمون کارایی داره یا نه؟

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

1- اساس تکنیک آزادسازی لاگرانژ (LR) بر این است که در مسئله قید سخت وقت وجود داره و حذف اون موجب کارایی میشه. اینکه چه قیدی سخت کننده هست برمیگرده به آزمایش های قبلی، ابتکار شما در تشخیص و ... . لذا اگر در مسئله تون قیدی مثل ظرفیت، بودجه و امثالهم وجود داره میشه روی تکنیک LR حساب باز کرد.

2- تکنیک LR بعضا موجب به تجزیه لاگرانژ (LD) میشه که بر اساس اون مسئله به زیر مسائل ساده تر تجزیه میشه. اگر مسئله تجزیه پذیر هست LR و LD کارایی خوبی دارند.

3- مسئله شما یا مشابه در ادبیات پیش تر توسط LR و LD حل شده باشه و در مقالات چاپ شده در ژورنال های معتبر (دقت کنید ژورنالهای معتبر ) نتیجه گرفته باشن که LR کارا هست، میتونید شما هم استفاده کنید

و ....

مهمترین نکات در رابطه با مدل های دوسطحی (Bi-Level programming) که در در سطح دوم (پیرو/Follower) غیرخطی بودن داره به صورت زیر هست:

1- اول برای اینکه این اطلاعات مفید باشه به طور کلی یاداوری میکنم که این مدل ها معمولا در شرایطی رقابتی یا گیم بین دو سازمان یا واحد تصمیم گیری رخ میده که واحد اصلی (یا اصطلاحا Leader ) باید بهینگی واحد پیرو (یا واحدی که تحت تاثیر تصمیمات اون هست یا همون Follower ) رو در نظر بگیره. این مسائل در ادبیات معمولا به بازی استکلبرگ (Stackelberg Game) هم معروف هست.

2- نکته اول اینه که حتی اگر مدل پیرو خطی هم باشه باز هم شرایط KKT تضمین نمیکنه حتما به جواب بهینه برسید. در واقع یکی از خاصیت های این مدل ها اینا که لزوما جواب بهینه ندارن. در واقع اگر پیرو پاسخ بهینه چندگانه داشته باشه در این صورت هیچ لزومی نداره که لیدر بتونه در شرایط بهینه قرار بگیره.
این رو گفتم که اشتباه نکنیم و فکر کنیم اگر سطح دوم / پیرو خطی هست دیگه راحت یک KKT بزنیم و تمام. البته با فرض اینکه پیرو به هر تصمیم لیدر فقط یک واکنش بهینه داره استفاد از KKT درست هست در حالت خطی. در حالت کلی چه خطی و چه غیرخطی ما فرض مذکور رو داریم(البته این فرض در برخی از مسائل واقعا غیرمنطقی هست ولی در مقالات معمولا این فرض هست)

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

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

5- در مدلهای غیرخطی، در صورتی که مدل پیرو کاملا پیوسته است (متغیر باینری و عددصحیح) نداشته باشه. اولین کاری که بهتره انجام شود، بررسی تحدب است. حالا نه لزوما با ماتریس هسین(Hessian) بلکه هر تکنیک که میتونید اعمال کنید. (مثلا جمع محدب ها محدب هست و توان 2 ها محدب هستن و ...) اگر تحدب برقرار هست با خیال راحت قیود KKT رو جایگزین کنید. باز هم میگم در این حالت هم هنوز اون فرض که عرض کردم رو باید قبول کرده باشیم. پر واضح است که اینجا هم مدل نهایی غیرخطی هست. نکته جالب اینجاست که حتی اگر مدل پیرو تحدب رو داشته باشه و KKT بزنید، باز هم هیچ تضمینی نیست مدل نهایی محدب باشه و اتفاقا معمولا عدم تحدب داره و خود این هم چالش است. حالا اگر مدل عددصحیح و غیره هم داشته باشه که چالش دو چندان هم میشه. البته در این شرایط معمولا خیلی راحت مدل نهایی رو یک Solver مثل BARON و ... داده میشه که حل کنه!!! که مطمئنا این حرکت چندان درست نیست و امکان داره لیدر بشدت در بهینگی محلی قرار بگیره (تازه اگر BARON یا BONMIN و امثالهم حل کنن مدل نهایی رو)

6- حالا اگر 5 مورد بالا را برای شما صدق نمیکنه و یا دنبال راه کارهای دیگری هستید؛ روش پیشنهادی بنده به صورت زیر هست که در کارهای مختلفی با تعامل GAMS و MATLAB و یا CPLEX و یا JAVA و CPLEX قابل پیاده سازی هست.

گام 1) جواب اولیه X برای متغیرهای تصمیم گیری لیدر در نظر گرفته شود.

گام 2) مسئله بهینه سازی پیرو (که یک مدل غیر خطی هست حل شود) با توجه به غیرخطی بودن این مدل موارد زیر پیشنهاد میشه:
* با رویکردهای حل ابتکاری و یا فراابتکاری حل شود و پاسخ نزدیک به بهینه Y (که امکان داره بهینه هم باشه) برای پیرو بدست آورده شود.
* با روش های برنامه ریزی عیرحطی (از جمله روش SQP و یا Trust Region ) پاسخ نزدیک به بهینه Y (که امکان داره بهینه هم باشه) برای پیرو بدست آورده شود.

گام 3) مدل بهینه سازی لیدر، با ثابت کردن تصمیم Y برای پیرو، حل می شود. حالا امکان داره این مدل خطی یاشه که از solverهایی مثل CPLEX و امثالهم استفاده میکنید و سریع X جدید رو برای لیدر بدست میاد. یا امکان داره خود این مدل هم غیرخطی باشه که باز هم دو روش * گام 2 پیشنهاد میشه و یا حتی solver غیرخطی موجود در GAMS و ... .

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

Integer Programming by Prof. Wosley