8. fejezet - Veszteséges-nyereséges folyamfeladat

A hagyományos folyamproblémában a folyam az éleken megőrződött. A gyakorlatban elképzelhetők olyan feladatok is, amikor ez nem áll fenn. Rendeljünk minden élhez a kapacitáson kívül egy nemnegatív szorzót. A veszteséges-nyereséges folyamnál ha egy élen folyam megy be az él kezdetén, akkor folyam jön ki az él végén. Ha , akkor az él veszteséges, ha pedig , akkor nyereséges. Ha minden , akkor a standard folyamfeladatot nyerjük. A veszteségek és a nyereségek miatt nem szükségképpen egyenlő a forrásból kifolyó és a nyelőben elnyelődő folyam értéke. A folyam maga is lehet tehát veszteséges vagy nyereséges. A folyam veszteségét a forrásból kifolyó és a nyelőbe befolyó folyam értékének a különbségeként definiáljuk, képletben . Feladatunk olyan folyam keresése, amelynek a vesztesége a legkisebb.

A minimális veszteségű folyamfeladat alatt a következő problémák valamelyikét értjük:

A megfogalmazott feladatoknál is érvényesek az élekre írt kapacitáskorlátok, azaz

és a közbülső pontokban érvényes a Kirchoff csomóponti törvény, amely szerint

Ezeknek a feladatoknak a megoldásával nem foglalkozunk, csupán a továbbfejlesztési lehetőségekre kívántunk rámutatni.