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