Tóth Georgina Nóra 1-2. gyakorlat OPERÁCIÓKUTATÁS

Tóth Georgina Nóra [email protected]

1-2. gyakorlat

OPERÁCIÓKUTATÁS

TÖRTÉNETI ÁTTEKINTÉS Ipari forradalom hatása a vállalatokra  II. világháború  Katonai hadműveletek (operációk)  Kutatók alkalmazása  Lendületes fejlődés  Számítástechnika robbanásszerű fejlődése 

OPERÁCIÓKUTATÁS CÉLJA, JELENTŐSÉGE 





Forráselosztás Bonyolultsági és szakosodási problémák megoldása Optimalizálási problémák

OPERÁCIÓKUTATÁS JELLEGZETESSÉGEI Operációkra (műveletekre) vonatkozó kutatás  Vállalaton belüli tevékenységek/műveletek összehangolására alkalmazzák  Tudományos megközelítés  Vállalattól függetlenül alkalmazható  Folyamat modell kialakítása lényeges vonások alapján  Optimális megoldás keresése 

MÓDSZEREK, SZABVÁNYOS ESZKÖZÖK Lineáris programozás  Szimplex módszer (George Dantzig 1947)  Dinamikus programozás  Sorbanállás elmélete  Raktározási problémák elmélete 

OPERÁCIÓKUTATÁS DEFINICIÓJA A döntéshozás olyan tudományos megközelítéseként írhatjuk le, amely szervezeti rendszerek működésével áll kapcsolatban. „operációkra vonatkozó kutatás”

OPERÁCIÓKUTATÁS DEFINICIÓJA 2. Az operációkutatás a valóságos életből eredő determinisztikus és sztochasztikus rendszerek modellezésével és ezekre vonatkozó döntések meghozatalával foglalkozik.

PROBLÉMA MEGFOGALMAZÁSA  Gyakorlati

életben zavaros problémák  Fontos tanulmányozni a rendszert  Célok meghatározása  Kényszerfeltételek  Vizsgálandó és egyéb területek közötti kapcsolatok megadása  Lehetséges cselekvéssorok  Időkorlátok Cél: a probléma egy jól definiált megfogalmazása!

MATEMATIKAI MODELL FELÉPÍTÉSE Probléma átfogalmazása, hogy elemzésre alkalmas legyen  Idealizált reprezentációk  n összefüggő döntés ->”döntési változók” x1,x2, ….xn A hatékonyságot a döntési változók függvényeként fejezzük ki. „CÉLFÜGGVÉNY” 

MATEMATIKAI MODELL FELÉPÍTÉSE Döntési változókra vonatkozó megszorítások „KÉNYSZERFELTÉTELEK” CÉLFÜGGVÉNY + KÉNYSZERFELTÉTELEK ÁLLANDÓI

BEMENETI vagy MODELLPARAMÉTEREK

FELADATTÍPUSOK  Termékek

olyan keverékének meghatározása, amely maximalizálja a hasznot  A földterület különböző termények vetésére vonatkozó olyan szétosztása, amely maximalizálja a nettó visszatérülést  Szennyeződés kiküszöbölésére irányuló módszerek olyan kombinációja, amelynek segítségével a levegő minőségére vonatkozó szabvány a lehető legkisebb költséggel érhető el

A MODELL MEGOLDÁSÁNAK LEVEZETÉSE Cél: a modellből levezetni a probléma egy megoldását  Szabványos algoritmusok  Programcsomagok Idealizált modell 

Nem biztos, hogy a megoldás a valós problémánál optimális

A MODELL MEGOLDÁSÁNAK LEVEZETÉSE

Optimális megoldás -> (Matematikai modell)

kielégítő megoldás (VALÓSÁG)

A MODELL ÉS A BELŐLE SZÁRMAZÓ MEGOLDÁS KIPRÓBÁLÁSA  Modell

helyességének ellenőrzése (helytelen interpretáció, rossz bemenő paraméter értékek)  Paraméter értékek megváltoztatása a hatás figyelemmel kísérése mellett  Visszatekintő ellenőrzés (történeti adatok+rekonstrukció) Jelentős-e a javulás? Hátránya: a múlt hűen reprezentálja a jövőt?

A MEGOLDÁSRA VONATKOZÓ ELLENŐRZÉSEK LÉTREHOZÁSA CÉL: A valóság változásainak követése  Rendszeres eljárások létrehozása  Kritikus paraméterek azonosítása (érzékenység vizsgálat)  Paraméterek statisztikailag szignifikáns változásának nyomon követése (folyamat ellenőrzési táblázatok, szabályozó kártyák)  Cselekvéssor kiigazítása 

A MEGOLDÁS MEGVALÓSÍTÁSA („ÜZEMBE HELYEZÉS”) 





Kritikus fázis A siker függ a felső vezetés támogatásának mértékétől Támogatás mellett a részvétel is fontos

A MEGOLDÁS MEGVALÓSÍTÁSÁNAK LÉPÉSEI („ÜZEMBE HELYEZÉS”)  Bevezetendő

megoldás, változtatás

ismertetése  Felelősség megosztása a bevezetést illetően  Érintett munkavállalók oktatása (operatív vezetés)  Változtatások elvégzése  Szükség esetén módosítás  Sikeres megoldás esetén periodikus alkalmazás

LINEÁRIS PROGRAMOZÁS

LINEÁRIS PROGRAMOZÁSI MODELL Célfüggvény

LINEÁRIS Korlátozó feltételek

A modellben szereplő összes függvény lineáris!

LINEÁRIS PROGRAMOZÁS LEGGYAKORIBB ALKALMAZÁSA Korlátozottan rendelkezésre álló források optimális elosztása egymással konkuráló célokat szolgáló tevékenységek között Pl.: termelőerők elosztása, nemzeti kincsek elosztása, kötvénycsomagok (portfolio) kiválasztása, logisztikai feladatok, szállítmányozás megszervezése, egészségügy (besugárzási terápia)

SZIMPLEX MÓDSZER 



Hatékony eljárás Lehetővé teszi óriási méretű lineáris programozási feladat megoldását

1. PÉLDA – WYNDOR ÜVEGGYÁRTÓ TÁRSASÁG Gyártott termékek:  Üvegajtó  Ablak

3 üzemben történik a gyártás: 1. üzem

Alumínium keretek, szerelvények

2. üzem

Fakeretek

3. üzem

Üveg alkatrészek

1. PÉLDA – WYNDOR ÜVEGGYÁRTÓ TÁRSASÁG  Veszteség

miatt több termék gyártását beszűntetik  Felszabadult kapacitás 2 új termék gyártására fordítják 1. termék

2m magas alumínium keretes ajtó

2. termék

Fakeretes dupla ablak (1x1,5m)

Mindkét termék gyártása leköti a 3. sz. üzem bizonyos kapacitását.

1. PÉLDA – WYNDOR ÜVEGGYÁRTÓ TÁRSASÁG

Milyen arányban keveredjék ennek a két terméknek a gyártása a legnagyobb profit elérése érdekében?

1. PÉLDA – WYNDOR ÜVEGGYÁRTÓ TÁRSASÁG Operációkutató csoport meghatározta: 1. Mindkét új termékre nézve a rendelkezésre álló százalékos kapacitást mind a három üzemben 2. Mindkét új termék esetében az egységnyi termék/perc termeléshez szükséges százalékos arányt 3. Egységnyi profitot mindkét termék esetén

1. PÉLDA – WYNDOR ÜVEGGYÁRTÓ TÁRSASÁG Üzem

Termék 1. termék 2. termék

Szabad kapacitás

1.

1

0

4

2.

0

2

12

3.

3

2

18

Profit/egység

3€

5€

-

1. PÉLDA – WYNDOR ÜVEGGYÁRTÓ TÁRSASÁG (MATEMATIKAI MODELL MEGFOGALMAZÁSA) Jelölések: x1, x2 – 1. ill. a 2. termék percenként termelt egységeinek száma / döntési változók Z – percenkénti profithozzájárulás

Célfüggvény: Z=3 x1 +5 x2

max Üzem

Termék

Szabad kapacitá s

1. termék

2. termék

1.

1

0

4

2.

0

2

12

3.

3

2

18

Profit/ egység

3€

5€

-

1. PÉLDA – WYNDOR ÜVEGGYÁRTÓ TÁRSASÁG (MATEMATIKAI MODELL MEGFOGALMAZÁSA) Megszorítások: Az 1 termék minden percenként megtermelt egysége az 1,. Üzem 1% kapacitását venné el a rendelkezésre álló 4-ből x1≤4 Hasonlóan a 2. üzemre: 2x2≤12 Üzem Termék Szabad x2≤6 kapacitá 1. 2. s

termék

termék

1.

1

0

4

2.

0

2

12

3.

3

2

18

Profit/ egység

3€

5€

-

1. PÉLDA – WYNDOR ÜVEGGYÁRTÓ TÁRSASÁG (MATEMATIKAI MODELL MEGFOGALMAZÁSA) Hasonlóan a 3. üzemre: 3x1 + 2x2≤18 A termelés nem lehet negatív, tehát: x1≥0 x2≥0 Üzem

Termék

Szabad kapacitá s

1. termék

2. termék

1.

1

0

4

2.

0

2

12

3.

3

2

18

Profit/ egység

3€

5€

-

MATEMATIKAI MODELL MEGFOGALMAZÁSA Z=3 x1 +5 x2

max

Feltéve, hogy x1

≤4 x2≤6 3x1 + 2x2≤18 x1 ≥0 x2≥0

Üzem

Termék

Szabad kapacitá s

1. termék

2. termék

1.

1

0

4

2.

0

2

12

3.

3

2

18

Profit/ egység

3€

5€

-

MEGOLDÁSOK KERESÉSE x2 9

Célfüggvény Z=3 x1 +5 x2 3x1+2x2≤18

6

Lehetséges megoldások halmaza

4

6

x1

LINEÁRIS PROGRAMOZÁSI MODELL ÁLTALÁNOSAN Jelölések: m db korlátozott forrás (1, 2,…,m) n db egymással konkuráló tevékenység (1,2,…,n) Döntési változó xj (j=1,2,…n) Z –együttes eredményesség megválasztott mértéke Cj – Z azon növekedése, amely xj egységnyi növelése okozna (j=1,2,…n) bi – i. forrásból rendelkezésre álló mennyiség (i=1,2,…n) aij- i-ik forrásnak az egységnyi j-ik tevékenység által felhasznált mennyisége(i=1,2,…m)(j=1,2,…n)

LINEÁRIS PROGRAMOZÁSI MODELL ADATAI Forrás

Tevékenység

Szabad forráskapacitás

1

2

…..

n

1

a11

a12

……..

a1n

b1

2

a21

a22

……….

a2n

b2

. . .

. . .

. . .

…….. . . …….

m

am1

am

. . . amn

2

ΔZ/egységnyi tevékenység

c1

c2

Tevékenység szintje

x1

x2

……….

cn xn

bm

A MODELL EGY STANDARD ALAKJA

Z  c1x1  c 2 x 2  ...  c n x n  max

Célfüggvény

feltéve, hogy a11x1  a12 x 2  ...  a1n x n  b1 a 21x1  a 22 x 2  ...  a 2 n x n  b 2

Megszorításo k/ funkcionális feltételek

a m1x1  a m 2 x 2  ...  a m nx n  b m és x1  0, x 2  0,....., x n  0,

Nemnegatívitási feltételek

SZIMPLEX MÓDSZER Kezdő lépés

Iteratív lépés

Optimalitási vizsgálat

Nem

Igen Elértük a kívánt eredményt?

STOP

SZIMPLEX MÓDSZER Lehetséges csúcspontmegoldások tulajdonságai: a) ha pontosan egy optimális megoldás létezik, akkor az szükségszerűen egy lehetséges csúcspontmegoldás b) ha egyszerre több optimális megoldás létezik, akkor kell lennie közöttük legalább két szomszédos lehetséges csúcspontmegoldásnak A lehetséges csúcspontmegoldások véges sokan vannak. Ha egy csúcspontmegoldás legalább olyan jó Z szempontjából mint a szomszédos lehetséges csúcspontmegoldások, akkor legalább olyan jó vagy jobb, mint az összes többi lehetséges csúcspontmegoldás, azaz optimális megoldás.

Üzem

MEGOLDÁSOK KERESÉSE x2 9

Termék 1. termék

2. termék

1.

1

0

4

2.

0

2

12

3.

3

2

18

Profit/ egység

3€

5€

-

Célfüggvény Z=3 x1 +5 x2

3x1+2x2≤18 6

Lehetséges megoldások halmaza

4

6

Szabad kapacitá s

x1

LINEÁRIS PROGRAMOZÁS ELŐFELTÉTELEI 

Arányosság

Külön-külön minden egyes tevékenységre N db tevékenységből válasszunk egyet (k.) xj =0, minden j=1,2,…..,n esetén és (j≠k) (1) Z kifejezhető ck xk módon (2) i-ik forrás felhasználása aik xk 

Mindkét mennyiség arányos a k. tevékenység szintjével (minden k=1,2,….,n esetén)

LINEÁRIS PROGRAMOZÁS ELŐFELTÉTELEI Additivitás  Összes tevékenységre együtt vizsgáljuk  Lehetséges kölcsönhatások vizsgálata 

Követelmény: Bármely x1 , x2 ,…., xn ) tevékenységi szintek mellett mind a hatékonyság mértéke (Z), mind a források teljes felhasználása a megfelelő mennyiségek összegeként legyen kifejezhető (ne legyenek kevert tagok!)

LINEÁRIS PROGRAMOZÁS ELŐFELTÉTELEI Oszthatóság  Valóságban a döntési változók értéke bizonyos esetekben csak egész értéket vehetnek fel.  Sokszor az optimális eredményhez kapott számok nem egész értékek. 



Oszthatósági szabály: a tevékenységek egységei bármilyen arányban oszthatók, a döntési változók pedig tört értékeket is felvehetnek.

LINEÁRIS PROGRAMOZÁS ELŐFELTÉTELEI 

Bizonyosság

Az összes paraméter (aij, bi, cj) mind ismert konstansok.  Valós problémák esetében ritka  Érzékenységi vizsgálat

TOVÁBBI PÉLDA LÉGSZENNYEZÉSSZABÁLYOZÁS

Nori&Leets Társaság – Steeltown  Légszennyezési probléma megoldása  Legjelentősebb légszennyező anyagok 

Szennyező

Éves kibocsájtás előírt csökkentése (millió pound)

Por

60

Kéndioxidok

150

Szénhidrogének

125

LÉGSZENNYEZÉS-SZABÁLYOZÁS (PÉLDA)  1. 2.

2 okozója a légszennyezésnek: Olvasztókemencék Nyílt-tüzelésű kohók

Légszennyezés csökkentéséhez lehetőségek: (1) Kémények magasságának megnövelése (kétséges) (2) Szűrő (gázcsapdák) a kéményekben (3) Különböző hatásfokú tisztító anyagok keverése a kohók üzemanyagaihoz

LÉGSZENNYEZÉS-SZABÁLYOZÁS (PÉLDA)

Magasabb kémények

Szűrők

Olvasztókemence

Olvasztókemence

Nyílttüzelésű kohó

Jobb tüzelőanyagok Nyílttüzelésű kohó

Olvasztókemence

Nyílttüzelésű kohó

Por

12

9

25

20

17

13

Kéndioxid

35

42

18

31

56

49

Szénhidrogé n

37

53

28

24

29

20

2. táblázat Az egyes módszerek korlátai

A fenti megoldások az előző táblázatba foglalt határig bármilyen kapacitással alkalmazhatók. Együttes alkalmazása lehetséges.

LÉGSZENNYEZÉS-SZABÁLYOZÁS (PÉLDA)

Módszer

Olvasztókemence

Nyílt-tüzelésű kohó

Magasabb kémények

8

10

Szűrők

7

6

Jobb tüzelőanyagok

11

9

3. táblázat Az egyes módszerek éves költségei teljes kihasználtság mellett (millió $)

LÉGSZENNYEZÉS-SZABÁLYOZÁS (PÉLDA) Mikor az adatokat megvizsgálták, világossá vált, önmagában egyik módszer sem elegendő.  Mindhárom módszer teljes kapacitásának bevetése, több mint elfogadható eredménnyel járna. (Nagyon magas költségek mellett.)  Kombinációkat kell vizsgálni. 

LÉGSZENNYEZÉS-SZABÁLYOZÁS (PÉLDA) Módszer

Olvasztókemence

Nyílt-tüzelésű kohó

Magasabb kémény

x1

x2

Szűrő

x3

x4

Jobb tüzelőanyag

x5

x6

Döntési változók

LÉGSZENNYEZÉS-SZABÁLYOZÁS (PÉLDA) Hat döntési változó: xj (j=1,2,…,6) Matematikai modell: Min Z=8 x1 +10 x2 +7 x3 +6 x4 + 11x5 +9 x6 1.

Szennyezés csökkentése:

12 x1 +9 x2 +25 x3 +20 x4 + 17 x5 +13 x6 ≥ 60 35 x1 +42 x2 +18 x3 +31 x4 + 56 x5 +49 x6 ≥ 150 37 x1 +53 x2 +28 x3 +24 x4 + 29 x5 +20 x6 ≥ 125

LÉGSZENNYEZÉS-SZABÁLYOZÁS (PÉLDA) 2. Technológia: xj ≤1 minden (j=1,2,…,6) esetén 3. Nemnegatívitás: xj ≥0 minden (j=1,2,…,6) esetén

LÉGSZENNYEZÉS-SZABÁLYOZÁS (PÉLDA) Módszer

Olvasztókemence

Nyílt-tüzelésű kohó

Magasabb kémény

x1

x2

Szűrő

x3

x4

Jobb tüzelőanyag

x5

x6

Döntési változók

Megoldás: (x1 ,x2 ,x3 ,x4 ,x5 ,x6)= (1, 0.623, 0.343, 1, 0.048, 1)

Érzékenységi vizsgálatot végeztek, majd a programot megvalósították.

SZÁLLÍTÁSI FELADAT Speciális

lineáris programozási

feladat Gyakori valós problémák Nagyszámú feltétel Sok döntési változó Sok 0 van a változók között (aij többsége) Speciális szerkezet

SZÁLLÍTÁSI FELADAT Feltételek

és együttható táblázata/mátrixa   a  11 A=  a.21  .   am1

a12 ...... a22 ......

am 2 ......

  a1n   a2 n     amn 

SZÁLLÍTÁSI FELADAT

Nem

nulla együtthatók kitűntetett helyen szerepelnek Számítási megtakarítás

SZÁLLÍTÁSI FELADAT MINTAPÉLDA  Borsókonzerv

A

termelés 3 konzervgyárban folyik  szállítás tehervonattal  4 értékesítő helyre  Fő kiadás a szállítási költség  Cél: szállítási költség csökkentése

SZÁLLÍTÁSI FELADAT MINTAPÉLDA 

Megbecsülték:

A következő szezonra várható termelést  Kihelyezés mennyiségét az adott árukból  Egy tehervagonra eső szállítási költségét 

A P&T TÁRSASÁG SZÁLLÍTÁSI ADATAI

Konzervgyár

Áruház

Terme -lés

1

2

3

4

1

464

513

654

867

75

2

352

416

690

791

125

3

995

682

388

685

100

80

65

70

85

Kihelyezés

SZÁLLÍTÁSI FELADAT MINTAPÉLDA Z a teljes szállítási költség  Xij (i=1,2,3 ; j=1,2,3,4 ) az i-ik konzervgyárból a j-ik áruházba szállítandó 

Célfüggvény:

Z  464 x11  513 x12  654 x13  867 x14  352 x21  416 x22   690 x23  791x24  995 x31  682 x32  388 x33  685 x34 Z  min

SZÁLLÍTÁSI FELADAT MINTAPÉLDA

Konzervgyár feltételei

Feltételek: =75

x11  x12  x13  x14

=125

x21  x22  x23  x24 x31  x32  x33  x34  x21

x11

x14

=65

 x32  x33

 x23

x13

=80

 x31  x22

x12

 x24

=100

=70  x34

=85

Az áruház feltételei

SZÁLLÍTÁSI FELADAT MINTAPÉLDA Feltételek:

xij  0 , (i=1,2,3; j=1,2,3,4)

SZÁLLÍTÁSI FELADAT MINTAPÉLDA

x11 x12 x13 x14 x21 x22 x23 x24 x31 x32 x33 x34 1 1 1 1    1 1 1 1   1 1 1 1    A 1 1 1    1  1 1   1 1 1    1 1 1

SZÁLLÍTÁSI FELADAT MINTAPÉLDA A feladat optimális megoldása:

x11  0, x12  20, x13  0, x14  55 x21  80, x22  45, x23  0, x24  0 x31  0, x32  0, x33  70, x34  30

SZÁLLÍTÁSI FELADAT MODELLJE TERMINOLÓGIA

Mintapélda

Általános feladat

Egy vagon borsókonzerv

Egységnyi áru

Három konzervgyár

m tárolóhely

Négy áruház

n felvevőhely

Az i-ik konzervgyár termelése

si, az i-ik tárolóhely készlete

A j-ik áruháznak történő juttatás

dj , a j-ik felvevőhely kereslete

Vagononkénti szállítási költség az i-ik konzervgyárból a j-ik áruházba

cij, egységnyi áru szállítási költsége az i-ik tárolóhelyről a j-ik felvevőhelyre

SZÁLLÍTÁSI FELADAT MODELLJE Z-a teljes szállítási költség  xij az i-ik tárolóhelyről a j-ik felvevőhelyre szállítandó egységek mennyisége 

m n

Z    cij xij , feltéve, hogy i 1 j 1

n

 xij

j 1

m

 si , i  1,2,....m,  xij  d j , j  1,2,....n, és i 1

xij  0 minden i - re és j - re

SZÁLLÍTÁSI FELADAT MODELLJE

Tárolóhely

Felvevőhely

Kereslet

Készle t

1

2

…

n

1

c11

c12

…

c1n

S1

2 . . m

. . cm1

cm2

…

cmn

. . sm

d1

d2

…

dn

SZÁLLÍTÁSI FELADAT MODELLJE

x11 x12 x13 ..x1n x21 x22 x23 ..x2 n ... xm1 xm 2 xm 3 ..xmn 1 1 1.. 1    1 1 1.. 1...   1 1 1.. 1    A 1 1 1    1  1 1   1 1 1    1 1 1

SZÁLLÍTÁSI FELADAT MODELLJE

Csak akkor létezik megengedett megoldása a modellnek ha m

 si

i 1

n

 dj j 1

A feltételek megkövetelik, hogy m

 si

i 1

n

m n

j 1

i 1 j 1

és  d j egyenlő   xij

OPERÁCIÓKUTATÁS OPTIMALIZÁLÁSI FELADATOK 

A matematikai (számoló) modell elkészítése    



Paraméterek elhelyezése Feltételezett megoldás(ok) elhelyezése Számoló cellák elkészítése (Kívánt értékek elhelyezése)

Solver – Megoldáskereső használata – Paraméterek megadása  

Célcella megadása Max, Min, vagy konkrét érték

Változó cellák megadása  Korlátozó feltételek  Az eredmény, - ha van, - értékelése, magyarázata 

A SOLVER HASZNÁLATA a megoldás menete, a modellek kialakítása és leképzése  lineáris egyenletrendszerek megoldása  egyszerű optimalizálási probléma megoldása 