15.2. 15.2. A feladat matematikai vizsgálata és megoldási algoritmusa

A trans-shipment feladatot egy standard szállítási feladatra lehet transzformálni az alábbiak szerint. A szállítási feladat termelői legyenek a trans-shipment feladat élei, a kínálati mennyiségek pedig legyenek az élek kapacitásai. A szállítási feladat fogyasztói legyenek a trans-shipment feladat pontjai, a keresleti mennyiségeket pedig az alábbi módon határozzuk meg. Jelölje az i pontból kiinduló élek kapacitásainak összegét, azaz

Ennek segítségével az alábbi módon határozzuk meg a keresleti mennyiségeket:

A szállítási feladat termelői és fogyasztói közötti szállítási egységköltségek pedig a következők: az „termelő” sorában az i oszlopban , a oszlopban a többi helyen pedig . Tehát soronként csak két helyen engedünk meg szállítást. Az alábbi táblázat a megkonstruált szállítási feladat sémáját mutatja, a könnyebb áttekinthetőség kedvéért a költség helyett a (-) letiltást alkalmaztuk:

A megkontruált szállítási feladat standard feladat, tehát az összkínálat megegyezik az összkereslettel. Ennek igazolását az olvasóra bízzuk.

Ezután megoldjuk a szállítási feladatot, pl. „magyar módszerrel”. Jelölje a megoldást abban a cellában, ahol a költség , a zérus költségű cellában pedig , a kínálati egyensúly miatt. Ezt mutatja az alábbi séma:

Most megvizsgáljuk, hogy a szállítási feladat feltételei hogyan teljesítik a trans-shipment feladat feltételeit.

A szállítási feladatban is előírás a nemnegativitás.

A szállítási feladat kínálati feltételei biztosítják az korlátozottsági feltételt.

A szállítási feladat keresleti feltételei pedig az alábbiak miatt biztosítják a forráspontokra, közbülső pontokra és a nyelőpontokra vonatkozó előírásokat. Az i-edik oszlopra az alábbi keresleti egyenlőség áll fenn:

ezt részletezve:

a definíciójából pedig következik a két oldal egyenlősége.

Végül a célfüggvények ekvivalenciáját az alábbiak szerint ellenőrizhetjük:

A fentiekből kiolvasható, hogy a trans-shipment feladat megoldó algoritmusa minden olyan algoritmus, amellyel szállítási feladat oldható meg. Mi a „magyar módszert” ismertettük a szállítási feladat megoldására, így a megoldó algoritmusunk a „magyar módszer”.

Megjegyzés:

A transzformálás akkor is alkalmazható, ha egy forrással és egy nyelővel rendelkező minimális költségű folyamfeladatunk van. A minimális költségű folyamfeladat ismertetésénél olyan algoritmust mutattunk be, amely sorozatos minimális útkeresésekből állt. Ezzel a transzformációval egy új megoldó algoritmust kaptunk a minimális költségű folyamfeladatra.