A szállítási feladat klasszikus megfogalmazása a következő. Adott n számú F 1. mennyiségűhomogén termékkel rendelkeznek, valamint m számú R 1

Dr. BenkőJános

A szállítási feladat

4. A SZÁLLÍTÁSI FELADAT A szállítási feladat klasszikus megfogalmazása a következő. Adott n számú F1 , F2 ,..., Fn feladó, akik f1 , f 2 ,..., f n mennyiségűhomogén termékkel rendelkeznek, valamint m számú R1 , R2 ,..., Rm megrendelő, akik r1 ,r2 ,..., rm mennyiséget igényelnek a szóban forgó termékből. Jelentse cij azt a fajlagos szállítási költséget, amelybe az egységnyi termék szállítása kerül, ha azt az i-edik feladótól a j-edik megrendelőhöz szállítjuk. A cél a megrendelők igényét úgy kielégíteni, hogy a szállítás összes költsége minimális legyen. Ha xij az i-edik feladótól a j-edik megrendelőhöz szállítandó mennyiséget jelenti, akkor a feladatot a következőformában írhatjuk fel: (4.1)

xij 0 (i = 1,...,n) (j = 1,...,m),

(4.2)

j xij f i ,

(4.3)

i xij rj ,

(4.4)

i f i j rj ,

(4.5)

 z  min . i j cij x ij 

A modell felírása után tekintsük a feltételek jelentését: Az (4.1) feltétel azt jelenti, hogy a szállítás egyirányú a feladóktól a megrendelők felé. A (4.2) feltétel szerint a feladók készletét el kell szállítani. A (4.3) feltételben kikötjük, hogy a megrendelők igényét ki kell elégíteni. A (4.4) feltétel értelmében a feladók készlete egyenlőa megrendelők igényével. Az (4.5) lineáris függvényben fogalmazzuk meg a célt. (Az összes szállítási költség akkor minimális, ha a fajlagos költségek és a szállított mennyiségek szorzatainak összege minimális.) A gyakorlatban az alapmodell (4.4) feltétele ritkán teljesül, azaz a i f i j rj . Ilyenkor a (4.2) és (4.3) feltételekben az egyenletek helyett csak egyenlőtlenségek követelhetők meg: ha a i f i j rj , akkor j xij  f i , ha a i f i j rj , akkor i xij rj .


Ezek a formák fiktív feladó vagy megrendelőbeiktatásával könnyen visszavezethetők az alapmodellre. A létezőés a fiktív feladók, illetve megrendelők viszonylatához cij 0 értékűfajlagos költséget rendelünk, a (4.4) feltételt pedig a úgy biztosítjuk, hogy a fiktív feladót j rj i f i készlettel, a fiktív megrendelő t i f i j rj igénnyel szerepeltetjük. A gyakorlati problémák megoldása során előfordulhat olyan kikötés is, hogy bizonyos feladók nem szállíthatnak bizonyos megrendelőknek. Ezeket a korlátozásokat az alapmodell változtatása nélkül úgy vehetjük figyelembe, hogy a tiltott relációkhoz cij  fajlagos költséget rendelünk. A gyakorlatban a tiltott relációk költsége: cij M , ahol M sokkal nagyobb, mint a többi cij elem. Az M-mel jelölt mennyiséget szokás tiltótarifának nevezni. A tiltótarifát alkalmazzuk akkor is, amikor a feladók készlete nagyobb, mint a megrendelők igénye, és valamely feladónál nem maradhat készlet. Ezt biztosan úgy érhetjük el, hogy a kitüntetett feladó nem szállíthat a fiktív megrendelőnek. Fordított esetben, amikor a megrendelők igénye a nagyobb, és valamely megrendelőigénye elsőbbséget élvez, akkor a fiktív feladó nem szállíthat az elsőbbséget élvezőmegrendelőnek. A tiltótarifa alkalmazásának lehetőségeit a gyakorlati problémák megfogalmazásakor részletesen bemutatjuk. Feltétlen említést érdemel, hogy a klasszikus formában, az anyagmozgatásban használatos kifejezésekkel megfogalmazott modell nagyon sokoldalúan alkalmazható más problémák megoldására is. Ezért talán helyesebb az irodalomban kevésbé elterjedt elosztási feladat elnevezés, a megtévesztőszállítási feladat helyett. Említést érdemel az elosztási feladatoknak a hozzárendelési feladat néven ismert csoportja, amikor is ti=rj=1 minden i,j-re és n=m. Ilyen feladat megoldása merül fel akkor, amikor n számú különbözőanyagmozgatási műveletet kell hozzárendelni n számú, különbözőműszaki paraméterrel jellemezhető géphez, és a munka elvégzésére fordított a költség minimalizálása a cél. A c ij fajlagos szállítási költséget eddig hallgatólagosan állandónak tekintettük. A gyakorlatban azonban előfordulhat, hogy cij az xij lineáris vagy kvadratikus függvénye. Ilyen jellegűfeladatokkal nem foglalkozunk, de megemlítjük, hogy ezek megoldására is hatékony algoritmusok állnak rendelkezésre [41]. Végül megjegyezzük, a modell maximumfeladatok megoldására is alkalmas. A cél megfordítását úgy érhetjük el, hogy a cij fajlagos költségelemeket –1-gyel szorozzuk. A szállítási feladat megoldására több heurisztikus és egzakt eredményt szolgáltató módszert ismerünk. A közelítőmódszerek egyrészt az optimumhoz közeli bázismegoldást adnak az egzakt eljárásokhoz, másrészt kézi számolás esetén kevesebb munkával szolgáltatnak a gyakorlat számára elfogadható eredményt. Ezért mindkét területről bemutatunk algoritmusokat. Ezeket a közérthetőség kedvéért egy példa megoldásával párhuzamosan ismertetjük.

2


4.1. A Vogel-Korda-féle eljárás A heurisztikus eljárások közül az egyik leghatékonyabb és az egyik legismertebb a Vogel-Korda-féle módszer. A módszer bemutatásához tekintsük a következőpéldát. Legyen a feladók száma n=3, a készletük f i =[50,40,30]. A megrendelők száma m=4, igényük rj =[40,10, 60,10]. A fajlagos szállítási költségek mátrixa: 6 4 1 5 2 1 3 8 C= 1 2 1 1 Az elsőlépés a költségmátrix redukálása. Ha a mátrix mindegyik sorának elemeiből levonjuk a sorban található legkisebb elemet, majd az így kapott mátrix mindegyik oszlopának elemeiből levonjuk az oszlopban található legkisebb elemet, akkor olyan költségmátrixhoz jutunk, amelyhez ugyanazon optimális megoldás tartozik, mint az eredetihez. Legyen pi az i-edik sor, q j pedig a j-edik oszlop legkisebb eleme, azaz

pi min{ cij j 1, 2,...,m} , q j min { cij pi i 1, 2,..., n}, akkor a redukált mátrix elemei: cijcij pi q j .

Ezt helyettesítsük az (4.5) célfüggvénybe: z i j (cijpi q j ) xij z i j cijxij  i j q j x ij i j pi xij  z i j c i pi ( j xij ) j q j ( i xij ) ij xij 

Felhasználva a (2) és (3) összefüggéseket a (4.6)

z i j c i pi f i j q j rj . ij xij 

Ezzel z célfüggvényt az xij -től függőés attól független részekre bontottuk, és a redukcióra vonatkozó állításunkat bizonyítottuk. Írjuk fel ezek után a példánkat táblázatos formában, majd hajtsuk végre a redukciót.

F1 F2 F3 rj

R1 6 2 1 40

R2 4 1 2 10

R3 1 3 1 60

R4 5 8 1 10

fi 50 40 30

3


R1 5 1 0 40

F1 F2 F3 rj

R2 3 0 1 10

R3 0 2 0 60

R4 4 7 0 10

fi 50 40 30

A következőlépés a költségelemek rangsorolása az ún. differenciák alapján. A differenciákat úgy számíthatjuk ki, hogy minden oszlopban és sorban vesszük a minimális elemek különbségét. A sorokban: 30=3, 10=1, 00=0. Az oszlopokban: 10=1, 10=1, 00=0, 40=4. Ha az előzőtáblázatunkat kiegészítjük a differenciákkal, akkor a következőtáblázatot nyerjük:

F1 F2 F3 rj

R1 5 1 0 40 1

R2 3 0 1 10 1

R3 0 2 0 60 0

R4 4 7 0 10 4

fi 50 40 30

3 1 0

A differenciák alapján dönthetünk arról, hogy melyik sorban illetve oszlopban kezdjük a programozást. Azt a sort, illetve oszlopot részesítjük előnyben, amelyikhez a legnagyobb differencia tartozik. Esetünkben ez egyértelműen a 4. oszlop. Ha a differenciák halmazában nincs egyértelműen maximális elem, akkor a legnagyobb differenciákhoz tartozó sorok illetve oszlopok közül szabadon választhatunk. A kiválasztott sor vagy oszlop minimális elemére a lehetőlegnagyobb mennyiséget programozzuk. Azt a sort, illetve oszlopot elhagyjuk, ahol a készlet 0-ra csökken, és újra kiszámítjuk a differenciákat. A leírt eljárást ezt követően addig folytatjuk, amíg az összes feladó készletét, illetve megrendelőigényét szét nem osztottuk. Az eljárás lépéseit a következőtáblázatokban nyomon követhetjük.

F1 F2 F3 rj

R1 5 1 0 40 1

R2 3 0 1 10 1

R3 0 2 0 60 0

R4 4 7 010 0 4

fi 50 40 20

3 1 0

4


F1 F2 F3 rj

F1 F2 F3 rj

F1 F2 F3 rj

F1 F2 F3 rj

R1 5 1 0 40 1

R2 3 0 1 10 1

R3 050 2 0 10 0

R4

R1

R2

R3

R4

1 0 40 1

0 1 10 1

2 010 0 2

R1

R2

R3

1 0 40 1

010 1 0 1

R1

R2

fi 0 40 20

fi 40 10

R4

1 0

fi 30 10

R3

3 1 0

R4

1 1

fi

130 010 0 1

0 0

0 0

A megoldás:

x13 =50, x21 =30, x 22 =10, x 31=10, x 33 =10, x 34 =10. A célfüggvény értéke: z =1*50+2*30+1*10+1*10+1*10+1*10=150, ami, mint később látni fogjuk, az optimális megoldás is. Természetesen nagyobb volumenűfeladatoknál ez nem mindig következik be, csupán abban lehetünk biztosak, hogy az optimumhoz közeli megoldást kapunk. 4.1. példa: Oldjuk meg a következőszállítási feladatokat a VogelKorda módszerrel:

1 3 2 50

0 5 7 40

2 1 6 50

6 9 0 40

60 30 90

5


–2 –3 –10 110

–4 –5 –6 100

0 0 M 60

10 60 200

4.2. A korlátozás és szétválasztás módszerének alkalmazása Az optimumszámítás területén az elmúlt évtizedekben előtérbe kerültek az ún. kombinatorikus módszerek. Ezek közé sorolható a korlátozás és szétválasztás. A továbbiakban ennek gyakorlati alkalmazását mutatjuk be a szállítási feladaton. Mivel a szállítási probléma minimumfeladat, a korlátozási tevékenységnél alsó korlátot állapítunk meg, a szétválasztásnál pedig a legkisebb alsó korlátot vesszük figyelembe [11]. Az összes megoldások halmazára alsó becslést úgy nyerünk, hogy az előzőpontban bemutatott módon redukáljuk a C költségmátrixot. A (4.6) alapján könnyű belátni, hogy a redukció nagysága: i pi f i j q j rj ,

a célfüggvényben: z i j cijxij i pi f i j q j rj

bekövetkezett változásokat mutatja. Az is belátható, hogy a cij0 miatt a redukció mértékénél kisebb értékűmegoldás nem található, ezért az összes megoldások halmazához alsó korlátként a z0 i pi f i j q j rj

összeget rendeljük. Szétválasztási kritériumnak tekintsük az összes cij0 elemre kiszámított



rij min ( cikk 1,2,..., j 1, j 1,..., m) f i (c  1, i 1,..., n) rj kj k 1,2,..., i  összegek halmazából a maximálisat, azaz a szétválasztási kritérium



Rij max rij .

Ez gyakorlatilag azt jelenti, valamennyi cij0 elemre megvizsgáljuk, hogy milyen mértékben növekedne a z célfüggvény, ha a vizsgált helyet tartalmazó megoldásokat kizárnánk a megoldások halmazából, majd ezek közül azt választjuk, amelynek a kizárása a legnagyobb célfüggvény növekedést eredményezi. Maga az eljárás nagyon egyszerű, az Rij -nek megfelelőcij =0 helyére c ij=M-t írunk, ami R ij redukciót tesz lehetővé. Mielőtt azonban ezt megtennénk, megvizsgáljuk, hogy milyen mértékben növekedne a célfüggvény akkor, ha a kiválasztott ij-viszonylatra a lehetőlegnagyobb mennyiséget programoznánk. Ezt úgy hajtjuk végre, hogy a kiválasztott helyre a lehetőlegnagyobb mennyiséget programozzuk, majd azt a sort vagy oszlopot, ahol 0-ra csökkent a készlet, elhagyjuk. Ezt követően redukáljuk a maradék költségmátrixot. Az így elérhetőredukció: Riji pi f i j q j rj ,

6




Most már eldönthetjük, hogy a szétválasztási kritérium alapján kiválasztott viszonylat kizárása (x ij=0), vagy bevonása (xij>0) kedvezőbb-e számunkra. Így gyakorlatilag az összes megoldások halmazát kettéválasztjuk. Az elsőbe tartoznak azok, amelyek nem tartalmazzák, a másodikba pedig azok, amelyek tartalmazzák az ij-viszonylatot. Ha az RijRij , akkor az ij helyet tartalmazó megoldásokat kizárjuk. A cij=M lesz, redukáljuk a költségmátrixot, és kiszámítjuk az új mátrixhoz tartozó alsó korlátot: z1 z0 Rij .

Ha az RijRij, akkor az ij viszonylatra programozunk. Elhagyjuk azt a sort vagy oszlopot, ahol 0-ra csökkent a készlet, redukáljuk a költségmátrixot, és kiszámítjuk az új mátrixhoz tartozó alsó korlátot: z1 z0 Rij .

Ezt követően a leírtakat addig ismételjük, amíg az összes készletet el nem osztjuk. A továbbiakban alkalmazzuk az eljárást az előzőpontban megismert példa megoldására.

F1 F2 F3 rj

R1 6 2 1 40

R2 4 1 2 10

R3 1 3 1 60

R4 5 8 1 10

fi 50 40 30

R2 3 0 1 10

R3 0 2 0 60

R4 4 7 0 10

fi 50 40 30

Redukáljuk a költségmátrixot:

F1 F2 F3 rj

R1 5 1 0 40

A redukció mértéke, amely egyben az alsó korlát is: z0=1*50+1*40+1*30=120. Határozzuk meg a szétválasztási kritériumot! r13 =3*50+0=150

r22 =1*40+1*10=50

r31 =0+1*40=40

r33 =0+0=0

r34 =0+4*10=40 Rij =max{rij}=R13=150 Az 1-3 viszonylat kizárása tehát 150-nel növeli a célfüggvény értékét. Most nézzük meg, hogy az 1-3-viszonylat bevonása milyen növekedést eredményez. Az 1-3 helyre programozható maximális mennyiség 50 egység, így az elsősor készlete 0-ra csökken, ezért az elsősort elhagyjuk, és redukáljuk a megmaradó C1költségmátrixot. A lépések a táblázatokban követhetők. 7


R1

R2

R3

R4

fi

F1

5

3

050

4

0

F2

1

0

2

7

40

F3

0

1

0

0

30

rj

40

10

10

10

R1

R2

R3

R4

fi

1 0 40

0 1 10

2 0 10

7 0 10

40 30

F1 F2 F3 rj Az elérhetőredukció:

R130. Mivel az R13 R13 , az x13=50, a C 1 mátrixot bontjuk tovább, a hozzá tartozó alsó korlát

z1 z0 R13120 . Ezután a C1költségmátrixhoz tartozó szétválasztási kritériumot határozzuk meg: r22=1*40+1*10=50

r31=0+1*40=40

r33=0+2*10=20

r34=0+7*10=70 R ij=max{rij }=R34 =70

A további lépéseket kommentár nélkül közöljük.

F1 F2 F3 rj

F1 F2 F3 rj

R1

R2

R3

R4

fi

1 0 40

0 1 10

2 0 10

7 010 0

40 20

R1

R2

R3

R4

fi

1 0 40

0 1 10

2 0 10

40 20

R340 , R34R34 , x 34 10 z2 z1 R34120 . A C 2 mátrixhoz tartozó szétválasztási kritérium:

8


r22 =1*40+1*10=50

r31 =0+1*40=40

r33 =0+2*10=20 Rij =max{rij}=R22=50

F1 F2 F3 rj

F1 F2 F3 rj

R1

R2

R3

1 0 40

010 1 0

2 0 10

R1

R2

R3

0 0 40

R4

fi 30 20

R4

1 0 10

fi 30 20

R 22 30, R 22 R22 , x22 10, z3 z2 R22150 A C 3 mátrixhoz tartozó szétválasztási kritérium: r21 =1*30+0=30

r31 =0+0=0

r33 =0+1*10=10 Rij = max{rij }=R21=30

R1 F1 F2 F3 rj

030 0 10

R1 F1 F2 F3 rj

R2

0 10

R3

R4

1 0 10

R2

R3

fi 0 20

R4

0 10

fi

20

R210, R  21 R21 , x 21 30, z4 z3 R21150 . Az utolsó sorban a szétosztás már egyértelmű, és a 0 elemek miatt a célfüggvény értéke sem változik. R1 R2 R3 R4 fi F1

F2 F3 rj

010 0

010 0

0

9


x31 10, x33 10, z z4 150 . A megoldás:

x13 50, x21 30, x22 10, x31 10, x33 10, x 34 10. A célfüggvény értéke: z=1*50+2*30+1*10+1*10+1*10+1*10=150. Az eredményeket összehasonlítva a Vogel-Korda-féle eljárással kapott eredményekkel megállapíthatjuk, hogy a korlátozás szétválasztás is optimumot adott. Természetesen az optimumban ennél az eljárásnál sem lehetünk biztosak. 4.2. példa: Oldjuk meg a következőszállítási feladatot a korlátozás és szétválasztás módszerével: 2 3 M 50

M 7 0 150

0 15 M 50

5 M 6 150

70 100 200

4.3. A disztribúciós módszer A szállítási feladat egzakt megoldásai között kitüntetett szerepe van a lineáris programozásban általánosan alkalmazható szimplex-módszernek, amely a korábbi tanulmányokból ismeretes. A szimplex-táblába foglalt modellből ugyanis egyértelműen látható a feladat speciális struktúrája. Ez lehetővé teszi a szimplex algoritmusnál kisebb számítás és memóriaigényűeljárások alkalmazását, nevezetesen a magyar és a disztribúciós módszerét. A (4.2), (4.3) feltételek és az (4.5) célfüggvény alapján az előzőpontban megfogalmazott példát szimplex-táblába foglalhatjuk (4.1. táblázat). 4.1. táblázat A mintapélda szimplex-táblája x11

x 12

x 13

x14

x 21

x 22

x23

x24

x 31

x32

x33

x 34

u1

1

1

1

1

0

0

0

0

0

0

0

0

50

u2

0

0

0

0

1

1

1

1

0

0

0

0

40

u3

0

0

0

0

0

0

0

0

1

1

1

1

30

v1

1

0

0

0

1

0

0

0

1

0

0

0

40

v2

0

1

0

0

0

1

0

0

0

1

0

0

10

v3 v4

0

0

1

0

0

0

1

0

0

0

1

0

60

0

0

0

1

0

0

0

1

0

0

0

1

10

6

4

1

5

2

1

3

8

1

2

1

1

0

A (4.2) és (4.3) feltételek egy m+n egyenletből álló egyenletrendszert határoznak meg, ahol az ismeretlenek száma m*n. A táblából látható, hogy egy olyan lineáris programozási feladattal állunk szemben, ahol a feltételi egyenletek csak 0 és 1 együtthatójú xij tagokat tartalmaznak, és 10


az együtthatómátrix oszlopvektorai az ei egy n eleműés ej m elemű egységvektorok. A tábla alapján belátható az is, hogy a feladat duál párja, ha ui-vel és vj-vel jelöljük a duálváltozókat: (4.7)

ui v j cij

(i 1,..., n; j 1,...,m )

(4.8)

i f i ui j rj v j z  max .

A feladat felépítése lehetővé teszi, hogy a szimplex-tábla helyett az ún. disztribúciós táblából induljunk ki, amely csak a szimplex-tábla peremadatait (C, f, r) tartalmazza. Később látni fogjuk, a disztribúciós táblán kijelölhetőa primál feladat egy lehetséges bázismegoldása, és elvégezhetőa bázismegoldás javítása anélkül, hogy a szimplex-táblán belüli változásokat nyilvántartanánk. A disztribúciós módszer alkalmazásának előfeltétele a (4.4) feltétel teljesülése, ami miatt a szimplex-tábla n+m egyenlete közül csak n+m 1 független egymástól. Ebből viszont az következik, hogy a bázismegoldásnak n+m1 eleme van, mivel a kötött ismeretlenek száma megegyezik az együtthatómátrix rangjával. A (4.7) duál feltételek pedig a kötött helyeken egyenlőség formájában teljesülnek. Ezt a megállapításunkat az optimalitás vizsgálat során fel fogjuk használni.

Az indulóprogram elő állítása Az indulóprogram (az elsőbázismegoldás) előállítására az irodalomban több módszer ismeretes. Többek között a Vogel-Korda-féle eljárás is alkalmazható. Itt most a sor és oszlop minimum módszert ismertetjük. A módszer bemutatását összekötjük az alkalmazással, ezért írjuk fel ismét a mintapéldánk induló disztribúciós tábláját, amelyben nyomon követhetjük a megoldás lépéseit.

F1 F2 F3 rj

R1 6 220 120 40

R2 4 110 2 10

R3 150 3 110 60

R4 5 810 1 10

fi 50 40 30

a/ Az fi és rj elemek között megkeressük a legnagyobbat. A példában r3 =60. b/ A kiválasztott feladó sorában, vagy megrendelőoszlopában megkeressük a legkisebb költségűviszonylatot (c13=1), és erre a helyre akkora mennyiséget programozunk, amennyit az f i és rj korlátok megengednek. A példában f1< r3, így x13=50. c/ A programozást a következőlegkisebb költségűhelyen folytatjuk, miközben betartjuk a következőszabályokat: Mindig maradunk egy sorban vagy oszlopban, amíg az illetősort vagy oszlopot teljesen ki nem merítettük. A le nem kötött f i és rj értékek közül mindig a kisebbet programozzuk.

11


Ha egyszerre csökken 0-ra a feladó készlete és a megrendelőigénye, akkor a feladatot degeneráltnak nevezzük. Ilyenkor a következőlegkisebb költségűhelyre xij=0 mennyiséget programozunk. d/ A programozást addig folytatjuk, amíg az összes készletet, illetve igényt szét nem osztottuk. A továbbiakban azokat a helyeket, ahová programoztunk, kötött helynek, a többit szabad helynek fogjuk nevezni. Az indulóprogramot a bázis javítása előtt célszerűellenőrizni. Ha betartottuk a szabályokat, akkor a kötött helyek száma n+m–1, és teljesülnek a (4.2), (4.3) feltételek. A példánk indulóprogramja az elosztás sorrendjében: x13=50, x33=10, x31=20, x21 = 20, x22= 10, x24=10, a célfüggvény pedig z=210.

Az optimalitás vizsgálata Az indulóprogram kielégíti az (4.1)-(4.4) feltételeket. A kérdés ezek után már csak az, miként dönthetjük el, hogy a bázismegoldás optimális-e, vagy pedig javítható. Az optimalitás feltételeit, mint tudjuk a szimplex-módszernél a dualitási tétel határozza meg. Ha a primál megoldás mellett ismernénk a duálváltozók (ui, vj) értékeit, akkor egyszerűen dönthetnénk. A disztribúciós táblából a duálváltozók sajnos nem olvashatók ki, de kiszámíthatók, mivel a primálbázisba vont vektorokhoz tartozó duálfeltételek mindig egyenlőség formájában teljesülnek, azaz ui+v j =cij. A továbbiakban az ui és vj duálváltozókat a disztribúciós módszernél használatos terminológiának megfelelően potenciáloknak nevezzük. Visszatérve az előzőekhez a potenciálok száma n+m, a primálbázisba vont vektorokhoz tartozó duálfeltételek száma n+m–1, így egy potenciál értéke szabadon választható, a többi pedig a c ij(ui+vj)=0

(4.9)

egyenletekből számítható. Az így meghatározott potenciálokat felhasználva megvizsgáljuk, hogy a szabad helyekre teljesül-e a (4.7) feltétel, azaz a dij=cij(ui+vj)0.

(4.10)

Ha található olyan szabad hely, ahol dij<0, akkor a program javítható. A gyakorlatban a potenciálok a következőtábla alapján számíthatók: v1

u1 u2 u3

v2

v3

v4

1 2 1

1

8 1

12


Legyen u1=0, akkor v 3=c13u1=1 u3 =c33v 3=0 v 1=c31u3=1 u2 =c21v 1=1 v 2=c22u2=0 v 4=c24u2=7 A kapott értékeket a (4.10)-be helyettesítve: d11=5, d12=4, d14=2, d23=1, d32=2, d34=6. Az indulóprogram tehát javítható.

A bázismegoldás javítása A bázismegoldást úgy javíthatjuk, hogy azt a helyet, amelyhez a legnagyobb abszolút értékűnegatív dij tartozik, bevonjuk a bázisba. A szállítási feladat speciális felépítése egy viszonylag egyszerű, mechanikusan alkalmazható vektorcserére ad lehetőséget. Ennek tárgyalása előtt bevezetjük a hurok fogalmát. Ha a C költségmátrix bármelyik elemétől kiindulva bástyamozgással haladunk úgy, hogy ugyanazon sorban és oszlopban csak két elemet érintünk, akkor hurkot kapunk. Bizonyítható, ha adott egy bázismegoldás, akkor bármely szabad helyhez egyértelműen hozzárendelhetőegy hurok, amelynek egyik csúcspontja a szóban forgó szabad hely, a többi csúcsa pedig az adott bázismegoldás egy-egy eleme. Az elmondottak egyszerűeljárást adnak a vektorcserére. Megrajzoljuk a bevonandó szabadhelyhez tartozó hurkot. A hurokban a szabad helyhez tartozó elemet, majd ezt követően minden másodikat pozitívnak, a többit negatívnak tekintjük. A negatív csúcsokon lévőxij mennyiségek közül a legkisebbet a negatív csúcsokon álló mennyiségekből levonjuk, a pozitív csúcsokon állókhoz pedig hozzáadjuk. Végül a negatív csúcsok közül azt, amelynél az xij mennyiség 0-ra csökkent, elhagyjuk a hurokból, de mindig csak egy csúcsot. Degeneráció esetén ugyanis több helyen is 0-ra csökkenhet az xij. A megmaradó hurok csúcspontjai, és az előzőbázismegoldás hurkon kívüli elemei alkotják az új bázist. A leírt eljárást alkalmazzuk a példán. A dij értékek alapján a 3-4 szabad helyet kell bevonni a bázisba. A disztribúciós táblán megrajzoljuk a hurkot, amelynek csúcspontjai: 3-4, 3-1, 2-1, 2-4. A negatív csúcsok között x24 a legkisebb, ezt levonjuk a negatív csúcson állókból, és hozzáadjuk a pozitív csúcson állókhoz.

F1 F2 F3 rj

R1 R2 6 4 +20 110 2 1-20 2 40 10

R3 150 3 110 60

R4 5 8-10 1+* 10

fi 50 40 30

13


x34=0+10=10 x31=2010=10 x21=20+10=30 x24=1010=0 Az x24-et elhagyjuk, így az új bázismegoldás: R1 R2 R3 R4 F1 6 4 150 5 F2 230 110 3 8 10 F3 110 2 1 110 rj 40 10 60 10

fi 50 40 30

x13=50, x21=30, x22=10, x31=10, x33=10, x34=10 Az optimalitás vizsgálat elvégzése után már valamennyi szabad helyen a dij értéke pozitív, vagyis a fenti bázismegoldás optimális. A célfüggvény értéke z=150. A megoldás részletes ismertetése után foglaljuk össze a disztribúciós módszer algoritmusát: a/ A feladatot a (4) feltételnek megfelelőalakra hozzuk fiktív megrendelővagy feladó beállításával. b/ Felírjuk a feladat induló tábláját: C

f

r c/ Az előzőekben leírt módon indulóprogramot készítünk, vagyis keresünk egy bázismegoldást. d/ A kötött helyekre felírható ui+v j=c ij egyenletrendszer segítségével kiszámítjuk a potenciálokat. e/ A szabad helyekre írható dij=cij(ui+vj)0 feltételek alapján megvizsgáljuk a bázismegoldás optimalitását. Ha a feltétel valamennyi ij párra teljesül, akkor a megoldás optimális. f/ A szabad helyek közül azt, ahol a dij negatív, és a legnagyobb abszolútértékű, bevonjuk a bázisba. A vektorcserét az ismertetett módon végezzük el. A vektorcsere után visszatérünk a d ponthoz. 4.3 példa: Négy raktár öt fogyasztót lát el. Az egységnyi termék raktározási költsége az egyes raktárakban rendre 30, 40, 30, 50 Ft. A raktárak kapacitása: [3000, 2000, 4000, 3500] egység. A fogyasztók igényei: [2000, 800, 1200, 1000, 1800] egység. A fajlagos szállítási költség az egyes viszonylatokban Ft/egység mértékegységben: R1 R2 R3 R4

F1 0 30 10 30

F2 20 0 20 20

F3 10 20 0 10

F4 20 10 0 20

F5 30 10 20 0 14


Határozzuk meg az optimális szállítási programot, továbbá kérdés, hogy megszüntethető-e valamelyik raktár anélkül, hogy a szállítási és raktározási költség növekedne? Alkalmazzuk a disztribúciós módszert.

4.4. A magyar módszer A magyar módszert H.W. Kuhn az ún. hozzárendelési probléma megoldására fejlesztette ki [43] Kőnig Dénes magyar matematikus egyik gráfelméleti tételének felhasználásával [46], amelyet egy másik magyar matematikus Egerváry Jenőáltalánosított [26]. E módszer széles körben felkeltette a matematikusok, és az elosztási problémákkal foglalkozó szakemberek figyelmét, különösen azóta, hogy Egerváry megmutatta, a módszer nemcsak a hozzárendelési probléma, hanem a szállítási feladat megoldására is alkalmas. A Kőnig-Egerváry-féle tétel általánosan a következők szerint fogalmazható meg: ha az R egy adott C[cij ] mátrix pontjainak egy nem üres részhalmaza, akkor az R-ben felvehetőfüggetlen pontok maximális száma megegyezik az R összes pontjait lefedővonalak minimális számával. A bizonyításnál abból indulnak ki, hogy adottnak tekintik az R-nek egy olyan maximális számú elemet tartalmazó F részhalmazát, amelynek minden eleme független pont. Ha az F pontjainak számát n-nel, az R minden pontját lefedővonalak számát v-vel jelöljük, akkor fennáll a vn összefüggés. Azt kell tehát csak megmutatni, hogy a v minimális értéke n. A gyakorlatban rendszerint az R halmazt ismerjük, és feladat az F meghatározása. A követendőeljárás a következő: a/ Az adott C C( 0 ) mátrixból elhagyjuk azokat a vonalakat, amelyeken nincs pontja R-nek. Legyen az így nyert mátrix C( 1) . b/ A C (1 ) -ben keresünk olyan vonalat, amelyen csak egy pontja van az R-nek. Ezt a pontot bevesszük a független pontok közé, majd a neki megfelelőkét vonalat elhagyva a C (1 ) -ből az eljárást annyiszor ismételjük, ahányszor csak lehetséges, így bizonyos számú lépés után vagy olyan C ( 2 ) mátrixhoz jutunk, amelyben már nincs pontja az R-nek, vagy pedig olyan C ( 3) mátrixot kapunk, amelynek minden vonalán legalább két R-hez tartozó pont található. Az elsőesetben a felvett független pontok száma maximális, és a fedővonalrendszer a később ismertetendőmódon megrajzolható. A második esetben azonban további lépések szükségesek. c/ A C( 3 ) egyik vonalán felvesszük a független pontok közé az R valamelyik elemét. Ezután a C( 3 ) -ból elhagyjuk a feltételezett független ponthoz tartozó két vonalat, majd az így nyert új mátrixszal az a, b és c lépéseket annyiszor ismételjük, ahányszor csak lehetséges. Az eljárás végén a független pontok olyan halmazához jutunk, amely újabb Rbeli ponttal nem bővíthető. Abban azonban nem lehetünk biztosak, hogy a független pontok száma maximális. Ez csak a fedővonalrendszer megszerkesztése után derül ki. Ha egy független pont sem esik a fedővonalak metszéspontjára, akkor a független pontok száma maxi15


mális. Ellenkezőesetben a független pontok halmazát és a fedővonalrendszert módosítani kell. A 3. pontban megfogalmazott szállítási feladatban az (5) célfüggvény minimumát keressük a (1)-(4) feltételek mellett. Ha a C költségmátrix soraihoz f i , oszlopaihoz pedig rj multiplicitásokat rendelünk, és az így nyert N-ed rendűmátrixot ( N i f i j rj ) B -vel jelöljük, akkor a problémát a következőképpen fogalmazhatjuk meg: Válasszunk ki a B -ben N független pontot úgy, hogy a megfelelőköltségelemek összege minimális legyen. Ha az f i rj 1, akkor a C minden sorának és oszlopának multiplicitása 1, és hozzárendelési problémával állunk szemben. Ennek a feladatnak a megoldása egyrészt a Kőnig-Egerváry-féle tételen alapszik, másrészt azon a tényen, hogy a cijcij pi q j ,

ahol a

pi min {cij j 1, 2,..., m}, q j min{cij pi i 1, 2,..., n}, transzformáció esetén, olyan C ' költségmátrixhoz jutunk, amelyhez ugyanaz az optimális megoldás tartozik, mint C -hez. A cij -t helyettesítsük a célfüggvénybe: z i j ( cijpi q j ) x ij  i j cijxij i j pi x ij  i j q j xij  i j cijx ij i pi ( j xij ) j q j ( i x ij ) .

Felhasználva a (4.2) és (4.3) összefüggéseket, a z i j c  i p i f i j q j r j . ij x ij 

Ezzel a z célfüggvényt az xij -től függőés attól független részekre bontottuk, és állításunkat bizonyítottuk. A transzformációt, mint már azt említettük, a költségmátrix redukciójának nevezzük. Legyen zi pi f i j q j rj ,

akkor a z i j cijx ij z  .

Könnyen belátható, hogy cij , pi , q j 0 kikötés mellett a z  z . Ha pedig min{  x ij } 0 , i j cij

akkor

min z  z . Bizonyítható, hogy mindig megadható a redukcióknak egy olyan véges sorozata, ami a fenti minimumra vezet. Alkalmazzuk a c(ij1) cij pi(1) q(j1) 16


redukciót, ahol

pi(1 ) min{cij j 1, 2,...,m} és q (j1) 0 . Ekkor a z i j cij(1 ) x ij z (1 ) , ahol a z (1 ) i pi( 1) f i .

A redukciót hajtsuk végre oszloponként is: cij( 2 ) cij pi( 2 ) q (j2 ) ahol a

pi( 2 ) 0 és q (j 2 ) min {cij i 1, 2,..., n} . A célfüggvény z i j cij( 2 ) xij z( 1) z ( 2 ) , ahol a z ( 2 ) i q (j2 ) rj . A cij( 2 ) mátrixban található zérus elemek közül az előzőleg leírt módon maximális számú független 0-át választunk ki. Ha ezek száma N, akkor min {i j c(ij2 ) xij } 0, és így min z z(1 ) z( 2 ) .

Ha azonban a független 0-ák száma kisebb, mint N, akkor megrajzoljuk a fedővonalrendszert, majd a le nem fedett elemek közül kiválaszt( 2) juk a minimálist. Ez legyen  . Ezután redukáljuk a cij( 2 ) költségmátrixot: c(ij3 ) cij( 2 ) pi( 3) q(j3 ) , ahol 0, pi( 3)  (2)  ,

ha az i-edik sor fedővonal,

0, q (j3)  (2)  ,

ha a j-edik oszlop fedővonal,

ha az i-edik sor nem fedővonal.

ha a j-edik oszlop nem fedővonal.

Ez gyakorlatilag azt jelenti, hogy a le nem fedett elemekből levonjuk ( 2) az  -t, az egyszer fedett elemeket változatlanul hagyjuk, a kétszer ( 2) fedett elemeket pedig  -vel növeljük. A redukció után a célfüggvény: z i j cij( 3 ) x ij z (1 ) z ( 2 ) z ( 3) ahol a 17

A szállítási feladat ( 2) ( 2) z ( 3)  d .

A d ( 2 ) az N-nek és a független zérusok számának a különbsége. A c(ij3 ) mátrixban független zérusokat keresünk, elkészítjük a fedővonalrendszert, majd redukáljuk a mátrixot. E lépéseket addig ismételjük, amíg olyan cij( r) mátrixot nem kapunk, amelyben a független zérusok száma N. Ekkor z cij( r ) x ij z (1 ) z( 2 ) ... z( r ) min , ahol a (r )  0. i j cij xij 

A módszer matematikai indoklása után tekintsük a hozzárendelési és a szállítási feladat esetén alkalmazható algoritmusokat.

A hozzárendelési feladat megoldása magyar módszerrel Feltételezzük, hogy adott négy professzor, akik valamennyien képesek előadásokat tartani különbözőtémakörökből. Tekintettel azonban a professzorok eltérőszakirányultságára, az egyes előadások előkészítéséhez szükséges időtartam professzoronként változó. A tanszékvezető egyéb területeken is szeretné foglalkoztatni a professzorokat, ezért az előadásokat, úgy kívánja elosztani közöttük, hogy azok előkészítése a lehetőlegkevesebb időt igényelje. Az előadások előkészítéséhez szükséges időtartamokat az a következőtáblázat foglalja össze: Professzor

Lineáris programozás

Sorbanállási elmélet

Dinamikus programozás

Regresszió analízis

Kovács Kiss

2 15

10 4

9 14

7 8

Fehér

13

14

16

11

Nagy

4

15

13

9

Oldjuk meg a problémát a magyar módszerrel. 1. Ha feladat a célfüggvény maximumának meghatározása, akkor változtassuk meg a költségmátrix minden elemének előjelét. A minimum feladathoz tartozó költségmátrix: 2 15 13 4

10 4 14 15

9 14 16 13

7 8 11 9

2. Redukáljuk a mátrixot soronként! 0 11 2 0

8 0 3 11

7 10 5 9

5 4 0 5

pi 2 4 11 4 21

3. Redukáljuk a mátrixot oszloponként! 18


qj

0 11 2 0 0

8 0 3 11 0

2 5 0 4 5

5 4 0 5 0

5

Az összes redukció értéke: z0 i pi j q j 21526.

4. Keressük meg azokat a sorokat, amelyekben független 0 elem van. (A 0 elem akkor független, ha egyedül álló jelöletlen 0 a szóban forgó sorban.) Ha találtunk ilyen sort, akkor a független 0 elemet jelöljük csillaggal (*). A független 0 elem oszlopában található többi 0 elemet pedig jelöljük meg kereszttel (+). A másodlagosan megjelölt 0-k segítségével megszüntetjük az oszlop aktivitását (ui. egy sorban és oszlopban csak egy 0 elemet jelölhetünk ki). Ismételjük az eljárást addig, amíg a sorokban újabb és újabb független 0 elemet tudunk kijelölni. 0* 11 2 0+

8 0* 3 11

2 5 0 4

5 4 0 5

5. Keressük meg azokat az oszlopokat, amelyekben független 0 elem van. (A 0 elem akkor független, ha egyedül álló jelöletlen 0 a szóban forgó oszlopban.) Ha találtunk ilyen oszlopot, akkor a független 0 elemet jelöljük csillaggal (*). A független 0 elem sorában található többi 0 elemet pedig jelöljük meg kereszttel (+). A másodlagosan megjelölt 0-k segítségével megszüntetjük a sor aktivitását. Ismételjük az eljárást addig, amíg az oszlopokban újabb és újabb független 0 elemet tudunk kijelölni. 0* 11 2 0+

8 0* 3 11

2 5 0* 4

5 4 0+ 5

6. Ismételjük a 4. és 5. lépéseket, amíg az eredményre vezet. Ha már nem tudunk új független 0-át kijelölni, akkor a következőhárom eset fordulhat elő. a/ minden sorban kijelöltünk egy független 0 elemet, b/ van olyan sor vagy oszlop, amelyikben legkevesebb két jel nélküli 0 elem van, c/ nincs jelöletlen 0 elem, de a független nulla elemek száma kevesebb, mint a sorok száma. 7. Ha az a/ eset fordul elő, akkor a kijelölés teljes, megkaptuk az optimális megoldást. A b/ esetben véletlenszerűen jelöljük meg az egyik jel nélküli 0 elemet csillaggal (*), majd ugyanebben a sorban és oszlopban jelöljük kereszttel (+) a többi jelöletlen nulla elemet, majd tér19


jünk vissza a 4. lépéshez. A harmadik, c/ esetben folytassuk az eljárást a 8. lépéssel. 8. Jelöljük meg azokat a sorokat, amelyekben nincs független 0. 9. Jelöljük meg azokat az oszlopokat, amelyek még nincsenek megjelölve, és az oszlopban található olyan 0, amely megjelölt sorban van. 10. Jelöljük meg azokat a sorokat, amelyek még nincsenek megjelölve, és amelyekben a független 0 a megjelölt oszlopban van. 11. Ismételjük a 9. és 10. lépéseket addig, amíg az eredményre vezet. 0* 11 2 0+ 

8 0* 3 11

2 5 0* 4



5 4 0+ 5



12. Fedjük le a meg nem jelölt sorokat és a megjelölt oszlopokat. Ez biztosítja, hogy a 0 elemeket minimális számú fedővonallal fedjük le. (Ha nem vétettünk hibát, akkor a fedővonalak száma megegyezik a független 0-k számával.) 0* 11 2 0+ 

8 0* 3 11

2 5 0* 4



5 4 0+ 5



13. Keressük meg a fedetlen elemek közül a legkisebbet ( ), ez esetünkben =2, majd a le nem fedett elemeket csökkentsük -nal, az egyszer fedett elemeket változatlanul hagyjuk, a kétszer fedett elemeket növeljük -nal, és térjünk vissza a 4. lépéshez. 0 13 4 0

6 0 3 9

0 5 0 2

3 4 0 3

A célfüggvény változása:

z1 z0 (n f ) 26 2 (4 3) 28 , ahol f a független 0 elemek száma. 0+ 13 4 0*

6 0* 3 9

0* 5 0+ 2

3 4 0* 3 20


A független 0 elemek száma f=4, így befejeződött az eljárás. Az optimális megoldás: x13 1; x22 1; x34 1; x41 1, a célfüggvény értéke pedig

z z1 28 .

A szállítási feladat megoldása magyar módszerrel Az algoritmus bemutatásához tekintsük a disztribúciós módszernél ismertetett feladatot: fi 6 4 1 5 50 2 1 3 8 40 1 2 1 1 30 rj 40 10 60 10 1. Redukáljuk a költségmátrixot soronként és oszloponként: fi 5 3 0 4 50 1 0 2 7 40 0 1 0 0 30 rj 40 10 60 10

pi 1 1 1

A redukció értéke: z0 i pi f i j q j rj 120 .

2. Független 0 elemet keresünk az i-edik sorban. (Független a 0 elem, ha az f i 0, rj 0 , és a sorban egyedül álló programozható 0.) Ha találtunk ilyen elemet, akkor arra annyit programozunk, amennyit a sor és oszlopkészlet megenged. Itt három eset lehetséges: Ha az f i rj , akkor egyszerre fogy el a sor- és oszlopkészlet. Ilyenkor elhagyjuk az i-edik sort és a j-edik oszlopot, és a következősoron megismételjük a 2. lépést. Ha az f i rj , akkor elfogy a sorkészlet, ekkor az i-edik sort elhagyjuk, és a j-edik oszlopban a 3. lépéssel folytatjuk. Ha az f i rj , akkor elfogy az oszlopkészlet, ekkor a j-edik oszlopot elhagyjuk, és az i+1-edik sorban a 2. lépéssel folytatjuk.

rj

5 1 0 40 40

3 010 1 10 0

50

0 2 10 0 60 0

4 7 0 10 10

fi 50 40 30

0 30 20

Ha elfogynak a sorok, akkor a 3. lépéssel folytatjuk. 3. Független 0 elemet keresünk a j-edik oszlopban. (Független a 0 elem, ha az f i 0 , rj 0 és az oszlopban egyedül álló programozható 0.) Ha találtunk ilyen elemet, akkor arra annyit programozunk, amenynyit a sor- és oszlopkészlet megenged. Itt három eset lehetséges: 21


Ha az f i rj , akkor egyszerre fogy el a sor- és oszlopkészlet. Ilyenkor elhagyjuk az i-edik sort és a j-edik oszlopot, és a következő oszlopon megismételjük a 3. lépést. Ha az f i rj , akkor elfogy a sorkészlet, ekkor az i-edik sort elhagyjuk, és a j+1-edik oszlopban a 3. lépéssel folytatjuk. Ha az f i rj , akkor elfogy az oszlopkészlet, ekkor a j-edik oszlopot elhagyjuk, és az i-edik sorban a 2. lépéssel folytatjuk.

5 1 20 0 40 20

rj

3 10 0 1 0 0

50

0 2 10 0 0 0

4 7 0 10 10

fi 0 40 20

0 30 0

4. Ismételjük a 2. és 3. lépéseket, amíg az eredményre vezet. Ha már nem találunk több független 0-t, akkor a következőhárom eset fordulhat elő: a/ a sor- és oszlopkészleteket sikerült teljesen elosztani; b/ a sor- és oszlopkészleteket nem sikerült teljesen elosztani, mivel vannak olyan sorok és oszlopok, ahol nem tudtunk egyértelműen független 0 elemet választani; c/ a sor- és oszlopkészleteket nem sikerült teljesen elosztani, mivel azokban a sorokban és oszlopokban, ahol maradt készlet, nincs programozható független 0 elem. 5. Az a/ esetben az elosztás teljes, megkaptuk az optimális megoldást. Ha a b/ eset fordul elő, véletlenszerűen kiválasztjuk az egyik programozható 0 elemet és annyit programozunk rá, amennyit a sor- és oszlopkészlet megenged, majd visszatérünk a 2. lépéshez. A c/ esetben a 6. lépéssel folytatjuk. 6. Megszerkesztjük a fedővonalrendszert. Ennek lépései a következők: a/ jelöljük meg azokat a sorokat, amelyekben van elosztatlan készlet; b/ jelöljük meg azokat az oszlopokat, amelyek még nincsenek megjelölve, és az oszlopban található olyan 0 elem, amely megjelölt sorban van; c/ jelöljük meg azokat a sorokat, amelyek még nincsenek megjelölve, és amelyekben a független 0 elem megjelölt oszlopban van; d/ ismételjük a b/, c/ lépéseket addig, amíg eredményre vezet.

rj

5 1 20 0 20

 3 10 0 1 0

50

0 2 10 0 0

4 7 0 10

fi 0 30 0



22


e/ fedjük le a meg nem jelölt sorokat és a megjelölt oszlopokat (ha a fedővonalak a független 0 elem felett nem keresztezik egymást, akkor a független 0-kat helyesen választottuk meg), és a 7. lépés szerint redukáljuk a mátrixot.  3 10 0 1 0

5 1 20 0 20

rj

50

0 2 10 0 0

fi 0 30 0

4 7 0 10



7. Redukció: a/ a fedetlen elemek közül megkeressük a legkisebbet, ez legyen  ; b/ az  -t a fedetlen elemekből levonjuk, a kétszer fedett elemekhez pedig hozzáadjuk; c/ az egyszer fedett elemeket változatlanul hagyjuk, és visszatérünk a 2. lépéshez. Az = 1 5 0 0 40

rj

4 0 2 10

0 1 0 60

fi 50 40 30

4 6 0 10

A célfüggvény változása:

z1 z0 ( N d ) 120 1(120 90) 150 , ahol az N i f i j rj , d pedig a független 0-k száma, vagyis az elosztott készlet. A 2. és a 3. lépések után megkapjuk az optimális megoldást. 5 30 0 10 0 40 0

rj

50

4 10 0 2 10 0

0 1 10 0 60 0

4 6 10 0 10 0

fi 50 40 30

0 0 0

x13 50; x 21 30; x 22 10; x 31 10; x 33 10; x34 10, z z2 150 . 4.5. példa: Egy úszócsapat edzőjének össze kell állítania a 4x50 m-es vegyesváltó csapatát. Gondot okoz, hogy öt úszó közül kell kiválasztani a négy úszásnemhez négy úszót, akiknek az 50 méteren elért eredményei a négy úszásnemben következők: Hát Mell Pillangó Gyors

Kovács 37,7 43,4 33,3 29,3

Kiss 32,9 33,1 28,5 26,4

Czene 33,8 42,2 38,9 29,6

Baross 37,0 34,7 30,4 28,5

Józsa 35,4 41,8 33,6 31,1 23


Kezeljük a feladatot hozzárendelési problémaként, és oldjuk meg a magyar módszerrel. 4.6. példa: Egy budapesti fuvarozónak a központi raktárából 4 vidéki vevőt kell ellátnia árukkal. A fuvarozó 5 darab tehergépkocsival rendelkezik. A rakodás és a szállítás költsége a tehergépkocsik különbözősége miatt függ a tehergépkocsi - vevőpárosítástól. Ezt a függőséget a következőköltségtáblázat mutatja:

Tgk. 1 Tgk. 2 Tgk. 3 Tgk. 4 Tgk. 5

Vevő1 300 500 400 300 400

Vevő2 500 600 700 600 500

Vevő3 600 400 500 500 600

Vevő4 400 500 600 400 300

A cél a tehergépkocsik és a vevők párosítása úgy, hogy az összes szállítási költség minimális legyen. 4.7. példa: Oldjuk meg a következőszállítási feladatot a disztribúciós és a magyar módszerrel: 5 3 4 5 3

5 8 4 5 3

5 8 12 5 3

10 8 12 17 3

2 2 4 4

4.8. példa: Három cementgyár (Ci) négy házgyárat (Hj) lát el cementtel. A cementgyárakban 1 tonna cement termelési költsége rendre 3000, 3100 és 3500 Ft. A házgyárak havi igénye 100, 150, 130 és 140 tonna cement. A cementgyárak kapacitása egyaránt 200 tonna havonként, a cement szállítási költsége pedig Ft/t-ban: H1

H2

H3

H4

C1

650

630

480

150

C2

520

460

370

610

C3

120

180

300

400

Ha a C1 cementgyár kapacitását teljes mértékben ki kell használni, és egyik cementgyár sem termelhet raktárra, akkor mi lesz az a termelési és szállítási terv, amely minimalizálja az összköltséget? Melyik cementgyár kapacitását kell csökkenteni és mennyivel? 4.9. példa: Oldja meg a következőkétlépcsős elosztási feladatot! Két üveggyár (Ti) éves kapacitása 600 illetve 800 ezer db szabványos üvegpalack. A két készletezővállalat raktárainak (Rj) éves átbocsátóképessége 200 és 400 ezer db üveg. A három fogyasztó (Fk ) éves felhasználása 200, 100 és 100 ezer db üveg. A gyárak milyen kapacitással termeljenek, a gyárak mely készletezőknek szállítsanak és mennyit, 24


a fogyasztók mely készletezőktől szerezzék be szükségletüket, ha az üveggyárak fajlagos termelési költsége: [38, 42]

Ft/1000 db,

a fajlagos szállítási költség a gyárak és db): R1 T1 12 T2 8

a készletezők között (Ft/1000 R2 22 16

a készletezők raktározási költsége: [5, 8]

Ft/1000 db

a fajlagos szállítási költség a készletezők és a fogyasztók között (Ft/1000 db): F1

F2

F3

R1

10

20

80

R2

90

50

10

4.5. Alkalmazások Ebben a fejezetben bemutatjuk a szállítási feladat széleskörűalkalmazási lehetőségeit, továbbá azokat a fogásokat, amelyek lehetővé teszik bonyolultabb problémák megfogalmazását a feladat keretei között. A gabonafelvásárlási modell a kétlépcsős szállítási feladat tipikus példája. Az áruelhelyezési modellben pedig megmutatjuk, hogyan lehet többféle terméket egyidejűleg optimálisan elosztani [13].

A gabonafelvásárlás modellje Kétlépcsős szállítási problémáról akkor beszélünk, ha a T1,...,Ti,...,Tn termelők t 1,...,ti,...,t n mennyiségűterméket állítanak elő, és ezt az R 1,..., Rj,...,R m készletezőraktárak vásárolják fel az r1,...,rj,...,rm kapacitásaiknak megfelelően, majd készleteikből az F 1,...,Fk ,...,Fp fogyasztók igényeit kielégítik az f 1,...,fk ,...,fp megrendelések szerint. A leírt modell egyszerűen adaptálható a gabonaipar felvásárlási tevékenységére, ahol a termelőknek a mezőgazdasági üzemek, a készletezőknek a gabonaipar saját raktárai és bértároló helyei, a fogyasztóknak pedig a malmok, takarmánykeverők felelnek meg. A matematikai modell megfogalmazása előtt tekintsük a feladat disztribúciós tábláját (4.2. táblázat). A modellben, illetve a disztribúciós táblában használt jelölések a következők: Ti az i-edik mezőgazdasági üzem, R j a j-edik raktár, B i bértároló hely az i-edik mezőgazdasági üzemben, F k a k-adik feldolgozó üzem, E értékesítés,  külsőbeszállító, ti az i-edik mezőgazdasági üzem feladása, 25


rj bi fk e  xij x'i yjk zik

j ßi  j  'i  k cij hi

a j-edik raktár kapacitása, a bértároló hely kapacitása, a k-adik feldolgozó üzem igénye, az értékesíthetőmennyiség, a külsőbeszállító által szállított mennyiség az i-edik mezőgazdasági üzemből a j-edik raktárba szállított mennyiség, az i-edik mezőgazdasági üzemben bértárolt mennyiség, a j-edik raktárból a k-adik feldolgozó üzembe szállított mennyiség, az i-edik bértároló helyről a k-adik feldolgozó üzembe szállított mennyiség, a j-edik raktár le nem kötött kapacitása, az i-edik bértároló le nem kötött kapacitása, a j-edik raktárból értékesített mennyiség, az i-edik bértárolóból értékesített mennyiség, a külsőbeszállítóktól a k-adik feldolgozó üzembe szállított mennyiség, az i-edik mezőgazdasági üzem és a j-edik raktár közötti fajlagos szállítási költség, a bértárolás fajlagos költsége,

4.2. táblázat A gabonafelvásárlási modell disztribúciós táblája R1

Rj

Rm

B1

Bi

Bn

F1

Fk

Fp

E

T1 Ti Tn

c 11 ci 1 c n1

c 1j cij c nj

c 1m cim cnm

h1 M

M hi

M M

M M

M M

M M

M

M

M M hn

0 M M

M 0 M

M M 0

M M M

M M M

M M M

M a11

M a1k

M a1p

M

R1

aj1 am 1

ajk amk

ajp amp

B1 Bi Bn

M M

M M

M M

0 M

M 0

M M

M

M

M

M

0

d1k dik dn,k

d1p dip dn,p

0 0

M

d11 di1 dn1



M r1

M rj

M rm

M b1

M bi

M bn

0 f1

0 fk

0 fp

M e

Rj Rm

0 0 0

0

t1 ti tn r1 rj rm b1 bi bn



ajk a j-edik raktár és a k-adik feldolgozó üzem közötti fajlagos szállítási költség, dik az i-edik bértároló és a k-adik feldolgozó üzem közötti fajlagos szállítási költség, M tiltótarifa. A Ti termelők az Rj gabonaipari raktárakba, vagy a Bi saját, bértárolásra kiadott raktáraikba szállíthatnak, ezért a termelők és a fel nem sorolt relációk között a szállítást letiltottuk, vagyis az Fk felhasználók 26


közvetlen ellátását, illetve az E értékesítést a Ti termelőktől kizártuk (4.2. táblázat). A szállítás második lépcsőjében az R j raktárakból és a Bi bértároló helyekről látjuk el alapanyaggal az Fk felhasználókat. A visszaszállítás lehetőségét tiltótarifa alkalmazásával akadályoztuk meg. Lehetőséget biztosítottunk azonban az j , ßi raktárkapacitás feleslegek, illetve a felhasználók igényét meghaladó  ' i termelői kapacitásfelesleg elhej,  lyezésére, vagyis a modellben a feladások és megrendelések egyenlősége automatikusan teljesül. Ha a ti>f k, akkor a termelői kapacitásfelesleg értékesíthető. Ezt a t i fk=e feltétellel biztosíthatjuk. Ha a t i<fk , akkor a fk ti=hiányt külsőbeszállítók egyenlítik ki. Ha a rj+bi>t i, akkor a raktárkapacitás-feleslegek az R j-Rj és Bi-B i relációk által meghatározott szektor diagonálisán csapódnak le. Ezt a diagonális 0 értékűköltségelemei biztosítják. Az elmondottak megértését a 4.3. táblázat segíti elő, amelyben a feladat megoldási mátrixát közöljük, amelyből már egyszerűen felírható a matematikai modell. 4.3. táblázat A gabonafelvásárlási modell megoldási mátrixa R1

Rj

Rm

B1

Bi

Bn

F1

Fk

Fp

T1 Ti

x 11 x i1

x1j x ij

x 1m x im

x' 1

0

0

0

0

Tn

x n1

xnj

x nm

0 0

0 x' i 0

0 x'n

R1 Rj

1

0 j

0

0

0

0

0

0

0

0 0 y 11 y j1

0 0 y 1k y jk

0 0 y 1p y jp

0

0

y m1

ymk

ymp

0

z11

z1k

z1p

zi1 zn1

zik znk

zip znp

1 f1

k fk

p fp

Rm

0 0

0

0 m

B1

0

0

0

0 ß1

Bi Bn

0

0

0

0

0 ßi

0

0

0

0

0

0 ßn



0 r1

0 rj

0 rm

0 b1

0 bi

0 bn

E 0 0 0 1

 j  m  '1  'i  'n 0

t1 ti tn r1 rj rm b1 bi bn



e

A matematikai modell: xij 0, yjk0, zik0, j 0, ßi 0,  0,  ' i0, k 0, j ahol az i=1,2,...,n, j=1,2,...,m, k=1,2,...,p, i x ij + j = rj, x'i + ßi = bi , jy jk + izik +k= fk , j ' i = e, j + i ahol az i t i k f k , ha i t i k f k 0, e  ha i t i k f k 0 0,

jx ij + x'i = t i, j + ky jk +  j = rj , 27


ßi + k zik +  'i = bi, k k = , ahol a  f i t i , ha i t i k f k 0,  k k 0, ha i t i k f k 0, 

it i + j rj + ibi + = jrj + ibi + kf k + e, ijcij xij + ihi x'i + jkajk y jk + ik dik zik = min.

Az áruelhelyezés optimalizálása a gabonaiparban A gabonaforgalmi és malomipari vállalatok a korábbi tröszti irányításnak köszönhetően egységes koncepció, a területi elv alapján kisebb szervezeti egységekre, ún. körzeti üzemekre tagolódtak. Ezek tevékenysége általában nem volt specializált, sőt inkább azt a sokszínűség (malomipar, takarmánygyártás, stb.) jellemezte, ami a privatizáció után sem sokat változott. Az üzemek gyártási folyamatai nemcsak anyagigényesek, hanem sokféle anyag elkülönített tárolását követelték meg. A felhasznált anyagok fizikai tulajdonságai eltérőek, tárolási módjuk különböző, amiből adódóan a raktárrendszerek is sokszínű képet mutatnak. Egy-egy üzemben a legkorszerűbb silóktól az ideiglenes horizontális raktárig mindenféle tároló fajta és típus megtalálható, amelyek más és más anyagmozgatási technológiát igényelnek. A nehézségeket tovább fokozza, hogy a raktárak és a feldolgozó üzemek különbözőidőszakokban létesültek, így magukon viselik a különbözőkorok építészeti stílus jegyeit és telepítésük sem mindig a legcélszerűbb. E helyzetkép ismeretében magától értetődően felvetődik a kérdés, ilyen sokszínűraktárrendszerben elképzelhető-e optimális áruelhelyezés. A kérdés megválaszolásához fogalmazzuk meg a problémát egy leegyszerűsített modell formájában. Adott egy üzem, amely meghatározott időszakban A1,...,A k,...,A l féle anyagot használ fel az F 1,...,Fj,...,F m féle gyártási tevékenységéhez f11,...,f jk,...,f ml mennyiségben. A gyártáshoz szükséges anyagokat az R1,...,Ri ,...,Rn raktárakban tároljuk r11,...,rik ,...,rnl mennyiségben. Az anyagokat úgy kell elhelyezni a raktárakban, hogy az összes raktározási (betárolási, tárolási, kezelési) és szállítási költség minimális legyen. A leírásból kiderül, a probléma a szokványos elosztási feladat formájában nem írható fel. A feladat specifikuma, hogy egyidejűleg többféle anyagot kell a raktár-felhasználó viszonylatokhoz hozzárendelni x ijk mennyiségben. Mivel a j x ijk rik ,

így a klasszikus feladattól eltérően az rik peremadatok is ismeretlenek. Ha ugyanis a

k rik ri triviális feltételnek megfelelően az rik értékeket előírnánk, akkor lemondanánk a raktározási költségek szerinti optimálásról, és a progra28


munk csak a raktárak felhasználók közötti szállítási költségekre nézve adná a legkedvezőbb megoldást. A jelzett probléma kiküszöbölésre alakítsuk át a modellünket. Legyen r'ik a k-adik anyagból az i-edik raktárban potenciálisan tárolható mennyiség, és legyen i k r 'ik ri , ahol az ri az i-edik raktár kapacitása, és az r'ikri. A k szerint szummázott r'ik akár az ri tényleges raktárkapacitás többszöröse is lehet. Ez akkor fordulhat elő, ha például az i-edik raktárban egyetlen anyag tárolását sem korlátozzuk. A i tehát egy olyan fiktív mennyiség, amely megmutatja, hogy az anyagonként megadott kapacitások összege mennyivel nagyobb az i-edik raktár tényleges kapacitásánál. A modell egyensúlyának biztosítására, a raktáranként jelentkezői kapacitásokat a i fiktív felhasználókkal kötjük le. A gyakorlati esetek többségében a felhasználók raktárigénye nem egyenlőa rendelkezésre álló raktárkapacitással, ezért további fiktív felhasználót és raktárt is be kell iktatni. A lehetséges esetek, ha a raktárkapacitás hiány, pedig a raktárkapacitás felesleg:

   f i ri , ha j k f jk i ri 0  j k jk 0, ha j k f jk i ri 0  és ha j k f jk i ri 0 0,  i ri j k f jk , ha j k f jk i ri 0 4.4. táblázat

Az áruelhelyezési modell disztribúciós táblája A1

Ak

Al

F1

Fj

Fm

F1

Fj

Fm

F1

Fj

Fm

1

i

n

A1

R1 Ri Rn

c 111 ci11 c n11

c1j1 cij1 cnj1

c1m1 cij1 c nm

M M M

0 M M

M 0 M

M M 0

Ak

M M M

M M M

M M M c1mk c ijk cnmk

M M M

M M M

M M M c 1jk cijk c njk

M M M

R1 Ri Rn

M M M c 11k c i1k c n1k

M M 0

M M M

M M M

M M M

M M M

M M M

M M M

M M M c1.ml cijl cnml

M 0 M

R1 Ri Rn

M M M c1jl cijl cnjl

0 M M

Al

M M M c 11l ci1l c n1l

0 M M

M 0 M

M M 0

R

0 f11

0 fj1

0 fm1

0 f1k

0 fjk

0 fmk

0 f11

0 fj1

0 fm1

M 1

M i

M n

29

 0 0 0 0 0 0 0 0 0 M 

r'11 r'i1 r'n1 r'1k r'ik r'nk r'1l r'il r'nl




4.5. táblázat Az áruelhelyezési modell megoldási mátrixa A1

A1

Ak

Al

Ak

F1

Fj

Fm

R1 Ri Rn

x 111 xi11 x n11

x 1j1 xij1 x nj1

x1m1 x ij1 x nm

0 0 0

R1 Ri Rn R1 Ri

0 0 0

0 0 0

0 0 0

0 0 0 x'11

0 0 0 x'j1

f11

fj1

Rn R

F1

Fj

Al Fm

F1

Fj

Fm

1

i

n

y 111

0 y ii1

0 0

0

ynn1

0 y iik

0 0

0

ynnk

0 yiil

0 0 0

0 0 0

0 0 0

0 0 0

x 11k x i1k x n1k

0 0 0 x 1jk x ijk x njk

x1mk x ijk xnmk

0 0 0 x' 1k

0 0 0 x' jk

0 0 0 x'mk

0 0 0 x1jl xijl

0 0 0

0 0 0 x' m1

0 0 0 x 11l xi1l

x1.ml xijl

x n1l

xnjl

xnml

x'1l

x'jl

x' ml

fm1

f1k

fjk

fmk

f1l

fjl

fml

0 0 y11k 0 0 y 11l 0 0 0 1

 y'11 y'i1 y'n1

r'11 r'i1 r'n1

0 0

y' 1k y'ik y' nk y'1l y' il

r'1k r'ik r'nk r'1l r'il

0

y nnl

y'nl

r'nl

0 i

0 n

0





Az új változók bevezetésével az áruelhelyezés optimumát biztosító modell a következő: xijk 0, (i 1,... n, j 1,...m , k 1,...l ) y ijk 0 x  0 jk

y ik 0 j xijk yiik y rik ik

rikri i xijk x  f jk jk

k yiik i

i k rikri i k rikj k f jk i i  i j k cijk x ijk z  min

ahol xijk az i-edik raktárból a j-edik felhasználóhoz szállított k-adik anyag mennyisége, yiik az i-edik raktárból az i-edik fiktív felhasználó által a k-adik anyagból lekötött mennyiség, x'jk a j-edik felhasználó raktárkapacitás hiánya a k-adik anyagból, y'ik az i-edik raktár kapacitás feleslege a k-adik anyagból, cijk a fajlagos raktározási és szállítási költség, fjk a j-edik felhasználó igénye a k-adik anyagból, rik az i-edik raktárban a k-adik anyagból potenciálisan tárolható mennyiség, i az i-edik fiktív felhasználó igénye, ri az i-edik raktár kapacitása,  az összes raktárkapacitás hiány  az összes raktárkapacitás felesleg. 30


A modell disztribúciós tábláját a 4.4. táblázatban, a megoldási mátrixot a 4.5. táblázatban közöljük. A táblázatokban az előzőeken kívül még a következőjelöléseket alkalmaztuk: R i az i-edik raktár (i=1,...,n) R fiktív raktár F j a j-edik felhasználó, A k a k-adik anyag, i az i-edik fiktív felhasználó,  fiktív felhasználó, M tiltótarifa. A modell alkalmazási lehetőségének megértéséhez tekintsük a következőegyszerűproblémát: Adott egy üzem két raktárral: R 1, R2 , amelyek kapacitása: r1=100 és r2 =150 egység. Az üzem három feldolgozó részlege: F 1, F2, F3 , három féle anyagot: A1 ='búza', A2 ='kukorica', A3 ='árpa' igényel a gyártási tevékenységéhez. Készítsünk optimális raktározási tervet. A felhasználók anyagonkénti igényét a 4.6. táblázat, a raktárakban az anyagonként tárolható mennyiségeket a 4.7. táblázat tartalmazza. 4.6. táblázat Felhasználó (Fj ) F1 F2 F3 F1 F2 F3 F1 F2 F3 Összesen

Anyag (Ak) búza

kukorica

árpa

Igény (fjk) 50 40 20 40 70 50 10 15 20 315

4.7. táblázat Raktár R i R1 R2

Anyag (Ak) búza

Kapacitás (r'ik) 80 100

R1 R2

kukorica

100 150

R1 R2 Összesen

árpa

100 150 680

Amint az látható a kukorica és az árpa, a két raktár kapacitását teljesen lekötheti, míg az elsőraktárban a búzából csak 80 egység, kukoricából pedig 100 egység tárolását engedjük meg. A raktáranként megadott mennyiségeket összegezve, majd abból a tényleges raktárkapacitást 31


levonva megkapjuk azokat az i mennyiségeket amelyeket a i fiktív felhasználók fognak lekötni.

1 k r1 k r1 280 100 180 , 2 k r2 r2 400 150 250 . k A felhasználók igényeit, a tényleges raktárkapacitásokkal összevetve: j k f jk i ri ,

ezért a különbséget a korábban említett feltételeknek megfelelően fiktív raktár beállításával egyenlítjük ki, amelynek a kapacitása =315250=65 egység. 4.8. táblázat Raktár (R i)

R1

R2

R1

R2

R1 R2

Felhasználó (Fj) F1 F2 F3 F1 F2 F3 F1 F2 F3 F1 F2 F3 F1 F2 F3 F1 F2

Anyag (A k)

búza

kukorica

árpa

Fajlagos szállítási költség (cijk) 5 6 2 4 5 3 6 5 3 4 6 4 5 5 4 5 7

Az egyszerűség kedvéért a fajlagos raktározási költségeket figyelmen kívül hagyjuk. A felhasználók és a raktárak közötti fajlagos szállítási költségeket a 4.8. táblázat tartalmazza. A táblázatban az árpánál a R2 F3 viszonylat nem szerepel, ami gyakorlatilag azt jelenti, hogy a F3 részére a R 2-ben nem tárolhatunk árpát. A disztribúciós táblában nyilvánvalóan ez a viszonylat tiltott lesz. Előfordulhat az is, hogy valamelyik anyag valamelyik raktárban egyetlen felhasználó részére sem tárolható. Ekkor a disztribúciós táblából egyszerűen elhagyjuk a nem kívánatos sort. Ha viszont valamelyik felhasználónak valamelyik anyagból nincs igénye, akkor értelemszerűen a disztribúciós tábla egyik oszlopa marad el. Az adatokat egyszerűen a 4.5. táblázatba helyettesítve nyertük a feladat disztribúciós tábláját (4.9. táblázat), amelybe az optimális raktározási programot is beírtuk. A 4.10. táblázat a megoldáshoz használt számítógép program által szolgáltatott eredményeket mutatja be. 32


4.9. táblázat A raktározási feladat disztribúciós táblája és megoldása A1 A2 A3 R1 R2 A1 A2 A3

F1

F2

R2

5 450

6 540

R1

M

R2

1 070

2

rik

M

80

0

100

F3 210

F1

F2

F3

F1

F2

F3

M

M

M

M

M

M

310

M

M

M

M

M

M

M

M

M

M

M

M

045

M

M

55 60

350

M

6 440

4

M

R1

M

M

M

M

M

M

M 420

M 065

R2

M

M

M

M

M

5 5 10

M 515 7

M

M

0

0

0

0

M

M

65

50

10

15

20

180

250

745

R1

R

0

0

0

0

M 065

fjk

50

40

20

40

70

M 100 110 0 150 M 100 140 0 150

4.10. táblázat OPTIMÁLIS NYERS- ÉS ALAPANYAG ELHELYEZÉS ANYAG

RAKTÁR

FELHASZNÁLÓ

MENNYISÉG

búza búza búza búza búza kukorica kukorica kukorica kukorica kukorica kukorica árpa árpa árpa árpa

raktár1 raktár1 raktár2 raktár2 raktár2 raktár1 raktár1 raktár1 raktár2 raktár2 raktár2 raktár1 raktár1 raktár1 raktár2

felhasználó3 fiktív felhasználó felhasználó1 felhasználó2 felhasználó3 felhasználó2 felhasználó3 fiktív felhasználó felhasználó1 felhasználó2 fiktív felhasználó felhasználó2 felhasználó3 fiktív felhasználó felhasználó1

10 70 50 40 10 5 50 45 40 0 110 15 20 65 10

árpa kukorica

raktár2 fiktív raktár

fiktív felhasználó felhasználó2

140 65

ÖSSZES RAKTÁROZÁSI ÉS SZÁLLÍTÁSI KÖLTSÉG: 990

Átrakási probléma Az átrakási (transshipment) probléma általában az összetett vagy kombinált szállítással összefüggésben merülhet fel. Összetett szállításról, mint ismeretes, akkor beszélünk, ha a szállítójárműváltoztatja a pályáját, vagy két, esetleg több járműtovábbítja az árut. Az utóbbi esetben azonos vagy különbözőközlekedési ágazatok járművei egyaránt szóba kerülhetnek, pl. közút, vasút, vízi út stb. Az összetett szállítás a járműváltás miatt általában nem elhanyagolható költséget is jelentőrakodással jár. Mégis, számos esetben az átrakás gazdaságilag olyan előnyös lehet, hogy nemcsak kompenzálja az átrakás költségét, hanem csökkenti az összes költséget is. Például a nagy távolságú vasúti szállítás sokkal olcsóbb, mint a közúti, ezért nagyon gyakori a közúti és vasúti szállítás kombinálása. Arra a kérdésre, 33


hogy milyen esetben olcsóbb a kombinált fuvarozás a közvetlen szállításnál, az átrakási probléma ad választ. Mint azt látni fogjuk, az átrakási probléma nagyon egyszerűen visszavezethetőa szállítási feladatra [34], és bármely ismert módszerrel megoldható. A feladat struktúrájának bemutatására tekintsük a következőpéldát. Három malom (M1, M2, M3) 1200, 1300, 1050 t havi kapacitással négy kenyérgyárat (K1 , K2 , K3, K4) lát el liszttel. A kenyérgyárak havi igénye 1250, 1000, 600, 700 tonna havonta. A liszt közvetlen szállítási költsége közúton a malmok és a kenyérgyárak között [Ft/t]: K1 90 1314 618

M1 M2 M3

K2 60 1284 588

K3 1224 48 1746

K4 588 1746 30

A kenyérgyárak vasúton is megközelíthetők, de csak közvetve, ezért a lisztet a malmokból vasúti átrakó helyekre (T1 , T2, T3), illetve az átrakó helyekről a kenyérgyárakba közúton kell szállítani. A vasúti szállítás fajlagos költségei az átrakási pontok között [Ft/t]: T1 0 816 352

T1 T2 T3

T2 816 0 1164

T3 352 1164 0

a malmok és az átrakási pontok között: T1 50 M M

M1 M2 M3

T2 M 40 M

T3 M M 48

az átrakási pontok és a kenyérgyárak között:

T1 T2 T3

K1 60 M M

K2 50 M M

K3 M 45 M

K4 M M 60

A malmok a malmokba, a kenyérgyárak a kenyérgyárakba közvetlen nem szállíthatnak. Kérdés: milyen szállítási program esetén lesz minimális az összes szállítási költség. A kétlépcsős szállítási feladatként megfogalmazott probléma disztribúciós tábláját és megoldását a 4.11. táblázatban közöljük. Amint látható, a szállítás elsőlépcsőjében a malmokból a vasúti terminálokra és a kenyérgyárakba szállíthatunk. A vasúti terminálok egya34


ránt lehetnek feladók és megrendelők, ezért a második lépcsőben a terminálokról szállítunk a kenyérgyárakba. A táblázatban magyarázatra egyedül a terminálok 3550 t kapacitása szorul. A terminálok különleges tulajdonságú pontok, mivel sem forrásuk, sem nyelésük nincs, és elvileg szállítóképességük a tényleges feladásokhoz és a megrendelésekhez viszonyítva végtelen nagy. A szállítási feladat természetéből fakadóan azonban a kapacitásukat felülről korlátozni kell. A legcélszerűbb felső korlátként az összes szállítás értékét megadni, ami a példában 3550 t. Ez az érték ugyanis lehetővé teszi, hogy akár az összes feladás áthaladjon egy átrakási ponton. A kihasználatlan terminálkapacitás a költségmátrix Ti-Tj partíciójának 0 elemein csapódik ki. 4.11. táblázat M1 M2 M3 T1 T2 T3 rj

T1 50 M M 2500

0 700 816 350 352 3550

T2 M 700 40 M 816 2850 0 1164 3550

T3 M M 350 48 352 1164 3200 0 3550

K1 90200 1314 618 1050

60 M M 1250

K2 1000

60 1284 588 50 M M 1000

K3 1224 600 48 1746 M 45 M 600

K4 588 1746 700 30 M M 60 700

A megoldásból látható, hogy a K2 , K3 , K4 kenyérgyárak közúton, közvetlen a malmokból lesznek ellátva liszttel. A K1 kenyérgyárba az M1 malomból közúton 200 t lisztet szállítunk. A hiányzó 1050 t-t az M2 és M3 malmok biztosítják. Ezek útja a következő: az M2 -ből a T2 terminálra 700 t, az M3-ból a T3 terminálra 350 t közúton érkezik, majd vasúton folytatja az útját a T1 terminálig, ahonnan ismét közúton szállítjuk a K1 kenyérgyárig. Az átrakási probléma a példában ismertetett szituációnál általánosabban is megfogalmazható úgy, hogy a feladatban valamennyi szállítási pont (feladó- és megrendelőhely egyaránt) lehet átrakási pont. Az átrakási pontok kapacitásainak felsőhatára ebben az esetben is egyenlőa ténylegesen mozgatott mennyiséggel, vagyis a tényleges feladások vagy megrendelések összegével. De mivel a feladók és a megrendelők is átrakási pontok, ezért a tényleges feladásokat és az igényeket egyaránt meg kell növelni az átrakási pontokra megadott kapacitáskorlát értékével. A kihasználatlan kapacitás az átrakási pontokon a költségmátrix főátlójának nulla elemeire kerül.

Objektumok optimális elhelyezése E feladat egyik változata az ún. lineáris elrendezési probléma, amelyben k=1,2,…,m számú korábban telepített objektumot (üzem, gép, berendezés, stb.) i=1,2,…,n számú új objektummal kell kiegészíteni. Az új objektumok j=1,2,…,n számú ismert koordinátájú helyre telepíthetők úgy, hogy egy helyre csak egy objektum és fordítva, egy objektum csak egy helyre kerülhet. A megoldáshoz ismert az új és a korábban telepített objektumok között egységnyi idő 35

fi 1200 1300 1050 3550 3550 3550


alatt szállítandó anyagmennyiség (Iik), az anyagáramlás intenzitásmátrixa, valamint a régi objektumok és a lehetséges új helyek közötti távolság (skj). (Vegyük észre, hogy ebben a feladatban az új objektumok között nincs anyagáramlás.) Kérdés: melyik objektumot, hova telepítsük ahhoz, hogy a rendszer egészére vonatkozóan az anyagmozgatási teljesítmény (Q) minimális legyen? A döntési változók (xij ) legyenek 0 és 1 értékűek. Ha az i-edik új objektumot a j-edik szabad helyre telepítjük, akkor xij =1, különben xij =0. A feladat feltételi egyenletei biztosítják, hogy egy helyre csak egy objektum és fordítva, egy objektum csak egy helyre kerüljön: n

x i1

ij

n

x

ij

1 ,

1 .

j1

A célfüggvény n

n

Q Qij xij min , i1 j1

ahol: Qij az i-edik új objektum által generált vagy elnyelt anyagmozgatási teljesítmény, ha az i-edik új objektumot a j-edik szabad helyre telepítjük. Feltételezve, hogy az anyagmozgatási költség arányos az anyagmozgatási teljesítménnyel, a költségmátrix elemeit (Qij ) a m

Qij I ik skj k 1

formulával számíthatjuk ki, ahol: Iik az anyagáram intenzitása az i-edik új és a k-adik régi objektum között [tömeg/idő], skj a k-adik régi és a j-edik új hely közötti távolság [távolság]. A feladat megoldása a fentiek alapján a hozzárendelési problémára vezethetővissza, és megoldható a magyar módszerrel. Egy mezőgazdasági nagyüzem a következőlétesítményekkel rendelkezik: RT1 karbantartó műhely, RT2 alkatrész raktár, RT3 magtár, RT4 tehenészeti telep, RT5 takarmány raktár. A termelési tevékenység bővítése miatt 4 új létesítményt kell telepíteni: UT1 szárító, UT2 takarmánykeverő, UT3 tejfeldolgozó, UT4.tejcsarnok. 36


Az új és a régi létesítmények közötti szállítási intenzitás (Iik) [t/év]: RT1

RT2

RT3

RT4

RT5

UT1

4

7

1200

20

400

UT2

3

4

800

90

200

UT3

5

3

0

1500

0

UT4

4

2

0

300

0

Az új létesítményeket 4 helyen (P j) lehet elhelyezni, de egy helyre csak egyet. A régi objektumok és a telepítésre kijelölt helyek egymáshoz viszonyított távolságai (skj) [km]: P1

P2

P3

P4

RT1

20

5

3

16

RT2

17

14

4

9

RT3

5

6

4

1

RT4

3

7

6

2

RT5

2

13

2

8

Jelöljük ki a létesítmények helyeit úgy, hogy az összes szállítási teljesítmény minimális legyen. Először a m

Qij I ik skj k 1

képletet használva, számítsuk ki a Qij költségmátrix elemeit (az Iik mátrix i-edik sorának elemeit szorozzuk a skj mátrix j-edik oszlopának elemeivel és a szorzatokat összegezzük): Q11=4*20+7*17+1200*5+20*3+400*2=7.059 Q12=4*5+7*14+1200*6+20*7+400*13=12.658 Q13=4*3+7*4+1200*4+20*6+400*2=5.760 Q14=4*16+7*9+1200*1+20*2+400*8=4.567 Q21=3*20+4*17+800*5+90*3+200*2=4.798 . Q44=4*16+2*9+0*1+300*2+0*8=682 Az eredményeket táblázatba foglalva a megoldandó hozzárendelési feladat: P1

P2

P3

P4

UT1

70599

12658

5760

4567

UT2

4798

8101

4165

2664

UT3

4651

10567

9027

3107

UT4

1014

2148

1820

682 37


A magyar módszerrel kapott megoldás x13=1, x 24=1, x31=1, x 42=1, azaz az UT1 szárítót a P 3 helyre, az UT 2 takarmánykeverőt P 4 helyre, UT 3 tejfeldolgozót a P1 helyre, és az UT4 tejcsarnokot a P2 helyre kell telepíteni. A célfüggvény értéke Q=15.223 tkm/év.

Nyereség maximalizálás Egy olajtársaság három olajkútjának (K1, K2, K3) termékét feldolgozatlanul nyersolajként (T1), illetve részben feldolgozott nehézolajként (T2) és teljesen feldolgozott finomított benzinként (T3) értékesítheti. A piacon mindhárom termékre szükség van, egy kút termékét azonban csak egyfajta feldolgozottsággal gazdaságos értékesíteni. Az egyes kutakból kitermelt, különböző feldolgozottságú termékek fajlagos előállítási és szállítási költségét Ft/kg-ban: T1

T2

T3

K1

25

50

100

K2

50

100

150

K3

50

75

200

A termékek eladási ára rendre 50, 100, 200 Ft/kg. Készítsünk optimális termelési tervet, amely a nyereséget maximalizálja. A feladatot hozzárendelési problémaként kezeljük. A nyereség mátrix az eladási árak és a költségek különbségeiből: T1

T2

T3

K1

25

50

100

K2

0

0

50

K3

0

25

0

Mivel a nyereség maximálása a cél a nyereség mátrix elemeit –1-gyel szorozzuk. T1

T2

T3

K1

25

50

100

K2

0

0

50

K3

0

25

0

Redukáljuk a mátrixot: T1

T2

T3

pi

K1

25

50

100

100

K2

0

0

50

50

K3

0

25

0

25 38


A sorredukció után: T1

T2

T3

K1

75

50

0

K2

50

50

0

K3

25

0

25

qj

25

0

0

Az összes redukció z0 = 150. Az oszlopredukció után kijelöljük a független 0 elemeket: T1

T2

T3

K1

50

50

0*

K2

25

50

0+

K3

0*

0+

25

A fedővonal rendszer megszerkesztése: T1

T2

T3

K1

50

50

0*



K2

25

50

0+



K3

0*

0+

25 

A legkisebb fedetlen elem,  =25, ezért a célfüggvény változása: z1= 150+25 = 125. Az értékét a fedetlen elemekből levonva és a kétszer fedettekhez hozzáadva, majd kijelölve a független 0 elemeket megkapjuk a feladat megoldását. T1

T2

T3

K1

25

25

0*

K2

0*

25

0+

K3

0+

0*

50

A megoldás szerint a K1 kútból kitermelt olajt finomított benzinként, K2 és a K3 kutakból kitermelt olajt nyersolajként, illetve részben feldolgozott nehézolajként értékesítjük, ekkor a nyereség 125 Ft/kg.

4.6. Ellenőrzőkérdések 1. Ismertesse a szállítási feladat feltételeit és célfüggvényét! 2. Ismertesse a tiltótarifa fogalmát, mutassa be néhány alkalmazását! 3. Egy szállítási feladaton mutassa be a Vogel-Korda-féle módszert! 39


4. Ismertesse a korlátozás és szétválasztás módszerét a szállítási feladat megoldására! 5. Ismertesse a disztribúciós és a szimplex módszer kapcsolatát! 6. Ismertesse a disztribúciós módszer algoritmusát! 7. Ismertesse a magyar módszer elméleti alapjait! 8. Mutassa be a magyar módszert egy hozzárendelési feladaton! 9. Alkalmazza a magyar módszert egy szállítási feladat megoldására! 10. Keressen többlépcsős szállítási feladat formájában leírható gyakorlati problémákat! 11. Ismertesse az átrakási probléma modelljét! 12. Mikor használható a lineáris elrendezési probléma modellje?

Jegyzetek, kérdések

40

A szállítási feladat klasszikus megfogalmazása a következő. Adott n számú F 1. mennyiségűhomogén termékkel rendelkeznek, valamint m számú R 1

Recommend Documents