השיטה ההונגרית היא אלגוריתם המאפשר למזער עלויות בבעיית אופטימיזציה על בסיס תכנות ליניארי.
מטרת השיטה ההונגרית היא למצוא את העלות המינימלית של מכלול משימות שיש לבצע על ידי האנשים המתאימים ביותר.
היא משתמשת בתכנות ליניארי (PL) לביצוע סדרת צעדים הניתנת לאוטומציה. לפיכך, לכלים כמו התוכנה הסטטיסטית R (בין היתר) יש כמה חבילות שימושיות מאוד לבעיות אופטימיזציה אלה.
מקור השיטה ההונגרית
יוצרו היה המתמטיקאי ההונגרי (ומכאן שמו) הרולד וו.קון בשנת 1955. מתמטיקאי אחר, ג'יימס מונקרס, תיקן אותו בשנת 1957. עם התפתחות זו הוא קיבל שמות אחרים כמו אלגוריתם ההקצאה מונקרס או קון-מונקרס.
מצד שני, לשיטה זו תקדים אצל שני מחברים, דנס קוניג וג'ן אג'ווארי, שניהם יהודים והונגרים. הראשון פיתח את תורת הגרפים שעליה מבוסס אלגוריתם זה. השני כלל את משפט קניג ואיפשר לקון לפתח את השיטה.
שלבי השיטה ההונגרית
השלבים שיש לבצע מאפשרים לבצע את השיטה ההונגרית בצורה פשוטה באמצעות גיליון אלקטרוני. בנוסף, תוכנית זו אותה אנו מראים תאפשר לנו לראות באופן עולמי את התהליך אותו נפתח בפירוט בדוגמה האחרונה.
- כשלבים ראשוניים, עליך להקצות אנשים (שורות) לסדרת פרויקטים (עמודות). בנוסף, יש צורך לחשב את העלויות השונות של כל פרויקט בהתאם למי שמבצע אותו ולבנות מטריצה (C) עם מידע זה.
- במטריצה (C) אנו מחפשים את הערך המינימלי של כל שורה. אנו מחסירים זאת מכל האלמנטים בשורה ומבצעים אותה פעולה עם העמודות. מטריצה חדשה (C`) תופיע עם תוצאות הפעולות הקודמות.
- לאחר מכן, אנו יוצרים את "גרף השוויון", המאפשר לנו לבחור את המשימות והפרויקטים בעלות הנמוכה ביותר. האופטימלי יהיה האלמנטים שהתוצאה שלהם הייתה אפס. אם נכון שאין אלמנט עם ערך אפס המוקצה ליותר משורה אחת, האלגוריתם מסתיים.
- אחרת, יש לבצע מטלה חדשה. מתבצעת מטריצה חדשה עליה מוחלים סדרת שינויים, כפי שנראה בדוגמה. אנו משחזרים את הגרף וממשיכים עד שיש לנו מטריצה שיש בה לפחות אפס אחד בכל שורה ובמיקומים שאינם חוזרים.
- עם מידע זה יש לנו כבר את האנשים והפרויקטים שהוקצו (האפסים) שמייעלים את הבעיה. אם כבר הוקצתה משימה בשורה קודמת, היא מושמכת בשורה הבאה. כדי לחשב את העלות המינימלית אנו מוסיפים את עלויות המטריצה הראשונית המופיעות במיקום האפסים הללו.
דוגמה לשיטה ההונגרית
בואו נסתכל על דוגמה פשוטה לשיטה ההונגרית של. בואו נדמיין שיש לנו שלושה עובדים והם צריכים להיות משויכים לשלושה פרויקטים. אנו יוצרים את המטריצה הראשונית (C) ואת ערכי העלות בכל תא. לשם כך עליכם להשתמש במידע הקיים בחברה. ברגע שיש לנו את כל זה אנו מתחילים בתהליך. גיליון אלקטרוני יכול לעזור.
אנו מחשבים את המינימום של כל שורה ומחסירים אותם מהאלמנטים של אותה שורה ועושים את אותו הדבר עם העמודות (שלבים 1 ו -2). במטריצה המתקבלת (C`) אנו מציירים קווים בצורה כזו שהם מכסים את כל האפסים ובתורם חוצים זה את זה (שלב 3). אנו רואים שיש שתי שורות, אך הערך הגדול ביותר של מספר השורות או העמודות הוא שלוש. עלינו להמשיך.
כעת אנו בוחרים את המספר הקטן ביותר של המספרים שלא נחשפו, בדוגמה זו הוא שניים (כחול כהה). אנו גורעים אותו מהקודמים ומוסיפים אותו לאלה שנמצאים במקום בו הקווים מצטלבים. במקרה שלנו מדובר בשניים נוספים (E3, T1). נשארנו עם מטריצה חדשה (שלב 4). אנו משרטטים מחדש את הקווים וסופרים. ישנן שלוש שורות, זהות למספר השורות או העמודות. האלגוריתם הסתיים.
אנו מתחילים בשורה או בעמודה עם הכי מעט אפסים (E1, T1). אם כבר הוקצתה משימה לא ניתן להקצות אותה מחדש, למשל, עם E2 אינך יכול להשתמש באפס הראשון של T1, מכיוון שמשימה זו הוקצתה ל- E1. העלות הכוללת, בשיטה ההונגרית, תהיה סכום העלויות של המטריצה המקורית (שלב 1) הממוקמת באותו מיקום כמו האפסים שנבחרו (שלב 5).