|
|
נתונה רשת קשירה עם מקור יחיד - ( צומת ו ) ויעד יחיד ( צומת ח , ( וקיימת זרימה של חומר מסויים מהמקור ליעד . לכל קשת ( נ . י ו ) ברשת נתונה קיבולתה המקסימלית , . C . . מטרתנו למצוא , מהי הזרימה המקסימלית שניתן להעביר מהמקור ליעד , באילוצי הקיבולות של הקשתות , ובהנחה שאין אבדן זרימה בצמתי ביניים . ניסוח הבעיה כבעית תכנות לינארי . נגדיר : / .. הזרימה בפועל בקשת »( i , j ) Max { F = E x . . } : n y 1 n כלומר , מקסימום זרימה היוצאת מהמקור . לכל ( 1 f j ) nnn האילוצים : 0 < x .. < C . . לכל ( נ , "ו ) - אילוצי קיבולת z x - I x . = 0 לכל k - 2 , 3 ח-ו ik kj אין אבדן זרימה בצמתי הביניים .
To the book |
|
|