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

Da WikiDsy.
Riga 2: Riga 2:
  
 
== News ==
 
== News ==
 +
Le lezioni di Venerdì 17 e di Lunedì 20 saranno di preparazione al compitino.
 +
 
Il primo compitino sarà Venerdì 24 novembre 2006, presumibilmente con argomenti fino alla dualità compresa.
 
Il primo compitino sarà Venerdì 24 novembre 2006, presumibilmente con argomenti fino alla dualità compresa.
  
Riga 213: Riga 215:
 
*Teorema sul duale del duale
 
*Teorema sul duale del duale
 
*Esempi vari
 
*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

Versione delle 17:40, 14 nov 2006


News

Le lezioni di Venerdì 17 e di Lunedì 20 saranno di preparazione al compitino.

Il primo compitino sarà Venerdì 24 novembre 2006, presumibilmente con argomenti fino alla dualità compresa.

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 lunedì 20/11/06 si terrà in aula 202. Qui l'avviso.
  • 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
Estratto da "https://wiki.dsy.it/index.php?title=Fondamenti_di_ricerca_operativa/2006-2007&oldid=16391"