الطريقة البيانية Graphical Method

نظرية (2 – 4):
إذا كانت x=(x_1,x_2,…,x_n) نقطة متطرفة للمجموعة (k), فأن المتجهات المكونة من العناصر الموجبة (x_i) تشكل مجموعة مستقلة خطياً.
البرهان:
نفرض أن المعاملات غير الصفرية هي أول (k) في المعاملات بحيث:
?_(i=1)^k??x_i p_i=0?
نستخدم لبرهان هذه النظرية طريقة التناقض (Contradiction) لذا سنفرض بأن (p_1,p_2,…,p_k) معتمدة خطياً, ومن ثم فأن هناك توافيق خطية لهذه المتجهات والتي تساوي متجه صفري.
?d_1 p?_1+?d_2 p?_2+?+d_k p_k=0 (2.18)
على الأقل واحد من (d_i?0) ومن فرض النظرية نحصل على:
?x_1 p?_1+?x_2 p?_2+?+x_k p_k=0 d>0 (2.19)
بضرب المعادلة (2.18) في (d) وطرح النتيجة من المعادلة (2.19) نحصل على المعادلتين التاليتين:
?_(i=1)^k??x_i p_i+d?_(i=1)^k??d_i p_i ?=p_0 ?
?_(i=1)^k??x_i p_i-d?_(i=1)^k??d_i p_i ?=p_0 ?
…(2.20)
لذا فأننا حصلنا على الحلين التاليين لقيود مسألة البرمجة الخطية والتي لا تشترط أن تكون حلول مقبولة وهذين الحلين هما:
x_1=(x_1+dd_1,x_2+dd_2,…,x_k+dd_k,0,…,0)
x_2=(x_1-dd_1,x_2-dd_2,…,x_k-dd_k,0,…,0) (2.21)
وبسبب أن (x_i>0) نجعل (d) اصغر ما يمكن بحيث تبقى (d) موجبة, لتجعل المركبات الأولى للمجموعة (k) من كلا النقطتين (x_1) و (x_2) موجبة, لذا فأن (x_1) و (x_2) حلول مقبولة. ولكن:
x=1/2 x_1+1/2 x_2
وهذا يناقض الفرضية التي تقول بأن (x) قيمة متطرفة ( لأن القيمة المتطرفة لا يمكن التعبير عنها كتوفيق محدب والنقطة x أعلاه تم التعبير عنها بتوفيق محدب ). لذا فأن فرضية الأعتماد والخطية للمتجهات (p_1,p_2,…,p_k) مستقلة خطياً.
2 – 5 الطريقة البيانية Graphical Method
تعتبر الطريقة البيانية طريقة خاصة لإيجاد الحل الأمثل لمسائل البرمجة الخطية لأنها تقتصر على تحليل المسائل المتضمنة متغيرين, ولكن بالرغم من ذلك فهي تعرض الأساس العلمي للطريقة العامة المستخدمة في تحليل البرامج الخطية.
تستند هذه الطريقة على تحديد منطقة الحل المقبول (Feasible Solution Space) وهي منطقة مغلقة بكافة القيود الواردة في مسألة البرمجة الخطية ثم تحديد النقطة ( النقاط ) المتطرفة (Extreme Points) التي تحقق القيمة العظمى أو الصغرى لدالة الهدف.
تعتمد الطريقة البيانية على الخطوات الأساسية التالية:
1 – اعتبار المتباينات في حالة مساواة ثم ترسم الخطوط المستقيمة المتمثلة لهذه القيود وبعد ذلك تطبق حالة التباين لأنصاف المستويات والتي تحقق أشارة كل متباينة حيث تقع جميع المعادلات في الربع الأول لأن (x_j?0).
2 – المضلع الناتج من تقاطع أنصاف المستويات يمثل منطقة الحلول المقبولة.
3 – نعين المستقيم الممثل لدالة الهدف بأعتباره يبتدأ من نقطة الأصل أو عندما تكون (x_0=0).
4 – نحدد نقطة أو نقاط متطرفة في منطقة الحل المقبول والتي تحقق القيمة العظمى أو الصغرى لدالة الهدف.