Ottimizzazione Combinatoria

Questo libro di testo di ottimizzazione combinatoria pone in particolare risalto i

risultati teorici e gli algoritmi che, al contrario delle euristiche, hanno una garanzia

di avere buone prestazioni. Comprende una vasta scelta di argomenti e nasce

come riferimento di diversi corsi di ottimizzazione combinatoria sia di base che di

livello avanzato. Il libro contiene dimostrazioni complete (ma concise) anche

di molti risultati avanzati, alcuni dei quali non sono mai apparsi prima in un libro.

Vengono anche trattati molti dei temi di ricerca più attuali e sono riportati molti

riferimenti alla letteratura. Quindi questo libro, traduzione della quarta edizione in lingua originale, rappresenta lo stato dell'arte dell'ottimizzazione combinatoria.

Traduzione di un famoso testo pubblicato in diverse lingue dalla casa madre Punto di riferimento insostituibile per ricercatori e studeni del settore

Autorentext

Bernhard Korte is professor of operations research and director of the Research Institute for Discrete Mathematics at the University of Bonn. He founded the Arithmeum in Bonn and received numerous awards, including a honorary doctoral degree and the "Staatspreis NRW". His research interests include combinatorial optimization and chip design. Jens Vygen is professor of discrete mathematics at the University of Bonn and principal investigator of the Hausdorff Center for Mathematics. He also co-authored the textbook "Algorithmic Mathematics" and has served as editor of several books and journals. His research interests include combinatorial optimization and algorithms for chip design.

Inhalt

1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.1 Enumerazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.2 Tempo di esecuzione degli algoritmi . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.3 Problemi di ottimizzazione lineare . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.4 Ordinamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

Riferimenti bibliografici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2 Grafi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.1 Definizioni fondamentali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.2 Alberi, cicuiti, e tagli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.3 Connettività . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.4 Grafi di Eulero e grafi bipartiti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

2.5 Planarità . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

2.6 Dualità Planare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

Riferimenti bibliografici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

3 Programmazione lineare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

3.1 Poliedri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

3.2 Algoritmo del simplesso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

3.3 Implementazione dell'algoritmo del simplesso . . . . . . . . . . . . . . . . . 63

3.4 Dualità . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

3.5 Inviluppi convessi and politopi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

Riferimenti bibliografici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

4 Algoritmi di programmazione lineare . . . . . . . . . . . . . . . . . . . . . . . . . 77

4.1 Dimensione dei vertici e delle facce . . . . . . . . . . . . . . . . . . . . . . . . . 77

4.2 Frazioni continue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

4.3 Eliminazione di Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

4.4 Il metodo dell'elissoide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

4.5 Il Teorema di Khachiyan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

4.6 Separazione ed ottimizzazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

Riferimenti bibliografici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

5 Programmazione intera . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

5.1 Inviluppo convesso di un poliedro . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

5.2 Trasformazioni unimodulari . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

5.3 Integralità totalmente duale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

5.4 Matrici totalmente unimodulari . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

5.5 Piani di taglio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

5.6 Rilassamento lagrangiano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127

Riferimenti bibliografici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131

6 Alberi di supporto e arborescenze . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135

6.1 Alberi di supporto minimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135

6.2 Arborescenze di peso minimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142

6.3 Descrizioni poliedrali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146

6.4 Packing alberi di supporto e arborescenze . . . . . . . . . . . . . . . . . . . . 149

Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152

Riferimenti bibliografici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156

7 Cammini minimi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159

7.1 Cammini minimi da una singola sorgente . . . . . . . . . . . . . . . . . . . . . 160

7.2 Cammini minimi tra tutte le coppie di vertici . . . . . . . . . . . . . . . . . 164

7.3 Circuiti di peso medio minimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166

Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169

Riferimenti bibliografici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171

8 Reti di flusso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173

8.1 Il Teorema di massimo flussominimo taglio . . . . . . . . . . . . . . . . . . 174

8.2 Teorema di Menger . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178

8.3 Algoritmo di Edmonds-Karp . . . . . . . . . . . . . .…