2-4-2- طرائق البحث عن الحل الأمثل

1- طريقة المسار المغلق

هي طريقة مباشرة تستخدم في اختبار مثولية الحل وتقوم على الخطوات التالية : 

أ- نحدد المتغيرات غير الأساسية والتي تمثل الخلايا الفارغة، ونبدأ من أول خلية فارغة في السطر الأول، ثم الخلية الفارغة التي تليها وهكذا في السطر الثاني.. الخ.

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

ج ـ نحسب التكلفة غير المباشرة لكل مسار من المسارات المغلقة في جدول الحل الأولي. ويتم حساب ذلك بإعطاء الخلية المراد اختبارها إشارة (+) ثم تتغير الإشارة في كل خطوة من خطوات المسار (+) إلى (-) وهكذا، على أن يكون عدد الخلايا في المسار زوجياً (4) أو (6).

د ـ نختار المسار ذو الكلفة السالبة الأكبر، علماً أن المسارات تأخذ أحد الأشكال التالية : 

هـ - نتيجة اختبار المسارات يمكن أن تكون كما يلي :

1- إذا كانت القيم الجبرية لكافة الخلايا المختبرة موجبة أو تساوي الصفر، فإننا نكون قد وصلنا إلى الحل الأمثل وفي هذه الحالة نحسب التكلفة الإجمالية للتوزيع الأمثل:

2 ـ أما إذا كان هناك قيماً سلبية للخلايا المختبرة فهذا يعني أن هذه الخلايا ستساهم في خفض تكاليف النقل في هذه الحالة علينا أن نعمل على تحسين الحل وذلك على

الشكل التالي:

ـ نختار المسار ذو التكلفة المباشرة الأكثر سلبية (في حالة كان هناك أكثر من مسار سالب).

ـ نختار من قيم المتغيرات الأساسية في المسار المختار القيمة الأقل (للكمية المؤشر عليها بإشارة سالب).

ـ تضاف هذه الكمية إلى قيمة المتغيرات ذات الإشارة الموجبة وتطرح من المتغيرات ذات الإشارة السالبة.

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

مثال(11- 4)

نعود لجدول الحل الأولي في المثال رقم (1) ونطبق خطوات الطريقة المذكورة أعلاه. 

1- المتغيرات غير الأساسية هي :

( س₁ ع ₁) ، ( س₁ ع ₃)، (س₃ ع₁)، (س₃  ع₂)

وعدد هذه الخلايا = ( م × ن) - (م + ن) - 1]

4 ـ المسار المتغير هو المسار الاول لأن قيمة التكاليف غير المباشرة فيه (-8) وهو المسار المتغير س₁ع₂

6 ـ التكلفة الاجمالية ت (ص) = 40 × 4 + 60 × 6 + 40 × 8 +20 × 7 + 100 × 6 = 1580 دينار .

ومقدار التوفير في التكاليف بنتيجة هذا التطوير في الحل هو :

1900 ــ 1500 = 320 دينار .

7 ـ نعود ونختبر مثالية هذا الحل باتباع نفس الخطوات السابقة ، وبالحل نلاحظ ان تكاليف المسارات المغلقة هي كالتالي :

نلاحظ ان قيم كل المسارات موجبة لذلك فان الحل السابق هو الامثل . 

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

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

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

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

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

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

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

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

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

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

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

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

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