Domande Orale Pappalardo

Rispondi
Avatar utente
InformateciBot
Messaggi: 314
Iscritto il: 30/09/2018, 16:33

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

Orale 11/01/2016

1) Dare la definizione di soluzione di base duale; dire cosa vuol dire degenere e disegnarne poi una non ammissibile
2) Scrivere il modello del duale ausiliario, dire a cosa serve ed enunciare il teorema che lo caratterizza
3) Scrivere il modello matematico del cammino minimo dal nodo i al nodo j e descrivere come risolverlo con il simplesso su reti
4) Costruire un potenziale di base non ammissibile degenere ed uno ottimo
5) Scrivere il modello matematico del problema del flusso massimo. Si può risolvere con il simplesso su reti? Perché?
6) Scrivere il modello matematico del TSP asimmetrico e dire come si calcolano valutazione superiore ed inferiore
7) Dare la definizione di flusso di base su una rete capacitata ed illustrare il cambio di base nel simplesso su reti capacitate
8 ) Dopo aver dato la definizione di taglio di una rete, illustrare l'algoritmo di Ford-Fulkerson

Orale 21/01/2016

1. Dare la definizione di soluzione di base primale e disegnarne una non ammissibile-degenere ed una ottima

2. Illustrare il simplesso primale e dimostrare la correttezza della scelta dell'indice h.

3. Enunciare la regola anticiclo di Bland per la PL (per h e per k) e dire a cosa serve.

4. Dare la definizione di taglio e di capacità di un taglio fornendo un esempio di rete con due tagli di capacità minima

5. Scrivere il modello matematico del problema dei potenziali su reti capacitate e non capacitate

6. Costruire un flusso di base non ammissibile e poi uno ottimo e degenere

7. Illustrare l'algoritmo che fornisce la soluzione ottima del rilassamento continuo del problema dello zaino 0-1 e di quello dello zaino intero.

8. Enunciare il teorema di equivalenza tra PL e PLI e scrivere poi l'equazione del piano di taglio di Gomory.

Orale 16 febbraio 2016
1) Dare la definizione di poliedro e disegnarne uno che abbia 4 elementi in V e 3 elementi in E
2) Illustrare l'algoritmo del simplesso duale
3) Enunciare il teorema fondamentale della PL e dire a cosa serve
4) Scrivere il modello matematico dell'albero dei cammini minimi e disegnare un albero non ottimo per tale problema
5) Dare la definizione di taglio di una rete, di capacità del taglio e scrivere un flusso ottimo per il problema max-flow
6) Dare la definizione di flusso di base e costruire un flusso ottimo degenere su una rete con almeno 4 nodi ed almeno 5 archi
7) Illustrare l'algoritmo delle toppe e l'algoritmo del nodo più vicino e dire a cosa servono
8 ) Dare la definizione di valutazione per un problema di PLI ed illustrare le regole di taglio del Branch and Bound per per problemi di massimo

Per chi non ha mai assistito ad un orale preciso che queste domande sono da scrivere su un foglio protocollo (max mezza pagina per ciascuna domanda, 40 minuti di tempo a disposizione). Dopo lo corregge, mette un voto (max 4 punti a domanda), fa la media con lo scritto vero e proprio, e vi fa delle domande (la parte orale vera e propria è abbastanza breve). Comunque il voto non si discosta moltissimo dalla media tra scritto vero e proprio ed orale-scritto fatto poco prima.

Orale 22 febbraio 2016

1) Dare la definizione di vertice di un poliedro ed enunciare il teorema di rappresentazione dei poliedri.
2) Scrivere il modello del duale ausiliario, dire a cosa serve ed enunciare il teorema che lo caratterizza.
3) Scrivere il modello matematico del problema del flusso massimo e descrivere come risolverlo con simplesso su reti.
4) Su una rete a 4 nodi e 5 archi costruire un potenziale di base non ammissibile degenere ed uno ottimo.
5) Scrivere il modello matematico del problema dell'assegnamento di costo minimo. Si può omettere il vincolo di interezza? Perché?
6) Dare la definizione di k-albero e dire a cosa serve.
7) Dare la definizione di piano di taglio* e scrivere l'equazione del piano di taglio di Gomory specificando il significato delle notazioni usate.
8) Scrivere il modello matematico del problema dello zaino binario illustrando gli algoritmi per la costruzione di una valutazione inferiore ed una superiore.

*Piano di taglio: [math]

29/06/2016

1) enunciare il teorema di rappresentazione dei poliedri (weyl). disegnare poi un poliedro con due elementi di E conicamente indipendenti indicando l'insieme V.
2) elencare i metodi per trasformare un generico problema di PL in uno standard primale ed in uno standard duale
3) scrivere il modello matematico del problema dei potenziali su reti capacitate e non capacitate
4) costruire un flusso di base ammissibile, uno non ammissibile, ed uno ottimo degenere
5) dare la deffinizione di disuguaglianza valida e di piano di taglio e scrivere poi l'equazione del piano di taglio di gomory
6) dare la definizione di assegnamento ed illustrare l'algoritmo delle toppe
7) illustrare l'algoritmo di ford-fulkerson
8) scrivere il duale ausiliario ed enunciare il teorema che mostra a cosa serve nella teoria della PL

Orale 13/09/2016

1. Dare la definizione di soluzione di base primale e disegnarne una ammissibile ed una non ammissibile e degenere
2. Illustrare l'algoritmo del simplesso duale
3. Enunciare il teorema di Weyl (rappresentazione dei poliedri) e dire a cosa serve
4. Scrivere il modello matematico del problema del flusso massimo e dire come si possa risolvere con l'algoritmo del simplesso
5. Dare la definizione di taglio di una rete, di capacità del taglio e disegnarne uno non ottimo
6. Dare la definizione di potenziale di base e costruirne uno ottimo degenere su una rete con almeno 4 nodi ed almeno 5 archi
7. Illustrare l'algoritmo delle toppe e dire a cosa serve
8. Dare la definizione di valutazione per un problema di PLI ed illustrare le regole di taglio del Branch and Bound per problemi di massimo

Orale 09/01/2017

1) Dare la definizione di soluzione di base duale; dire cosa vuol dire degenere e disegnarne poi una non ammissibile ed una ammissibile.

2) Scrivere il modello del duale ausiliario, dire a cosa serve ed enunciare il teorema che lo caratterizza.

3) Scrivere il modello matematico del flusso massimo dal nodo i al nodo j e descrivere come risolverlo con il simplesso su reti.

4) Costruire un flusso di base non ammissibile degenere ed uno ottimo.

5) Dare la definizione di disuguaglianza valida e di piano di taglio. Scrivere la disequazione di taglio di Gomory.

6) Scrivere il modello matematico del TSP asimmetrico e simmetrico.

7) Dare la definizione di flusso di base su una rete capacitata ed illustrare il cambio di base nel simplesso su reti capacitate.

8) Dopo aver dato la definizione di taglio di una rete (per problemi di flusso massimo), illustrare brevemente l'algoritmo di Ford-Fulkerson.

Orale 19/01/2017

1.Dare la definizione di soluzione di pase primale, dire cosa significa degenere e disegnarne poi una non ammissibile ed una ottima non unica.
2.Enunciare il teorema fondamentale della PL e fornirne una breve dimostrazione.
3.Scrivere il modello matematico del cammino minimo dal nodo i al nodo j e descrivere come risolverlo con un simplesso su reti.
4.Costruire un potenziale di base degenere ed uno ottimo.
5.Dare la definizione di poliedro e di vertice di n poliedro.
6.Descrivere gli algoritmi per il calcolo delle valutazioni superiori e inferiori dello zaino binario.
7.Dare la definizione di potenziale di base su una rete capacitata ed enunciare il teorema di Bellman.
8.Illustrare l'algoritmo di Djkstra.

Orale 26/01/2017

1. Scrivere il modello del duale ausiliario e dire a cosa serve.
2. Dare la definizione di 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 ottimo x di entrambi
5. Scrivere i modelli matematici dei problemi di flusso di costo minimo e dei potenziali su reti capacitate
6. Costruire un potenziale di base ammissibile ed uno non ottimo su una rete capacitata a 4 nodi e 5 archi
7. Dopo aver dato le definizioni descrivere la relazione tra assegnamenti 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 08/02/2017

1. Dare la definizione di soluzione di base duale e disegnarne una degenere ed una ottima
2. Illustrare brevemente il simplesso primale e dimostrare la correttezza della scelta dell'indice k
3. Enunciare la regola anticiclo di Bland per la PL (per h e k) e dire a cosa serve.
4. Dare la definizione di assegnamento fornendo un esempio (5x5) con due assegnamenti ottimi distinti.
5. Scrivere il modello matematico del problema dei potenziali su reti capacitate e non capacitate
6. Costruire, su una rete a 4 nodi e 5 archi, un flusso di base non ammissibile e poi uno non di base
7. Illustrare l'algoritmo che fornisce la soluzione ottima del rilassamento continuo del problema delle zaino 0-1 e di quello dello zaino intero
8. Elencare le regole di taglio del Branch and Bound per problemi di massimo e per problemi di minimo

Domande orale Pappalardo del 16/02/2017

1. Scrivere modello duale ausiliario e dire a cosa serve
2. Dare definizione "poliedro" e "vertice". Disegnare una soluzione di base duale ammissibile e una non ammissibile.
3. Disegnare problema di PL (di massimo) illimitato superiormente e dire come il simplesso lo certifica (risposta: trattare il caso di AiW^h<0 per ogni i appartenente a N).
4. Definizione di "capacita di un taglio", disegnare rete con due tagli di capacità minima distinti. (risposta disegno: io mi sono ricordata di max flow min cut).
5. Scrivere modello matematico del problema dei potenziali su reti capacitare e dare la definizione di "flusso di base su reti capacitate". (il modello è il duale di quello del flusso min cx/Ex=b/0<=x<=u)
6. Definizione "k-albero" e "ciclo hamiltoniano". Descrivere la loro relazione. (Possibile risposta: parlare del TSP).
7. Enunciare "Teorema di equivalenza tra PL e PLI". Scrivere equazione del taglio di Gomory. (Il teorema è quello che dice che dato S limitato e A,b razionali allora max cx dato x appartenente a S = max cx dato x appartenente a convS. Consiglio:descrivere l'equazione, dire esempio cos'è a tilde ecc.)

Domande del pre-orale scritto del 09/03/2017

1. Dare la definizione di soluzione di base duale e disegnarne una non ammissibile ed una ottima.
2. Illustrare il simplesso primale e dimostrare la correttezza della scelta dell'indice h.
3. Enunciare la regola anticiclo di Bland per la PL (per h e per k) e dire a cosa serve.
4. Dare la definizione di taglio e di capacità di un taglio fornendo un esempio di rete con due tagli di capacità minima.
5. Scrivere il modello matematico del problema dei potenziali su reti capacitate e non capacitate.
6. Costruire un flusso di base non ammissibile e poi uno ottimo e degenere.
7. Illustrare l'algoritmo che fornisce la soluzione ottima del rilassamento continuo del problema dello zaino 0-1 e di quello dello zaino intero.
8. Enunciare il teorema di equivalenza tra PL e PLI e scrivere poi l'equazione del piano di taglio di Gomory.

Consiglio di non dimenticare nulla nello scrivere le risposte dato che è piuttosto fiscale nel punteggio.
Il voto concorrerà a fare media assieme allo scritto, non discostandosi molto da quello finale.


Qualche domanda orale fatta quel giorno:

1. Regole del Branch & Bound per lo zaino 0-1
2. Algoritmo delle toppe.
3. Implementando l'algoritmo del simplesso su un calcolatore, cosa dovresti fare per poter fornire al programma una base ammissibile di partenza ?

Raccolgo in questa breve nota le mie impressioni della prova "scritto-orale" del 29/01/2018 di Ricerca Operativa.

DOMANDE:

1. Dare la definizione di soluzione di base duale; dire cosa vuol dire degenere e disegnare poi una non ammissibile. ( -> disegno: fo non nel cono di competenza )
2. Scrivere il modello del duale ausiliario, dire a cosa serve ed enunciare il teorema che lo caratterizza. ( -> Teorema 3.2.2. pg 81 )
3. Scrivere il modello di cammino minimo dal nodo i al nodo j e mostrare con un esempio che la soluzione ottima può non essere unica. ( -> il modello va modificato, il bilancio del nodo sorgente va messo a -1, nodo destinazione a 1 e i restanti a 0 )
4. Costruire una rete capacitata ad almeno 4 nodi e 5 archi, un potenziale di base non ammissibile ed uno degenere.
5. Enunciare e dimostrare il test di ottimali per la PL. ( -> Teorema 2.3.6. (Scarti complementari) )
6. Scrivere il modello matematico del TSP asimmetrico e dire come si calcolano la valutazione superiore ed inferiore. ( -> Vi: Rilassamento vincolo 3, Vs: algoritmo delle toppe )
7. Dare la definizione di potenziale di base su una rete capacitata e illustrare il cambio di base nel simplesso si reti capacitate.
8. Dopo aver dato la definizione di taglio di una rete, illustrare l'algoritmo di Ford-Fulkerson.

orale febbraio 2018:
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 trasformazione in problema di flusso su reti ed ennunciare il teorema max/flow-min/cut
4 Dopo aver dato la definizione di potenziale di base,costruirne uno ottimo e degenere su una rete capacitata a 4 nodi e 5 archi
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 sia 6-albero
7 Enunciare e dimostrare il teorema che caratterizza le basi dei problemi di flusso di costo minimo come albero di copertura
8 Enunciare il teorema della dualita' forte e dire a cosa serve e quando si applica

Orale Luglio 2018
1. Dare la definizione di soluzione di base primale e dire cosa vuol dire degenere. Disegnare una soluzione di base primale non ammissibile ed una soluzione primale ammissibile non di base.
2. Dare la definizione di piano di taglio e scrivere l'equazione del piano di taglio di Gomory.
3. Scrivere il modello matematico del cammino minimo dal nodo i al nodo j e descrivere come risolverlo con il simplesso su reti.
4. Su una rete capacitata a 4 nodi e 5 archi, costruire un flusso di base ammissibile degenere ed uno non di base ottimo.
5. Scrivere il modello matematico del problema dell'assegnamento di costo minimo. Lo si pu6
risolvere con il simplesso su reti? Perché?
6. Scrivere il modello matematico del TSP simmetrico e di quello asimmetrico.
7. Dare la definizione di potenziale di base su una rete capacitata. Cosa dice il teorema di
Bellman?
8. Dopo aver dato la definizione di taglio di una rete, illustrare l'algoritmo di Ford-Fulkerson.
Rispondi

Torna a “[RO] Ricerca Operativa”