Programma :
Introduzione ai modelli decisionali:
Classificazione dei problemi di ottimizzazione.
Modelli di programmazione matematica. Programmazione
lineare. Programmazione lineare intera. Classificazione
degli algoritmi di ottimizzazione. Complessità
computazionale degli algoritmi.
Programmazione lineare:
Richiami di algebra lineare: matrici, calcolo
dell’inversa, rango di una matrice, sistemi
di equazioni lineari. Richiami di analisi convessa:
insiemi convessi, funzioni convesse, poliedro
convesso, punti estremi, direzioni estreme, teoremi
della rappresentazione, ottimi locali e ottimi
globali, teorema di esistenza dell’ottimo
globale. Modello di programmazione lineare: ipotesi
della programmazione lineare, funzione obiettivo,
significato economico dei coefficienti di costo,
regione di ammissibilità, forma generale,
riduzione alla forma standard e variabili ausiliarie,
forma canonica e variabili artificiali. Soluzioni
di base ammissibili, soluzione di base degenere,
soluzioni di base adiacenti, soluzione ottima,
soluzione ottima degenere. Soluzioni di base ammissibili
e punti estremi. Risoluzione geometrica della
programmazione lineare. Metodi di risoluzione:
matrice tableau, operazione di pivot, metodo del
simplesso standard, metodo matrice pivot, metodo
della forma matriciale, metodi revisionati della
matrice pivot e in forma prodotto. Teorema fondamentale
del simplesso. Caso di soluzione ottima illimitata.
Caso di infinite soluzioni ottime equivalenti.
Convergenza del metodo del simplesso. Problema
di Beale. Riduzione a forma canonica: metodo delle
due fasi, metodo della penalità. Caso di
non esistenza delle soluzioni ammissibili. Interpretazione
geometrica del metodo del simplesso. Cenni sull’utilizzo
del software LINDO. Applicazioni della programmazione
lineare: problemi di mix ottimo della produzione,
problema della dieta ottima, problema di investimento,
problemi di scheduling del personale, problemi
di programmazione della produzione manifatturiera.
Teoria della dualità ed analisi della
stabilità:
Programmazione non lineare. Moltiplicatori di
Lagrange. Rilassamento langragiano. Lower bound
della funzione obiettivo. Gap di dualità.
Rilassamento lagrangiano nel caso lineare. Passaggio
primale-duale. Primale e duale simmetrici. Significato
economico delle variabili duali. Primale e duale
nel caso generale. Teoremi fondamentali della
dualità. Teorema degli scarti complementari.
Corollario degli scarti complementari. . Significato
economico del corollario. Lettura del duale dal
primale. Risoluzione del duale dal primale in
forma matriciale. Significato dei costi ridotti.
Valutazione della " bontà " della
soluzione di metodi euristici. Metodo duale del
simplesso: ipotesi di base, interpretazione geometrica
del metodo duale. Analisi di sensitività.
Analisi di stabilità: variazione dei costi,
variazione delle risorse, ulteriori vincoli.
Casi particolari di Programmazione Lineare:
Problema dei trasporti: modello matematico, proprietà
della matrice dei vincoli, duale del problema
dei trasporti, algoritmo di Dantzig. Problema
di assegnamento: modello matematico, algoritmo
ungherese.
Testi di Riferimento :
F. Pezzella, E. Faggioli, Ricerca
Operativa: problemi di gestione della produzione,
Pitagora, Bologna.
F. Pezzella, Elementi di Programmazione Lineare,
Liguori, Napoli.
Modalità di svolgimento dell’esame
:
Si terranno presso il Centro di
Calcolo dell'Università esercitazioni numeriche
basate sull'utilizzo di software di ottimizzazione
e di fogli elettronici per la risoluzione di problemi
reali di gestione della produzione. L'esame consisterà
in una prova scritta ed una orale.
Ricevimento Studenti :
Contattare il docente.
|