1
Operációkutatás NYME KTK, gazdálkodás szak, levelez˝o alapképzés 2002/2003. tanév, II. évf. 2.félév El˝oadó: Dr. Takách Géza NyME FMK Információ Technológia Tanszék 9400 Sopron, Bajcsy Zs. u. 9. GT fszt. 3. (99) 518 640 (30) 5600 785
[email protected] http://titanic.nyme.hu/˜takach
4. konzultáció: Szállítási feladat Mintafeladat. Két raktárban (feladóhelyek) rendre 20 illetve 25 raklap áru van, ezeket kell elszállítani három üzletbe (rendeltetési helyek), amelyek rendre 10, 20 illetve 15 raklap áruratartanak igényt. A szállítási költségek táblázata: F1 F2
R1 2 4 10
R2 3 1 20
R3 5 2 15
20 25 45
Hogyan szervezzük a szállítást, hogy minimális legyen a szállítási összköltség? Visszavezetés a hozzárendelési feladatra. oszlop, stb.
Ez egy 45 × 45-ös hozzárendelési feladat, F1 -nek 25 sor felel meg, R1 -nek 10
A feladat LP modellje F1 F2
A költségek és kapacitások:
A szállított mennyiségek:
F1 F2
R1 2 4 10 R1 x11 x21 10
R2 3 1 20 R2 x12 x22 20
R3 5 2 15
20 25 45
R3 x13 x23 15
20 25 45
Az LP model: x11
+
x12
+
x13
x11
+
x21 x21
x12 2x11
+
3x12
+ x22
+
x23
+ x22 +
x13 5x13
+ 4x21
+ x22
+ x23 + 2x23
= 20 = 25 = 10 = 20 = 15 → min
2
LP modell általánosan
Adott m feladóhely: F1 , . . . , Fm , és n rendeltetési hely: R1 , . . . , Rn . Az i-edik feladóhelyen fi mennyiség˝u homogén áru áll rendelkezésre, ezeket kell elszállítani a rendeltetési helyekre. A j-edik rendeltetési hely rj árumennyiséget igényel. Feltételezzük, hogy a készletek és az igények összhangban vannak, azaz m X
fi =
n X
i=1
rj .
j=1
Jelölje cij az egységnyi áru szállítási költségét az i-edik feladóhelyr˝ol a j-edik rendeltetési helyre történ˝o szállításkor: F1 F2 .. .
R1 c11 c21 .. .
R2 c12 c22 .. .
. . . Rn . . . c1n . . . c2n .. .
Fm
cm1
cm2
. . . cmn
Jelölje xij az i-edik feladóhelyr˝ol a j-edik rendeltetési helyre szállítandó árumennyiséget: F1 F2 .. . Fm
R1 x11 x21 .. .
R2 x12 x22 .. .
. . . Rn . . . x1n . . . x2n .. .
xm1 r1
xm2 r2
. . . xmn . . . rn
f1 f2 .. . fm
A következ˝o feltételek azt fejezik ki, hogy a feladóhelyekr˝ol minden árut el kell szállítani, és a rendeltetési helyek igényét ki kell elégíteni: m X i=1 n X
xij
= Rj
(j = 1, . . . , n)
xij
= Fi
(i = 1, . . . , m)
xij
≥ 0
j=1
(i = 1, . . . , m; j = 1, . . . , n)
A célfüggvény, aminek a minimumát keressük, K=
n X n X
cij xij → min .
i=m j=1
Ez egy lineáris programozási feladat: mn változó, m + n feltétel. A mátrixos alak feleslegesen sok nullát tartalmaz, hiszen egy egyenl˝otlenségben m vagy n 1-es szerepel, a többi elem nulla. Ezért célszer˝ubb a bázistáblánál tömörebb írásmód használata: disztribúciós táblázat. Ez nem jelent mást, mint hogy a költségmátrixban bekeretezzük azon viszonylatoknak megfelel˝o elemeket, ahol szállítunk és azt is melléírjuk, hogy abban a viszonylatban mennyit szállítunk. Tétel. Ha feladóhelyek száma m arendeltetési helyek száma n, akkor az (m + n) × (mn)-es együtthatómátrix rangja m + n − 1. Bizonyítás. Könyvben (2.1. Tétel). Tétel. A szállítási feladatnak mindig van lehetséges megoldása. Bizonyítás. A bizonyításban módszert is adunk egy lehetséges megoldás megkeresésére. (Disztribúciós módszer)
3
Disztribúciós módszer A mintafeladaton: R1
R2
10
F1 F2
2 4 10 0
R1 2
F2
4 10 0
3 1 20
R2
10
F1
R3
3 20
1 20 0
5 2 15
R1 20 10 25 45
10
F1 F2
2 4 10 0
R1
R3 5
10
2 15 5
20 10 0 25 5 45
F1 F2
2
10
4 10 0
R2
R3
3 1 20
5 2 15 5
10
R2
20 10 0 25 45 R3
3
5
20
1 20 0
10 5
2 15 5 0
20 10 0 25 5 0 45
Disztribúciós módszer Válasszuk ki a C költségmátrix egy cij elemét, s legyen xij = min(fi , rj ). A cij elemet bekeretezzük, fölé írva xij értékét. Ha fi < rj , azaz xij = fi , akkor az Fi készlete kiürült, míg Rj igénye xij -vel csökkent. Ennek megfelel˝oen az i-edik sort töröljük, rj -t pedig rj − fi -re változtatjuk. Ha rj < fi , azaz xij = rj , akkor az Rj igényeit kielégítettük, míg Fi készlete xij -vel csökkent. Ennek megfelel˝oen az j-edik oszlopot töröljük, fi -t pedig fi − rj -re változtatjuk. Ha fi = rj : degeneráció, ld. kés˝obb. Ezt ismételgetve m + n − 2 lépés után egyetlen sor és oszlop marad, amit már egyszerre törölhetünk. Tehát mindig m + n − 1 viszonylatban fogunk szállítani. Azon cij ket, ahol szállítunk, kötött elemeknek, a többit szabad elemeknek nevezzük. Megjegyzés. Belátható (kell is, ld. 2.2. Tétel a könyvben), hogy az így kapott megoldás bázismegoldása a szállítási feladathoz tartozó LP feladatnak.
Optimum létezése Tétel. A szállítási feladat célfüggvénye korlátos a lehetséges megoldások halmazán. Pn Bizonyítás. Mivel j=1 xij = fi (i = 1, . . . , n), ezért X X n n n X n X |K| = cij xij ≤ |cij |xij ≤ i=m j=1 i=m j=1 n n n n X X X X max |cij |xij = max |cij | xij = ≤ i=m
=
n X i=m
j=1
j
i=m
j
j=1
max |cij |fi , j
és ez már konstans. Megjegyzés. A könyvbeli bizonyításban durvább becslés szerepel.
♦
4
Optimális-e az aktuális program? A mintafeladat LP modellje: x11
+
x12
+
x13
x11
x21 x21
+
+ x22
x12 2x11
+
3x12
+
x23
+ x22 +
x13 5x13
+ 4x21
+ x23 + 2x23
+ x22
= 20 = 25 = 10 = 20 = 15 → min
Duálisának feltételrendszere: ui + vj ≤ cij
(i = 1, . . . , m; j = 1, . . . , n),
ahol az ui -k a sorokhoz, vj -k az oszlopokhoz tartozó változók. Ismert, hogy ezek el˝ojelkötetlen változók, mert egyenleteknek felelnek meg. A feltételrendszer eltérésvektorokkal: ui + vj + δij = cij
(i = 1, . . . , m; j = 1, . . . , n),
ahol δij ≥ 0. A duál feladat eltérésvektorának azon komponensei nullák lesznek, amelyeknek megfelel˝o primál változók a programban vannak, azaz ha xij kötött elem, akkor δij = 0, azaz ui + vj = cij .
Módszer. 1. Adjunk meg olyan ui és vj elemeket, hogy a költségmátrix kötött cij elemeire ui + vj = cij teljesüljön. Ebben az egyenletrendszerben van egy szabad változó, így egy ismeretlen értéke szabadon választható. Szokásosan: u1 = 0. 2. Képezzük azt a ∆ mátrixot, amelynek elemei δij = cij − ui − vj . Nyilvánvalóan δij = 0 a kötött elemeknél. 3. Ha minden δij ≥ 0, akkor a duál feladat egy lehetséges megoldásáról van szó, ami azt jelenti, hogy a primál feladat aktuális megoldása, tehát az aktuális szállítási program optimális. Ha nem → JAVÍTÁS. Mintafeladat. ui -k és vj -k meghatározása: v1 = 2 u1 = 0 u2 = −3
2
10
4
v2 = 4 v3 = 5 3 1
20
5 2
10 5
∆ meghatározása: δ11 = c11 − u1 − v1 = 2 − 0 − 2 = 0 δ12 = c12 − u1 − v2 = 3 − 0 − 4 = −1 .. . A −1 elem mutatja, hogy az aktuális megoldás nem optimális.
" ∆=
0 −1 5 0
0 0
# ,
5
Hurkok
Definíció. Huroknak nevezzük a költségmátrix elemeinek olyan sorozatát, ahol a szomszédos elemek felváltva vannak egy sorban ill. egy oszlopban (az utolsó elem szomszédosnak számít az els˝ovel), továbbá egyik sorban és oszlopban sincs kett˝onél több kiválasztott elem. Tétel. Bármely hurok elemeihez tartozó aij vektorok lineárisan függ˝o rendszert alkotnak. Ha egy vektort elghagyunk közülük, akkor lineárisan független rendszert kapunk. Bizonyítás. Nem kell. Tétel. Ha egy m × n-es disztribúció táblázatban m + n − 1 kötött elem van, akkor minden szabad elemet pontosan egy olyan hurok tartalmaz, melynek összes többi eleme kötött Bizonyítás. Nem kell.
A program javítása A javítás menete: 1. Válasszunk egy negatív δij -t. A költségmátrix ennek megfelel˝o szabad eleméb˝ol kötött elem lesz. 2. Keressük meg a megfelel˝o hurkot. 3. A hurok mentén felváltva növeljük ill. csökkentsük szállítandó mennyiséget (az új kötött elemen növeljük!). A növelés/csökkentés mértékét a legkisebb csökkentend˝o mennyiség adja (negatívba nem mehet át!); ez az átalakítás után szabad elem lesz
"
0 −1 5 0
A mintapéldán: ∆ =
0 0
#
2
10
3 |
4
1
−
5
10
|
20
−
2
5
A 3 és a 2 költségen szállított mennyiség n˝o, az 1 és az 5 költségen szállított csökken. A sz˝uk keresztmetszetet az jelenti, hogy az 5 költség˝u viszonylatban 10-nél többel nem lehet csökkenteni. Ez az elem tehát kikerül a programból: 2 0 −2
2 4
3 10
4 1
3 0 1
10
" ∆=
5 2
15
0 4
OPTIMUM!!!
Disztribúciós módszer (összefoglalás) 1. Indulóprogram meghatározása 2. ui -k és vj -k meghatározása a kötött elemek segítségével. 3. A ∆ mátrix meghatározása az ui -k és vj -k segítségével. 4. Ha ∆-nak nincs negatív eleme, akkor a jelenlegi program optimális. STOP 5. Ha ∆-nak van negatív eleme, akkor a. Keresünk egy hurkot a költségmátrix megfelel˝o elemén át. b. A hurok mentén javítjuk a programot, majd GOTO 2.
0 0
1 0
#
Redukálás
6
Tétel. Ha a költségmátrix egy sorának vagy oszlopának minden eleméhez ugyanazt a számot adjuk, vagy abból ugyanazt a számot kivonjuk, ekvivalens feladatot kapunk. Ugyanott lesz az optimum, csak értéke lesz más. Bizonyítás. Ha az i-edik sorból kivonunk c-t, akkor a célfüggvény értéke minden programban cfi -vel csökken, ami független a programtól. ♦
Módszer az indulóprogram meghatározására A fenti módszerben tetsz˝oleges volt a költségmátrix elemeinek kiválsztása azokból a sorokból és oszlopokból, amiket még nem húztunk ki. Szeretnénk úgy választani, hogy már az indulóprogram is minél közelebb legyen az optimumhoz. Mohó módszer: mindig a legkisebb költségen szállítunk. Ez nem vált be! Vogel-Korda-módszer: mindig arra az elemre programozunk, amelyre ha nem programoznánk, rossz költségalakulást jelentene. Minden sorra és oszlopra meghatározzuk a legkisebb és a második legkisebb elem különbségét (0 is lehet!), és ahol ez a legnagyobb, arra a minimális elemre programozunk.
Rendkívüli esetek. Degeneráció az indulóprogramban. El˝ofordulhat, hogy az indulóprogram meghatározásakor egy elem sorának és oszlopának aktuális kapacitása megegyezik. Ilyenkor csak a sorát vagy az oszlopát húzzuk ki, a másik kapacitása nulla lesz. Ilyenkor biztosan szükség lesz egy olyan viszonylat kiválasztására, amelyben nulla mennyiség˝u árut szállítunk. Degeneráció menet közben. El˝ofordulhat, hogy egy javításkor egy hurokban több helyen is megjelenik a sz˝uk keresztmetszet. Fontos viszont, hogy ilyenkor csak az egyiket vegyük ki a programból, a másikat hagyjuk benne nulla szállított áruval. Mindkét el˝oz˝o esetben el˝ofordulhat, hogy az optimális megoldás már nem lesz degenerált, de az is lehet, hogy az marad. Alternatív optimum. Ha a ∆ mátrixban nincs negatív elem, de szabad elemnek megfelel˝o helyen is van benne nulla, akkor a duál feladat degenerált, azaz a primál szállítási feladatnak altaernatív optimuma van. Ezt úgy lehet megtalálni, ha a "javítást" ennél a szabad elemnél végezzük el. Eltér˝o kereslet és kínálat. Ha pl. nagyobb a kereslet, mint a kínálat, akkor egy névleges feladóhelyet iktatunk be, akkora kapacitással, minta amekkora a túlkereslet. Azokat az igényeket, amiket innen kellene kielégíteni az optimális megoldásban, nem elégítjük ki. Tiltott viszonylatok. Ha egy feladóhely és egy rendeltetési hely között tilos a szállítás, akkor oda végtelen költséget kell írni. Ilyenkor szokás szerint ∞ − c = ∞. Korlátozott útvonal. El˝ofordulhat, hogy egy viszonylatban szállíthatunk ugyan, de csak korlátozott mennyiségben. ld. 2.9. Példa illetve 2.7. Tétel.
