مسألة الإسناد
مشكلة الاسناد أو مشكلة الاسناد الأمثل عرفت منذ بداية علم بحوث العمليات و لها تطبيقات عملية جد مطلوبة.
مثال ابتدائي[عدل]
شركة تتشغل 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
مراجع[عدل]
- ^ KUHN, Harold W. The Hungarian method for the assignment problem. Naval research logistics quarterly, 1955, vol. 2, no 1‐2, p. 83-97 نسخة محفوظة 26 مارس 2019 على موقع واي باك مشين.
- ^ Michael R. Garey and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H.Freeman ed 1979
