كتب attribution issue
اذا لم تجد ما تبحث عنه يمكنك استخدام كلمات أكثر دقة.
مسألة الإسناد (معلومة)
مشكلة الاسناد أو مشكلة الاسناد الأمثل عرفت منذ بداية علم بحوث العمليات و لها تطبيقات عملية جد مطلوبة.
مثال ابتدائي
شركة تتشغل n أشخاص لوظائف مختلفة عددها الكلي n. نحدد متغيرًا الربحية rij ≥ 0 بالنسبة لأي شخص i مأهل للمنصب j ، على سبيل المثال rij تمثل الربح الذي يمكن أن تحققه المؤسسة إذا أسند الشخص i إلى الوظيفة j ، تكمن المشكلة في تحديد تعيين الأشخاص لمحطات العمل بالكيفية التي تزيد من قيمة الربحية الإجمالية.
نماذج الثمثيل
الثمثيل ببيان ثنائي
يمكن تمثيل هذه المشكلة بواسطة بيان ثنائي (G(U,V,E، تكون فيه مجموعة الرؤوس U هي الأشخاص ومجموعة الرؤوس V هي مناصب الشغل ، أما ثقل كل ضلع (w(ui,vj فيمثل الربحية.
تتمثل المهمة هنا في العثور على الإقتران في البيان الثنائي ذا أقصى مجموع أثقال الأضلاع.
الثمثيل بمصفوفة
يمكن كذلك تمثيل المشكلة بواسطة مصفوفة حدوث R حيث يمثل كل سطر شخصًا ويمثل كل عمود منصبا ، عناصر المصفوفة تساوي rij
الحل الأمثل هنا يتمثل في العثور على مجموعة من العناصر rij ليس لها أي خط ولا عمود مشترك في المصفوفة R ومجموعهم المتراكم له أكبر قيمة ممكنة ، و هذا يتناسب مع الطرح الشكلي لمسألة برمجة خطية
خوارزميات الحل الأمثل
يمكن الحصول على الحل الأمثل بواسطة تخصيص أيّ خوارزميات البرمجة الخطية ، لكن أول طريقة تستغرق زمنا كثير الحدود قطعي لحل هذه المسألة هي طريقة كوهن المعروفة باسم الخوارزمية المجرية
صنف التعقيد
لم تذكر مشكلة الانساد الأمثل تحت صيغتها الخام ضمن القائمة الأساسية لمايكل غاري و دايفيد جونسون للمسائل من صنف التعقيد الحسابي NP-كامل ، و نظرا بأن الخوارزمية المجرية تسمح حلّها خلال زمن كثير الحدود قإن هذه المسألة تنتمي إلى صنف التعقيد P
