2003. tanév, II. évf. 2

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) 509 7361 [email protected] http://titanic.nyme.hu/˜takach

1. konzultációs hét Gráfelmélet • Alapfogalmak • Euler-vonal • Hamilton-kör • Legrövidebb út

Algoritmusok!

• Minimális feszít˝ofa • Hozzárendelési feladat • Folyamprobléma Széls˝oértékszámítás!!!

Irodalom F. S. Hillier és G. J. Lieberman. Bevezetés az operációkutatásba. LSI Oktatóközpont, Budapest, 1994. Szükséges részek: 10. fejezet, azaz 237–247, 258–261 oldal.

A többi anyagrészhez: ld. tantárgy honlapja

A gráf definíciója 1.. DEFINÍCIÓ. Legyen V egy véges halmaz, E pedig V -beli rendezetlen elempárok véges rendszere. Ekkor a G=(V, E) párt gráfnak nevezzük. V elemei a gráf csúcsai, E elemei a gráf élei. Ha e = (v1 , v2 ) egy él, akkor azt mondjuk, hogy az e él a v1 és a v2 csúcsokat köti össze.

2

Egy labdarúgó tornán 6 csapat vesz részt. Ez a gráf azt írja le, hogy mely csapatok mérk˝oztek meg egymással az els˝o négy fordulóban. V = {A, B, C, D, E, F } E = {(A, B), (A, C), (A, D), (A, F ), (B, C), (B, E), (B, F ), (C, D), (C, E), (D, E), (D, F ), (E, F )}

Rendezetlen elempáron azt értjük, hogy nem teszünk különbséget a (v1 , v2 ) és a (v2 , v1 ) pár között, a rendszer pedig abban különbözik a halmaztól, hogy egy elem többször is szerepelhet benne.

Gráfelméleti alapfogalmak

2.. DEFINÍCIÓ. Egy gráf egy csúcsa izolált csúcs, ha nem indul ki bel˝ole él. (W ) Többszörös élr˝ol beszélünk, ha két pontot több él köt össze.((Y, V ) ) A hurokél önmagába visszatér˝o él, azaz két végpontja azonos.((X, X)) Az üres gráf csupa izolált pontokból álló gráf, azaz E = ∅. Az egyszer˝u gráfok nem tartalmaznak sem hurokélet, sem többszörös élet.

Gráfelméleti alapfogalmak

3.. DEFINÍCIÓ. A teljes gráfok olyan egyszer˝u gráfok, amelyekben bármely két különböz˝o csúcs között vezet él. Kn : n csúcsú teljes gráf. ¯ gráf, amely teljes gráffá egészíti ki; tehát G és G ¯ csúcsai megegyeznek, továbbá két Egy G egyszer˝u gráf komplementere az a G ¯ csúcs között pontosan akkor vezet él G-ben, ha G-ben nem vezet él. A G1 = (V, E 0 ) gráf a G = (V, E) gráf részgráfja, ha E 0 ⊆ E; tehát G1 -et G-b˝ol néhány él elhagyásával kapjuk. A G1 és G2 gráfok izomorfak, ha létezik a csúcsok között olyan bijekció, hogy két G1 -beli csúcs között pontosan akkor vezet él, ha a megfelel˝o két G2 -beli csúcs is össze van kötve.

3

Síkgráfok 4.. DEFINÍCIÓ. Egy gráf síkgráf, ha lerajzolható úgy a síkba, hogy élei csak a szögpontokban metszik egymást.

G síkgráf, mert a vele izomorf H a síkba van rajzolva. Ha egy gráf lerajzolható a síkba, akkor lerajzolható úgy is, hogy minden éle egyenes szakasz legyen. (K)

Síkgráfok

K5 és K3,3 nem rajzolhatók le a síkba. Az is belátható, hogy ha egy gráf nem rajzolható síkba, akkor K5 vagy K3,3 valahol "benne van" a gráfban.

Fokszámok 5.. DEFINÍCIÓ. Egy csúcs fokszáma a bel˝ole kiinduló élek száma. Megjegyzés. Egy n-pontú teljes gráfban minden csúcs fokszáma n − 1, és összesen

n 2




élet tartalmaz.

6.. TÉTEL. Egy gráf páratlan fokú csúcsainak száma páros. Bizonyítás. Felhasználjuk az alábbi segédtételt. 7.. SEGÉDTÉTEL. Egy gráf csúcsai fokszámainak összege megegyezik az élek számának kétszeresével. Ezek után a tétel bizonyítása a következ˝o: Jelölje a gráf csúcsait A1 , . . . An , a megfelel˝o fokszámokat ρ(A1 ), . . . , ρ(An ). Tegyük fel, hogy ρ(A1 ), . . . , ρ(Ak ) páratlan számok, ρ(Ak+1 ), . . . , ρ(An ) párosak. A segédtétel szerint ρ(A1 ) + . . . + ρ(An ) páros, így páros számokat elhagyva ρ(A1 ) + . . . + ρ(Ak ) is páros lesz. Páratlan számok összege pedig csak akkor lehet páros, ha páros sok van bel˝olük.

♦

Fokszámok

4

8.. TÉTEL. Legyen G egy n-csúcsú egyszer˝u gráf, n ≥ 2. Ekkor van legalább két olyan csúcs, melyek fokszáma megegyezik. Bizonyítás. Minden egyes csúcs fokszáma 0, 1, . . . , n − 1 lehet, vagyis n-féle. Egy 0-fokú csúcs izolált csúcs, egy (n − 1)-fokú pedig minden másik csúccsal össze van kötve. Tehát nem lehet a gráfban egyszerre 0-fokú és (n−1)-fokú csúcs is, vagyis csak (n−1) féle lehet a fokszám. Ekkor a skatulya-elv szerint van két azonos fokszámú csúcs. ♦

Gráfok bejárása

5

9.. DEFINÍCIÓ. Sétán két csúcsot összeköt˝o élsorozatot értünk. Speciális séták: • vonal: olyan séta, melyben minden él legfeljebb egyszer szerepel (a csúcsok többször is szerepelhetnek). • zárt vonal: olyan vonal, melynek kezd˝o és végpontja azonos. • nyílt vonal: olyan vonal, melynek kezd˝o és végpontja különböz˝o. • út: minden csúcsot legfeljebb egyszer érint˝o séta. • kör: olyan séta, melynek a kezd˝o és végpontja azonos, a többi csúcsot legfeljebb egyszer érinti. 10.. DEFINÍCIÓ. Egy gráf összefügg˝o, ha bármely két csúcs között vezet út.

Königsbergi hidak Eulert˝ol megkérdezték Königsberg lakói, hogy miért nem tudnak átmenni a város hídjain úgy, hogy mindegyiken pontosan egyszer mentek át:

Euler-vonal Melyik ábra (gráf) rajzolható le egy vonallal a ceruza felemelése nélkül?

6 A kukásautónak egy körzet minden utcáján végig kell mennie, és be kell gy˝ujteni a szemetet. Meg tudja-e ezt tenni úgy, hogy minden utcán csak egyszer megy végig?

Euler-vonal 11.. DEFINÍCIÓ. Euler-vonal: olyan vonal (séta), melyben minden él pontosan egyszer szerepel. Szükséges feltétel Euler-vonal létezésére: zárt Euler-vonal esetén minden pontba pont ugyanannyiszor megyünk be mint ki ⇒ minden pont foka páros. Belátható, hogy ez elegend˝o is! 12.. TÉTEL. Egy összefügg˝o gráfban pontosan akkor létezik zárt Euler-vonal, ha minden csúcs fokszáma páros. Egy összefügg˝o gráfban pontosan akkor létezik nyitott Euler-vonal az A csúcsból a B csúcsba, ha csak A és B fokszáma páratlan. Ha egy összefügg˝o gráfban a páratlan fokszámú csúcsok száma 2k, akkor a gráf k darab diszjunkt vonal egyesítése. ⊗

Algoritmusok "Algoritmus" zárt Euler-vonal keresésére: Tetsz˝oleges csúcsból kiindulva rajzolom fel a gráfot, ügyelve arra, hogy a le nem rajzolt rész összefügg˝o maradjon. "Algoritmus" nyílt Euler-vonal keresésére: Ugyanaz, mint a zártra, de a kiindulópont szükségszer˝uen az egyik páratlan fokú csúcs.

Utazó ügynök probléma Egy ügynöknek meg kell látogatnia bizonyos városokat útja során (és végül haza kell térnie). Adott: • mely városokból mely másik városokba van járat(közvetlen út) • milyen költséggel tud eljutni egyik városból másikba (repül˝ojegy, autóút ára).

7 Cél: az utak összköltségét minimalizálni. Ez a feladat sok alkalmazás során felmerül, és csak bizonyos speciális esetekben ismeretesek jó algoritmusok a megoldására. Ha bármely két város közt, melyek között van összeköttetés, az 1 költség˝u, és az ügynöknek minden várost meg kell látogatnia, akkor a feladat a Hamilton-kör létezésére vezet.

Hamilton-kör 13.. DEFINÍCIÓ. A Hamilton-kör olyan kör, amely minden csúcson átmegy (szükségszer˝uen pontosan egyszer). A Hamilton-kör létezésére nem ismert egyszer˝u szükséges és elégséges feltétel, s ugyancsak nincs gyors algoritmus sem Hamiltonkör keresésére. Elégséges, de nem szükséges feltétel Hamilton-kör létezésére: 14.. TÉTEL. Legyen G n-csúcsú egyszer˝u összefügg˝o gráf. Ha minden csúcs fokszáma legalább n/2, akkor a gráfban létezik Hamilton-kör. ⊗

Hamilton-kör Szükséges, de nem elégséges feltétel Hamilton-kör létezésére: 15.. TÉTEL. Ha egy G = (V, E) gráfban van Hamilton-kör, akkor bármely S ⊆ V ponthalmaz esetén S pontjait és a bel˝olük kiinduló csúcsokat elhagyva a maradék gráfnak legfeljebb annyi össefügg˝o komponense van, mint |S|. Másképpen: Ha egy G = (V, E) gráfban létezik olyan S ⊆ V ponthalmaz, hogy S pontjait és a bel˝olük kiinduló csúcsokat elhagyva a maradék gráfnak |S|-nál több össefügg˝o komponense van, akkor a gráfban nincs Hamilton-kör.

Legrövidebb út keresése Alapfeladat: Adott egy összefügg˝o gráf, egy kezd˝o- és egy végs˝o csúcs, valamint az élekhez rendelt távolságok. Keressük a legrövidebb utat a kezd˝o és a végs˝o csúcs között. Figyelem! Nem a felhasznált élek számát kell minimalizálni, hanem a hosszaik összegét. Átfogalmazások: Az elemekhez rendelt számok jelképezhetnek költségeket illetve id˝otartamokat is. Ilyenkor a minimális költség˝u illetve a legkevesebb id˝o alatt bejárható utat keressük.

Algoritmus. A gráf minden élére meghatározzuk a kezd˝oponttól oda vezet˝o legrövidebb utat. A kezd˝oponttól mért távolságok szerint növekv˝o sorrendben vesszük a pontokat. 1. iterációs lépés: Meghatározzuk a kezd˝oponthoz legközelebbi pontot. n. iterációs lépés: Meghatározzuk a kezd˝oponthoz n. legközelebbi pontot. Bemenet: A legközelebbi n−1 csúcs, beleértve a legrövidebb útvonalakat is. (Ezeket nevezzük megoldott pontoknak (beleértve a kezdeti pontot is), a többit megoldatlan pontnak mondjuk.) Jelöltek: minden megoldott ponthoz a legközelebbi megoldatlan pont (ha van ilyen). Döntés: minden jelöltre kiszámítjuk a jelöl˝o–kezd˝o távolság és a jelölt–jelöl˝o távolság összegét, és ezek közül a minimálisat választjuk. A jelöl˝o csúcsot is feljegyezzük. A legrövidebb út: Ha az iterációban elérek a végs˝o pontig, akkor készen vagyok. (Visszafejtés!)

8

n 1 2 4

5

6

Jelöl˝o O O A A B C A B E D E

Jelölt A C B D E E D D D T T

Távolság 2 4 2+2=4 2+7=9 4+3=7 4+4=8 2+7=9 4+4=8 7+1=8 8 + 5 = 13 7 + 7 = 14

Gy˝oztes A C B

Távolság 2 4 4

Összeköttetés OA OC AB

E

7

BE

D D T

8 8 13

BD ED DT

Visszafejtés Az összeköttetés oszlop tartalma: OA, OC, AB, BE, BD, ED, DT

Azaz OABEDT és OABDT a két legrövidebb út.

Fák 16.. DEFINÍCIÓ. Fának nevezzük az olyan összefügg˝o gráfokat, amikben nincs kör. A fák szükségszer˝uen egyszer˝u gráfok, hiszen a hurokél 1-hosszú kör, a többszörös él 2-hosszú kör.

9

Fák jellemzése 17.. TÉTEL. Legyen G egy n-csúcsú gráf. Ekkor a következ˝o állítások ekvivalensek 1. G fa; 2. G összefügg˝o és n − 1 éle van; 3. G összefügg˝o, de tetsz˝oleges élét elhegyva már nem lesz összefügg˝o. 4. G-ben nincs kör, de egy tetsz˝oleges új élet hozzávéve már lesz benne kör.

⊗

Feszít˝o fák 18.. DEFINÍCIÓ. Legyen G egyszer˝u, összefügg˝o gráf. Az F fa a G gráf feszít˝o fája, ha F olyan részgráfja G-nek, mely a G minden csúcsát és bizonyos éleit tartalmazza.

Minimális kifeszít˝o fa keresése Feladat: Adott egy n csúcsú, egyszer˝u összefügg˝o gráf, valamint az élekhez rendelt valós számok, amelyek az élek hosszai. Keressük azt a kifeszít˝o fát, amelyben az élek összhossza minimális. 1. ALGORITMUS (K RUSKAL - FÉLE MOHÓ ALGORITMUS ): • Rendezzük hosszuk szerint növekv˝o sorrendbe az éleket.

• Válasszunk ki sorban éleket, de olyan élet ne válasszunk ki, melynek kiválasztásával kör keletkezne.

10

• Az el˝oz˝o pontot ismételjük n − 1-szer. 2.

ALGORITMUS :

ld. [HL], 10.4. Ez szintén mohó algoritmus, de végig összefügg˝o részgráfot alkotnak a kiválasztott élek.

Páros gráfok

19.. DEFINÍCIÓ. Egy G = (V, E) gráfot páros gráfnak nevezünk, ha van olyan V = B ∪ J felbontás, hogy B ∩ J = ∅, továbbá minden él egyik végpontja B-ben, a másik J-ben van. Jelölése: G = (B, J; E). Vegyük észre, hogy ha B és J nem adott, akkor nem egyszer˝u feladat eldönteni, hogy a gráf páros-e.

Hozzárendelési feladat páros gráfokban

20.. DEFINÍCIÓ. A G = (B, J; E) páros gráf éleinek egy M halmaza lefedést (matching-et, független élrendszert, párosítást) alkot, ha nincs két olyan M -beli él, amelyeknek van közös végpontja. Egy csúcs lefedetlen az M élrendszerben, ha nem végpontja egyetlen M -beli élnek sem. Egy lefedés teljes lefedés, ha a gráf minden csúcsát lefedi. (Teljes lefedés csak akkor létezhet, ha |B| = |J| teljesül.)

Javító útak 21.. DEFINÍCIÓ. Adott egy M párosítás egy páros gráfban. Ha egy út felváltva tartalmaz M -hez tartozó és M -hez nem tartozó éleket, akkor alternáló útnak nevezzük. Egy alternáló út javító út (b˝ovít˝o út), ha mindkét végpontja lefedetlen csúcs.

11

Javító útak Vegyük észre, hogy ha U egy b˝ovít˝o út az M párosításra nézve, akkor az U 4 M eggyel nagyobb elemszámú párosítás, mint M . Tehát az alternáló út M -hez tartozó éleit M -b˝ol elhagyva, az M -hez nem tartozó éleit M -hez hozzávéve eggyel nagyobb elemszámú párosítást nyerünk.

22.. TÉTEL. Egy páros gráf M lefedése akkor és csak akkor maximális elemszámú független élrendszer, ha nem létezik b˝ovít˝o út a gráfban M -re nézve.

Matching-algoritmus Adott egy G = (B, J; E) páros gráf, valamint egy M kiindulási párosítás (amely esetleg üres is lehet). M -b˝ol kiindulva keresünk egy maximális elemszámú párosítást G-ben. • Ha nincs lefedetlen csúcs B-ben, akkor M maximális párosítás, STOP. Ha van, akkor folytassuk a következ˝o lépéssel. • Keressünk egy b˝ovít˝o utat, • Ha találunk b˝ovít˝o utat, akkor ennek segítségével b˝ovítsük M -et, és folytassuk az els˝o lépéssel. Ha nem találtunk b˝ovít˝o utat, akkor M maximális elemszámú párosítás.

Javító út keresése Kisebb gráfok esetén ránézésre, nagyobb méret esetén erre is van algoritmus: • Cimkézzünk meg minden B-beli lefedetlen csúcsot 0-val. • Minden egyes i ∈ B csúcsra és (i, j) ∈ / M élre cimkézzük meg a (J-beli) j csúcsot i-vel. • Minden egyes lefedett j ∈ J csúcsra cimkézzük meg a (B-beli) i csúcsot j-vel, ahol (i, j) ∈ M .

12

24.. TÉTEL. Egy páros gráfban tetsz˝oleges párosítás elemszáma kisebb vagy egyenl˝o tetsz˝oleges éllefogó ponthalmaz elemszámánál. Következésképpen ha |M | = |W | teljesül, akkor M maximális elemszámú párosítás, W pedig minimális elemszámú éllefogás.

Hálózatok Alapfeladat: Adott egy gráf, minden élének mindkét irányú kapacitása, valamint két kitüntetett csúcs: a forrás és a nyel˝o. Keresünk egy maximális érték˝u megengedett folyamot (áramlást).

Szemléltetésképpen feltehetjük, hogy a hálózattal egy olajvezetékrendszert ábrázolunk. A kapacitások a vezeték vastagságát jelentik, vagyis azt, hogy egységnyi id˝o alatt mennyi olaj folyhat át azon a vezetékdarabon. A kérdés az, hogy egy adott hálózaton mennyi olaj folyhat át s-b˝ol t-be. Szoktak beszélni úthálózatokról is, ahol a kapacitás az utak átereszt˝oképessége, és árukat kell eljuttatni a termel˝ot˝ol a fogyasztókhoz. De beszlélhetünk számítógéphálózatokról és adatátviteli sávszélességr˝ol is.

Folyamok

13 25.. DEFINÍCIÓ. Folyamon a hálózat minden egyes éléhez rendelt számot értünk, amely azt mutatja, hogy mekkora az élen átáramló anyag mennyisége. Meg kell adni az áramlás irányát is. (Irányított gráf!) Megengedett folyamnak nevezünk egy olyan folyamot, ahol a forrásból csak kifelé, a nyel˝obe csak befelé vezet áramlás, minden egyes egyéb csúcs esetén a kifolyó áramlások összege megegyezik a befolyók összegével, továbbá a egyik élen sem haladja meg az él kapacitását. 26.. DEFINÍCIÓ. Egy út kapacitásán a rajta lév˝o minimális élkapacitást értjük.

Algoritmus 1. Keresünk egy forrás→nyel˝o utat pozitív kapacitással (c). Ha nincs ilyen út, akkor a jelenlegi folyam maximális. STOP! 2. Növeljük a folyamot c-vel ezen az úton. 3. Csökkentsük ezen az úton c-vel a kapacitást minden élen. Növeljük az ellenkez˝o irányú úton a kapacitást c-vel minden élen. Folytassuk az 1. lépéssel.

Vágások Hogyan gy˝oz˝odhetünk meg egyszer˝uen arról, hogy egy folyam maximális, azaz hogy nem tudunk további áramlást indítani s-b˝ol t-be? 27.. DEFINÍCIÓ. Egy vágás irányított élek olyan halmaza, amelyek minden forrás→nyel˝o útból tartalmaz egy élet. Egy vágás értéke a hozzá tartozó élek kapacitásainak összege. 28.. TÉTEL. Minden megengedett folyam értéke kisebb minden vágás értékénél. S˝ot, a maximális folyamok(ok) értéke egyenl˝o a minimális vágás értékével. A tétel megkönnyíti az algoritmus 1. lépésében a döntést: ha úgy t˝unik, hogy nincs már pozitív kapacitású forrás→nyel˝o út, akkor megpróbálok keresni egy 0-érték˝u vágást. Ha van nulal érték˝u vágás, akkor biztos hogy nincs pozitív kapacitású forrás→nyel˝o út. Ha úgy t˝unik, hogy nincs nulal érték˝u vágás, akkor valószín˝uleg van pozitív kapacitású forrás→nyel˝o út...

Van-e Euler vonal az alábbi gráfban?

Minden csúcs foka 3 ⇓ Nincs!

Van-e Euler vonal az alábbi gráfban?

Minden csúcs foka páros ⇓ Van, méghozzá zárt!

KÉSZ!!!

Van-e Hamilton-kör az alábbi gráfban?

Igen, pedig a csúcsok foka = 3 < 8/2

Van-e Hamilton-kör az alábbi gráfban?

2 pont elvételével 3 komponensre esik Szét, tehát nincs Hamilton-kör!

Keressünk egy minimális feszítőfát! 7

A

B

13

11 C

8

5

D

12

12

3

3 F

E 10

9 2

G

H

n=8 csúcs esetén n-1=7 él kell ⇒ kész!

Keressünk egy maximális folyamot Aből G-be! 6

A5 4

0 B3 6 A

0C

0E 5 0 0

2 3

0 8 F 9 0

0D 5

0 0

G

0E 5

0

3 kapacitású út 3 B0

3 A

0 B3

G

3E 2 3

G

3 értékű folyamot indítunk. Az útvonalon módosítjuk a kapacitásokat.

0 B 3 3 A5 4 A 4

0C

0D

3E 2 0 0

2 3

3 0

0 8 F 9 0

5

0 F 9 0

0D 5 4 értékű folyamot indítunk. Az útvonalon módosítjuk a kapacitásokat.

G

G 4 kapacitású út

A 0

4 4D 1

F 5 4

G

0 B 3 3 A5 0

0C

4D

3E 2 0 0

2 3

2 értékű folyamot indítunk. Az útvonalon módosítjuk a kapacitásokat.

4

0 8 F 5 4

1

A5

3

0C

0

2

A3

G

E 2 3

2 kapacitású út

2C

0

2

G

E 0 5

G

0 B 3 3 A3 0

2C

4D A3

2C

0 3 1

3

3E 0 2 0 0 8 F 5 4

4

G

3 kapacitású út 0

3 értékű folyamot indítunk. Az A0 útvonalon módosítjuk a kapacitásokat.

5

4

G

F 5

5C

0 3

7 F 2

G

0 B 3 3 A0 0

5C

4D

0 0 1

3E 0 2 0 3 8 F 2 4

5 7

G

Látszólag nincs több pozitív kapacitású forrás-nyelő út. Keressünk egy nulla értékű vágást! Tehát az aktuális folyam maximális!

Mi az aktuális (s egyben maximális) folyam? Összaadhatnánk az indított áramlásokat, de egyszerűbb a kezdeti és az aktuális kapacitások különbségét tekinteni! 3 6 0 5 A 4 0

30 B

5

0C

30 20 3

0

4 0D51

3

0E 5 0 0 0 2 0

30 8 8 F 92 4 0

Ellenőrizzük a csomóponti törvényt, illetve a folyamértéket!

7

5

A folyam értéke: 12 3

B

3 A

5 0 G 0

E

2

5

C

G

3 F

4 D

4

7

Operációkutatás

1

NYME KTK, gazdálkodás szak, levelez® alapképzés 2002/2003. tanév, II. évf. 2.félév El®adó: 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) 509 7361 [email protected] http://titanic.nyme.hu/takach

Parciális függvény, parciális derivált (ismétlés) Deníció. Az f (x, y) kétváltozós függvény y = b-hez tartozó parciális függvénye az fx = fx (x) = f (x, b) egyváltozós függvény, az x = a-hoz tartozó parciális függvénye az fy = fy (y) = f (a, y) egyváltozós függvény. Tehát az egyik változót lerögzítjük.

Kétváltozós függvények grakonja egy felület: az értelmezési tartomány a sík , ill. a sík egy részhalmaza, és minden x, y ponthoz a felület (x, y, z) pontja tartozik, ahol z = f (x, y). A parciális függvény grakonja a felületb®l az y = b illetve x = a (függ®leges) síkok által kimetszett síkgörbe. függvénygrakon  domborzat, parciális függvény  út (Észak-Déli, illetve Kelet-Nyugati)

Deníció.

fy0 .

Egy kétváltozós függvény parciális deriváltjain a parciális függvények deriváltjait értjük. Jelölés: fx0 ill.

Mivel a parciális derivált függ attól is, hogy hogyan rögzítettük le a másik változót, szokás kétváltozós függvénynek is tekinteni. Pl. fx0 (1, 3) azt jelenti, hogy az f (x, 3) = fx függvényt deriváljuk, majd x = 3-at behelyettesítünk. A gyakorlatban azonban általánosan van szükségünk fx0 (x, y)-ra; ezt úgy kapjuk meg, ha y -t számnak képzeljük, és úgy deriválunk, mintha egyváltozós függvényr®l lenne szó, amely csak x-t®l függ.

A fenti g(x, y) = 2x2 y 3 + 3xy + 2x − 5y + 1-re gx0 (x, y) = 4xy 3 + 3y + 2.

2

Hasonlóan gy0 (x, y) = 6x2 y 2 + 3x − 5. Az egyváltozós esethez hasonlóan beszélhetünk magasabbrend¶ parciális deriváltakról. Itt azonban nem egy, hanem négy másodrend¶ parciális derivált van. Ha f (x, y)-t el®ször x szerint deriváljuk, majd y szerint, akkor kapjuk 00 00 fxy (x, y)-t, ha mindkétszer y szerint, akkor fyy (x, y)-t, stb. Ellen®rzési pont, hogy általában 00 00 fxy (x, y) = fyx (x, y)

.

Széls®értékszámítás Deníció. Az f függvénynek lokális

minimuma van az m ∈ M helyen, ha létezik m-nek olyan K környezete, hogy tetsz®leges x ∈ M ∩ K esetén f (x) > f (m). f -nek globális minimuma van az m ∈ M helyen, ha tetsz®leges x ∈ M esetén f (x) > f (m). A lokális és globális maximum fogalmát hasonlóképpen értelmezhetjük.

Tétel.

Legyen az (a, b) pont az f (x, y) függvény értelmezési tartományának egy bels® pontja. f (x, y)-nak széls®értéke van az (a, b) helyen, akkor els®rend¶ parciális deriváltjai az (a, b) helyen nullák, azaz fx0 (a, b) = fy0 (a, b) = 0. Ha az f (x, y) függvény els®rend¶ parciális deriváltjai az (a, b) helyen nullák, továbbá a másodrend¶ parciális deriváltakra

Ha

00 00 00 00 D(a, b) = fxx (a, b)fyy (a, b) − fxy (a, b)fyx (a, b) > 0,

akkor

00 00 (a, b) < 0. (a, b) > 0, és maximuma, ha fxx f -nek széls®értéke van az (a, b) helyen. Méghozzá minimuma, ha fxx

00 00 00 00 (a, b) > 0 feltétel azt fejezi ki, hogy a két parciális függvénynek ugyanolyan (a, b)fyx (a, b) − fxy (a, b)fyy A D(a, b) = fxx típusú széls®értéke legyen. Az olyan tulajdonságú pontot, ahol az egyik parciális függvénynek minimuma, a másiknak pedig maximuma van, nyeregpontnak nevezzük.

Ha az els®rend¶ parciális deriváltak nullák, de D(a, b) < 0, akkor biztosan nincs széls®érték, ha pedig D(a, b) = 0, akkor további vizsgálat szükséges.

3

Széls®érték korlátos zárt halmazon

Rögzítsünk egy M ⊂ Rn halmazt, továbbá egy olyan n-változós f függvényt, amely M minden pontjában értelmezve van és dierenciálható. (Nálunk n = 1 vagy n = 2 lesz.)

Tétel.

(Weierstrass) Ha

M korlátos és zárt, akkor f -nek van globális minimuma és maximuma M -en.

Tudjuk, hogy ha m a M értelmezési tartomány bels® pontja és f -nek lokális széls®értéke van m-ben, akkor f els®rend¶ parciális deriváltjai m-ben nullák (illetve f 0 (m) = 0 az egyváltozós esetben). Ez módot ad M azon bels® pontjainak meghatározására, ahol lokális széls®értékek lehetnek. A másodrend¶ deriváltak segítségével azt is megállapíthatjuk, hogy melyik helyen van minimum, maximum, ill. nincs széls®érték. Ha csak véges sok lokális széls®érték van, akkor a globális széls®érték nem más, mint a legnagyobb lokális széls®érték, tehát behelyettesítéssel eldönthetjük, hogy hol van globális széls®érték. Az értelmezési tartomány határán azonban széls®érték lehet akkor is, ha a derivált(ak) nem nulla. Például a [0, 1] zárt intervallumon értelmezett g(x) = 2x + 3 függvénynek lokális minimuma van a 0-ban, lokális maximuma az 1-ben.

Lemma.

Az [a, b] zárt intervallumon értelmezett g(x) egyváltozós függvénynek pontosan akkor van lokális minimuma a-ban, ha g 0 (a) > 0, b-ben pedig pontosan akkor, ha g 0 (b) < 0. Feladat.

Határozzuk meg az f (x) = x3 −6x2 −15x+3 függvény lokális és globális széls®értékeit a [-10, 6] intervallumon!

Deriválással megállapítható, hogy az x = −1 helyen maximum, az x = 5 helyen minimum van. Mivel f 0 (−10) > 0 és f 0 (6) > 0, ezért az x = −10 helyen minimum, az x = 6 helyen maximum van. Behelyettesítéssel meggy®z®dhetünk arról, hogy a globális széls®értékek az x = −10 és az x = −1 helyen vannak.

Megoldás.

Kétváltozós függvények esetén szorítsuk meg az f függvényt M határára, és állapítsuk meg az ottani lehetséges (glob¨is) széls®érték-helyeket. Ez általában már csak egyváltozós széls®érték-számítás, de továbbra is egy korlátos zárt halmazon. A globális széls®értékek megállapításához a bels® és határpontokban lév® lehetséges lokális széls®értékhelyek mindegyikén számuljuk ki a függvény helyettesítési értékét. Határozzuk meg az f (x, y) = x2 + 2xy + 8y − 4x függvény globális széls®értékeit az M = {(x, y)| 0 ≤ x ≤ 3, 0 ≤ y ≤ 1} halmazon!

Feladat.

Megoldás.

Az

fx0 = 2x + 2y − 4 = 0 fy0 = 2x + 8 = 0 egyenletrendszer megoldása a (−4, 6) pont,

azonban ez nincs M -ben. Tehát M bels® pontjaiban nincs lokális széls®érték sem. Az M tartomány egy téglalap,4 határát négy szakasz alkotja: Ha x = 0, akkor az f (y) = 8y, (0 ≤ y ≤ 1) egyváltozós függvény széls®értékeit keressük. Mivel f (y) monoton n®, y = 0-ban minimuma, y = 1-ben maximuma van. Tehát az f (x, y)-nak a (0, 0) pont lehetséges minimumhelye, a (0, 1) pont lehetséges maximumhelye. Ha x = 3, akkor f (y) = 14y−3, (0 ≤ y ≤ 1) szintén monoton n®, így f (x, y)-nak az (1, 0) pont lehetséges minimumhelye, az (1, 1) pont lehetséges maximumhelye. Ha y = 0, akkor az f (x) = x2 − 4x, (0 ≤ x ≤ 3) egyváltozós függvényt vizsgáljuk. f 0 (x) = 2x − 4 pozitív a (2, 3] intervallumon, negatív a [0, 2) intervallumon, így f (x)-nek lokális minimuma van x = 2-ben, lokális maximuma van x = 0-ban és x = 3-ban. Tehát az f (x, y)-nak a (2, 0) pont lehetséges minimumhelye, a (0, 0) és a (3, 0) pontok lehetséges maximumhelyei. Ha y = 1, akkor hasonlóan kapjuk, hogy f (x, y)-nak az (1, 1) pont lehetséges minimumhelye, a (0, 1) és a (3, 1) pontok lehetséges maximumhelyei. Ezek után behelyettesítünk a lehetséges széls®értékhelyeken: f (0, 0) = 0 f (0, 1) = 8 f (1, 1) = 7 f (2, 0) = −6 f (3, 0) = −3 f (3, 1) = 11 Ennek alapján a (2, 0) globális minimumhely, a (3, 1) globális maximumhely. Feladat. ∗

Határozzuk meg az el®z® feladatbeli függvény lokális széls®értékeit!

Vizsgáljuk meg a fenti hat lehetséges széls®értékhelyet: A (0, 0) és a (3, 0) pontok biztosan nem lokális széls®értékhelyek, mert az egyik parciális függvénynek minimuma, a másiknak maximuma van, ahogyan azt az el®z® feladatban is kiszámoltuk (nyeregpontok). A (0, 1) pontban mindkét parciális függvénynek maximuma van, ami lokális maximumhelyre utal. Valóban, fx0 < 0 és fy0 > 0 nemcsak a (0, 1) pontban, hanem egy környezetében is fennáll. Tehát ha az M -beli (a, b) pont elég közel van a (0, 1) ponthoz, akkor f (0, 1) > f (0, b) > f (a, b). Hasonlóan indokolható, hogy a (3, 1)-ben is maximum van. Megoldás.

Az (1, 1) ill. a (2, 0) pontban az fy0 = 2x+8 képletbe helyettesítve kapjuk, hogy az f (y) parciális függvénynek maximuma ill. minimuma van. Ez el®z®ekhez hasonlóan kapjuk, hogy az (1, 1) nyeregpont, a (2, 0) pedig minimumhely. Határozzuk meg az f (x, y) = x2 + 2y 2 + 3 függvény globális széls®értékeit az M = {(x, y)|x2 + y 2 ≤ 1} halmazon!

Feladat.

Megoldás.

Az

fx0 = 2x = 0 fy0 = 4y = 0 egyenletrendszer megoldása a (0, 0) pont, lehetséges széls®értékhely. Az M tartomány egy körlap, határát az x2 + y 2 = 1 egyenlet¶ kör alkotja. A függvényt úgy szorítjuk meg a körvonalra, hogy a körvonal egyenletének segítségével kiküszöböljük ez egyik változót f (x, y)-ból: f (y) = y 2 + 4, (−1 ≤ y ≤ 1).

f 0 (y) = 2y -ból f (y)-nak y = 0 minimumhelye, y = 1 és y = −1 maximumhelyei. Az ezen y értékeknek megfelel® pontok, azaz (1, 0), (−1, 0), (0, 1), (0, −1) az f (x, y) lehetséges széls®értékhelyei. Behelyettesítéssel kapjuk, hogy a (0, 1), (0, −1) (nem szigorú) globális maximumhelyek, a (0, 0) pedig globális minimumhely.

1 Operációkutatás #, NYME KTK III. évf. nappali Játékelmélet Dr. Takách Géza NyME FMK Informatikai Intézet [email protected] http://inf.nyme.hu/˜takach 2004. o˝ sz

Játékelmélet Irodalom: Hilier-Lieberman 12. fejezet Kétszemélyes zéróösszeg˝u játékot tekintünk: az egyik játékos azt nyeri meg, amit a másik elveszít. Mindkét játékos néhány lehet˝oség (stratégia) között dönt, nem ismerve a másik döntését. Ugyanakkor sok menetet játszanak, s így esetleg kiismerhetik a másik stílusát. A kifizetési táblázat (mátrix) mutatja, hogy mely esetben mennyi lesz az 1. játékos nyeresége (= 2. játékos vesztesége). A mátrix sorai felelnek meg az 1., az oszlopai a 2. játékos startégiáinak. Feltételezzük, hogy mindkét játékos 1. racionális (logikusan gondolkozik), és 2. önz˝o (kizárólag maximális nyereségre törekszik).

Dominált stratégiák Definíció. Egy játékos egyik stratégiája dominálja a másikat, ha az ellenfél minden döntése esetén legalább olyan jó, mint a másik. A dominált stratégiákelhagyhatóak feltételezéseink miatt. Példa. 1 2 3

1 1 1 0

2 3 2 4 0 5 1 −1

Az 1. játékos 3-as startégiáját dominálja az 1-es, vagyis az 3. sor elhagyható: 1 1 1

1 2

2 2 0

3 4 5

A 2. játékos 3-as startégiáját dominálja az 1-es, vagyis az 3. oszlop elhagyható:

1 2

1 1 1

2 2 0

Az 1. játékos 2-es startégiáját dominálja az 1-es, vagyis az 2. sor elhagyható: 1

1 1

2 2

A 2. játékos 2-es startégiáját dominálja az 1-es, vagyis az 2. oszlop elhagyható: 1

2

1 1

Kaptuk: mindkét játékosnak az 1. stratégiát célszer˝u választania. Ekkor az 1. játékos nyeresége 1 lesz. Ezt a számot a játék értékének nevezzük.

Minimax-elv A minimax-elv szerint mindkét játékosnak minimalizálnia kell a maximális veszteségét, másképpen maximalizálni a minimális nyereségét. Azaz: 1. játékos: a sorok minimumai közül melyik a maximális? Ez a játék alsó értéke. 2. játékos: az oszlopok maximumai közül melyik a minimális? Ez a játék fels˝o értéke. Ha a játék alsó és fels˝o értékét a táblázat ugyanazon eleme adja, akkor az szükségszer˝uen egy nyeregpont, azaz sorában minimális, oszlopában maximális elem. Ez mindkét játékos számára hasznos, mert ha a másik eltér ett˝ol, akkor ez neki csak javítja a hasznát. 1 2 3 Max

1 2 3 −3 −2 6 2 0 2 5 −2 −4 5 0 6

Min −3 0 −4

Ha nincs nyeregpont... A nyeregpont léte stabil megoldást ad, azaz egyik játékosnak sem hasznos eltérni a minimax kritérium adta stratégiától. (Ez a dominált stratégiák kiküszöbölésekor is igaz.) Ha nincs nyeregpont, akkor instabil lesz a megoldás: 1 2 3 Max 1. 2. 1. 2. 1. .. .

1 2 3 0 −2 2 5 4 −3 2 3 −4 5 4 2

Min −2 −3 −4

sor 3. elemét adná a minimax elv. DE: játékosnak az 2. stratégia jobb. játékos ezt kiismeri, és áttér a 2. sorra. játékos ezt kiismeri, és áttér a 3. oszlopra. játékos ezt kiismeri, és áttér a 1. sorra.

Kevert startégiák Legyenek x1 , . . . , xm illetve y1 , . . . , yn valószín˝uségeloszlások, ahol m illetve n az 1. illetve a 2. játékos számára rendelkezésre álló stratégiák száma. Ezen vektorok által megadott kevert stratégiák abban állnak, hogy a játékosok az adott valószín˝uségeloszlások szerint véletlenszer˝uen választják a megfelel˝o startégiákat. Például (1/2, 1/3, 1/6) esetben a játékos feldob egy kockát, és 1,2,3 esetén az 1., 4,5 esetén a 2., 6 esetén a 3. stratégia mellett dönt. A várható kifizetés, amit az 1. játékos kap: X i,j

aij xi yj ,

ahol aij a kifizetési táblázat megfelel˝o elem.

3

Minimax kritérium:Minimalizálni kell a várható veszteségek maximumát, másképpen maximalizálni a várható nyereség minimumát.

2 × 2-es táblázat Tegyük fel, hogy a kifizetési táblázat

p 1−p

q 1 k11 k21

1 2

1−q 2 k12 k22

és a játékosok a táblázat szélein jelzett p és 1 − p ill. q és 1 − q valószín˝uséggel választják az egyes stratégiákat. Ekkor az els˝o játékos várható nyeresége: = k11 pq + k12 p(1 − q) + k21 (1 − p)q + k22 (1 − p)(1 − q) =   B C D = = Apq + Bp + Cq + D = A pq + p + q + A A A     C B BC D = A p+ q+ − 2 + = A A A A    B BC C q+ +D− . = A p+ A A A

K



C K =A p+ A

  B BC q+ +D− A A

A szorzattá alakítás után maradt D − BC A lesz a játék értéke, míg az optimális stratégiát az biztosítja, hogy az A(p + ill. qopt = − B szorzat 0 legyen. Tehát popt = − C A A.

C A )(q

+

B A)

Ez abból következik, hogy ha pl. p 6= − C o megválasztásával elérheti, hogy a szorzat értéke A , akkor a II. játékos q megfelel˝ negatív legyen, s így K értéke csökken, azaz I. kevesebbet nyer.

Mintapélda Adjunk optimális kevert startégiát az alábbi játékra:

p 1−p

1 2

q 1 -1 3

1−q 2 4 -1

Megoldás. K

Tehát popt = 49 , qopt =

5 9

és v =

= −1pq + 4p(1 − q) + 3(1 − p)q − 1(1 − p)(1 − q) 5 4 1 = −9pq + 5p + 4q − 1 = −9(pq − p − + ) = 9 9 9 4 5 11 4 5 11 = −9[(p − )(q − ) − ] = −9(p − )(q − ) + . 9 9 81 9 9 9 11 9 .

4

Grafikus eljárás Akkor alkalmazható, ha az egyik, mondjuk az 1. játékosnak csak 2 stratégiája van.

x 1−x

1 2

y1 1 0 5

y2 2 -2 4

y3 3 2 -3

Ha y = 1, akkor K = 0 · x + 5(1 − x) = 5 − 5x Ha y = 2, akkor K = −2x + 4(1 − x) = 4 − 6x Ha y = 3, akkor K = 2x − 3(1 − x) = −3 + 5x Keressük ezek minimumainak maximumát, azaz az egyenesek alsó burkolójának maximumát. Ábráról: x = 7/11, a játék értéke pedig K = 4 − 6 · 7/11 = 2/11. A 2. játékos szempontjából: y1 (5 − 5x) + y2 (4 − 6x) + y3 (−3 + 5x) = 2/11 y1 (5 − 5x) + y2 (4 − 6x) + y3 (−3 + 5x) = 2/11 Másrészt y1 + y2 + y3 = 1. Innen adódik, hogy y1 = 0. Általában is felhasználhatjuk, hogy amely egyenes nem megy át a kérdéses metszésponton, az ahhoz tartozó yj értéke 0. Marad: y2 (4 − 6x) + y3 (−3 + 5x) = 2/11. Ennek minden 0 és 1 közti x-re teljesülnie kell, speciálisan 0-ra és 1-re is: 4y2 − 3y3 −2y2 + 2y3 Ebb˝ol y3 = 6/11, y2 = 5/11.

= 2/11 = 2/11

3. konzultáció: Hozzárendelési feladat

1

Példa. Adott 5, alvállalkozóknak kiadandó feladat. 5 alvállalkozó mindegyike árajánlatot ad mind az 5 feladatra, de mindegyikük csak egy feladatot tud elvégezni a szoros határid˝ok miatt. Rendeljünk minden feladathoz különböz˝o alvállalkozót úgy, hogy az összes kifizetés minimális legyen! Feladat. Teljes páros gráfban keresünk min. költség˝u teljes párosítást. Más megfogalmazás. Adott egy n × n-es C (költség)mátrix, melynek minden eleme nemnegatív egész. Válasszunk ki n elemet, hogy semelyik sorból és oszlopból se legyen több bel˝olük, és összegük minimális legyen Képletekkel megfogalmazva: x (i = 1, . . . , n; j = 1, . . . , n) Pij ∈ {0, 1} xij = 1 (i = 1, . . . , n) j P 1 P (j = 1, . . . , n) i xij =P K(x) = i j cij xij → min Itt xij = 1, ha a cij elemet kiválasztottuk, azaz az i-edik munkát a j-edik alvállalkozónak adtuk ki, xij = 0, ha nem.

Redukálás 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 párosítás esetén c-vel csökken, ami független a párosítástól. ♦ Módszer. Redukáljuk a költségmátrixot. Ha utána nulla összköltségen tudunk párosítani, akkor az biztosan optimális. Els˝o lépésben minden sorból kivonjuk a minimális elemét, majd minden oszlopból is. Természetesen ahol van nulla, az marad változatlan. Ezek után általában szükség van még további redukálásra, pl. egy oszlophoz hozzáadok egy számot, hogy ezután több sorból is kivonhassam ugyanazt a számot. Ennek rendezett formába hozása lesz a magyar módszer.

Független nullák. Definíció. A költségmátrixban található két nullát függetlennek nevezünk, ha nem fekszenek azonos sorban sem azonos oszlopban. Nulla összköltség˝u párosítás n darab (páronként) független nulla kiválasztását jelenti. Ennél több független nulla nincs is. Tehát minél több független nullára van szükségünk. Módszer független nullák kiválasztására. Az egyik legkevesebb nullát tartalmazó sort vagy oszlopot kiválasztjuk, az egyik nullát kijelöljük, majd kihúzzuk a sorát és oszlopát. Ha ezután találunk olyan sort vagy oszlopot, amelyben már nincs nulla, azt is ki lehet húzni, s ezután el˝olr˝ol folyatjuk.

Fed˝ovonalak Definíció. Fed˝ovonalon a költségmátrix egy sorára vagy oszlopára fektetett vonalat értünk. Fed˝ovonalak nullákat fednek le: Tétel. (König-Egerváry) Egy mátrixban kiválasztható független nullák maximális száma megegyezik az összes nullát lefed˝o fed˝ovonalak minimális számával. Bizonyítás. Nem kell.

2 Módszer minimáli számú fed˝ovonal keresésére. El˝oször a nem független (azaz az el˝oz˝oekben ki nem választott) nullákat fedjük le. Ezek ugyanis azért nem függetlenek, mert a sorukban vagy az oszlopukban van még egy kiválasztott nulla. Ennek megfelel˝oen a nem független nulla sorára vagy oszlopára tesszük a fed˝ovonalat, hogy egyúttal egy független nullát is lefedjünk.

ε-transzformáció Ha a König-Egerváry tétel alapján megállapítjuk, hogy nem tudunk nulla költségen párosítani (vagyis nem létezik n darab független nulla), akkor: ε-transzformáció. Jelölje ε a költségmátrix legkisebb elemét (ε > 0 egész). A lefedetlen elemeket csökkentsük ε-nal, az egyszeresen fedetteket hagyjuk változatlanul, a kétszeresen fedetteket pedig növeljük ε-nal. Más megközelítésben: A fedetlen sorokból kivonjuk ε-t, a lefedett oszlopokhoz pedig hozzáadjuk ε-t. Tehát az ε-transzformáció redukálást jelent, s így ekvivalens feladatra vezet, ahol általában nagyobb lesz a fügetlen nullák száma. El˝ofordulhatnak olyan lépések is, ahol nem n˝o a független nullák száma, de az optimális megoldás költsége minden lépésben csökken, így véges sok lépésben eljutunk egy olyan költségmátrixhoz, ahol nulla az optimum, azaz n darab független nulla van. Megjegyzés. Az optimális megoldás csökkenése egy lépésben: Rε = ε · (n − lefedetlen sorok száma + lefedett oszlopok száma).

Általánosítások Maximumfeladat kezelése. A költségek ellentettjével egy minimumfeladatot kell megoldani. Ekkor azonban negatív költségek is vannak: redukcióval (hozzáadás) el kell érni, hogy sehol se legyen negatív költség. (Pl. minden sorhoz hozzáadom a benne álló legnagyobb abszolút érték˝u negatív szám abszolút értékét. n × m-es költségmátrix. Szükség van úgynevezett névleges "állomás" beiktatására. Ez azt jelenti, hogy négyzetesre egészítjük ki a költségmátrixot, csupa nulla költséggel. Ezután megoldjuk a feladatot, és azon elemeknek, amelyeknek ilyen névleges pár jut, nem lesz párjuk. Tiltott viszonylatok. Ha egy viszonylatban tilos a párosítás, akkor oda végtelen költséget kell írni. Ilyenkor szokás szerint ∞ − c = ∞ a számolási szabály. Túl sok végtelen költség esetén nem biztosított a véges összköltség˝u párosítás létezése.

Operációkutatás

1

NYME KTK, gazdálkodás szak, levelez® alapképzés 2002/2003. tanév, II. évf. 2.félév El®adó: 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) 509 7361 [email protected] http://titanic.nyme.hu/takach

Széls®érték korlátos zárt halmazon Feladat.

f (x, y) függvény, valamint egy g(x, y) = 0 feltétel. Jelölje G a g(x, y) = 0 feltételt g(x, y) = 0 egyenlet¶ görbe pontjainak) halmazát. Keressük a Df ∩ G halmazra megszorított széls®értékeit; ezeket nevezzük az f (x, y) függvény g(x, y) = 0 feltételre vonatkozó széls®értékeinek.

Adott egy kétváltozós

kielégét® pontok (tehát a

f (x, y)

függvény

Lagrange-módszer.

Tekintsük a

ϕ(x, y) = f (x, y) + λ · g(x, y) függvényt.

Igazolható, hogy az

x, y, λ ismeretlenekre

vonatkozó

ϕ0x (x, y) = 0 ϕ0y (x, y) = 0 ϕ0λ (x, y) = g(x, y) = 0

egyenletrendszer megoldásai között biztosan ott lesznek az

Feladat. Keressük meg az az

x+y−2=0

f (x, y)

feltételes széls®értékei. Fordítva nem okvetlenül!

egyenes origóhoz legközelebbi pontját!

f (x, y) = x2 + y 2 függvény x + y − 2 = 0 feltételre vonatkozó minimumát kell g(x, y) = x + y − 2, valamint ϕ(x, y) = x2 + y 2 + λ(x + y − 2), tehát a megoldandó egyenletrendszer:

Megoldás.

Az

megkeresni.

ϕ0x (x, y) = 2x + λ = 0 ϕ0y (x, y) = 2y + λ = 0 g(x, y) = x + y − 2 = 0

λ

értékére nincs szükségünk,

x=y=1

pedig könnyen adódik. Mivel

ϕ00xx ϕ00yx továbbá

ϕ00xx = 2 > 0,

Feladat.

ezért itt

Keressük meg az

Megoldás.

ϕ(x, y)-nak

ϕ00xy 2 = ϕ00yy 0

0 = 4 > 0, 2

minimuma van, tehát az

f (x, y) = x2 + 3xy + y 2

(1, 1)

pont annál inkább feltételes széls®értékhely.

függvény maximumát feltéve, hogy

ϕ(x, y) = x2 + 3xy + y 2 + λ(x + y − 100),

x + y = 100!

tehát a megoldandó egyenletrendszer:

ϕ0x (x, y) = 2x + 3y + λ = 0 ϕ0y (x, y) = 3x + 2y + λ = 0 g(x, y) = x + y − 100 = 0

λ

x = y = 50 pedig viszonylag könnyen adódik. Mivel a másodrend¶ parciális derivál-2 ϕ(x, y)-nak nincs széls®értéke ebben a pontban, de f (x, y)-nak mégis feltételes maximuma van. Valóban, a kérdéses feltétel mellett az x = 0, 50, 100 helyeken felvett függvényérték rendre 10000, 12500, 10000, vagyis 0 ≤ x ≤ 100 intervallumon valahol maximumnak kell lennie, ez pedig csak az x = 50-ben lehet. értékére itt sincs szükségünk,

takból alkotott determináns itt negatív,

Feladat.

Keressük meg az

f (x, y, z) = x2 + 2y 2 + 3z 2

függvény

x2 + y 2 + z 2 = 1 feltételre vonatkozó globális feltételes

széls®értékeit!

Megoldás.

ϕ(x, y, z) = x2 + 2y 2 + 3z 2 + λ(x2 + y 2 + z 2 − 1),

tehát a megoldandó egyenletrendszer:

ϕ0x (x, y, z) = 2x + 2λx ϕ0y (x, y, z) = 4y + 2λy ϕ0z (x, y, z) = 6z + 2λz g(x, y, z) = x2 + y 2 + z 2 − 1

= 0 = 0 = 0 = 0

Átrendezve

x(λ + 1) y(λ + 2) z(λ + 3) 2 x + y2 + z2 Ennek 6 megoldása van:

•

x, y

és

z

= 0 = 0 = 0 = 1

közül pontosan kett® nulla, a harmadik pedig

±1.

Behelyettesítés!!!

Széls®érték korlátos zárt halmazon: a határon lév® lehetséges széls®értékek meghatározása történhet Lagrangemódszerrel.

• n-változós •

függvény esetén is m¶ködik, ott

Több feltétel esetén

g1 , g2 , . . .

n+1

egyenletb®l áll az egyenletrendszer.

s ennek megfelel®en

λ1 , λ 2 , . . .

szükséges:

ϕ(x1 , x2 , . . .) = f (x1 , x2 , . . .) + λ1 g1 (x1 , x2 , . . .) + λ1 g1 (x1 , x2 , . . .) + . . .

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ó: Sorbanállás Irodalom: Csernyák 5. fejezet 5.1. A kés˝obbiekhez kell: jelölések, a kés˝obbi bizonyításokban felhasználandó egyszer˝u összefüggések. 5.2. A 4 feltevés, illetve a differenciálegyenletrendszer (biz. nélkül) 5.3. Stacionárius folyamatra vonatkozó egyenletrendszer 5.4. és 5.5. végig kell, bizonyításokkal, kivéve a Kendall-képlet.

Exponenciális elsozlás (ismétlés) Az exponenciális eloszlás folytonos eloszlás, s˝ur˝uségfüggvénye  µe−µt f (t) = 0

ha t ≥ 0 ha t < 0

Eloszlásfüggvénye:  F (t) = P (η < t) =

1 − e−µt 0

ha t ≥ 0 ha t0 < 0

Ez eloszlás két fontos tulajdonsága: 1. (Örökifjú tulajdonság) Annak a valószín˝usége, hogy még egy percnél többet kell várnom a buszra, nem függ attól, hogy eddig mennyit vártam. 2. Annak a valószín˝usége, hogy éppen a következ˝o percben jön a busz, egyre csökken.

2

Örökifjú tulajdonság

1. Örökifjú tulajdonság. Annak a valószín˝usége, hogy még egy percnél többet kell várnom a buszra, nem függ attól, hogy eddig mennyit vártam. Állítás. P (η > t + ∆t|η > t) = P (η > ∆t). Bizonyítás. A bal oldal: P (η > t + ∆t|η > t)

=

P (η > t + ∆t és η > t) P (η > t + ∆t) = = P (η > t) P (η > t)

=

1 − P (η < t + ∆t) 1 − (1 − e−µ(t+∆t) ) = = 1 − P (η < t) 1 − (1 − e−µt )

= e−µ∆t A jobb oldal: P (η > ∆t) = 1 − P (η < ∆t) = 1 − (1 − e−µ∆t ). ♦

A remény fogy...(?) Annak a valószín˝usége, hogy éppen a következ˝o percben jön a busz, egyre csökken. Állítás. P (t0 ≤ η < t0 + ∆t) > (t1 ≤ η < t1 + ∆t), ha t0 < t1 . Bizonyítás. P (t0 ≤ η < t0 + ∆t) = (1 − e−µ(t0 +∆t) ) − (1 − e−µt0 ) = e−µt0 (1 − e−µ∆t ) és hasonlóan P (t1 ≤ η < t1 + ∆t) = e−µt1 (1 − e−µ∆t ). Mivel t0 < t1 , ezért −µt0 > −µt1 , vagyis e−µt0 > e−µt1 .

♦

Teljes eseményrendszer Definíció. Teljes eseményrendszer: A1 , A2 , . . . , An véges sok, vagy A1 , A2 , . . . végtelen sok esemény, melyek páronként kizárják egymást, és összegük a biztos esemény. A P (A1 ), P (A2 ), . . . , P (An ) illetve P (A1 ), P (A2 ), . . . véges vagy végtelen sok szám diszkrét eloszlást alkot, vagyis olyan 0 és 1 közti számokról van szó, melyek összege 1.

Sorbanállás Modell: m ennyi egység képzelhet˝o el összesen a rendszerben (általában végtelennek tételezzük fel) n beérkez˝o egységek, azaz sorbanállók + kiszolgálásban részesül˝ok v várakozók (sorbanállók) j kiszolgálásban részesül˝ok S kiszolgáló csatornák ρ üres csatornák n ≤ S esetén n = j (mindenkit kiszolgálnak) és n + ρ = S, v = 0. n > S esetén ρ = 0 (minden csatornánál folyik a kiszolgálás), és S = j, n = v + j.

3

Valószínuségek ˝ Tegyük fel, hogy n, v, j valószín˝uségi változók, és pk = P (n = k). A rendszerben lév˝o egységek várható száma: M (n) = 0 · p0 + 1 · p1 + . . . + m · pm =

m X

ipi

i=1

A sor hosszának várható értéke: m X

M (v) = 0 · p0 + 0 · p1 + . . . + 0 · pS + 1 · pS+1 + 2 · pS+2 + . . . + (m − S)pm =

(i − S)pi

i=S+1

. Az üres állomások várható értéke: M (ρ) = Sp0 + (S − 1)p1 + . . . + 1 · pS−1 + 0 · pS + . . . + 0 · pm =

S−1 X

(S − i)pi

i=0

Nyilván M (n) = M (v) + S − M (ρ).

Poisson-típusú sorbanállási rendszer Jelölések: ek (∆t) = P (∆t id˝o alatt k egység érkezik a rendszerbe). pk (t) = P (t id˝opontban k egység van a rendszerben). Feltételezéseink: 1. ek (∆t) csak a ∆t id˝ointervallum hosszától függ, a kezdetét˝ol nem. 2. lim

∆t→0

e1 (∆t) = λ, ∆t

ahol λ az id˝oegységenkénti átlagos beérkezés. 3. (ritkasági feltétel) e2 (∆t) + e3 (∆t) + . . . 1 − e0 (∆t) − e1 (∆t) = lim = 0, ∆t→0 ∆t→0 ∆t ∆t azaz egyszerre több egység nem érkezik a rendszerbe. lim

Poisson-típusú sorbanállási rendszer Tétel. 1,2,3 teljesülése esetén ek (∆t) =

(λt)k −λt e k!

(k = 0, 1, 2, . . .).

Bizonyítás. Nem kell. További feltételezésünk, hogy 4 Egy egység kiszolgálásának id˝otartama exponenciális eloszlású kiszolgálni egy csatorna.

1 µ

várható értékkel, azaz id˝oegységenként µ egységet tud

Tétel. 1-4 teljesülése esetén a pi valószín˝uségek kielégítik következ˝o differenciálegyenlet-rendszert. ... Bizonyítás. Nem kell!

4

Stacionárius folyamat

Ha p0n (t) = 0, azaz pn (t) = pn nem függ az id˝ot˝ol, akkor a fenti differenciálegyenlet-rendszer az alábbi egyenletrendszerbe megy át: 0 = −λp0 + µp1 (n = 0) 0 = −(λ + nµ)pn + λpn−1 + (n + 1)µpn+1 (1 ≤ n < S) 0 = −(λ + Sµ)pn + λpn−1 + Sµpn+1 (n ≥ S)

Ezen egyenletrendszerb˝ol vezetjük le a pi -kre vonatkozó képletet. Az egycsatornás rendszereknél, ahol S = 1, nincs olyan n, amire 1 ≤ n < S. Így az egyenletrendszer: 0 = −λp0 + µp1 (n = 0) 0 = −(λ + µ)pn + λpn−1 + µpn+1

(n ≥ 1)

Egycsatornás rendszerek Definíció. Legyen ψ =

λ µ

a forgalom intenzitása, azaz az id˝oegység alatti beérkezések és kiszolgálások hányadosa.

Egy csatorna esetén elvárható, hogy ψ < 1 teljesüljön, különben a sora végtelenségig növekedne. Állítás. p0 = 1 − ψ, pn = (1 − ψ)ψ n . Bizonyítás. Az egyenletrendszerben az els˝o egyenletb˝ol: 0 = −λp0 + µp1

(n = 0)

⇒

p1 =

λ p0 = ψp0 . µ

A második egyenletb˝ol: 0

1 λ = −(λ + µ)pn + λpn−1 + µpn+1 ⇒ pn+1 = (λ + µ) pn − pn−1 µ µ

Tehát 1 λ 1λ λ λ2 p2 = (λ + µ) p1 − p0 = (λ + µ) p0 − p 0 = 2 p0 = ψ 2 p 0 µ µ µµ µ µ

Egycsatornás rendszerek Hasonlóan p3

pn

= . . . = ψ 3 p0 .. . = . . . = ψ n p0

Másrészt 1 = p0 + p1 + . . . =

∞ X n=0

Ebb˝ol p0 = 1 − ψ, és pn = (1 − ψ)ψ n .

p0 ψ n = p0

1 . 1−ψ ♦

5

További képletek Tétel. 1. M (n) =

ψ 1−ψ

2. M (v) =

ψ2 1−ψ

3. várható sorbanállási id˝o: M (ts ) =

1 ψ µ 1−ψ

4. várható rendszerben töltött id˝o: M (tr ) =

1 1 µ 1−ψ

Bizonyítás. könyvben. Megjegyzés. 1. M (n) − M (v) = S = 1 2. M (tr ) − M (ts ) = µ1 (kiszolgálási id˝o. 3. ψ → 1 esetén M (n), M (v), M (ts ), M (tr ) → ∞.

Többcsatornás rendszerek Ha S csatorna van, akkor λ továbbra is az egységnyi id˝o alatt a rendszerbe érkez˝ok száma, de µ az egy csatornán id˝oegység alatt kiszolgált egységek száma. Tehát ψ = µλ < S a feltétele, hogy ne torlódjon a sor a végtelenségig. Tétel. Az egyenletrendszer megoldása S csatornás rendszer esetén: pn pn p0

ψn (1 ≤ n ≤ S) n! ψn (S < n) = p0 S!S n−S 1 = PS−1 n ψS + n=0 ψn! S!(1− ψ ) = p0

s

Bizonyítás. könyvb˝ol. Tétel. M (v)

=

M (n)

=

M (ts )

=

M (tr )

=

M (ρ)

=

P (ts > 0)

=

ψ S+1 1 · p0 · 2 S · S! (1 − ψ S) M (v) + S M (v) λ M (n) λ S−ψ X P (n ≥ S) = pn = p0 n≥S

Bizonyítás. könyvb˝ol.

ψS S!(1 −

ψ S)

6

Képletgyujtemény ˝

ψ=

beérkezések λ = µ kiszolgálások

S=1 M (n) = S>1

ψ<1 ψ 1−ψ

(id˝oegységenként)

M (v) =

ψ<S

pn = (1 − ψ)ψ n

p0 = 1 − ψ ψ2 1−ψ

p0 =

M (ts ) =

ψS S!(1− ψ s)

1 ψ µ1−ψ

M (tr ) =

1 PS−1

+

ψn n=0 n!

ψn ψn (1 ≤ n ≤ S) pn = p0 (S < n) n! S!S n−S ψ S+1 1 M (v) = · · p0 M (n) = M (v) + S 2 S · S! (1 − ψ S) M (n) M (v) M (tr ) = M (ρ) = S − ψ M (ts ) = λ λ ψS P (ts > 0) = p0 S!(1 − ψ S) pn = p0

1 1 µ1−ψ

1 Operációkutatás #, NYME KTK III. évf. nappali Szállítási feladat Dr. Takách Géza NyME FMK Informatikai Intézet [email protected] http://inf.nyme.hu/˜takach 2004. o˝ sz

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

A költségek és kapacitások:

A szállított mennyiségek:

Az LP model:

x11

+

x12

+

R1 2 4 10

F1 F2

F1 F2

R1 x11 x21 10

+

x21 x21

x12 +

3x12

R2 x12 x22 20

R3 5 2 15

20 25 45

R3 x13 x23 15

20 25 45

x13

x11

2x11

R2 3 1 20

+ x22

+

x23

+ x22 +

x13 5x13

+ 4x21

+ x22

+ x23 + 2x23

= 20 = 25 = 10 = 20 = 15 → min

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 i=1

fi =

n X j=1

rj .

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

2

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:  1  0   ..  .   0 A =   1   0   .  .. 0 x = c = b =

mn változó, m + n feltétel. 1 ... 1 0 ... 0 .. .

...

0 ... 0 0 ... 0 1 ... 0 .. .

0 0 ... 0 1 1 ... 1 .. .. . . 0 0 ... 0 1 0 ... 0 0 1 ... 0 .. .. . .

0 ... 1

0

...

0 ... 1

... ... ...

 0 0 ... 0 0 0 ... 0   .. ..  . .     1 1 ... 1   = A1 A2 1 0 ... 0   0 1 ... 0   .. ..  . .  0 0 ... 1

[x11 , x12 , . . . , x1n ; x21 , x22 , . . . , x2n ; xm1 , xm2 , . . . , xmn ]∗ [c11 , c12 , . . . , c1n ; c21 , c22 , . . . , c2n ; cm1 , cm2 , . . . , cmn ]∗ [f1 , f2 , . . . , fm ; r1 , r2 , . . . , rn ]∗ = [f ∗ , r∗ ] Ax = b x ≥ 0 K(x) = c∗ x → min

Az A mátrix oszlopvektorai: A = [a11 , a12 , . . . , a1n ; a21 , a22 , . . . , a2n ; am1 , am2 , . . . , amn ]

ahol

 aij =

3



ei ej

(ei egy m, ej egy n komponens˝u egységvektor)

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 A együtthatómátrix rangja m+n−1. Bizonyítás. • A rang nem lehet nagyobb, mint a sorok száma, azaz m + n. • Mivel az els˝o n sor összege és az utolsó m sorösszege egyaránt csupa 1 komponensekb˝ol áll, ezért az els˝o n sor összege és az utolsó m sorösszegének különbsége 0: 1∗ A1 − 1∗ A2 = 1∗ − 1∗ = 0 Vagyis A sorai lineárisan függ˝oek, így a rang kisebb m + n-nél, legfeljebb m + n − 1. • A rang m + n − 1, mert az els˝o blokk oszlopai, valamint a további blokkok els˝o oszlopai oszlopai lineárisan függetlenek:       e1 e1 e1 a11 = , a12 = , . . . a1n = , e2 en e1       e2 e3 em a2n = , a3n = , . . . amn = , en en en

Disztribúciós módszer 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) A mintafeladaton: R1

R2

10

F1 F2

2 4 10 0

R1 10

F1

2

F2

4 10 0

R3

3 1 20

R2 3 20

1 20 0

5 2 15

R1 20 10 25 45

F1 F2

2 4 10 0

R1

R3 5

10

2 15 5

10

20 10 0 25 5 45

F1 F2

Disztribúciós módszer Válasszuk ki a C költségmátrix egy cij elemét, s legyen xij = min(fi , rj ).

2

10

4 10 0

R2

R3

3 1 20

5 2 15 5

10

R2 3 20

1 20 0

20 10 0 25 45 R3

5

10 5

2 15 5 0

20 10 0 25 5 0 45

A cij elemet bekeretezzük, fölé írva xij értékét.

4

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ó hogy az így kapott megoldás bázismegoldása a szállítási feladathoz tartozó LP feladatnak: (Biz. nem kell, a könyvbeli bizonyítás hiányos.)

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. Bizonyítás. Mivel

Pn

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.

Optimális-e az aktuális program? A mintafeladat LP modellje: x11

+

x12

+

x13

x11

+

x21 x21

x12 2x11

+

3x12

+ x22

+

x23

+ +

x23 2x23

+ x22 +

x13 5x13

+ 4x21

+ 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 ahol δij ≥ 0.

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

A duál feladat eltérésvektorának azon komponensei nullák lesznek, amelyeknek megfelel˝o primál változók a programban vannak, 5 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

2

u2 = −3

v2 = 4 v3 = 5

10

4

3 1

5

20

2

10 5

∆ meghatározása: δ11 δ12 .. .

= c11 − u1 − v1 = 2 − 0 − 2 = 0 = c12 − u1 − v2 = 3 − 0 − 4 = −1

Tehát

" ∆=

0 −1 5 0

0 0

# ,

A −1 elem mutatja, hogy az aktuális megoldás nem optimális.

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 elhagyunk 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.

6

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

A program javítása "

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

0 0

1 0

#

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.

Redukálás 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.7 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, annak a sornak vagy oszlopnak a minimális elemére 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.

Rendkívüli esetek. (folyt.) 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.