الطريقة المجرية: مما تتكون منه ، مثال - دوداس - 2025

على طريقة المجري هو الخوارزمية المستخدمة في مشاكل تخصيص عندما كنت ترغب في تقليل التكلفة. بمعنى ، يتم استخدامه للعثور على الحد الأدنى للتكلفة عن طريق تعيين عدة أشخاص لأنشطة مختلفة بناءً على أقل تكلفة. يجب تعيين كل نشاط لشخص مختلف.

مشكلة التخصيص هي نوع خاص من مشاكل البرمجة الخطية ، حيث يكون الهدف هو تقليل تكلفة أو وقت إكمال عدد من الوظائف بواسطة عدة أشخاص.

المصدر: pixabay.com

تتمثل إحدى الخصائص المهمة لمشكلة التخصيص في تعيين وظيفة واحدة (أو عامل) لجهاز (أو مشروع).

تم تطوير هذه الطريقة من قبل عالم الرياضيات المجري د. كونيج. لهذا السبب ، تُعرف بالطريقة المجرية لمشاكل التعيين. تُعرف أيضًا باسم خوارزمية تخصيص Kuhn-Munkres.

يمكن حل أي مشكلة تخصيص بسهولة من خلال تطبيق هذه الطريقة التي تتكون من مرحلتين:

- مع المرحلة الأولى ، يتم إجراء تخفيضات في الصفوف وتخفيضات في العمود.

- في المرحلة الثانية ، يتم تحسين الحل على أساس تكراري.

ما هي الطريقة المجرية؟

تتكون الطريقة المجرية من أربع خطوات. يتم تنفيذ الخطوتين الأوليين مرة واحدة فقط ، بينما يتم تكرار الخطوتين 3 و 4 حتى يتم العثور على التخصيص الأمثل.

تعتبر المصفوفة المربعة من الرتبة n في n بمثابة بيانات إدخال ، والتي يجب أن تحتوي فقط على عناصر غير سالبة.

بالنسبة إلى مشكلة معينة ، إذا كان عدد الصفوف في المصفوفة لا يساوي عدد الأعمدة ، فيجب إضافة صف وهمي أو عمود وهمي ، اعتمادًا على الحالة. يتم دائمًا تخصيص تكاليف التخصيص لتلك الخلايا الوهمية على أنها صفر.

الخطوة 1: اطرح الحد الأدنى لكل صف

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

الخطوة 2: اطرح القيم الدنيا من كل عمود

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

الخطوة 3: قم بتغطية جميع الأصفار بأقل عدد من الأسطر

يجب تغطية جميع الأصفار في المصفوفة الناتجة عن الخطوة 2 باستخدام أقل عدد من الخطوط الأفقية والعمودية ، إما عن طريق الصفوف أو الأعمدة.

إذا كان إجمالي عدد n من الأسطر مطلوبًا لتغطية جميع الأصفار ، حيث n يساوي الحجم n في n من المصفوفة ، فسيكون هناك توزيع أمثل بين الأصفار وبالتالي تتوقف الخوارزمية.

خلاف ذلك ، إذا كانت هناك حاجة إلى أقل من n من الأسطر لتغطية جميع الأصفار في الصفيف ، فانتقل إلى الخطوة 4.

الخطوة 4: إنشاء أصفار إضافية

يتم تحديد أصغر عنصر في المصفوفة (يسمى k) والذي لم يتم تغطيته بأحد الخطوط الموجودة في الخطوة 3.

يتم طرح قيمة k من جميع العناصر التي لا تغطيها الأسطر. بعد ذلك ، تضاف قيمة ka إلى جميع العناصر التي يغطيها تقاطع سطرين.

يتم ترك العناصر التي يغطيها سطر واحد كما هي. بعد تنفيذ هذه الخطوة ، تعود إلى الخطوة 3.

التخصيص الأمثل

بعد إيقاف الخوارزمية في الخطوة 3 ، يتم اختيار مجموعة من الأصفار بحيث يتم تحديد صفر واحد فقط لكل صف وكل عمود.

إذا لم يكن هناك صفر واحد في صف أو عمود في عملية التحديد هذه ، فسيتم اختيار أحد هذه الأصفار. تتم إزالة الأصفار المتبقية في هذا العمود أو الصف ، مع تكرار نفس الشيء مع المهام الأخرى أيضًا.

إذا لم يكن هناك تخصيص صفري واحد ، فهناك حلول متعددة. ومع ذلك ، ستظل التكلفة كما هي لمجموعات مختلفة من التعيينات.

تتم إزالة أي صفوف أو أعمدة وهمية تمت إضافتها. وبالتالي فإن الأصفار المختارة في هذه المصفوفة النهائية تتوافق مع التخصيص المثالي المطلوب في المصفوفة الأصلية.

مثال

لنفكر في شركة بها أربعة أنشطة (A1 ، A2 ، A3 ، A4) يجب أن يقوم بها أربعة عمال (T1 ، T2 ، T3 ، T4). يجب تعيين نشاط واحد لكل عامل.

توضح المصفوفة التالية تكلفة تعيين عامل معين لنشاط معين. الهدف هو تقليل التكلفة الإجمالية للمهمة المكونة من هذه الأنشطة الأربعة.

الخطوة 1: اطرح الحد الأدنى لكل صف

تبدأ بطرح العنصر ذي القيمة الدنيا في كل صف من العناصر الأخرى في ذلك الصف. على سبيل المثال ، أصغر عنصر في الصف الأول هو 69. لذلك ، يتم طرح 69 من كل عنصر في الصف الأول. المصفوفة الناتجة هي:

الخطوة 2: اطرح القيم الدنيا من كل عمود

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

الخطوة 3: قم بتغطية جميع الأصفار بأقل عدد من الأسطر

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

نظرًا لأن عدد الأسطر المطلوبة هو ثلاثة وهو أقل من حجم المصفوفة (ن = 4) ، فإننا نواصل الخطوة 4.

الخطوة 4: إنشاء أصفار إضافية

يتم تحديد أصغر عنصر لا تغطيه السطور ، وقيمته 6. يتم طرح هذه القيمة من جميع العناصر غير المغطاة وتضاف هذه القيمة نفسها إلى جميع العناصر التي يغطيها تقاطع سطرين. ينتج عن هذا المصفوفة التالية:

كما هو مبين في الطريقة المجرية ، يجب تنفيذ الخطوة الثالثة مرة أخرى.

الخطوة 3 (كرر)

مرة أخرى ، يتم تحديد الحد الأدنى لعدد الأسطر المطلوبة لتغطية جميع الأصفار في المصفوفة. هذه المرة أربعة أسطر مطلوبة:

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

التخصيص الأمثل

كما تشير الطريقة ، فإن التحديد الذي تم إجراؤه للأصفار التالية يتوافق مع التعيين الأمثل:

يتوافق اختيار الأصفار هذا مع التخصيص الأمثل التالي في مصفوفة التكلفة الأصلية:

لذلك ، يجب على العامل 1 أداء النشاط 3 ، والعامل 2 ، والنشاط 2 ، والعامل 3 ، والنشاط 1 ، والعامل 4 يجب أن يؤدي النشاط 4. التكلفة الإجمالية لهذا التعيين الأمثل هي 69 + 37 + 11 + 23 = 140.

المراجع

1. الخوارزمية المجرية (2019). الخوارزمية المجرية. مأخوذة من: hungarianalgorithm.com.
2. دراسة (2019). استخدام الخوارزمية المجرية لحل مشاكل التخصيص. مأخوذة من: study.com.
3. وظائف الحكمة (2018). الطريقة المجرية لحل مشكلة التعيين - الأساليب الكمية للإدارة. مأخوذة من: wisdomjobs.com.
4. Geeks for Geeks (2019). الخوارزمية المجرية لمشكلة التعيين. مأخوذة من: geeksforgeeks.org.
5. كارلي مور ، ناثان لاندمان (2019). خوارزمية المطابقة القصوى المجرية. متألق. مأخوذة من: brilliant.org.