ما هي مشكلة التعيين؟

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

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

وصف الأداة

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

أمثلة

مصفوفة الإدخال (3 عمال × 3 مهام):

المهمة 1 المهمة 2 المهمة 3
العامل 1 400 150 400
العامل 2 400 450 600
العامل 3 300 225 300

التعيينات المثلى:

العامل المهمة التكلفة
العامل 1 المهمة 2 150
العامل 2 المهمة 1 400
العامل 3 المهمة 3 300

التكلفة الإجمالية: 850

الميزات

  • مصفوفة قابلة للتحرير — انقر على أي خلية أو رأس عمود لإعادة تسمية العمال والمهام والتكاليف مباشرة في الجدول
  • حجم قابل للتكوين — يدعم المصفوفات من 2×2 إلى 8×8
  • نتائج فورية — تعمل خوارزمية المجر في المتصفح بدون جولة خادم

كيف يعمل

تستخدم الأداة خوارزمية Munkres (المجر) لحل مشكلة التعيين بشكل أمثل. تقوم بإنشاء مصفوفة تكلفة من المدخلات الخاصة بك، وتطبيق سلسلة من خطوات تقليل الصفوف والأعمدة، وتجد بشكل متكرر أقصى مطابقة للأصفار حتى يتم تحديد تعيين أمثل كامل. التعقيد الزمني هو $O(n^3)$، حيث $n$ هو بُعد المصفوفة.

بالنسبة للمصفوفات غير المربعة (عمال أكثر من المهام أو العكس)، تقوم الخوارزمية بملء المصفوفة بأصفار بحيث يتم مطابقة كل عامل وكل مهمة.

شرح الخيارات

  • عدد العمال / الصفوف — يتحكم في عدد الصفوف التي تظهر في مصفوفة التكلفة (2–8)
  • عدد المهام / الأعمدة — يتحكم في عدد الأعمدة التي تظهر في مصفوفة التكلفة (2–8)
  • خلايا مصفوفة التكلفة — أدخل تكلفة تعيين عامل معين لمهمة معينة؛ يتم قبول أي قيمة رقمية

القيود

  • حجم المصفوفة محدود بـ 8×8 (64 خلية)
  • تقلل الخوارزمية التكلفة الإجمالية؛ للتعظيم (على سبيل المثال، لمصفوفات الربح)، قم بنفي القيم قبل إدخالها
  • يتم التعامل مع قيم الخلايا غير الرقمية على أنها صفر