Operációkutatás

Operációkutatás......Page 1
Bevezetés......Page 9
Algoritmusok hatékonyságáról......Page 13
Gráfok bejárása: elérhetőség......Page 19
Szélességi keresés......Page 22
Mélységi keresés......Page 23
Bevezetés......Page 26
Legolcsóbb utak aciklikus digráfban......Page 27
Legolcsóbb utak nemnegatív költségekre: Dijkstra algoritmusa......Page 31
Konzervatív költségfüggvények, megengedett potenciálok, tenziók......Page 33
Legolcsóbb utak: min-max tétel és optimalitási feltétel......Page 38
Algoritmusok......Page 40
Páros gráfok optimális párosításai......Page 47
Maximális elemszámú párosítások: a javító utak módszere......Page 48
Maximális súlyú teljes párosítások: a magyar módszer......Page 50
Egerváry eredeti bizonyítása és algoritmusa......Page 54
Maximális súlyú párosítások......Page 57
Fogalmak......Page 60
Motivációk......Page 62
Megengedett áramok......Page 64
Áramok és folyamok kapcsolata......Page 66
Folyam algoritmusok......Page 68
Skálázási technika......Page 69
Legrövidebb növelő utak......Page 70
Minimális költségű folyamok......Page 71
Vektortér, altér, lineáris függetlenség......Page 79
Mátrixok, egyenletrendszerek megoldhatósága......Page 82
Egyenletrendszer megoldáshalmaza, affin alterek......Page 87
Bevezetés......Page 93
Megjegyzések az intuícióról......Page 94
Kúpok, poliéderek, politópok......Page 97
Kúpok......Page 98
Poliéderek és politópok......Page 99
Bázismegoldások......Page 103
Csúcsos poliéderek......Page 107
Korlátos poliéderek......Page 109
A Fourier–Motzkin-elimináció és következményei......Page 110
Oszlop-elimináció......Page 111
Poliéder = politóp + generált kúp......Page 112
Az FM-eljárás hatékonysága......Page 117
Alkalmazások......Page 118
Megoldhatóság: a Farkas-lemma......Page 120
Direkt bizonyítás......Page 123
A szimplex algoritmus a Farkas-lemmára......Page 126
Lineáris és logikai következmény......Page 131
Alkalmazások......Page 133
Iránymenti korlátosság......Page 137
Optimalitás......Page 140
Optimalitási feltételek......Page 141
A dualitástétel......Page 144
Következmények......Page 147
Játékelméleti alkalmazás......Page 148
Teljesen unimoduláris mátrixok......Page 153
Definíciók és példák......Page 154
Farkas-lemma, dualitástétel, optimalitási feltételek TU-mátrixokra......Page 157
Kerekítés és egyenletes színezés......Page 159
Páros gráfok: optimális részgráfok......Page 161
Páros gráfok: élszínezések......Page 164
Megengedett potenciálok, legolcsóbb utak......Page 165
Megengedett áramok és folyamok......Page 166
Minimális költségű áramok és folyamok......Page 167
Hálózati mátrixokkal adott lineáris programok......Page 169
Primál szimplex módszer......Page 171
A szimplex módszer tulajdonságai......Page 173
A szimplex módszer egy lépése......Page 175
Érzékenységvizsgálat......Page 177
A duál szimplex módszer tulajdonságai......Page 179
A duál szimplex módszer egy lépése......Page 180
Alkalmazás: primál megengedett bázis keresése......Page 181
A duál szimplex módszer egy másfajta interpretációja......Page 182
Kétfázisú szimplex módszer......Page 183
Hálózati szimplex módszer......Page 185
Primál hálózati szimplex módszer lépései......Page 188
Duál hálózati szimplex módszer......Page 189
Kezdeti primál bázis keresése......Page 191
Erősen megengedett bázisok......Page 193
Bevezetés......Page 195
Vágósíkos eljárás......Page 199
Gomory-vágás......Page 200
Bináris hátizsákfeladat......Page 203
Korlátozás és szétválasztás......Page 204
Minimális lefogó csúcshalmaz......Page 208
Minimális költségű lefogó csúcshalmaz......Page 210
Alaptulajdonságok......Page 213
Konvex halmazok szeparációja......Page 216
Konvex függvények......Page 217
Feltétel nélküli optimalizálás......Page 219
Feltételes optimalizálás......Page 220
A Karush–Kuhn–Tucker-tétel......Page 221
Lagrange-duális......Page 224
Megengedett csökkenési irány keresése......Page 225
Aranymetszés módszer......Page 227
Newton módszer......Page 228
Ajánlott irodalom......Page 231