الانتقال إلى المحتوى
العودة إلى نتائج البحث

توليد الأعمدة (دانزيغ-وولف)

قدّمه
George B. Dantzig and Philip Wolfe
السنة
1960
النوع
algorithm
العائلة
Optimization

هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية

حجم الخط

ماذا تفعل؟

توليد الأعمدة، الذي طوره جورج بي. دانزيغ وفيليب وولف في عام 1960، هو تقنية تحسين قوية لحل مشاكل البرمجة الخطية واسعة النطاق ذات الهيكل الخاص. يُعرف أيضًا باسم تفكيك دانزيغ-وولف، وهو يفكك المشكلة إلى مشكلة رئيسية (مقيدة بمجموعة فرعية من المتغيرات/الأعمدة) ومشكلة تسعير فرعية (تحديد متغيرات جديدة)، ويحسن الحل بشكل تكراري عن طريق إدخال الأعمدة ذات الصلة فقط.

الفكرة الحدسية وراء الطريقة

تدرك هذه الطريقة أن العديد من مشاكل التحسين الكبيرة لها هيكل خاص: عدد كبير من المتغيرات ولكن عدد قليل من القيود المهمة حقًا، أو مشاكل فرعية قابلة للتفكيك بشكل طبيعي. بدلاً من حل المشكلة الكاملة بجميع المتغيرات الممكنة، يحتفظ توليد الأعمدة بمجموعة فرعية صغيرة فقط من الأعمدة الواعدة (المتغيرات). مشكلة التسعير، التي يتم حلها باستخدام التكاليف المخفضة وهيكل المشكلة، تحدد أعمدة جديدة تحسن الحل الرئيسي. من خلال إضافة الأعمدة الواعدة الأكثر بشكل تكراري، يبني الخوارزمية حلاً بكفاءة، متجنبًا العبء الحسابي للتعامل مع جميع الأعمدة في وقت واحد.

التاريخ

قدم دانزيغ وولف مبدأ التفكيك للبرامج الخطية في عام 1960، مما أسس الأساس النظري. طبق جيلمور وجوموري (1961) ذلك على مشكلة قطع المخزون، مما أظهر القوة العملية. اكتسبت الطريقة شهرة لمشاكل توجيه المركبات وجدولتها في الثمانينيات والتسعينيات. وسع الدمج مع التفرع والحد، مما أدى إلى إنشاء خوارزميات التفرع والتوليد، نطاق التطبيق ليشمل البرمجة الصحيحة. تشمل التطبيقات الحديثة جدولة طواقم الطائرات، وتوجيه السفن، وتحسين لوجستيات واسعة النطاق.

متى تُستخدم

طبق توليد الأعمدة عند حل برامج خطية واسعة النطاق ذات هيكل خاص، خاصة عندما يكون عدد المتغيرات ضخمًا ولكن مجموعة فرعية صغيرة تهيمن على الحل الأمثل. إنها مثالية لمشاكل قطع المخزون، وتوجيه المركبات، وجدولة الطواقم، وتعبئة الصناديق. استخدمها عندما يسمح هيكل المشكلة بحل مشكلة تسعير فعالة. بالنسبة للمشاكل التي لا تحتوي على هيكل قابل للاستغلال أو ذات حجم معتدل، فإن أدوات حل البرمجة الخطية القياسية أكثر عملية.

الحدود والاعتبارات

  • تتطلب هيكل مشكلة يسمح بحل فعال لمشكلة التسعير الفرعية
  • يمكن أن يكون التقارب بطيئًا، خاصة بالقرب من الأمثلية (تأثير التذييل)
  • يجب أن يكون حل مشكلة التسعير الفرعية موثوقًا وفعالًا، وإلا فإن مكاسب الكفاءة تضيع
  • تعقيد التنفيذ أكبر من طرق البرمجة الخطية القياسية
  • مشاكل الاستقرار العددي مع القيم الثنائية الكبيرة والتكاليف المخفضة

لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.

نقاط القوة

  • حل مشاكل واسعة النطاق لا يمكن حلها بالطرق القياسية بسبب انفجار الأعمدة
  • استغلال هيكل المشكلة لتوليد الأعمدة ذات الصلة فقط
  • توفير حدود لجودة الحل أثناء التكرار
  • مناسبة بشكل طبيعي للمشاكل ذات الهيكل الفرعي الخاص (مشاكل فرعية متطابقة، تناظر)
  • قابلة للدمج مع التفرع والحد لبرامج الأعداد الصحيحة (التفرع والتوليد)

التطبيقات

  • مشكلة قطع المخزون: تقليل الهدر عند قطع المواد إلى أحجام مطلوبة
  • توجيه المركبات: تحسين المسارات للتسليم والنقل مع نوافذ زمنية وقيود سعة
  • جدولة الطواقم: تعيين أفراد الطاقم للرحلات أو المناوبات مع تقليل التكلفة الإجمالية
  • تعبئة الصناديق: تعبئة العناصر بكفاءة في حاويات لتقليل الهدر وعدد الحاويات
  • وضع الجداول: جدولة العمال عبر المناوبات مع مراعاة قيود التوفر والتفضيلات
  • تخطيط الطيران: جدولة الرحلات، وتعيينات الطواقم، وتنسيق صيانة الطائرات

كيف يعمل

كيف يعمل

1

ابدأ بمشكلة رئيسية مقيدة تحتوي فقط على مجموعة فرعية من الأعمدة اللازمة لحل أولي ممكن.

2

حل الثنائية للمشكلة الرئيسية المقيدة الحالية باستخدام جدول السيمبلكس. حدد التكاليف المخفضة وأنشئ مشكلة التسعير الفرعية للعثور على المتغيرات ذات التكلفة المخفضة السالبة (للتقليل).

3

حل مشكلة التسعير الفرعية باستخدام هيكلها الخاص. إذا تم العثور على عمود جديد بتكلفة مخفضة سالبة، فأضفه إلى المشكلة الرئيسية وكرر. إذا لم يكن هناك عمود محسّن، فإن الحل الحالي هو الأمثل.

الأخطاء الشائعة

  • اختيار خوارزمية غير فعالة لمشكلة التسعير الفرعية، مما يلغي مكاسب الكفاءة من توليد الأعمدة
  • الفشل في التعرف على هيكل المشكلة القابل للتفكيك، مما يؤدي إلى أداء ضعيف
  • كشف غير كافٍ عن التقارب أو تفاوت صارم للغاية، مما يهدر التكرارات
  • عدم تطبيق تقنيات الاستقرار لمعالجة تأثير التذييل

الأسئلة الشائعة

ما هي مشكلة التسعير في توليد الأعمدة وكيف ترتبط بالتكاليف المخفضة؟

تحدد مشكلة التسعير المتغيرات الجديدة (الأعمدة) ذات التكلفة المخفضة السالبة التي تحسن الحل الرئيسي. تأتي قيم التكلفة المخفضة من الثنائية للمشكلة الرئيسية المقيدة وتوجه البحث في مشكلة التسعير الفرعية.

لماذا يعتبر توليد الأعمدة أفضل من حل المشكلة الكاملة بجميع الأعمدة؟

في العديد من المشاكل، يكون عدد الأعمدة المحتملة أسيًا أو لا نهائيًا، مما يجعل من المستحيل تعدادها جميعًا. يقوم توليد الأعمدة بتوليد الأعمدة الضرورية فقط عند الطلب، مما يقلل بشكل كبير من العبء الحسابي.

ما هو تأثير التذييل وكيف يمكن التخفيف منه؟

يحدث التذييل عندما يحقق توليد الأعمدة تقدمًا بطيئًا بالقرب من الأمثلية، ويولد العديد من الأعمدة بتحسينات طفيفة. تقنيات الاستقرار (تنعيم الثنائية، طرق المنطقة الموثوقة، استراتيجيات القطع) تقلل من تأثيره.

كيف يوسع التفرع والتوليد توليد الأعمدة إلى البرمجة الصحيحة؟

يجمع التفرع والتوليد بين توليد الأعمدة والتفرع والحد: عند كل عقدة، يحل توليد الأعمدة استرخاء البرمجة الخطية، وقرارات التفرع تقيد المشكلة بشكل أكبر عندما تكون حلول البرمجة الخطية كسرية.

طرق ذات صلة

المصادر

  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
    تم النسخ.