الفصل الرابع 
البرمجة الخطية
العناوين الرئيسة 
1- البرمجة الخطية (النماذج العامة)
1-1-مقدمة في البرمجة الخطية
-2-1- طرائق البرمجة الخطية
2 - البرمجة الخطية (مسائل النقل)
1-2- نموذج مصفوفة النقل
-2-2- دالة الهدف
-3-2- نماذج مصفوفة النقل
4-2- حل مسائل النقل
3- البرمجة الخطية (مسائل التخصيص)
-1-3- الشكل العام
-2-3- الشروط
3-3- الطريقة الهنغارية في حل مسائل التخصيص
4-3- مسألة البائع المتجول 

الأهداف:
يهدف هذا الفصل إلى : 
1- توضيح مفهوم وأساسيات البرمجة الخطية.
2 ـ شرح طرائق البرمجة الخطية (الطريقة البيانية والسمبلكس).
3ـ شرح مسائل النقل وبيان أهميتها في إدارة العمليات الإنتاجية.
4 - توضیح استخدامات البرمجة الخطية (مسائل التخصيص) في إدارة العمليات الإنتاجية.

1. البرمجة الخطية (النماذج العامة)
1-1- مقدمة في البرمجة الخطية
تعد البرمجة الخطية من أكثر الطرائق الكمية المستخدمة في حل مسائل اتخاذ القرارات، وهي أسلوب رياضي يبحث عن أفضل الطرائق لاستخدام الموارد المتاحة بما يحقق أفضل كفاية للمنظمات. وأهم المسائل التي تعالج بهذه الطريقة ما يلي :  
1 - مسائل تخطيط الإنتاج والطاقة الإنتاجية.
2 - مسائل المزيج ذو الكلفة الأقل للإنتاج.
3 - مسائل النقل والتخصيص وتوزيع المنتجات.
4- مسائل التوظيف وتنظيم المزيج التسويقي الأفضل.
ويتم معالجة تلك المسائل في ظل توافر الشروط التالية :
1 ـ وجود هدف نهائي واحد A Single Objective، ويأخذ شكلين تعظيم النتائج (في حالة الأرباح)، وتقليل النتائج (في حالة التكاليف).
2 ـ وجود قيود معينة Restrictions على المتغيرات التي تتضمنها المشكلة تؤثر في تحقيق الهدف النهائي (قيود الموارد، الزمن ، المساحات، الخ..).
3 ـ وجود علاقة تناسبية Proportionality تتمثل بعلاقة خطية بين المتغيرات الموجودة في المسألة المراد حلها يمكن التعبير عنها بخط مستقيم.
4 ـ خاصة الإيجابية No negativity أي أن قيم المتغيرات التي نحصل عليها بنتيجة الحل يجب أن تكون موجبة (تمثل وحدات حقيقة).
صياغة نموذج البرمجة الخطية : 
لحل مسائل البرمجة الخطية يتم صياغة المسألة موضوع الدراسة على شكل نموذج رياضي يعبر عن معطيات المسألة، ويتم بناء النموذج باتباع الخطوات التالية:
1 ـ تحديد دالة الهدف للمسألة المدروسة (تعظيم ، تقليل) وذلك بعد تحديد مساهمة كل متغير (مقدار الربح، مقدار التكاليف) في دالة الهدف.
-2 تحديد العلاقة بين المتغيرات والهدف المراد تحقيقه، وكذلك بين المتغيرات والقيود الموضوعة على هذه المتغيرات.  
2-1  طرائق البرمجة الخطية 
إن الطرائق المتبعة في البرمجة الخطية عديدة وهي التالية :
طرائق عامة (الطريقة البيانية، السبمبلكس).
طرائق خاصة (طريقة النقل التخصيص).
1-2-1- الطريقة البيانية 
تعد الطريقة البيانية من أبسط طرائق البرمجة الخطية التي تهدف إلى إيجاد الحلول المناسبة للمسائل الإدارية المختلفة (مسائل الإنتاج مسائل التسويق، مسائل الأفراد)... وبخاصة تلك المتعلقة باتخاذ القرارات ذات الموضوعات الفنية والمعايير الكمية. ويقتصر استخدام هذه الطريقة على حالات خاصة كتلك التي لا يزيد فيها عدد المتغيرات عن ثلاثة ، وذلك بسبب صغر تمثيل المشكلة بالرسم في حالة ازداد عدد المتغيرات عن ثلاثة.
تتألف الطريقة البيانية من الخطوات التالية :
1 - يتم تحديد دالة الهدف على شكل معادلة رياضية تمثل المتغيرين للمشكلة المراد حلها.
2 - يتم تحديد قيود المسألة على شكل متباينات .
3 - يرسم محورين متعامدين المحور الأفقي يمثل المتغير (س) والمحور العامودي يمثل المتغير (ص). 
4 - نرسم المستقيمات التي تحددها المتباينات ونحدد المنطقة المقبولة والمنطقة المرفوضة (تحديد منطقة الحل).
5- تحديد الحل الأمثل للبرنامج الخطي. 
استخدامات الطريقة البيانية
تستخدم الطريقة البيانية في الحالتين التاليتين: 
1- حل مسألة مزيج الإنتاج (تعظيم الربح).
مثال (4-1) 
تواجه إدارة مصنع الأدوات المنزلية مشكلة اتخاذ القرار حول مزيج الإنتاج الذي يحقق لها أكبر ربح ممكن وحيث أن لديها الإمكانية لإنتاج البرادات والغسالات. وإنتاج كـل نـوع يتطلب المرور في قسمي الإنتاج، وهما (قسم إنتاج الأجزاء ، قسم التجميع). ويحتاج إنتاج كل نوع لزمن معالجة في كلا القسمين وذلك كما هو موضح بالجدول التالي:
 
ولقد كانت الطاقة الإنتاجية المتاحة القصوى لقسم إنتاج الأجزاء 12,000 ساعة. والطاقة الإنتاجية المتاحة القصوى لقسم التجميع 3500 ساعة. والربح الناتج عن بيع الغسالة الواحدة (100) دينار والربح الناتج عن بيع البراد الواحد (125) دينار.
المطلوب :
ما هو القرار المناسب المتعلق بتحديد مزيج الإنتاج الذي يحقق أقصى ربح ممكن لهذه الشركة. 
الحل :
يتمثل الحل بالخطوات التالية : 
1ـ تلخيص المشكلة على الشكل التالي :
نفرض ان (س) تمثل الكمية التي تصنع من الغسالات .
نفرض ان (ص) تمثل الكمية التي تصنع من البرادات .
2ـ تابع الهدف (الربح) :  
 
 
من خلال الرسم البياني نلاحظ ان منطقة الحل تقع تحت الخط (أ، ب)  
  

5 ـ تمثل جميع القيود بيانيا على  رسم واحد (أي تمثيل تابع للهدف) 
 
من الرسم البياني نلاحظ ان نقطة الحل المثالية تتمثل بالنقطة هـ (نقطة تقاطع القيد الاول مع القيد الثاني) وتُحسب على الشكل التالي :  
 
وبما ان القيدين متساوية عند النقطة (هـ) فاننا نحصل على المتراجحة التالية :

 وبتعويض هذه القيمة في إحدى القيدين نحصل على قيمة س = 225، وبالتعويض في تابع الهدف نحصل على الربح التالي :  
هـ  ↑ =  100 (225)  + 125 (250) = 53.750 دينار .