Ugrás a tartalomhoz

Operációkutatás alapjai

Dr. Bánkuti Göngyi, Dr. Kövér György (2014)

Kaposvári Egyetem

A szállítási feladat megoldása disztribúciós módszerrel

A szállítási feladat megoldása disztribúciós módszerrel

A korábbiakban kiderült, hogy a szállítási feladat nem más, mint egy lineáris programozási feladat, a korábbi fogalmaink szerint módosított normálfeladat. A megoldása a szimplex módszerrel lehetséges. Jegyezzük meg, hogy a szállítási feladat reprezentálására alkalmas lineáris programozási feladat mérete a kisebb gyakorlati esetekben is óriási. Ugyanakkor a feladat specialitásából származóan egyéb megoldási módszerek is kidolgozásra kerültek, melyek olcsóbban és gyorsabban vezetnek optimális vagy szuboptimális megoldásra.

A szállítási feladat esetében is a szimplex módszerhez hasonlóan járunk el. Előállítunk egy lehetséges bázismegoldást, majd lépésről lépésre javítjuk a megoldást újabb változóknak a bázisba vonásával, amíg az optimumot, vagyis a minimális szállítási költséget el nem érjük. Mivel lineáris programozási feladatróól van szó, vegyük figyelembe az alternatív megoldások lehetőségét. A szállítási feladatnak is lehetséges több, egymástól eltérő, de azonos kiszállítási költségű megoldása.

A szállítási feladat egy lehetséges bázismegoldása

A megoldás megadja, hogy mely viszonylatokban mennyi terméket kell kiszállítani, mely telephelyről mely fogyasztónak. A fogyasztók igényeit igyekszünk kielégíteni.

További bizonyítás nélkül fogadjuk el, hogy akkor találtuk meg egy szállítási feladat lehetséges bázismegoldását, ha n+m-1 számú viszonylatot választottunk ki úgy, hogy a fogyasztói igényeket kielégítettük, a kapacitásokat kihasználtuk. Amennyiben fiktív fogyasztót, telephelyet vezettünk be, akkor n+m viszonylatot kell megfelelően kiválasztanunk.

A többi viszonylaton szállítás nem történik, vagyis nulla mennyiséget szállítunk.

Jegyezzük meg, hogy amint a lineáris programozási feladatok megoldása során találkoztunk degenerációval, úgy ez itt is jelentkezhet. A pontosan n+m-1 (esetleg n+m) szállítási viszonylatot akkor is meg kell választanunk, ha nulla mennyiséget kell továbbítanunk. A szállítási viszonylatokat kötött helyeknek is nevezzük.

A szállítási feladat egy lehetséges bázismegoldásának előállítása

Három, a gyakorlatban is elterjedt módszert ismertetünk. Ismertetésük sorrendjében bonyolultságuk egyre fokozódik, egyre gyakrabban egyre inkább megközelítik az optimális megoldást. De a minimális költségnél jelentősen kedvezőtlenebb megoldást is szolgáltathatnak, hiszen csak azt garantálják, hogy lehetséges bázismegoldást állítanak elő, azt nem, hogy az optimálisat.

A szállítási feladat egy lehetséges bázismegoldásának előállítása: "Északnyugati sarok" másképp "Bástya"-módszer

Válasszuk a bevezető feladatunkat a módszer bemutatására. Állítsunk elő egy lehetséges bázismegoldást. A megoldás során NEM törekszünk arra, hogy a megoldás a szállítási összköltséget valamely mértékben is minimalizálja. Célunk csupán egy lehetséges megoldás meghatározása, amely esetleg a legköltségesebb az összes közül.

Az eljárás során az első telephely kapacitását felhasználva megpróbáljuk az első fogyasztónak kiszállítani az igényelt mennyiséget. Ha marad felesleg, akkor azt a következő fogyasztónak szállítjuk. Ha a második fogyasztó igényét nem elégítettük ki, akkor a második telephelyről azt pótoljuk, és így tovább.

A megoldás előállítását lépésről-lépésre szemléltetjük a következőkben.

A költségmátrix elemeit a megoldás előállítása során nem vesszük figyelembe. A telephelyek kapacitásait sorban felhasználjuk a fogyasztók igényeinek kielégítésére. A telephelyek fennmaradó kapacitását, a fogyasztók maradék igényeit és az összes szállítási költséget lépésről-lépésre kiszámítjuk.

Az induló disztribúciós táblázatunk a következő:

Az első telephely (T1) kapacitásából teljes egészében kielégítjük az első fogyasztó (F1) igényét 40 egységnyi termékkel. T1-ben marad 5 egységnyi termék.

A szállítási összköltség: z = 7*40 = 280.

Az első telephely (T1) maradék kapacitásából 5 egységnyi terméket szállítunk a második fogyasztónak (F2). Az első telephely kapacitását kimerítettük. A második fogyasztó további 35 egységnyi terméket igényel.

A szállítási összköltség: z = 7*40+8*5 = 320.

A második fogyasztónak (F2) a második telephelyről (T2) szállítjuk ki a 35 egységnyi terméket, 15 egységnyi maradék keletkezik.

A szállítási összköltség: z = 7*40+8*5+2*35 = 390.

Az eddigiekhez hasonlóan hajtjuk végre a szállítási feladat lehetséges bázismegoldását előállító lépéseket.

Az "Északnyugati sarok" módszer által előállított lehetséges bázismegoldást láthatjuk a következő táblázatban. A bázismegoldáshoz tartozó szállítási összköltség:

z = 7*40+8*5+2*35+15+4*25+3*40 = 625.

A degenerált eset

A lineáris programozási feladatnál korábban tapasztaltakhoz hasonlóan a degeneráció esete a szállítási feladat megoldása során is jelentkezhet. A gyakorlatban ez azt jelenti, hogy a telephely kapacitása épp fedezi a fogyasztó igényét, nincs maradék kapacitás. A lehetséges bázismegoldást úgy állítjuk elő ebben az esetben, hogy a telephely és a következő fogyasztó viszonylatában nulla mennyiség kiszállítását programozzuk. Ezt a nullát, mint a kötött helyek egyikét, jelölnünk kell. A nulla mennyiség szállítását jelentő kötött helyeket a 0 határozott kiírásával meg tudjuk különböztetni a nem kötött helyektől.

Lássunk példát a degenerációra, az előzőleg megoldott feladat egy változatával. Az eltérés annyi, hogy a második telephely (T2) kapacitása 35 egység, épp fedezi a második fogyasztó igényét.

lehetséges bázismegoldás előállítása során ügyelnünk kell arra, hogy a kötött helyek száma mindig m+n-1 legyen. Ezt biztosítjuk degenerált esetben a 0 mennyiség programozásával.

A szállítási feladat egy lehetséges bázismegoldásának előállítása: soronként, oszloponként a legkisebb költségű helyek kiválasztása

A módszer bemutatására szintén a bevezető feladatunkat választjuk. A különböző módszerekkel meghatározott megoldások így összevethetővé válnak.

Az "Északnyugati sarok"-módszer nem igyekezett minimalizálni a szállítási összköltséget. Úgy tűnik, hogy a legkézenfekvőbb módja az összes szállítási költség csökkentésének az, ha figyelembe vesszük a viszonylatonkénti költségeket, és a kisebb költségű viszonylatokon igyekszünk szállítani, természetesen az igényeknek és a kapacitásoknak megfelelően a lehető legtöbbet.

Állítsunk elő egy lehetséges bázismegoldást a legkisebb költségű helyek figyelembevételével. A megoldás során arra törekszünk arra, hogy a szállítási összköltséget, vagyis a célfüggvényt minimalizáljuk.

Az eljárás során azon a viszonylaton kezdjük a szállítás programozását, ahol az egységenkénti költség a legkisebb. Ha a telephely kapacitása nem elég a fogyasztónak, akkor a következő alacsony költségű telephelyről szállítjuk a maradékot. Ha a telephely kapacitása több, akkor a telephely sorában keressük a következő alacsony költségű viszonylatot. Ezt az eljárást követve határozunk meg egy lehetséges bázismegoldást.

A bevezető feladatunk:

Az induló disztribúciós táblázatunk:

A legkisebb költségű viszonylat a T2->F3, egységenkénti költsége 1. A harmadik fogyasztó (F3) ignyét teljes egészében ki tudjuk elégíteni 40 egységnyi termékkel. T1-ben marad 10 egységnyi termék.

A szállítási összköltség: z = 40.

A második telephely (T2) maradék kapacitásából 10 egységnyi terméket szállítunk a második fogyasztónak (F2). A második telephely kapacitását kimerítettük. A második fogyasztó további 30 egységnyi terméket igényel.

A szállítási összköltség: z = 40+2*10= 60.

A második fogyasztónak (F2) az első telephelyről (T1) (8<9) szállítjuk ki a 30 egységnyi terméket, 15 egységnyi maradék keletkezik.

A szállítási összköltség: z = 40+2*10+8*30 = 390.

Az eddigiekhez hasonlóan hajtjuk végre a szállítási feladat lehetséges bázismegoldását előállító lépéseket.

A soronként, oszloponként legkisebb költségű helyek kiválasztásával előállított lehetséges bázismegoldást láthatjuk a következő táblázatban. A bázismegoldáshoz tartozó szállítási összköltség:

z = 40+2*10+8*30+6*15+3*25+5*40 = 665.

Ez jóval magasabb, mint az "Északnyugati sarok"-módszer által szolgáltatott 625. A romló érték magyarázatát abban a szemellenzős, "mohó" törekvésben találjuk meg, hogy minden esetben az adódó legkisebb költégű viszonylatot választjuk a szállítás programozására. Ez teljesen félrevezető lehet, mint ez a példa is szemlélteti.

A szállítási feladat egy lehetséges bázismegoldásának előállítása: A "Vogel-Korda"-féle módszer

A "Vogel-Korda" eljárás alapgondolata megpróbálja a soronként, oszloponként legkisebb költségű helyek kiválasztására épülő megoldás kedvezőtlen tulajdonságait kiküszöbölni. Soronként és oszloponként képezzük a két legkisebb költségadat különbségét. Annál a fogyasztónál vagy telephelynél kezdjük a készletek kiszállítását, amely esetében a legolcsóbb és a második legolcsóbb viszonylat közötti árdifferencia a legmagasabb.

A módszer bemutatására szintén a bevezető feladatunkat választjuk. A különböző módszerekkel meghatározott megoldások így összevethetővé válnak.

Állítsunk elő egy lehetséges bázismegoldást a Vogel-Korda-módszerrel. A megoldás előállítását lépésről lépésre szemléltetjük a következőkben.

A költségmátrix elemeit a megoldás előállítása során természetesen figyelembe kell venni. Fogyasztónként és telephelyenként kiszámítjuk a legolcsóbb és a második legolcsóbb helyek közötti különbséget, ezt fel is tüntetjük a táblázatunkban a "Diff." felirat sorban/oszlopban.

Az induló disztribúciós táblázatunk:

Láthatjuk, hogy preferálnunk kell a szállítási program készítése során a második fogyasztót. Az első lépésben az ő igényeit kell kielégíteni a második telephelyről. Ha ezt csak egy későbbi fázisban tennénk, akkor a második telephely kapacitása már kötött lehetne.

A szállítási összköltség: z = 2*40 = 80.

A második fogyasztóhoz a szükséges mennyiséget kiszállítva a költségek közötti differenciát ismételten meg kell határozni, mielőtt a szállítási terv második kötött helyét megválasztanánk. A második fogyasztó már nem vesz részt a számításban.

A harmadik és a negyedik fogyasztó esetében a költségdifferencia egyaránt három. Válasszuk a negyediket a kötött hely meghatározásához, ott kisebb a költség (3).

A szállítási összköltség: z = 2*40+3*40= 200.

A differenciák ismételt meghatározása után döntünk a harmadik kötött helyről.

A harmadik fogyasztó bevonása következik, az igényét a második telephelyről részben kielégítjük, majd ismételten meghatározzuk a differenciákat.

A szállítási összköltség: z = 2*40+3*40+10= 210.

Az első fogyasztóhoz szállítjuk a harmadik telephely megmaradó készletét (25).

Befejezésként az első telephely készletét az első és harmadik fogyasztó között felosztjuk.

A "Vogel-Korda"-módszer által előállított lehetséges bázismegoldást láthatjuk a következő táblázatban.

A bázismegoldáshoz tartozó szállítási összköltség:

z = 2*40+3*40+10+5*25+7*25+5*30 = 590.

Annak ellenére, hogy a "Vogel-Korda"-módszerrel látványos költségcsökkentést értünk el, ez nem jelenti azt, hogy minden feladat esetében ilyen sikeresen járunk el. Abban sem lehetünk biztosak, hogy ez az optimális megoldás, vagyis nincs alacsonyabb költségű szállítási terv.