בעיית זרימה

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש

בעיית "Min cost flow" הינה בעיית אופטימיזציה שמטרתה מציאת הדרך הזולה ביותר להעברת זרימה בגודל מסוים ברשת זרימה קיימת.

הגדרה

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

מטרת הבעיה הינה להעביר כמות נתונה של זרימה מקודקוד המקור (s) לקודקוד הבור (t), כך שהמחיר הכולל,

יהיה מינימלי.

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

אילוצי קיבול:
סימטריה נגדית:
שימור זרימה (שימור חומר): for all
שימור גודל הזרימה הנדרש: and

הכללה ובעיות הקשורות לבעיית Min cost flow

גרסאות אחרות של בעיה זו מדברות על מציאת זרימה מקסימלית בעלת המחיר הקטן ביותר מבין כל הזרימות המקסימליות האפשריות, בעיות מסוג זה נקראות "minimum cost maximum flow". הכללה של בעיה זו היא minimum cost circulation problem שבעזרתה ניתן לפתור את הבעיה הנדונה. זה נעשה על ידי חסימת ערכי קיבולות הקשתות ברשת על ידי 0 (חסם תחתון) והוספת קשת נוספת בעלת קיבולת וחסם תחתון , (המחברת ישירות את קודקוד הבור (t) חזרה לקודקוד המקור (s)) אשר קובעת את הזרימה הכוללת להיות . את הבעיה ניתן לחלק למקרים פרטיים בהם אילוצי הקיבולת מוסרים (ולכן הבעיה הופכת לבעיית מציאת המסלול הקצר ביותר), ומקרים בהם אנו מתעלמים ממחיר הזרימה (ולכן מחיר הזרימה דרך כל אחת מהקשתות שווה), בהם נקבל את בעיית הזרימה המקסימלית.

שיטות לפתרון הבעיה

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

אלגוריתמים ידועים (שקיימים במספר ווריאציות שונות) לפתרון הבעיה הם:

  • Cycle Canceling
  • Minimum Mean Cycle Canceling
  • Successive Shortest Path and Capacity Scaling - שיטות דואליות שהן הכללה של שיטת פורד פולקרסון.
  • Cost Scaling
  • Network Simplex - מקרה פרטי של תכנון לינארי בעזרת simplex medthod .

ראו גם

לקריאה נוספת

  • Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin (1993). Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Inc.. ISBN 0-13-617549-X
  • Morton Klein (1967). "A primal method for minimal cost flows with applications to the assignment and transportation problems". Management Science 14: 205-220.
  • Andrew V. Goldberg and Robert E. Tarjan (1989). "Finding minimum-cost circulations by canceling negative cycles". Journal of the ACM 36 (4): 873-886.
  • Jack Edmonds and Richard M. Karp (1972). "Theoretical improvements in algorithmic efficiency for network flow problems". Journal of the ACM 19 (2): 248-264.
  • Andrew V. Goldberg and Robert E. Tarjan (1990). "Finding minimum-cost circulations by successive approximation". Math. Oper. Res. 15 (3): 430-466.

קישורים חיצוניים