3-2 خوارزمية السيمبلكس المطورة ⁽¹⁾ 

تهدف الطرائق المطورة للسمبلكس إلى حل الصعوبات التي تعترض الطرائق التقليدية في حل جملة المعادلات الخطية (مثل ظهور قيم سالبة مع عامود الثوابت ث) أثناء تطور الحل ، وسوف نستعرض أهم هذه الطرائق وهي خوارزمية السيمبلكس المطوّرة.

تتكون هذه الطريقة من ثلاث مراحل أساسية وهي التالية :

المرحلة الأولى : وتتألف من الخطوات التالية :

1 ـ وضع البرنامج الخطي بالصيغة النظامية (دالة الهدف، نوع تعظيم Max )   

2ـ وضع الشروط الخطية من الشكل ≥ وجميع المتغيرات ≥ 0 

3 - تحويل الشروط الخطية إلى معادلات بإضافة متغيرات الفرق إلى الشروط الخطية.

4 - نقل الطرف الأيسر من دالة الهدف إلى الطرف الأيمن.

5- نشكل جدول السيمبلكس المختزل والذي يأخذ الشكل التالي :

6- يتحقق الحل الأمثل إذا كانت العناصر المقابلة لمتغيرات خارج القاعدة في سطر (هـ) كلها موجبة والعناصر المقابلة لمتغيرات القاعدة مع عامود (ث) كلها موجبة أيضاً. 

المرحلة الثانية : معالجة العناصر السالبة في كل من (هـ) و (ث). 

وهنا لدينا حالتين هما :

حالة (1)

معالجة عناصر سطر (هـ) باستخدام خوارزمية الأولى ومرافقه Primal and Olual Algorithrn ، وخطوات الحل في هذه الحالة هي التالية :

1- تحديد عامود الدوران Pivot Column وذلك باختيار إحدى القيم السالبة في سطر (هـ) المقابلة لمتغيرات خارج القاعدة، ولتكن ت _ك < 0 ويكون عامود الدوران هو س _ك .

2- تحديد عنصر الدوران Pivot element وذلك باستخدام معيار ماغوط للأولي التالي بقسمة عناصر عامود (ث) على عناصر عامود الدوران المقابلة لمتغيرات القاعدة (فقط القسمة على العناصر ذات القيمة الموجبة) واختيار النسبة الأصغر يكون عنصرها في عامود الدوران هو عنصر الدوران. 

3- تحديد سطر الدوران Pivot Line وهو السطر الذي يتقاطع مع عامود الدوران عند عنصر الدوران.

4- تشكيل جدول جديد باتباع الخطوات التالية :

أ- نضع في مكان عنصر الدوران مقلوبه .

ب ـ نضع نواتج قسمة سطر الدوران في الجدول القديم على عنصر الدوران بدل العناصر القديمة.

ج ـ نضع نواتج قسمة عامود الدوران في الجدول القديم على عنصر تغيير الإشارة بدل العناصر القديمة.

د ـ العناصر الأخرى تحسب من الجدول القديم على الشكل التالي :

هنا نميز الحالات التالية : 

1- إذا كانت جميع القيم في السطر (هـ) موجبة نكون قد وصلنا إلى حل ممكن مرافق ،  وعندها ننتقل إلى الحالة الثانية أي معالجة عناصر السطر (ث) فإذا كانت كلها موجبة نكون قد وصلنا إلى حل أمثل. 

2- إذا كان هناك عنصراً سالباً في السطر (هـ) نكرر الخطوات من (1) إلى (5) حتى تصبح كل عناصر السطر (هـ) موجبة.  

مثال (4-5)

لنعد إلى البرنامج الخطي السابق في مثال رقم (1)

المطلوب : حل هذا البرنامج باستخدام خوارزمة السيمبلكس المطورة.

الحل :

1- نكتب البرنامج الخطي

هـ 6س₁ - 2س₂ = 0

نضيف للشروط متغیرات فرق س₃، س₄

س₁  + 2س₂ + س₃   = 30

2س ₁ + 2س₂ +س₄ =  28  

2 ـ نشكل جدول السيمبلكس المختزل (الحل الأولي)

3 ـ الحل ليس أمثل لأن العناصر المقابلة لمتغيرات خارج القاعدة في سطر (هـ) فيها قيم سالبة يجب التخلص منها وذلك وفق الخطوات التالية :

أ- تحديد عامود الدوران وهو هنا (س₁) الذي يحوي قيمة سالبة في سطر (هـ) وهي  (6-).

ب- تحديد عنصر الدوران بقسمة عناصر عامود (ث) على العناصر الموجبة في عامود الدوران المقابلة، ونأخذ النسبة الأقل وهنا فإن عنصر الدوران هو (2)

ج- تحديد سطر الدوران وهو السطر (س4) تقاطع عامود الدوران مع عنصر الدوران. 

د ـ نشكل جدول جديد وفق القواعد المذكورة سابقاً وذلك على الشكل التالي :

1- نضع مكان عنصر الدوران مقلوبه (2) يصبح 2./1

2 ـ نضع مكان بقية عناصر سطر (س₁) نواتج قسمة عناصر سطر الدوران على عنصر الدوران.

3 ـ نضع مكان بقية عناصر عامود (س) نواتج قسمة عناصر عامود الدوران على عنصر الدوران مع تغير الإشارات.

نلاحظ ان جميع العناصر في سطر (هـ) وكذلك في عامود (ث) هي قيم موجبة ، لذلك الحل الذي تم التوصل اليه هو الحل الامثل ، حيث ان :

مثال( 4-6) :

لدينا البرنامج الخطي النظامي التالي :

الحل : نكتب البرنامج الخطي على الشكل التالي :

نكتب البرنامج الخطي على الشكل التالي

هـ 4س₁ ــ 3س_{2 =}  0

القيود مع اضافة المتغيرات :
2س1 + س₂ + س₃ = 1800

س₁ + 2س₂ + س₄ = 1440

س₁ ، س₂ ، س₃ ،س₄ اكبر او يساوي Φ .

نلاحظ ان عامود الدوران هو (س) وسطر الدوران (س₃) ، والحل ليس امثلاً بسبب وجود قيم سالبة في سطر(هـ) ولمعالجتها نشكل دول جديد

نلاحظ ان الحل الجديد ليس امثلاً لأن هناك قيمة سالبة في سطر (هـ) ، يجب ان تعالج ، لذلك نكرر الخطوات السابقة ونشكل جدول افضل .
 

وبالتالي فإن الحل الأخير هو الأمثل ( لا يوجد أي قيمة سالبة في سطر هـ) وعليه  س ₁  =  

ــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ 

1) انظر: د. خالد الماغوط ، البرمجة الخطية جامعة حلب، حلب، 1986.

وكذلك د. إبراهيم نائب د. أنعام بافية، بحوث العمليات (خوارزميات وبرامج حاسوبية) دار وائل عمان، 1999. 

مواضيع ذات صلة

البرمـجـة الخـطيـة لمسألة البائع المتجول (حالة خاصة في التخصيص)

البرمـجـة الخـطيـة (مـسائل التخـصيـص) فـي حالـة تـعظيـم الأربـاح

الطـريـقـة الهنـغاريـة فـي حـل مـسائـل التـخصـيـص

البرمجة الخطية (مسائل التخصيص) ـ الشكل العام والحالة الخاصة

طـريقـة التـوزيـع المعدلة (Multiplies Method) لحـل مسألـة الـنقـل

طرائق البحث عن الحل الأمثل لمسألـة الـنقـل (طـريـقـة المـسـار المـغـلـق)

طـريـقـة الجـزاء (طـريـقـة فـوجـل NAM) لحـل مسألـة الـنقـل

نـمـاذج مـصفوفـة الـنقـل و طرائـق حـل مسألـة الـنقـل

البـرمـجة الخـطيـة (مـسائـل النـقـل) ــ نـمـوذج مـصفـوفـة النقل ودالـة الهـدف

خـوارزمـيـة السيـمـبـلـكـس الـمطـورة وأمثلة تـطبيقـية عـليـها (حـالـة 2)

طرائـق البـرمـجـة الخـطيـة (طريـقة السيـمبلـكس The Simplex Method) 2

طرائـق البـرمـجـة الخـطيـة (طريـقة السيـمبلـكس The Simplex Method) 1