בעיית זרימה

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

הגדרה

בהינתן, רשת זרימה $\,G(V,E,s,t,c)$ כאשר $s\in V$ צומת מקור, $t\in V$ צומת בור וקשת $(u,v)\in E$ בעלת קיבולת $\,c(u,v)$, זרימה $\,f(u,v)$ ומחיר $\,a(u,v)$. מחיר העברת הזרימה בקשת $(u,v)$ הוא $f(u,v)\cdot a(u,v)$.

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

$\sum _{u,v\in V}a(u,v)\cdot f(u,v)$ יהיה מינימלי.

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

אילוצי קיבול:	$\,f(u,v)\leq c(u,v)$
סימטריה נגדית:	$\,f(u,v)=-f(v,u)$
שימור זרימה (שימור חומר):	$\,\sum _{w\in V}f(u,w)=0$ for all $\,u\neq s,t$
שימור גודל הזרימה הנדרש:	$\,\sum _{w\in V}f(s,w)=d$ and $\,\sum _{w\in V}f(w,t)=d$

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

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

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

בעיית 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.. מסת"ב 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.

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

• LEMON C++ library with several maximum flow and minimum cost circulation algorithms

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

33289051בעיית זרימה