[ تعرٌف على ] مسألة الإسناد # أخر تحديث اليوم 2024/05/22

تم النشر اليوم 2024/05/22 | مسألة الإسناد

خوارزميات الحل الأمثل

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

صنف التعقيد

لم تذكر مشكلة الانساد الأمثل تحت صيغتها الخام ضمن القائمة الأساسية لمايكل غاري و دايفيد جونسون للمسائل من صنف التعقيد الحسابي NP-كامل ، و نظرا بأن الخوارزمية المجرية تسمح حلّها خلال زمن كثير الحدود قإن هذه المسألة تنتمي إلى صنف التعقيد P

نماذج الثمثيل

الثمثيل ببيان ثنائي
يمكن تمثيل هذه المشكلة بواسطة بيان ثنائي (G(U,V,E، تكون فيه مجموعة الرؤوس U هي الأشخاص ومجموعة الرؤوس V هي مناصب الشغل ، أما ثقل كل ضلع (w(ui,vj فيمثل الربحية. تتمثل المهمة هنا في العثور على الإقتران في البيان الثنائي ذا أقصى مجموع أثقال الأضلاع. الثمثيل بمصفوفة
يمكن كذلك تمثيل المشكلة بواسطة مصفوفة حدوث R حيث يمثل كل سطر شخصًا ويمثل كل عمود منصبا ، عناصر المصفوفة تساوي rij الحل الأمثل هنا يتمثل في العثور على مجموعة من العناصر rij ليس لها أي خط ولا عمود مشترك في المصفوفة R ومجموعهم المتراكم له أكبر قيمة ممكنة ، و هذا يتناسب مع الطرح الشكلي لمسألة برمجة خطية

مثال ابتدائي

شركة تتشغل n أشخاص لوظائف مختلفة عددها الكلي n. نحدد متغيرًا الربحية rij ≥ 0 بالنسبة لأي شخص i مأهل للمنصب j ، على سبيل المثال rij تمثل الربح الذي يمكن أن تحققه المؤسسة إذا أسند الشخص i إلى الوظيفة j ،
تكمن المشكلة في تحديد تعيين الأشخاص لمحطات العمل بالكيفية التي تزيد من قيمة الربحية الإجمالية.

شرح مبسط

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