البرمجة الصحيحة الحتمية — التحسين الدقيق باستخدام متغيرات القرار الصحيحة
- قدّمه
- Ralph E. Gomory
- السنة
- 1958
- النوع
- Exact combinatorial optimization
- العائلة
- Simulation / optimization
هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية
ماذا تفعل؟
البرمجة الصحيحة الحتمية (DIP) هي نهج تحسين رياضي يجد أفضل حل للمشكلات التي يجب أن تأخذ فيها بعض متغيرات القرار أو كلها قيمًا صحيحة، مع الأخذ في الاعتبار بيانات الهدف والقيود المعروفة بالكامل (الحتمية). إنها الشكل الكلاسيكي غير العشوائي للبرمجة الصحيحة، وهي أساسية في بحوث العمليات والتحسين التوافقي منذ أواخر الخمسينيات.
الفكرة الحدسية وراء الطريقة
العديد من القرارات الواقعية تكون منفصلة بطبيعتها: تفتح منشأة أو لا تفتحها؛ تعين عاملاً لنوبة عمل أو لا تعينه. لا تستطيع طرق التحسين المستمر فرض هذه المتطلبات العددية الصحيحة. تتعامل البرمجة الصحيحة الحتمية مع هذا عن طريق تقييد المتغيرات بالأعداد الصحيحة بينما تكون جميع معلمات المشكلة — التكاليف، القدرات، الطلبات — معروفة بيقين. النتيجة هي حل دقيق ومثبت التحسين بموجب افتراض اليقين هذا، مما يجعلها الصيغة المرجعية التي تُقارن بها المتغيرات العشوائية والمتينة.
التاريخ
نشأت البرمجة الصحيحة من البرمجة الخطية في أواخر الخمسينيات. كانت خوارزمية المستوى القطعي المنهجية الدقيقة الأولى لرالف غوموري عام 1958. بالتزامن مع التفرع والحد (لاند ودويج، 1960)، حددت هذه الأساليب المجال. يميز الصفة 'الحتمية' الصيغة الكلاسيكية عن البرمجة الصحيحة العشوائية (بيرج ولويفو، 1997) وأصبحت مصطلحًا قياسيًا مع انتشار المتغيرات المدركة لعدم اليقين.
متى تُستخدم
استخدم البرمجة الصحيحة الحتمية عندما: (1) تكون متغيرات القرار منفصلة بطبيعتها (تعيين، جدولة، تحديد موقع منشأة، تعبئة صناديق، تصميم شبكة)؛ (2) تكون جميع معلمات المشكلة معروفة بيقين أو يمكن تقديرها بشكل موثوق كقيم نقطية؛ (3) يلزم حل أمثل دقيق بدلاً من تقريب استدلالي. لا تستخدم عندما: تكون المعلمات غير مؤكدة أو تعتمد على سيناريوهات (استخدم البرمجة الصحيحة العشوائية أو المتينة بدلاً من ذلك)؛ يكون حجم المشكلة كبيرًا جدًا بحيث يكون التفرع والحد غير قابل للحساب وتكون الاستدلالات مقبولة؛ تكون المتغيرات مستمرة حقًا (استخدم البرمجة الخطية)؛ أو يجب موازنة أهداف متعددة متعارضة في وقت واحد (استخدم البرمجة الصحيحة متعددة الأهداف).
الحدود والاعتبارات
- تفترض أن جميع معلمات المشكلة معروفة بدقة — يتم تجاهل عدم اليقين في العالم الواقعي بحكم التصميم.
- صعبة NP بشكل عام؛ ينمو وقت الحل في أسوأ الحالات بشكل أسي مع حجم المشكلة.
- قد تتطلب المشكلات التوافقية الكبيرة ساعات أو أيامًا من الحساب حتى مع الحلول الحديثة.
- تؤثر جودة صيغة النموذج (شد القيود، كسر التناظر) بشكل كبير على وقت الحل.
لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.
نقاط القوة
- تضمن حلاً أمثل مثبتًا ضمن افتراضات النموذج الحتمي.
- تتعامل بشكل طبيعي مع هياكل القرارات المنفصلة والتوافقية التي لا تستطيع الطرق المستمرة التعامل معها.
- مدعومة بحلول ناضجة وعالية الكفاءة تجارية ومفتوحة المصدر (CPLEX، Gurobi، SCIP).
- توفر شهادة فجوة المثالية، مما يتيح إنهاء مبكرًا مبنيًا على أسس للمشكلات الكبيرة.
- تُعد الصيغة المرجعية القياسية لمقارنة المتغيرات الاستدلالية والعشوائية.
التطبيقات
- تخطيط الإنتاج وجدولته باستخدام موارد آلات أو عمال منفصلة
- تحديد مواقع المنشآت: تحديد المستودعات أو المصانع التي سيتم فتحها
- توجيه المركبات وجدولة الطواقم في النقل والخدمات اللوجستية
- الميزنة الرأسمالية: اختيار محفظة من مشاريع الاستثمار غير القابلة للتجزئة
- تصميم شبكات الاتصالات بتكاليف ثابتة لإنشاء الروابط
- جدولة موظفي الرعاية الصحية وجدولة غرف العمليات
كيف يعمل
كيف يعمل
تعريف نموذج التحسين: دالة هدف لتقليل (أو زيادة) كمجموع خطي لمتغيرات القرار الصحيحة، تخضع لمجموعة من قيود عدم المساواة أو المساواة الخطية. جميع المعاملات (c، A، b) ثابتة ومعروفة — وهذا ما يجعل الصيغة حتمية. المتغيرات الثنائية (0/1) هي حالة خاصة لقرارات نعم/لا.
الصيغة
\min \; c^\top x \quad \text{s.t.} \quad Ax \leq b,\; x \geq 0,\; x \in \mathbb{Z}^nحل استرخاء البرمجة الخطية (LP)، والذي يسمح مؤقتًا للمتغيرات بأخذ قيم مستمرة. هذا يعطي حدًا أدنى لهدف الأعداد الصحيحة الأمثل. إذا كان حل استرخاء البرمجة الخطية بالفعل ذا قيم صحيحة، فهو أمثل للبرمجة الصحيحة (IP)؛ وإلا يبدأ التفرع.
الصيغة
\text{Solve LP relaxation: } \min \; c^\top x \quad \text{s.t.} \quad Ax \leq b,\; x \geq 0اختيار متغير كسري من حل استرخاء البرمجة الخطية وتقسيم المنطقة الممكنة عن طريق إضافة قيد الحد الأدنى (x_j <= القيمة الصحيحة السفلية) في فرع واحد وقيد الحد الأعلى (x_j >= القيمة الصحيحة العلوية) في الفرع الآخر، مما يولد مشكلتين فرعيتين يتم حلهما بشكل تكراري.
الصيغة
\text{Select fractional variable } x_j^*. \text{ Create two subproblems: } x_j \leq \lfloor x_j^* \rfloor \text{ and } x_j \geq \lceil x_j^* \rceilحل استرخاء البرمجة الخطية لكل مشكلة فرعية للحصول على حد. إذا كان حد العقدة أسوأ من أفضل حل صحيح معروف (المحتجز)، يتم تقليمه. إذا أنتجت المشكلة الفرعية حلاً صحيحًا ممكنًا أفضل من المحتجز، يتم تحديث المحتجز. تشكل العملية شجرة بحث بالتفرع والحد (branch-and-bound).
الصيغة
\text{Compute bounds; prune nodes where LP bound} \geq \text{incumbent. Update best integer solution.}طرق المستوى القطعي (cutting-plane methods) — وأبرزها تخفيضات غوموري (Gomory cuts) — تستمد متباينات خطية إضافية من جدول البرمجة الخطية (LP tableau) التي ترضيها جميع الحلول الصحيحة ولكن يخل بها حل البرمجة الخطية الكسري الحالي. إضافة هذه التخفيضات تشد استرخاء البرمجة الخطية وتقلل التفرع. تجمع الحلول الحديثة بين التفرع والحد مع التخفيضات في إطار التفرع والقطع (branch-and-cut).
الصيغة
\text{Optionally add Gomory cuts or problem-specific valid inequalities to tighten LP relaxation.}تنتهي الخوارزمية عندما يتم تقليم جميع العقد المفتوحة أو تنتج حلولاً صحيحة. المحتجز عند الانتهاء هو الحل الصحيح الأمثل المثبت. تقدم الحلول أيضًا فجوة بين أفضل حد والمحتجز، والتي يمكن استخدامها كمعيار إيقاف للمشكلات الكبيرة.
الصيغة
\text{Return optimal integer solution } x^* \text{ with objective value } z^* = c^\top x^*الأخطاء الشائعة
- يمكن أن يؤدي معالجة المعلمات غير المؤكدة كتقديرات نقطية حتمية إلى حلول ضعيفة الأداء في الممارسة العملية — تحقق من هذا الافتراض قبل تطبيق البرمجة الصحيحة الحتمية.
- تؤدي استرخاءات البرمجة الخطية الضعيفة (فجوات تكامل كبيرة) إلى أشجار تفرع وحد ضخمة؛ استثمر في المتباينات الصحيحة وإعادة الصياغة قبل التوسع.
- يمكن أن يؤدي انفجار المتغيرات الثنائية من صيغ big-M إلى زعزعة استقرار استرخاء البرمجة الخطية عدديًا؛ فضل إعادة صياغة قيود أكثر إحكامًا.
- الخلط بين إمكانية الحل والمثالية عند استخدام تسامح فجوة غير صفري — قم دائمًا بالإبلاغ عن الفجوة جنبًا إلى جنب مع قيمة الهدف.
- تجاهل التناظر في النماذج (مثل، آلات أو عمال متطابقون) يسبب تفرعًا زائدًا؛ أضف قيود كسر التناظر.
الأسئلة الشائعة
ما الذي يميز البرمجة الصحيحة الحتمية عن البرمجة الصحيحة العشوائية؟
في البرمجة الصحيحة الحتمية، تكون جميع معلمات الهدف والقيود ثابتة ومعروفة. البرمجة الصحيحة العشوائية تُنمذج صراحة المعلمات غير المؤكدة عبر توزيعات احتمالية أو سيناريوهات، وتنتج حلولاً تكون متينة أو مثالية في المتوسط عبر تلك السيناريوهات. البرمجة الصحيحة الحتمية أبسط وأسرع في الحل ولكنها تتجاهل عدم اليقين.
هل البرمجة الثنائية حالة خاصة من البرمجة الصحيحة؟
نعم. البرمجة الثنائية (0-1) تقيد كل متغير قرار بـ {0، 1}. إنها الحالة الخاصة الأكثر شيوعًا، وتستخدم لقرارات نعم/لا مثل ما إذا كان سيتم فتح منشأة، أو اختيار مشروع، أو تعيين عامل. البرمجة الصحيحة العامة تسمح بأي قيمة صحيحة غير سالبة.
متى يجب أن أتحول من البرمجة الصحيحة الحتمية إلى طريقة استدلالية؟
عندما تكون شجرة التفرع والحد كبيرة جدًا بحيث لا يمكن استكشافها ضمن حد زمني مقبول وتكون فجوة المثالية من استدلال جيد (خوارزمية جينية، تلدين محاكى، بحث في الجوار الكبير) مقبولة للتطبيق. قم بالإبلاغ عن الفجوة وتبريرها عند الانحراف عن التحسين الدقيق.
هل يمكن للبرمجة الصحيحة الحتمية التعامل مع أهداف أو قيود غير خطية؟
تفترض البرمجة الصحيحة الحتمية الكلاسيكية الخطية (البرمجة الخطية الصحيحة). توجد البرمجة الصحيحة غير الخطية ولكنها أصعب بكثير؛ يمكن خطية العديد من الأشكال غير الخطية من خلال متغيرات ثنائية مساعدة وصيغ big-M. البرمجة التربيعية الصحيحة (QIP) مدعومة مباشرة ببعض الحلول الحديثة.
ما هو الحل الذي يجب أن أستخدمه للبرمجة الصحيحة الحتمية في الممارسة العملية؟
تجارية: Gurobi أو IBM CPLEX للحصول على أفضل أداء. أكاديمية/مفتوحة المصدر: SCIP، CBC (عبر COIN-OR)، أو HiGHS. جميعها تنفذ التفرع والقطع مع معالجة مسبقة تلقائية. لمستخدمي Python، توفر PuLP، Pyomo، أو scipy.optimize.milp واجهات نمذجة مريحة.
طرق ذات صلة
المصادر
Gomory, R. E. (1958). Outline of an algorithm for integer solutions to linear programs. Bulletin of the American Mathematical Society, 64(5), 275-278.
افتح مرجع DOIتم النسخ.Wolsey, L. A. (1998). Integer Programming. Wiley-Interscience, New York.
ردمك: 9780471283669تم النسخ.