שיעור תאוריה עם דוגמה מודרכת

בעיית תובלה: מפתרון התחלתי לאופטימום

איך מזהים שהנושא מתאים

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

אינטואיציה

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

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

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

הגדרות פורמליות

min Z = ∑ᵢ∑ⱼ cᵢⱼxᵢⱼ ממזערים את עלות המשלוחים בכל צירופי המקור והיעד.

∑ⱼ xᵢⱼ = sᵢ, i = 1,...,m בכל שורת מקור, סכום המשלוחים שווה להיצע של אותו מקור.

∑ᵢ xᵢⱼ = dⱼ, j = 1,...,n בכל עמודת יעד, סכום המשלוחים שווה לביקוש של אותו יעד.

xᵢⱼ ≥ 0 כמות משלוח אינה יכולה להיות שלילית.

סימון או מושג	משמעות
xᵢⱼ	הכמות שנשלחת ממקור i ליעד j.
cᵢⱼ	עלות משלוח של יחידה אחת ממקור i ליעד j.
sᵢ	ההיצע הזמין במקור i.
dⱼ	הביקוש הנדרש ביעד j.
תא בסיסי	תא שהקצאתו משתתפת בבסיס הנוכחי. בפתרון לא מנוון יש m+n-1 תאים בסיסיים.
uᵢ, vⱼ	פוטנציאל של שורת מקור ופוטנציאל של עמודת יעד.
Δᵢⱼ	העלות המצומצמת של תא לא בסיסי.
θ	כמות העדכון במעגל השיפור.

הבעיה מאוזנת כאשר:

∑ᵢ sᵢ = ∑ⱼ dⱼ

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

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

שיטת פתרון

שלב 1: פתרון התחלתי

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

שיטת המחיר המינימלי:

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

שיטת הקנסות של פוגל:

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

שלב 2: בדיקת אופטימליות בשיטת הפוטנציאלים

בכל תא בסיסי כותבים uᵢ+vⱼ=cᵢⱼ.
קובעים פוטנציאל אחד לאפס ופותרים את שאר הפוטנציאלים.
לכל תא לא בסיסי מחשבים Δᵢⱼ=cᵢⱼ-uᵢ-vⱼ.
בבעיית מינימום, אם כל העלויות המצומצמות אינן שליליות, הפתרון אופטימלי.
אם יש ערך שלילי, התא בעל הערך השלילי ביותר נכנס לבסיס.

שלב 3: מעגל שיפור

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

דוגמה מלאה: שלושה מקורות וארבעה יעדים

בכל תא המספר הכחול הקטן הוא העלות ליחידה. ההיצע הכולל הוא 90+40+100=230, והביקוש הכולל הוא 70+30+50+80=230; לכן הבעיה מאוזנת.

מקור \ יעד	יעד 1	יעד 2	יעד 3	יעד 4	היצע
מקור 1	10	14	13	9	90
מקור 2	17	8	15	14	40
מקור 3	19	20	13	21	100
ביקוש	70	30	50	80	230

א. פתרון בפינה הצפון-מערבית

מקור \ יעד	יעד 1	יעד 2	יעד 3	יעד 4	היצע
מקור 1	1070	1420	13	9	90
מקור 2	17	810	1530	14	40
מקור 3	19	20	1320	2180	100
ביקוש	70	30	50	80	230

W_NW = 10·70 + 14·20 + 8·10 + 15·30 + 13·20 + 21·80 W_NW = 3,450

ב. פתרון התחלתי בשיטת פוגל

איטרציה	הקנס הגדול	התא הזול שנבחר	הקצאה
1	עמודה 1: 17-10=7	x₁₁, עלות 10	min(90,70)=70
2	שורה 3: 20-13=7	x₃₃, עלות 13	min(100,50)=50
3	שורה 2 או עמודה 2: קנס 6	x₂₂, עלות 8	min(40,30)=30
4	נותר יעד 4 בלבד	x₁₄,x₂₄,x₃₄	20,10,50

מקור \ יעד	יעד 1	יעד 2	יעד 3	יעד 4	היצע
מקור 1	1070	14	13	920	90
מקור 2	17	830	15	1410	40
מקור 3	19	20	1350	2150	100
ביקוש	70	30	50	80	230

W_Vogel = 10·70 + 8·30 + 13·50 + 9·20 + 14·10 + 21·50 W_Vogel = 2,960

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

ג. פוטנציאלים ועלויות מצומצמות

נקבע u₁=0. זוהי בחירת נרמול שרירותית; כל בחירה אחרת עקבית תיתן אותן עלויות מצומצמות.

u₁ = 0 בוחרים פוטנציאל אחד כאפס כדי שלמערכת תהיה נקודת התחלה.

v₁ = 10, v₄ = 9 מהתאים הבסיסיים x₁₁ ו-x₁₄: מחסרים את u₁ מעלות התא.

u₂ = 14-v₄ = 5, v₂ = 8-u₂ = 3 עוברים דרך התאים הבסיסיים x₂₄ ו-x₂₂.

u₃ = 21-v₄ = 12, v₃ = 13-u₃ = 1 עוברים דרך התאים הבסיסיים x₃₄ ו-x₃₃.

הערת דיוק לגבי קובץ המקור

במקור נכתב שנקבע v₄=0, אך הפוטנציאלים שמופיעים בו חושבו לפי u₁=0. שתי בחירות הנרמול מותרות, אבל אין לערבב ביניהן. כאן כל החישובים משתמשים בעקביות ב-u₁=0.

תא לא בסיסי	חישוב	עלות מצומצמת
x₁₂	14-0-3	11
x₁₃	13-0-1	12
x₂₁	17-5-10	2
x₂₃	15-5-1	9
x₃₁	19-12-10	-3
x₃₂	20-12-3	5

מכיוון ש-Δ₃₁=-3, התא x₃₁ נכנס לבסיס.

ד. מעגל השיפור

x₃₁(+) → x₃₄(-) → x₁₄(+) → x₁₁(-) → x₃₁ θ = min{x₃₄, x₁₁} = min{50,70} = 50

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

x₃₁ = 0+50 = 50 תא פלוס: מוסיפים את θ.

x₃₄ = 50-50 = 0 תא מינוס: מחסרים את θ; התא מתאפס ויוצא מהבסיס.

x₁₄ = 20+50 = 70 תא פלוס: מוסיפים את אותה כמות.

x₁₁ = 70-50 = 20 תא מינוס: מחסרים את אותה כמות.

מקור \ יעד	יעד 1	יעד 2	יעד 3	יעד 4	היצע
מקור 1	1020	14	13	970	90
מקור 2	17	830	15	1410	40
מקור 3	1950	20	1350	21	100
ביקוש	70	30	50	80	230

ה. הוכחת אופטימליות

לאחר העדכון נקבע שוב u₁=0. מתקבלים u=(0,5,9) ו-v=(10,3,4,9).

תא לא בסיסי	Δᵢⱼ
x₁₂	11
x₁₃	9
x₂₁	2
x₂₃	6
x₃₂	8
x₃₄	3

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

W* = 10·20 + 9·70 + 8·30 + 14·10 + 19·50 + 13·50 W* = 2,810

פתרון	עלות
הפינה הצפון-מערבית	3,450
פתרון התחלתי של פוגל	2,960
פתרון אופטימלי לאחר מעגל השיפור	2,810

הערות מוכנות למבחן

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

שאלות מבחן קשורות