مسئله (۲-۱۲) به مسئله Monge-Kantorovich mass transportation معروف است ]۲۰[. یک تابع غیر منفی، پیوسته، و متقارن است.
اگر باشد، ماتریسی از مرتبه است که دارای برخی خواص برای تقریب مسائل بهینهسازی تصادفی است.
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))
و توزیعهای متناهی به ترتیب متناظر با مجموعه سناریوهای اولیه و مجموعه سناریوهای کاهش یافته میباشند و اگر
| (۲-۱۳) |
توزیع Kantorovich را میتوان به این صورت تعریف کرد]۱۸[:
| (۲-۱۴) |
که این توزیع از طریق تعیین کردن احتمالات همه سناریوهای از دست رفته به نزدیکترین سناریو در مجموعه باقیمانده به دست می آید.
در این پایان نامه بر الگوریتم fast-forward تأکید شده است. این الگوریتم یک فرایند تکرارشونده است که با یک درخت تهی آغاز می شود. در هر تکرار، از مجموعه سناریوهای انتخاب نشده، سناریویی که توزیع Kantorovich را بین درخت کاهش یافته و درخت اصلی حداقل می کند انتخاب می شود. الگوریتم هنگامی به پایان میرسد که یا به تعداد مشخصی از سناریوها دست یافته شود یا توزیع Kantorovich معینی به دست آید]۱۲[.
یک مسئله برنامه ریزی تصادفی را در نظر بگیرید که با [۳۰] نشان داده می شود و شامل متغیر تصادفی است. فرض شده است که با یک مجموعه سناریوی اولیه و مشخص شده است. هدف، جستجوی یک مجموعه سناریوی کاهش یافته است که مناسبی را برای حل نشان دهد.
در الگوریتم fast-forward توصیف شده در ]۱۸[، اختلاف بین دو سناریوی و توسط تابع نشان شده و طبق (۲-۱۳) محاسبه می شود. در مقابل، روش کاهش سناریوی استفاده شده در این پایان نامه تابع را به این صورت تعریف می کند]۱۲[:
| (۲-۱۵) |
که به صورت زیر محاسبه می شود.
-
- مسئله قطعی [۳۱] مرتبط با مسئله برنامه ریزی تصادفی حل می شود. به این معنی که مسئله به گونه ای حل می شود که متغیر تصادفی با مقدار مورد انتظار آن جایگزین می شود. متغیرهای بهینه به دست آمده از حل در مرحله اول با نشان داده میشوند.
-
- برای هر سناریو یک مسئله تک سناریویی، که با نشان داده می شود، مبتنی بر حل می شود که در آن:
(الف) متغیر تصادفی با تحقق آن در سناریوی جایگزین می شود، یعنی، .
(ب) تصمیمات مرحله اول برابر میباشد.
-
- برابر با مقدار بهینه تابع هدف مسئله است.
سپس یک مقدار جدید بین توابع احتمال به این صورت تعریف می شود:
| (۲-۱۶) |
