בעיית זרימה
בעיית "Min cost flow" היא בעיית אופטימיזציה שמטרתה מציאת הדרך הזולה ביותר להעברת זרימה בגודל מסוים ברשת זרימה קיימת.
הגדרה
בהינתן, רשת זרימה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,G(V,E,s,t,c)} כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle s \in V} צומת מקור, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle t \in V} צומת בור וקשת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (u,v) \in E} בעלת קיבולת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,c(u,v)} , זרימה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,f(u,v)} ומחיר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,a(u,v)} . מחיר העברת הזרימה בקשת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (u,v)} הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(u,v) \cdot a(u,v)} .
מטרת הבעיה היא להעביר כמות נתונה של זרימה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,d} מקודקוד המקור (s) לקודקוד הבור (t), כך שהמחיר הכולל,
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{u,v \in V} a(u,v) \cdot f(u,v)} יהיה מינימלי.
הפתרון נדרש לקיים את אילוצי הזרימה הבאים:
אילוצי קיבול: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,f(u,v) \le c(u,v)} סימטריה נגדית: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,f(u,v) = - f(v,u)} שימור זרימה (שימור חומר): הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,\sum_{w \in V} f(u,w) = 0} for all הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,u \neq s, t} שימור גודל הזרימה הנדרש: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,\sum_{w \in V} f(s,w) = d} and הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,\sum_{w \in V} f(w,t) = d}
הכללה ובעיות הקשורות לבעיית Min cost flow
גרסאות אחרות של בעיה זו מדברות על מציאת זרימה מקסימלית בעלת המחיר הקטן ביותר מבין כל הזרימות המקסימליות האפשריות, בעיות מסוג זה נקראות "minimum cost maximum flow". הכללה של בעיה זו היא minimum cost circulation problem שבעזרתה ניתן לפתור את הבעיה הנדונה. זה נעשה על ידי חסימת ערכי קיבולות הקשתות ברשת על ידי 0 (חסם תחתון) והוספת קשת נוספת בעלת קיבולת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle c(t,s)=d} וחסם תחתון הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle l(t,s)=d} , (המחברת ישירות את קודקוד הבור (t) חזרה לקודקוד המקור (s)) אשר קובעת את הזרימה הכוללת להיות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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.
קישורים חיצוניים
בעיית זרימה33289051Q2897180