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

تولید ستون (دانتزیگ-ولف)

معرفی‌شده توسط
George B. Dantzig and Philip Wolfe
سال
1960
نوع
algorithm
خانواده
Optimization

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

اندازه قلم

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

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

شهود پشت روش

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

تاریخ

دانتزیگ و ولف اصل تجزیه را برای برنامه‌های خطی در سال ۱۹۶۰ معرفی کردند و مبانی نظری آن را بنا نهادند. گیلמור و گوموری (۱۹۶۱) آن را برای مسئله برش مواد به کار بردند و قدرت عملی آن را نشان دادند. این روش در دهه‌های ۱۹۸۰-۹۰ برای مسائل مسیریابی وسایل نقلیه و زمان‌بندی شهرت یافت. ادغام با شاخه و کران، ایجاد الگوریتم‌های شاخه و قیمت، کاربرد آن را به برنامه‌ریزی صحیح گسترش داد. کاربردهای مدرن شامل زمان‌بندی خدمه خطوط هوایی، مسیریابی کشتی‌ها و بهینه‌سازی لجستیک در مقیاس بزرگ است.

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

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

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

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

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

نقاط قوت

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

کاربردها

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

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

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

1

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

2

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

3

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

دام‌های رایج

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

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

مسئله قیمت‌گذاری در تولید ستون چیست و چگونه با هزینه‌های کاهش‌یافته ارتباط دارد؟

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

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

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

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

دم‌کشی زمانی رخ می‌دهد که تولید ستون در نزدیکی بهینگی پیشرفت کندی دارد و ستون‌های زیادی با بهبود اندک تولید می‌کند. تکنیک‌های تثبیت (هموارسازی دوگان، روش‌های ناحیه اعتماد، استراتژی‌های برش) تأثیر آن را کاهش می‌دهند.

چگونه شاخه و قیمت، تولید ستون را به برنامه‌ریزی صحیح گسترش می‌دهد؟

شاخه و قیمت، تولید ستون را با شاخه و کران ترکیب می‌کند: در هر گره، تولید ستون استراحت LP را حل می‌کند و تصمیمات شاخه‌بندی مسئله را در صورت کسری بودن راه‌حل‌های LP بیشتر محدود می‌کنند.

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

منابع

  1. Dantzig, G. B., & Wolfe, P. (1960). Decomposition principle for linear programs. Operations Research, 8(1), 101-111.

    باز کردن مرجع DOI
    کپی شد.
  2. Gilmore, P. C., & Gomory, R. E. (1961). A linear programming approach to the cutting-stock problem. Operations Research, 9(6), 849-859.

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