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

برنامه‌ریزی خطی چندهدفه (MOLP)

معرفی‌شده توسط
Steuer, R. E.; Charnes, A.; Cooper, W. W.
سال
1955–1986
نوع
Mathematical optimization / vector optimization
خانواده
Simulation / optimization

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

اندازه قلم

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

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

شهود پشت روش

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

تاریخ

مبانی نظری برنامه‌ریزی خطی چندهدفه به کارهای دهه ۱۹۵۰ Charnes و Cooper در زمینه برنامه‌ریزی هدف و Koopmans در زمینه تولید کارا بازمی‌گردد. کتاب درسی Steuer در سال ۱۹۸۶ این حوزه را تثبیت کرد و روش‌های مجموع وزنی، اپسیلون-قید و تعاملی را که امروزه استاندارد باقی مانده‌اند، سیستماتیک کرد. MOLP اکنون یک موضوع اصلی در برنامه‌های درسی تحقیق در عملیات در سراسر جهان است.

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

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

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

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

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

نقاط قوت

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

کاربردها

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

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

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

1

k تابع هدف خطی f1(x) تا fk(x) و یک ناحیه شدنی X تعریف شده توسط قیود نامساوی و تساوی خطی (Ax <= b, x >= 0) را فرمول‌بندی کنید. مشخص کنید کدام اهداف باید کمینه و کدام باید بیشینه شوند. تأیید کنید که تمام توابع هدف و قیود نسبت به متغیرهای تصمیم، خطی هستند.

فرمول
\min_{x \in X} \mathbf{f}(x) = (f_1(x), f_2(x), \ldots, f_k(x))^T \text{ s.t. } Ax \leq b,\; x \geq 0
2

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

3

یک تکنیک مقیاس‌بندی را برای تبدیل مسئله برداری به دنباله‌ای از LPs تک‌هدفه اعمال کنید. در رویکرد مجموع وزنی، min sum(wi * fi(x)) را برای بردارهای وزنِ به طور سیستماتیک تغییر یافته حل کنید. هر نقطه حدیِ کارای فضای هدف را ثبت کنید.

فرمول
\min_{x \in X} \sum_{i=1}^{k} w_i f_i(x), \quad w_i \geq 0, \; \sum w_i = 1
4

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

5

تصمیم‌گیرنده را برای انتخاب یک راه‌حل ترجیحی از مجموعه کارا درگیر کنید. روش‌های تعاملی (STEM, NIMBUS) بین ارائه راه‌حل‌ها و پرسیدن از تصمیم‌گیرنده برای بیان ترجیحات، متناوباً عمل می‌کنند و به یک انتخاب نهایی که بهترین بازتاب اولویت‌های او باشد، همگرا می‌شوند.

دام‌های رایج

  • استفاده از وزن‌های ثابت در مقیاس‌بندی مجموع وزنی و گزارش تنها یک راه‌حل، مرز را مبهم می‌کند و هدف MOLP را از بین می‌برد.
  • اشتباه گرفتن کارایی پارتو با بهینگی: هر نقطه روی مرز کارا است، اما هیچ‌کدام بدون اطلاعات ترجیحی 'بهترین' جهانی نیستند.
  • نادیده گرفتن بررسی اینکه آیا ناحیه شدنی کراندار است؛ یک مسئله نامحدود مجموعه کارای محدودی تولید نمی‌کند.
  • در نظر گرفتن MOLP به عنوان یک جعبه سیاه بدون درگیر کردن تصمیم‌گیرنده در انتخاب، منجر به انتخاب‌های نهایی دلخواه می‌شود.
  • اعمال MOLP بر مسائل ذاتاً صحیح بدون تغییر به برنامه‌ریزی صحیح چندهدفه، تولید راه‌حل‌هایی که یکپارچگی را نقض می‌کنند.

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

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

برنامه‌ریزی هدف یک حالت خاص یا واریانت است: هر هدف را به یک سطح آرمانی تبدیل می‌کند و سپس انحرافات از آن اهداف را کمینه می‌کند و یک راه‌حل واحد تولید می‌کند. MOLP در شکل کلی خود به دنبال توصیف مرز کارای کامل بدون تعیین سطوح هدف از پیش است و به تصمیم‌گیرنده انعطاف‌پذیری بیشتری می‌دهد.

آیا MOLP می‌تواند بیش از دو هدف را مدیریت کند؟

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

اگر داده‌های من نامطمئن باشند چه؟

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

آیا MOLP همان بهینه‌سازی چندهدفه است؟

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

کدام روش مقیاس‌بندی را باید استفاده کنم؟

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

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

منابع

  1. Steuer, R. E. (1986). Multiple Criteria Optimization: Theory, Computation, and Application. John Wiley & Sons, New York.

    شابک: 9780471888468
    کپی شد.
  2. Chankong, V., Haimes, Y. Y. (1983). Multiobjective Decision Making: Theory and Methodology. North-Holland, New York.

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