3. fejezet - Minimális út-maximális potenciál feladatpár

3.1. 3.1. A feladatpár megfogalmazása

Legyen adott egy hálózat. A hálózat éleihez rendelt nemnegatív egész számot az él hosszának nevezzük. Legyen a hálózatnak két kitüntetett pontja .

Minimális út feladat (primál feladat)

Meghatározandó azon s-ből t-be vezető

út, amely mentén a

mennyiség minimális.

A k(P) mennyiséget úthossznak nevezzük.

Maximális potenciál feladat (duál feladat)

Meghatározandó a hálózat minden pontjához egy , egész szám úgy, hogy

maximális legyen, feltéve, hogy

A értéket az x pont potenciáljának nevezzük. Az összes ponthoz rendelt értékeket együttesen () potenciálrendszernek szokás nevezni.

A feladatok jobb megértése érdekében jelentsen a hálózat egy éle egy útszakaszt, az élre írt szám pedig ezen útszakaszon történő szállítás költségét jelentse. Ez a költség arányos lehet az él hosszúságával, innen az úthossz elnevezés. Ezen értelmezés szerint a minimális út feladat nem más, mint a két kitüntetett pont közötti legkisebb költséggel megvalósítható szállítás útvonalának meghatározása.

A maximális potenciál feladatot pedig a következő okoskodással érthetjük meg leginkább. Tegyük fel, hogy egy vállalkozó felajánlja, hogy a szállítást elvégzi a szállíttató helyett és megad minden pontra egy értéket, amely azt jelenti, hogy az s-ből az x-be ennyiért hajlandó szállítani. A árajánlatnak nyilván olyannak kell lennie, hogy elfogadható legyen. Egyrészt tehát az s-be való szállítás zérus legyen, másrészt, ha s-ből az x-be a vállalkozó szállítana (ennek költsége: ), utána az élen pedig a szállíttató szállítana (ennek költsége: ), akkor az s-ből az y-ba történő szállítás költségére nyilvánvalóan fenn kell állnia, hogy

ez pedig átrendezéssel a duál feltétel. A fenti feltételeket kielégítő árajánlatok közül választhat a vállalkozó, hogy a s-ből t-be történő szállítási megbízást megkapja. A vállalkozó célja természetesen az, hogy olyan árajánlatot adjon, amelynél a legnagyobb bevételre tesz szert, azaz a t-be történő szállítás költsége a lehető legnagyobb legyen.