الــبــرٍمــجــة الـريـاضـيـة الـخـطيـة

الــبــرٍمــجــة الـريـاضـيـة الـخـطيـة خلال الحرب العالمية الثانية، وبنتيجة محدودية الموارد العسكرية، كلفت الحكومة البريطانية فريقاً من كبار العلماء دراسة مسائل كيفية توزيع مواردها العسكرية، وما يتناسب مع أفضل وضع دفاعي جوي وبري، ولقد أطلق على دراسات هذا الفريق اسم بحوث العمليات أو البحث العملياتي. ثم أخذت هذه التسمية تطلق على كافة الأبحاث والدراسات التي تتعامل مع مسائل البرمجة أو التوزيع ومسائل اتخاذ القرار. وقد حثَّت النتائج المشجعة لفريق بحوث العمليات البريطاني الإدارة العسكرية الجوية الأمريكية على تكوين فريق مشابه للقيام بالدراسات اللازمة في هذا المجال. فقد وجدت هذه الفرق أن أساليب مسائل التفضيل التقليدية، كطريقة مضاريب لاغرانج مثلاً، ليست ذات فائدة كبيرة في حل مسائل البرمجة الخطية، مما استوجب إيجاد أساليب أكثر فاعلية في عام 1947 م حين طور جورج دانتزغ Dantzig عضو الفريق الأمريكي لبحوث العمليات الطريقة المبسطة (السمبلكس) لحل مسألة البرمجة الخطية؛ لكن لم تنشر تفاصيل هذه الطريقة إلا في عام 1956م.

وبعد نشر الطريقة المبسطة (السمبلكس) حدث تسارع كبير في استخدام وتطوير البرمجة الخطية. ومن المشاركات التطويرية المهمة في ذلك المجال أعمال جال Gal التي قام بها وحده أو بمشاركة آخرين معه، إذ قاموا بصَوْغ المسألة الثنائية لمسألة البرمجة الخطية. وفي أيامنا هذه نجد أن البرمجة الخطية تستخدم في مختلف المجالات الصناعية والاقتصادية والخدمية والعسكرية، وحيثما توجد عدة موارد محدودة الكمية مشتركة في تشكيل أو إنتاج سلعة أو تقديم خدمة معينة.

إن المسائل الاقتصادية أو العلمية، والتي يمكن أن تصاغ كمسألة برمجة خطية، يجب أن يتوفر فيها الأساسيات التالية:

1 ـ وجود غاية أو هدف يراد الوصول إلية مثل تحقيق ربح أعظمي أو تحقيق كلفة أصغرية أو اقتصاد أعظمي في الوقت أو الجهد وغير ذلك. ويعبر عن ذلك بتابع رياضي خطي نسميه بتابع الهدف أو تابع الربح في حالة تعظيم، أو بتابع الخسارة في حالة تقليل.

2 ـ وجود عدد كبير من المتحولات أو المجاهيل التي يجب تحديد قيمها للوصول إلى الغاية المطلوبة، وتسمى هذه المتحولات بمتحولات القرار.

3 ـ وجود علاقات ارتباط خطية بين تلك المتحولات وتسمى هذه العلاقات بقيود المسألة.

إذن البرنامج الخطي هو استمثال optimization (تعظيم أو تقليل) دالَّة خطية، تحت قيود خطية. ويمكن رياضياً أن نعبر عن ذلك بالشكل التالي:

حيث المجموعة {I={1,2,…,m تعبر عن مجموعة الأدلة الكلية للقيود، والمجموعة I0هي مجموعة جزئية من I وتعبر عن مجموعة الأدلة التي تصف قيود المساواة للمسألة، والمجموعة -I هي مجموعة جزئية من I وتعبر عن مجموعة الأدلة التي تصف قيوداً أصغر أو تساوي للمسألة، والمجموعة +I هي مجموعة جزئية من I وتعبر عن مجموعة الأدلة التي تصف قيوداً أكبر أو تساوي للمسألة.

نفترض أن التوابع

هي توابع خطية. إنه ليس قيداً إذا افترضنا أن جميع المتحولات (Xi(i=1,….,n ليست سالبة لأنه إذا وجد متحول xjيأخذ قيماً حقيقية لا على التعيين موجبة أو سالبة، يمكننا الاستعاضة عنه بالفرق -xj+- xj حيث المتحولان +xj و -xj يأخذان قيماً غير سالبة . أما إذا وجد متحول سالب من الشكل 0£ xj فإنه يمكننا أيضاً إبداله بمتحول جديد من الشكلyj=-xj.

آلية وضْع البرنامج الرياضي الخطي

لوضع البرنامج الرياضي الخطي يجب اتباع الخطوات التالية:

1 ـ تحديد المتحولات التي يجب علينا إيجاد قيمها (متحولات القرار) وتمثيلها برموز جبرية.

2 ـ تحديد جميع القيود والعلاقات الممكنة التي تربط بين هذه المتحولات، ويعبَّر عن ذلك بمعادلات خطية أو متراجحات بحيث تكون هذه القيود خطية.

3 ـ تحديد تابع الهدف وتمثيله بتابع خطي بالنسبة للمتحولات، وتحديد ما إذا كان الهدف من المسألة تعظيم التابع الهدفي أو تقليله.

ويمكننا أن نكتب البرنامج الرياضي الخطي بطريقة المصفوفات كما يلي:

حيث عدد المتحولات غير المعلومة هو n وعدد القيود m و A مصفوفة القيود m×n و c متجهة عمود بـ n مركبة و b متجهة عمود بـ m مركبة أيضاً و T يرمز إلى المنقول.

إن حل البرنامج السابق يعني إيجاد القيمة الحقيقية التي تعطي التابع قيمة أعظميه (قيمة مثلى للتابع) على منطقة القيود، التي تسمى عادة منطقة الإمكانات. أما إذا أردنا أن نفتش عن النقطة (قيم مثلى للمتحولات) من منطقة الإمكانات، والتي توافق القيمة فنكتب المسألة على الشكل التالي: