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

البرمجة الخطية الحتمية — البرمجة الخطية الكلاسيكية بمعاملات مؤكدة

قدّمه
George B. Dantzig
السنة
1947
النوع
Deterministic mathematical optimization
العائلة
Simulation / optimization

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

حجم الخط

ماذا تفعل؟

البرمجة الخطية الحتمية (DLP) هي الشكل الكلاسيكي للبرمجة الخطية التي تكون فيها جميع معاملات دالة الهدف، ومعاملات القيود، وقيم الطرف الأيمن معروفة على وجه اليقين. إنها تجد التخصيص الأمثل للموارد لتعظيم أو تقليل هدف خطي يخضع لقيود خطية، مما يوفر حلاً دقيقًا وقابلاً للتكرار في ظل بيانات ثابتة ومؤكدة.

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

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

التاريخ

تمت صياغة البرمجة الخطية رسميًا بواسطة جورج ب. دانتزيغ في عام 1947 مع تطوير خوارزمية السمبلكس أثناء العمل للقوات الجوية الأمريكية. أصبحت أطروحة دانتزيغ عام 1963 المرجع الأساسي. ظهرت الصفة 'الحتمية' مع تقديم متغيرات البرمجة الخطية العشوائية (Dantzig and Beale، 1950s–1960s) للتمييز بين النموذج الأصلي ذي المعاملات المؤكدة وامتداداته الاحتمالية.

متى تُستخدم

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

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

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

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

نقاط القوة

  • ضمان حل أمثل عالمي لأي حالة برمجة خطية ممكنة ومحدودة بسبب التحدب.
  • قابلية توسع عالية - الحلول الحديثة تتعامل مع ملايين المتغيرات والقيود في ثوانٍ.
  • توفر المتغيرات المزدوجة وتحليل الحساسية تفسيرًا اقتصاديًا غنيًا لأسعار الظل والنطاقات.
  • صياغة شفافة وقابلة للتدقيق: كل افتراض واضح في مصفوفة القيود.
  • نظام بيئي ناضج للبرامج (CPLEX، Gurobi، HiGHS، GLPK) مع تطبيقات موثوقة ومختبرة جيدًا.
  • إشارة واضحة للنجاح/الفشل في قابلية الحل: يكشف عدم القابلية للحل عن سوء صياغة النموذج على الفور.

التطبيقات

  • جدولة الإنتاج والتصنيع بسعات موارد ثابتة وطلب معروف.
  • النقل والخدمات اللوجستية: إيجاد طرق الشحن بأقل تكلفة عبر شبكة.
  • مشاكل النظام الغذائي والخلط: صياغة مخاليط غذائية أو كيميائية بأقل تكلفة تلبي قيود التركيب.
  • تحسين المحافظ المالية في ظل قيود العائد الخطي والميزانية.
  • تخطيط أنظمة الطاقة: الإرسال الأمثل لوحدات توليد الطاقة بتكاليف وسعات معروفة.
  • تصميم شبكة سلسلة التوريد عندما يُعامل الطلب وأوقات التسليم كثوابت معروفة.

كيف يعمل

كيف يعمل

1

عرّف متغيرات القرار x (مثل كميات الإنتاج، كميات التدفق)، ودالة الهدف c^T x للتقليل أو التعظيم، ومجموعة القيود Ax <= b مع x >= 0. تُعامل جميع المعاملات في c و A و b على أنها ثوابت دقيقة ومعروفة - وهذا ما يجعل النموذج حتميًا. اكتب البرمجة الخطية بالشكل القياسي: min c^T x subject to Ax = b, x >= 0.

الصيغة
\min_{x} \; c^\top x \quad \text{s.t.} \quad Ax \leq b, \; x \geq 0
2

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

3

حل البرمجة الخطية باستخدام خوارزمية السمبلكس (التحويل عبر حواف المضلع المحدب نحو الرأس الأمثل) أو طريقة النقطة الداخلية (اتباع مسار عبر داخل منطقة الحل الممكن). كلا النهجين يستغلان تحدب مجموعة الحل الممكن وخطية الهدف، مما يضمن أن أي حل أمثل محلي هو حل أمثل عالمي. الحلول الحديثة (CPLEX، Gurobi، HiGHS) تتعامل مع ملايين المتغيرات والقيود بكفاءة.

4

يعيد الحل متجه القرار الأمثل x* وقيمة الهدف المثلى c^T x*. نظرًا لأن منطقة الحل الممكن هي مضلع محدب والهدف خطي، فإن الحل الأمثل يتحقق دائمًا عند رأس (حل أساسي ممكن). سجل x* وتحقق من أنه يلبي جميع القيود، ثم قم بترجمته مرة أخرى إلى مصطلحات إدارية (مثل الوحدات المراد إنتاجها، المسارات المراد استخدامها).

الصيغة
x^* = \arg\min \{ c^\top x : Ax \leq b,\; x \geq 0 \}
5

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

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

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

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

ما الذي يجعل البرمجة الخطية 'حتمية' بدلاً من 'عشوائية'؟

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

هل خوارزمية السمبلكس فعالة دائمًا؟

في الممارسة العملية، نعم - تحل خوارزمية السمبلكس تقريبًا جميع مشاكل البرمجة الخطية الواقعية بسرعة فائقة. نظريًا، يمكن أن تستغرق وقتًا أسيًا في أسوأ الحالات (أمثلة Klee–Minty)، ولكن طرق النقطة الداخلية (مثل خوارزمية Karmarkar) تعمل في وقت متعدد الحدود وتتنافس معها في الحالات الكبيرة جدًا.

هل يمكنني استخدام البرمجة الخطية الحتمية إذا كان يجب أن تكون بعض متغيرات قراري أعدادًا صحيحة؟

لا. إذا كان يجب أن تكون المتغيرات صحيحة (مثل عدد الآلات المراد شراؤها)، فإن النموذج يصبح برنامجًا صحيحًا مختلطًا أو صحيحًا بحتًا. يمكن أن يؤدي حل استرخاء البرمجة الخطية والتقريب إلى انتهاك القيود أو تفويت الحل الأمثل الصحيح؛ استخدم حلاً مخصصًا للبرمجة الصحيحة المختلطة بدلاً من ذلك.

كيف تساعد أسعار الظل بعد الحل؟

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

متى يجب أن أقوم بالترقية من البرمجة الخطية الحتمية إلى البرمجة الخطية القوية أو العشوائية؟

قم بالترقية عندما يكون عدم اليقين في المعاملات غير تافه وتكون تكلفة حل غير قابل للحل أو ضعيف في ظل قيم المعاملات الفعلية كبيرة. إذا كان انحراف بنسبة 10-20٪ في معامل رئيسي سيغير الحل المفضل أو يسبب انتهاكًا للقيود، فإن افتراض اليقين في البرمجة الخطية الحتمية قوي جدًا.

طرق ذات صلة

المصادر

  1. Dantzig, G. B. (1963). Linear Programming and Extensions. Princeton University Press, Princeton, NJ.

    ردمك: 9780691059136
    تم النسخ.
  2. Linear programming. Wikipedia.

    افتح مرجع المنشور
    تم النسخ.