A diszkrét programozás kombinatorikus módszerei

Tartalom

Elősző
1. fejezet. Diszkrét programozási modellek gazdasági
problémákra és néhány matematikai programozási feladatra 1
1.1 A diszkrét programozási feladatok általános alakja 1
1.2 A hátizsák probléma 4
1.3 Hajórakodási probléma 9
1.4 Az utazó ügynök probléma 11
1.5 Fix-költséges problémák 15
1.6 Egy beruházási probléma 19
1.7 Gyártelepitési probléma 21
1.8 Üres szállítókocsi probléma 23
1.9 Alternatív feltételek 25
Példák 26
1.10 Optimalizálás nemlineáris, szeparálható célfüggvénnyel 27
1.11 Feltételes megszorítások 28
1.12 Konkáv függvény minimuma egy konvex poliéderen 29
2. fejezet. Tiszta leszámlálási algoritmusok 31
2.1 Vektorok parciális és lexikografikus rendezése 31
2.2 A Lawler-Bell algoritmus 33
2.3 A Lawler-Bell algoritmus rövid összefoglalása
és néhány megjegyzés 38
2.4 Leszámlálási struktúrák 42
2.5 Egy alapvető jelentőségű leszámlálási struktura 44
2.6 Feladatok megoldása leszámlálási struktúra segítségével 54
3. fejezet. A korlátozás és szétválasztás módszere 65
3.1 A korlátozás és szétválasztás elve 66
3.2 A "hátizsák" probléma megoldása korlátozás és
szétválasztás módszerével 70
3.3 Az utazó ügynök probléma megoldása 78
3.4 Land és Dóig módszere vegyes egészértékű lineáris
feladatok megoldására 91
4. fejezet. Dinamikus programozás alkalmazása egészértékű
programozási feladatok megoldására 103
4.1 A dinamikus programozás optimalitás elvének bemutatása egy gazdasági modellen 103
4.2 A hátizsák probléma megoldása dinamikus
programozással 107
4.3 Több paraméteres egészértékű problémák megoldása dinamikus programozással 111
5. fejezet. A többfázisú duál algoritmus 121
5.1 Az s-feltétel képzése 122
5.2 Erős s-feltétel keresése 128
5.3 Tesztek 131
5.4 Az algoritmus leírása 137
6. fejezet. Módosított additív algoritmus 149
6.1 A feladat kitűzése 150
6.2 Módosított leszámlálási algoritmus 151
6.3 Jelölések, fogalmak 156
6.4 Az algoritmus leírása 159
6.5 Megjegyzések az algoritmushoz 161
6.6 Példa 163
7. fejezet. A vegyes egészértékű programozási feladatok
felbontása 173
7.1 A feladat kitűzése 173
7.2 A feladat átfogalmazása a C kup poláris halmaza
segítségével 175
7.3 Néhány előkészítő lemma 179
7.4 Számítási eljárás vegyes diszkrét feladatok megoldására particionálással 186
7.5 Egy numerikus példa megoldása teljes felbontással és az előző szakaszban leírt algoritmussal 191
8. fejezet. Módosított filter módszer 203
8.1 A feladat megfogalmazása 203
8.2 Optimális indexelés 208
8.3 Megoldás-fa és pszeudo-megoldás-fa 209
8.4 A korlátozás és szétválasztás módszerének alkalmazása 219
8.5 Tesztek 221
8.6 Az algoritmus leírása 225
8.7 Egy numerikus példa 238
Irodalom 247

Témakörök