בחינת סוף סמסטר, פברואר 2026 · שיעור פתרון

שאלה 3: בעיית תובלה עם מחסור וקנסות

שיעור תאוריה רלוונטי

נוסח השאלה

חברת הובלה מספקת יחידות משני מחסנים לשלושה לקוחות. למחסן A היצע 50 ולמחסן B היצע 30. הביקושים של לקוחות 1, 2 ו-3 הם 20, 40 ו-30 יחידות, בהתאמה.

מקור \ יעדלקוח 1לקוח 2לקוח 3היצע
מחסן A15302050
מחסן B10453030
ביקוש20403090

יש לספק את כל דרישת הלקוחות. לכל יחידה שלא תסופק יש קנס: 90 ללקוח 1, 80 ללקוח 2 ו-110 ללקוח 3.

  1. א. מצאו פתרון בסיסי אפשרי התחלתי באמצעות שיטת המחיר המינימלי. הסבירו את הפתרון וחשבו את עלויות ההובלה, עלויות הקנס והעלות הכוללת.
  2. ב. האם הפתרון שמצאתם בסעיף א אופטימלי? נמקו. אם לא, שפרו אותו באמצעות פוטנציאלים ומעגלי שיפור, ובצעו לפחות שתי בדיקות איטרטיביות בדרך לאופטימום.
  3. ג. אם אי אפשר לשלוח רובוטים ממחסן B ללקוח 3, מה יהיו התשובות לסעיפים א-ב?

זיהוי השיטה

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

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

פתרון מודרך

איזון הבעיה

ההיצע הכולל הוא 50+30=80, והביקוש הכולל הוא 20+40+30=90. חסרות 10 יחידות. נוסיף מקור דמה D עם היצע 10. הקצאה מן המקור הדמי ללקוח פירושה ביקוש שלא סופק, ולכן עלות התא היא הקנס של אותו לקוח.

מקור \ יעדלקוח 1לקוח 2לקוח 3היצע
A15302050
B10453030
D - מחסור908011010
ביקוש20403090

נסמן ב-xᵢⱼ את הכמות שמוקצית ממקור i∈{A,B,D} ללקוח j∈{1,2,3}. בשורת D, הכמות היא מחסור ולא משלוח ממשי.

א פתרון התחלתי בשיטת המחיר המינימלי

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

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

  1. העלות הנמוכה ביותר היא 10 בתא B-1. מקצים min(30,20)=20. לקוח 1 סופק ול-B נשארו 10.
  2. התא הזול הבא הוא A-3 בעלות 20. מקצים min(50,30)=30. לקוח 3 סופק ול-A נשארו 20.
  3. נשאר לקוח 2 בלבד. מקצים 20 מ-A, עוד 10 מ-B, ואת המחסור 10 ממקור הדמה בעלות קנס 80 ליחידה.
מקור \ יעדלקוח 1לקוח 2לקוח 3סך שורה
A0203050
B2010030
D - מחסור010010
סך עמודה20403090
עלות הובלה = 20·10 + 30·20 + 20·30 + 10·45 = 1850 קנס מחסור = 10·80 = 800 עלות כוללת = 1850 + 800 = 2650

יש חמישה תאים בסיסיים חיוביים, ובבעיה המאוזנת יש שלושה מקורות ושלושה יעדים. אכן m+n-1=3+3-1=5, ולכן הפתרון הבסיסי אינו מנוון.

תוצאת הסעיף: הפתרון ההתחלתי עולה 2,650: מתוכם 1,850 עלויות הובלה ו-800 קנס על 10 יחידות מחסור אצל לקוח 2.

ב בדיקת אופטימליות ושיפור

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

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

איטרציה 1: בדיקת הפתרון ההתחלתי

בתאים הבסיסיים פותרים uᵢ+vⱼ=cᵢⱼ. נבחר uA=0:

A₂: uA+v₂=30   ⇒   v₂=30 A₃: uA+v₃=20   ⇒   v₃=20 B₂: uB+v₂=45   ⇒   uB=15 B₁: uB+v₁=10   ⇒   v₁=-5 D₂: uD+v₂=80   ⇒   uD=50

לכל תא לא בסיסי מחשבים Δᵢⱼ=cᵢⱼ-uᵢ-vⱼ:

תאחישובעלות מצומצמת
A₁15-0-(-5)20
B₃30-15-20-5
D₁90-50-(-5)45
D₃110-50-2040

הערך ΔB,3=-5 שלילי, ולכן כל יחידה שנכניס לתא B₃ יכולה להפחית את העלות ב-5, כל עוד נשמור על מאזני השורות והעמודות.

מעגל השיפור הוא:

B₃(+) → B₂(-) → A₂(+) → A₃(-) → B₃ θ = min{xB,2,xA,3} = min{10,30} = 10

מוסיפים 10 בתאי הפלוס ומחסירים 10 בתאי המינוס:

מקור \ יעדלקוח 1לקוח 2לקוח 3סך שורה
A0302050
B2001030
D - מחסור010010
סך עמודה20403090
עלות חדשה = 20·10 + 10·30 + 30·30 + 20·20 + 10·80 = 2600 שיפור = 2650 - 2600 = 50

איטרציה 2: אימות הפתרון החדש

התא B₂ התאפס ויצא מן הבסיס. שוב נבחר uA=0. מן התאים הבסיסיים A₂, A₃, B₁, B₃ ו-D₂ מתקבלים:

uA=0,   uB=10,   uD=50 v₁=0,   v₂=30,   v₃=20
תא לא בסיסיעלות מצומצמת
A₁15-0-0=15
B₂45-10-30=5
D₁90-50-0=40
D₃110-50-20=40

כל העלויות המצומצמות אינן שליליות, ולכן אין מסלול נוסף שיכול להוזיל את העלות.

תוצאת הסעיף: הפתרון ההתחלתי אינו אופטימלי. לאחר מעגל שיפור אחד מתקבל פתרון אופטימלי בעלות 2,600.

ג איסור משלוח ממחסן B ללקוח 3

נוסח הסעיף: אם אי אפשר לשלוח ממחסן B ללקוח 3, מה יהיו התשובות לסעיפים א-ב?

הרעיון: מסלול אסור אינו מועמד להקצאה ואינו נבדק כתא נכנס. הפתרון ההתחלתי מסעיף א אינו משתמש ב-B₃, ולכן הוא עדיין אפשרי.

סעיף א מחדש: שיטת המחיר המינימלי נותנת אותה הקצאה התחלתית, משום שהמסלול B₃ לא קיבל בה יחידות. העלות נשארת 2,650.

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

ΔA,1=20,   ΔD,1=45,   ΔD,3=40

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

תוצאת הסעיף: ההקצאה מסעיף א נשארת, והעלות האופטימלית תחת האיסור היא 2,650.

תשובה סופית

  1. א. ההקצאה ההתחלתית היא A₂=20, A₃=30, B₁=20, B₂=10 ומחסור 10 אצל לקוח 2. עלות ההובלה 1,850, הקנס 800 והעלות הכוללת 2,650.
  2. ב. התא B₃ נכנס עם Δ=-5 ו-θ=10. הפתרון האופטימלי הוא A₂=30, A₃=20, B₁=20, B₃=10 ומחסור 10 אצל לקוח 2, בעלות 2,600.
  3. ג. כאשר B₃ אסור, הפתרון ההתחלתי נעשה אופטימלי והעלות היא 2,650.

המשך במבחן

בחינת סוף סמסטר, פברואר 2026 · שאלה 3

זהו פתרון השאלה האחרון במבחן.

חזרה לרשימת המבחנים