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

تجزیه بندرز

معرفی‌شده توسط
Jacques F. Benders
سال
1962
نوع
algorithm
خانواده
Optimization

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

اندازه قلم

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

تجزیه بندرز (Benders Decomposition)، که توسط ژاک اف. بندرز در سال ۱۹۶۲ معرفی شد، یک چارچوب الگوریتمی قدرتمند برای حل مسائل برنامه‌ریزی عدد صحیح مختلط (MIP) در مقیاس بزرگ است. این روش مسئله را به یک مسئله اصلی (کنترل‌کننده متغیرهای پیچیده‌کننده) و زیرمسائل (مدیریت متغیرهای باقیمانده) تجزیه می‌کند و از صفحات برش تولید شده از اطلاعات دوگان زیرمسئله برای سفت کردن مکرر مسئله اصلی استفاده می‌کند.

شهود پشت روش

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

تاریخ

بندرز روش تجزیه خود را در سال ۱۹۶۲ برای تقسیم مسائل برنامه‌ریزی عدد صحیح مختلط معرفی کرد. جفریون در سال ۱۹۷۲ این رویکرد را برای مدیریت مسائل غیرخطی تعمیم داد و چارچوبی را ایجاد کرد که در کاربردهای مدرن استفاده می‌شود. این روش با پیشرفت در قدرت محاسباتی و حل‌کننده‌ها اهمیت یافت. تحولات اخیر شامل برش‌های ترکیبی بندرز، انواع چندبرشی و ادغام با الگوریتم‌های شاخه و برش مدرن است که آن را به یک تکنیک اساسی در بهینه‌سازی پیشرفته تبدیل کرده است.

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

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

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

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

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

نقاط قوت

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

کاربردها

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

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

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

1

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

2

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

3

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

دام‌های رایج

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

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

متغیرهای پیچیده‌کننده چه هستند و چگونه آنها را شناسایی می‌کنید؟

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

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

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

تجزیه بندرز چگونه همگرایی را تضمین می‌کند؟

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

چه زمانی تجزیه بندرز به حل مستقیم مسئله با یک حل‌کننده MIP ارجحیت دارد؟

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

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

منابع

  1. Benders, J. F. (1962). Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik, 4(1), 238-252.

    باز کردن مرجع DOI
    کپی شد.
  2. Geoffrion, A. M. (1972). Generalized Benders decomposition. Journal of Optimization Theory and Applications, 10(4), 237-260.

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