Operációkutatás. Glashütter Andrea

Operációkutatás

Glashütter Andrea

Operációkutatás

Mátrixok

I. Mátrixok A mátrixok olyan számtáblázatok, amelyek n db sorral és m db oszloppal rendelkeznek.

a11 a Általános mátrix: A = 21 M a n1 Egy tetsz leges mátrix: M =

a12 a 22 M an 2

K a1m K a2m O M K a nm

n× m

1 2 8 5

7 1

, ahol 2x3 számpár jelöli a mátrix típusát. 2 x3

A mátrix egy tetsz leges elemére a következ képpen hivatkozhatunk: a 22 = 7 .

Speciális mátrixok: 1. Kvadratikus (négyzetes) mátrix: sorok és oszlopok száma megegyezik. 1 K= 7 5

1 0 2 4

1 9

3×3

A kvadratikus mátrix azon elemei, amelynek a sor és oszlopindexei megegyeznek a mátrix f átlóját alkotják. 2. Diagonális mátrix: olyan kvadratikus mátrix, melynek a f átlón kívüli elemei csupa nullák. 1 0

D=

0 2

2×2

3. Egységmátrix: olyan diagonális mátrix, melynek f átlójában csak egyesek vannak. 1 0 0 E= 0 1 0 0 0 1

3×3

Az egységmátrix jele mindig: E. Ha egy tetsz leges mátrixot megszorzunk egységmátrixszal és a szorzás elvégezhet , akkor az eredménymátrix megegyezik az eredeti mátrixszal.

2

Készítette: Glashütter Andrea

Operációkutatás

Mátrixok

4. Alsó háromszög mátrix: olyan kvadratikus mátrix, melynek a f átlója felett csak nullák vannak.

A=

1

0

0

2 1

7 0 5 3

3×3

5. Fels háromszög mátrix: olyan kvadratikus mátrix, melynek a f átlója alatt csak nullák vannak. 14 F= 0 0

1 2 7 0

6 3

3×3

6. Nullmátrix: olyan mátrix, melynek minden eleme nulla 0 0 0 0= 0 0 0 0 0 0

3×3

7. Oszlopvektor: nx1 típusú mátrix. 1 2 o= 3 4 8. Sorvektor: 1xm típusú mátrix.

s* = (1

2

3)

9. Egységvektor: olyan vektor, amelynek egyetlen komponense 1, az összes többi nulla. e1* = (1 0 0 )

e 3* = (0 0 1 0) 10. Összegz vektor: olyan vektor, melynek minden komponense 1. 1 1 1= 1 1

3


Operációkutatás

Mátrixok

M veletek: 1 2

Legyen A = 1.

1 2 1 , és B = 0 8 1

1 3 6 2

Transzponálás:

1 A* =

2

1 0 , azaz az A mátrix elemeinek oszlop- és sorindexét felcserélve kapjuk 2 8

* = 1. AT mátrix elemeit. Ha a12 = 1 , akkor a 21

1 Az A kvadratikus mátrix szimmetrikus, ha A = A* . Pl: SZ = 4 5

4

5

2 6

6 3 0

Az A kvadratikus mátrix ferdén szimmetrikus, ha

2.

A = A * . Pl: F =

5 6

5 0 1

6 1 0

Relációk: < > =

Csak azonos típusú mátrixokat lehet egymással összehasonlítani. Mindig az azonos index9 elemeket kell összehasonlítani a két mátrixban. Ha van olyan reláció, amely minden egyes elempár esetén igaz, akkor a reláció igaz a két mátrixra is. Pl: ha C = 3.

1 3

1 3 , akkor elmondhatjuk, hogy A 1 9

C.

Összeadás:

Csak azonos típusú mátrixok adhatók össze, az összeadást elemenként végezzük. Az azonos index9 elemeket adjuk rendre össze. A+ B =

2 3

2 5 . 6 10

Tulajdonságok:

-kommutatív: A+B=B+A -asszociatív: (A+B)+C=A+(B+C)

4


Operációkutatás

4.

Mátrixok

Kivonás:

Csak azonos típusú mátrixoknak lehet a különbségét képezni. A m9veletet elemenként végezzük. Az azonos index9 elemeknek képezzük a különbségét. A B= 5.

0 1

0 6

1 6

Skalárral való szorzás: A mátrix minden elemét megszorozzuk a kijelölt skalárral (valós számmal). Legyen: @ = 2 . Ekkor @ C =

2 6

2 6 2 18

@ A=A @ (@ µ ) A = @ (µ A )

Tulajdonságok:

Legyen A1, A2, … An azonos típusú mátrixok, 1, 2, …, n tetsz leges skalárok. Ekkor a 1A1+ 2A2+…+ nAn mátrixot az A1, A2, … An mátrixok 1, 2, …, n skalárokkal való lineáris kombinációjának nevezzük. Nemnegatív lineáris kombinációról beszélünk, ha a skalárok nemnegatívak. Konvex lineáris kombinációról beszélünk, ha a skalárok nemnegatívak és az összegük 1.

6.

A1 =

1 2

1 2 0 8

1=2

A2 =

1 1

1 3 6 3

2=5

A3 =

1 3

1 3 1 9

3=10

1A1+ 2A2+ 3A3

=

17 39

17 49 40 121

Mátrixok szorzása FALK-SÉMÁval: A=

1

2

1 1

; B= 2× 2

1 2 0 1

1 3

2×3

A szorzás nem minden esetben végezhet el. Meg kell vizsgálni, hogy az els tényez (A) oszlopainak száma (2) megegyezik-e a második tényez (B) sorainak számával (2). Ha a két szám egyenl , akkor a szorzás elvégezhet , ellenkez esetben nem.

5


Operációkutatás

Mátrixok

A B

1

2

1 1

1 2

1

1*(-1)+2*3

0 1 3 1 4 5 1

1 4

1*1+2*0

(-1)*(-1)+1*3 (-1)*2+1*1

1*2+2*1 (-1)*1+1*0 Tulajdonságok:

általában nem kommutatív asszociatív: (A B) C=A (B C) (ha a m9veletek elvégezhet k) ( A) B= (A B) disztributív: (A+B) C=A C+B C A (B+C)=A B+A C (ha a m9veletek elvégezhet k)

Összefoglaló tulajdonságok:

7.

(A+B)*=A*+B* ( A)*= AT (A B)*=B* A*

Hatványozás: Csak kvadratikus mátrixokat lehet hatványozni! A0=E (mindig ugyanolyan típusú amilyen A mátrix) A1=A A2=A A A3=A2 A M An=An-1 A

6


Operációkutatás

Lineáris egyenletrendszerek és a Gauss-elimináció

II. Lineáris

egyenletrendszerek

és

a

Gauss-

elimináció A lineáris egyenletrendszer b vített mátrixán hajtunk végre ekvivalens m9veleteket úgy, hogy az eredeti mátrixból egy fels háromszögmátrixot kapjunk. Így már könnyen leolvashatjuk az egyenletrendszer megoldásait.

Elvégezhet m veletek: 1. Tetsz leges 0-tól különböz valós számmal bármelyik sort meg lehet szorozni. 2. Bármelyik sorhoz hozzá lehet adni a többi sornak egy lineáris kombinációját. 3. A sorok sorrendjét fel lehet cserélni. A m9veletek elvégzése után, a megoldások leolvasáskor a következ találkozhatunk: az egyenletrendszernek 1 megoldása van az egyenletrendszernek végtelen sok megoldása van az egyenletrendszernek nincs megoldása

esetekkel

1. feladat Oldjuk meg a következ lineáris egyenletrendszert! 2x 1 x1 x1

+ 3x 2 x2

= = =

12x 3 + x3 + 2x 3

25 4 3

Az egyenletrendszerb l els ként fel kell írni annak b vített mátrixát. Ez a b vített mátrix az együtthatókból és az egyenletek jobb oldalából áll:

2 1 1

3 1

12 1

25 4

0

2

3

Ezen a mátrixon kell a fenti m9veleteket végrehajtani úgy, hogy fels háromszög mátrix alakú legyen.

1. lépés: a 2. sorhoz adjuk hozzá a 3 sort:

2

3

12

25

0 1

1 0

3 2

7 3

7


Operációkutatás

Lineáris egyenletrendszerek és a Gauss-elimináció

2. lépés: az els sorhoz adjuk hozzá a 3. sor kétszeresét:

0

3

8

19

0 1

1 0

3 2

7 3

0

2

3

1 3

3 8

7 19

3. lépés: cseréljük fel az 1. és a 3. sort:

1 0 0

4. lépés: a 3. sorhoz adjuk hozzá a 2. sor háromszorosát:

1

0

0 0

2 3

1 3 7 0 1 2

Megkaptuk a mátrix kívánt alakját. Ebb l is fel tudunk írni egy egyenletrendszert, amelynek a megoldásai megegyeznek az eredeti lineáris egyenletrendszer megoldásaival: - x1

+ 0x 2 - x2

+ 2x 3 + 3x 3 x3

= 3 = 7 = 2

Az egyenletrendszer 3. sorából leolvashatjuk hogy x3=2. Ezt behelyettesítve a 2. egyenletbe már csak x2 marad ismeretlen. Megoldva az egyenletet kapjuk: x2=-1. Végül az els egyenletbe behelyettesítve az ismert értékeket x1=1 eredményre jutunk. Megkaptuk tehát az egyenletrendszer megoldásait. Láthatjuk ennek az egyenletrendszernek 1 megoldása van. 2. feladat

2x 1 3x 1 2x 1 2x 1

+ 6x 2 + 10x 2 + 2x 2 + 4x 2

+ + + +

4x 3 5x 3 9x 3 3x 3

x4 x4 4x 4 + x4

= = = =

5 8 6 2

Megoldás: az egyenletrendszernek nincs megoldása. 3. feladat

x1 5x 1 2x 1 2x 1

2x 2 + 2x 2 + 2x 2 + 2x 2

x4 x3 + 2x 3 + x3

+ 6x 5 x5

x4

= = = =

3 7 4 4

Megoldás: az egyenletrendszernek végtelen sok megoldása van.

8


Operációkutatás

Lineáris programozási feladatok megoldása grafikus módszerrel

III. Lineáris programozási feladatok megoldása grafikus módszerrel 1. feladat 2x 1 3x 1 3x 1 - 2x 1

3x1

+ +

x2 4x 2 3x 2 + 3x 2 x1 , x 2

+ 7 x2

8 36 -9 - 12 0

max

FELTÉTELEK

CÉLFÜGGVÉNY

Meg kell keresni az összes olyan pontot, amelyek a megadott feltételeket egyidej9leg teljesítik (L: lehetséges megoldások halmaza). A kapott pontokból kiválasztunk egyet, vagy többet, amelynél a célfüggvény felveszi a kívánt széls értéket. MAXIMUM PONT

LEHETSÉGES MEGOLDÁSOK HALMAZA

z1: 3x1

+ 7 x2

= 21

Maximum pont meghatározása: toljuk a célfüggvényt felfelé mindaddig, míg el nem érünk egy olyan pontot, amelynél ha még feljebb tolnánk z1-et, akkor már elhagyná L-t. Ez a pont lesz a maximumpont. Jelen esetben ez a pont a 2. egyenes és 3. egyenes metszéspontja: 3x 1

+ 4x 2

3x 1

3x 2

24 45 és x 2 = . Ezeket az értékeket a 7 7 = - 9 célfüggvénybe behelyettesítve kapjuk a maximum értékét: 387 7 = 36 amelyb l x 1 =

9


Operációkutatás


Definíciók: Halmaz bels pontja: olyan pont, amelynek van olyan környezete, ami szintén a halmazhoz tartozik. Határpont: minden környezet olyan, hogy a halmazhoz tartozó és halmazon kívüli része is van. Extremális pont: a csúcspontok.

2. feladat x1 - x1 x1

+ +

3x 2 x2 2x 2 x1 ; x 2

x1 + x 2

3 4 4 0

max

Látható, hogy L most egy nemkorlátos halmaz, melyen z1: x1 + x 2 = 6 függvényt felfelé tolva a felvett függvényérték tetsz legesen nagy lehet, így a célfüggvény nem korlátos a lehetséges megoldások halmazán, a feladatnak nincs optimális megoldása. (Az, hogy L nem korlátos nem jelenti egyértelm9en, hogy nincs optimális megoldása a feladatnak, hiszen ha z: x 1 + x 2 min lenne, akkor a célfüggvényt értelemszer9en lefelé kellene tolni, és akkor a (0,2) koordinátájú pont lenne az optimális megoldás.)

10


Operációkutatás


3. feladat

- x1

A feltételrendszer legyen ugyanaz, mint a 1. feladatban, de a célfüggvény legyen: + x2 max . Legyen z1: - x 1 + x 2 = 1 Ekkor a következ képpen alakul az ábra:

Ha a célfüggvényt felfelé toljuk láthatjuk, hogy egybe fog esni a 3. egyenessel. Azaz a maximumot most nem egyetlen pontban veszi fel, hanem egy szakasz összes pontjában. Ennek a szakasznak kell felírni az egyenletét: Legyenek a szakasz végpontjai Q1 és Q2. Ki kell számolni ezek koordinátáit. 15 42 Q1 koordinátáit az 1. és 3. egyenesek metszéspontja adja: . , 9 9 24 45 Q2 koordinátáit már kiszámoltuk az 1. feladatban: . , 7 7 A szakasz egyenlete: @ q1 + (1 @ )q 2 , ahol 0 @ 1 és q1 Q1 pont, q 2 Q2 pont koordinátái.( Megjegyzés: q i koordinátáit oszlopvektor alakban kell megadni!) Behelyettesítve a kapott értékeket: 19 6 24 7 + (1 @ ) A szakasz összes pontja: @ , ahol 0 @ 1 . 53 45 7 A szakasz egy tetsz leges pontjának (pl. valamely végpontjának) koordinátáit a célfüggvénybe helyettesítve megkapjuk a maximum értékét (3).

11


Operációkutatás


4. feladat

- 2x 1

A feltételrendszer legyen ugyanaz, mint a 2. feladatban, de a célfüggvény legyen: + 2x 2 max . Legyen z1: - 2x 1 + 2x 2 = 2 Ekkor a következ képpen alakul az ábra:

Ha a célfüggvényt felfelé toljuk láthatjuk, hogy egybe fog esni a 2. egyenes L halmazt határoló félegyenesével. Azaz a maximumot most sem egyetlen pontban veszi fel, hanem egy félegyenes összes pontjában. Ennek a félegyenesnek kell felírni az egyenletét: Legyenek a félegyenes végpontja Q0. Ki kell számolni a koordinátáit. Q0 koordinátáit az 2. egyenes és az x2 tengely metszéspontja adja: (0 , 4). A félegyenes egyenlete: q 0 + t v , ahol 0 t , q 0 Q0 pont koordinátái és v a félegyenes irányvektora. (Megjegyzés: q i koordinátáit oszlopvektor alakban kell megadni!) A félegyenes irányvektora a következ képpen adható meg: A célfüggvény egyenlete - 2x 1

+ 2x 2

= 2 , azaz ennek irányvektora

x 2 együtthatója x 1 együtthatójának ( 1) - szerese Behelyettesítve a kapott értékeket: 2 0 A félegyenes összes pontja: + t , ahol 0 t . 2 4 A félegyenes tetsz leges pontjának (pl. kezd pontjának) célfüggvénybe helyettesítve megkapjuk a maximum értékét (8).

2 , ahol 2

a vektor elemei a következ k:

12

koordinátáit

a


Operációkutatás

Szöveges feladatok

IV. Szöveges feladatok Egy pék 150 kg lisztet, 22 kg cukrot, 27,5 kg vajat használhat fel 2 féle süti elkészítéséhez. Egy tucat A süti elkészítéséhez 3 kg lisztre, 1 kg cukorra és 1 kg vajra, míg 1 tucat B süti elkészítéséhez 6 kg lisztre, ½ kg cukorra és 1 kg vajra van szüksége. 1 tucat A sütin 20 Ft, 1 tucat B sütin 30 Ft a nyeresége. Hány tucat A és B süti elkészítése maximalizálja a pék nyereségét? TERMÉKEK

ER
A

B

KAPACITÁS

LISZT

3

6

150

CUKOR

1

½

22

VAJ

1

1

27,5

TERMÉKEK HOZAMA

20

30

A táblázat alapján felírhatjuk az LP feladat matematikai modelljét: 3x 1

+

x1

+

x1

+ x1 ,

20x 1

6x 2 1 x2 2 x2 x2

150 27,5 0

+ 30x 2

max

22

(A feladatot grafikusan megoldva a következ megoldást kapjuk: x1=5; x2=22,5; és max=775)

13


Operációkutatás

Modellalkotás

V. Modellalkotás 1. feladat Egy gyár négyféle terméket (A,B,C,D) termel három er forrás (I., II., III.) segítségével. A fajlagos felhasználásokat, az egyes termékek árát és az egyes er források kapacitását az alábbi táblázat mutatja: TERMÉKEK

ER
A

B

C

D

ERZFORRÁSOK KAPACITÁSA

I.

1

0

2

1

280

II.

2

1

0

0

140

III:

0

1

1

1

120

ÁR

4

5

6

8

Mennyit termeljen az egyes termékekb l a gyár, ha a maximális árbevételt akar elérni az alábbi feltételek teljesülése esetén: a) Az er források kapacitása nem léphet túl. b) Az A és B termékekb l legalább annyit kell termelni, mint C-b l. c) A B termékb l legfeljebb 5 egységgel termelhet több, mint D-b l. Megoldás: Jelölje x1 az A-ból, x2 az B-b l, x3 az C-b l, x4 az D-b l gyártandó mennyiséget! Ezekkel a változókkal a feladat matematikai modellje a következ formában írható fel: x1 2x 1 x1

+ x2 x2 x2 x2

+

2x 3

+

x4

+ +

x3 x3

+

x4

x1 , 4x 1

+ 5x 2

x2,

+ 6x 3

14

x4 x3, x4 + 8x 4

280 140 120 0 5 0 max


Operációkutatás

Modellalkotás

2. feladat Egy üzemben három gépen (I., II., III.) ötféle terméket (A1, A2, A3, A4, A5) lehet el állítani. Minden terméknek mindhárom gépen keresztül kell mennie. Az egyes termékek gépid szükséglete az egyes gépeken különböz . A fajlagos gépid szükségletet, a gépek kapacitását munkaórában a következ táblázat mutatja: TERMÉKEK

A2

A3

A4

A5

ERZFORRÁSOK KAPACITÁSA

I.

1

2

4

3

2

480

II.

3

1

1

5

3

460

III:

2

3

1

1

5

450

GÉPEK

A1

Az egyes termékek értékei rendre: 2, 3, 2, 4, 2 egység. Mennyit termeljen az egyes termékekb l, ha az a célja, hogy maximális termelési értéket érjen el az alábbi feltételek teljesülése esetén: a) A gépek kapacitása nem léphet túl. b) Az els termékb l legalább kétszer annyit kell termelni, mint az ötödikb l. c) A második és a harmadik termékb l összesen legfeljebb 120 darab termelhet . Megoldás: Ha xi jelöli az Ai matematikai modellje: x1 3x 1 2x 1 x1

2x 1

(i=1,2,3,4,5) termékb l gyártandó mennyiséget, akkor a feladat + 2x 2 + x2 + 3x 2 + x2 + 3x 2

+ 4x 3 + x3 + x3 +

x3 x1 ,

+ 2x 3

15

+ + +

3x 4 5x 4 x4

+ + +

2x 5 3x 5 5x 5 2x 5

x2,

x3,

x4,

x5

+ 4x 4

+ 2x 5

480 460 450 0 120 0 max


Operációkutatás

Szállítási feladat

VI. Szállítási feladat 1. feladat FELVEV
RAKTÁRAK

F1

F2

F3

F4

RAKTÁROZOTT MENNYISÉG

R1

8

2

4

7

30

R2

7

4

3

2

40

R3

2

5

5

9

50

IGÉNY

20

16

42

42

120

A táblázatban található számok költségeket jelentenek, azaz például az els raktárból az els felvev helyre 1 egység terméket 8 egység költséggel tudunk elszállítani. (A költségeket jelöl számok által alkotott mátrixot költségmátrixnak nevezzük, elemeit cij-vel jelöljük.) Célunk, hogy megtaláljuk a legolcsóbb szállítást, mellyel minden felvev hely igénye kielégítést nyer, és minden raktár kiürül. Kezdeti feltételként meg kell szabnunk, hogy: A RAKTÁROZOTT MENNYISÉGEK ÖSSZEGÉNEK EGYENL5NEK KELL LENNIE A FELVEV5HELYEK IGÉNYEINEK ÖSSZEGÉVEL!!!. A feladatot sorminimum-módszer segítségével oldjuk meg. Az eljárás lényeg a következ : Kiválasztjuk a táblázat els sorát. Mivel célunk a legolcsóbb szállítást megtalálni, így a legkisebb költségelem által meghatározott viszonylatban elszállítjuk a maximális mennyiséget. (Ezzel a szállítással vagy kimerült egy raktár, vagy egy megrendel igényét teljesen kielégítettük.) A táblázat szélén lév kapacitást és igényt csökkentjük az elszállított mennyiséggel. Ha nem a tárolóhely kapacitása merült ki, akkor a sor következ legkisebb elemével ismételjük meg ezt a lépést. Ha a tárolóhelyen már nincs elszállítandó termék, akkor a következ sorra lépünk, és ott ismételjük meg az eljárást. Ezeket a lépéseket addig ismételjük, míg eljutunk az utolsó sorba és kifogynak a raktáraink, valamint minden felvev helyre eljuttatuk a kívánt mennyiséget. Az eljárás segítségével megkapunk egy lehetséges megoldást, mellyel azt a feltételt teljesítettük, hogy raktáraink kiürüljenek és az igényeket is kielégítettük. Ha a fenti lépéseket a kezdeti táblázaton végrehajtjuk a következ táblázatot kapjuk:

16


Operációkutatás


F1

F2

F3

F4


R1

8

2 16

4 14

7

30 14, 0

R2

7

4

3

2 40

40 0

R3

2 20

5

5 28

92

50 30, 2, 0

IGÉNY

20 0

16 0

42 28, 0

42 2, 0

120

Azokat a helyeket, ahol szállítás történik kötött helynek (pl: 2 16 ), a többit pedig szabad helynek nevezzük A kötött helyek száma minden szállítási feladatban: RAKTÁRAK SZÁMA (m db)+FELVEV1HELYEK SZÁMA (n db)-1 Azaz ebben a feladatban: 3+4-1=6, ami teljesül is, hiszen pontosan 6 kötött helyet jelöltünk be. Tehát egy lehetséges megoldása a feladatnak a következ : Szállítások: Elszállított mennyiség: 1. szállítás: R1 \ F2 x12=16 2. szállítás: R1 \ F3 x13=14 3. szállítás: R2 \ F4 x24=40 4. szállítás: R3 \ F1 x31=20 5. szállítás: R3 \ F3 x33=28 x34=2 6. szállítás: R3 \ F4 Ezen szállítás költsége: 2*16+4*14+2*40+2*20+5*28+9*2=366. Kérdés: ez az optimális megoldás, vagy létezik ennél olcsóbb szállítás is? Ennek eldöntéséhez rendeljünk hozzá a táblázat minden sorához és oszlopához változókat! Legyenek ezek sorok szerint u1, u2, … um, az oszlopok szerint v1, v2, … vn! Határozzuk meg ezeknek változóknak az értékét úgy, hogy fennálljon a következ összefüggés: Kötött helyeken: cij=ui+vj Szabad helyekre számoljuk ki cij-( ui+vj) értékeket. v1 u1 u2 u3

1

v2

2

v3

4

v4

8

0

8+

2 16

4 14

7-

-6

7+

4+

3+

2 40

1

2 20

5+

5 28

92

17


Operációkutatás


Kötött helyekre képezzük a cij=ui+vj egyenleteket: (m+n-1 db egyenlet) 1. 2. 3. 4. 5. 6.

u1+v2=2 u1+v3=4 u2+v4=2 u3+v1=2 u3+v3=5 u3+v4=9

7 változó, 6 egyenlet ` egy szabad ismeretlen legyen u1=0

u1 helyére 0-át behelyettesítve a többi változó értéke rendre kiszámítható.

Szabad helyekre számítsuk ki a cij-( ui+vj) értékeket. Ha ezen értékek mindegyike pozitív, az eljárás véget ért, a feladat lehetséges megoldása egyben optimális megoldás is. Ha ezen értékek között van negatív, akkor a lehetséges megoldás nem optimális megoldás, szállítások átrendezésével a költségeinket csökkenteni tudjuk. Keressük meg a negatív értékek közül a legkisebbet. Ebb l a pontból indulva képezzünk hurkot a következ képpen: Hurok: olyan zárt poligon, amelyik egy szabad helyr l indul ki, és úgy jut oda vissza, hogy közben a poligon sarkain csak kötött helyek vannak. A fenti példában egyetlen egy olyan helyet találtunk a táblázatban, amelyre cij-( ui+vj) érték negatív. Ebb l a pontból kell kiindulnia a huroknak. A megfelel kötött helyek megkeresésével a következ hurkot kapjuk:

A hurok elemeit jelöljük el „+” illetve „–„ jelekkel a következ képpen: a hurok kiindulási pontjában lév szabad elem „+” jelet kap, majd a kötött helyeket felváltva „–„ és „+” jelekkel lássuk el. Így a következ ket kapjuk:

Számítsuk ki a „–„ jellel ellátott helyeken lév szállítások minimumát: min(14;2)=2. Ezt a minimumot adjuk hozzá a „+” jellel ellátott helyek szállításához, és vonjuk ki a „–„ jellel ellátott helyek szállításából. A hurok a következ képpen alakul:

Látható, hogy 7 szabad hely volt, eddig ott nem volt szállítás, de az átrendezéssel 2 egység szállítást rendeltünk hozzá, így ez a hely kötötté vált. Ugyanakkor 9 kötött hely volt 2 egység szállítással, de elvettük onnan az összes szállítást, így szabad hellyé vált. Általánosságban is elmondható, hogy hurokképzés után egy szabad helyb l kötött hely lesz, míg egy kötött hely szabaddá válik. Mivel a kötött és szabad helyek viszonya megváltozott újra kell számítani az u-v táblázat értékeit.

18


Operációkutatás


v1 u1 u2

1

v2

2

v3

4

v4

7

0

8+

2 16

4 12

72

-5

7+

4+

3+

2 40

1

2 20

5+

5 30

9+

u3

Látható, hogy most minden szabad helyen az cij-( ui+vj) értékek pozitívak, azaz a feladat ezen lehetséges megoldása egyben optimális megoldás is. Megkaptuk a lehet legolcsóbb szállítást az adott feltételek mellett. Optimális megoldás: Szállítások: Elszállított mennyiség: 1. szállítás: R1 \ F2 x12=16 2. szállítás: R1 \ F3 x13=12 3. szállítás: R1 \ F4 x14=2 4. szállítás: R2 \ F4 x24=40 5. szállítás: R3 \ F1 x31=20 x33=30 6. szállítás: R3 \ F3 Szállítási költség: 2*16+4*12+7*2+2*40+2*20+5*30=364.

Fiktív igényl , fiktív raktár A szállítási feladatok esetében sokszor el fordul, hogy a feladat kiírása nem tesz eleget annak a követelménynek, hogy az raktározott mennyiségek összege egyenl legyen az igényel mennyiségek összegével. Két eset fordulhat el : raktárak felesleges kapacitással rendelkeznek túlkínálat van fiktív igényl t iktatunk be. több az igény, mint a raktározott mennyiség túlkereslet van fiktív raktár biztosítja a hiányzó mennyiséget. Fiktív helyeken a szállítások költsége minden esetben 0 (cij=0). 2. feladat F1

F2

F3

F4


R1

12

2

5

3

30

R2

6

4

9

6

40

R3

7

2

3

2

30

IGÉNY

22

25

17

21

A raktározott mennyiségek összege: 100. Igények összege: 85. fiktív felvev helyet kell felvenni, ahol az igény éppen annyi, hogy az egyenl ség teljesüljön, azaz 15.

19


Operációkutatás


F1

F2

F3

F4

F5


R1

12

2

5

3

0

30

R2

6

4

9

6

0

40

R3

7

2

3

2

0

30

IGÉNY

22

25

17

21

15

Ezek után a feladatot ugyanúgy kell megoldani, mint az 1. feladat esetében. Optimális megoldás: Szállítások: Elszállított mennyiség: 1. szállítás: R1 \ F2 x12=22 x14=8 2. szállítás: R1 \ F4 3. szállítás: R2 \ F1 x21=22 4. szállítás: R2 \ F2 x22=3 x25=15 5. szállítás: R2 \ F5 6. szállítás: R3 \ F3 x33=17 7. szállítás: R3 \ F4 x34=13 Szállítási költség: 289.

20


Operációkutatás

Játékelmélet

VII. Játékelmélet A játékelméletben olyan helyzeteket vizsgálunk, amelyekben két vagy több személy cselekvései befolyásolják egy esemény kimenetelét, de nem feltétlenül határozzák meg. Így az olyanféle játékok, amelyek kimenetele csak a véletlent l függ (pl.: kockajáték) nem tartoznak a játékelmélet körébe, mert itt nem egy másik játékossal, hanem a szerencsével áll szemben a játékos. Minden játéknak megvannak a szabályai, amelyek a mi esetünkben a következ k: 1. A játékosok száma. 2. Az egyes játékosok lehetséges tevékenységei. Ezeket a tevékenységeket a játékelméletben a játékos stratégiáinak nevezzük. 3. Az egyes stratégiák alkalmazása esetén a játékos mennyit nyer vagy veszít. Ezt adja meg a kifizet függvény. Legegyszer9bb játékelméleti probléma a kétszemélyes, zérusösszeg9 játékok problémája. ZérusösszegG a játék, ha a játékosok nyereményeinek és veszteségeinek összege 0, vagyis amennyit nyer az egyik annyit veszít a másik. Minden kétszemélyes játék kifizet függvénye egy mátrixszal adható meg. A mátrixnak annyi sora van, amennyi az egyik játékos stratégiáinak száma, és annyi oszlopa, ahány stratégiája van a másik játékosnak. A mátrix eleme az els játékos nyereményét (ill. a másik játékos veszteségét) adja meg. A játékosokat nevezzük „A”-nak és „B”-nek. „A” stratégiáinak száma legyen n, „B” stratégiáinak száma m. Az „A” játékos nyereményét tartalmazza a C mátrix: c11 c12 K c1m c c 22 K c 2m C = 21 M M O M

c n1 c n2 K c nm A cij szám azt mutatja meg, hogy ha az els játékos az i-edik stratégiát, a második játékos a j-edik stratégiát választja, akkor az els játékos nyereménye cij. Ha cij>0, akkor az els játékos nyer cij-t, ha cij<0, akkor az els játékos veszít. Az „A” olyan i kiválasztására törekszik, hogy cij a legnagyobb, a „B” pedig olyan j-t választ, hogy cij a legkisebb legyen. 1. feladat

Egy vendéglátós egység növelni akarja árait. Különféle lehet ségei vannak az áremelés mértékére, kiterjedésére. Az áremelésre a vendégkör is különböz képpen reagálhat: van akit nem befolyásol az áremelés, ugyanannyit fogyaszt, tehát többet fizet, így az egységnek n a bevétele. Van aki ritkábban jön, kevesebbet fogyaszt, így az egységnek csak kisebb mértékben n , vagy nem változik bevétele. Lehet, hogy egyesek nem jönnek többet az étterembe, így az áremelés az egység számára ráfizetést eredményez. Tegyük fel, hogy az egység áremelési stratégiát alkalmazhat, a vendégkör pedig 4 típusra osztható, azaz 4 féle stratégiát alkalmazhat. Legyen „A” játékos a vendéglátó egység, „B” játékos a vendégkör. Az „A” játékos nyereménymátrixa:

21


Operációkutatás

Játékelmélet

B A

I. II. III. IV. 1 1 -2 -1 -1 2 0 2 0 3 3 -3 -1 0 2

Az „A” és „B” játékosnak egyidej9leg kell választania stratégiát, vagyis „A”-nak egy sort, „B”-nek egy oszlopot kell választania. „A” játékos gondolkodása: Megnézem, hogy az egyes stratégiák választása esetén mi a legrosszabb eset, vagyis mennyi a minimális nyereségem (ami persze veszteség is lehet). Ha az 1. stratégiát választom, akkor az els sor elemei: 1,-2,-1,-1 közül kell választani a legkisebbet, ez -2. Hasonlóképpen a 2 stratégia esetén a minimális nyereség 0, végül a harmadik sor elemei közül a legkisebb -3. Tehát a minimális nyereségek sorban: 2 0 3 Akkor járok a legjobban, ha ezek közül a legnagyobbat (0) választom, tehát a 2. stratégiát alkalmazom. Ebben az esetben az ellenfél bármely stratégiája esetén is legalább 0 érték9 nyereségem van, vagyis biztosan nem veszítek semmit, de lehet ségem van a nyerésre is. „B” játékos gondolkodása:

Hasonlóképpen a legrosszabb esetet, a maximális veszteséget nézem meg az egyes stratégiák alkalmazása esetén. ha az I. stratégiát választom, akkor az els oszlop elemei mutatják a veszteséget: lehet 1, 0 vagy -3 (vagyis a nyereségem 3). ezek közül a legnagyobb 1. A II. stratégia esetén a második oszlop elemei közül kell kiválasztani a legnagyobbat, ez . A harmadik oszlop elemei közül a legnagyobb 0, végül a negyedik oszlop elemei közül a legnagyobb a 3. Tehát a maximális veszteségek: 1 2 0 3 Akkor járok a legjobban, ha ezek közül a legkisebbet választom (0), tehát a III. stratégiát alkalmazom. Ekkor legfeljebb 0 a veszteségem, de nyerhetek is. Jelöljük be ezeket a döntéseket a mátrixban:

I.

II. III. IV.

1

1

-2

-1

-1

2

0

2

0**

3

3

-3

-1

0

2

Tehát ha az „A” játékos a 2., és a „B” játékos a III. stratégiát alkalmazza, akkor mindkét játékos a mátrixnak ugyanazt az elemét választja, a játék értéke pedig 0. A játék igazságos, mert egyik játékos sem nyer és egyik sem veszít. A kifizet függvény, a mátrix nyeregpontjának nevezzük azt a (k,l) számpárt, amelyre igaz, hogy a hozzá tartozó ckl függvényérték az t tartalmazó sorban a legkisebb, ugyanakkor az t tartalmazó oszlopban a legnagyobb szám.

22


Operációkutatás

Játékelmélet

Ha létezik a mátrixnak nyeregpontja, akkor a játékot szigorúan determináltnak nevezzük, és az a (k,l) stratégiapár az optimális stratégia. A szigorúan determinált játék optimális stratégiáját tiszta stratégiának nevezzük, a nyeregpontban lév elem, ckl pedig a játék értéke. Ha a játék értéke 0, akkor a játékot igazságosnak nevezzük. A példában ismertetett játék szigorúan determinált, az optimális tiszta stratégia, a mátrix nyeregpontja a (2,3) számpár. A játék igazságos, mert a játék értéke, c23 0-val egyenl . 2. feladat Nem minden esetben olyan egyszer9 a megoldás, mint az el z példában. Legyen a játék mátrixa: 2 5 C= 4 1 Nézzük meg, hogy van-e nyeregpontja a mátrixnak: Soronkénti minimumokat és oszloponkénti maximumokat keresve kapjuk: I.

II.

1.

2*

5

2.

4*

1

Látható, hogy a mátrixnak nincs nyeregpontja, a játék nem szigorúan determinált. Így tehát nem lehet megadni az eddig ismertetett módon az optimális stratégiát. Hogyan gondolkodhatnak a játékosok? Mivel egyik stratégia sem optimális, felváltva alkalmazom mindkét lehetséges stratégiát. Ezt kevert stratégiának nevezzük Az „A” játékos számára a kevert stratégia a következ ket jelenti: „Játszd az 1. sort p1 valószín9séggel, a 2. sor p2 valószín9séggel.” A „B” játékos számára pedig a kevert stratégia: „Az I. oszlopot q1 valószín9séggel, a II. oszlopot q2 valószín9séggel válaszd!” Az „A” játékos nyereménye egy diszkrét valószín9ségi változó, jelöljük -vel, és képezzük a nyeremény várható értékét. Az „A” játékosnak az az érdeke, hogy úgy válassza meg p1, p2 értékét, hogy a nyeremény várható értéke a lehet legnagyobb legyen. a „B” játékosnak ezzel szemben pedig célja úgy megválasztani q1, és q2 értékét, hogy a várható érték minimális legyen. A várható érték felírásánál felhasználjuk, hogy a két játékos stratégiája független, így tehát pl. annak a valószín9sége, hogy „A” az 1., és „B” is az I. stratégiát választja: p1q1, vagyis a táblázat bal fels sarkában lév 2 egység nyereményének a valószín9sége. Így a várható érték: M(c ) = 2p1q 1 + 5p1q 2 + 4p 2 q1 + 1p 2 q 2 .

Vizsgáljuk meg a két játékos szemszögéb l a fenti feladatot, valamint számítsuk ki a hiányzó valószín9ségeket: A továbbiakban jelölje a játék értékét: v.

23


Operációkutatás

Játékelmélet

„A” játékos szemszögéb l: + p2 = 1 + 4p 2 v 2p1 + 4 v p2 = 1 p1 + p2 v 4p1 + 1 v p1 , p 2 0 Az els és az utolsó feltétel nyilvánvaló a valószín9ség fogalmából. A 2. sorban lév egyenl tlenség bal oldala az „A” játékos nyereményének várható értéke abban az esetben, ha „B” az 1. stratégiát választja. Ez a várható érték nem lehet kisebb, mint a játék értéke, vagyis v. A következ egyenl tlenség is azt fejezi ki, hogy a nyeremény várható értéke legalább v kell hogy legyen a „B” 2. stratégiája esetén. Ábrázoljuk a egyenl tlenségeket koordinátarendszerben! Felvesszük a p1 és v tengelyt, és a koordinátarendszerben ábrázoljuk az egyenl tlenségek megoldását, a közös megoldásra egy síkbeli tartományt kapunk. Mivel „A” maximális nyereségre törekszik megkeressük a lehetséges megoldások közül azt, amelyhez tartozó v értéke a legnagyobb. Ez a két egyenes metszéspontja, ahol p1=½ (így p2 =½) és v=3. p1 2p1 5p1

„B” játékos szemszögéb l:

+ q2 = 1 + 5q 2 v 3p1 + 5 v q2 = 1 q1 + q2 v 3p1 + 1 v q1 , q 2 0 Az els és az utolsó feltétel nyilvánvaló a valószín9ség fogalmából. A 2. sorban lév egyenl tlenség bal oldala a „B” játékos veszteségének várható értéke abban az esetben, ha „A” az 1. stratégiát választja. Ez a várható érték nem lehet nagyobb, mint a játék értéke, vagyis v. A következ egyenl tlenség is azt fejezi ki, hogy a veszteség várható értéke legfeljebb v lehet az „A” 2. stratégiája esetén. Ábrázoljuk a egyenl tlenségeket koordinátarendszerben! Felvesszük a q1 és v tengelyt, és a koordinátarendszerben ábrázoljuk az egyenl tlenségek megoldását, a közös megoldásra egy síkbeli tartományt kapunk. Mivel „B” minimális veszteségre törekszik megkeressük a lehetséges megoldások közül azt, amelyhez tartozó v értéke a legkisebb. Ez a két egyenes metszéspontja, ahol q1=d(így q2 =e) és v=3. Tehát az optimális stratégia: „A” játékos: mindkét lehet séget ½ valószín9séggel választja. „B” játékos: az els lehet séget d, a második lehet séget e valószín9séggel választja. A játék értéke: 3. q1 2q 1 4q 1

24


Operációkutatás

Döntésanalízis

VIII. Döntésanalízis Egy döntési probléma tisztázása felismerésével kezd dik, hogy bizonyos cél eléréséhez két vagy több cselekvési lehet ségünk van. Ilyen esetekben a döntést hozó szeretné a legkedvez bb cselekvési lehet séget kiválasztani egy el re meghatározott kritérium alapján. A döntési kritérium azoknak a szempontoknak az összessége, az a megítélési szint, amelynek alapján a döntést hozó a cselekvési lehet ségek közül választ. A választást megnehezíti az a tény, hogy a döntést hozó nem tudja pontosan megmondani, hogy a cselekvési lehet ségek milyen következményekkel járnak. Ha egy cselekvési lehet ségnél két vagy több következménnyel számolhatunk, akkor azt mondjuk, hogy a bizonytalanság körülményei között kell döntést hozni. A döntést hozó helyzetét egy mátrix segítségével szemléltetjük. A mátrixban a1, a2, …, an-nel jelöljük a cselekvési lehet ségeket, és S1, S2, …, Sm-mel a várható kimeneteleket, vagyis várható eseményeket. Kimenetelek\ Cselekvési S1 lehet ségek`

S2

K

Sm

a1

e11 e12 K

e1m

a2

e21 e22 K

e2m

M

M

an

en1 en2 K

M

O

M enm

A mátrix elemei a megfelel cselekvési lehet séghez és eseményhez tartozó eredményeket jelölik. Például, ha a döntést hozó az a1 cselekvést választja és az S2 esemény következik be, akkor az eredmény a döntést hozó számára e12. Általánosan az ai cselekvéshez és Sj eseményhez tartozó eredmény eij. Az eredménymátrix elemei csak azonos tartalmúak lehetnek, általában nyereséget jelentenek. 1. feladat Legyen az eredménymátrix a következ : a1 a2 a3

S1 21 28 17

S2 S3 S4 13 8 4 15 7 -5 11 10 6

A mátrix elemei jelentsenek nyereséget. Döntéselméleti feladatokat az alábbi kritériumok alapján értékelhetünk: I. A széls ségesen optimista döntést hozó A döntést hozó választásának alapja a maximális nyereségek maximumának megszerzése. A döntést hozó úgy gondolkodik, hogy ha a1-et választja, akkor S1 fog bekövetkezni, az eredménye 21 lesz, ha a2-t választja, akkor S1 valósul meg, és eredménye 28 lesz….. Tehát optimizmusával minden cselekvési lehet séghez egy számot rendel hozzá, 25


Operációkutatás

Döntésanalízis

mégpedig minden cselekvési lehet séghez a sorokban található elemek maximumát (nyereség maximalizálására törekszik): a1: 21 a2: 28 a2 a3: 17 Mivel cél a maximális nyereség elérése, ezért a döntést hozó elsöpr optimizmusával a2-t választja. II. A pesszimista döntést hozó A pesszimista mindig a legrosszabb esetre számít, és ezzel minden cselekvési lehet séghez egy-egy számot rendel hozzá, mégpedig a soronkénti minimumokat. a1: 4 a2: -5 a3 a3: 6 Ezek közük választja ki számára a legkedvez bbet, azaz itt a3-at, hiszen ezen cselekvés választása esetén ennél csak többet nyerhet, de kevesebbet nem. III. Középérték kritérium Más elnevezés: egyenl valószínGségek esete. A döntést hozó nem tud semmit az S1, S2, S3, S4 események bekövetkezésér l. Ez a „tudatlanság” adja azt az ötletet, hogy mindegyik cselekvési lehet séghez rendeljük hozzá az el re számított értékek átlagát. Másképpen: mivel az események megvalósulásával kapcsolatosan nincsen semmi információnk, tételezzük fel, hogy egyenl valószín9séggel következnek be, és számítsuk ki a várható értéket. Így egy átlagszámot rendelünk a döntési változókhoz: a1: 11,5 a2: 11,25 a1 a3: 11,0 A legkedvez bb döntés, ha ezek közül a maximálisat választja a döntést hozó, itt a1-et. IV. Az elmulasztott nyereségek kritériuma Egy mátrixból újat készítünk úgy, hogy mindegyik oszlop mindegyik elemét kivonjuk az illet oszlop legnagyobb eleméb l. Az így kapott mátrix az elmulasztott nyereségek táblázata: a1 a2 a3

S1 S2 7 2 0 0 11 4

S3 S4 2 2 3 11 0 0

Valójában úgy gondolkodunk, hogy az eseményb l indulunk ki. Ha tudnánk, hogy S1 fog bekövetkezni, akkor a2-t választanánk, hiszen ezzel érhet el a legnagyobb eredmény. Ehhez a döntési alternatívához a2 esetében 0-t rendelünk. A többihez a már ismertetett módon az elmulasztott nyereséget. A mátrix kiértékelése a következ : mivel elmulasztott nyereségekr l van szó az a célunk, hogy az a legkisebb legyen. Így kiválasztjuk soronként a maximumokat, majd ezek közül a minimálisat, hiszen az így kapott eredménynél az adott cselekvést választva az elmulasztott nyereség csak ennél kevesebb lehet. a1: 7 a2: 11 a1 a3: 11 A döntés tehát: a1. 26


Operációkutatás

Döntésanalízis

V.Hurwicz-féle optimizmus együttható A pesszimista és a széls ségesen optimista magatartás közötti közbüls megoldás leírására jött létre ez a módszer. Hurwicz gondolata volt az optimizmus együttható bevezetése. Jele: , amelyre 0 1, és annak a hitnek a mértékét fejezi ki, amennyire a döntést hozó a legjobb esemény bekövetkezésére számít. Az optimista döntést hozónál =1, a pesszimistánál =0. Képezzük konvex lineáris kombinációját az egyes cselekvési lehet ségek legjobb és legrosszabb kimeneteleinek értékeivel. Ezeket Hurwicz-kifejezéseknek nevezzük. H1 (g ) = 21g + 4(1 g ) = 17g + 4 H 2 (g ) = 28g 5(1 g ) = 33g 5 H 3 (g ) = 17g + 6(1 g ) = 11g + 6 A Hurwicz-kifejezések els fokú kifejezései. ezért ábrázolhatjuk ezeket a kifejezéseket egy olyan koordinátarendszerben, amelyben x tengelyt tengelynek nevezzük. Az tengelynek csupán [0,1] intervallumára van szükség, mert 0 1. Az tengelyre =0 pontban állított mer leges tengelyt pesszimista tengelynek, az =1 pontban állított tengelyt optimista tengelynek nevezzük.

Az ábráról leolvasható, hogy ha 0 < 0,33 , akkor az a3 stratégiához tartozó Hurwicz érték a legnagyobb. = 0,33 , akkor H 1 ( ) = H 3 ( ) , azaz nem tudunk egyértelm9en dönteni. Itt alternatív optimum van. 0,33 < < 0,56 , akkor az a1 stratégiához tartozó Hurwicz érték a legnagyobb. = 0,56 , akkor H 2 ( ) = H 3 ( ) , azaz nem tudunk egyértelm9en dönteni. Itt alternatív optimum van. 0,56 < 1 , akkor az a2 stratégiához tartozó Hurwicz érték a legnagyobb.

27


Operációkutatás

Tartalomjegyzék

IX. Tartalomjegyzék I.

Mátrixok ................................................................................................................... 2

II.

Lineáris egyenletrendszerek és a Gauss-elimináció................................................. 7

III.

Lineáris programozási feladatok megoldása grafikus módszerrel ........................... 9

IV.

Szöveges feladatok ................................................................................................. 13

V.

Modellalkotás ......................................................................................................... 14

VI.

Szállítási feladat ..................................................................................................... 16

VII.

Játékelmélet ............................................................................................................ 21

VIII.

Döntésanalízis ........................................................................................................ 25

28


Operációkutatás. Glashütter Andrea

Recommend Documents