שיטה הונגרית: ממה זה מורכב, למשל - דודס - 2025

השיטה ההונגריה היא אלגוריתם משמש בעיות הקצאה כאשר אתה רוצה למזער עלות. כלומר, הוא משמש למציאת העלות המינימלית על ידי הקצאת אנשים מרובים לפעילויות שונות על סמך העלות הנמוכה ביותר. יש להקצות כל פעילות לאדם אחר.

בעיית הקצאה היא סוג מיוחד של בעיית תכנות לינארית, כאשר המטרה היא למזער את העלות או הזמן של השלמת מספר עבודות על ידי מספר אנשים.

מקור: pixabay.com

אחד המאפיינים החשובים של בעיית ההקצאה הוא שרק עבודה (או עובד) אחת מוקצה למכונה (או לפרויקט).

שיטה זו פותחה על ידי המתמטיקאי ההונגרי ד. קוניג. מסיבה זו, היא ידועה כשיטה הונגרית לבעיות הקצאה. זה ידוע גם כאלגוריתם ההקצאה של קוהן-מונקר.

ניתן לפתור בקלות כל בעיית הקצאה על ידי יישום שיטה זו המורכבת משני שלבים:

- עם הפחתת שורת השלב הראשון מתבצעות הפחתות עמודות.

- בשלב השני הפתרון ממוטב על בסיס איטרטיבי.

מהי השיטה ההונגרית?

השיטה ההונגרית מורכבת מארבעה שלבים. שני הצעדים הראשונים מבוצעים פעם אחת בלבד ואילו שלבים 3 ו -4 חוזרים על עצמם עד למציאת הקצאה אופטימלית.

מטריצה ​​מרובעת בסדר n על ידי n נחשבת כנתוני קלט, אשר חייבים להכיל רק אלמנטים לא שליליים.

לבעיה נתונה, אם מספר השורות במטריקס אינו שווה למספר העמודות, יש להוסיף שורה דמה או עמודת דמה, תלוי במקרה. עלויות ההקצאה לאותם תאי דמה מוקצים תמיד כאפס.

שלב 1: גרעו את המינימום של כל שורה

עבור כל שורה במערך, האלמנט עם הערך הנמוך ביותר נבחר ומופרע מכל אלמנט באותה שורה.

שלב 2: מחסירים את המינימום מכל עמודה

באופן דומה, הפריט עם הערך הנמוך ביותר נבחר לכל עמודה ומופרע מכל פריט באותה העמודה.

שלב 3: כסו את כל האפסים במספר מינימלי של שורות

יש לכסות את כל האפסים במטריקס הנובעים משלב 2 באמצעות מספר מינימלי של קווים אופקיים ואנכיים, בין שורות או עמודות.

אם נדרשים סך הכל של שורות לכיסוי כל האפסים, כאשר n שווה לגודל n כפול n של המטריצה, תתקבל הקצאה אופטימלית בין האפסים ולכן האלגוריתם נעצר.

אחרת, אם נדרשים פחות מ- n שורות לכיסוי כל האפסים במערך, המשך לשלב 4.

שלב 4: צור אפסים נוספים

נבחר האלמנט הקטן ביותר במטריקס (הנקרא k) שאינו מכוסה על ידי אחד הקווים שנעשו בשלב 3.

הערך של k מופרע מכל האלמנטים שאינם מכוסים בשורות. בהמשך, הערך של ka מתווסף לכל האלמנטים המכוסים בצומת של שתי שורות.

פריטים המכוסים בשורה אחת נותרים כמות שהם. לאחר ביצוע שלב זה אתה חוזר לשלב 3.

הקצאה אופטימלית

לאחר עצירת האלגוריתם בשלב 3, קבוצה של אפסים נבחרת כך שבכל שורה ובכל עמודה נבחר רק אפס אחד.

אם בתהליך בחירה זה אין אפס בודד בשורה או בעמודה, ייבחר אחד מהאפסים הללו. האפסים שנותרו בעמודה או בשורה זו מוסרים, וחוזרים על אותם הדברים גם עבור שאר המטלות.

אם אין הקצאת אפס יחידה, ישנם פתרונות מרובים. עם זאת העלות תישאר זהה עבור קבוצות שונות של מטלות.

כל שורות או עמודות דמה שנוספו מוסרים. האפסים שנבחרו במטריצה ​​סופית זו תואמים אפוא את המשימה האידיאלית הנדרשת במטריקס המקורי.

דוגמא

הבה נבחן חברה בה יש ארבע פעילויות (A1, A2, A3, A4) שחייבים להתבצע על ידי ארבעה עובדים (T1, T2, T3, T4). יש להקצות פעילות אחת לכל עובד.

המטריצה ​​הבאה מציגה את עלות הקצאת עובד מסוים לפעילות מסוימת. המטרה היא למזער את העלות הכוללת של המשימה המורכבת מארבע פעילויות אלה.

שלב 1: גרעו את המינימום של כל שורה

אתה מתחיל בחיסור האלמנט בערך המינימלי בכל שורה מהרכיבים האחרים באותה שורה. לדוגמה, האלמנט הקטן ביותר בשורה הראשונה הוא 69. לפיכך, 69 מופרעים מכל רכיב בשורה הראשונה. המטריצה ​​המתקבלת היא:

שלב 2: מחסירים את המינימום מכל עמודה

באותו אופן, האלמנט עם הערך המינימלי של כל עמודה מופרע מהרכיבים האחרים של אותה עמודה, ומקבל את המטריצה ​​הבאה:

שלב 3: כסו את כל האפסים במספר מינימלי של שורות

כעת נקבע את מספר הקווים המינימלי (אופקי או אנכי) הנדרש לכיסוי כל האפסים במטריקס. ניתן לכסות את כל האפסים באמצעות 3 שורות:

מכיוון שמספר השורות הנדרשות הוא שלוש והוא פחות מגודל המטריצה ​​(n = 4), אנו ממשיכים עם שלב 4.

שלב 4: צור אפסים נוספים

נבחר האלמנט הקטן ביותר שאינו מכוסה על ידי השורות, שערכו 6. ערך זה מופרע מכל האלמנטים שלא מכוסים, ואותו ערך מוסף לכל האלמנטים המכוסים בצומת של שתי שורות. התוצאה היא המטריצה ​​הבאה:

כפי שצוין בשיטה ההונגרית, יש לבצע שוב את שלב שלישי.

שלב 3 (חזרה)

שוב נקבע מספר השורות המינימלי הנדרש לכיסוי כל האפסים במטריקס. הפעם נדרשות ארבע שורות:

מכיוון שמספר השורות הנדרש הוא 4, שווה לגודל המטריצה ​​(n = 4), יש לנו הקצאה אופטימלית בין האפסים במטריקס. לכן האלגוריתם נעצר.

הקצאה אופטימלית

כפי שעולה מהשיטה, הבחירה מבין האפסים הבאים תואמת להקצאה אופטימלית:

מבחר אפסים זה מתאים להקצאה האופטימלית הבאה במטריצת העלות המקורית:

לפיכך על עובד 1 לבצע פעילות 3, עובד 2, פעילות 2, עובד 3, פעילות 1, ועובד 4 חייב לבצע פעילות 4. העלות הכוללת של משימה אופטימלית זו היא 69 + 37 + 11 + 23 = 140.

הפניות

1. האלגוריתם ההונגרי (2019). האלגוריתם ההונגרי. נלקח מ: hungarianalgorithm.com.
2. לימוד (2019). שימוש באלגוריתם ההונגרי כדי לפתור בעיות הקצאה. נלקח מ: study.com.
3. משרות חכמה (2018). שיטה הונגרית לפתרון בעיית מטלות - טכניקות כמותיות לניהול. נלקח מ: חכמה.
4. Geeks for Geeks (2019). אלגוריתם הונגרי לבעיית הקצאה. נלקח מ: geeksforgeeks.org.
5. קרלי מור, נתן לנדמן (2019). האלגוריתם התואם ההונגרי. מַברִיק. נלקח מ: brilliant.org.