Operációkutatás

Description

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