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

برنامه‌ریزی عدد صحیح مختلط چندهدفه (Multi-Objective Mixed-Integer Programming)

معرفی‌شده توسط
Ehrgott, M.; Mavrotas, G. and others in multi-criteria optimization
سال
1980s–2000s
نوع
Mathematical optimization
خانواده
Simulation / optimization

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

اندازه قلم

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

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

شهود پشت روش

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

تاریخ

برنامه‌ریزی عدد صحیح مختلط در دهه‌های ۱۹۵۰-۱۹۶۰ از طریق کارهای گوموری و لند و دایگ فرموله شد. توسعه‌های چندهدفه در دهه‌های ۱۹۷۰-۱۹۸۰ با درک محققان از اینکه بسیاری از مسائل مهندسی و تحقیق در عملیات شامل اهداف رقابتی هستند، ظهور کردند. درمان سیستماتیک توسط ارگوت (۲۰۰۵) و ماوروتاس (۲۰۰۹) تثبیت شد، که پیاده‌سازی اپسیلون-قید آنها همچنان یک مرجع پراستناد برای MO-MIP عملی باقی مانده است.

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

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

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

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

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

نقاط قوت

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

کاربردها

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

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

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

1

مسئله را با مشخص کردن k تابع هدف f_1(x), ..., f_k(x) برای حداقل‌سازی یا حداکثرسازی، مجموعه‌ای از قیود خطی یا غیرخطی Ax <= b، و دامنه‌های متغیر که در آن برخی متغیرها صحیح (مثلاً باینری ۰/۱) و برخی دیگر پیوسته هستند، فرمول‌بندی کنید. قبل از حل، حدود و داده‌ها را به وضوح تعریف کنید.

2

از یک استراتژی اسکالرسازی یا تجزیه برای تبدیل مسئله چندهدفه به دنباله‌ای از زیرمسائل MIP تک‌هدفه استفاده کنید. استراتژی‌های رایج شامل روش مجموع وزنی (حداقل‌سازی مجموع w_i * f_i)، روش اپسیلون-قید (بهینه‌سازی یک هدف در حالی که اهداف دیگر را به سطوح آستانه محدود می‌کنیم) و توابع اسکالرسازی دستیابی هستند.

3

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

4

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

5

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

دام‌های رایج

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

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

MO-MIP چگونه با برنامه‌ریزی خطی چندهدفه استاندارد متفاوت است؟

در LP چندهدفه تمام متغیرهای تصمیم‌گیری پیوسته هستند، بنابراین راه‌حل‌های پارتوی کارآمد در رئوس یک چندوجهی محدب یافت می‌شوند. MO-MIP نیازمند این است که برخی یا تمام متغیرها صحیح باشند، که مجموعه عملی را غیرمحدب و گسسته می‌سازد، و این امر نیازمند جستجوی شاخه و کران به جای روش‌های مبتنی بر سیمپلکس است.

آیا می‌توانم از فراابتکارها مانند NSGA-II به جای حل‌کننده‌های دقیق MIP استفاده کنم؟

بله، و برای مسائل در مقیاس بزرگ یا پیچیده ترکیبی، فراابتکارها اغلب ترجیح داده می‌شوند زیرا بهتر مقیاس‌پذیر هستند. مبادله این است که آنها جبهه‌های پارتوی تقریبی را بدون تضمین بهینگی ارائه می‌دهند، در حالی که حل‌کننده‌های دقیق MO-MIP عدم مغلوب بودن را برای راه‌حل‌های یافت شده تضمین می‌کنند.

روش اپسیلون-قید چیست و چرا توصیه می‌شود؟

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

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

این بستگی به تعداد اهداف و وضوح مورد نیاز برای تصمیم‌گیری دارد. برای دو هدف، معمولاً ۲۰ تا ۵۰ راه‌حل با فاصله مساوی برای توصیف جبهه کافی است. برای سه یا چند هدف، تعداد به طور ترکیبی افزایش می‌یابد؛ روش‌های تعاملی یا هدایت‌شده با ترجیحات برای جلوگیری از بارگذاری بیش از حد راه‌حل توصیه می‌شوند.

آیا MO-MIP برای مسائل با عدم قطعیت در داده‌ها مناسب است؟

MO-MIP استاندارد داده‌های قطعی را فرض می‌کند. هنگامی که داده‌های ورودی نامشخص هستند، باید با افزونه‌های بهینه‌سازی مقاوم یا برنامه‌ریزی تصادفی ترکیب شود - به عنوان مثال، MO-MIP دو مرحله‌ای تصادفی یا MO-MIP مقاوم با حدود هدف بدترین حالت.

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

منابع

  1. Ehrgott, M. (2005). Multicriteria Optimization (2nd ed.). Springer, Berlin.

    شابک: 9783540213987
    کپی شد.
  2. Mavrotas, G. (2009). Effective implementation of the epsilon-constraint method in Multi-Objective Mathematical Programming problems. Applied Mathematics and Computation, 213(2), 455-465.

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