البرمجة الخطية — تحسين الأهداف الخطية في ظل القيود الخطية
- قدّمه
- George B. Dantzig
- السنة
- 1947
- النوع
- Mathematical programming / continuous optimization
هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية
ماذا تفعل؟
البرمجة الخطية (LP)، التي رائدها جورج ب. دانتزيغ في عام 1947، هي طريقة رياضية لإيجاد أفضل قيمة لدالة هدف خطية — مثل الحد الأدنى للتكلفة أو الحد الأقصى للربح — تخضع لمجموعة من قيود عدم المساواة والمساواة الخطية. إنها التقنية الأساسية في بحوث العمليات وتدعم تخطيط الإنتاج، وتخصيص الموارد، والخدمات اللوجستية، ومشاكل النظام الغذائي، وسيناريوهات اتخاذ القرار التي لا حصر لها في الهندسة والاقتصاد والعلوم الطبيعية.
الفكرة الحدسية وراء الطريقة
تخيل أنك تدير مصنعًا صغيرًا ينتج منتجين. كل منتج يدر عليك ربحًا معينًا، لكن إنتاجه يستهلك مواد خام محدودة ووقت آلة. تجد البرمجة الخطية المزيج الدقيق للمنتجات الذي يستخلص أقصى ربح من مواردك الثابتة — دون انتهاك أي حد مادي أو تعاقدي. الجزء 'الخطي' يعني أن الربح واستهلاك الموارد يتناسبان بعلاقة خط مستقيم مع الكميات التي تنتجها. تشكل الخيارات الممكنة مضلعًا (في بعدين) أو متعدد السطوح (في أبعاد أعلى)، والإجابة المثلى تقع دائمًا عند إحدى زواياه.
التاريخ
بدأ التطوير المنهجي للبرمجة الخطية في عام 1947 عندما اخترع جورج ب. دانتزيغ، الذي كان يعمل في القوات الجوية الأمريكية، خوارزمية Simplex لأتمتة تخطيط اللوجستيات العسكرية. نشر دانتزيغ النظرية الأساسية في أطروحته عام 1963، والتي لا تزال المرجع القياسي. تناولت الأعمال المستقلة والمتوازية ليونيد كانتوروفيتش في الاتحاد السوفيتي (1939) تخطيط الإنتاج باستخدام أفكار رياضية مماثلة، وحصل كانتوروفيتش على جائزة نوبل في الاقتصاد عام 1975 جزئيًا لهذا المساهمة. تم تسوية السؤال النظري حول قابلية الحل في وقت كثير الحدود بواسطة طريقة الإهليلج لـ Khachian (1979) ولاحقًا بواسطة طريقة النقطة الداخلية لـ Karmarkar (1984)، والتي أثبتت أنها سريعة عمليًا للمشاكل واسعة النطاق. اليوم، تُدمج مُحفزات البرمجة الخطية التجارية ومفتوحة المصدر في تخطيط موارد المؤسسات، وجدولة شركات الطيران، وأنظمة الطاقة في جميع أنحاء العالم.
متى تُستخدم
تكون البرمجة الخطية مناسبة كلما احتجت إلى تحسين كمية تعتمد خطيًا على مجموعة من متغيرات القرار، وجميع القيود خطية. لا تتطلب أي افتراضات توزيعية أو حد أدنى لحجم العينة — إنها نموذج رياضي حتمي، وليست مقدرًا إحصائيًا. تنطبق الطريقة عندما تكون متغيرات القرار مستمرة (القيم الكسرية ذات معنى)؛ إذا كان يجب أن تكون المتغيرات أعدادًا صحيحة أو ثنائية، فستكون البرمجة الصحيحة مطلوبة بدلاً من ذلك. تُستخدم البرمجة الخطية على نطاق واسع في جدولة الإنتاج، ولوجستيات سلسلة التوريد، ومشاكل النظام الغذائي والخلط، وتحسين المحافظ المالية، ومشاكل النقل والتخصيص، وإرسال الطاقة.
الحدود والاعتبارات
- متطلب الخطية: إذا كانت دالة الهدف أو أي قيد غير خطي، فإن نموذج البرمجة الخطية مُصاغ بشكل خاطئ وقد يكون الحل غير صحيح أو غير ممكن.
- متغيرات مستمرة فقط: عندما يجب أن تأخذ متغيرات القرار قيمًا صحيحة أو ثنائية، فإن استرخاء البرمجة الخطية يعطي حدًا أدنى ولكنه ليس حلاً صالحًا؛ يجب استخدام البرمجة الصحيحة.
- حتمي: البرمجة الخطية لا تُنمذج عدم اليقين في المعلمات؛ يلزم البرمجة العشوائية أو التحسين القوي عندما تكون البيانات غير مؤكدة.
- الانحلال والدوران: في حالات نادرة، يمكن لخوارزمية Simplex أن تدور بين قواعد منحلة دون التقارب، على الرغم من أن قواعد مكافحة الدوران (مثل قاعدة بلاند) تحل هذه المشكلة.
لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.
نقاط القوة
- حل أمثل عالمي مضمون: نظرًا لأن المنطقة الممكنة هي متعدد سطوح محدب، فإن أي حل أمثل محلي هو أيضًا حل أمثل عالمي، دون خطر الوقوع في حل دون المستوى الأمثل.
- قابلية توسع عالية: تتعامل المُحفزات الحديثة (HiGHS، Gurobi، CPLEX) مع نماذج تحتوي على ملايين المتغيرات والقيود في ثوانٍ.
- معلومات غنية بعد الحل: توفر أسعار الظل ونطاقات الحساسية رؤى قابلة للتنفيذ حول قيمة الموارد ومتانة الحل دون الحاجة إلى تشغيلات إضافية.
- لا توجد افتراضات توزيعية: البرمجة الخطية نموذج جبري بحت، لذا فهي لا تتطلب خاصية طبيعية أو أي خاصية إحصائية للبيانات.
التطبيقات
- تخطيط الإنتاج: إيجاد المزيج الأمثل للمنتجات الذي يزيد الربح إلى أقصى حد مع احترام حدود سعة الآلات والمواد الخام.
- لوجستيات سلسلة التوريد والنقل: تقليل تكاليف الشحن عبر شبكة من المستودعات والعملاء.
- مشاكل النظام الغذائي والخلط: اختيار كميات المكونات التي تلبي المتطلبات الغذائية بأقل تكلفة.
- تحسين المحافظ المالية: تخصيص رأس المال عبر الأصول لزيادة العائد المتوقع مع مراعاة قيود المخاطر والتنظيم.
- إرسال الطاقة وجدولة شبكة الكهرباء: تقليل تكلفة الوقود مع تلبية الطلب على الكهرباء وحدود سعة المولدات.
- جدولة الموظفين والقوى العاملة: تخصيص ورديات للعمال لتغطية الطلب بأقل تكلفة عمالة.
كيف يعمل
كيف يعمل
تُترجم مشكلة القرار الواقعية إلى رموز رياضية. تحدد متغيرات القرار (الكميات التي يمكنك التحكم فيها)، وتكتب دالة الهدف (ما تريد تعظيمه أو تقليله) كمزيج خطي من تلك المتغيرات، وتكتب كل قيد — حدود الموارد، وسقوف السعة، ومتطلبات الطلب — كعدم مساواة أو مساواة خطية. تتميز مشكلة البرمجة الخطية المُصاغة جيدًا بهدف واضح، وحدود واضحة للمتغيرات، وكل قيد هيكلي مُعبر عنه خطيًا.
يتم تحويل النموذج إلى شكل قياسي أو معياري يمكن للمُحلل معالجته. يتم تحويل عدم المساواة إلى مساواة عن طريق إدخال متغيرات فائضة أو متبقية غير سالبة، ويتم استبدال أي متغير غير مقيد بفرق متغيرين غير سالبين. هذه الخطوة الميكانيكية تنتج الجدول أو التمثيل المصفوفي الذي يعمل عليه الخوارزمية، ولا تغير المشكلة — بل تعيد تشكيلها فقط للحساب.
تبحث الخوارزمية في متعدد السطوح الممكن عن الزاوية المثلى. تقوم خوارزمية Simplex الكلاسيكية بالانتقال من رأس إلى آخر على طول حواف متعدد السطوح، مع تحسين (أو الحفاظ على) الهدف دائمًا، حتى لا يوجد جار محسّن. بدلاً من ذلك، تسلك طرق النقطة الداخلية (الحاجز) مسارًا عبر داخل المنطقة الممكنة على طول مسار مركزي، وهو فعال بشكل خاص للنماذج الكبيرة جدًا. تضمن كلتا العائلتين العثور على حل أمثل عالمي عند وجوده، لأن المنطقة الممكنة محدبة.
تُرجع الخوارزمية القيم المثلى لمتغيرات القرار وقيمة الهدف المثلى، جنبًا إلى جنب مع المتغيرات المزدوجة (أسعار الظل) ونطاقات الحساسية. تُحدد أسعار الظل مقدار تحسن الهدف إذا تم تخفيف قيد ملزم بوحدة واحدة — مما يخبر صانع القرار مباشرةً أين ستكون الموارد الإضافية الأكثر قيمة. تحدد تحليل الحساسية مقدار التغيير الذي يمكن أن يحدث في معامل التكلفة أو قيمة الطرف الأيمن قبل أن يتوقف الأساس الحالي عن كونه أمثل.
الأخطاء الشائعة
- تطبيق البرمجة الخطية عندما تكون القيود أو دالة الهدف غير خطية — سيكون الحل خاطئًا أو سيرفض المُحلل النموذج.
- تجاهل متطلبات التكامل: تقريب حل البرمجة الخطية المستمر إلى أعداد صحيحة لا ينتج عنه بشكل عام حل صحيح أو أمثل للأعداد الصحيحة؛ استخدم البرمجة الصحيحة بدلاً من ذلك.
- نماذج غير ممكنة أو غير محدودة: إذا كانت المنطقة الممكنة فارغة (قيود متعارضة) أو كانت دالة الهدف غير محدودة (قيود حدود مفقودة)، فسيبلغ المُحلل عن فشل — تحقق دائمًا من هيكل النموذج قبل التشغيل.
- معاملة مخرجات البرمجة الخطية كتوصية دون تحليل الحساسية: قد يكون الحل الأمثل تقنيًا على حافة دقيقة حيث يقلب تغيير صغير في البيانات التوصية — يجب دائمًا فحص نطاقات الحساسية.
الأسئلة الشائعة
ما الذي يجعل المشكلة 'خطية' لأغراض البرمجة الخطية؟
يجب أن تكون كل من دالة الهدف وكل قيد خطيًا — مما يعني أن كل حد هو ثابت مضروب في متغير قرار واحد، دون حاصل ضرب المتغيرات، أو أسس، أو دوال غير خطية. إذا كان حتى قيد واحد أو الهدف يتضمن، على سبيل المثال، x مضروبًا في y أو x تربيع، فإن البرمجة الخطية القياسية لم تعد تنطبق ويلزم استخدام مُحلل برمجة غير خطية أو تربيعية.
لماذا يقع الحل الأمثل دائمًا عند زاوية المنطقة الممكنة؟
المنطقة الممكنة المحددة بالقيود الخطية هي متعدد سطوح محدب (أو متعدد الأوجه). دالة الهدف الخطية هي بحد ذاتها خطية، لذا لا يمكن 'سحبها' نحو داخل مجموعة محدبة — فهي تحقق قيمتها القصوى دائمًا على الحدود، وتحديدًا عند رأس (نقطة زاوية). هذه هي الرؤية الهندسية التي تقوم عليها استراتيجية Simplex من رأس إلى رأس.
متى يجب أن أستخدم البرمجة الصحيحة بدلاً من البرمجة الخطية؟
كلما كان يجب أن يأخذ متغير قرار واحد أو أكثر قيمًا صحيحة أو ثنائية (0/1) — على سبيل المثال، ما إذا كان سيتم فتح منشأة (نعم/لا)، وعدد الشاحنات التي سيتم إرسالها (أعداد صحيحة)، أو العناصر التي سيتم تضمينها في اختيار. مجرد حل البرمجة الخطية وتقريب الحل المستمر ليس موثوقًا به: قد تكون الحلول المقربة غير ممكنة أو بعيدة عن الأمثل. تتعامل البرمجة الصحيحة مع التكامل بشكل صحيح، بتكلفة حسابية أكبر.
ماذا تخبرني أسعار الظل؟
يشير سعر الظل (المتغير المزدوج) لقيد ملزم إلى مقدار تحسن قيمة الهدف المثلى إذا تم تخفيف الطرف الأيمن لهذا القيد بوحدة واحدة، مع الحفاظ على كل شيء آخر ثابتًا. على سبيل المثال، يعني سعر الظل 3 لقيد ساعات العمل أن إضافة ساعة عمل إضافية ستحسن الهدف بمقدار 3 وحدات. القيود التي ليست ملزمة لها سعر ظل صفر — فهي لا تحد من الحل الأمثل الحالي.
طرق ذات صلة
المصادر
Dantzig, G.B. (1963). Linear Programming and Extensions. Princeton University Press.
ردمك: 9780691059136تم النسخ.Vanderbei, R.J. (2014). Linear Programming: Foundations and Extensions. Springer.
افتح مرجع DOIتم النسخ.