Differenze tra le versioni di "Fondamenti di ricerca operativa/2006-2007"

Da WikiDsy.
(→‎Lezione di Venerdì 27 ottobre 2006)
 
(22 versioni intermedie di 5 utenti non mostrate)
Riga 2: Riga 2:
  
 
== News ==
 
== 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 ===
 
=== Lezioni cancellate/spostate ===
 +
*La lezione di venerdì 3/11/06 è annullata.
 +
=== Appelli ===
 
[...]
 
[...]
  
−
=== Appelli ===
+
== Anni precedenti ==
−
[...]
+
* [http://wiki.dsy.it/w/Fondamenti_di_ricerca_operativa/2005-2006 F.R.O. 05/06 sul Wiki]
  
 
== Informazioni generali ==
 
== Informazioni generali ==
Riga 26: Riga 34:
  
 
===  Orari e luogo delle lezioni ===
 
===  Orari e luogo delle lezioni ===
−
* Lunedì 13.30 - 15.15 in aula 305 (via Celoria)
+
* Lunedì: 13:30-15:30, aula G12, via Golgi
−
* Venerdì 14.30 - 16.15 in aula 305 (via Celoria)
+
* Venerdì: 14:30-16:30, aula G22, via Golgi
−
* Dal DICo: http://www.dico.unimi.it/occorrenza.php?z=0;id_occ=1197
+
* Dal DICo: http://www.dsi.unimi.it/avviso.php?z=0;pagina=avvisistudenti;id=4488
  
 
=== Orario di ricevimento studenti ===
 
=== Orario di ricevimento studenti ===
Riga 39: Riga 47:
 
* In DSI: http://homes.dsi.unimi.it/~trubian/studenti.htm
 
* In DSI: http://homes.dsi.unimi.it/~trubian/studenti.htm
  
−
=== Forum del corso, e affini ===
+
=== Forum del corso (non ufficiale) ===
 
* Da dsy: http://www.dsy.it/forum/forumdisplay.php?forumid=228
 
* Da dsy: http://www.dsy.it/forum/forumdisplay.php?forumid=228
  
Riga 74: Riga 82:
 
* Notazioni
 
* Notazioni
 
* Problema di programmazione dinamica
 
* 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 ===
 +
[http://homes.dsi.unimi.it/~trubian/aa200607.htm 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

Versione attuale delle 16:13, 15 lug 2008


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

Informazioni generali

Docenti

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

Orario di ricevimento studenti

  • Ricevimento su appuntamento tramite email
  • Stanza P103

Informazioni specifiche

Sito del corso

Forum del corso (non ufficiale)

Materiale didattico

Programma del corso

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

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

Estratto da "https://wiki.dsy.it/index.php?title=Fondamenti_di_ricerca_operativa/2006-2007&oldid=18771"