שיטת פוגל היא הליך היוריסטי המשמש לפתרון בעיות אופטימיזציה הקשורות לתחבורה ולעלויות הנלוות לה.
מטרתה העיקרית של שיטת פוגל היא למזער את העלויות הללו. כשאנחנו אומרים שזה היוריסטי, אנחנו מתכוונים שהוא משתמש בקריטריונים פשוטים כדי לפתור בעיות קשות. בנוסף, יש לו יתרון על פני אחרים מכיוון שלמרות שהוא דורש איטרציות רבות יותר, התוצאות הראשוניות שלו - לא פיקטיביות - טובות יותר. זה דומה לשיטות אחרות, כמו השיטה ההונגרית.
מקור שיטת פוגל
עם בוא המהפכה התעשייתית גברו הבעיות העסקיות. ביניהם אלה של הקצאת משימות ועלויות. מסיבה זו צצו כמה שיטות שאיפשרו לעשות זאת ביעילות. לפיכך, בשנת 1955 הציע הרולד וו. קון את השיטה ההונגרית, במקביל לכך שדומים החלו להתפתח בענף ניהול התפעול.
אחת הבעיות העיקריות מתעוררת בתחבורה. המטרה היא כיצד להחליט מסלולים, זמנים או יעדים, בהתבסס על הצורך למזער את העלויות ולהיות מסוגלים לספק את הביקוש עם ההיצע הזמין. ויליאם ר 'פוגל מציע, לשם כך, את השיטה המקבלת את שמו. שיטה שבאמצעות אלגוריתם פותרת בעיות הקשורות להובלות והקצאתן.
צעדים לביצוע בשיטת פוגל
היתרון העיקרי של שיטת פוגל הוא שהיא משתמשת בסדרת קנסות כדי לחשב את העלות המינימלית, כמו גם שהחישוב שלה פשוט. מאידך, החיסרון העיקרי הוא בכך שהוא דורש מאמצים גדולים יותר מאחרים ועל סמך זה הוא אינו מספק קריטריון להחליט אם הפיתרון הוא הטוב ביותר.
עם זאת, בואו נסקור את הצעדים שעלינו לנקוט בכדי לעשות זאת; למרות שנראה זאת ביתר פירוט בדוגמה:
- ראשית, עלינו לחשב עונש שנוסיף למטריצה הראשונית. לביצוע שלב זה מופחתות שתי העלויות הנמוכות ביותר בכל שורה ועמודה. לאחר מכן משתמשים בשורה או בעמודה עם העונש הגבוה ביותר. אם ישנם שני ערכים מקסימליים שווים, הבחירה היא בידי האדם שמבצע את הניתוח.
- לאחר מכן, עלינו להסתכל על השורה או העמודה שבחרנו. אנו בוחרים את התא בעלות הנמוכה ביותר ומקצים לו את המספר הגדול ביותר של יחידות הביקוש שאנו יכולים, תוך התחשבות בהיצע הזמין. באופן זה, שאר השורה או העמודה ההם יהיו אפסים ונוכל לחסל אותה.
- לבסוף, ישנם מספר כללים סופיים שכדאי לזכור. אם נותרה רק שורה אחת, האלגוריתם נעצר. אם יש לזה ערכים חיוביים, עליך לקבוע את המשתנים הבסיסיים של הפתרון. אחרת, הוא חוזר לנקודה הראשונה והתהליך מתחיל מחדש.
דוגמה לשיטת פוגל
על מנת להבין טוב יותר מושג זה, מוצגת להלן דוגמא לכך.
בואו נדמיין שיש לנו סדרה של מפעלי ייצור, שחייבים לספק סחורות ליעדים מסוימים. ראשית, אנו יוצרים את טבלת הכניסה הכפולה הראשונית המציגה את עלויות היחידה עבור כל אפשרות. מצד שני, יכולות ההיצע (O) וצורכי הביקוש (D) מוצגות בשורה ובעמודה המתאימים, כמו גם בטבלה מימין (איור 1).
בשלב הראשון מחושבים העונשים (Pe1), כפי שהוסבר קודם, ונבחר הגבוה ביותר מהם, השלושה (כחול כהה) מהקופסה (Pe1, D3). אנו בוחרים את הערך הקטן ביותר בעמודה זו, שיהיה הארבעה (כחול באמצע) של התיבה (P2, D3). בטבלה מימין, באותו מיקום, מוכנס הערך הגבוה ביותר האפשרי על פי דרישת העמודה ההיא, שהיא 30 (אפור). לכן, יישארו 10 בהצעה, שכן המקסימום שלה הוא 40.
לכן, אנו חוזרים לתהליך בשלב 2, לאחר שהעמודה D3 בוטלה. אנו מחשבים את העונש השני (Pe2), וחוזרים על השלבים הקודמים. השורה שנבחרה תהיה P1, עם הערך הנמוך ביותר של חמישה ועם ערך מקסימאלי בטבלת ההיצע והביקוש של חמישים. בשלב 3 אנו עושים את אותו הדבר, כולל העונש השלישי (Pe3).
כפי שאנו רואים, באיור 2 מופיע רק עמודה D2 וכל הערכים חיוביים. במובן זה הגענו לסוף. כעת, כאשר אנו לוקחים את שתי העמדות הללו (P2D2; P3D2) בטבלת ההיצע והביקוש, אנו רואים אילו ערכים חסרים כדי שהכל יהיה אפס. במקרה זה המספרים החסרים הם עשרה וחמישה עשר.
לבסוף אנו יכולים לראות כי שיטת Vogel מציעה עלות כוללת המחושבת על ידי הכפלת נתונים מימין בעלויות היחידה שלה משמאל. הכנסנו את הטבלה המקורית מההתחלה כדי להקל על החישוב. העלות הכוללת תהיה 650 ובתורנו נוכל לראות את החלק האפשרי של כל אפשרות.
