Orale del 8/01/15

1 ) Scrivere il modello del duale ausiliario e dire a cosa serve
2 ) Dare la definizione di una soluzione di base primale ammissibile non ottima. Costruirne una graficamente.
3 ) Disegnare un problema di PL (di massimo) illimitato superiormente e dire come il simplesso lo certifica
4 ) Disegnare una rete con due alberi distinti di cammini minimi e scrivere poi il vettore X di entrambi
5 ) Scrivere il modello matematico del problema dei potenziali su reti capacitate e dare poi la definizione di potenziale di base
6 ) Costruire un potenziale di base ammissibile ed uno non ottimo su una rete a 4 nodi e 5 archi
7 ) Dopo aver dato le definizioni descrivere la relazione tra assegnamento e cicli hamiltoniani
8 ) Enunciare il teorema di equivalenza tra PL e PLI e scrivere poi l'equazione del piano di taglio di Gomory
Orale del 19/01/15

1 ) illustrare il test di ottimalità per la PL, dire dove si utilizza e commentare il caso degenere
2 ) Dare la definizione e costruire graficamente una soluzione di base duale non ammissibile. Come si controlla l'ottimalità?
3 ) Dare la definizione di flusso di base e costruirne uno ottimo non unico
4 ) Dare la definizione di taglio di una rete, di capacità del taglio ed enunciare il teorema del MAX-FLOW MIN-CUT
5 ) Scrivere il modello matematico del problema del TSP simmetrico. Costruire poi un esempio a 5 nodi e scrivere un vincolo violato dalla valutazione inferiore
6 ) Illustrare l'algoritmo dei rendimenti, dire a cosa serve e mostrare con un esempio che a volte trova l'ottimo
7 ) Illustrare la regola anticiclo di Bland e dire a cosa serve
8 ) Illustrare il cambio di base del simplesso su reti capacitate
Orale del 29/01/15

1 ) dare la definizione di poliedro e disegnare poi un problema di PL con ottimo finito e poliedro illimitato
2 ) illustrare l'algoritmo del simplesso duale
3 ) enunciare il teorema di Weyl (rappresentazione dei poliedri) e dire a cosa serve. Esistono poliedri senza vertici?
4 ) scrivere il modello matematico dell'albero dei cammini minimi e disegnare un albero non ottimo per tale problema
5 ) dare la definizione di disuguaglianza valida e piano di taglio. scrivere l'equazione del piano di taglio di Gomory
6 ) enunciare il teorema di Bellman e costruire un potenziale ottimo degenere su una rete capacitata
7 ) Illustrare l'algoritmo delle toppe e dire a cosa serve
8 ) Dare la definizione di valutazione (superiore ed inferiore) per un problema di PLI ed illustrare le regole di taglio del Branch and Bound per problemi di massimo
Orale 13/02/15

1 ) Illustrare l'algoritmo del simplesso duale
2 ) Dare la definizione di poliedro e disegnarne uno con 3 vertici e una direzione di recessione
3 ) Scrivere il modello matematico del flusso massimo, descrivere la sua trasformata in problema di flusso su reti ed enunciare il teorema del Max-Flow Min-Cut
4 ) Dopo aver dato la definizione di potenziale di base, costruirne uno ottimo e degenere
5 ) Dare la definizione di disuguaglianza valida e di piano di taglio e scrivere l'equazione del piano di taglio di Gomory
6 ) Dare la definizione di 5-albero e disegnarne uno che sia un 2-albero ma che non sia un 6-albero
7 ) Enunciare il teorema della dualità per la PL e dire a cosa serve
8 ) Scrivere le regole di taglio del Branch and Bound per problemi di massimo. Cosa sono gli algoritmi greedy? Quali conosci?
Orale 22/06/2015

1 ) Dare la definizione di poliedro e disegnare una soluzione di base non ammissibile e degenere (primale/duale)
2 ) Scrivere il modello del flusso massimo e disegnare un taglio di capacità minima
3 ) Scrivere il (D) ausiliario e dire a cosa serve
4 ) Dare la definizione di potenziale di base e costruire un potenziale ottimo con 4 nodi e 5 archi
5 ) Definizione di assegnamento e di ciclo hamiltoniano e illustrare la relazione tra i due concetti
6 ) Elencare le regole di taglio Branch & Bound