الصيغة العامة للبرمجة الخطية - بحوث عمليات

2 – 3 الصيغة العامة للبرمجة الخطية
The General Linear Programming (L.P) problem
من الأمثلة السابقة للبرمجة الخطية, يمكن وضع صياغة ثابتة للبرنامج الخطي تتضمن دالة الهدف (x_0) والقيود التي من الممكن أن تأخذ (?,=,?) والشيء المتعارف عليه هو أن جميع المتغيرات (x_j) المطلوب أتحاذ القرار بشأنها تكون غير سالبة لأنها متغيرات تتصل بالواقع لذلك تصبح النتائج السالبة كميات غير حقيقية.
دالة الهدف objective function
Maximize or Minimize x_0=c_1 x_1+c_2 x_2+?+c_n x_n
Subject to:
a_11 x_1+a_12 x_2+?+a_1n x_n (?,=,?)b_1
a_21 x_1+a_22 x_2+?+a_2n x_n (?,=,?)b_2
?
a_m1 x_1+a_m2 x_2+?+a_mn x_n (?,=,?)b_m
x_1,x_2,…,x_n?0 (2.1)
حيث أن: c_j , b_i , a_ij ثوابت تحدد من سياق المسألة
i=1,2,…,m j=1,2,…,n
x_j المتغيرات المطلوب اتخاذ القرار بشأنها.
ونلاحظ من الصياغة أن أشارة المتغيرات x_j مقيدة بشرط عدم السلبية non – negative وهذا الشرط ضروري لتطوير طريقة حل نموذج L.P.
وبصورة عامة أذا كانت (b_i) تمثل كمية الموارد المحدودة والمطلوب برمجتها لتحقيق هدف معين, فأن (a_ij) تمثل كمية الموارد المحدودة من النوع (i) والمطلوب تخصيصها لكل وحدة واحدة من النشاط أو الفعالية (j), وأن قيمة هذا التخصيص لكل وحدة يعبر عنها (c_j) حيث تمثل (c_j) الربح أو الكلفة.
يمكن وضع الصيغة العامة بالشكل المختصر التالي باستخدام أشارة المجموع أولاً, وباستخدام المصفوفات والمتجهات ثانياً.
دالة الهدف
Max or Min x_0=?_(j=1)^(n )??c_j x_j ?
Subject to
?_(j=1)^(n )??a_ij x_j ? (?,=,?) b_i (i=1,2,…,m)
x_j?0 j=1,2,…,n (2.2)
Max or Min x_0=CX
Subject to:
AX(?,=,?)B (2.3)
x_j?0
حيث أن:
C : تمثل متجه صفي عدد عناصره n
X : تمثل متجه عمودي عدد عناصره n
A : مصفوفة من مرتبة m×n
B : تمثل متجه عمودي عدد عناصره m
أن الخطوط الرئيسية التالية بعد صياغة نموذج البرمجة الخطية هي تحليل النموذج رياضياً, ولكن نظراً لأختلاف صيغ البرمجة الخطية من الضروري تعديل هذه الصيغ لتحديد نموذج حل مناسب والذي سنتطرق إليه لاحقاً. توجد صيغتان هما الشكل أو الصيغة القانونية canonical form والصيغة القياسية أو المعيارية standard form وفيما يلي توضيح للطريقتين.