البرمجة الخطية
•• البرمجة الخطية ( linear programming ) : هي طريقة تعتمد التمثيل البياني على المستوى الإحداثي لإيجاد أكبر قيمة مُمكنة (قيمة عظمى) ، أو أصغر قيمة مُمكِنة (قيمة صغرى) لاقتران يُسمّى الاقتران الهدف ، ضمن مجموعة قيود ، يُمثّل كلٌّ منها متباينة خطية. فبتمثيل المتباينات الخطية (القيود) تتحدّد منطقة حلّ مشتركة لها تُسمّى منطقة الحلول المُمكنة ، وفيها تتحقَّق أكبر قيمة مُمكنة، أو أصغر قيمة مُمكنة للاقتران الهدف عند رؤوس المضلع الذي يُحدّد منطقة الحلول المُمكنة.
•• تُعرَّف البرمجة الخطية أيضًا بأنَّها طريقة البحث عن الحلّ الأمثل ، وتتكوَّن مسألتها ممّا يأتي :
1) الاقتران الهدف : يكون في صورة: P = a x + b y ، حيث :
P : اسم الاقتران (مثل الربح).
a , b : عددان حقيقيان . x , y : متغيران.
2) القيود : نظام من المتباينات الخطية، وهي تُكتَب بدلالة المتغيرين x , y ، وتُحدِّد منطقة الحلول المُمكنة كما في الشكل المجاور.
مفهوم أساسي : إذا وُجدت قيمة عظمى أو قيمة صغرى للاقتران الهدف، فإنَّها تكون عند واحد أو أكثر من رؤوس منطقة الحلول المُمكنة.