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

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

معرفی‌شده توسط
Ben-Tal, A. and Nemirovski, A.; further developed by Bertsimas, D. and Sim, M.
سال
1999–2004
نوع
Uncertainty-robust linear optimization
خانواده
Simulation / optimization

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

اندازه قلم

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

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

شهود پشت روش

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

تاریخ

بهینه‌سازی مقاوم توسط Ben-Tal و Nemirovski (1999) بر پایه نظری محکمی بنا نهاده شد، که نشان دادند برنامه‌های خطی نامطمئن با مجموعه‌های عدم قطعیت بیضوی، برنامه‌های مخروط مرتبه دوم قابل حل تولید می‌کنند. Bertsimas و Sim (2004) چارچوب بودجه عدم قطعیت را معرفی کردند که بازسازی را به عنوان یک برنامه خطی حفظ می‌کند و مقاومت را از طریق یک پارامتر واحد قابل تنظیم می‌سازد و پذیرش عملی آن را در تحقیق در عملیات و مهندسی به شدت گسترش داد.

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

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

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

  • جهت‌گیری بدترین حالت می‌تواند راه‌حل‌های بیش از حد محافظه‌کارانه تولید کند، زمانی که سناریوهای شدید بسیار بعید هستند.
  • مجموعه‌های عدم قطعیت بیضوی، برنامه‌های مخروط مرتبه دوم قابل حل تولید می‌کنند اما دیگر LP خالص نیستند و نیاز به حل‌کننده‌های بیشتری دارند.
  • نیاز دارد که تحلیلگر یک مجموعه عدم قطعیت را مشخص کند، که خود یک انتخاب مدل‌سازی است و به طور قابل توجهی بر نتایج تأثیر می‌گذارد.
  • مستقیماً گزاره‌های احتمال نقض را ارائه نمی‌دهد؛ اگر احتمالات دم مهم باشند، برنامه‌ریزی تصادفی بهتر است.
  • زمانی که گاما (Gamma) = 0 باشد، به LP اسمی تقلیل می‌یابد و هیچ حفاظتی در برابر عدم قطعیت ارائه نمی‌دهد.

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

نقاط قوت

  • تضمین‌های سخت امکان‌پذیری بدترین حالت را بدون نیاز به فرضیات توزیعی فراهم می‌کند.
  • فرمول‌بندی بودجه برتسیماس-سیم (Bertsimas-Sim) یک همتای LP قابل حل تولید می‌کند که با حل‌کننده‌های آماده قابل حل است.
  • بودجه مقاومت گاما (Gamma) به تحلیلگر یک اهرم شهودی برای مبادله کیفیت راه‌حل با محافظه‌کاری می‌دهد.
  • از نظر محاسباتی کارآمد است — همتایان مقاوم برای مجموعه‌های بودجه دارای پیچیدگی مشابه LP اصلی هستند.
  • به ویژه برای مسائلی که نقض محدودیت در آن‌ها پرهزینه یا ناامن است، مناسب است.

کاربردها

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

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

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

1

برنامه‌ریزی خطی اسمی را فرموله کنید: کمینه‌سازی یک تابع هدف خطی c^T x تحت محدودیت‌های نامساوی خطی Ax <= b و نامنفی بودن. مشخص کنید کدام ضرایب — معمولاً درایه‌های ماتریس محدودیت a_ij — نامطمئن هستند. این مرحله منعکس‌کننده مدل‌سازی استاندارد LP است اما هر پارامتر نامطمئن را علامت‌گذاری می‌کند.

فرمول
\min c^T x \text{ s.t. } Ax \leq b, \; x \geq 0
2

یک مجموعه عدم قطعیت U بسازید که محدوده مقادیر قابل قبول پارامتر را بدون نیاز به توزیع احتمال، در بر گیرد. انتخاب‌های رایج عبارتند از مجموعه‌های جعبه‌ای (هر پارامتر به طور مستقل در محدوده [a_bar - a_hat, a_bar + a_hat] تغییر می‌کند)، مجموعه‌های بیضوی (Ben-Tal and Nemirovski, 1999) و مجموعه‌های بودجه (Bertsimas and Sim, 2004). پارامتر بودجه گاما (Gamma) تعداد پارامترهایی را که می‌توانند همزمان مقادیر بدترین حالت خود را بگیرند، محدود می‌کند.

فرمول
\mathcal{U} = \{ a_i : a_i = \bar{a}_i + \hat{a}_i \xi_i, \; \|\xi\|_\infty \leq 1 \}
3

هر محدودیت نامطمئن را با همتای مقاوم آن جایگزین کنید: امکان‌پذیری را برای هر تحقق در U الزامی کنید. این کار مسئله اصلی را به یک برنامه نیمه‌نامتناهی تبدیل می‌کند — تعداد نامتناهی محدودیت، یکی برای هر عنصر U.

فرمول
\max_{a_i \in \mathcal{U}} a_i^T x \leq b_i \quad \forall i
4

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

فرمول
\bar{a}_i^T x + \Gamma_i \max_{\{S: |S| \leq \Gamma_i\}} \sum_{j \in S} \hat{a}_{ij} |x_j| \leq b_i
5

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

دام‌های رایج

  • تنظیم گاما (Gamma) بیش از حد بالا، باعث می‌شود همه محدودیت‌ها همزمان بدترین حالت را تجربه کنند و راه‌حلی بیش از حد محافظه‌کارانه و گران‌قیمت ایجاد شود.
  • اشتباه مشخص کردن مجموعه عدم قطعیت (به عنوان مثال، نادیده گرفتن ساختار همبستگی) می‌تواند منجر به محافظت بیش از حد یا کمتر از حد شود.
  • اشتباه گرفتن LP مقاوم با LP تصادفی: RLP عملکرد بدترین حالت را به حداکثر می‌رساند، نه عملکرد مورد انتظار.
  • نادیده گرفتن گزارش قیمت مقاومت — همیشه راه‌حل مقاوم را با راه‌حل LP اسمی مقایسه کنید تا هزینه محافظه‌کاری را کمی کنید.
  • اعمال RLP به مسائل با متغیرهای صحیح بدون تغییر به فرمول‌بندی مختلط صحیح مقاوم، که نیاز به بازسازی‌های متفاوتی دارد.

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

تفاوت Robust LP با Stochastic LP چیست؟

LP تصادفی عملکرد مورد انتظار را با توجه به توزیع احتمال بر روی سناریوها بهینه می‌کند و به دانش توزیعی نیاز دارد. Robust LP عملکرد بدترین حالت را بر روی مجموعه عدم قطعیت بهینه می‌کند و فقط به کران‌ها نیاز دارد — بدون توزیع احتمال. Robust LP زمانی ترجیح داده می‌شود که توزیع‌ها غیرقابل اعتماد باشند؛ LP تصادفی زمانی ترجیح داده می‌شود که به خوبی تخمین زده شده باشند.

قیمت مقاومت چیست؟

قیمت مقاومت، افزایش در مقدار هدف (هزینه) راه‌حل مقاوم نسبت به راه‌حل LP اسمی است. Bertsimas و Sim (2004) اثبات کردند که این قیمت تنها به اندازه ریشه دوم تعداد پارامترهای نامطمئن برای مجموعه‌های بودجه رشد می‌کند و مقاومت را به طرز شگفت‌انگیزی مقرون به صرفه می‌سازد.

بودجه مقاومت گاما (Gamma) چیست؟

گاما (Gamma) پارامتری در مدل Bertsimas-Sim است که کنترل می‌کند چه تعداد از ضرایب نامطمئن می‌توانند همزمان مقادیر بدترین حالت خود را بگیرند. گاما (Gamma) = 0، LP اسمی را بازیابی می‌کند؛ گاما (Gamma) = n، در برابر انحراف همزمان همه n پارامتر محافظت می‌کند. تحلیلگران معمولاً گاما (Gamma) را بر اساس حدود احتمال نقض قابل قبول انتخاب می‌کنند.

آیا Robust LP به حل‌کننده خاصی نیاز دارد؟

خیر. برای مجموعه‌های عدم قطعیت جعبه‌ای و بودجه، همتای مقاوم خود یک برنامه خطی است که با هر حل‌کننده LP استاندارد (CPLEX, Gurobi, HiGHS, و غیره) قابل حل است. مجموعه‌های بیضوی به حل‌کننده برنامه مخروط مرتبه دوم نیاز دارند که آن نیز به طور گسترده پشتیبانی می‌شود.

چه زمانی باید به جای آن از Robust Mixed-Integer Programming استفاده کنم؟

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

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

منابع

  1. Bertsimas, D., Sim, M. (2004). The price of robustness. Operations Research, 52(1), 35–53.

    باز کردن مرجع DOI
    کپی شد.
  2. Ben-Tal, A., Nemirovski, A. (1999). Robust solutions of uncertain linear programs. Operations Research Letters, 25(1), 1–13.

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