تحليل مسائل البرمجة الخطية

2 – 4 تحليل مسائل البرمجة الخطية
Analysis of Linear Programming Problems
يتم تحليل مسائل البرمجة الخطية من أجل تحديد قيم المتغيرات المطلوب اتخاذ القرار بصددها ( أي تحديد قيم ? x?_j) والتي تعٌظم أو تقٌلل قيمة دالة الهدف, باستخدام الطريقة البيانية في حالة وجود متغيرين أو باستخدام الطريقة العامة لتحليل البرامج الخطية (Simplex method) عند وجود متغيرين فأكثر. ولكن قبل التطرق إلى طرق الحل لا بد من تعريف بعض المصطلحات الخاصة بحل مسائل البرمجة الخطية.
2 – 4 - 1 الحل المقبول Feasible Solution
الحل المقبول هو متجه {x=(x_1,x_2,…,x_n)} التي تحقق كافة القيود الواردة في المسألة, بعبارة أخرى هو قيم المتغيرات (x_j) حيث (j=1,2,…,n) التي تحقق كافة القيود الواردة في المسألة.
?_(j=1)^n??a_ij x_j (?,=,?)b_i ? i=1,2,…,m
x_j?0 j=1,2,…,n (2.11)
2 – 4 - 2 الحل الأساسي المقبول Basic Feasible Solution(B.F.S)
يسمى بالحل المقبول أذا كان عدد المتغيرات الموجبة فيه لا يتجاوز عدد القيود (m) الواردة في المسألة .


2 – 4 - 3 الحل الأساسي المقبول غير المفكك Non – degenerate يكون الحل الأساسي المقبول حلاً غير مجزأً أذا أحتوت بالضبط على (m) من المتغيرات الموجبة (x_j>0), أي أن عدد المتغيرات يساوي عدد المعادلات.
2 – 4 - 4 الحل الأمثل Optimal Solution
وهو الحل الذي يحقق كافة القيود إضافة إلى ذلك يجعل قيمة دالة الهدف في نهايتها العظمى أو في نهايتها الصغرى.
2 – 4 – 5 المجموعات المحدبة Convex sets التوافيق المحدبة للنقاط (u_1,u_2,…,u_n) هي عبارة عن النقطة التي تحقق العبارة التالية:
u=?_1 u_1+?_2 u_2+?+?_n u_n (2.12)
بحيث أن:
?_(i=1)^n??_i =1 ?_i?0
حيث (?_i) ثوابت المجموعة الجزئية (c) للمجال (E_n) هي مجموعة محدبة أذا وفقط أذا (iff) كان لكل زوج من النقاط (u_1,u_2 ) التي تقع في (c) لها توافيق محدبة وأن أي توفيق محدب (u=?_1 u_1+?_2 u_2) يقع في (c) أيظاً.