شرح بحوث عمليات pad351 لطلاب الادارة العامة!!

[المُعلم]

بسم الله الرحمن الرحيم
قواعد حل مسائل البرمجة الخطية بطريقة السمبلكس

- أولاً: بناء النموذج الرياضي للمسألة
* تحديد البدائل
* تحديد الهدف
* التعبير عن دالة الهدف رياضياً كالتالي:
↑د(هـ) تعني: اقصى ربح
↓د(هـ) تعني: ادنى تكلفة
*تحديد القيود المفروضة على شكل متباينات أو متراجحات:
≤ اصغر من او تساوي
≥ اكبر من او تساوي

مراعاة قيد عدم السالبية : جميع المتغيرات القرارية (البدائل) ≥ صفر

- ثانياً مراعاة الشكل الكانونيكال (النظامي)
• يقال للبرنامج الخطي انه موضوع طبقاً للشكل الكانونيكال (النظامي) اذا حقق المواصفات التالية:
1- جميع قيم المتغيرات القرارية موجبة او صفر أي غير سالبة (≥ صفر).
2- جميع قيود البرنامج الخطي موضوعة على شكل اصغر من (≤)
3- تكون دالة الهدف من نوع ايجاد اعلى قيمة ↑د(هـ)
• هذا يعني انه لو كان لدينا برنامج خطي ليس على الشكل الكانونيكال فانه يلزم اجراء بعض التعديلات الجبرية على عناصر البرنامج لتحويله الى الشكل الكانونيكال المطلوب كالتالي:
- بضرب دالة الهدف من نوع ايجاد ادنى قيمة ↓د(هـ) بالمقدار (-1) لتتحول الى ↑د(هـ) ونكمل الحل لايجاد اعلى قيمة د(هـ)، وعند ايجاد الحل الامثل فإن:
قيمة ↓د(هـ) = - ↑د(هـ)
- بضرب طرفي متراجحة القيد التي على شكل اكبر من (≥) بالمقدار (-1) للتحول المتراجحة الى شكل اصغر من (≤)
• الفرق الوحيد بين البرنامج الخطي غير الكانونيكال والكانونيكال هو فقط اشارة قيمة معادلة دالة الهدف بينما القيم التي تاخذها المتغيرات القرارية هي نفسها سواء اتت من حل البرنامج غير الكانونيكال او الكانونيكال، حيث ان البرنامجين متكافئين رياضياً.

ثالثاً: مراعاة الشكل العام القياسي (المعياري)
• تحويل متراجحات القيود المفروضة الى شكل معادلات، ولابد من ادخال متغيرات جديدة:
- اضافية اذا كانت متراجحة القيود على شكل اصغر من (≤)
- مطروحة كانت متراجحة القيود على شكل اكبر من (≥)
• حتى يكون البرنامج الخطي طبقاً للشكل المعياري يجب ان يحقق المواصفات التالية:
1- جميع قيود البرنامج الخطي موضوعة على شكل معادلات، ما عدا قيود المتغيرات القرارية والتي تظل مشروطة بان أي متغير قراري يكون (≥صفر) أي اكبر من صفر.
2- يكون الحد المطلق لمحتوى الطرف الايسر لجميع معادلات القيود قيم موجبة.
3- يشترط ان تكون قيم جميع المتغيرات القرارية موجبة او صفر أي غير سالبة (≥صفر) أي اكبر من صفر.
4- يمكن ان تكون دالة الهدف من النوع ↑د(هـ) او النوع ↓د(هـ)
• المتغيرات الاضافية:
هي متغيرات جديدة تضاف الى المتراجحة التي على شكل اصغر من (≤) لتحويلها معادلة، وحيث ان الطرف الايمن مطلوب ان يكون دائماً اقل من او يساوي الطرف الايسر فانه يجب اضافة مقدار متغير الى الطرف الايمن ليصبح الطرفان متساويان.
• المتغيرات المطروحة:
هي متغيرات جديدة تطرح من المتراجحة التي على شكل اكبر من (≥) لتحويلها الى معادلة، وحيث ان الطرف الايمن مطلوب ان يكون دائماً اكبر من او يساوي الطرف الايسر فانه يجب طرح مقدار متغير من الطرف الايمن ليصبح الطرفان متساويان.
• المتغيرات الوهمية:
هي متغيرات جديدة تضاف الى المتراجحة التي على شكل اكبر من (≥) لتحويلها الى معادلة مع استخدام المتغيرات المطروحة، حيث انه عند استخدام المتغير المطروح سيكون معامله سالباً مما يخل بالشكل المعياري الذي يشترط ان يكون أي متغير قراري موجب او صفر، فيضاف ايضاً المتغير الوهمي للحصول على معامل موجب. كما يتسخدم المتغير الوهمي في حالة ان احد القيود معطى اصلاً على شكل معادلة(=).
رابعاً: تكوين جدول الحل المبدئي للمسالة .
خامساً: فحص امكانية تحسين الحل.
انتهى...