البرمجة الصحيحة — البرمجة الصحيحة (IP) والبرمجة الصحيحة المختلطة (MIP)
- قدّمه
- Ralph Gomory (cutting planes, 1958); land-and-doig branch-and-bound (1960)
- السنة
- 1958
- النوع
- Mathematical optimisation — exact combinatorial method
هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية
ماذا تفعل؟
البرمجة الصحيحة (IP)، والتي تسمى أيضاً البرمجة الصحيحة المختلطة (MIP) عندما تكون بعض المتغيرات مقيدة بالأعداد الصحيحة فقط، هي فرع من التحسين الرياضي يجب أن تأخذ فيه بعض متغيرات القرار أو كلها قيماً صحيحة أو ثنائية. بناءً على البرمجة الخطية، تم إضفاء الطابع الرسمي عليها من خلال طريقة المستويات القاطعة لـ Ralph Gomory (1958) وخوارزمية التفرع والحد لـ Land و Doig (1960)، وأصبحت منذ ذلك الحين الإطار الدقيق القياسي لمشاكل الجدولة، والتخصيص، والتوجيه، وتخصيص الموارد.
الفكرة الحدسية وراء الطريقة
تجد البرمجة الخطية العادية أفضل نقطة في منطقة ممكنة مستمرة. لكن العديد من القرارات الواقعية منفصلة — لا يمكنك توظيف 2.7 ممرضة أو فتح نصف مستودع. تضيف البرمجة الصحيحة القيد بأن بعض المتغيرات أو كلها يجب أن تكون أعداداً صحيحة (أو خيارات ثنائية 0/1). ثمن هذا القيد هو حسابي: المجموعة الممكنة لم تعد سطحاً أملساً بل مجموعة مبعثرة من النقاط، وإيجاد الأفضل يمكن أن يتطلب فحص عدد هائل من الحلول المرشحة. تدير الحلول هذا عن طريق تقسيم المشكلة بذكاء إلى مشاكل فرعية أصغر (التفرع) وتقليم الفروع التي لا يمكن أن تتفوق على أفضل حل تم العثور عليه حتى الآن (الحد)، مع تشديد التقريب المستمر من خلال إضافة متباينات (مستويات قاطعة).
التاريخ
ظهرت البرمجة الصحيحة في أواخر الخمسينيات من القرن الماضي حيث سعى الباحثون إلى توسيع البرمجة الخطية لتشمل القرارات المنفصلة. قدم Ralph Gomory طريقة المستويات القاطعة المنهجية في عام 1958، وأثبت أنه يمكن حل أي برنامج صحيح من حيث المبدأ عن طريق إضافة عدد محدود من القواطع. قام Land و Doig (1960) بإضفاء الطابع الرسمي على التفرع والحد، والذي أصبح الخوارزمية الدقيقة المهيمنة. قدم Wolsey (1998) و Nemhauser و Wolsey (1988) المعالجات النصية القياسية التي لا يزال المجال يعتمد عليها. جاء الثورة العملية مع تطوير حلول التفرع والقطع في التسعينيات، ودمج كلتا التقنيتين مع الخوارزميات الاستدلالية المتقدمة، ولاحقاً مع الانفجار في أداء الحلول التجارية والمفتوحة المصدر التي تمكن التطبيقات الواقعية واسعة النطاق اليوم.
متى تُستخدم
استخدم البرمجة الصحيحة عندما تكون القرارات منفصلة بطبيعتها — خيارات نعم/لا ثنائية، كميات صحيحة، أو قيود منطقية تشغيل/إيقاف — وعندما تحتاج إلى حل أمثل دقيق أو شبه دقيق مع حد جودة قابل للإثبات. إنها مناسبة للجدولة، وتخصيص الطاقم والموارد، وتوجيه المركبات، وتحديد المواقع، وميزانية رأس المال، واختيار المحفظة. لا يوجد حد أدنى لحجم العينة مطلوب لأن البرمجة الصحيحة هي إطار تحسين حتمي بدلاً من إجراء استدلال إحصائي. يمكن أن تكون أنواع المتغيرات ثنائية، فئوية (مشفرة كثنائية)، أو مستمرة (في حالة البرمجة الصحيحة المختلطة). المتطلب العملي الرئيسي هو أن المشكلة يمكن نمذجتها بدالة هدف خطية وقيود خطية؛ إذا كانت الدالة الهدف أو القيود غير خطية، فإن امتدادات البرمجة الصحيحة غير الخطية المختلطة (MINLP) مطلوبة.
الحدود والاعتبارات
- البرمجة الصحيحة هي NP-hard بشكل عام؛ يمكن أن ينمو وقت الحل بشكل أسي مع حجم المشكلة والصياغة الضعيفة.
- استخلاص برمجة خطية ضعيف (فجوة تكامل كبيرة) يؤدي إلى أشجار بحث عميقة ومكلفة وأوقات تشغيل طويلة.
- توسيع المتغيرات الفئوية ذات العدد الكبير إلى ثنائية يمكن أن يؤدي إلى تضخم حجم النموذج.
- بالنسبة للحالات الكبيرة جداً، قد تحتاج الحلول إلى الإنهاء المبكر مع تحمل فجوة بدلاً من تحقيق فجوة صفرية.
لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.
نقاط القوة
- تنتج حلولاً مثلى دقيقة مع فجوة أمثلية معتمدة، على عكس الخوارزميات الاستدلالية التي لا تقدم ضمان جودة.
- تتعامل مع المتغيرات الثنائية والمتغيرات الصحيحة العامة بشكل أصلي، مما يجعلها الإطار الطبيعي للقرارات التوافقية.
- قابلة للتطبيق عبر مجموعة واسعة من مشاكل المجال — الجدولة، التوجيه، التخصيص، حقيبة الظهر — بنفس الآلية الرياضية.
- يمكن لحلول التفرع والقطع الحديثة حل مشاكل تحتوي على ملايين المتغيرات والقيود التي كانت ستكون غير قابلة للحل قبل عقود.
التطبيقات
- جدولة الموظفين والممرضات — تخصيص ورديات لتلبية متطلبات التغطية مع احترام لوائح ساعات العمل.
- توجيه المركبات واللوجستيات — إيجاد مسارات توصيل بأقل تكلفة تحت قيود السعة وفترات زمنية محددة.
- تحديد مواقع المرافق — تحديد المستودعات أو المصانع التي سيتم فتحها لتقليل إجمالي تكلفة التوزيع.
- ميزانية رأس المال — اختيار محفظة من المشاريع الاستثمارية ضمن ميزانية لزيادة إجمالي العائد.
- تخطيط الإنتاج — تحديد أحجام دفعات صحيحة عبر فترات زمنية لموازنة تكاليف الإعداد وتكاليف الاحتفاظ.
- تصميم الشبكة — اختيار الروابط التي سيتم تثبيتها في شبكة اتصالات أو نقل.
كيف يعمل
كيف يعمل
تُصاغ المشكلة كبرنامج رياضي: تحديد متغيرات القرار (التي يجب الإعلان عنها كأعداد صحيحة أو ثنائية حيث تتطلب المشكلة ذلك)، وكتابة دالة هدف خطية للتصغير أو التكبير، وسرد جميع القيود الخطية. صياغة محكمة — تكون فيها استرخاء البرمجة الخطية (LP) قريبة قدر الإمكان من الأمثل الصحيح تماماً — تقلل بشكل كبير من وقت الحل.
يتم إسقاط قيود التكامل مؤقتاً للحصول على استرخاء البرمجة الخطية. حل هذا الاسترخاء سريع ويعطي حداً: قيمته المثلى دائماً أفضل من الأمثل الصحيح تماماً (حد أدنى للتصغير). إذا كان حل الاسترخاء بأكمله صحيحاً بالصدفة، يتم حل المشكلة. بخلاف ذلك، فإن الفجوة بين الاسترخاء والتكامل توجه البحث.
يتم اختيار متغير كسري في حل الاسترخاء ويتم تقسيم المشكلة إلى مشكلتين فرعيتين — واحدة تتطلب تقريب هذا المتغير للأسفل، والأخرى للأسفل. يتم استرخاء كل مشكلة فرعية وحلها، مما يخلق شجرة بحث. يتم تقليم الفروع التي يكون حد استرخائها أسوأ من أفضل حل صحيح تم العثور عليه حتى الآن دون مزيد من الاستكشاف.
المستويات القاطعة هي متباينات خطية صالحة تقطع جزءاً من المنطقة الممكنة لاستخلاص البرمجة الخطية دون إزالة أي نقطة ممكنة صحيحة. إضافة قواطع قوية (قواطع Gomory، متباينات الغطاء، قواطع الـ clique) تشد حد البرمجة الخطية وتقلل عدد العقد التي يجب على الحل استكشافها.
يتم إرجاع أفضل حل صحيح ممكن تم العثور عليه عبر جميع العقد المستكشفة كحل أمثل. يتم الإبلاغ عن فجوة الأمثلية — النسبة المئوية للفرق بين أفضل حل صحيح وأفضل حد متبقٍ؛ فجوة صفرية تشهد على الأمثلية الشاملة. بالنسبة للحالات الكبيرة التي تكون NP-hard، قد ينتهي الحل مبكراً بتسامح فجوة محدد من قبل المستخدم، مع إرجاع حل شبه أمثل مع حد قابل للإثبات.
الأخطاء الشائعة
- الإعلان عن المتغيرات كمستمرة عندما يجب أن تكون صحيحة — أو العكس — ينتج عنه حلول خاطئة بصمت؛ تحقق دائماً من أن أنواع المتغيرات تتطابق مع الواقع المادي للمشكلة.
- صياغة فضفاضة مع فجوة استخلاص برمجة خطية كبيرة تسبب تفرعاً مفرطاً؛ استثمر الوقت في تشديد الصياغة (متباينات قوية، كسر التناظر) قبل الحل.
- تجاهل فجوة التكامل في مخرجات الحل: القيمة الهدف المبلغ عنها هي فقط أفضل حل صحيح تم العثور عليه، وليس بالضرورة الأمثل الشامل ما لم تكن الفجوة صفراً.
- تطبيق البرمجة الصحيحة على مشاكل تكون فيها الدالة الهدف أو القيود غير خطية دون معالجة MINLP المناسبة سيؤدي إلى نماذج غير صحيحة.
- بالنسبة لمشاكل الجدولة أو التوجيه، فإن الفشل في إضافة متباينات صالحة (مثل قواطع الـ clique أو الغطاء) يترك مكاسب أداء كبيرة على الطاولة.
الأسئلة الشائعة
ما الفرق بين البرمجة الصحيحة (IP) والبرمجة الصحيحة المختلطة (MIP)؟
في البرمجة الصحيحة البحتة (IP) يجب أن يكون كل متغير قرار عدداً صحيحاً. في البرمجة الصحيحة المختلطة (MIP)، تكون بعض المتغيرات صحيحة أو ثنائية بينما يُسمح للآخرين بأن يكونوا مستمرين. MIP هو الإطار الأكثر عمومية والأكثر استخداماً في الممارسة العملية، لأن معظم المشاكل الواقعية تمزج بين الخيارات المنفصلة والكميات المستمرة.
لماذا البرمجة الصحيحة NP-hard إذا كانت البرمجة الخطية متعددة الحدود؟
تقوم البرمجة الخطية بالتحسين على متعدد السطوح محدب ويمكن حلها في وقت متعدد الحدود بواسطة طرق السمبلكس أو النقاط الداخلية. إضافة قيود التكامل تحطم هذا التحدب: تصبح المجموعة الممكنة مجموعة محدودة ولكنها قد تكون ضخمة بشكل فلكي من النقاط الصحيحة، ولا يُعرف خوارزمية متعددة الحدود لإيجاد الأفضل بشكل عام. يوفر استخلاص البرمجة الخطية حداً ولكنه لا يوفر حلاً مباشراً.
كيف أعرف ما إذا كان حلي أمثل؟
يقوم الحل بالإبلاغ عن فجوة أمثلية — النسبة المئوية للفرق بين أفضل حل صحيح تم العثور عليه وأفضل حد أدنى متبقٍ. فجوة 0% تشهد على الأمثلية الشاملة. بالنسبة للمشاكل الكبيرة، يمكنك تعيين تحمل فجوة (على سبيل المثال، 1%) وقبول حل شبه أمثل؛ الحد لا يزال يضمن أن الأمثل الحقيقي لا يمكن أن يكون أفضل بأكثر من هذه النسبة.
ما الذي يجعل الصياغة 'محكمة' ولماذا هي مهمة؟
الصياغة المحكمة هي تلك التي يعطي فيها استخلاص البرمجة الخطية حداً قريباً من الأمثل الصحيح، تاركاً فجوة تكامل صغيرة. عندما تكون الفجوة صغيرة، يحتاج التفرع والحد إلى استكشاف عدد أقل من العقد وينتهي بشكل أسرع. إضافة متباينات صالحة مثل قواطع Gomory، أو متباينات الغطاء، أو قواطع الـ clique تشد الصياغة وغالباً ما تكون الطريقة الأكثر تأثيراً لتسريع الحل.
طرق ذات صلة
المصادر
Wolsey, L.A. (1998). Integer Programming. Wiley.
ردمك: 9780471283669تم النسخ.Nemhauser, G.L. & Wolsey, L.A. (1988). Integer and Combinatorial Optimization. Wiley.
ردمك: 9780471359432تم النسخ.