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

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

معرفی‌شده توسط
Charnes, A. & Cooper, W. W. (goal programming); Mulvey, J. M. et al. (robust optimization framework)
سال
1961 (GP); 1990s (robust extension)
نوع
Mathematical programming under uncertainty
خانواده
Simulation / optimization

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

اندازه قلم

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

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

RGP در مسائل برنامه‌ریزی که در آن‌ها اهداف بلندپروازانه هستند و داده‌های ورودی دارای تغییرپذیری ذاتی یا خطای تخمین هستند، ارزشمند است.

شهود پشت روش

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

تاریخ

برنامه‌ریزی هدف توسط Charnes و Cooper در سال 1961 به عنوان راهی برای مدیریت اهداف چندگانه با کمینه‌سازی انحرافات وزنی از اهداف معرفی شد. چارچوب بهینه‌سازی قوی، که توسط Mulvey، Vanderbei، و Zenios در سال 1995 رسمی شد، راهی اصولی برای گنجاندن عدم قطعیت مبتنی بر سناریو در برنامه‌های ریاضی فراهم کرد. ادغام آن‌ها در برنامه‌ریزی هدف قوی به طور طبیعی در طول دهه‌های 1990 و 2000 با اعمال ایده‌های بهینه‌سازی قوی بر روی مسائل برنامه‌ریزی چندهدفه در تحقیق در عملیات دنبال شد.

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

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

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

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

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

نقاط قوت

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

کاربردها

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

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

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

1

متغیرهای تصمیم، سطوح هدف بلندپروازانه برای هر هدف (مانند سود >= T1، ضایعات <= T2)، و ساختار اولویت (لکسیکوگرافیک یا وزنی) را شناسایی کنید. متغیرهای انحراف مثبت و منفی d+ و d- را که میزان دستیابی بیش از حد و کمتر از حد هر هدف را اندازه‌گیری می‌کنند، تعریف کنید.

2

منابع عدم قطعیت را مشخص کنید: اهداف نامشخص سمت راست، ضرایب محدودیت، یا وزن‌های هدف. عدم قطعیت را به صورت مجموعه‌ای متناهی از سناریوها S = {s1, ..., sK} با احتمالات ps، یا به صورت مجموعه‌های عدم قطعیت بازه‌ای/چندوجهی برای فرمول‌بندی‌های بهینه‌سازی قوی نمایش دهید.

3

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

4

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

5

راه‌حل را در تمام سناریوها ارزیابی کنید: میانگین، بدترین حالت، و بهترین حالت دستیابی به هدف را گزارش دهید. تحلیل حساسیت را بر روی پارامتر مبادله استحکام لامبدا انجام دهید تا مرز کارایی بین بهینگی و پایداری را آشکار سازید.

دام‌های رایج

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

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

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

GP تصادفی انحرافات مورد انتظار (متوسط) را در میان سناریوهای وزن‌دار با احتمال کمینه‌سازی می‌کند. GP قوی معمولاً واریانس یا نتایج بدترین حالت را نیز جریمه می‌کند — محافظه‌کارتر است اما راه‌حل‌هایی تولید می‌کند که در تمام سناریوها، حتی موارد با احتمال کم، عملکردی پایدارتر دارند.

آیا می‌توانم از عدم قطعیت بازه‌ای به جای سناریوها استفاده کنم؟

بله. هنگامی که پارامترها در بازه‌ها یا چندوجهی‌ها قرار می‌گیرند، می‌توان یک فرمول‌بندی همتای قوی (به دنبال رویکرد Ben-Tal و Nemirovski) استخراج کرد که GP نامشخص را به یک برنامه قطعی تبدیل می‌کند که با حل‌کننده‌های استاندارد LP یا SOCP قابل حل است.

پارامتر لامبدا چه چیزی را کنترل می‌کند؟

لامبدا مبادله بین عملکرد نامی و استحکام را کنترل می‌کند. لامبدای صفر، GP ارزش مورد انتظار را بازیابی می‌کند؛ افزایش لامبدا واریانس یا انحراف بدترین حالت را بیشتر جریمه می‌کند و راه‌حل‌های قوی‌تر اما بالقوه کمتر بهینه (از نظر مورد انتظار) تولید می‌کند.

آیا نرم‌افزار برای برنامه‌ریزی هدف قوی موجود است؟

فرمول‌بندی‌های استاندارد را می‌توان با هر حل‌کننده LP/QP (CPLEX، Gurobi، GLPK) حل کرد. فرمول‌بندی‌های تصادفی می‌توانند از GAMS، SPInE، یا کتابخانه‌های پایتون مانند PuLP و Pyomo با شمارش سناریو استفاده کنند.

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

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

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

منابع

  1. Charnes, A., Cooper, W. W. (1961). Management Models and Industrial Applications of Linear Programming. Wiley, New York.

    شابک: 9780471155041
    کپی شد.
  2. Mulvey, J. M., Vanderbei, R. J., Zenios, S. A. (1995). Robust optimization of large-scale systems. Operations Research, 43(2), 264-281.

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