300 דוגמאות

בעיית זרימה מרבית

Maximum Flow Problem

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

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



גיבשו את המודל

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



בעיית זרימה מרבית ב- Excel

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



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

ב. מה האילוצים להחלטות אלה? זרימת הרשת (Flow Out - Flow In) של צומת A, B, C, D ו- E צריכה להיות שווה ל 0. במילים אחרות, Flow Out = Flow In. כמו כן, לכל קשת יכולת קבועה. הזרימה על כל קשת צריכה להיות פחות מיכולת זו.

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



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

שם טווח תאים
מ B4: B15
ל C4: C15
זְרִימָה D4: D15
קיבולת F4: F15
דרישת אספקה K5: K9
MaximumFlow D17

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

הכנס פונקציות

הסבר: ה SUMIF פונקציות מחשבות את זרימת הרשת של כל צומת. עבור צומת A, פונקציית SUMIF הראשונה מסכמת את הערכים בעמודה Flow עם 'A' בעמודה From (Flow Out). הפונקציה השנייה SUMIF מסכמת את הערכים בעמודה Flow עם 'A' בעמודה To (Flow In). זרימה מרבית שווה לערך בתא I4, שהוא הזרימה החוצה מצומת S. מכיוון שלצומת A, B, C, D ו- E יש זרימה נטו של 0, זרימה של צומת S תהיה שווה לזרימה פנימה של צומת T.

ניסוי וטעייה

בעזרת ניסוח זה, קל לנתח כל פתרון ניסיון.

1. לדוגמא, הנתיב SADT עם זרימה של 2. הנתיב SCT עם זרימה של 4. הנתיב SBET עם זרימה של 2. נתיבים אלה נותנים זרם כולל של 8.

פתרון ניסיון

כיצד להכין רשימת תבליטים באקסל

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

לפתור את המודל

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

1. בכרטיסיה נתונים, בקבוצה ניתוח, לחץ על פותר.

לחץ על פותר

הערה: לא מצליחים למצוא את כפתור הפותר? לחץ כאן כדי לטעון את תוסף לפותר .

הזן את הפרמטרים לפותר (המשך לקרוא). התוצאה צריכה להיות עקבית עם התמונה למטה.

פרמטרים לפותר

יש לך אפשרות להקליד את שמות הטווחים או ללחוץ על התאים בגיליון האלקטרוני.

2. הזן את MaximumFlow עבור המטרה.

3. לחץ על מקס.

4. הזן זרימה עבור התאים המשתנים המשתנים.

5. לחץ על הוסף כדי להזין את האילוץ הבא.

אילוץ זרימת נטו

6. לחץ על הוסף כדי להזין את האילוץ הבא.

אילוץ קיבולת

7. סמן 'הפוך משתנים בלתי מוגבלים לבלתי שליליים' ובחר 'LP פשוט'.

8. לבסוף, לחץ על פתר.

תוֹצָאָה:

תוצאות פותר

הפיתרון האופטימלי:

תוצאה מקסימאלית של בעיית זרימה

מסקנה: השביל SADT עם זרימה של 2. השביל SCT עם זרימה של 4. השביל SBET עם זרימה של 2. השביל SCET עם זרימה של 2. השביל SACET עם זרימה של 1. השביל SACDT עם זרימה של 1. נתיבים אלה נותנים זרימה מקסימאלית של 12.

5/7 הושלם! למידע נוסף על הפותר>
עבור לפרק הבא: ניתוח ToolPak



^