النموذج الثنائي لمسائل البرمجة الخطيةDuality in Linear Programming:تحليل الحساسية (Sensitivity Analysis): |
7757
04:45 مساءً
التاريخ: 22-2-2022
|
أقرأ أيضاً
التاريخ: 29-1-2022
15848
التاريخ: 29-1-2022
2397
التاريخ: 27-1-2022
1824
التاريخ: 30-1-2022
3172
|
تحليل الحساسية (Sensitivity Analysis):
من المعروف بأنه في معظم التطبيقات العملية أن بعض المعلومات لا تكون دقيقة إنها هي مقربة أو محاكاة للواقع الفعلي إلى حد حقيقي جداً، وعليه فإن من المهم أن تجد الحل الأمثل مرة أخرى عند إتاحة المعلومات (Information Availability) الأكثردقة حتى يعد حل المسائل، وهذا ممكن أن يحصل بدون إعادة حل المسألة الأصلية من البداية. وفي بعض الأحيان أن بعض المتغيرات يحصل عليه تغير أثناء عملية صياغة المسائلة وقبيل بدأ الحل أو في إحدى مراحل الحل.
بالإضافة إلى ذلك أن بعض القيود لا تكون مساوية تماماً عند الحصول على الحل الأمثل وبالتالي يجب النظر في هذه الإنتاجية من خلال وجود الحل الأمثل، ويمكن أن يضاف قيد آخر بعد حل المسألة نظراً للتطورات التي تحصل في المسألة من البداية.
كل هذه التطورات التي تحصل على نموذج البرمجة الخطية وما شابه ذلك يمكن أن تسمى بتحليل الحساسية . فعلى سبيل المثال:
ولمعرفة أهمية قواعد الحساسية وذلك باعتبار مسألة تطبيقية وذلك على النحو الآتي:
بعد الحصول على الحل الأمثل ترغب إدارة الإنتاج لتحديد هذه الحالة وفقاً للتغيرات الآتية :
1- يرغب قسم تخطيط الإنتاج لزيادة 2 طن مون المواد الخام B ويقابل هذا زيادة المواد الخام A إلى 3 طن.
2- إن الاحتياج إلى المنتج x2 يصبح 3.5 بدلاً من 2 كنهاية للطلب.
3- استخدام الماجة الخام B & A يتطلب دراسة لتقليصها في المادة.
4- معاملات الربح في دالة الهدف وفقاً لقسم الحسابات بالمصنع تتغير إلى 2.5 ، 1.5 د.ل/ طن بدلاً من 3 ، 2 كما هو في المسألة الأصلية.
5- من خلال دراسات السوق وجد أنه لا يمكن استخدام كمية من المواد B ، A أكثر من 3 طن بدلاً من 6 و 8.
نلاحظ أن قائمة المطالب والتي تشمل تغيير المسألة الأصلية تحتاج إلى زمن كثير لحل المسألة 5 مرات على الأقل. وهذه الحالة يعبر عنها بتحليل الحساسية. والسؤال المطروح هل عندما تحصل هذه المتغيرات يبقى الحل الأمثل - هو الحل الأمثل. والجواب يقع في احتمالين لا غير.
1- الحل الحالي يمكن أن يصبح حل خيالي (Infeasible).
2- الحل الحالي يمكن أن يصبح غير مثالي (Nonoptimal).
وهذان الاحتمالات يعتمد على نتيجة حسابات النموذج الأولي - الثنائي. وبناء على المناقشة يمكن اتخاذ إجراءات تحليل الحساسية في الخطوات التالية:
الخطوة الأولى: حل المسألة الأصلية للبرمجة الخطية لإيجاد الحل الأمثل بواسطة طريقة السمبلكس.
الخطوة الثانية: وفقاً للتغيرات المطلوبة في معاملات المسألة تستخدم طريقة حساب النموذج الأولي - الثنائي.
الخطوة الثالثة: إذا كان جدول المصفوفات الجديد لا يطابق الحل الأمثل. أذهب إلى كان الحل المثالي توقف.
الخطوة الرابعة: طبق طريقة السمبلكس الاعتيادية لإيجاد الحل الأمثل للمسألة (الجدول) الجديدة. أو أثبت أن الحل ذو مساحة غير معلومة (Unbounded).
الخطوة الخامسة: طبق طريقة الحل للنموذج الأولي - والثنائي لإيجاد الحل الأمثل الجديد، أو وضح أنه لا يوجد للمسألة حل.
وفقاً للخطوات السابقة نتجه الآن لشرح كيفية تطبيق تحليل الحساسية للمسألة المذكورة أعلاه.
المسألة الأولية:
الخطوة الابتدائية تحول كل القيود من كـ وإضافة المتغير الاحتياطي (Stack variable) للحصول على إشارة التساوي (=).
إن الحل الأمثل للمسألة الأولية يعطي بالجدول التالي:
وكل هذه المعلومات تصلح لبداية تحليل الحساسية كما هو مشار إليه في الخطوة الأولى المذكورة أعلاه.
سوف نشير إلى الحل الأمثل بالحل الحالي (solution Current).
1. حالات الحساسية
1- التغير في الطرف الأيمن في القيود (bj)
إذا حصل تغير في القيد الأول للطرف الأيمن من 6 طن إلى 7 طن فما هو التغير الذي يحصل على الحل الأمثل. يمكن معالجته باستخدام طريقة الحل الأولي - الثنائي وذلك على النحو الآتي:
وبما أن الطرف الأيمن الجديد مازال غير سالب. هذا يعني أن الحل الأمثل يبقى أمثل ويصبح التغير فقط في قيم x5 = 2 , x2 = 2 , x1 = 3
أما إذا فرضنا في الطرف الأيمن تغيرت قيم القيد الأول والثاني من 6 و 8 إلى 7 ، 4 فيمكن حساب الطرف الأيمن الجديد على النحو الآتي:
ولهذا التغير أثر على قيم x6,x5 تحولن إلى قيم سالبة وأصبح الحل خيالي.
والآن يجب أن نطبق طريقة النموذج الأولي - الثنائي لمعالجة مشكلة الخيالية وذلك يوضح القيم في الجدول التالي:
وأن قيمة (z) الجديدة 23/3 وأن الجدول أعلاه يعطي الحل المثالي حيث معادلة Z تمتاز بأن قيمتها كلها 0 ≤ لكن الحل خيالي لأن بعض القيم سالبة وبالتالي فإن تطبيق طريقة السمبلكس للنموذج الأولي - الثنائي تعتبر ضرورية لتحقيق المثالية والحقيقة. ووفقاً لقواعد الطريقة فإن x5 تخرج من متغيرات الحل وx تدخل لمتغيرات الحل والتي يعطي بالجدول التالي:
هذا الجدول يحقق شرط الحل الأمثل والأعداد الحقيقية والحل الأمثل هو:
Z = 7 , x2 = 2 , x1 = 1 حيث أن الحل ذو أعداد حقيقية تحقق في محاولة واحدة فقط.
2- إضافة قيد جديد للمسألة الأولى:
عند إضافة قيد جديد سوف ينتج عنه شرطين لا غيرهما:
1- تحقيق أن الحل الأمثل لا يتغير نتيجة كون القيد مكرر أو داخل منطقة الحل .(Nonbinding or redundant)
2- إن القيد لا يحقق الحل الأمثل ولا الأعداد الحقيقية، وبالتالي نحتاج إلى تطبيق طريقة السمبلكس للنموذج الأولي - الثنائي ولتوضيح هذه الحالات نفرض إضافة القيد التالي:
وهذا القيد يجب أن يضاف إلى النموذج الأول.
وبما أن من الواضح أنه يحقق القيد المضاف ولا داعي لحصول أي تغير يذكر.
أما إذا افترضنا أن القيد المضاف
من الواضح أنه لا يحقق الحل الحالي لأننا لن نعطي حقيقة الأرقام.
ولحل المسألة بعد إضافة القيد الجديد يجب أن نضيف له المتغير الفائض.
فيصبح القيد على النحو الآتي:
من المعروف أنه في الحل الحالي x1 في الحل الأمثل وبالتعويض في معادلة القيد الأول
وبالتالي يصبح القيد الجديد
أو
وأن القيمة السالبة في الطرف الأيمن تعطي عدم توفر شرط الأرقام الحقيقي.
فإذا قلنا أن
فالجدول التالي يوضح المعلومات الملخصة أعلاه:
بطريقة السمبلكس الأولي - الثنائي x7 و4 x مع تدخل والتي يعطي التالي الحل الأمثل.
وهو الحل الأمثل الجديد في محاولة واحدة فقط.
3- التغير في معاملات دالة الهدف
يمكن شرح هذه الظاهرة مباشرة باستخدام المثال السابق حيث:
وتغيرت هذه الدالة
فيمكن حساب القيم الثنائية (y1) (Duol values)
والخطوة الثانية بإعادة حساب معاملات المعادلة z بواسطة أخذ الفرق ما بين الطرف الشمالي والطرف اليمين لقيود المسألة الثنائية.
وهذا يعمل على النحو الآتي:
وبما أن كل معاملات المعادلة 2 ≥ 0 (تعظيم) وهذا . يعني أن دالة الهدف لا تغير من الحل الأمثل الحالي وقيمتها الجديدة.
فإذا فرضنا أن دالة الهدف تغيرت إلى الحالة التالية:
ويمكن التحقق من قيم Z الجديدة :
وبما ان (قيمة سالبة) فيجب X3 ان تدخل الحل وتحقق الحل الأمثل بتطبيق طريقة السمبلكس للنموذج الأول – الثنائي وكما هو موضح بالجداول التالية:
4 - إضافة نشاط جديد (New x).
يمكن المقصود بإضافة متغير جديد وفق المثال الآتي:
Maximize تعظيم
ويعني إضافة متغير مستوى لعمل تغير دالة الهدف. ويمكن اعتبار x7 بأنها موجودة أصلا في المسألة مع توفر معاملات صفر.
وأول اختبار يجب التفكير فيه اختيار النموذج الثنائي المقابل.
وبما ان نلاحظ أن X7 متغير غير أساسي (لا يدخل في الحل) في المسألة الأولية.
النموذج الثنائي غير متغير.
فإن معامل x7 في الحل الأول مثالي.
وهذا يعني ان الحل سوف يتحسن إذا x7 أًبحت (+).
الحل المثالي الحالي يمكن تحسنه بخلق عمود ف الطرف الشمالي للمعادلة Z ومعاملها التي تساوي - 1/4.
والقيد المصاحب بما يحسب على النحو الاتي:
192
|
|
للتخلص من الإمساك.. فاكهة واحدة لها مفعول سحري
|
|
|
|
|
العلماء ينجحون لأول مرة في إنشاء حبل شوكي بشري وظيفي في المختبر
|
|
|
|
|
قسم الشؤون الفكرية يحتفي بإصدار العدد الألف من نشرة الكفيل
|
|
|