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

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

معرفی‌شده توسط
Birge, J. R.; Louveaux, F.; Sen, S.
سال
1990s–2000s
نوع
Stochastic optimization model
خانواده
Simulation / optimization

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

اندازه قلم

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

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

شهود پشت روش

بسیاری از مسائل برنامه‌ریزی واقعی، انتخاب‌های بله/خیر یا اعداد صحیح را اجبار می‌کنند — ساخت یک تأسیسات یا عدم ساخت آن، تخصیص تعداد صحیحی از وسایل نقلیه — اما آینده نامشخص است. SMIP با در نظر گرفتن مجموعه‌ای از سناریوهای محتمل آینده و انتخاب تعهدات مرحله اول (قبل از آشکار شدن عدم قطعیت) که هزینه مورد انتظار را در تمام سناریوها به حداقل می‌رساند یا سود مورد انتظار را به حداکثر می‌رساند، این موضوع را رسمی می‌کند. محدودیت‌های صحیح، مسئله را از نظر ترکیبیاتی دشوار می‌کنند، اما الگوریتم‌های تجزیه از ساختار سناریو برای قابل حل کردن نمونه‌های بزرگ بهره می‌برند.

تاریخ

برنامه‌ریزی تصادفی با Dantzig (1955) و Beale (1955) به عنوان LP دو مرحله‌ای آغاز شد. توسعه عدد صحیح مختلط به طور برجسته در دهه 1990 با انطباق‌های روش L-شکل برای جبران صحیح توسط Laporte و Louveaux (1993) و درمان جامع در کتاب درسی Birge و Louveaux (1997) ظهور کرد. الگوریتم C3/D2 از Sen و Higle (2005) حل‌کننده‌های مقیاس‌پذیر SMIP را پیش برد و این حوزه را به عنوان یک رشته بالغ در تحقیقات عملیاتی تثبیت کرد.

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

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

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

  • پیچیدگی محاسباتی به صورت ترکیبیاتی با تعداد سناریوها و متغیرهای صحیح رشد می‌کند؛ نمونه‌های بزرگ ممکن است بدون تجزیه مؤثر غیرقابل حل باشند.
  • نیازمند توزیع‌های احتمال صریح یا مجموعه‌های سناریو است — مدل‌های عدم قطعیت نادرست مشخص شده منجر به راه‌حل‌هایی می‌شوند که در خارج از نمونه عملکرد ضعیفی دارند.
  • فرمول‌بندی‌های دو مرحله‌ای ممکن است تصمیمات چند دوره‌ای را بیش از حد ساده کنند؛ SMIP چند مرحله‌ای به طور قابل توجهی دشوارتر است.
  • جبران صحیح مرحله دوم، محدب بودن مورد بهره‌برداری توسط برش‌های استاندارد بندرز را از بین می‌برد و نیازمند برش‌های L-شکل صحیح تخصصی است.

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

نقاط قوت

  • تصمیمات گسسته ترکیبیاتی را تحت عدم قطعیت در یک مدل بهینه‌سازی منسجم واحد مدیریت می‌کند.
  • برنامه‌های مرحله اول پوشش‌یافته‌ای تولید می‌کند که عملکرد مورد انتظار را در تمام سناریوها متعادل می‌کنند.
  • معیارهای VSS و EVPI توجیه شفافی برای ارزش مدل‌سازی تصادفی ارائه می‌دهند.
  • الگوریتم‌های تجزیه (L-شکل، تدریج پوششی) با مجموعه‌های سناریوی بزرگ مقیاس می‌شوند.
  • به طور گسترده در حل‌کننده‌های تجاری (CPLEX، Gurobi) و زبان‌های مدل‌سازی (AMPL، Pyomo) پشتیبانی می‌شود.

کاربردها

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

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

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

1

متغیرهای تصمیم را شناسایی کنید: تصمیمات مرحله اول x که قبل از آشکار شدن عدم قطعیت گرفته می‌شوند (در میان آن‌ها اعداد صحیح و/یا دودویی)، و متغیرهای جبرانی مرحله دوم y(xi) که پس از وقوع سناریو xi گرفته می‌شوند. ضرایب هدف، ماتریس‌های محدودیت، و توزیع احتمال یا مجموعه سناریوهای گسسته برای پارامترهای نامشخص را مشخص کنید.

2

یک مجموعه سناریوی متناهی {xi_1, ..., xi_S} با احتمالات مرتبط {p_1, ..., p_S} که توزیع زیربنایی را تقریب می‌زند، بسازید. سناریوها می‌توانند از داده‌های تاریخی، استنتاج خبره، نمونه‌برداری هایپِرکیوب لاتین، یا روش‌های تطبیق گشتاور استخراج شوند. کیفیت سناریو مستقیماً بر کیفیت راه‌حل تأثیر می‌گذارد.

3

معادل قطعی را فرموله کنید: minimize c'x + sum_s p_s Q(x, xi_s) تحت محدودیت‌های مرحله اول و صحت. Q(x, xi_s) تابع ارزش مرحله دوم است — هزینه بهینه اقدامات جبرانی با توجه به x و سناریوی xi_s. برنامه ترکیبی یک MIP بزرگ است که اندازه آن با تعداد سناریوها افزایش می‌یابد.

فرمول
\min_{x \in X} c^T x + \mathbb{E}_\xi[Q(x,\xi)] \quad \text{s.t. } Ax = b,\; x \in \mathbb{Z}^p \times \mathbb{R}^{n-p}
4

با استفاده از الگوریتم‌های تجزیه حل کنید — روش L-شکل (تجزیه بندرز) برای مراحل دوم محدب، برش-و-انشعاب با زیرمسائل سناریو، یا تدریج پوششی برای تجزیه موازی سناریو. صحت در مرحله دوم نیازمند برش‌های اضافی (برش‌های L-شکل صحیح، لیفت-و-پروجکت) است. حل‌کننده‌های مدرن (CPLEX، Gurobi با فراخوانی‌ها، یا کتابخانه‌های خاص SMIP) این رویه‌ها را پیاده‌سازی می‌کنند.

5

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

دام‌های رایج

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

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

SMIP چگونه با برنامه‌ریزی عدد صحیح مختلط معمولی متفاوت است؟

MIP معمولی تحت پارامترهای ثابت و شناخته شده بهینه‌سازی می‌کند. SMIP به طور صریح پارامترهای نامشخص را به عنوان مجموعه‌ای از سناریوها با احتمالات مدل‌سازی می‌کند، عملکرد مورد انتظار را در تمام سناریوها بهینه‌سازی می‌کند و در عین حال اطمینان حاصل می‌کند که تصمیمات مرحله اول قبل از آشکار شدن عدم قطعیت گرفته می‌شوند.

به چند سناریو نیاز دارم؟

قانون جهانی وجود ندارد. ممکن است ۱۰ تا ۵۰ سناریو برای تصمیمات مرحله اول پایدار در برخی مسائل کافی باشد؛ برخی دیگر به هزاران نفر نیاز دارند. تکنیک‌های کاهش سناریو و آزمون‌های پایداری (بررسی اینکه راه‌حل بهینه با افزودن سناریوهای بیشتر تغییر نمی‌کند) به تعیین کفایت کمک می‌کنند.

روش L-شکل چیست؟

روش L-شکل یک تجزیه بندرز است که برای برنامه‌های تصادفی تطبیق داده شده است. این روش به طور تکراری یک MIP اصلی بر روی متغیرهای مرحله اول و زیرمسائل سناریو را حل می‌کند و برش‌های بهینگی و امکان‌پذیری را به اصلی اضافه می‌کند تا زمانی که همگرا شود. برای جبران صحیح، برش‌های L-شکل صحیح جایگزین برش‌های استاندارد بندرز می‌شوند.

چه زمانی باید به جای روش L-شکل از تدریج پوششی استفاده کنم؟

تدریج پوششی بر اساس سناریو به جای ساختار زیرمسئله تجزیه می‌شود، که آن را برای محاسبات موازی مناسب می‌سازد. زمانی که سناریوها زیاد و زیرمسائل بزرگ هستند و الگوریتم را می‌توان بر روی یک خوشه اجرا کرد، ترجیح داده می‌شود. L-شکل به طور کلی برای سناریوهای کمتر و با ساختار خوب ترجیح داده می‌شود.

آیا SMIP می‌تواند بیش از دو مرحله را مدیریت کند؟

بله، اما SMIP چند مرحله‌ای نیازمند یک درخت سناریو است که با تعداد مراحل به صورت نمایی رشد می‌کند و تجزیه به طور قابل توجهی پیچیده‌تر می‌شود. در عمل، بیشتر مدل‌های SMIP کاربردی از دو مرحله استفاده می‌کنند و پویایی‌های چند دوره‌ای را از طریق افق غلتان یا تجمیع تقریب می‌زنند.

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

منابع

  1. Birge, J. R., & Louveaux, F. (1997). Introduction to Stochastic Programming. Springer Series in Operations Research. New York: Springer.

    شابک: 9780387982175
    کپی شد.
  2. Sen, S., & Higle, J. L. (2005). The C3 theorem and a D2 algorithm for large scale stochastic mixed-integer programming: Set convexification. Mathematical Programming, 104(1), 1–20.

    باز کردن مرجع DOI
    کپی شد.