Ciascuno di noi si trova quotidianamente a dover prendere delle decisioni. Pochi però si soffermano sulla natura del processo che porta a formalizzare un problema decisionale e a cercarne la soluzione. Il libro nasce dal tentativo di razionalizzare i processi di decisione tipici di ambienti scientifici, ingegneristici ed economici, mettendo in luce gli aspetti sistemistica-funzionali che nei sistemi organizzati collegano il livello tecnologico a quello organizzativo. Questo scopo viene perseguito presentando una trattazione a due livelli: a livello metodologico, ripercorrendo il panorama dei principali modelli concettuali di decisione, esplicitandone il meccanismo di mutua interazione e le trasformazioni dell'uno nell'altro; a livello pratico, per mezzo di un consistente numero di esempi di carattere didattico e di problemi relativi a particolari realtà tecnologiche. Il risultato è una presentazione formale, ma al tempo stesso orientata verso aspetti progettuali e applicativi.

Premessa. Parte prima. Generalità 1. Modelli di sistemi organizzati 1.1. Introduzione 1.2. Cosa significa modellare La definizione di un modello come processo decisionale 1.3. Strumenti di rappresentazione 1.4. Soluzione per enumerazione totale 1.5. La formulazione dei modelli 1.6. Microscopio, macroscopio e lateroscopio 1.7. Evoluzione storica della modellistica per problemi di decisione e di gestione 2. Alcuni esempi di problemi di decisione e di gestione 2.1. Percorso di tempo minimo su una rete stradale 2.2. Costruzione di un'autostrada 2.3. Controllo delle scorte 2.4. Come salvare capra e cavoli 2.5. Scacchi (il gioco del Re) 2.6. I ponti di Königsberg, ovvero il circuito euleriano 2.7. Problemi di sequenziamento 2.8. Alcuni problemi scolastici 2.9. Rete di trasporto con ritardo 2.10. Lo zaino 2.11. Dimensionamento della capacità produttiva 2.12. Pianificazione delle attività con vincoli di precedenza 2.13. Pianificazione di agenda 2.14. Definizione delle aree di sosta in un parcheggio Parte seconda. Formalizzazione 3. Una prima definizione formale di modello 3.1. Problema di decisione 3.2. Problema di ottimizzazione 3.3. Problema di ottimizzazione a molti obiettivi 3.4. Problema con molti decisori 3.5. Soluzioni approssimate 3.6. Alcuni paradigmi di formulazione, soluzione e valutazione del modello Complessità/Decomposizione/Rilassamento/Restrizione 4. Paradigmi di rappresentazione: poliedri, grafi, ipergrafi, matrici, funzioni booleane, autonomi 4.1. Poliedri 4.2. Geometria della programmazione lineare 4.3. Problema duale e problema primale 4.4. Teoria assiomatica della dualità 4.5. Grafi 4.6. Definizioni preliminari Grafo orientato e non orientato/Adiacenza e incidenza/Multigrado/Grado/Isomorfismo e operazioni su grafi/Sottografi indotti, parziali, massimali/Grafo complemento/Grafi pesati 4.7. Cammini e percorsi Connessione/Centro, raggio e diametro 4.8. Circuiti e cicli 4.9. Partizioni e tagli Partizioni/Tagli 4.10. Copertura e abbinamento Copertura dei nodi di un grafo (Copertura con archi)/Copertura degli archi di un grafo (copertura con nodi)/Abbinamento 4.11. Grafi completi Proprietà di un grafo completo/Clique e insieme indipendente/Colorazione di un grafo 4.12. Grafi bipartiti Proprietà di un grafo bipartito/Grafi bipartiti completi/Grafi stratificati 4.13. Grafi planari Proprietà di un grafo planare/Duale di un grafo planare/Grafi e griglia/Grafi serie-parallelo/Genere di un grafo 4.14. Grafi aciclici, foreste e alberi Proprietà di un grafo aciclico/Albero binario/Albero ricoprente/Stella/Ragni e bruchi 4.15. Grafi euleriani e grafi hamiltoniani Grafo euleriano/Grafo hamiltoniano/Alcuni esempi 4.16. Grafi perfetti Grafi triangolari o cordali/Grafi intervallo 4.17. Grafi di adiacenza Proprietà di un grafo di adiacenza 4.18. Ipergrafi Ipergrafo duale/Grafo intersezione di un ipergrafo 4.19. Rappresentazione matriciale di grafi e ipergrafi Matrice di adiacenza/Matrice di incidenza/Matrici di incidenza totalmente unimodulari 4.20. Matroidi Esempi/Matroidi e poliedri 4.21. Funzioni booleane 4.22. Notazioni e funzioni booleane di largo uso 4.23. Algebra di Boole 4.24. Tavole di verità 4.25. Formule booleane duali 4.26. Funzioni booleane duali 4.27. Basi e insiemi completi di funzioni booleane 4.28. Esempi di insiemi completi 4.29. Classi chiuse massimali 4.30. Funzioni booleane ottime Esempi 4.31. Insiemi parzialmente ordinati, autonomi e linguaggi formali 4.32. Automi a stati finiti 4.33. Grammatiche 4.34. Automi pushdown 4.35. Macchine di Turino 5. Paradigmi di decisione 5.1. Decisioni qualitative e decisioni binarie 5.2. Paradigmi fondamentali di decisione qualitativa Selezione/Associazione 5.3. Decisione booleana Implicazione (y←х)/Equivalenza tra proposizioni elementari (y↔x)/Negazione (y← ┐x, y ↔ ┐x)/OR logico (y↔x1 V x2)/AND logico (y↔x1 ∩ x2) 5.4. Esempi di decisione booleana 5.5. Assegnamento 5.6. Esempi di assegnamento 5.7. Ordinamento 5.8. Esempi di ordinamento 5.9. Copertura e riempimento 5.10. Esempi di copertura e riempimento 5.11. Partizione 5.12. Esempi di partizione 5.13. Scelta di sottografo 5.14. Esempi di scelta di sottografo 5.15. Decisioni quantitative 5.16. Livello di produzione/prezzo implicito Un modello per un sistema di produzione/Prezzo implicito 5.17. Esempi 5.18. Flusso/potenziale Modelli di flusso single-commodity/Modelli di flusso multi-commodity/Reti di attività 5.19. Esempi 5.20. Altri modelli di programmazione lineare 6. Paradigmi algoritmici 6.1. Introduzione 6.2. Problemi continui, discreti e lineari 6.3. Metodi incrementali Metodi greedy/Metodi per la programmazione lineare/Metodi di ricerca locale/Metodi interni: l'ellissoide 6.4. Metodi ricorsivi Il concetto di induzione/Problemi con cicli/Commenti sul metodo/Commenti sulla complessità 6.5. Metodi enumerativi Branch & bound/L'algoritmo di risoluzione nel calcolo proposizionale 6.6. Metodi probabilistici Introduzione/Metodi Monte Carlo/Un criterio di arresto probabilistico/Miglioramento iterativo/Simulated annealing 7. La rete di modelli 7.1. Modelli, formulazioni e dati 7.2. Trasformazioni, transizioni, riduzioni 7.3. Definizione della rete 7.4. Interpretazione della rete 7.5. La rete e gli algoritmi 7.6. La complessità nella rete dei modelli 7.7. Cenni sulla teoria della complessità computazionale 7.8. L'euristica e l'approssimazione nella rete dei modelli 7.9. Conclusioni Parte terza. Un'applicazione 8. Problemi di decisione nel progetto di circuiti integrati 8.1. Il layout 8.2. Il partitioning 8.3. Il placement 8.4. Il routing in una sola passata 8.5. Il routing iterativo e il routing di dettaglio 8.6. Minimizzazione del numero di via 8.7. Il layout di gate array 8.8. Il channel routing 8.9. PLA folding.