Ottimizzazione su Rete - Prova d'esame Giugno 2011

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

Corso di Ottimizzazione su Rete (Prof. Antonio Sforza) - Prova scritta del 22.06.2011

Esercizio n. 1

Per il grafo in figura si scriva:

• a) la matrice di adiacenza vertice-vertice
• b) la matrice dei costi sul grafo
• c) la matrice di incidenza vertice-arco
• d) la matrice di incidenza arco-percorso per le coppie origine/destinazione 4-1 e 4-5
• e) la struttura dati lista con puntatori

Esercizio n. 2

• (a) La rete dell'esercizio 1 rispetta le condizioni per cui il circuito minimo della rete sia hamiltoniano?
• (b) Se il circuito minimo di una rete non e' hamiltoniano come si effettua la sua determinazione?
• (c) Per il grafo dell'esercizio 1 esiste un circuito euleriano? Qualunque sia la risposta spiegare perché.

Esercizio n. 3

Si consideri la rete in figura, sulla quale sono riportati il costo di spostamento su ciascun arco, il flusso generato o attratto da ciascun nodo e in tratto doppio l'albero di una soluzione basica ammissibile iniziale.

• (a) Si scriva il modello di flusso single-commodity senza vincoli di capacità e la tabella del simplesso per la rete in figura, senza riportare le variabili artificiali.
• (b) Si determini la configurazione di flusso per la soluzione iniziale segnata in figura con tratto doppio e si dica a quale tipo di soluzione basica ammissibile corrisponde.
• (c) A partire da questa soluzione si determini la soluzione ottima del problema, utilizzando l'algoritmo del simplesso su rete.

Esercizio n. 4

Si dimostri la corrispondenza tra le soluzioni basiche ammissibili di un problema di flusso single commodity e gli alberi estraibili dalla rete.