Forwarded from 𝙰𝚕𝚒 𝙿𝚊𝚙𝚒
VRP_AliPapi_SingleDepot.gms
1.5 KB
Forwarded from 𝙰𝚕𝚒 𝙿𝚊𝚙𝚒
دو کد بسیار کارا برای حل مسئله مسیریابی وسایل نقلیه (VRP) 👆🏻👆🏻
یک مزیت بسیار خوب که دو کد فوق دارند، اینه که با توجه به همگون بودن وسایل نقلیه، اندیس وسیله نقلیه تعریف نشده که بشدت موجب کارایی کدها در عمل شده.
برای استفاده همه دوستان 🌷
یک مزیت بسیار خوب که دو کد فوق دارند، اینه که با توجه به همگون بودن وسایل نقلیه، اندیس وسیله نقلیه تعریف نشده که بشدت موجب کارایی کدها در عمل شده.
برای استفاده همه دوستان 🌷
Forwarded from 𝙰𝚕𝚒 𝙿𝚊𝚙𝚒
Optimyar | آپتیمیار
مدل سویستر.pdf
دقت کنید که روش Soyster بسیار محافظه کار هست و اصطلاحا Conservatism بالایی داره که در عمل چندان مناسب نیست. رویکردهای مختلف Robust Optimization در کتاب Ben-Tal و یا رویکرد Bertsimas & Sim کاراتر هستن و در مقالات متعددی مورد استفاده قرار گرفتن
Forwarded from 𝙰𝚕𝚒 𝙿𝚊𝚙𝚒
توضیحاتی که نوشتید کاملا درست هستید. فقط برای محاسبه EVPI ی خورده اشتباه کردید و اونجا هم که گفتید روش های حل میشن EV و WS اشتباه گفتید. میشن EV و SP . چون اصلا WS روش حل نیست بلکه یک رویه است که مثلا شما بهترین وضعیت برای هر سناریو رو بدست میارید.
اول دقت کنید برای حل یک مسئله بهینه سازی تحت شرایط عدم قطعیت سناریومحور دو رویکرد اصلی وجود داره.
یک رویکرد EV یا همون مقدار انتظاری که گفتید
و دوم رویکرد برنامه ریزی تصادفی سناریومحور (یا همون SP)
حالا برای ارزیابی پاسخ رویکرد SP شما دو تا حالت زیر رو میتونید انجام بدید.
1- معیار VSS رو به صورت زیر محاسبه کنید
VSS= Z_SP - Z_EV
و در مسئله min این مقدار همواره بیشتر یا مساوی 0 است. هرچی بیشتر باشه نشون میده رویکرد تصادفی با ارزش تر است.
2- مقدار بهترین حالت هر سناریو که اصطلاحا Waite and See یا WS میگن رو برای هر سناریو محاسبه کنید و بهترین مقدار میانگین رو بدست بیارید. حالا ارزش اطلاعات کامل رو به یکی از دو صورت زیر محاسبه کنید
حالت الف)
EVPI= Z_SP - Z_WS
حالت ب)
EVPI= Z_EV - Z_WS
که هرچه این مقادیر بیشتر باشن نشون میده که داشتن اطلاعات در مورد اینکه دقیقا کدوم سناریو میخواد رخ بده، باارزش تر است. من خودم شخصا معیار ب رو بیشتر ترجیح میدم ولی در کتب و مقالات معمولا همون الف رو مینویسن.
دیگه اینا رو از این بیشتر و بهتر نمیشه در گروه توضیح داد 😉
اول دقت کنید برای حل یک مسئله بهینه سازی تحت شرایط عدم قطعیت سناریومحور دو رویکرد اصلی وجود داره.
یک رویکرد EV یا همون مقدار انتظاری که گفتید
و دوم رویکرد برنامه ریزی تصادفی سناریومحور (یا همون SP)
حالا برای ارزیابی پاسخ رویکرد SP شما دو تا حالت زیر رو میتونید انجام بدید.
1- معیار VSS رو به صورت زیر محاسبه کنید
VSS= Z_SP - Z_EV
و در مسئله min این مقدار همواره بیشتر یا مساوی 0 است. هرچی بیشتر باشه نشون میده رویکرد تصادفی با ارزش تر است.
2- مقدار بهترین حالت هر سناریو که اصطلاحا Waite and See یا WS میگن رو برای هر سناریو محاسبه کنید و بهترین مقدار میانگین رو بدست بیارید. حالا ارزش اطلاعات کامل رو به یکی از دو صورت زیر محاسبه کنید
حالت الف)
EVPI= Z_SP - Z_WS
حالت ب)
EVPI= Z_EV - Z_WS
که هرچه این مقادیر بیشتر باشن نشون میده که داشتن اطلاعات در مورد اینکه دقیقا کدوم سناریو میخواد رخ بده، باارزش تر است. من خودم شخصا معیار ب رو بیشتر ترجیح میدم ولی در کتب و مقالات معمولا همون الف رو مینویسن.
دیگه اینا رو از این بیشتر و بهتر نمیشه در گروه توضیح داد 😉
Forwarded from 𝙰𝚕𝚒 𝙿𝚊𝚙𝚒
الگوریتم تجزیه بندرز (Benders Decomposition) کلاسیک برای مسائلی MILP ارائه شده و تجزیه بر اساس نوع متغیرها صورت میگیره و مستلزم اونه که یک زیر مسئله کاملا پیوسته باشه. اما در توسعه الگوریتم بندرز، تجزیه میتونه بر اساس ساختار ماتریس فتی نیز صورت بگیره. این حالت دوم میتونه برای هر نوع مسئله باشه. در حالتی که مسئله کاملا پیوسته باشد به الگوریتم L-Shaped معروف هست. برای مسائل کاملا عدد صحیح هم حالت دوم مستلزم تجزیه پذیر بودن مسئله بر اساس ساختار ضرایب/ماتریس فنی هست. به مثال زیر توجه کنید
min c1x1 + c2x2 + c3x3
s.t
Ax1 + Bx2<=b
Vx3 + Kx2<=u
x1 , x2 , x3 are integer
در این مسئله، ساختار ضرایب فنی به صورتی است که مسئله نسبت به متغیر x2 کاملا تجزیه پذیر است و به دو زیر مسئله کوچک تر تجزیه میشه. این نوع تجزیه رو هم چون روی متغیر صورت میگیره به افتخار پروفسور بندرز، تجزیه بندرز میگن (هرچند با فرم کلاسیک تجزیه بندرز فرق داره) دقت کنید در این مثال که عرض کردم اگر فرض کنید بعد دسته متغیرهای x1 و x3 زیاد باشه و بعد متغیر x2 کم باشه، واقعا تجزیه میتونه بسیار کارآمد باشه. یک یاداوری هم کنم اینجا اگر متغیرها همگی پیوسته بودن به تجزیه L-shaped میرسیدیم که اون هم الهام گرفته از تجزیه بندرز است و چند سال بعد از مقاله بندرز چاپ شده.
کتاب پروفسور conejo در گروه قرار داد شده که پیشنهاد میکنم مطالعه کنید.
min c1x1 + c2x2 + c3x3
s.t
Ax1 + Bx2<=b
Vx3 + Kx2<=u
x1 , x2 , x3 are integer
در این مسئله، ساختار ضرایب فنی به صورتی است که مسئله نسبت به متغیر x2 کاملا تجزیه پذیر است و به دو زیر مسئله کوچک تر تجزیه میشه. این نوع تجزیه رو هم چون روی متغیر صورت میگیره به افتخار پروفسور بندرز، تجزیه بندرز میگن (هرچند با فرم کلاسیک تجزیه بندرز فرق داره) دقت کنید در این مثال که عرض کردم اگر فرض کنید بعد دسته متغیرهای x1 و x3 زیاد باشه و بعد متغیر x2 کم باشه، واقعا تجزیه میتونه بسیار کارآمد باشه. یک یاداوری هم کنم اینجا اگر متغیرها همگی پیوسته بودن به تجزیه L-shaped میرسیدیم که اون هم الهام گرفته از تجزیه بندرز است و چند سال بعد از مقاله بندرز چاپ شده.
کتاب پروفسور conejo در گروه قرار داد شده که پیشنهاد میکنم مطالعه کنید.
Forwarded from 𝙰𝚕𝚒 𝙿𝚊𝚙𝚒
دو مقاله زیر رو مطالعه کنید.
مقاله اول نوشته پروفسر روکافلر و پروفسر یورسایف هست که در سال 1999 برای اولین بار به ضعف VaR اشاره مکینن و یک معیار جدید به اسم CVaR رو معرفی میکنن که ارزش انتظاری مقادیری کمتر از VaR (برای حالت سود) و مقادیر بیشتر از VaR (برای حالت زیان) هست.
مقاله دوم هم که دقیقا در سال 1999 توسط پروفسر آرتزنر و همکارنشون چاپ شده، به معرفی TVaR میپردازه و گرچه در بیان کمی متفاوت هستن، ولی در مفهوم و فرمولاسیون دقیقا همون CVaR هست.
"بنظر بنده اگر تغییر جزیی هم هست مرتبط با استنباط متفاوت خوانندگان و یا نویسندگان مقالات بعدی هست (این دو مقاله بیش از 15هزار ارجاع دارند)". وگرنه مفهوم TVaR و CVaR بر اساس مطالعه بنده از هر دو مقاله، کاملا یکسان هست.
👇🏻👇🏻
مقاله اول نوشته پروفسر روکافلر و پروفسر یورسایف هست که در سال 1999 برای اولین بار به ضعف VaR اشاره مکینن و یک معیار جدید به اسم CVaR رو معرفی میکنن که ارزش انتظاری مقادیری کمتر از VaR (برای حالت سود) و مقادیر بیشتر از VaR (برای حالت زیان) هست.
مقاله دوم هم که دقیقا در سال 1999 توسط پروفسر آرتزنر و همکارنشون چاپ شده، به معرفی TVaR میپردازه و گرچه در بیان کمی متفاوت هستن، ولی در مفهوم و فرمولاسیون دقیقا همون CVaR هست.
"بنظر بنده اگر تغییر جزیی هم هست مرتبط با استنباط متفاوت خوانندگان و یا نویسندگان مقالات بعدی هست (این دو مقاله بیش از 15هزار ارجاع دارند)". وگرنه مفهوم TVaR و CVaR بر اساس مطالعه بنده از هر دو مقاله، کاملا یکسان هست.
👇🏻👇🏻
Forwarded from 𝙰𝚕𝚒 𝙿𝚊𝚙𝚒
Optimyar | آپتیمیار
دو مقاله زیر رو مطالعه کنید. مقاله اول نوشته پروفسر روکافلر و پروفسر یورسایف هست که در سال 1999 برای اولین بار به ضعف VaR اشاره مکینن و یک معیار جدید به اسم CVaR رو معرفی میکنن که ارزش انتظاری مقادیری کمتر از VaR (برای حالت سود) و مقادیر بیشتر از VaR (برای…
CVaR.pdf
359.3 KB
Forwarded from 𝙰𝚕𝚒 𝙿𝚊𝚙𝚒
Optimyar | آپتیمیار
دو مقاله زیر رو مطالعه کنید. مقاله اول نوشته پروفسر روکافلر و پروفسر یورسایف هست که در سال 1999 برای اولین بار به ضعف VaR اشاره مکینن و یک معیار جدید به اسم CVaR رو معرفی میکنن که ارزش انتظاری مقادیری کمتر از VaR (برای حالت سود) و مقادیر بیشتر از VaR (برای…
TVaR.pdf
152.4 KB
Forwarded from 𝙰𝚕𝚒 𝙿𝚊𝚙𝚒
در مورد ترجمه و مفهوم واژه ها:
1- Stochastic Programming (SP)
با معنای برنامه ریزی تصادفی که بعضا بهش برنامهریزی احتمالی (Probabilistic Programming) هم گفته میشه؛ دو شاخه پیوسته و گسسته داره که عمدتا SP بر شاخه گسسته و سناریومحور تمرکز داره و شاخه پیوسته به CCP یا برنامه ریزی قیود شانسی معروف هست. SP در صورتی که پارامترهای غیرقطعی یا شرایط مختلف حاکم بر سیستم/مدل به صورت چندین سناریو قابل بیان باشن استفاده میشه و CCP معمولا برای بیان شانس/احتمال یا درجه اطمینان قیود مورد استفاده قرار میگیره.
2- Posibilistic Programing (or Fuzzy Posibilistic Programming)
با ترجمه برنامه ریزی امکانی. از شاخه های برنامه ریزی ریاضی هست و در مواقعی استفاده میشه داده های غیرقطعی یک مسئله بهینهسازی به صورت اعداد/متغیرهای فازی با تابع عضویت مشخص (معمولا مثلثی و ذوزنقه ای یا گاوسین) بیان میشه، و برای اندازه گیری درجه امکان یا اطمینان برقراری قیود از اندازه/measure امکان استفاده میشه.
لازم به توضیح است که بعضا اندازههای دیگری مثل necessity و یا credibility هم مورد استفاده قرار میگیره. در کل اگر بخوایم یک اسم کامل و درست تر به این شاخه بهینهسازی تحت شرایط عدمقطعیت بگیم، بهتره بگیم Fuzzy Chance Constraint Programming که اندازه سنجش شانس میتونه possibility یا necessity و یا هر measure دیگری باشه.
3- Posibilistic-Stochastic Programming
اگر در یک مدل تصادفی سناریومحور، داده های فازی هم وجود داشته باشه، این رویکرد مورد استفاده قرار میگره. مثلا شما فرض کنید که تقاضا به صورت سه سناریو بیان میشه و مقدار تقاضا در هر سناریو دقیقا مشخص نیست و به صورت یک عدد فازی بیان میشه.
———————————————————————————
رویکرد Robust Fuzzy Stochasti Programmingc که در سال 2018 چاپ شده (مقاله اش رو قبلا در گروه قرار دادم)، یک رویکرد ترکیبی/hybrid ساده و کاربردی هست که رویکرد برنامه ریزی امکانی استوار و رویکرد برنامه ریزی تصادفی استوار پروفسر مالوی. این میشه مورد 3 که عرض کردم ولی مفاهیم استواری بهینگی و شدنی بودن (Optimality and Feasibility Robustness) هم در نظر گرفته میشه.
فرض کنید که ریسک های اختلالی محتمل برای یک سیستم یا شبکه زنجیره تامین و رو صورت چندین سناریو بیان کردید. در هر وضعیت/سناریو، ریسکهای عملیاتی مرتبط با عدمقطعیت برخی از دادهها هستند که مقدارشون قطعی نیست و به صورت اعداد فازی بیان میشه.برای برنامه ریزی بهینه در این سیستم، رویکرد RFSP مناسب هست.
1- Stochastic Programming (SP)
با معنای برنامه ریزی تصادفی که بعضا بهش برنامهریزی احتمالی (Probabilistic Programming) هم گفته میشه؛ دو شاخه پیوسته و گسسته داره که عمدتا SP بر شاخه گسسته و سناریومحور تمرکز داره و شاخه پیوسته به CCP یا برنامه ریزی قیود شانسی معروف هست. SP در صورتی که پارامترهای غیرقطعی یا شرایط مختلف حاکم بر سیستم/مدل به صورت چندین سناریو قابل بیان باشن استفاده میشه و CCP معمولا برای بیان شانس/احتمال یا درجه اطمینان قیود مورد استفاده قرار میگیره.
2- Posibilistic Programing (or Fuzzy Posibilistic Programming)
با ترجمه برنامه ریزی امکانی. از شاخه های برنامه ریزی ریاضی هست و در مواقعی استفاده میشه داده های غیرقطعی یک مسئله بهینهسازی به صورت اعداد/متغیرهای فازی با تابع عضویت مشخص (معمولا مثلثی و ذوزنقه ای یا گاوسین) بیان میشه، و برای اندازه گیری درجه امکان یا اطمینان برقراری قیود از اندازه/measure امکان استفاده میشه.
لازم به توضیح است که بعضا اندازههای دیگری مثل necessity و یا credibility هم مورد استفاده قرار میگیره. در کل اگر بخوایم یک اسم کامل و درست تر به این شاخه بهینهسازی تحت شرایط عدمقطعیت بگیم، بهتره بگیم Fuzzy Chance Constraint Programming که اندازه سنجش شانس میتونه possibility یا necessity و یا هر measure دیگری باشه.
3- Posibilistic-Stochastic Programming
اگر در یک مدل تصادفی سناریومحور، داده های فازی هم وجود داشته باشه، این رویکرد مورد استفاده قرار میگره. مثلا شما فرض کنید که تقاضا به صورت سه سناریو بیان میشه و مقدار تقاضا در هر سناریو دقیقا مشخص نیست و به صورت یک عدد فازی بیان میشه.
———————————————————————————
رویکرد Robust Fuzzy Stochasti Programmingc که در سال 2018 چاپ شده (مقاله اش رو قبلا در گروه قرار دادم)، یک رویکرد ترکیبی/hybrid ساده و کاربردی هست که رویکرد برنامه ریزی امکانی استوار و رویکرد برنامه ریزی تصادفی استوار پروفسر مالوی. این میشه مورد 3 که عرض کردم ولی مفاهیم استواری بهینگی و شدنی بودن (Optimality and Feasibility Robustness) هم در نظر گرفته میشه.
فرض کنید که ریسک های اختلالی محتمل برای یک سیستم یا شبکه زنجیره تامین و رو صورت چندین سناریو بیان کردید. در هر وضعیت/سناریو، ریسکهای عملیاتی مرتبط با عدمقطعیت برخی از دادهها هستند که مقدارشون قطعی نیست و به صورت اعداد فازی بیان میشه.برای برنامه ریزی بهینه در این سیستم، رویکرد RFSP مناسب هست.
👍1
Forwarded from 𝙰𝚕𝚒 𝙿𝚊𝚙𝚒
در بهینهسازی و برنامهریزی ریاضی، واژه tractable رو میشه ترجمه کرد حلشدنی، حلپذیر، و یا محاسبهشدنی و هر واژه دیگری که مفهوم حل شدن یک مسئله یا عدم پیچیدگی یک الگوریتم رو بده.
مفهومش یعنی اینکه بر پیچیدگی محاسباتی مسئله افزوده نمیشه و قابل حل توسط الگوریتم با مرتبه محاسباتی چندجملهای هست . مثل مسائل برنامهریزی خطی با الگوریتم حل سیمپلکس یا نقطه درونی
به عنوان یک مثال دیگر، میگیم مدلهای بهینهسازی استوار محدب همگی tractable هستن چون یا خطی هستن یا توسط برنامهریزی مخروطی و روش نقطه درونی قابل حل در زمان چندجملهای هستند.
#tractable
#tractability
#حلشدنی
#پیچیدگی
مفهومش یعنی اینکه بر پیچیدگی محاسباتی مسئله افزوده نمیشه و قابل حل توسط الگوریتم با مرتبه محاسباتی چندجملهای هست . مثل مسائل برنامهریزی خطی با الگوریتم حل سیمپلکس یا نقطه درونی
به عنوان یک مثال دیگر، میگیم مدلهای بهینهسازی استوار محدب همگی tractable هستن چون یا خطی هستن یا توسط برنامهریزی مخروطی و روش نقطه درونی قابل حل در زمان چندجملهای هستند.
#tractable
#tractability
#حلشدنی
#پیچیدگی
Forwarded from 𝙰𝚕𝚒 𝙿𝚊𝚙𝚒