طرق حل نماذج البرمجه الخطيه-الطريقه البيانيه الاولى

طرق حل نماذج البرمجة الخطية
هناك طريقتان اساسيتان لحل نماذج البرمجة الخطية
1- الطرقة البيانية
2- الطريقة البسيطة simplex

اولا" / الطريقة البيانية
1-تصلح هذه الطريقة لحل مشاكل البرمجة الخطية والتي تحتوي على متغيرين اثنين فقط
2-تستخدم هذه الطريقة اذا كانت المتغيرات مقيدة او غير مقيدة بالإشارة

وتعتبر هذه الطريقة من الطرق البسيطة والتي تعطي نتائج دقيقة الا انها طريقة غير كفوءة في معالجة مشكلات البرمجة الخطية في الحياة العملية0
الخطوات
1- نحول القيود من متباينات الى معادلات
2- نعوض بأحد المتغيرات في المعادلة الواحدة بقيمة صفر لاستخراج قيمة المتغير الثاني، ثم نكرر ذلك بالنسبة للمتغير الاخر، وبذلك تصبح لدينا نقطتين لكل معادلة(مستقيم) وبوساطة هاتين النقطتين يمكن رسم المستقيم الذي تمثله المعادلة0
3- بعد رسم جميع المستقيمات التي تمثل القيود يتم تحديد منطقة الحل الممكن والتي تسمى بالمنطقة المحدبة0
4- تحدد منطقة الحل الاساسي الابتدائي المقبول (منطقة الحلول المقبولة) اذ تحقق هذه المنطقة جميع القيود في وقت واحد0
5- تحدد منطقة الحل الامثل التي تمثل احدى النقاط على الاقل الواقعة على تقاطعات المستقيمات الممثلة لمنطقة الحل الاساسي الابتدائي المقبول التي تسمى بنقاط التطرف التي تجعل الارباح اعظم ما يمكن اذا كانت دالة الهدف تعظيم او اقل ما يمكن اذا كانت دالة الهدف متدنية 0
6- نرسم على المستوى الاحداثي (الافقي والعمودي)ليمثل احدهما المتغير X1 وكميته ويمثل الاخر X2 وكميته

انواع الحلول بالطريقة البيانية

1-اسلوب تحديد الحل الامثل
بعد رسم جميع المستقيمات على المستوى نحدد نقاط التطرف (وهي النقاط التي تحيط بمنطقة الحلول الممكنة )ونختبر كل منها بالتعويض عنها في دالة الهدف والنقطة التي تجعل دالة الهدف اكبر ما يمكن ،تكون هي التي تمثل الحل الامثل اذا كانت دالة الهدف من نوع التعظيم Max والعكس بالعكس 0اي ان النقطة التي تجعل دالة الهدف اقل ما يمكن في حالة كون دالة الهدف من النوع المتدني Min هي التي تمثل الحل الامثل 0



مثال:
اوجد الحل الامثل لنموذج البرمجة الخطية
Max Z=4X1+3X2
S.T
5X1+3X2? 30
2X1+3X2? 21
X1, X2 ?0
القيد الاول: نجعله عبارة عن معادلة اي نستبدل علامة الاقل او تساوي بالمساواة
5X1+3X2=30
X1=0 , X2=10 (0,10) X1=6 , X2=0 (6,0)

القيد الثاني
2X1+3X2=21
X1=0 ,X2=7 (0,7)
X1=10.5 X2=0 (10.5,0)



بعد هذا تحدد منطقة الحلول الممكنة وحسب ما هو مطلوب من القيود وهي المنطقة التي تحقق جميع القيود في وقت واحد وهي كما مبين في الشكل اعلاه (A,B,C,D) وبما ان احداثي جميع النقاط معلومة وهي (A,B,C,D) ما عدا النقطة (c) فيتم تحديد احداثيتها على النحو الاتي :

الوسيلة الاولى:
يقتضي هذا الاسلوب انزال اعمدة من النقطة المراد معرفة احداثيتها مثل (C) على المحوريين العمودي والافقي ويتقاطع هذين العمودين مع المحاور يتعين احداثي النقطة (C) على المحور العمودي وعلى المحور الافقي
الوسيلة الثانية:
الاسلوب يتضمن احدى الطرق الرياضية بما ان النقطة (C) تولدت من تقاطع المستقيمين الاول والثاني وهي الحذف او التعويض وعلى النحو التالي:
5X1+3X2=30 ……………..(1)
X1=3 3X2=±21………..(2)±2X1±
3X1 = 9 X1= 9/3 = 3
بعد ذلك نستخرج قيمة المتغير X2 وذلك بالتعويض بقيمة المتغير X1=3 بإحدى المعادلتين اما (1) او (2) وليتم التعويض بالمعادلة الاولى
5(3) + 3X2 = 30 3X2=15 X2=5


اما تحديد نقطة الحل الامثل فبعد ان يتم تحديد المنطقة المحدبة التي هي المحددة بالنقاط (A,B,C,D))) التي تمثل منطقة الحلول الممكنة وبعد ان يتم معرفة احداثي جميع نقاط التطرف يتم التعويض بإحداثي النقاط في دالة الهدف وكما يلي:
نقاط التطرف احداثي نقاط التطرف (X1,X2) قيمة دالة الهدف عند الاحداثيات(X1,X2)
A (0,0) Za=0
B (6,0) Zb=24
C (3,5) Zc=27
D (0,7) Zd=21

بما ان النقطة Cحققت اعلى عائد في دالة الهدف Zc=27 وبما ان دالة الهدف من نوع Max فأن نقطة C تحقق الحل الامثل
ملاحظة:
تكون نقطة واحدة على الاقل من نقاط التطرف تمثل الحل الامثل 0اي معنى هذا ممكن ان تكون هناك نقطتان تمثل الحل الامثل0