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

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

معرفی‌شده توسط
Dantzig, G. B.; Beale, E. M. L.
سال
1955
نوع
Optimization under uncertainty with discrete decisions
خانواده
Simulation / optimization

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

اندازه قلم

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

برنامه‌ریزی عدد صحیح تصادفی (SIP) یک چارچوب بهینه‌سازی است که متغیرهای تصمیم عدد صحیح (گسسته) را با مدل‌سازی احتمالی صریح عدم قطعیت ترکیب می‌کند. این روش به دنبال بهترین تصمیمِ «هم‌اکنون» است که هزینه مورد انتظار (یا سود مورد انتظار) را در سراسر توزیعی از سناریوهای آینده به حداقل می‌رساند (یا به حداکثر می‌رساند)، با در نظر گرفتن این واقعیت که برخی تصمیمات باید قبل از رفع عدم قطعیت اتخاذ شوند.

شهود پشت روش

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

تاریخ

برنامه‌ریزی تصادفی به دانتزیگ (1955) و بیل (1955) بازمی‌گردد که به طور مستقل مدل‌های جبرانی دو مرحله‌ای را برای برنامه‌های خطی تحت عدم قطعیت پیشنهاد کردند. گسترش صحیح با بلوغ برنامه‌ریزی صحیح در دهه‌های 1960 تا 1980 پدیدار شد. کتاب درسی بیرج و لووکس در سال 1997 این حوزه را مدون کرد و کلیگت و همکاران (2002) تقریب میانگین نمونه را به عنوان رویکرد محاسباتی استاندارد برای بهینه‌سازی گسسته تصادفی در مقیاس بزرگ معرفی کردند.

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

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

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

  • پیچیدگی محاسباتی با افزایش تعداد سناریوها و متغیرهای صحیح به سرعت افزایش می‌یابد؛ نمونه‌های بزرگ NP-hard هستند.
  • تولید سناریو نیازمند توزیع‌های احتمالی معتبر است که ممکن است استخراج یا تخمین آن‌ها از داده‌های محدود دشوار باشد.
  • گسترش‌های چند مرحله‌ای (بیش از دو مرحله) با رشد نمایی درخت‌های سناریو مواجه هستند و به ندرت فراتر از سه مرحله قابل حل هستند.
  • مهارت مدل‌سازی برای مشخص کردن صحیح امکان‌پذیری جبرانی، محدودیت‌های عدم پیش‌بینی (non-anticipativity) و ساختارهای جریمه مورد نیاز است.

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

نقاط قوت

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

کاربردها

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

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

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

1

فرموله‌بندی مسئله مرحله اول: انتخاب متغیرهای تصمیم صحیح (یا مختلط صحیح) x قبل از آشکار شدن عدم قطعیت. هدفی را تعریف کنید که شامل هزینه فوری و هزینه جبرانی مورد انتظار در تمام سناریوها باشد. محدودیت‌هایی که x را به شرایط امکان‌پذیری پیوند می‌دهند در اینجا مشخص می‌شوند.

فرمول
\min_{x \in \mathbb{Z}^n} c^T x + \mathbb{E}_\xi[Q(x, \xi)]
2

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

3

در فرمول‌بندی استاندارد دو مرحله‌ای، پس از تثبیت x و تحقق سناریوی xi، یک مسئله جبرانی (مرحله دوم) اقدامات اصلاحی y را تعیین می‌کند. مسئله جبرانی اغلب یک برنامه خطی یا صحیح است. مدل کامل c^T x را به علاوه هزینه جبرانی مورد انتظار E[Q(x, xi)] به حداقل می‌رساند.

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

زیرمسائل سناریو را حل کنید تا هزینه جبرانی را برای هر سناریو با توجه به x ارزیابی کنید. تکنیک‌ها شامل شاخه و کران (branch-and-bound)، تجزیه بندر (Benders decomposition)، آرام‌سازی لاگرانژی (Lagrangian relaxation) و روش تقریب میانگین نمونه (Sample Average Approximation - SAA) است. برای درخت‌های سناریوی بزرگ، الگوریتم‌های تجزیه از ساختار بلوکی در سراسر سناریوها بهره می‌برند.

5

نتایج زیرمسائل را تجمیع کنید تا هزینه جبرانی مورد انتظار را تخمین بزنید. در SAA، این میانگین روی S سناریوی نمونه‌برداری شده است. تقریب حاصل به انتظار واقعی با رشد S همگرا می‌شود. کران‌های آماری کیفیت راه‌حل را می‌توان از واریانس نمونه محاسبه کرد.

فرمول
\mathbb{E}_\xi[Q(x,\xi)] \approx \frac{1}{S} \sum_{s=1}^{S} Q(x, \xi_s)
6

بهینگی یا نزدیکی به بهینگی را از طریق شکاف‌های بهینگی، معیارهای همگرایی، یا فواصل اطمینان آماری از SAA تأیید کنید. اگر شکاف قابل قبول نیست، مجموعه سناریو را اصلاح کنید، اندازه نمونه را افزایش دهید، یا آرام‌سازی‌ها را تنگ‌تر کنید. راه‌حل مرحله اول x* و هزینه کل مورد انتظار آن را گزارش دهید.

دام‌های رایج

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

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

برنامه‌ریزی عدد صحیح تصادفی چگونه با بهینه‌سازی مقاوم (robust optimization) متفاوت است؟

SIP هزینه مورد انتظار را در سراسر مجموعه‌ای وزن‌دار از سناریوها به حداقل می‌رساند و می‌پذیرد که برخی سناریوها ممکن است هزینه بالایی داشته باشند اگر احتمال وقوع آن‌ها کم باشد. بهینه‌سازی مقاوم هزینه بدترین حالت را در یک مجموعه عدم قطعیت به حداقل می‌رساند و هیچ فرض احتمالی نمی‌کند. SIP نیازمند توزیع احتمالی است؛ بهینه‌سازی مقاوم فقط به مجموعه عدم قطعیت نیاز دارد. SIP به طور کلی محافظه‌کارانه‌تر است اما به داده بیشتری نیاز دارد.

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

این به ابعاد مسئله و دقت مورد نظر بستگی دارد. رویکرد تقریب میانگین نمونه (SAA) فواصل اطمینان آماری را در مورد شکاف بهینگی ارائه می‌دهد. مطالعات کاربردی معمول از ده‌ها تا هزاران سناریو استفاده می‌کنند؛ تشخیص همگرایی (واریانس تخمین‌گر کران) انتخاب را هدایت می‌کند. برای مسائل ساختاریافته، تکنیک‌های کاهش سناریو (مانند Heitsch-Romisch) می‌توانند تعداد سناریوها را به طور قابل توجهی کاهش دهند.

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

بله، اما SIP چند مرحله‌ای به طور قابل توجهی دشوارتر است. درخت سناریو با افزایش مراحل به صورت نمایی رشد می‌کند و محدودیت‌های عدم پیش‌بینی باید در هر گره اعمال شوند. در عمل، مدل‌های سه مرحله‌ای برای کاربردهای قابل حل، هنجار هستند؛ فراتر از آن، معمولاً تقریب‌هایی مانند افق غلتان (rolling-horizon) یا کاهش درخت سناریو مورد نیاز است.

چه نرم‌افزارهایی می‌توانند مدل‌های برنامه‌ریزی عدد صحیح تصادفی را حل کنند؟

حل‌کننده‌های رایج شامل CPLEX و Gurobi (از طریق زبان‌های مدل‌سازی جبری مانند AMPL، JuMP در Julia، یا PuLP/Pyomo در Python) هستند که از تجزیه سناریو پشتیبانی می‌کنند. چارچوب‌های تخصصی برنامه‌ریزی تصادفی شامل PySP (Python)، حل‌کننده‌های فرمت SMPS و بسته Julia StochasticPrograms.jl است که SAA و پیش‌روی تدریجی (progressive hedging) را پیاده‌سازی می‌کند.

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

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

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

منابع

  1. Birge, J. R., & Louveaux, F. (1997). Introduction to Stochastic Programming. Springer, New York.

    شابک: 978-1-4614-0237-4
    کپی شد.
  2. Kleywegt, A. J., Shapiro, A., & Homem-de-Mello, T. (2002). The sample average approximation method for stochastic discrete optimization. SIAM Journal on Optimization, 12(2), 479-502.

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