الصيغة القياسية Standard form - بحوث عمليات

مثال (2 - 3): حوٌل مشكلة البرمجة الخطية التالية إلى الصيغة القانونية:
Min??x_0 ?=3x_1-3x_2+7x_3
Subject to:
x_1+x_2+3x_3 ?40
x_1+9x_2-7x_3?50
5x_1+3x_2 =20
|5x_1+8x_3 |?100
x_1,x_2?0 ,x_3 Unrestricted in Sign
الحل:
يتم تحويل مشكلة (L.P) باستخدام عمليات التحويل الأولية المشار إليها أعلاه وكما يأتي:
Max g_0=(-x_0 )=-3x_1+3x_2-7(x_3^ -x_3^ )
Subject to:
x_1+x_2+3(x_3^ -x_3^ ) ?40
-x_1-9x_2+7(x_3^ -x_3^ )?-50
-5x_1-3x_2 ?20
5x_1+8(x_3^ -x_3^ )?100
-5x_1-8(x_3^ -x_3^ )?100
x_1,x_2,x_3^ ,x_3^ ?0
2 – 3- 2 الصيغة القياسية Standard form
تعتبر هذه الصيغة أفضل من الصيغة السابقة لأنها تستخدم في الطريقة العامة المعتمدة في تحليل البرامج الخطية, أي الطريقة المبسطة (Simplex Method) وأن أهم خصائص هذه الصيغة هي:
1 – جميع القيود الواردة في المسألة عبارة عن معادلات ما عدا القيد الخاص بإشارة المتغيرات.
2 – عناصر الطرف الأيمن من كل قيد يكون (?0) أي أن (b_i?0).
3 – جميع المتغيرات تكون أكبر أو مساوية للصفر أي أنها مقيدة (x_j?0).
4 – دالة الهدف تكون من نوع (Maximum) أو (Minimum).
ملاحظة:
يتم تحويل قيود المتباينات إلى مساواة (معادلات) وذلك بإضافة أو بطرح متغيرات تكميلية (slack variable) (s_i?0) إلى الطرف الأيسر من كل قيد وهذه المتغيرات تضاف للقيود من (?) اصغر أو يساوي وتطرح من القيود من نوع اكبر أو يساوي (?), وكما موضح في المثال التالي.
a_1 x_1+a_2 x_2?b?a_1 x_1+a_2 x_2-s_1=b
حيث أن (s_1?0) متغير وهمي ولا يؤثر على الحل.
a_1 x_1+a_2 x_2?b?a_1 x_1+a_2 x_2+s_1=b
تلعب الصيغة القياسية دوراً مهماً في حل مسائل البرمجة الخطية وبصورة عامة أذا كانت لديك مسألة (L.P) كما يأتي:
Max x_0=?_(j=1)^n??c_j x_j ?
Subject to:
?_(j=1)^n??a_ij x_j ??b_i b_i?0,? x?_j?0
…(2.9)
تمثل الصيغة (2.9)أعلاه بالصيغة القياسية كما يأتي:
Max x_0=?_(j=1)^n??c_j x_j ?
Subject to:
?_(j=1)^n??a_ij x_j ?+s_i=b_i i=1,2,…,m
s_i?0,? x?_j?0 (2.10)