مسألة الـ Assignment: طريقة Hungarian خطوة بخطوة
مسألة الـ assignment بتوزع عمال على شغلانات بأقل تكلفة كلية. هتتعلم طريقة Hungarian: تخفيض الصفوف والأعمدة وتغطية الأصفار والتوزيع النهائي.
مسألة الـ assignment بتوزع n عامل على n شغلانة، واحد لكل واحدة، بحيث التكلفة (أو الوقت) الكلية تبقى أقل ما يمكن. هي حالة خاصة من الـ transportation وكل العرض والطلب فيها 1. البيانات مصفوفة تكلفة n في n. لو المصفوفة مش مربعة ضيف صفوف أو أعمدة dummy أصفار. ولو الهدف تعظيم الربح حوّلها بطرح كل قيمة من أكبر قيمة وبعدين minimize.
خطوات طريقة Hungarian: واحد، تخفيض الصفوف: اطرح أصغر قيمة في كل صف من كل عناصر الصف. اتنين، تخفيض الأعمدة: اطرح أصغر قيمة في كل عمود من عناصر العمود. تلاتة، غطّي كل الأصفار بأقل عدد من الخطوط الأفقية والرأسية. لو عدد الخطوط يساوي n يبقى فيه توزيع optimal بين الأصفار. أربعة، غير كده لاقي أصغر قيمة مش مغطاة، واطرحها من كل العناصر الغير مغطاة وضيفها للعناصر المغطاة مرتين، وكرر الخطوة تلاتة.
علشان تعمل التوزيع النهائي، ابدأ بالصفوف أو الأعمدة اللي فيها صفر واحد بس، ووزّع الصفر ده، واشطب باقي صفه وعموده. كمّل لحد ما كل صف ياخد توزيع. والتكلفة الكلية بتتقري من المصفوفة الأصلية مش المخفضة. ولو في توزيعات كتير ليها نفس التكلفة تبقى المسألة ليها حلول مثلى متعددة.
أهم النقاط
- لازم مصفوفة مربعة وضيف dummy لو مش مربعة.
- تخفيض صفوف وبعدين أعمدة.
- أقل عدد خطوط تغطية = n معناه optimal.
- غير كده عدّل بأصغر قيمة مش مغطاة.
- في maximization اطرح من أكبر قيمة الأول.
مثال محلول
تكاليف عاملين وشغلانتين: W1 = [8, 6] وW2 = [5, 9]. تخفيض الصفوف: W1 بيبقى [2, 0] وW2 بيبقى [0, 4]. تخفيض الأعمدة: أصغر قيمة في العمود الأول 0 والتاني 0 فمفيش تغيير. الأصفار عند (W1, J2) و(W2, J1) وخطين بيغطوهم وده يساوي n = 2. وزّع W1 على J2 وW2 على J1. التكلفة الكلية من المصفوفة الأصلية = 6 + 5 = 11.
أسئلة شائعة
لو الشغلانات أكتر من العمال؟
ضيف عمال dummy (صفوف أصفار) علشان المصفوفة تبقى مربعة.
إزاي أحوّل assignment تعظيم لتصغير؟
اطرح كل قيمة من أكبر قيمة في المصفوفة وبعدين طبّق طريقة Hungarian.
مواضيع مرتبطة
- مسألة الـ Transportation: Northwest Corner وLeast Cost وVogel
- البرمجة الخطية: الـ Formulation وطريقة الرسم Graphical
- طريقة Simplex: الخطوات والـ Slack Variables والـ Tableau
- كل المواضيع: الأوبريشنز ريسيرش
بصمجلي مشروع طلابي مستقل، مش موقع رسمي لجامعة الدلتا. ارجع لمحاضراتك ودكتورك دايمًا.