Programma del corso

Guida alla Facoltà di Ingegneria 2004-2005
 

 

 
A.A. 2004/2005
Laurea Triennale
MAT/09
Ricerca Operativa (6 cfu)

Corso di Laurea: Ing. Informatica e dell'Automazione

 

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.

 

 

Facoltà di Ingegneria - Via Brecce Bianche - Monte Dago - 60131 Ancona - Tel. 0039-071-2204708