logo-polimi
Loading...
Risorse bibliografiche
Risorsa bibliografica obbligatoria
Risorsa bibliografica facoltativa
Scheda Riassuntiva
Anno Accademico 2019/2020
Scuola Scuola di Ingegneria Industriale e dell'Informazione
Insegnamento 054124 - METODI DI OTTIMIZZAZIONE
Docente Occhinero Francesco
Cfu 5.00 Tipo insegnamento Monodisciplinare

Corso di Studi Codice Piano di Studio preventivamente approvato Da (compreso) A (escluso) Insegnamento
Ing Ind - Inf (1 liv.)(ord. 270) - LC (367) INGEGNERIA DELLA PRODUZIONE INDUSTRIALE*AZZZZ054124 - METODI DI OTTIMIZZAZIONE

Obiettivi dell'insegnamento

Obiettivi

Il corso si propone di descrivere i principali modelli decisionali quantitativi, rivolti alla rappresentazione matematica di processi decisionali complessi, che si presentano nella gestione delle aziende e di strutture organizzate. Ampio spazio viene dedicato al significato applicativo dei modelli illustrati, e all'interpretazione economica e gestionale dei risultati ottenuti attraverso la risoluzione di ciascun modello descritto. 


Risultati di apprendimento attesi

Alla fine del corso lo studente deve aver svlipuppato un'autonoma capacità di analizzare un problema reale, di fornire il modello matematico che lo rappresenta, di individuare un algoritmo risolutivo e infine di interpretarne i risultati.


Argomenti trattati

Programma del corso di Metodi di Ottimizzazione

(Per i teoremi con (*) è richiesta la dimostrazione)

Modelli di ottimizzazione (cap. 1)

  • modelli matematici per le decisioni: fasi di svoluppo di un modello, esempi di problemi di ottimizzazione; modelli di ottimizzazione; modelli di ottimizzazione matematica; ottimizzazione multi-obiettivo con e senza priorità.

Ottimizzazione lineare (cap. 2)

  • Esempi di modelli di ottimizzazione linerare: mix produttivo, miscelazione e dieta, trasporto, pianificazione produttiva multi-periodo, selezione di investimenti finanziari. 
  • Formulazioni di ottimizzazione lineare: forma generale uniforme, forma standard, forma generale mista; equivalenza tra formulazioni; assunzioni dell'ottimizzazione lineare, assunzione di rango pieno; proprietà di ammissibilità, illimitatezza e ottimalità di un problema di ottimizzazione lineare.

Geometria dell'ottimizzazione lineare (cap. 3) 

  • Geometria di problemi in due e tre dimensioni: rappresentazione dei vincoli e della funzione obiettivo; soluzione del modello lineare per via grafica; caratterizzazione delle soluzioni ottimali; soluzioni ottimali multiple; problemi inammissibili e illimitati; vincoli attivi, inattivi e ridondanti; geometria di problemi in forma standard.
  • Poliedri, vertici e soluzioni di base: insiemi convessi; iperpiani, semispazi e poliedri; punti estremi e vertici di un poliedro; soluzioni di base e loro interpretazione geometrica; equivalenza tra soluzioni di base, vertici e punti estremi (teorema 3.2.6*, teorema 3.2.7*); numerosità delle soluzioni di base; soluzioni di base degeneri; corrispondenza tra basi e soluzioni di base; soluzioni di base per variabili limitate; esistenza di soluzioni di base ottimali.  

Algoritmo del simplesso (cap. 4)

  • Geometria del simplesso nello spazio delle variabili; condizioni di ottimalità (teorema 4.2.1*); direzioni ammissibili e algoritmo del simplesso; generica iterazione dell'algoritmo (fase II): condizioni di illimitatezza e cambio di base; ricerca di una soluzione ammissibile iniziale (fase I).
  • Tableau del simplesso; convergenza dell'algoritmo (cenni), degenerazione e regole anticiclaggio; estensione al caso di variabili limitate; complessità dell'algoritmo (cenni).

Dualità (cap. 5)

  • Esempi di problemi duali: duale del problema di mix produttivo, della dieta, del trasporto; problemi lineari duali e relative trasformazioni; corrispondenze tra primale e duale.
  • Teoremi di dualità: dualità debole (teorema 5.3.1*, corollario 5.3.1*, corollario 5.3.2*); dualità forte (teorema 5.3.2*); teorema degli scarti complementari (teorema 5.3.4*).

Analisi di sensitività e parametrica (cap. 6)

  • Analisi di sensitività: variazioni nella funzione obiettivo; variazioni nel termine noto.
  • Analisi parametrica rispetto al termine noto (andamento locale e globale della curva del valore ottimo, analisi grafica e interpretazione economica); analisi parametrica rispetto ai coefficienti di costo (andamento globale della curva del valore ottimo). 
  • Prezzi ombra: definizione, interpretazione economica e loro legame con i coefficienti di costo ridotto (teorema 6.4.1*); aggiunta di una nuova variabile; nozione di costo opportunità; interpretazione del report del simplesso.

Ottimizzazione nei grafi (cap.9)

  • Grafi
  • Alberi di supporto di costo minimo; modelli di ottimizzazione matematica; problemi di cammino minimo; Algoritmo di Dijstra. Problema del commesso viaggiatore.
  • Problemi di massimo flusso. Algoritmo di Ford-Fulkerson.

Ottimizzazione di progetti (cap. 10)

  • Rappresentazione di progetti mediante digrafi; scomposizione di un progetto in attività elementari; digrafi con le attività sui nodi; digrafi con le attività sugli archi; identificazione del cammino critico; calcolo degli istanti di inizio al più presto e al più tardi; diagrammi di gantt.
  • Modelli probabilistici per l'analisi PERT; distribuzione del tempo di completamento; analisi PERT di un progetto; analisi dei costi.
  • Modelli di ottimizzazione matematica; progetti a risorse illimitate,bilanciamento tempi e costi; progetti a risorse limitate.

Attività di laboratorio

E' previsto l'utilizzo di programmi di calcolo per formulare e risolvere esempi e casi applicativi.

 


Prerequisiti

Prerequisiti

Conoscenze matematiche di base relative all'analisi e al calcolo matriciale.


Modalità di valutazione

Gli appelli d'esame consistono in una  prova scritta, superata la quale, si  sostiene una prova orale.


Bibliografia
Risorsa bibliografica obbligatoriaCarlo Vercellis, OTTIMIZZAZIONE Teoria, metodi, applicazioni, Editore: McGraw-Hill, ISBN: 978-88-386-6442-7

Forme didattiche
Tipo Forma Didattica Ore di attività svolte in aula
(hh:mm)
Ore di studio autonome
(hh:mm)
Lezione
32:30
48:45
Esercitazione
17:30
26:15
Laboratorio Informatico
0:00
0:00
Laboratorio Sperimentale
0:00
0:00
Laboratorio Di Progetto
0:00
0:00
Totale 50:00 75:00

Informazioni in lingua inglese a supporto dell'internazionalizzazione
Insegnamento erogato in lingua Italiano
Disponibilità di materiale didattico/slides in lingua inglese
schedaincarico v. 1.6.1 / 1.6.1
Area Servizi ICT
22/02/2020