Fondamenti di ricerca operativa/2006-2007

Da WikiDsy.


News

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
Estratto da "https://wiki.dsy.it/index.php?title=Fondamenti_di_ricerca_operativa/2006-2007&oldid=16366"