S Z Á L L Í T Á S I F E L A D A T

Döntéselmélet SZÁLLÍTÁSI FELADAT

Szállítási feladat meghatározása 2

 Speciális lineáris programozási feladat.  Legyen adott 𝑚 telephely, amelyeken bizonyos fajta,

tetszés szerint osztható termékből 𝑎1 , 𝑎2 , … , 𝑎𝑚 mennyiséget tárolnak. Adott továbbá 𝑛 felvevőhely, amelyek 𝑏1 , 𝑏2 , … , 𝑏𝑛 mennyiséget igényelnek ebből a termékből.  Egységnyi terméknek az 𝑖-edik telephelyről a 𝑗-edik felvevőhelyre való szállítási költsége 𝑐𝑖𝑗 -vel legyen jelölve. Jelölje továbbá 𝑥𝑖𝑗 az 𝑖-edik telephelyről a 𝑗edik felvevőhelyre szállítandó – egyelőre ismeretlen – mennyiséget. 𝑖 = 1, 2, … , 𝑚, 𝑗 = 1, 2, … , 𝑛 Szikora Péter - Döntéselmélet - Szállítási feladat


 Feltesszük, hogy

𝑚

𝑛

𝑎𝑖 = 𝑖=1

𝑏𝑗 𝑗=1

azaz, hogy a tárolt áru összmennyisége megegyezik az igényelt áru összmennyiségével. Ez nem jelenti az általánosság megszorítását, hiszen vagy fiktív telephely, vagy fiktív felvevőhely beiktatásával mindig elérhető az előbbi egyenlőség. Olyan szállítást kell megvalósítanunk, amelynek során minden telephelyről minden árut elszállítanak, az egyes felvevőhelyek igényeit kielégítik, és ezt mind úgy teszik, hogy az összszállítási költség minimális. Szikora Péter - Döntéselmélet - Szállítási feladat


 A szállítási problémát matematikailag a

következőképpen fogalmazhatjuk meg: Legyen adott egy 𝑐11 𝑐1𝑗 𝑐1𝑛 𝐶 = 𝑐𝑖1 𝑐𝑖𝑗 𝑐𝑖𝑛 𝑐𝑚1 𝑐𝑚𝑗 𝑐𝑚𝑛 𝑚 × 𝑛-es mátrix, a költségmátrix. Legyenek továbbá adva az 𝑎1 ≥ 0, … , 𝑎𝑚 ≥ 0( tárolt mennyiségek) illetve 𝑏1 ≥ 0, … , 𝑏𝑚 ≥ 0( igényelt mennyiségek) Szikora Péter - Döntéselmélet - Szállítási feladat


melyekre a

𝑚

𝑛

𝑎𝑖 = 𝑖=1

𝑏𝑗 𝑗=1

teljesül. Meghatározandók az olyan 𝑥𝑖𝑗 mennyiségek, amelyek eleget tesznek a 𝑛 𝑗=1 𝑥𝑖𝑗 = 𝑎𝑖 , 𝑖 = 1, 2, … , 𝑚 𝑚 𝑖=1 𝑥𝑖𝑗

= 𝑏𝑗 , j = 1, 2, … , 𝑛

𝑥𝑖𝑗 ≥ 0 , 𝑖 = 1, 2, … , 𝑚, 𝑗 = 1, 2, … , 𝑛

feltételeknek, Szikora Péter - Döntéselmélet - Szállítási feladat


s amelyekkel a

𝑚

𝑛

𝑐𝑖𝑗 𝑥𝑖𝑗 𝑖=1

𝑗=1

költségfüggvény felveszi a minimumát. A szállítási probléma egy minimum lineáris programozási feladat.

Szikora Péter - Döntéselmélet - Szállítási feladat

Megoldási módszer 7

 Szimplex módszer  m*n változós speciális termelésprogramozási feladat. (hosszadalmas, nehézkes) – lásd lineáris programozás általános esete.

 Disztribúciós módszer  induló megoldás meghatározása után optimalizálás


Disztribúciós módszer 8

Induló program készítése 2. Értékelés, hogy optimális-e (a hurok módszerrel) 3. A program javítása, ha még nem optimális. (Ismétlés addig, amíg nem az) 4. Módosítás megváltozott feltételeknek megfelelően. 1.

(Ahol szállítunk azt kötött elemnek, ahol nem szállítunk azt szabad elemnek hívjuk. A kötött elemek száma megegyezik a sorok+oszlopok száma-1-el.) Szikora Péter - Döntéselmélet - Szállítási feladat

Példa 9

 4 gabonaraktárból 5 malomba akarnak összesen 200

tonnát elszállítani a lehető legkisebb összköltséggel.  Raktári készletek: 40, 70, 60, 30, igények: 30, 60, 50, 40, 20 tonna.  Egységnyi költségek a raktárak és malmok viszonyában a

mellékelt ún. „Költség-mátrix” elemei szerint (eFt-ban):

 6 2 8 7 5 4 3 7 5 9    2 1 3 6 4    5 6 4 8 3  Szikora Péter - Döntéselmélet - Szállítási feladat

Északnyugati sarok módszer 10

 Északnyugati sarok módszer  Az adott eljárás nem használja a megoldandó feladathoz tartozó C = ||cij||m × n költség mátrixot.  Legkisebb költségű helyek választása

 Frekvenciák módszere  Vogel-Korda módszer



 Az igények kielégítését a táblázat bal felső sarkából

kezdjük

f1 f2 f3 f4

r1 6 4 2 5 30

r2 2 3 1 6 60

r3 8 7 3 4 50

r4 7 5 6 8 40

r5 5 9 4 3 20

40 70 60 30 200

 Majd, ha az első sort elszállítottuk, akkor folytatjuk a

következő sorokkal.




kezdjük

f1 f2 f3 f4

r1 630 4 2 5 30

r2 210 350 1 6 60

r3 8 720 330 4 50

r4 7 5 630 810 40

r5 5 9 4 320 20

40 70 60 30 200

 A szállítási költség a következő lesz:

6*30+2*10+3*50+7*20+3*30+6*30+8*10+3*20 = = 900 eFT


Legkisebb költségű helyek választása 13

 Az igények kielégítését a táblázat legkisebb elemével

kezdjük

f1 f2 f3 f4

r1 6 4 2 5 30

r2 2 3 1 6 60

r3 8 7 3 4 50

r4 7 5 6 8 40

r5 5 9 4 3 20

40 70 60 30 200

 Fontos, hogy nem ürülhet ki egy lépésben egyszerre feladóhely és

rendeltetési hely (kivéve az utolsó lépés), így, ha ilyen eset adódna, akkor a következő elemet kell választani.  Ha egy sor (oszlop) kiürült, akkor az adott opszlopban (sorban) kell a következő legkisebb költségű helyen szállítani.


Legkisebb költségű helyek választása 14


kezdjük

f1 f2 f3 f4

r1 6 4 230 5 30

r2 240 3 120 6 60

r3 8 710 310 430 50

r4 7 540 6 8 40

r5 5 920 4 3 20

40 70 60 30 200


2*40+7*10+5*40+9*20+2*30+1*20+3*10+4*30 = = 760 eFT


Frekvenciák módszere 15

 A feladat megoldásához először egy új táblát kell

alkotni.

f1 f2 f3 f4

r1 6 4 2 5 30

r2 2 3 1 6 60

r3 8 7 3 4 50

r4 7 5 6 8 40

r5 5 9 4 3 20

40 70 60 30 200

Az eredeti költségmátrixot sorok illetve oszlopok szerint a sorokban lévő költségelemek, illetve az oszlopokban lévő költségelemek átlagával redukáljuk. Meg kell keresni a legkisebb számot a táblázatban, és ott kell elkezdeni a programozást. Ezt a módszert közelítő módszerként használjuk. Jó induló programot ad, közel esik az optimumhoz. Szikora Péter - Döntéselmélet - Szállítási feladat


 Az igények kielégítését a táblázat legkisebb elemével

kezdjük

f1 f2 f3 f4

r1 -3,85 -5,855 -5,45-4,45 30


r2 -6,604 -5,607 -5,208 -2,20 60

r3 -3,10 -4,10 -5,706 -6,703 50

r4 -5,10 -7,102 -3,70 -3,70 40

r5 -5,85-1,85 -4,45 -7,451 20

40 70 60 30 200



kezdjük

f1 f2 f3 f4

r1 6 430 2 5 30

r2 240 30 120 6 60

r3 8 7 340 410 50

r4 7 540 6 8 40

r5 5 9 4 320 20

40 70 60 30 200


2*40+4*30+3*0+5*40+1*20+3*40+4*10+3*20 = = 640 eFT


Vogel-Korda módszer 18

 A feladat megoldásához először egy új táblát kell

alkotni.

f1 f2 f3 f4

r1 6 4 2 5 30

r2 2 3 1 6 60

r3 8 7 3 4 50

r4 7 5 6 8 40

r5 5 9 4 3 20

40 70 60 30 200

Az eredeti költségmátrixot sor majd utána oszlop minimumok segítségével redukáljuk. A következő lépésben minden sorhoz és oszlophoz a két legkisebb elem meghatározásával különbségeket képzünk.



 Az igények kielégítését a legnagyobb differenciánál

kezdjük

f1 f2 f3 f4 diff

r1 3 0 0 1 30 0

r2 0 0 0 3 60 0

r3 5 3 1 0 50 1

r4 3 0 3 3 40 3

r5 3 6 3 0 20 3

40 70 60 30 200

 Ha több van, akkor mindegy melyikkel indulunk.


diff 3 0 0 0



kezdjük

f1 f2 f3 f4

r1 6 430 2 5 30

r2 240 3 120 6 60

r3 8 7 340 410 50

r4 7 540 6 8 40

r5 5 9 4 320 20

40 70 60 30 200


2*40+4*30+5*40+1*20+3*40+4*10+3*20 = = 640 eFT


Induló program javítás 21

 Hurok módszer Akkor kell javítani, ha a hurokérték < 0, azaz ij < 0. Ha megtaláltuk, hogy hol javítunk  a szabad elemet programunkba vonjuk. Szabad elem mindig + sarok, utána váltakoznak! Hogyan döntjük el, hogy mennyit lehet szállítani?  A – sarkokon lévő mennyiség dönti el, hogy mekkora mennyiséget lehet mozgatni. A minimálist kell választani, ezt lehet átpakolni. A hurkon belül a – sarokból levonni, a + sarokhoz hozzáadni. Minden szabad elemre el kell végezni! Egészen addig, míg nem jutunk el az optimumba


Hurok módszer 22

 Vizsgáljuk meg az egyik induló program feladatát: f1 f2 f3 f4

r1 630 4 2 5 30

r2 210 350 1 6 60

r3 8 720 330 4 50

r4 7 5 630 810 40

r5 5 9 4 320 20

40 70 60 30 200

 Minden szabad elemhez fel lehet írni egy hurkot,

ahol a hurkot úgy kell meghatározni, hogy csak kötött elemnél lehet fordulni. (Ha átmegyünk egy kötött elemen, és nem fordulunk, akkor az az elem nem lesz része a huroknak) Szikora Péter - Döntéselmélet - Szállítási feladat

Hurok módszer 23

 Vizsgáljuk meg az egyik induló program feladatát: f1 f2 f3 f4

r1 6 4 2 5 30

r2 2 3 1 6 60

r3 8 7 3 4 50

r4 7 5 6 8 40

r5 5 9 4 3 20

40 70 60 30 200

 Minden szabad elemhez fel lehet írni egy hurkot,

ahol a hurkot úgy kell meghatározni, hogy csak kötött elemnél lehet fordulni. (Ha átmegyünk egy kötött elemen, és nem fordulunk, akkor az az elem nem lesz része a huroknak) Szikora Péter - Döntéselmélet - Szállítási feladat

Hurok módszer 24

 Határozzuk meg az első hurkot. f1 f2 f3 f4

r1 6 4 2 5 30

r2 2 3 1 6 60

 8 szabad elemhez: +8-7+3-2=+2  7 szabad elemhez:+7-6+3-7+3-2=-2

r3 8 7 3 4 50

r4 7 5 6 8 40

-2

+8

+3

-7

40 70 60 30 200

+7

-2 +3

r5 5 9 4 3 20

-7 +3

-6

Minden további elemhez hasonlóan lehet meghatározni a hurkokat Ha találtunk negatív hurkot akkor az alkalmazható a feladatra. Szikora Péter - Döntéselmélet - Szállítási feladat

Hurok módszer 25

 Táblázat a hurok eredményekkel: f1 f2 f3 f4

r1 6

30


r2 2 3

60

r3 + 7 3 50

r4 6 8 40

r5

3 20

40 70 60 30 200

Hurok módszer 26

+7

-210

Alkalmazzuk a negatív(-2) értékű hurkot: +350 -720 A negatívval jelölt kötött elemeken a +330 -630 legkisebb szállított mennyiség: {10,20,30}  10, tehát ezt a mennyiséget lehet szállítani a szab elemen. Minden + jelölésű elemhez hozzáadjuk, minden - jelölésből levonjuk. -2 +710 A költségünk 2*10 egységgel fog csökkeni. + 60 - 10

3

7

+340 -620


Hurok módszer 27

 Javítás alkalmazása: f1 f2 f3 f4

r1 630 4 2 5 30

r2 2 360 1 6 60

r3 8 710 340 4 50

r4 710 5 620 810 40

r5 5 9 4 320 20

40 70 60 30 200


6*30+7*10+3*60+7*10+3*40+6*20+8*10+3*20 = = 800 eFT Az új táblázathoz is kell hurkokat keresni, amíg csak + vagy 0 értékű hurkok lesznek csak. Szikora Péter - Döntéselmélet - Szállítási feladat

S Z Á L L Í T Á S I F E L A D A T

Recommend Documents