Stochastic programming — برنامه‌ریزی تصادفی

برنامه‌ریزی تصادفی (انگلیسی: stochastic programming) — شاخه‌ای از برنامه‌ریزی ریاضی است که مدل‌ها و روش‌های حل مسائل بهینه‌سازی را در شرایط عدم قطعیت توسعه می‌دهد؛ شرایطی که در آن برخی پارامترهای مدل به‌طور دقیق مشخص نیستند، بلکه به‌صورت متغیرهای تصادفی با توزیع‌های احتمالاتی معلوم یا تخمینی ارائه می‌شوند.

برخلاف مسائل قطعی که در آن‌ها همه داده‌ها ثابت و معین فرض می‌شوند، برنامه‌ریزی تصادفی هدف دارد راه‌حلی (یا سیاست تصمیم‌گیری) بیابد که به معنایی آماری بهینه باشد. در بیشتر موارد این به معنای کمینه‌سازی یا بیشینه‌سازی امید ریاضی تابع هدف است. ایده اصلی یافتن چنان سیاست تصمیم‌گیری است که «به‌طور میانگین» برای تمام تحقق‌های ممکن پارامترهای تصادفی بهترین باشد؛ این امر به‌ویژه برای مسائلی که تصمیمات به‌طور مکرر در شرایط مشابه اتخاذ می‌شوند اهمیت دارد (مانند مدیریت موجودی یا سیستم‌های انرژی).

صورت‌بندی ریاضی مسئله

به‌طور کلی مسئله برنامه‌ریزی تصادفی را می‌توان به شکل زیر فرمول‌بندی کرد: $\underset{x\in X}{\min }\mathbb{𝔼}[f(x,\xi )]$ که در آن:

• $x$ — بردار متغیرهای کنترلی (تصمیمات) که باید تعیین شوند.
• $X$ — مجموعه راه‌حل‌های مجاز برای $x$، که با قیود قطعی تعریف می‌شود.
• $\xi$ — بردار تصادفی نمایانگر پارامترهای نامعین مسئله (مثلاً تقاضا، قیمت‌ها، شرایط آب‌وهوایی).
• $f(x,\xi )$ — تابع هدف که مقدار آن هم به تصمیم اتخاذشده $x$ و هم به تحقق بردار تصادفی $\xi$ بستگی دارد.
• $\mathbb{𝔼}[\cdot ]$ — عملگر امید ریاضی که بر اساس توزیع احتمال بردار $\xi$ محاسبه می‌شود.

مهم‌ترین اصل زیربنایی مدل‌های تصادفی چند مرحله‌ای، اصل عدم پیش‌بینی (انگلیسی: non-anticipativity principle) است. این اصل بیان می‌کند که تصمیمات اتخاذشده در هر مرحله تنها می‌توانند به اطلاعات موجود تا آن لحظه وابسته باشند و نمی‌توانند «به آینده نگاه کنند».

مسئله دو مرحله‌ای با حق جبران

رایج‌ترین مدل، مسئله تصادفی دو مرحله‌ای با حق جبران (انگلیسی: two-stage stochastic program with recourse) است. فرآیند تصمیم‌گیری به دو مرحله تقسیم می‌شود:

1. مرحله اول: تصمیم «اینجا و اکنون» (here-and-now) اتخاذ می‌شود — بردار $x$ تعیین می‌گردد. این تصمیم باید پیش از آنکه تحقق مشخص بردار تصادفی $\xi$ مشخص شود، اتخاذ گردد.
2. مرحله دوم: پس از وقوع رویداد تصادفی، تصمیم اصلاحی یا جبرانی (recourse decision) — بردار $y(\xi )$ — اتخاذ می‌شود که هدف آن کمینه‌سازی پیامدهای منفی یا بهره‌برداری از فرصت‌های مطلوب ناشی از ترکیب تصمیم مرحله اول $x$ و نتیجه $\xi$ است.

مسئله برنامه‌ریزی خطی تصادفی دو مرحله‌ای به‌صورت ریاضی به شرح زیر فرمول‌بندی می‌شود: $\underset{x\in {\mathbb{ℝ}}^{n_1}}{\min }\{c^{T}x+{\mathbb{𝔼}}_{\xi }[Q(x,\xi )]\}$ با قیود مرحله اول: $Ax=b,x\ge 0$. در اینجا $Q(x,\xi )$ — تابع جبران (recourse function) است که مقدار بهینه مسئله مرحله دوم را نشان می‌دهد: $Q(x,\xi )=\underset{y\in {\mathbb{ℝ}}^{n_2}}{\min }\{q(\xi {)}^{T}y\mid T(\xi )x+Wy=h(\xi ),y\ge 0\}$ که در آن $\xi$ — بردار تصادفی شامل پارامترهای $q(\xi ),T(\xi )$ و $h(\xi )$ است؛ و $c,A,b$ و $W$ پارامترهای قطعی هستند.

ویژگی‌ها و قضایای کلیدی

• محدب بودن: یکی از نتایج بنیادی نظریه این است که برای مسئله برنامه‌ریزی خطی تصادفی دو مرحله‌ای، تابع جبران مورد انتظار $Q(x)={\mathbb{𝔼}}_{\xi }[Q(x,\xi )]$ یک تابع محدب است. این ویژگی اهمیت فوق‌العاده‌ای دارد، زیرا تضمین می‌کند که مسئله کلی مرحله اول یک مسئله برنامه‌ریزی محدب است که برای آن روش‌های کارآمدی وجود دارد و بهینه سراسری با بهینه محلی یکی است.
• معادل قطعی: اگر بردار تصادفی $\xi$ تعداد محدودی از تحقق‌های ممکن (سناریو) ${\xi }_1,\dots ,{\xi }_K$ با احتمالات $p_1,\dots ,p_K$ داشته باشد، مسئله برنامه‌ریزی تصادفی را می‌توان به‌صورت یک مسئله بزرگ بهینه‌سازی قطعی بازنویسی کرد. در این حالت امید ریاضی با یک جمع وزنی بر روی تمام سناریوها جایگزین می‌شود. با این حال اندازه این مسئله به‌طور خطی با تعداد سناریوها رشد می‌کند که به «لعنت ابعاد» منجر می‌شود و این رویکرد را برای تعداد زیادی سناریو از نظر محاسباتی غیرقابل‌حل می‌سازد.

مقایسه با بهینه‌سازی استوار

برنامه‌ریزی تصادفی یکی از چند رویکرد بهینه‌سازی در شرایط عدم قطعیت است. تفاوت کلیدی آن با بهینه‌سازی استوار در شیوه مدل‌سازی عدم قطعیت و معیار بهینگی نهفته است.

مقایسه رویکردهای بهینه‌سازی در شرایط عدم قطعیت

معیار	بهینه‌سازی تصادفی	بهینه‌سازی استوار
نمایش عدم قطعیت	پارامترها متغیرهای تصادفی با توزیع احتمالاتی معلوم هستند	پارامترها به یک مجموعه عدم قطعیت داده‌شده تعلق دارند و نیازی به توزیع نیست
معیار بهینگی	بهینه‌سازی امید ریاضی تابع هدف	بهینه‌سازی در بدترین سناریو (minimax)
ماهیت راه‌حل	سیاستی که «به‌طور میانگین» بهینه است، ممکن است برای سناریوهای نادر غیرمجاز باشد	راه‌حلی که برای تمام تحقق‌ها تضمیناً مجاز است؛ ممکن است محافظه‌کارانه باشد

مثال‌ها

• مسئله روزنامه‌فروش (انگلیسی: newsvendor problem): مسئله کلاسیک مدیریت موجودی که در آن فروشنده باید تصمیم بگیرد چه مقدار کالا تهیه کند، بدون اینکه از تقاضای دقیق آینده آگاه باشد. راه‌حل میان ریسک زیان از مازاد و ریسک از دست دادن سود به‌دلیل کمبود تعادل برقرار می‌کند.
• مسئله کشاورز: کشاورز تصمیم می‌گیرد چه مقدار از زمین را در مساحت کل به کشت محصولات مختلف اختصاص دهد، بدون اینکه از آب‌وهوای آینده که بر عملکرد محصول تأثیر می‌گذارد آگاه باشد. پس از آنکه آب‌وهوا مشخص شد، کشاورز می‌تواند اقدامات اصلاحی انجام دهد (مثلاً مازاد را بفروشد یا محصول کم‌آمده را از بازار خریداری کند).

همچنین ببینید

• برنامه‌ریزی ریاضی
• تحقیق در عملیات
• بهینه‌سازی استوار
• برنامه‌ریزی پویا
• نظریه کنترل

یادداشت‌ها

</references>