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

تقوم هذه الطريقة على عدد من الخطوات وهي التالية :

أ- نؤشر على أقل قيمة في كل صف ونطرح منها باقي القيم من ذلك الصف.

ب ـ نؤشر على أقل قيمة في كل عامود ونطرح منها باقي القيم من ذلك العامود. 

ج- نخصص في كل صف به صفر واحد ونشطب باقي الأصفار في عامود ذلك الصفر.

د ـ نخصص في كل عامود به صفر واحد، ونشطب باقي الأصفار في صف ذلك الصفر.

هـ - الهدف تخفيض التكلفة إلى أقل حد ممكن. 

مثال (4 ـ12 )

ورد للشركة الحديثة للتعدين خمسة أوامر إنتاج هي ، (1، 2، 3، 4، 5)، يتوجب معالجتها على الآلات الخمس التالية (أ، ب، ج، د، هـ)، وتكاليف الأوامر على تلك الآلات هي كما واردة في المصفوفة التالية : 

المطلوب :

تخصيص هذه الأوامر على الآلات المتاحة بحيث يترتب على معالجتها أقل تكلفة.

الحل:

نستخدم في حل هذه المسألة الإدارية الطريقة الهنغارية، والتي تتكون من الخطوات التالية :

1- نحدد أقل قيمة في كل صف ونطرح باقي قيم الصف منها، فنحصل على المصفوفة التالية.

2.نحدد أقل قيمة في كل عامود ونطرح باقي قيم العامود منها فنحصل على نفس المصفوفة لأن القيم في الأعمدة كانت صفر وبالتالي تبقى المصفوفة أعلاه على حالها. 

3- نخصص الصفوف التي بها صفر، ونشطب باقي الأصفار في عامود ذلك الصفر.

4- نخصص الأعمدة التي بها صفر واحد ، ونشطب باقي الأصفار في صف ذلك الصفر.

ملاحظة:

يصعب في بعض الحالات الوصول إلى حل كامل وفق الخطوات السابقة، لذلك يمكن تطوير الحل وفق الخطوات التالية :

1 ـ نؤشر على الأعمدة التي بها أصفار بخط عند تخصيص الصفوف.

2 ـ نؤشر على الصفوف التي بها أصفار بخط عند تخصيص الأعمدة.

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

3- نأخذ أقل قيمة غير مؤشرة بخط.

4ـ نطرح هذه القيمة من كل قيمة لم تؤشر بخط.

5ـ نجمع هذه القيمة إلى كل قيمة تقع عند تقاطع خطين.

6ـ القيم التي يمر بها خط واحد وكذلك الأصفار تظل كما هي.

7- نكرر خطوات (3) ، (4) سابقاً ونتابع الخطوات الجديدة حتى نصل إلى حل كامل.

مثال (4-3)

لدينا أوامر الإنتاج الستة التالية (1 ، 2 ، 3 ،4 ،5 ، 6) ، وتكاليف إنجازها على  الآلات التالية (أ، ب، ج، د هـ، و)، وذلك كما هو وارد في المصفوفة التالية :

المطلوب :

تخصص هذه الأوامر على الآلات المتاحة بحيث يترتب على معالجتها أقل تكلفة.
الحل :

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

2 ـ نطرح من كل عامود أقل قيمة فيه فنحصل على المصفوفة التالية : 

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

ب ـ صف (ج) فيه صفر واحد نخصصه، ونشطب باقي أصفار العامود (6) الموجود فيه. 

ج ـ صف (هـ) فيه صفر واحد نخصصه.

د ـ عامود (1) فيه صفر واحد نخصصه.

هـ ـ عامود (4) فيه صفر واحد نخصصه ونشطب باقي أصفار صف (و) الموجود فيه هذا الصفر.

و ـ عامود (5) فيه صفر واحد نخصصه

نلاحظ أننا لم نصل إلى حل كامل لذلك نتبع الخطوات التالية : 

1- الصفر الموجود في الخلية (أ2) خصص عند اختيار الصفوف، لذلك نضع خطاً على العامود (2) .

2 ـ الصفر في الخلية ( ب 5) خصص عند اختيار الأعمدة، لذلك نضع خطاً على صف (ب).

3- الصفر في الخلية (ج6) خصص عند اختيار الصفوف، لذلك نضع خطاً على عامود (6) . 

4 الصفر في الخلية ( هـ3) خصص عند اختيار الصفوف، لذلك نضع خطاً على عامود .(3)

5- الصفر في الخلية (و4) خصص عند اختيار الأعمدة، لذلك نضع خطاً على صف (و).

6- أن أقل قيمة غير مغطاة بخط موجود في الخلية (د4) ومقدارها (1).

7 ـ تطرح هذه القيمة من كل قيمة لم يمر بها خط.

8- تضاف هذه القيمة على كل قيمة تقاطع عندها خطان على أن لا تتغير الأصفار للقيم التي مر بها خط واحد فنحصل على الجدول التالي:

9 ـ  نعيد تخصيص الصفوف والاعمدة من جديد فنحصل على الجدول (اعلاه ايضاً) .
10 ـ تخصيص الاوامر يتم على الشكل التالي :

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

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

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

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

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

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

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

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

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

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

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

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

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