Economic subjects | Operational Research » GDF Dr. Kósa András - Operációkutatás előadásvázlatok

Gábor Dénes Főiskola FML-029F/01 ELŐADÁSVÁZLATOK OPERÁCIÓKUTATÁS 207 Vezetőtanár: DR. KÓSA ANDRÁS 2001/2002 Informatikai Rendszerek Intézete Operációkutatás – 207 1. oldal Gábor Dénes Főiskola TANKÖNYVEK 1. Hilier-Liebermann: Bevezetés az operációkutatásba, LSI Oktatóközpont, 1994 (H-L) 2. Kósa A: Optimalizált eljárások I-II, LSI Oktatóközpont, 1989 (K I; K II) 3. Csernyák L-Szarka Z-Szelezsán J: Matematika I, LSI Oktatóközpont, 1994 (SZ; 350-407. o) Ajánlott kézikönyv Kósa A.: Optimumszámítási modellek, Műszaki Könyvkiadó, 1979 (K) Informatikai Rendszerek Intézete Operációkutatás – 207 2. oldal Gábor Dénes Főiskola BEVEZETÉS Az "ókorban" is vizsgált szélsőértékproblémák Az "újkori" problémák születése geometriai problémák fizikai problémák műszaki problémák gazdasági problémák Konkrét feladatok a brachisztochron-probléma a minimális felszínű forgásfelület

problémája Informatikai Rendszerek Intézete Operációkutatás – 207 3. oldal Gábor Dénes Főiskola A SZÉLSŐÉRTÉKRŐL ÁLTALÁBAN A természetben, az egyes tudományokban általában FELTÉTELES SZÉLSŐÉRTÉKPROBLÉMÁK vetődnek fel. Példák: izoperimetrikus problémák gazdasági tervezés műszaki feladatok A dualitás mint a feltételes szélsőértékproblémák egyik sajátos velejárója. Informatikai Rendszerek Intézete Operációkutatás – 207 4. oldal Gábor Dénes Főiskola ISMÉTLÉS A KÖZÉPISKOLAI GEOMETRIÁBÓL (L. SZ) szám, számpár, számhármas számegyenes koordinátasík koordinátatér ("tér") pont két pont távolsága pont adott sugarú környezete ponthalmaz belseje ponthalmaz külseje ponthalmaz határa Informatikai Rendszerek Intézete Operációkutatás – 207 5. oldal Gábor Dénes Főiskola vektorok vektorok számszorosa vektorok összege bázis R2-ben és R3-ban vektorok koordinátás megadása vektorok

skaláris szorzata konvex ponthalmazok síkbeli egyenes egyenlete, ha adva van • egy pontja és normálvektora • egy pontja és irányvektora • két pontja Informatikai Rendszerek Intézete Operációkutatás – 207 6. oldal Gábor Dénes Főiskola félsíkok a koordinátasíkban ax1 + bx2  d képe (a, b, c  R) konvex sokszög mint félsíkok közös része félterek a koordinátatérben ax1 + bx2 + cx3  d (a, b, c  R) konvex poliéder mint félterek közös része Informatikai Rendszerek Intézete Operációkutatás – 207 7. oldal Gábor Dénes Főiskola VALÓS FÜGGVÉNY ABSZOLÚT SZÉLSŐÉRTÉKÉNEK ÉRTELMEZÉSE Elegendő pl. csak a maximumot értelmezni. A f: A  R aA f(x)  f(a) minden A-beli x-re a, f(a) elnevezése A x a Informatikai Rendszerek Intézete Operációkutatás – 207 8. oldal Gábor Dénes Főiskola VALÓS FÜGGVÉNY FELTÉTELES SZÉLSŐÉRTÉKÉNEK AZ ÉRTELMEZÉSE Elegendő pl. csak a minimumot értelmezni

A f: A  R B  A, B  , B  A minden B-beli x-re f(x)  f(a) x B A a Informatikai Rendszerek Intézete Operációkutatás – 207 9. oldal Gábor Dénes Főiskola A legegyszerűbb klasszikus szélsőérték-feladat (2) (2) (1) (2) (1) (2) (1) (1) Elégséges feltétel lokális minimumra "jó" függvény esetében: f(a)=0; f(a)>0. Informatikai Rendszerek Intézete Operációkutatás – 207 10. oldal Gábor Dénes Főiskola RÖVID ÁTTEKINTÉS AZ OPTIMUMSZÁMÍTÁS FONTOSABB MÓDSZEREIRŐL geometriai módszerek feltétel nélküli szélsőértékproblémák a differenciálszámítás módszereivel feltételes szélsőértékproblémák variációszámítás lineáris programozás matematikai programozás dinamikus programozás irányításelmélet stb. A matematika alkalmazásának mintegy 70%-át szélsőérték-feladatok (extrémumkeresés, optimumszámítás) teszi ki. Informatikai Rendszerek Intézete Operációkutatás

– 207 11. oldal Gábor Dénes Főiskola VEKTOROK ÉS MÁTRIXOK • N a természetes számok halmaza (0  N) • R a valós számok halmaza • n  N esetén Rn a rendezett szám-n-esek halmaza • a  Rn   ai  R (i=1,,n) olyan, hogy a = (a1,,an) • (def., ill tétel, a felépítés szerint) (a1,an)=(b1,,bn) ai=bi(i=1,,n) Informatikai Rendszerek Intézete Operációkutatás – 207 12. oldal Gábor Dénes Főiskola Egy belső és egy külső művelet • (a1,,an)+(b1,,bn):=(a1+b1,,an+bn) (bármely a, b  Rn esetén) • (a1,,an):= (a1,,an) (bármely   R és a  Rn esetén) • Geometriai háttér, gazdasági feladatok, számpéldák, elnevezések Informatikai Rendszerek Intézete Operációkutatás – 207 13. oldal Gábor Dénes Főiskola • Mátrixok megadása: a a . ( A =) . . a   11   21       n1 a12 . a1m  a 22 . a 2m  an2 . a      nm  (=:[aij]) n x m-es

valós mátrix (aij  R, i=1,,n; j=1,,m) • az n x m méretű valós mátrixok halmaza: Rnxm • aij A i-edig sorában és j-edik oszlopában álló komponens, koordináta (régiesen: elem) Informatikai Rendszerek Intézete Operációkutatás – 207 14. oldal Gábor Dénes Főiskola • Rnx1 n dimenziós oszlopvektorok halmaza • R1xn n dimenziós sorvektorok halmaza • A*:=[aij] ( Rmxn) A transzponáltja • azonosítjuk Rn-et Rnx1-gyel • értelemszerű szereposztással: a . . (a1,,an)= . a   1              n  = [a1,an]* Informatikai Rendszerek Intézete Operációkutatás – 207 15. oldal Gábor Dénes Főiskola • a1,,an  Rnx1 (=Rn) Az előző tábla mátrixa így is felírható: (A=) [a1,,an] • a sorvektorokkal történő felírás • számpéldák • mátrixok összege (csak azonos mértékűeké) • mátrixok állandószorosa • számpéldák • egy n x m méretű mátrixnak csak

valamely m x k méretű mátrixszal való szorzatát értelmezzük: általános formula, számpéldák, speciális esetek • egységmátrixok Informatikai Rendszerek Intézete Operációkutatás – 207 16. oldal Gábor Dénes Főiskola • vektorok lineáris függetlensége és összefüggése • lineáris tér, dimenzió, bázis • rangtétel: bármely mátrix sorai (sorvektorai) között ugyanannyi lineárisan független vektor van, mint az oszlopai között • mátrix rangja • az elemi bázistranszformáció fogalma Informatikai Rendszerek Intézete Operációkutatás – 207 17. oldal Gábor Dénes Főiskola MINORMÁTRIX Legyen n, m  N; n, m > 1; A n x m méretű mátrix i  1,,n; j  1,,m Az Aij az az (n-1)x(m-1) méretű mátrix, amelyet A-ból úgy származtatunk, hogy elhagyjuk az i-edik sorát és a j-edik oszlopát. Informatikai Rendszerek Intézete Operációkutatás – 207 18. oldal Gábor Dénes Főiskola AZ ELEMI

BÁZISTRANSZFOMÁCIÓ b1,,bk,bn bázis Rn-ben c1,,ck,,cn  R; ck  0 x1,,xk,,xn  R c:=c1b1++ckbk++cnbn x:=x1b1+xkbk++xnbn c-t bevisszük a bázisba bk helyébe (c "bemegy" a bázisba: bk "kijön" a bázisból) Informatikai Rendszerek Intézete Operációkutatás – 207 19. oldal Gábor Dénes Főiskola x komponensei az "új" b1,,c,bn bázisban: 1. komponens: x1 − xc k c1 k . . . k. komponens: . xk ck . . n. komponens: x n − xc k cn k ck: az ún. generáló elem Informatikai Rendszerek Intézete Operációkutatás – 207 20. oldal Gábor Dénes Főiskola RÖVID ÁTTEKINTÉS AZ OPTIMUMSZÁMÍTÁS FONTOSABB MÓDSZEREIRŐL geometriai módszerek feltétel nélküli szélsőértékproblémák a differenciálszámítás módszereivel feltételes szélsőértékproblémák variációszámítás lineáris programozás matematikai programozás dinamikus programozás irányításelmélet stb. A matematika alkalmazásának mintegy

70%-át szélsőérték feladatok (extrémumkeresés, optimumszámítás) teszik ki. Informatikai Rendszerek Intézete Operációkutatás – 207 21. oldal Gábor Dénes Főiskola LINEÁRIS ALGEBRAI EGYENLETRENDSZER Adottak: m, n  N A  Rnxm b  Rn Ax=b megoldás x  Rm; (x1,,xm)  Rm; x1,,xm (hagyományosan) elnevezések Informatikai Rendszerek Intézete Operációkutatás – 207 22. oldal Gábor Dénes Főiskola RÉSZLETES KIÍRÁS a a .a1m  a a .a2m   .  .   . a a .anm    11 12   21 22        n1 n2 x1  b1     x2  b2  .  =   .    .    xm  b   n            KOORDINÁTA FELÍRÁS a x + a12 x2 +.+ a1m x m = b1 a x + a22 x2 +.+ a2m xm = b2 . . . a x + an2 x2 +.+ an x m = bn   11 1    21 1        n1 1 Informatikai

Rendszerek Intézete Operációkutatás – 207 23. oldal Gábor Dénes Főiskola NÉGYZETES MÁTRIX DETERMINÁNSA a) n: = 2; , , ,   R    α β  α β  det :=     γ δ  γ δ       b) n: = 3 A  R3x3 a a12 a13  det A:= A := a a 22 a 23  := a a 32 a 33    11   21   31 Informatikai Rendszerek Intézete Operációkutatás – 207 24. oldal Gábor Dénes Főiskola a  a  a22 a23  a a 23  22   21  21 a − a + a =    12  13  a32 a33  a31 a33  a31 a32    11   a11⋅detA11 - a12 ⋅detA12 + a13 ⋅detA13 c) n  N; A  Rnxm det A := A := a a12 . a1n  a a 22 . a 2n    11   21 .  .   n1  a a n2 . a     nn   := ∑(−1)1 + k ⋅det A1k n k =1 Informatikai Rendszerek Intézete Operációkutatás – 207

25. oldal Gábor Dénes Főiskola +-+- -+-+ +-+- . . . 1. PÉLDA A D-t a 3. oszlopa, a harmadrendűeket pedig az 1. soruk szerint fejtjük ki 1 −1 0 2 1 −1 2 D:= 3 4 −1 6 = 0⋅ . − (−1)⋅ 4 − 4 5 + 4 −4 2 5 1 1 −1 1 1 3 −1 1 −1 2 1 −1 2 2⋅ 3 4 6 + (−3) 3 4 6 = 1 1 −1 4 −4 5 Informatikai Rendszerek Intézete Operációkutatás – 207 26. oldal Gábor Dénes Főiskola 1⋅ − 4 5 − (−1) 4 5 + 2⋅ 4 − 4 + 1 −1 1 1 1 1        3 4 3 6 4 6 2⋅ 1⋅ − (−1) +2 + 1 −1 1 1  1 −1        3 4 3 6 4 6 (−3)⋅ 1⋅ − (−1) +2  = . 4 5 4 − 4  −4 5 Informatikai Rendszerek Intézete Operációkutatás – 207 27. oldal Gábor Dénes Főiskola A CRAMER-FÉLE SZABÁLY n  N, A  Rnxn, b  Rn Ax = b ill. koordinátákban felírt változata: a11x1 + a12x2 + + a1n = b1 (1) a21x1 + a22x2 + + a2n = b2 . . . an1x1 + an2x2 + + ann = bn Informatikai

Rendszerek Intézete Operációkutatás – 207 28. oldal Gábor Dénes Főiskola Legyen: D:= det A b1 a12 . a1n b2 a22 a2n ;.; D1 = . . bn an2 ann a 11 . a 1(n - 1) b 1 a 21 a 2(n - 1) b 2 Dn = . . a 2n a n(n - 1) b n (1) megoldás (Cramer-szabály): xi = Di D (i = 1,,n). Informatikai Rendszerek Intézete Operációkutatás – 207 29. oldal Gábor Dénes Főiskola (1) kibővített mátrixa: a11.a1m; b1   . .  .  an1 anm; bm          TÉTEL: Az (1) egyenletrendszernek pontosan akkor van megoldása, ha a mátrixának és a kibővített mátrixának a rangja egyenlő. Informatikai Rendszerek Intézete Operációkutatás – 207 30. oldal Gábor Dénes Főiskola A GAUSS-FÉLE MÓDSZER Egy, már a kívánt alakban felírt egyenletrendszer: x1 - 2x2 + 3x3 = 9 x2 + 3x3 = 5 x3 = 2 Megengedett változtatások a) felcserélés b) R {0}-beli számmal való szorzás c) összeadás Mátrixok hasonlósága Informatikai

Rendszerek Intézete Operációkutatás – 207 31. oldal Gábor Dénes Főiskola 1. PÉLDA x1 + 2x2 + 3x3 = 6 2x1 + 3x2 + 2x3 = 6 -x1 + x2 + x3 = 4 [I(-2)+II; I+III] x1 + 2x2 + 3x3 = 6 -x2 - 4x3 = -6 3x2 + 4x3 = 10 Informatikai Rendszerek Intézete Operációkutatás – 207 32. oldal Gábor Dénes Főiskola [I(3)+III] x1 + 2x2 + 3x3 = 6 -x2 - 4x3 = -6 -8x3 = -8 x3 = 1; x2 = 2; x = -1 (-1,2,1) Az egyenletrendszer EGYÉRTELMŰEN MEGOLDHATÓ. Informatikai Rendszerek Intézete Operációkutatás – 207 33. oldal Gábor Dénes Főiskola 2. PÉLDA x1 - 3x2 + x3 = 1 2x1 - x2 - 2x3 = 2 x1 + 2x2 - 3x3 = -1 [I(-2)+II; I(-1)+III] x1 - 3x2 + x3 = 1 5x2 - 4x3 = 0 5x2 - 4x3 = -2 Informatikai Rendszerek Intézete Operációkutatás – 207 34. oldal Gábor Dénes Főiskola [II(-1)+III] x1 - 3x2 + x3 = 1 5x2 - 4x3 = 0 0 = -2 Az utolsó egyenlőség nem állhat fenn, ezért az egyenletrendszer NEM OLDHATÓ MEG. Informatikai Rendszerek Intézete

Operációkutatás – 207 35. oldal Gábor Dénes Főiskola 3. PÉLDA x1 + x2 - 3x3 = -1 x2 - x3 = 0 -x1 + 2x2 =1 [I+III] x1 + x2 - 3x3 = -1 x2 - x3 = 0 3x2 - 3x3 = 0 Informatikai Rendszerek Intézete Operációkutatás – 207 36. oldal Gábor Dénes Főiskola [II(-3)+III] x1 + x2 - 3x3 = -1 x2 - x3 = 0 0=0 x2 = x3 x1 = -x2 + 3x3 - 1 = 2x3 - 1 VÉGTELEN SOK MEGOLDÁS van; bármely x3 R mellett: (2x3 -1, x3, x3) Informatikai Rendszerek Intézete Operációkutatás – 207 37. oldal Gábor Dénes Főiskola Az 1. PÉLDA mátrixok ún hasonlósági transzfomációval: 1 2 3 ; 6  2 3 2 ; 6  -1 1 1 ; 4          1 2 3 ; 6   0 -1 - 4 ; - 6  0 3 4 ; 10         1 2 3 ; 6   0 -1 - 4 ; - 6 0 0 - 8 ; - 8         (Párhuzamosan mutatandó be a 32-34. oldallal.) Informatikai Rendszerek Intézete Operációkutatás –

207 38. oldal Gábor Dénes Főiskola Az 1. példa az ún Gauss-Jordan-féle módszerrel Az egyenlet: x1 + 2x2 + 3x3 = 6 2x1 + 3x2 + 2x3 = 6 -x1 + x2 + x3 = 4 A kibővített mátrix: 1 2 3 ; 6   0 -1 - 4 ; - 6 0 0 - 8 ; - 8         Informatikai Rendszerek Intézete Operációkutatás – 207 39. oldal Gábor Dénes Főiskola [II(-1); III:(-8)] 1 2 3 ; 6   0 1 4 ; 6 0 0 1 ; 1          [II(-2)+I] 1 2 - 5 ; - 6   0 1 4 ; 6 0 0 1 ; 1          Informatikai Rendszerek Intézete Operációkutatás – 207 40. oldal Gábor Dénes Főiskola [III(5)+I; III(-4)+I; III(-4)+II] 1 0 0 ; -1  0 1 0 ; 2 0 0 1 ; 1          Ez a mátrix az x1 = -1 x2 =2 x3 = 1 egyenletrendszernek felel meg (ugyanaz, mint korábban). Informatikai Rendszerek Intézete

Operációkutatás – 207 41. oldal Gábor Dénes Főiskola 4. PÉLDA Az egyenlet: 2x1 + 4x2 - 2x3 = 0 3x1 + 5x2 =1 A kibővített mátrix 2 4 - 2 ; 0  3 5 0 ; 1     [I:2] 1 2 - 1 ; 0   3 5 0 ; 1     [I(-3)+II] 1 2 -1 ; 0  0 -1 3 ; 1     Informatikai Rendszerek Intézete Operációkutatás – 207 42. oldal Gábor Dénes Főiskola [II(-1)] 1 2 -1 ; 0  0 1 - 3 ;-1     [II(-2)+I] 1 0 5 ; 2  0 1 - 3 ; -1     Az ekvivalens egyenletrendszer x1 + 5x3 = 2 x2 - 3x3 = -1 x2 = 3x3 - 1; x1 = -5x3 + 2 VÉGTELEN SOK MEGOLDÁS van: bármely x3  R mellett (-5x3 + 2, 3x3-1, x3) Informatikai Rendszerek Intézete Operációkutatás – 207 43. oldal Gábor Dénes Főiskola A LINEÁRIS PROGRAMOZÁS STANDARD FELADATA Adottak: m, n  N; A  Rmxn, b  Rm, c  Rn Feladat: Meghatározandó az(ok) az x  Rn

vektor(ok), amely(ek)re maximalizálandó z = c1x1 + + cnxn, feltéve, hogy Ax  b, és x0 [amennyiben ilyen vektor(ok) van(nak)] • jelölésmagyarázat • legalább öt konkrét gyakorlati feladat • a lineáris programozási modell adatai Informatikai Rendszerek Intézete Operációkutatás – 207 44. oldal Gábor Dénes Főiskola MINTAPÉLDA z = 3x1 + 5x2  max, feltéve, hogy x1  4 2x2  12 3x1 + 2x2  18, és x1  0, x2  0 Informatikai Rendszerek Intézete Operációkutatás – 207 45. oldal Gábor Dénes Főiskola A MEGENGEDETT MEGOLDÁSOK HALMAZA x2 10 3x1+2x2=18 8 x1=4 6 2x2=12 4 2 0 2 4 6 8 x1 Informatikai Rendszerek Intézete Operációkutatás – 207 46. oldal Gábor Dénes Főiskola A MINTAPÉLDA GRAFIKUS MEGOLDÁSA x2 10 8 Z=36=3x1+5x2 6 (2.6) Z=20=3x1+5x2 4 Z=10=3x1+5x2 2 0 2 4 6 8 x1 Informatikai Rendszerek Intézete Operációkutatás – 207 47. oldal Gábor Dénes Főiskola TERMINOLÓGIA A

lineáris programozási feladat • döntési változói • megoldásai (következetlen elnevezés) • lehetséges megoldásai • lehetséges csúcspontmegoldásai • optimális megoldásai Informatikai Rendszerek Intézete Operációkutatás – 207 48. oldal Gábor Dénes Főiskola TÉTEL A lineáris programozási feladat optimális megoldása csak valamelyik csúcspontmegoldás lehet. • analógiák • az alábbi 3 eset valamelyike áll fenn: a) nincs optimális megoldása; b) pontosan egy optimális megoldás van; c) végtelen sok optimális megoldás van. Informatikai Rendszerek Intézete Operációkutatás – 207 49. oldal Gábor Dénes Főiskola ELNEVEZÉSEK • eltérésváltozók • kibővített megoldások • bázismegoldások • lehetséges bázismegoldások • bázison kívüli változók • bázisváltozók Informatikai Rendszerek Intézete Operációkutatás – 207 50. oldal Gábor Dénes Főiskola SZIMPLEXMÓDSZER MENETE A MINTAPÉLDA

NYOMÁN • Az első belépő, ill. kilépő bázisváltozó meghatározása • Generáló elem bázisváltozó egyenlet felső határa x3 x3=4-x1 nincs x4 x4=12-2x2 x2 12 =6min x5 x5=18-3x1-2x2 x2 18 =9 2 2 Informatikai Rendszerek Intézete Operációkutatás – 207 51. oldal Gábor Dénes Főiskola SZIMPLEXTÁBLÁZAT AZ ITERÁCIÓ ELSŐ LÉPÉSE UTÁN Együtthatók x2 x3 Iteráció Bázisváltozó Egy. sz. Z x1 0 Z x3 x4 x5 0 1 2 3 1 0 0 0 -3 1 0 3 -5 0 2 2 Z 0 1 -3 x3 x4 x5 1 2 3 0 0 0 1 0 3 1 x4 x5 Jobb oldal 0 1 0 0 0 0 1 0 0 0 0 1 0 4 12 18 0 0 5 2 0 30 0 1 0 1 0 0 0 0 0 1 4 6 6 1 2 -1 • Az új lehetséges bázismegoldás: (0,6,4,0,6); z = 30 • Az optimalitás ellenőrzése Informatikai Rendszerek Intézete Operációkutatás – 207 52. oldal Gábor Dénes Főiskola AZ ITERÁCIÓ FOLYTATÁSA • A második belépő, ill. kilépő bázisváltozó Együtthatók x2 x3 Bázisváltozó Egy. sz. x4

x5 Jobb oldal Z x1 Z 0 1 -3 0 0 5 2 0 30 x3 1 0 1 0 1 0 0 4 x4 2 0 0 1 0 1 2 0 6 x5 3 0 3 0 0 -1 1 6 Arány 4 1 =4 6 3 =2 minimum Informatikai Rendszerek Intézete Operációkutatás – 207 53. oldal Gábor Dénes Főiskola • A teljes szimplextáblázat Együtthatók x2 x3 Iteráció Bázisváltozó Egy. sz. Z x1 0 Z x3 x4 x5 0 1 2 3 1 0 0 0 -3 1 0 3 -5 0 2 2 Z 0 1 -3 x3 x4 x5 1 2 3 0 0 0 Z 0 x3 1 2 x4 x5 Jobb oldal 0 1 0 0 0 0 1 0 0 0 0 1 0 4 12 18 0 0 5 2 0 30 1 0 3 0 1 0 1 0 0 0 1 2 -1 0 0 1 4 6 6 1 0 0 0 3 2 1 36 1 0 0 0 1 x4 2 0 0 1 0 x5 3 0 1 0 0 1 3 1 2 1 − 3 1 3 2 0 6 1 3 2 − • optimalitási vizsgálat • optimális megoldás (x1,x2)=(2,6), z (célfüggvény) maximuma: 36 Informatikai Rendszerek Intézete Operációkutatás – 207 54. oldal Gábor Dénes Főiskola PÉLDA B Z x4 x5 x6 Z x4 x5 x3 Z x1 Z 1 0 0 0 1 0 0 0 1 0 x1 -2 2 1 0

-2 2 1 0 0 1 2 x5 0 0 3 x3 0 0 x2 1 1 2 1 2 1 3 1 2 3 1 2 5 2 1 2 x3 -2 0 -2 2 0 0 0 1 0 0 x4 0 1 0 0 0 1 0 0 1 0 1 2 1 − 2 1 0 x5 0 0 1 0 0 0 1 0 0 0 x6 0 0 0 1 1 0 1 0 10 20 5 5 10 25 1 0 15 5 1 1 20 0 1 2 5 2 Optimális megoldás: (5,0, 52 ) Z maximuma: 15 S: sorszám; B: bázisváltozók 1 2 5 2 x 4 kilép S 0 1 2 3 0 1 2 3 0 1 x 6 kilép maximalizálandó x=2x 1-x 2+2x 3, feltéve, hogy 10 2x 1+x 2 x 1+2x 2-2x 3 20 x 2+x 3 5, és x 10, x 20, x 30. Informatikai Rendszerek Intézete Operációkutatás – 207 55. oldal Gábor Dénes Főiskola A STANDARD ALAKTÓL KÜLÖNBÖZŐ FELADATOK • maximum helyett minimum • lehetnek egyenlőség-feltételek is • megfordul az egyenlőtlenség • a jobb oldalon negatív számok is lehetnek . . . • a feltételek diszkutálása • mesterséges változók • "nagy M" módszer Informatikai Rendszerek Intézete Operációkutatás – 207 56. oldal Gábor Dénes

Főiskola MÓDOSÍTOTT MINTAFELADAT minimalizálandó x=3x1+5x2, feltéve, hogy x1 4 2x2 = 12 3x1+2x2  18, és x1  0, x2  0 Informatikai Rendszerek Intézete Operációkutatás – 207 57. oldal Gábor Dénes Főiskola A MINTAPÉLDA EGYENLŐSÉGFELTÉTELEKKEL maximalizálandó Z = 3x1 + 5x2, feltéve, hogy (1) x1 (2) +2x2 (3) 3x1 +2x2 és +x3 +x4 +x5 =4 = 12 = 18 xj  0 minden j = 1,2,,5 esetén maximalizálandó z, feltéve, hogy (0)Z-3x1 -5x2 (1) x1 (2) +2x2 (3) 3x1 +2x2 és +x3 +x4 +x5 =0 =4 = 12 = 18 xj  0 minden j = 1,2,,5 esetén. Informatikai Rendszerek Intézete Operációkutatás – 207 58. oldal Gábor Dénes Főiskola A MÓDOSÍTOTT MINTAPÉLDA SZIMPLEXTÁBLÁZATA Iteráció 0 1 2 Együtthatók x2 x3 x4 x5 x6 Jobb oldal 0 0 M 0 -30M 0 2 2 1 0 0 0 1 0 0 0 1 0 0 1 4 12 18 (-3M+3) 0 0 (2M-5/2) M 0 -6M-30 0 0 0 1 0 3 0 1 0 1 0 0 0 1/2 -1 0 0 -1 0 0 1 4 6 6 0 -1 0 0 0 (M-3/2) 1 (M-1) -36 x3

1 0 0 0 1 1 3 -1 3 2 x2 2 0 0 1 0 0 0 6 x1 3 0 1 0 0 1 3 1 2 -1 3 -1 1 3 2 Bázisváltozó Egy. sz. Z Z 0 -1 x3 x4 x5 1 2 3 0 0 0 1 0 3 Z 0 -1 x3 x4 x5 1 2 3 Z x1 (-3M+3) (-4M+5) 3 Informatikai Rendszerek Intézete Operációkutatás – 207 59. oldal Gábor Dénes Főiskola DINAMIKUS PROGRAMOZÁS Mintapélda Egy repülőgépet az S0 = (V0,H0) helyzetből el kívánunk juttatni minimális költség mellett az S =(V ,H ) helyzetre (V: sebesség; H: magasság). Közelítés: minden helyzetben vagy csak a magasságot, vagy csak a sebességet változtatjuk: H Hw Sw H S H0 S0 0 V0 V Vw V Informatikai Rendszerek Intézete Operációkutatás – 207 60. oldal Gábor Dénes Főiskola Hω − H 0 Vω −V0 ∆v := n ; ΔH: = ; n2 := 8; n2 := 6 1 n 2 (Mindegyik út 14 lépésből áll) H S H H0+5H H0+4H H0+3H H0+2H H0+H H H0 S0 0 V0 V V 0 +2V V 0 +4V V 0 +6V V V

Informatikai Rendszerek Intézete Operációkutatás – 207 61. oldal Gábor Dénes Főiskola A LEHETSÉGES UTAK SZÁMA 3003 1 1 3 1 2 1 3 1 1 14  = 14  = 3003 6   8       14 elem 6-odosztályú kombinációinak a száma. ffffffjjjjjjjj Informatikai Rendszerek Intézete Operációkutatás – 207 62. oldal Gábor Dénes Főiskola AZ ÜZEMANYAGKÖLTSÉG MEGADÁSA H H 10 9 7 8 10 H0 0 11 S0 V0 20 17 14 12 10 11 12 12 8 6 7 8 9 18 14 13 13 8 9 11 13 9 8 8 10 10 16 13 12 12 8 8 10 13 10 7 9 11 12 15 10 10 10 8 7 9 V 14 11 8 9 10 13 14 11 9 11 10 9 13 15 12 10 10 11 14 12 13 8 13 12 13 14 14 13 11 11 12 14 15 14 11 15 13 14 17 13 12 10 8 10 12 17 17 15 20 15 18 20 S 14 12 9 7 9 10 V V Informatikai Rendszerek Intézete Operációkutatás – 207 63. oldal Gábor Dénes Főiskola A FOLYAMATOT VISSZAFELÉ IRÁNYÍTJUK B1 B1 17 13 Sw 17 14 17 Sw 17 13 14 17 B2 14 Az

eljárás folytatása "lefelé vagy balra" 32 C1 15 17 17 13 Sw 14 B2 30 17 C2 14 12 C3 26 A felső 4 x 3-as téglalapot vizsgáljuk részletesen. A következő lapok az előadáson egymásra rakott fóliákon, lépésről-lépésre kerülnek bemutatásra. Informatikai Rendszerek Intézete Operációkutatás – 207 64. oldal Gábor Dénes Főiskola S Informatikai Rendszerek Intézete Operációkutatás – 207 65. oldal Gábor Dénes Főiskola 14 14 12 15 11 11 14 13 12 9 8 14 8 14 17 12 11 11 13 17 13 13 10 11 15 12 15 9 10 15 S 20 Informatikai Rendszerek Intézete Operációkutatás – 207 66. oldal Gábor Dénes Főiskola 17 17 S 14 14 Informatikai Rendszerek Intézete Operációkutatás – 207 67. oldal Gábor Dénes Főiskola 17 17 13 30 31 17 S 14 14 Informatikai Rendszerek Intézete Operációkutatás – 207 68. oldal Gábor Dénes Főiskola 32 14 15 46 14 44 17 17 14 13 30 12 S

14 42 41 15 12 26 Informatikai Rendszerek Intézete Operációkutatás – 207 69. oldal Gábor Dénes Főiskola 32 17 17 S 14 44 30 14 41 26 Informatikai Rendszerek Intézete Operációkutatás – 207 70. oldal Gábor Dénes Főiskola 44 15 12 59 57 13 32 17 17 S 14 44 13 57 52 11 30 14 41 26 40 51 55 20 9 35 Informatikai Rendszerek Intézete Operációkutatás – 207 71. oldal Gábor Dénes Főiskola 44 32 17 17 S 14 57 44 30 14 52 41 26 51 35 Informatikai Rendszerek Intézete Operációkutatás – 207 72. oldal Gábor Dénes Főiskola 14 58 11 68 44 32 17 17 S 14 57 12 69 60 8 44 30 14 52 41 26 51 35 11 63 66 15 Informatikai Rendszerek Intézete Operációkutatás – 207 73. oldal Gábor Dénes Főiskola 44 32 17 17 S 14 57 44 30 14 60 52 41 26 63 51 35 Informatikai Rendszerek Intézete Operációkutatás – 207 74. oldal Gábor Dénes Főiskola 14 44 32 17

17 S 14 11 11 68 79 9 69 57 44 30 14 60 52 41 26 63 51 35 10 70 76 13 Informatikai Rendszerek Intézete Operációkutatás – 207 75. oldal Gábor Dénes Főiskola 44 32 17 17 S 14 69 57 44 30 14 60 52 41 26 70 63 51 35 Informatikai Rendszerek Intézete Operációkutatás – 207 76. oldal Gábor Dénes Főiskola 44 32 17 17 S 14 69 8 77 81 11 57 44 30 14 60 52 41 26 70 63 51 35 Informatikai Rendszerek Intézete Operációkutatás – 207 77. oldal Gábor Dénes Főiskola 44 32 17 17 S 14 57 44 30 14 69 60 52 41 26 77 70 63 51 35 Informatikai Rendszerek Intézete Operációkutatás – 207 78. oldal Gábor Dénes Főiskola AZ EREDETI FELADAT TELJES MEGOLDÁSA H H 127 20 10 122 17 14 12 H0 0 139 V0 13 110 110 11 118 13 127 13 91 98 102 12 111 12 121 14 10 79 11 10 86 8 10 94 9 8 11 8 103 7 115 96 V 109 60 70 80 9 91 8 105 44

52 13 63 14 70 11 81 15 95 17 41 14 12 15 26 51 9 20 35 8 13 57 7 15 42 10 14 14 14 14 10 12 13 30 S 17 12 11 12 17 13 11 14 13 15 13 11 13 9 13 10 10 10 12 10 86 57 32 14 10 11 77 12 12 9 69 44 15 11 68 9 8 10 11 78 14 58 7 10 9 15 10 8 8 9 12 91 73 13 8 8 11 S0 104 16 9 7 10 10 129 14 6 8 120 105 89 13 8 7 122 18 12 9 118 101 67 9 18 12 17 79 51 10 20 V 61 V Informatikai Rendszerek Intézete Operációkutatás – 207 79. oldal Gábor Dénes Főiskola A műveletek száma 1. dinamikus programozásnál: <1572=210 2. "közvetlen módszerrel": >30032=6006 Valóságos modell: Hw H0 v0 vw v Informatikai Rendszerek Intézete Operációkutatás – 207 80. oldal Gábor Dénes Főiskola A dinamikus programozás alapelve (BELLMAN-féle elv) "Bármely optimális folyamat egy "közbülső" állapotát véve a

"maradék" folyamat optimális a "közbülső" állapotból kiinduló problémára nézve."