البرمجة الخطية
البرمجة الخطية: هي طريقة تعتمد التمثيل البياني على المستوى الإحداثي لإيجاد أكبر قيمة ممكنة (قيمة عظمى) أو أصغر قيمة ممكنة (قيمة صغرى) لاقتران يسمى اقتران الهدف ضمن مجموعة قيود.
مجموعة القيود هي عبارة عن مجموعة من متباينات خطية
منطقة الحلول الممكنة هي منطقة حل مشتركة تتحدد بتمثيل المتباينات الخطية (القيود) وتتحقق فيها أكبر قيمة ممكنة أو أصغر قيمة ممكنة لاقتران الهدف عند رؤوس المضلع الذي يحدد منطقة الحدود الممكنة.
البرمجة الخطية هي طريقة البحث عن الحل الأمثل وتتكون من:
1) اقتران الهدف يكون في صورة:
حيث P هو اسم الاقتران (مثل الربح)، وa و b عددان حقيقيان، و x و y متغيران.
2) القيود: نظام من المتباينات الخطية، تكتب بدلالة المتغيرين y, x، وتحدد منطقة الحلول الممكنة كما في الشكل المجاور.
في المسائل التي تخص الشركات نحتاج إلى أقل كلفة وأكبر ربح ضمن قيود (التمويل, عدد العمال, عدد ساعات العمل, عوامل العرض والطلب, وغيرها) ولحل هذه المسائل نتبع الخطوات الآتية:
1) صياغة الفرضيات وكتابة اقتران الهدف الذي يراد إيجاد قيمته العظمى أو الصغرى، ثم تحديد القيود.
2) تمثيل نظام المتباينات بيانيا، وتظليل منطقة الحلول الممكنة.
3) تحديد إحداثيات رؤوس منطقة الحلول الممكنة.
4) اختيار القيمة العظمى أو الصغرى وفقا لما هو مطلوب في المسألة.
ملاحظة: بعض المسائل الحياتية تتضمن إيجاد أقل تكلفة ممكنة أو أقل كمية مستهلكة فتكون منطقة الحل عندئذ مفتوحة لأن قيودها تفرض ذلك