Egészértékű programozás

Tartalom

Jelölések 7
I. rész. A DISZKRÉT PROGRAMOZÁS ALAPJAI 9
1. BEVEZETÉS 11
1.1. A diszkrét programozás tárgya 11
1.2. Feladatok és modellek 12
1.2.1. A hátizsák feladat és variánsai 13
1.2.2. A halmazfedési feladat és társai 16
1.2.3. Általános lineáris diszkrét programozási feladatok 17
1.2.4. Az utazó ügynök feladata 18
1.3. A feladatok osztályozása 20
1.4. Megjegyzések 22
2. A DISZKRÉT PROGRAMOZAS MATEMATIKAI ALAPJAI 24
2.1. A feladatok megoldhatósága 24
2.2. Hilbert-bázisok 37
2.3. Poliéderben fekvő rácspontok konvex burkának bonyolultsága 45
2.4. Sperner-rendszerek 49
2.5. Egyenletekkel definiált diszkrét ponthalmazok 54
2.6. Egyenlőtlenségekkel definiált bináris
ponthalmazok 62
2.7. Egyetlen egyenlőtlenséggel jellemzett
bináris ponthalmazok 74
2.8. Bináris fák 91
2.9. Megjegyzések és irodalom a 2. Fejezethez 98
FÜGGELÉK A 2. Fejezethez: Feladatok, feladatosztályok, algoritmusok és ezek nehézsége 102
3. KÉT ALAPVETŐ ELV 105
3.1. A relaxációs elv 105
3.2. Az egészértékű programozási feladatok
egy gráfelméleti modellje 106
II. rész: A MATEMATIKAI PROGRAMOZÁS ÁLTALÁNOS
MÓDSZEREINEK ALKALMAZÁSA A DISZKRÉT PROGRAMOZÁSBAN 117
4. VÁGÁS TÍPUSÚ MÓDSZEREK 120
4.1. A Gomory-módszer 121
4.2. Egyéb Gomorv-típusú vágások 136
4.3. Általános vágások 144
4.4. Egy konvex vágás 147
4.5. Megjegyzések és irodalom 152
5. DINAMIKUS PROGRAMOZÁS 155
5.1. A Bellman-elv 155
5.2. Gráfban legrövidebb utat kereső algoritmusok 157
5.3. Lineáris diofantoszi egyenlet megoldhatósága 165
5.4. Felső korlátos változókat tartalmazó
hátizsák feladat megoldása 177
5.5. A hátizsák feladat megoldása explicit
felső korlátok nélküli feladat esetén 185
5.6. A dinamikus programozás alkalmazása
több feltételt tartalmazó feladatok esetén 195
5.7. Megjegyzések és irodalom 197
6. A KORLÁTOZÁS ÉS SZÉTVÁLASZTÁS MŐDSZERE 199
6.1. A módszer elméleti váza 199
6.2. Korlátos egész változókat tartalmazó
feladat megoldása a korlátozás és szétválasztás módszerével 205
6.3. A hátizsák feladatra alapozott módszer 219
6.4. Az adatszerkezet 224
7. LAGRANGE SZORZOK 232
7.1. A Lagrange szorzók használata a matematikai programozásban - néhány alapvető eredmény 232
7.2. Módszerek a szorzók megválasztására 237
7.3. Egy további optimalitási kritérium 253
7.4. Diszkrét programozási feladatok méretének redukciója 257
7.5. Dekompozíició Lagrange-szorzók segítségével 262
7.6. Megjegyzések és irodalom 275
8. A SZOMSZÉDSÁGFOGALMON ALAPULÓ HEURISZTIKA 278
8.1. A módszer általános váza 278
8.2. A módszer alkalmazása a diszkrét programozásban 280
8.3. A módszer termodinamikai változata 283
8.4. Megjegyzések és irodalom 285
9. A MOHÓ MÓDSZER 287
9.1. A módszer általános alakja 287
9.2. A belső pontos mohó eljárások néhány általános tulajdonsága 293
9.3. A mohó módszer néhány speciális tulajdonsága a hátizsák feladat esetén305
9.4. Megjegyzések és irodalom 321
III. rész. A DISZKRÉT PROGRAMOZÁS SPECIÁLIS
MÓDSZEREI 325
10. LESZÁMLÁLÁSI ALGORITMUSOK 327
10.1. A leszámlálási algoritmusok alapvető struktúrája 327
10.2. Tesztek a lineáris diszkrét programozási feladat esetében 338
10.3. Az algoritmus részletei a lineáris diszkrét programozási feladat esetén 347
10.4. Megjegyzések és irodalom 358
11. A CSOPORTELMÉLETI MÓDSZER 359
11.1. A csoportfeladat 359
11.2. A mátrixok Smith-féle normálalakja 361
11.3. A csoportfeladat előállítása a Smith-féle normálforma segítségével 371
11.4. A csoportfeladat megoldása dinamikus programozással 373
11.5. A csoportfeladat optimális megoldásának néhány tulajdonsága 380
11.6. A csoportelméleti módszer beágyazása a korlátozás és szétválasztás algoritmusába 382
11.7. Megjegyzések és irodalom 390

Témakörök