10.2. 10.2. Algoritmus a szűk-keresztmetszetű szállítási feladat megoldására

Kézenfekvő az alábbi egyszerű algoritmus, amelynek lényege, hogy a szűk-keresztmetszetű szállítási feladatot általános Kőnig feladatok sorozatával oldjuk meg.

1. lépés: Kezdeti szállítás készítése.

Ezt végezhetjük például a legkisebb időértékeken keresztül.

2. lépés: A szállítás lebonyolítási idejének meghatározása.

Jelöljük -nal a szállítás lebonyolításának idejét, amely

tehát a tényleges szállításhoz tartozó időértékek maximuma.

3. lépés: Új szállítás készítése

Próbáljunk meg olyan új szállítást meghatározni, amelynek lebonyolítási ideje az előzőnél kisebb. Ez tulajdonképpen egy olyan általános Kőnig feladat, amelyben ott engedjük meg a szállítást, ahol . Az általános Kőnig feladat megoldhatósága szerint két esetet vizsgálunk:

  1. Ha nem tudtuk az összes árut elszállítani, akkor az előző szállítás a legjobb. Vége az algoritmusnak.

  2. Ha az összes árut elszállítottuk, akkor egy olyan új szállítást kaptunk, amelynek lebonyolítási ideje biztosan jobb (kisebb), mint az előző. A 2. és a 3. lépéseket addig ismételjük, amíg az (1) esetet nem kapjuk.

Nyilvánvaló, hogy az eljárás véges lépésben végetér.