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

Posted by: w6

Linear Programming

البرمجة الخطية هي فرع من الاستمثال الرياضي وهذا الفرع يبحث في إيجاد النقاط المثلى لدالة معينة وفق قيود (constraints) معينة.
البرمجة الخطية هي حالة خاصة جداً بحيث أن الدالة هي خطية والقيود عبارات عن متراجحات خطية .
ولها تطبيقات كثيرة ،
مثلاً في متغيرين x_1,x_2 نريد أن نجد أصغر قيمة للمقدار c_1x_1 + c_2 x_2 ولكن بشرط أن يحقق الحل المتراجحات التالية:
\begin{array}{l}a_{11}x_1+a_{12}x_2 \leq b_1 \\a_{21}x_1+a_{22}x_2 \leq b_2 \\a_{31}x_1+a_{32}x_2 \leq b_3\end{array}


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

يمكن تعميمها لـ n من المتغيرات بـ m من المتراجحات .
لتكن c,x \in \mathbb R^n , b \in \mathbb R^m, A \in \mathbb R^{m \times n}

فإن مسألة البرمجة الخطية تصاغ بالشكل المصفوفي المختصر:
\begin{array}{ll}\mbox{minimize} & c^T x \\ \mbox{subject to} & Ax \leq b \end{array}

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

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

خوارزمية السبملكس (simplex algorithm) هي خوارزمية لحل مسائل البرمجة الخطية ، ولذا كانت طريقة simplex طريقة منظمة للبحث عن النقطة المثلى. وقد طورها George Dantzig عام 1948 .

This entry was posted on 11:48 ص . You can leave a response and follow any responses to this entry through the الاشتراك في: تعليقات الرسالة (Atom) .

0 التعليقات

إرسال تعليق

رسالة أحدث رسالة أقدم