Ottimizzazione su Rete - Prova d'esame Giugno 2010

Universita' degli Studi di Napoli "Federico II" - Facolta' di Ingegneria

Corso di Ottimizzazione su Rete (Prof. Antonio Sforza)

Prova scritta del 28.6.2010

Esercizio n. 1

Con riferimento al grafo in figura si risponda alle seguenti domande:

1. Qual e' la densita' del grafo?
2. Il grafo e' pieno?
3. Il grafo e' completo?
4. E' fortemente connesso?

Esercizio n. 2

Per il grafo dell'esercizio 1 si scriva:

• la matrice di adiacenza con i costi di spostamento, assumendo che ciascun arco abbia un costo pari al numero del suo vertice destinazione.
• La struttura con liste e puntatore
• La matrice di incidenza arco-percorso per la coppia di vertici 1-6

Esercizio n. 3

1. Si illustri la classificazione dei problemi e degli algoritmi di minimo percorso

Esercizio n. 4

Si consideri la rete in figura, sulla quale sono riportati i costi di spostamento su ciascun arco, il flusso generato o attratto da ciascun nodo e la soluzione basica ammissibile iniziale riportata in figura con tratto doppio.

1. (a) Si scriva il modello di flusso single-commodity senza vincoli di capacita' e la tabella del simplesso associata al caso in figura, senza riportare le variabili artificiali.
2. (b) Per quale motivo e sotto quali circostanze la soluzione di un modello di flusso single-commodity e' intera anche se non si impone esplicitamente il vincolo di interezza delle variabili?
3. (c) Si determini la soluzione ottima del problema in figura, utilizzando l'algoritmo del simplesso su rete.