Complete course notes

Page 1

RIASSUNTO TEORICO METODI DI OTTIMIZZAZIONE DELLA RICERCA OPERATIV A PRIMA PARTE Dimostrazione 3.2.5 Dimostrazione 3.2.6 Dimostrazione 3.2.7 Dimostrazione 3.2.12 Dimostrazione 4.2.3 Dimostrazione 4.7.1 Dimostrazione 5.3.1 Corollario 1 Corollario 2 Dimostrazione 5.3.2 Dimostrazione 5.3.4 SECONDA PARTE Enunciato e dimostrazione di unimodularità Definizione e dimostrazione di taglio di Gomory Formulazione alberi di supporto con costo minimo Formulazione problema di cammino minimo Formulazione del problema di flusso massimo Problema del taglio di capacità minima Teoremi dualita’ debole e forte (pagine 22-24-24 delle slides) e saper giustificare la correttezza dell’arresto dell’algoritmo di flusso massimo (cioe’ che quando l’algoritmo s’arresta e’ perche’ si e’ individuato un taglio di capacita’ uguale al valore del flusso corrente) Formulazione costo minimo Formulazione commesso viaggiatore Teorema equivalenza VAM e VAPO PARTE I Teorema 3.2.5 - Caratterizzazione dei punti estremi Dato un poliedro P = {x ∈ Rn: Ax = b} e un vettore y ∈ P , dove A è una matrice di dimensioni m x n, sia I={i: a’it = bi} l’insieme degli indici dei vincoli attivi in y. Il vettore y è un punto estremo di P se e solo se esistono n vettori linearmente indipendenti nell’insieme, ossia se e solo se il rango della matrice è n. Dimostrazione -> Sia y un punto estremo di P e suppongo per assurdo che il rango di A sia minore di n. Questo implica l’esistenza di un vettore che soddisfa la relazione a’iw = 0, con i ∈ I. Poiché a’iy = bi per i che non appartiene ad I, allora esiste ℇ > 0, tale che i vettori u = y+ℇw e v = y-ℇw sono soluzioni del sistema a’iy ≤ bi . Ne consegue che i vincoli u e v soddisfano il sistema Ax ≤ b e quindi appartengono a P . Il vettore y può essere espresso come punto interno al…