المحاضرة العاشرة - اساليب كمية 9/5/2012 - الساعة 9 صباحا الفصل السابع " البرمجة الخطية بالأعداد الصحيحة " يقصد بهذا الأسلوب...
المحاضرة العاشرة - اساليب كمية 9/5/2012 - الساعة 9 صباحا
دى اخر محاضرة فى الاساليب الكمية
وباقى المنهج ملغى عشان دكتور علاء الغرباوى مسافر امريكا
انتهت المحاضرة .. كتبها كريم السيد
الفصل السابع " البرمجة الخطية بالأعداد الصحيحة "
يقصد بهذا الأسلوب أن هناك بعض المشكلات التى تواجهها المنظمات تحتاج لأن يكون الناتج أو الحل فى شكل أعداد صحيحة وليس كسرية ؛ فمثلاً فى مجالى الأجهزة الكهربائية والسيارات ليس من المنطقى أن يتم إنتاج نصف سيارة أو ربع ثلاجة ولكن فى صناعات أخرى مثل صناعة البويات يمكن قبول ذلك نصف كيلو ربع كيلو وهكذا .
س: ما هى أنواع المشاكل التى تواجه البرمجة العددية ؟
* برمجة عددية كاملة أو صافية : وهذا النوع يتطلب أن تكون القيم لجميع المتغيرات فى شكل صحيح وليس كسرى
* برمجة عددية مختلطة : وهذا النوع يسمح لبعض المتغيرات أن تكون فى شكل صحيح والبعض الآخر يكون فى شكل كسرى
س: ما هى منافع هذا الأسلوب ؟
يفيد هذا الأسلوب فى تخفيض التكاليف والحفاظ على الوقت المستخدم فى جدولة الإنتاج
س: ما هى طرق حل مشكلات البرمجة العددية ؟
* أسلوب جومرى
* أسلوب الحد والفرع " ملغى "
مثال صــــ 259
3س1 + 2س2
فى ظل القيود التالية:-
3س1+ س2 < 9
س1 + 3س2 < 7
* س1 + س2 < 1
قيد عدم السالبية س1 , س2 > صفر ؛ أعداد صحيحة
(1) تحويل المتابينات الى متساويات :
3س1 + س2 = 9
س1 = 0 :. س2 = 9
س2 = 0 :. س1 = 3
س1 + 3س2 = 7
س1 = 0 :. س2 = 2 1/3
س2 = 0 :. س1 = 7
-س1 + س2 = 1
س1 = 0 :. س2 = 1
س2 = 0 .: س1 = -1
(2) الرسم البيانى :
(3) إختبار النقاط الركنية :
دالة الهدف كانت 3س1 + 2س2
أ = ( 3 , 0 ) = 3 (3) + 2 (0) = 9
ب = (2.5 ,1.5 ) = 3 (2.5) + 2 (1.5) = 10.5
ج = (1 ,2 ) = 3 (1 ) + 2 (2) = 7
د = (0 , 1 ) = 3( 0 ) + 2 (1) = 2
الحل الأمثل :
س1 = 2.5 وحدة
س2 = 1.5 وحدة
الربح = 10.5 جنية
هذا الحل يعتبر حلاًُ أمثل من وجهة نظر البرمجة الخطية العادية لأنة يستوفى شرط عدم السالبية ولكنة لا يعتبر أمثل من وجهة نظر البرمجة العددية لأنة لا يستوفى سرط عدم الكسرية إذا يجب إستكماله بأسلوب جومرى للوصول للحل الأمثل .
" طريقة جومرى "
تعتبر أفضل الطرق للتعامل مع مشاكل البرمجة العددية ويطلق عليها أيضاً طريقة محذوفات جومرى وهناك ثلاثة حالات أو أنواع من المشكلات التى يمكن حلها بأسلوب جومرى :
(1) حالة التقييد الكامل للمشكلة ويطلق عليها إسم برمجة عددية كاملة أو صافية لأنها لا تسمح أن تكون المتغيرات فى شكل كسرى
(2) حالة التقييد الجزئى للمشكلة ويطلق عليها إسم برمجة خطية مختلطة وذلك لأنها تسمح لبعض المتغيرات أن تكون كسر
(3) حالة الصفر والواحد وهى تهدف لجعل قيم المتغيرات للمشكلة إما صفراً أو واحد
مثال صــــــ 275
3س1 + 4س2
فى ظل القيود
2س1 + 2س2 < 11
-2س1 + 2س2 < 5
قيد عدم السالبية س1 ؛ س2 > صفر
قيد عدم الكسرية س1 ؛ س2 = أعداد صحيحة
(1) تحويل المتباينات إلى متساويات :
2س1 + 2س2 = 11
س1 = 0 .: س2 = 5.5
س2 = 0 .: س1 = 5.5
-2س1 + 2س2 = 5
س1 = 0 .: س2 = 2.5
س2 = 0 .: س1 = 2.5
(2) الرسم البيانى :
(3) إختبار دالة الهدف :
أ = (5.5 , 0 ) = 3 (5.5) + 4 ( 0 ) = 16.5
ب = (1.5 , 4 ) = 3 (1.5 ) + 4 ( 4 ) = 20.5
ج = ( 0 , 2.5 ) = 3 ( 0 ) + 4 ( 2.5 ) = 10
الحل الأمثل :
س1 = 10.5 وحدة
س2 = 4 وحدة
الربح = 20.5 جنية
ويعتبر هذا الحل أمثل فقط من وجهة نظر البرمجة العادية ولكنة ليس أمثل من وجهة نظر البرمجة العددية ولذلك سنطبق طريقة محذوفات جومرى
* يتم حذف جزء من منطقة الحلول
* رسم خطوط رأسية وأفقية من القيم الصحيحة على المحورين
* نرسم محور موازى لكل معادلة من داخل منطقة الحلول بشرط أن يلامس رؤوس المربعات
* إختبار دالة الهدف بالأرقام الجديدة
أ = ( 5 , 0 ) = 3 ( 5 ) + 4 ( 0 ) = 15
ب = ( 2 , 3 ) = 3 ( 2 ) + 4 ( 3 ) = 18
ج = ( 1 , 3 ) = 3 ( 1 ) + 4 ( 3 ) = 15
د = ( 0 , 2 ) = 3 ( 0 ) + 4 ( 2 ) = 8
الحل الأمثل
س1 = 2 وحدة
س2 = 3 وحدات
الربح = 18 جنية
هذا الحل يحقق الشرطين معاً
دى اخر محاضرة فى الاساليب الكمية
وباقى المنهج ملغى عشان دكتور علاء الغرباوى مسافر امريكا
