الصياغة العامة للبرمجة الخطية

الصياغة العامة للبرمجة الخطية :-

Min or Max Z= C1X1 + C2X2 + ….. + CnXn
Subject to


a11x1 + a12x2 + …. + a1nxn ? , = , ? b1
a21x1 + a22x2 + …. + a2nxn ? , = , ? b2




am1x1 + am2x2 + …. + amnxn ? , = , ? bm

x1 , x2 , x3 , ….. , xn ?0

ويمكن كتابة الصيغة الرياضية العامة السابقة بالشكل الاتي :-

Min or Max Z=?_(j=1)^n?cjxj ( j= 1,2, ….. n )
S .to

?_(j=1)^n?aijxj ?(?@=@?) bi (i=1,2,…. M)


xj? 0

حيث ان bi , aij , cj = ثوابت


هناك عدة طرق لحل مشاكل القرار اعلاه منها :-
الطريقة البيانية ( طريقة الرسم البياني ) .
الطريقة المبسطة Simplex Method .




اولاً :- طريقة الرسم البياني :- نعتمد فيها على متغيرين اثنين فقط وذلك لوجود محورين .


مثال (1) :-
Max Z= 6x1+4x2
s.to
2x1+4x2? 20
5x1+3x2 ? 30
x1 ,x2 ? 0
لحل هذا النموذج ووفق هذه الطريقة نتبع الخطوات التالية :-

رسم الشكل البياني :-
نجعل المتغير X1 على المحور الافقي وx2 على المحور العمودي .
تحديد مناطق التمثيل البياني وكما في الشكل الاتي :-




(+,+) (+,-)



(- ,+ ) (- ,-)



القيود :- يتم اتباع الخطوات التالية في رسم القيود
تحويل المتباينات الى معادلات 2x1+4x2 = 20
ولغرض رسم القيد الاول ، نفترض انتاج منتوج واحد فقط هو x2
أي ان x1=0 فأن قيمة x2
2(0) +4x2 =20 ?x2=5
النقطة هي ( 0,5 ) ونرمز لها بالرمز D
اما اذا قررنا انتاج المنتوج X1 فان X2 = 0 و X1= 10
وبذلك ستكون لدينا نقطة احداثيات هي ( 10,0 ) نرمز لها ب B

ويمكن ان نرسم القيد النهائي بنفس الطريقة
R(0,10) ? ( 6,0 ) بـ M

بذلك يمكن تمثل النقاط اعلاه على الشكل التالي
(0,5) D
(10,0) B
(0,10) R
(6,0) M