Webinar Faber
Teoria e metodi di ottimizzazione lineare
Il metodo del simplesso
Edizione: 1991
Collana: Studi Superiori
ISBN: 9788843009497
- Pagine: 256
- Prezzo:€ 24,99
- Acquista
In breve
In questo volume viene presentata un'analisi dettagliata del problema di programmazione lineare e dell'algoritmo più diffuso per la sua risoluzione: il metodo del simplesso. La trattazione, pur non sacrificando gli aspetti teorici, esplora in particolare le possibilità applicative del metodo, attraverso la presentazione di alcuni 'casi'. Ampio spazio è dedicato all'analisi di sensitività, vista come tecnica per il supporto delle decisioni manageriali, e ad alcune importanti applicazioni a problemi di ottimizzazione su grafi. Il testo è adatto a un corso di Ricerca operativa per le Facoltà di Scienze dell'Informazione o di Ingegneria; trascurando alcuni approfondimenti teorici e dettagli algoritmici, può essere utilmente usato anche da studenti di Economia e Commercio.
Indice
Prefazione
1 Programmazione lineare: esempi
1.1. Il problema della dieta
1.2. Il problema di miscelazione ottimale
1.3. Il problema dei trasporti
1.4. Problemi di flusso su reti
1.4.1. Flussi su reti – 1.4.2. Il problema del cammino di costo minimo – 1.4.3. Problemi di
flusso di costo minimo
2 Fondamenti di programmazione lineare
2.1. Forma di un problema di programmazione lineare
2.1.1. Vincoli di diseguaglianza – 2.1.2. Variabili libere
2.2. Soluzioni, basi, soluzioni ammissibili
2.3. Interpretazione del concetto di base
2.3.1. Basi e soluzioni di base in problemi di flusso
2.4. Il teorema fondamentale della programmazione lineare
Esercizi
2.5. Una geometria per la programmazione lineare
Esercizi
3 Il metodo del simplesso
3.1. Formulazione matriciale
3.1.1. Ottimalità di una soluzione ammissibile – 3.1.2. Scelta di una nuova soluzione
ammissibile di base – 3.1.3. Ulteriori considerazioni sulla condizione di ottimalità – 3.1.4.
Inizializzazione del metodo del simplesso
Esercizi
3.2. Un tableau per il simplesso
3.3. Un tableau per il metodo due fasi
Esercizi
4 Teoria della dualità
4.1. Introduzione
4.2. Definizione di problema duale
4.3. Teoremi di dualità
4.4. Interpretazione del problema duale
4.4.1. Duale del problema della dieta – 4.4.2. Duale del problema del cammino di costo
minimo
4.5. Complemenatry slackness
4.5.1. Interpretazione delle condizioni di complementary slackness
4.6. Informazione duale nel tableau
4.7. Dualità per problemi non lineari
4.8. Il metodo del simplesso duale
Esercizi
5 Analisi di sensitività
5.1. Introduzione
5.2. Sensitività sul termine noto
5.3. Sensitività sul vettore dei costi
5.3.1. Variazione del costo di una variabile non di base – 5.3.2. Variazione del costo di una
variabile di base
5.4. Aggiunta di una nuova variabile
5.5. Sensitività sulla matrice dei coefficienti
5.5.1. Modifica di una colonna non di base – 5.5.2. Modifica di una colonna di base
5.6. Aggiunta di un nuovo vincolo
Esercizi
6 Aspetti computazionali del metodo del simplesso
6.1. Il metodo del simplesso modificato
6.1.1. Forma prodotto dell'inversa – 6.1.2. Decomposizione LU
Esercizi
7 Il metodo primale-duale
7.1. Descrizione del metodo
7.1.1. Inizializzazione del metodo primale-duale
Esercizi
8 Il problema del cammino di costo minimo
8.1. Il metodo primale-duale
8.2. L'algoritmo di Dijkstra
Esercizi
9 Il problema del massimo flusso
9.1. Il metodo primale-duale
9.2. L'algoritmo di Ford-Fulkerson
9.2.1. Il teorema Max-flow min-cut.
Esercizi.
Appendice A. Cenni di teoria dei grafi.
Appendice B. Il problema della dieta.
Appendice C. Un problema di miscelazione.
Appendice D. Un problema di trasporto.
Riferimenti bibliografici.
Soluzione degli esercizi.
Indice analitico.