Fondamenti di ricerca operativa/2006-2007

Da WikiDsy.
Versione del 15 nov 2007 alle 17:19 di 151.23.84.110 (discussione) (→‎Lezione di lunedì 27 novembre 2006)


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=18170"