Skip to content
بازگشت به نتایج جست‌وجو

برنامه‌ریزی خطی تصادفی — بهینه‌سازی تحت عدم قطعیت با پارامترهای تصادفی

معرفی‌شده توسط
George B. Dantzig
سال
1955
نوع
Stochastic optimization model
خانواده
Simulation / optimization

این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید

اندازه قلم

چه کاری انجام می‌دهد؟

برنامه‌ریزی خطی تصادفی (SLP) برنامه‌ریزی خطی کلاسیک را به محیط‌هایی گسترش می‌دهد که در آن‌ها برخی پارامترهای مدل — هزینه‌ها، تقاضاها، در دسترس بودن منابع — نامشخص بوده و به‌عنوان متغیرهای تصادفی مدل‌سازی می‌شوند. با بهینه‌سازی هزینه‌های مورد انتظار بر روی توزیع احتمال سناریوها، SLP تصمیماتی را تولید می‌کند که در طیفی از آینده‌های ممکن، به‌جای یک حالت مفروض از جهان، عملی و تقریباً بهینه باقی می‌مانند.

شهود پشت روش

برنامه‌ریزی خطی کلاسیک فرض می‌کند که هر ضریب به‌دقت مشخص است. در عمل، تقاضای آینده، قیمت‌ها و بازده‌ها نامشخص هستند. SLP این عدم قطعیت را مستقیماً در مدل جاسازی می‌کند: به‌جای بهینه‌سازی برای یک سناریوی ثابت، برنامه‌ریز ابتدا اقدامات مرحله اول را اکنون انجام می‌دهد، سپس مشاهده می‌کند که کدام سناریو تحقق می‌یابد، و در نهایت اقدامات جبرانی را برای رفع هرگونه کمبود یا مازاد انجام می‌دهد. هدف، حداقل کردن کل هزینه مورد انتظار در میان تمام سناریوها است و هزینه‌های تعهد را با هزینه‌های جبرانی مورد انتظار متعادل می‌کند. این امر منطق مدیریتی واقعی را منعکس می‌کند — شما امروز تصمیم می‌گیرید چه چیزی را پیش‌خرید کنید، و فردا می‌توانید با هزینه بیشتر بخرید یا مازاد را با تخفیف بفروشید.

تاریخ

برنامه‌ریزی تصادفی توسط جورج دنتزیگ پیشگام شد، که مدل دو مرحله‌ای را در سال ۱۹۵۵ اندکی پس از توسعه روش سیمپلکس معرفی کرد. بل (۱۹۵۵) به‌طور مستقل ایده‌های مشابهی را پیشنهاد کرد. این حوزه توسط کتاب درسی تأثیرگذار ۱۹۹۷ بیرج و لووکس و با توسعه الگوریتم تجزیه L-شکل (بندر) در دهه‌های ۱۹۶۰–۱۹۸۰ نظام‌مند شد. SLP اکنون مبنای تصمیمات عملیاتی در انرژی، لجستیک و امور مالی در سراسر جهان است.

چه زمانی استفاده شود

زمانی از SLP استفاده کنید که: (۱) پارامترهای کلیدی ورودی واقعاً نامشخص باشند و بتوان آن‌ها را با یک توزیع احتمال یا مجموعه سناریوی تجربی مشخص کرد؛ (۲) تصمیمات باید قبل از رفع عدم قطعیت گرفته شوند، اما اقدامات اصلاحی بعداً با هزینه امکان‌پذیر باشند؛ (۳) هدف و محدودیت‌ها در متغیرهای تصمیم خطی باشند. کاربردهای معمول شامل برنامه‌ریزی تولید، طراحی زنجیره تأمین، اعزام انرژی، و بهینه‌سازی پورتفولیو است. زمانی از SLP استفاده نکنید که: عدم قطعیت را نتوان به‌صورت احتمالی کمی کرد (به‌جای آن از بهینه‌سازی قوی استفاده کنید)؛ رابطه بین تصمیمات و نتایج غیرخطی یا صحیح باشد (از برنامه‌ریزی عدد صحیح تصادفی یا برنامه‌ریزی پویا تصادفی استفاده کنید)؛ مجموعه سناریو برای شمارش بیش از حد بزرگ باشد و تجزیه از نظر محاسباتی غیرممکن باشد؛ یا زمانی که یک تحلیل حساسیت قطعی ساده‌تر برای درک تأثیر عدم قطعیت کافی باشد.

محدودیت‌ها و ملاحظات

  • نیاز به مشخص کردن یک توزیع احتمال یا مجموعه سناریو برای پارامترهای نامشخص دارد — این فرض توزیعی اغلب دشوار است که اعتبارسنجی شود.
  • بار محاسباتی با تعداد سناریوها و متغیرهای مرحله اول به‌سرعت افزایش می‌یابد؛ مسائل بزرگ به تجزیه و منابع قابل توجه حل‌کننده نیاز دارند.
  • به اهداف و محدودیت‌های خطی محدود است؛ ساختارهای غیرخطی یا صحیح به بسط‌هایی نیاز دارند که پیچیدگی بیشتری اضافه می‌کنند.
  • هدف ارزش مورد انتظار ممکن است ریسک‌های دم را نادیده بگیرد؛ انواع ریسک‌گریز (CVaR، محدودیت‌های شانس) سربار مدل‌سازی و محاسباتی را اضافه می‌کنند.

شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.

نقاط قوت

  • عدم قطعیت احتمالی را مستقیماً در بهینه‌سازی لحاظ می‌کند و تصمیماتی تولید می‌کند که در سناریوهای مختلف قوی هستند، نه برای یک آینده مفروض واحد.
  • چارچوب دو مرحله‌ای به‌دقت فرآیندهای واقعی تصمیم‌گیری را منعکس می‌کند: اکنون تعهد کنید، بعداً با جبران تطبیق دهید.
  • ارزش راه‌حل تصادفی (VSS) و EVPI معیارهای اصولی برای انتقال سود مدل‌سازی عدم قطعیت ارائه می‌دهند.
  • توسط الگوریتم‌های بالغ (تجزیه L-شکل / بندر) و حل‌کننده‌های تجاری (CPLEX, Gurobi) به‌خوبی پشتیبانی می‌شود.
  • از طریق تجزیه به مسائل عملی بزرگ مقیاس می‌شود؛ قابل موازی‌سازی در میان سناریوها.

کاربردها

  • برنامه‌ریزی سیستم قدرت الکتریکی و تعهد واحد تحت تولید تجدیدپذیر و تقاضای نامشخص.
  • طراحی شبکه زنجیره تأمین با تقاضای مشتری، زمان تحویل، یا هزینه‌های حمل‌ونقل نامشخص.
  • برنامه‌ریزی محصول و آبیاری تحت باران و قیمت‌های کالای نامشخص.
  • بهینه‌سازی پورتفولیوی مالی با بازده دارایی نامشخص تحت محدودیت‌های بودجه و مقرراتی.
  • مدیریت درآمد و زمان‌بندی خدمه خطوط هوایی تحت تقاضای مسافر نامشخص.
  • پیش‌موقعیت‌سازی لجستیک بشردوستانه از اقلام امدادی قبل از سناریوهای فاجعه نامشخص.

چگونه کار می‌کند

چگونه کار می‌کند

1

مدل دو مرحله‌ای را فرمول‌بندی کنید: متغیرهای مرحله اول x تصمیمات «اینک و اکنون» را که قبل از رفع عدم قطعیت گرفته می‌شوند، نشان می‌دهند؛ هدف، حداقل کردن هزینه مرحله اول c^T x به‌علاوه هزینه جبرانی مورد انتظار E[Q(x,xi)] بر روی بردار تصادفی xi است. محدودیت‌های Ax = b باید برای تصمیمات مرحله اول صرف‌نظر از سناریو برقرار باشند.

فرمول
\min_{x} c^T x + \mathbb{E}_\xi[Q(x, \xi)] \quad \text{s.t. } Ax = b,\; x \geq 0
2

بردار تصادفی xi را از طریق مجموعه‌ای گسسته از سناریوها {xi_1, ..., xi_S} که هر کدام با احتمال p_s (با مجموع ۱) نمایش دهید. سناریوها می‌توانند از داده‌های تاریخی، استنتاج خبرگان، یا نمونه‌گیری مونت کارلو استخراج شوند. کیفیت مجموعه سناریو به‌طور حیاتی کیفیت راه‌حل را تعیین می‌کند؛ تکنیک‌های کاهش سناریو (مانند خوشه‌بندی فاصله واسرشتاین) معمولاً برای قابل‌کنترل نگه داشتن اندازه مسئله به‌کار می‌روند.

3

برای هر سناریوی xi_s، مسئله جبرانی فرعی را حل کنید: با توجه به تصمیم مرحله اول x، ارزان‌ترین اقدام اصلاحی y_s را که W y_s = h(xi_s) - T(xi_s) x و y_s >= 0 را برآورده می‌کند، بیابید. اگر جبران عملی ممکن نباشد، یک جریمه بزرگ (یا عدم امکان عملی) اعمال می‌شود که نشان‌دهنده این است که تصمیم مرحله اول بیش از حد تهاجمی بوده است.

فرمول
Q(x, \xi) = \min_{y} q(\xi)^T y \quad \text{s.t. } W y = h(\xi) - T(\xi) x,\; y \geq 0
4

فرم گسترده کامل (تمام سناریوها به‌عنوان یک LP بزرگ انباشته شده) را برای مجموعه‌های سناریوی کوچک تا متوسط حل کنید، یا برای مجموعه‌های بزرگ از تجزیه بندر (روش L-شکل) استفاده کنید. روش L-شکل به‌طور تکراری برش‌های بهینگی و امکان عملی را به یک مسئله اصلی اضافه می‌کند تا زمانی که همگرایی حاصل شود و از ساختار بلوکی قطری مسائل فرعی سناریو بهره می‌برد.

5

کیفیت راه‌حل را از طریق ارزش راه‌حل تصادفی (VSS) — سود نسبت به راه‌حل میانگین قطعی — و ارزش مورد انتظار اطلاعات کامل (EVPI) — حد بالایی برای ارزش دانش کامل — ارزیابی کنید. تصمیم مرحله اول x*، هزینه کل مورد انتظار، و هزینه‌های جبرانی به‌ازای هر سناریو را برای انتقال پروفایل ریسک به تصمیم‌گیرندگان گزارش دهید.

دام‌های رایج

  • استفاده از سناریوهای کم، منجر به یک راه‌حل بایاس شده می‌شود که در خارج از نمونه عملکرد ضعیفی دارد؛ همیشه با آزمایش سناریوی خارج از نمونه اعتبارسنجی کنید.
  • اشتباه گرفتن راه‌حل قطعی میانگین (قرار دادن مقادیر مورد انتظار) با راه‌حل تصادفی — VSS می‌تواند حتی زمانی که پارامترها پایدار به نظر می‌رسند، بزرگ باشد.
  • نادیده گرفتن امکان عملی جبران: اگر مسئله فرعی مرحله دوم برای برخی سناریوها قابل اجرا نباشد، مدل به محدودیت‌های جبران کامل یا جریمه‌های صریح نیاز دارد.
  • بیش‌برازش به توزیع سناریوی تاریخی بدون آزمایش استرس در برابر سناریوهای دم یا خصمانه، به‌ویژه در کاربردهای زنجیره تأمین یا مالی.
  • درمان برنامه‌ریزی خطی تصادفی به‌عنوان یک جایگزین مستقیم برای بهینه‌سازی قوی، زمانی که تصمیم‌گیرنده در واقعیت نسبت به عدم قطعیت بی‌تفاوت است تا ریسک‌گریز.

پرسش‌های متداول

تفاوت بین برنامه‌ریزی خطی تصادفی و بهینه‌سازی قوی چیست؟

SLP هزینه مورد انتظار را بر روی یک توزیع احتمال سناریوها حداقل می‌کند و اقدامات جبرانی را پس از رفع عدم قطعیت مجاز می‌داند. بهینه‌سازی قوی در عوض بدترین حالت را بر روی یک مجموعه عدم قطعیت بدون فرض توزیع احتمال بهینه‌سازی می‌کند و معمولاً یک راه‌حل ثابت واحد تولید می‌کند که برای همه سناریوها عملی است. SLP زمانی ترجیح داده می‌شود که بتوان احتمالات را تخمین زد؛ بهینه‌سازی قوی زمانی ترجیح داده می‌شود که فقط مجموعه عدم قطعیت شناخته شده باشد یا زمانی که حفاظت از ریسک دم اولویت اصلی باشد.

معمولاً به چند سناریو نیاز است؟

این به ابعاد مسئله و پیچیدگی توزیعی بستگی دارد. ده‌ها تا چند صد سناریو اغلب برای مسائل برنامه‌ریزی کافی هستند اگر به‌طور هوشمندانه تولید شوند (مانند از طریق تطبیق گشتاور یا کاهش سناریو). تقریب میانگین نمونه مبتنی بر مونت کارلو (SAA) ممکن است برای راه‌حل‌های با دقت بالا به هزاران سناریو نیاز داشته باشد، با فواصل اطمینان که همگرایی را هدایت می‌کنند.

آیا SLP می‌تواند تصمیمات صحیح یا دودویی را مدیریت کند؟

مستقیماً نه — متغیرهای صحیح به برنامه‌ریزی عدد صحیح تصادفی (SIP) یا برنامه‌ریزی عدد صحیح مختلط تصادفی (SMIP) نیاز دارند که از نظر محاسباتی به‌طور قابل توجهی دشوارتر هستند. SLP فقط زمانی کاربرد دارد که تمام متغیرهای تصمیم پیوسته باشند.

ارزش راه‌حل تصادفی (VSS) چه چیزی را اندازه‌گیری می‌کند؟

VSS = EEV - RP، که در آن EEV هزینه مورد انتظار راه‌حل قطعی میانگین است که بر روی تمام سناریوها ارزیابی می‌شود، و RP بهینه تصادفی واقعی (مسئله جبرانی) است. یک VSS بالا نشان می‌دهد که نادیده گرفتن عدم قطعیت و استفاده از پارامترهای میانگین منجر به نتایج به‌طور قابل توجهی بدتر می‌شود.

چه حل‌کننده‌ها و نرم‌افزارهایی از برنامه‌ریزی خطی تصادفی پشتیبانی می‌کنند؟

حل‌کننده‌های تجاری مانند CPLEX و Gurobi می‌توانند فرم گسترده را مستقیماً حل کنند. چارچوب‌های منبع باز شامل خواننده‌های فرمت SMPS، PySP (بخشی از Pyomo)، و بسته Julia به نام StochasticPrograms.jl هستند. برای مسائل در مقیاس بزرگ، پیاده‌سازی‌های سفارشی تجزیه L-شکل در تحقیقات و صنعت رایج هستند.

روش‌های مرتبط

منابع

  1. Dantzig, G. B., & Madansky, A. (1961). On the solution of two-stage linear programs under uncertainty. Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, 1, 165–176.

    باز کردن مرجع انتشار
    کپی شد.
  2. Birge, J. R., & Louveaux, F. (1997). Introduction to Stochastic Programming. Springer, New York.

    شابک: 9780387982175
    کپی شد.