البرمجه الخطيه

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





في حالة متغيرين في مجموعة حل نظام المتراجحات تكون عادة محددة بمضلع ما . والمبرهنة[م] الرئيسة للبرمجة الخطية هي أن النقطة المثلى (إن وجدت) هي أحد رؤوس المضلع!

يمكن تعميمها لـ n من المتغيرات بـ m من المتراجحات .
لتكن



فإن مسألة البرمجة الخطية تصاغ بالشكل المصفوفي المختصر:




تكون مجموعة حل نظام المتباينات عبارة فوق-مسطح polytope في الفضاء ، وتكون النقطة المثلى إن وجدت أحد رؤوس فوق-المسطح.
وتسمى هذه المنطقة المحصورة بالمسطح بالمجموعة الممكنة feasible set ، وإن كانت المجموعة خالية فإن المسألة غير ممكنة infeasible .

لذا يجب البحث عن النقطة المثلى عبر رؤوس هذا المسطح والتي قد يكون عددها كبيراً عندما تكون n بالمئات أو الآلاف[/center]