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

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

معرفی‌شده توسط
Contini, B. (building on Charnes & Cooper's chance-constrained programming)
سال
1968
نوع
Stochastic multi-goal optimization
خانواده
Simulation / optimization

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

اندازه قلم

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

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

شهود پشت روش

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

تاریخ

برنامه‌ریزی هدف توسط چارنز و کوپر در اواخر دهه 1950 معرفی شد. کونتینی (1968) به طور رسمی آن را با استفاده از ایده‌های برنامه‌ریزی محدودیت شانس به تنظیمات تصادفی گسترش داد. دهه‌های بعدی شاهد کاربردهای فزاینده‌ای در امور مالی، کشاورزی و سیاست عمومی بود. این روش از طریق ارتباط با بهینه‌سازی مقاوم که در دهه‌های 1990 و 2000 توسعه یافت، مبنای نظری بیشتری کسب کرد.

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

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

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

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

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

نقاط قوت

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

کاربردها

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

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

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

1

متغیرهای تصمیم، اهداف آرمانی چندگانه (اهداف) و هرگونه محدودیت سخت را تعریف کنید. هر هدف i به صورت زیر بیان می‌شود: f_i(x) + d_i^- - d_i^+ = g_i، که در آن d_i^- و d_i^+ متغیرهای انحراف منفی و مثبت از هدف g_i هستند. وزن‌های اولویت را که اهمیت نسبی دستیابی به هر هدف را منعکس می‌کنند، اختصاص دهید.

2

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

3

محدودیت‌های نامشخص را به محدودیت‌های شانس (احتمالی) تبدیل کنید. برای یک محدودیت تصادفی شامل پارامتر تصادفی b_i با توزیع F، لازم است P(g_i(x) <= b_i) >= alpha_i، که در آن alpha_i سطح اطمینان مشخص شده توسط کاربر است (مانند 0.90 یا 0.95). تحت مفروضات نرمال، اینها می‌توانند به عنوان محدودیت‌های مخروط مرتبه دوم قطعی بازسازی شوند.

فرمول
P(g_i(x) \leq b_i) \geq \alpha_i
4

مسئله بهینه‌سازی حاصل (احتمالاً بازسازی شده) را حل کنید: مجموع وزنی انحرافات را به حداقل برسانید min sum_i (w_i^+ d_i^+ + w_i^- d_i^-) با رعایت معادل‌های قطعی محدودیت‌های شانس و هرگونه محدودیت سخت باقی‌مانده. بسته به ساختار مسئله از حل‌کننده‌های LP، MILP یا غیرخطی استفاده کنید.

فرمول
\min \sum_{i} (w_i^+ d_i^+ + w_i^- d_i^-)
5

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

دام‌های رایج

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

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

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

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

کدام فرض توزیعی بیشتر مورد استفاده قرار می‌گیرد؟

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

چگونه سطوح اطمینان alpha_i را برای هر محدودیت شانس انتخاب کنم؟

سطوح اطمینان منعکس کننده تحمل ریسک تصمیم‌گیرنده برای هر هدف است. مقادیر 0.90-0.95 در عمل رایج هستند. مقادیر بالاتر مسئله را محافظه‌کارانه‌تر می‌کنند و ممکن است نیاز به تعدیل اهداف دیگر داشته باشند؛ مقادیر پایین‌تر اجازه ریسک بیشتری می‌دهند اما ممکن است منجر به نتایج غیرقابل قبول شوند.

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

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

آیا باید هنگام داشتن پارامترهای نامشخص از برنامه‌ریزی هدف تصادفی یا بهینه‌سازی مقاوم استفاده کنم؟

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

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

منابع

  1. Contini, B. (1968). A stochastic approach to goal programming. Operations Research, 16(3), 576–586.

    باز کردن مرجع DOI
    کپی شد.
  2. Charnes, A., Cooper, W. W. (1959). Chance-constrained programming. Management Science, 6(1), 73–79.

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