Fondamenti di ricerca operativa/2006-2007

News

Il primo compitino si svolgerà alle 14.20 in aula G12. Gli argomenti sono tutti quelli trattati fino all'analisi di sensività su vincoli e funzione obiettivo.

Tratto da: http://www.dsi.unimi.it/avviso.php?z=0;pagina=avvisistudenti;id=4488:

• Si avvisano gli studenti che a partire dal 13 Ottobre le lezioni di Fondamenti di ricerca operativa si terranno nelle seguenti aule:
  • Lunedì: 13:30-15:30, aula G12, via Golgi
  • Venerdì: 14:30-16:30, aula G22, via Golgi

Lezioni cancellate/spostate

• La lezione di venerdì 3/11/06 è annullata.

Appelli

[...]

Anni precedenti

• F.R.O. 05/06 sul Wiki

Informazioni generali

Docenti

• Prof. Marco Trubian
  • Email: trubian [AT] dsi [DOT] unimi [DOT] it
  • Pagina personale sul DSI: http://homes.dsi.unimi.it/~trubian/
  • Pagina personale sul DICo: http://www.dico.unimi.it/persona.php?z=0;id_persona=284

Modalità d'esame

(come anno precedente) L’esame consisterà in una prova scritta, che viene considerata valida se la valutazione è maggiore o uguale a 17, e in una parte orale obbligatoria per chi ha un voto dello scritto pari a 17 o 18 oppure >=28. La parte orale consiste nella discussione dello scritto e in un'eventuale integrazione, ed è facoltativa per chi ottiene un punteggio nello scritto tra il 19 e il 27. Sono inoltre previste 2 prove in itinere (che valgono come scritto).

Prerequisiti al corso

Elementi di algebra delle matrici.

Orari e luogo delle lezioni

• Lunedì: 13:30-15:30, aula G12, via Golgi
• Venerdì: 14:30-16:30, aula G22, via Golgi
• Dal DICo: http://www.dsi.unimi.it/avviso.php?z=0;pagina=avvisistudenti;id=4488

Orario di ricevimento studenti

• Ricevimento su appuntamento tramite email
• Stanza P103

Informazioni specifiche

Sito del corso

• In DSI: http://homes.dsi.unimi.it/~trubian/studenti.htm

Forum del corso (non ufficiale)

• Da dsy: http://www.dsy.it/forum/forumdisplay.php?forumid=228

Materiale didattico

Programma del corso

• Dal DICo: http://www.dico.unimi.it/files/occorrenza/programma/programma815291.pdf

Testi

• M. Fischetti - "Lezioni di Ricerca Operativa" - Edizioni Libreria Progetto Padova, 1995.

• R. Baldacci, M. Dell'Amico - "Fondamenti di Ricerca Operativa" - Pitagora Editrice Bologna, 2002. (Contiene i lucidi del corso)

• M. Dell’Amico - "120 esercizi di ricerca operativa" - Pitagora Editrice Bologna, 1996. (Eserciziario)

Altro materiale

• Come esercizi preparatori sono inoltre suggeriti i vecchi temi d'esame reperibili sul sito del Prof. Trubian: http://homes.dsi.unimi.it/~trubian/studenti.htm.

• Alcuni appunti online disponibili sul DSY

Diario del corso

Lezione di Lunedì 02 ottobre 2006

• Introduzione al corso e informazioni generali
• Ricerca Operativa
  • Definizione
  • Origini
• Esempi di modellizzazione di problemi
  • Distribuzione ottimale sul territorio di centraline di rilevazione sismica o di trasmettitori (set covering)
  • Problema dei 7 ponti di Köenigsberg (Kaliningrad)
  • Problema dell'assegnazione del personale
• Programmazione matematica
• Notazioni
• Problema di programmazione dinamica

Lezione di Venerdì 06 ottobre 2006

• Combinazione convessa, insieme convesso, funzione convessa e funzione concava
• Intersezione di insiemi convessi
• Teoremi
• Minimo locale e minimo globale

Lezione di Lunedì 09 ottobre 2006

• Metodo di risoluzione grafica di un problema di PL
  • Disegno sul grafico cartesiano dei vincoli
  • Disegno sul grafico cartesiano della funzione obiettivo
  • Metodo del gradiente per il calcolo del vertice ottimo
• Modelli di PL
  • Problema di MIX PRODUTTIVO
  • Problema dell'ASSEGNAMENTO

Lezione di Venerdì 13 ottobre 2006

• Scrittura della matrice dei coefficienti dei vincoli
• Scrittura del vettore delle variabili
• Scrittura del vettore dei termini noti dei vincoli
• Modelli di PL
  • Problema della DIETA
  • Problema del SISTEMA DI PRODUZIONE MONOPRODOTTO
  • Problema del SISTEMA DI PRODUZIONE MULTIPRODOTTO
  • Problema del TRASPORTO
  • Problema KNAPSACK
  • Problema BIN PACKING

Lezione di Lunedì 16 ottobre 2006

• Problema di MIX PRODUTTIVO con introduzione di lotto minimo
  • Modellizzazione con introduzione della variabile di supporto M ("emme grande")
• Problema BLENDING
• Problema di TURNAZIONE DEL PERSONALE
• Problema di SEQUENZIAMENTO SU MACCHINA SINGOLA con dead-line
  • Modellizzazione con introduzione della variabile di supporto M
• Uso della variabile di supporto M per modellare vincoli alternativi (OR esclusivo)

Lezione di Venerdì 20 ottobre 2006

• Standardizzazione di un problema di PL
  • Standardizzazione dei vincoli
    • Vincoli di disuguaglianza
    • Variabili di scarto
  • Standardizzazione delle variabili
    • Variabili negative
    • Variabili libere in segno
  • Standardizzazione dei termini noti col metodo del cambio di segno
• Esempi di standardizzazione di problemi
• Semispazio affine
• Iperpiano
• Poliedro
• Politopo
• Vertici e punti di un poliedro
  • Teorema della finitezza dei vertici
  • Teorema della ricavabilità dei punti di un poliedro per combinazione convessa dei vertici
    • Estensione a k vertici del concetto di combinazione convessa
  • Teorema delle soluzioni ottime su vertici
• Risoluzione di un problema di PL in forma grafica dopo standardizzazione

Lezione di Lunedì 23 ottobre 2006

• Matrice A dei coefficienti dei vincoli
• Concetto di Base/Variabili in base/Variabili fuori base
• Matrice B dei coefficienti delle variabili in base
• Matrice F dei coefficienti delle variabili fuori base
• Calcolo dei vertici/delle soluzioni considerando i vincoli
• Calcolo della soluzione associata ad un vertice/ad una base
• Concetto di Base degenere e sua correlazione con vertici e soluzioni
• Teorema della doppia implicazione tra vertice e soluzione di base corrispondente alla base

Lezione di Venerdì 27 ottobre 2006

• Corollario del teorema della lezione precedente sull'esistenza di una soluzione ammissibile di base ottima
• Algoritmo del simplesso
  • Forma canonica di un problema di PL
  • Teorema dell'ottimalità di una soluzione di base ammissibile
  • Condizioni di ottimalità
  • Vettore dei coefficienti di costo ridotto
  • Esempio di risoluzione di un problema
    • Calcolo della base iniziale
    • Calcolo dell'ottimalità
    • Criteri per il cambio di base
    • Cambio di base
    • Rappresentazione grafica del cambio di base
    • Condizioni di scelta per la variabile da far entrare in base..

Lezione di Lunedì 30 ottobre 2006

• Completato l'esempio di risoluzione di un problema
• Risoluzione dello stesso problema col metodo del tableau
  • Sistemazione del problema nel tableau
  • Significato di righe e colonne del tableau
  • Cambio di base nel tableau
    • Condizioni di scelta
    • Passo di pivot
    • Creazione del nuovo tableau
  • Riconoscimento della soluzione ottima

Lezione di Venerdì 3 novembre 2006

Lezione annullata.

Lezione di Lunedì 6 novembre 2006

AVVISO: il prof. ha comunicato la data del primo compitino, il 24 novembre. Ulteriori informazioni verranno scritte nella sezione "news" in questa stessa pagina (all'inizio).

• Metodo delle 2 fasi (come affrontare un problema nel quale non è individuabile una base ammissibile di partenza)
  • Condizioni di utilizzo
  • Sostituzione del problema originale con quello di supporto
    • Nuova funzione obiettivo
    • Nuove variabili e loro posizione
  • Risoluzione del problema di supporto
  • Caso 1: presenza di variabili ausiliarie non nulle nella soluzione ottima trovata
  • Caso 2:
    • Sottocaso 1: assenza di variabili ausiliarie nella soluzione ottima trovata
    • Sottocaso 2: presenza di variabili ausiliarie solo nulle nella soluzione ottima trovata
  • Rotorno al problema originario e sua risoluzione
• Regola di Bland
• Teorema per la validità della regola di Bland
• Problema ben posto e mal posto
  • Condizioni
  • Esempio di problema mal posto
• Dualità
  • Ambito di interesse della dualità
  • Formulazioni di disequazioni valide per il politopo P di riferimento
    • Partenza
    • Operazioni valide
    • Disequazioni trovate e loro forma generale

Lezione di Venerdì 10 novembre 2006

• Lemma di Farkas
• Conversione da primale a duale
• Conversione da primale a duale partendo dalla forma non standard
• Tabella per la conversione da primale a duale
• Teorema sul duale del duale
• Esempi vari

Lezione di Lunedì 13 novembre 2006

• Duale del problema del trasporto
• Teorema di Dualità Forte
• Teorema di Dualità Debole
• Corollario
• Interpretazione del problema duale e delle sue variabili
  • Interpretazione algebrica
  • Interpretazione geometrica
  • Interpretazione economica
  • Interpretazione come variazione della funzione obiettivo al variare dei termini noti (prezzi ombra)
• Risoluzione del duale mediante gli scarti complementari
• Esercizi

Lezione di venerdì 17 novembre 2006

• Analisi del possibile cambiamento dei termini noti dei vincoli senza cambiare la composizione della base ottima
• Analisi del possibile cambiamento dei coefficienti della funzione obiettivo senza cambiare la composizione della base ottima
• Esercizi in preparazione del compitino

Lezione di lunedì 20 novembre 2006

• Esercizi in preparazione al compitino
• Analisi della sensitività per via algebrica
• Spiegazione della correlazione tra variabile duale e vincolo primale e implicazione nel segno delle varibili duali

Lezione di lunedì 27 novembre 2006

• Ulteriore interpretazione delle variabili duali-prezzi ombra: l'analisi parametrica
• Principio dei profitti marginali non crescenti
• Programmazione Lineare Intera (PLI)
  • Introduzione
  • PL come rilassamento continuo della PLI
  • Convex Hull
  • Formulazione ideale di un problema di PL
  • Matrici unimodulari e totalmente unimodulari: definizioni e teoremi
  • Esempio di matrice totalmente unimodulare

NO