Linear programming — البرمجة الخطية
البرمجة الخطية هي فرع من البرمجة الرياضية وأحد أساليب بحوث العمليات المستخدمة على نطاق واسع، وهي مكرسة لتطوير نظرية وأساليب حل المسائل المتعلقة بإيجاد القيم القصوى (العظمى أو الدنيا) لدالة خطية في ظل وجود قيود خطية.
تُعد البرمجة الخطية واحدة من أقوى الأدوات وأكثرها استخدامًا لحل مسائل الأمثلية في الاقتصاد والإدارة والتخطيط والخدمات اللوجستية وغيرها من المجالات.
الموضوع والغرض
المهمة الأساسية للبرمجة الخطية هي إيجاد الطريقة الأفضل (المثلى) لتوزيع الموارد المحدودة لتحقيق هدف معين، عندما يمكن التعبير عن كل من الهدف والقيود على استخدام الموارد بعلاقات خطية.
- تتيح البرمجة الخطية حل مسائل عملية مثل:
- التخطيط الأمثل للإنتاج.
- أمثَلَة تدفقات النقل (مسألة النقل).
- التوزيع الأمثل للاستثمارات.
- التقطيع الأمثل للمواد. مسألة التعيين.
الصياغة الرياضية لمسألة البرمجة الخطية
تُصاغ مسألة البرمجة الخطية القياسية على النحو التالي:
المطلوب هو إيجاد قيم متغيرات القرار التي تعظم أو تدني دالة الهدف الخطية. وفي الوقت نفسه، تخضع متغيرات القرار لقيود في شكل نظام من المعادلات الخطية و/أو المتباينات الخطية. كقاعدة عامة، يُضاف شرط عدم سلبية متغيرات القرار (يجب أن تكون قيمها أكبر من أو تساوي الصفر)، وهو ما يمليه غالبًا المعنى المادي أو الاقتصادي للمسألة.
رياضيًا، هذا يعني التعامل مع دوال خطية وأنظمة من المعادلات/المتباينات الخطية.
المفاهيم الأساسية للبرمجة الخطية
- متغيرات القرار (المتغيرات المتحكم بها): هي الكميات التي يجب تحديد قيمها في عملية حل المسألة (على سبيل المثال، حجم إنتاج المنتجات المختلفة، كمية الموارد الموجهة لأغراض مختلفة).
- دالة الهدف: هي دالة خطية من متغيرات القرار، والمطلوب هو تعظيم أو تدنية قيمتها. تعبر هذه الدالة كميًا عن هدف المسألة (على سبيل المثال، إجمالي الربح، التكاليف الإجمالية).
- القيود: هي نظام من المعادلات و/أو المتباينات الخطية التي يجب أن تستوفيها متغيرات القرار. تعكس القيود حدود الموارد، والمتطلبات التكنولوجية، والمهام المخطط لها، وشروط أخرى للمسألة.
- منطقة الحلول الممكنة (Feasible Region): هي مجموعة كل مجموعات قيم متغيرات القرار التي تستوفي جميع قيود المسألة. هندسيًا، في الفضاء متعدد الأبعاد، تمثل منطقة الحلول الممكنة متعدد سطوح محدب (polyhedron)، والذي قد يكون غير محدود أو فارغ.
- الحل الممكن: هو أي مجموعة من قيم المتغيرات تنتمي إلى منطقة الحلول الممكنة.
- الحل الأمثل: هو الحل الممكن الذي تصل عنده دالة الهدف إلى قيمتها القصوى (العظمى أو الدنيا). إذا كان الحل الأمثل موجودًا، فإنه يقع دائمًا على حدود منطقة الحلول الممكنة، في رأس واحد على الأقل من رؤوس متعدد السطوح المحدب لمنطقة الحلول الممكنة (النظرية الأساسية للبرمجة الخطية).
طرق حل مسائل البرمجة الخطية
توجد عدة طرق أساسية لحل مسائل البرمجة الخطية:
- الطريقة البيانية: تُستخدم للمسائل ذات متغيري قرار. تسمح بتصوير منطقة الحلول الممكنة ودالة الهدف بشكل مرئي على المستوى وإيجاد الحل الأمثل من خلال تحليل رؤوس منطقة الحلول الممكنة أو تحريك خط مستوى دالة الهدف.
- طريقة السيمبلكس: خوارزمية تكرارية عالمية طورها جورج دانتزيغ. تنتقل الطريقة بشكل متسلسل من رأس في منطقة الحلول الممكنة إلى رأس مجاور، مع تحسين قيمة دالة الهدف في كل خطوة، حتى يتم العثور على الحل الأمثل. وتعتبر الطريقة الكلاسيكية والأكثر شهرة لحل مسائل البرمجة الخطية.
- طرق النقطة الداخلية: فئة بديلة من الخوارزميات ظهرت بعد طريقة السيمبلكس. تتحرك هذه الطرق نحو الحل الأمثل داخل منطقة الحلول الممكنة، وليس على طول حدودها. هذه الطرق فعالة بشكل خاص لحل مسائل البرمجة الخطية ذات الأبعاد الكبيرة جدًا.
الثنائية في البرمجة الخطية
يمكن ربط كل مسألة برمجة خطية (تسمى المسألة الأولية) بمسألة برمجة خطية أخرى تسمى المسألة الثنائية. ترتبط المسألتان الأولية والثنائية ارتباطًا وثيقًا:
حل إحدى المسألتين يوفر معلومات عن حل الأخرى. تتطابق القيم المثلى لدوال الهدف في كلتا المسألتين (إذا كانت موجودة). للمتغيرات في المسألة الثنائية تفسير اقتصادي مهم — فهي تتوافق مع الأسعار الظلية (أو التقييمات الثنائية) للموارد، حيث توضح مدى تغير القيمة المثلى لدالة الهدف في المسألة الأولية عند حدوث تغيير طفيف في القيد على المورد المقابل.
تطبيقات البرمجة الخطية
تجد البرمجة الخطية تطبيقات واسعة في:
- الاقتصاد والأعمال (تخطيط الإنتاج، الخدمات اللوجستية، التمويل، التسويق).
- الصناعة (أمثَلَة العمليات التكنولوجية، إدارة المخزون، تقطيع المواد).
- النقل (أمثَلَة المسارات، الجداول الزمنية).
- الزراعة (أمثَلَة المساحات المزروعة، حصص الأعلاف).
- الطاقة (أمثَلَة تحميل قدرات التوليد).
المراجع
- دانتزيغ، ج. البرمجة الخطية، تطبيقاتها وتعميماتها. — موسكو: بروغريس، 1966.
- يودين، د. ب.، غولشتين، ي. ج. البرمجة الخطية (النظرية، الطرق والتطبيقات). — موسكو: ناوكا، 1969.
- Taha, Hamdy A. Operations Research: An Introduction. — Pearson. (10th ed., 2017)
- Hillier, Frederick S.; Lieberman, Gerald J. Introduction to Operations Research. — McGraw-Hill Education. (11th ed., 2021)
انظر أيضًا
- بحوث العمليات
- الأمثَلَة
- دالة الهدف
- القيود
- منطقة الحلول الممكنة
- الحل الأمثل