✅ בעיית הנתיב הקצרה ביותר באקסל

תוכן העניינים

גיבוש המודל | ניסוי וטעייה | פתור את המודל

השתמש בפותר ב לְהִצטַיֵן למצוא את הדרך הכי קצרה מצומת S לצומת T ברשת בלתי מכוונת. נקודות ברשת נקראות צמתים (S, A, B, C, D, E ו- T). קווים ברשת נקראים קשתות (SA, SB, SC, AC וכו ').

גיבוש המודל

המודל שאנו הולכים לפתור נראה כדלקמן ב- Excel.

1. לנסח זאת בעיה בנתיב הקצר ביותר, ענה על שלוש השאלות הבאות.

א. מה ההחלטות שצריך לקבל? לבעיה זו, אנו זקוקים לאקסל כדי לברר אם קשת נמצאת בנתיב הקצר ביותר או לא (כן = 1, לא = 0). לדוגמה, אם SB הוא חלק מהנתיב הקצר ביותר, תא F5 שווה 1. אם לא, תא F5 שווה ל- 0.

ב. מהם האילוצים על החלטות אלו? זרימת הרשת (זרימה החוצה - זרימה פנימה) של כל צומת צריכה להיות שווה לאספקה/ביקוש. לצומת S צריכה להיות רק קשת יוצאת אחת (זרימה נטו = 1). לצומת T צריכה להיות רק קשת נכנסת אחת (נטו זרימה = -1). לכל שאר הצמתים צריכה להיות קשת יוצאת אחת וקשת נכנסת אם הצומת נמצא בנתיב הקצר ביותר (נטו זרימה = 0) או ללא זרימה (זרימה נטו = 0).

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

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

שם טווח	תאים
מ	B4: B21
ל	C4: C21
מֶרְחָק	D4: D21
ללכת	F4: F21
NetFlow	I4: I10
דרישת אספקה	K4: K10
מרחק כולל	F23

3. הכנס את הפונקציות הבאות.

הסבר: הפונקציות SUMIF מחשבות את זרימת הנטו של כל צומת. עבור צומת S, הפונקציה SUMIF מסכמת את הערכים בעמודה Go עם "S" בעמודה From. כתוצאה מכך, רק תא F4, F5 או F6 יכול להיות 1 (קשת אחת יוצאת). עבור צומת T, הפונקציה SUMIF מסכמת את הערכים בעמודה Go עם "T" בעמודה To. כתוצאה מכך, רק תא F15, F18 או F21 יכול להיות 1 (קשת נכנסת אחת). עבור כל הצמתים האחרים, Excel מחפש בעמודה מאת וללא. סך המרחק שווה לתוצר הסכום של מרחק ומעבר.