x
هدف البحث
بحث في العناوين
بحث في المحتوى
بحث في اسماء الكتب
بحث في اسماء المؤلفين
اختر القسم
موافق
تاريخ الرياضيات
الاعداد و نظريتها
تاريخ التحليل
تار يخ الجبر
الهندسة و التبلوجي
الرياضيات في الحضارات المختلفة
العربية
اليونانية
البابلية
الصينية
المايا
المصرية
الهندية
الرياضيات المتقطعة
المنطق
اسس الرياضيات
فلسفة الرياضيات
مواضيع عامة في المنطق
الجبر
الجبر الخطي
الجبر المجرد
الجبر البولياني
مواضيع عامة في الجبر
الضبابية
نظرية المجموعات
نظرية الزمر
نظرية الحلقات والحقول
نظرية الاعداد
نظرية الفئات
حساب المتجهات
المتتاليات-المتسلسلات
المصفوفات و نظريتها
المثلثات
الهندسة
الهندسة المستوية
الهندسة غير المستوية
مواضيع عامة في الهندسة
التفاضل و التكامل
المعادلات التفاضلية و التكاملية
معادلات تفاضلية
معادلات تكاملية
مواضيع عامة في المعادلات
التحليل
التحليل العددي
التحليل العقدي
التحليل الدالي
مواضيع عامة في التحليل
التحليل الحقيقي
التبلوجيا
نظرية الالعاب
الاحتمالات و الاحصاء
نظرية التحكم
بحوث العمليات
نظرية الكم
الشفرات
الرياضيات التطبيقية
نظريات ومبرهنات
علماء الرياضيات
500AD
500-1499
1000to1499
1500to1599
1600to1649
1650to1699
1700to1749
1750to1779
1780to1799
1800to1819
1820to1829
1830to1839
1840to1849
1850to1859
1860to1864
1865to1869
1870to1874
1875to1879
1880to1884
1885to1889
1890to1894
1895to1899
1900to1904
1905to1909
1910to1914
1915to1919
1920to1924
1925to1929
1930to1939
1940to the present
علماء الرياضيات
الرياضيات في العلوم الاخرى
بحوث و اطاريح جامعية
هل تعلم
طرائق التدريس
الرياضيات العامة
نظرية البيان
النموذج الثنائي لمسائل البرمجة الخطيةDuality in Linear Programming:طريقة حل المسائل الثنائية بواسطة السمبلكس
المؤلف: ا.د. ابو القاسم مسعود الشيخ
المصدر: بحوث العمليات
الجزء والصفحة: 175-179
22-2-2022
6303
طريقة حل المسائل الثنائية بواسطة السمبلكس
(Dual Simplex Method)
من خلال المقالات السابقة التي تناولت طريقة السمبلكس للمسألة الأولى تبين إذا كان في حالة التعظيم لأي متغير أو أكثر فإن المسألة ليس له الحل الأمثل - وأن الشرط الأساسي لتحقيق الحل الأمثل أن جميع لكل (J).
فإذا نظرنا إلى هذا الشرط من ناحية أو جهة المسائل الثنائية، فإن :
والذي يعني أن المسألة الثنائية لها حل غير موجود وهذا الشرط يتحقق عندما تكون المسألة الأولية ليس حل أمثل.
ومن جهة أخرى عندما يكون:
وهذا يعني أن المسألة الثنائية في دائرة الحل أو طريقها للحل عندما تكون المسألة الأولى لها حل مثالي.
وبناء على النتائج المدونة أعلاه فإنه يقترح حل مسألة البرمجة الخطية من جديد أو من بدايتها مرة ثانية، حيث تكون بداية المسألة ليس حل واضح ولكن في النهاية لها حل مثالي (ويمكن مقارنتها بطريقة السمبلكس الاعتيادية والتي تبدأ لها في أن لها الحل واضح وفي الأخير لا يوجد لها حل، أما الطريقة التي تختصر الحل تسمى السمبلكس الثنائي (Dual Simplex). والتي تبدأ من عدم وجود حل واضح (Infeasibility)
وتنتهي عندما يتوفر وضوح وجود للمسألة (Feasibility) وعند توفر (Feasibility) عندما يكون الحل الأمثل (Optimality). وهذا النوع من المسائل متوفر جداً في مسائل البرمجة الخطية وله أهمية كبرى، ويمكن أن يكون له عامل مساعد ومباشر في تحليل حساسية متغيرات مسائل LP.
مثال .4
الخطوة الابتدائية تحول كل القيود من ≥ وإضافة المتغير الاحتياطي (Stack variable) للحصول على إشارة التساوي (=).
البداية بطريقة السمبلكس الاعتيادية والتي توضح أن المتغيرات الاحتياطية ,x3 ,x4 , x5 لا توفر حل واضح مادام المسألة تصغر وكل معاملات دالة الهدف تكون وهذا يعني أن الحل الأساسي للمسألة هو
فهو حل مثالي (Optimal) لكن غير منظور أو حل خيالي لأنه لا يحقق شرط للجميع.
المسألة يمكن معالجة حلها بطريق السمبلكس الثنائي:
وكما هو معروف في طريقة السمبلكس - أن الطريقة تعتمد على توفر الحل المثالي - وشرط عدم الخيالية في الأرقام - حيث شرط توفر الحل المثالي تضمن توفر الحل المثالي – وعدم الخيالية تضغط على قيم المتغيرات نحو نقاط الحل ومساحته المعروفة بطرق استخدام الرسم .
شرط عدم الخيالية في فهم الأرقام (Feasibility Condition)
إن المتغير الذي يخرج من المتغيرات الأساسية يعتبر له أكبر قيمة سالبة. أما إذا كان المتغير الأساسي غير سالم فإن عمليات التغيير يجب أن تتوقف ويعتبر الحل المنظور (الغير خيالي) مثالي.
شرط وجود الحل المثالي (Optimality):
إن المتغير الذي يدخل من ضمن متغيرات الحل يتم اختياره من ضمن المتغيرات الغير أساسية في الحل (Nonbasic). تأخر النسبة بال بالنسبة للطرف الشمال أو معاملات الطرف الشمال لـ المعادلة Z إلى المعاملات المقابلة للمتغير المقترح أو المختار خروجه من المتغيرات الأساسية. إهمال أي نسبة مقامها + أو صفر - ويقرر دخول المتغير وفقاً للأقل نسبة موجبة، أما إذا كانت كل المقامات صفر أو قيمة موجبة فإن المسألة لها حل خيالي. (unfeasible)
ويعد اختيار المتغير الذي يدخل متغيرات الحل واختيار المتغير الذي يخرج يلي ذلك الحصول على تغيير الصفوف للحصول على المصفوفة الأحادية المعهودة ومنها إلى محاولة أخرى حتى الوصول إلى الحل الأمثل أو التوقف عن وجود حل.
فبالإشارة إلى الجدول السابق نلاحظ أن المتغير المختار إلى الخروج (6- = ) x لأنه يتحصل أكبر قيمة سالبة. أما المتغير التي دخل الحل فيعطي وفقاً للجدول التالي:
المتغير المرشح للدخول : لأنه مقابل إلى أقل قيمة موجبة (1/3) وبتطبيق قواعد المصفوفات للحصول على المصفوفة الأحادية التالية للمتغيرات نحصل على الجدول التالي:
الحل المدرج أعلاه مثالي ولكن خيالي حيث
فإذا اخترنا x3 لمغادرة المتغيرات الأساسية ، فإن x1 تنطبق عليه الشروط للدخول إلى قائمة المتغيرات الأساسية والتي تعطي بالجدول التالي:
ومن الجدول الأخير يتضح ان الحل مثالي وغير خيالي.
يعتبر تطبيق طريقة السمبلكس الثنائية ذات استخدام مفيد في تحليل الحساسية. وتظهر هذه الأهمية عندما يضاف قيد جديد للمسألة بعد الحصول على الحل للمسألة بكل الإضافة. فإذا كان القيد (المضاف) لا يحقق شرط الحل الأمثل والغير خيالي فإن المسألة سيبقى لها حل مثالي ولكن خيالي. وبالتالي طريقة السمبلكس الثنائية يمكن استخدامها بدون إعادة الحل من البداية حتى تحقق شروط الحل الأمثل والغير خيالي في عدد قليل من الخطوات الحسابية.