15.3. 15.3. Példamegoldás

Oldjuk meg az alábbi ábrán látható trans-shipment feladatot! Az élekre írt adatok közül az első az él kapacitását, a második (zárójelben lévő) az élen az egységköltséget jelenti. A pontok melletti adatoknál az betű a forrást, az betű a nyelőt jelöli, a számadatok pedig a forrásokból kifolyó folyamok ill. a nyelőkbe befolyó folyamok mennyiségét jelenti.

Megoldás:

Legelőször készítsük el a szállítási feladat sémáját. A szállítási feladat termelői az élek, fogyasztói pedig a pontok. A kínálati mennyiségek az élek kapacitásai. A keresleti mennyiségek számítása pedig az alábbi egyszerű módon történik. Az i pont kereslete: össze kell adni a bal szegélyen lévő azon élek kapacitását, amely él kezdőpontja i, majd nyelőpont esetén ehhez hozzá kell adni a nyelőpontra előírt mennyiséget ill. forráspont esetén ebből ki kell vonni a forráspontra előírt mennyiséget. A szállítási egységköltségek beírása is egyszerű: az él i kezdőpontjának cellájába zérust, a j végpontjának cellájába értéket írunk, a többi cellát letiltjuk. A pontokat a következőkben -vel jelöljük. A szállítási feladat sémája tehát a következő:

Az éleket betüvel jelöljük a szállítási feladat megoldása során.

A szállítási feladatot „magyar módszerrel” oldjuk meg. Könnyen látható, hogy sorredukcióra és oszlopredukcióra nincs szükség, így a redukált költségtáblázat az eredeti költségtáblázat, amely az alábbi:

Elkezdjük az általános Kőnig feladat megoldását, az induló megoldást É-Ny-i sarok módszerrel végezzük és címkézéssel próbálunk javítani a szállításon.

Nem sikerült a javítás, következik a redukált költségtáblázat lefedése (), majd az új redukált költségtáblázat meghatározása, amelyet az alábbi táblázat mutat:

A szabaddá vált cellán 1 egységgel, a szintén szabaddá vált cellán pedig 4 egységgel javíthatunk a szállításon, majd címkézéssel próbálunk javítani a szállításon.

Sikerült utat találnunk a címkézéssel, így javítható a szállítás, ezt mutatja a következő táblázat. Újra címkézéssel próbálunk javítani a szállításon:

Nem sikerült a javítás, következik a redukált költségtáblázat lefedése (), majd az új redukált költségtáblázat meghatározása, amelyet az alábbi táblázat mutat:

A szabaddá vált cellán 1 egységgel javíthatunk a szállításon, majd címkézéssel próbálunk javítani a szállításon.

Nem sikerült a javítás, következik a redukált költségtáblázat lefedése (), majd az új redukált költségtáblázat meghatározása, amelyet az alábbi táblázat mutat:

Most nincs triviális javítási lehetőség, címkézéssel próbálunk javítani a szállításon.

Sikerült utat találnunk a címkézéssel, így javítható a szállítás, ezt mutatja a következő táblázat.

Mivel az összes áru el lett szállítva, így az algoritmust befejezzük. A szállítási feladat megoldását a fenti táblázat, a trans-shipment feladat megoldását pedig az alábbi táblázat mutatja. A szürkén jelzett cellákon olvasható le a trans-shipment feladat optimális folyama.

A megoldást hálózaton az alábbi ábra mutatja:

A minimális költség : 26.