Ottimizzazione su rete - Esercizi

Università degli Studi di Napoli "Federico II" - Facoltà di Ingegneria

Corso di Ottimizzazione su Rete (Prof. Antonio Sforza)

Prova scritta del 15.09.2009

Esercizio n. 1

• Si diano le seguenti definizioni: grafo, densità di un grafo, grafo pieno, grafo fortemente connesso, grafo a livelli, arborescenza, albero.
• Qual è la differenza tra grafo e rete? Come si definisce una rete?

Esercizio n. 2

Si descrivano le strutture dati note per la rappresentazione di un grafo.

Esercizio n. 3

• Si illustri la classificazione dei problemi e degli algoritmi di minimo percorso.
• Si descriva il modello del minimo percorso.
• Quale problema di minimo percorso risolve il modello descritto?
• Si determini l'arborescenza dei minimi percorsi con origine nel vertice 1 della rete in figura, utilizzando l'algoritmo di Bellman.
• Qual è la complessità computazionale dell'algoritmo utilizzato?

Esercizio n. 4

• Si consideri la rete in figura, sulla quale sono riportati il costo di spostamento su ciascun arco ed il flusso generato o attratto da ciascun nodo. Si scriva il modello di flusso single-commodity senza vincoli di capacità e la tabella del simplesso associata al caso in figura, senza riportare le variabili artificiali.
• Si costruisca per tentativi una prima soluzione basica ammissibile del problema, indicando la configurazione dei flussi e il costo totale della soluzione.
• Qual è la struttura della soluzione?
• Si descriva l'algoritmo del Simplesso su rete per la effettuazione di uno step a partire dalla prima s.b.a.

Esercizio n. 1

a) Si diano le seguenti definizioni: grafo, densità di un grafo, grafo pieno, grafo fortemente connesso, grafo a livelli, arborescenza, albero.

b) Qual è la differenza tra grafo e rete? Come si definisce una rete?

Esercizio n. 2

Si descrivano le strutture dati note per la rappresentazione di un grafo.

Esercizio n. 3

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

b) Si descriva il modello del minimo percorso.

c) Quale problema di minimo percorso risolve il modello descritto?

d) Si determini l'arborescenza dei minimi percorsi con origine nel vertice 1 della rete in figura, utilizzando l'algoritmo di Bellman.

e) Qual è la complessità computazionale dell'algoritmo utilizzato?

Esercizio n. 4

a) Si consideri la rete in figura, sulla quale sono riportati il costo di spostamento su ciascun arco ed il flusso generato o attratto da ciascun nodo. Si scriva il modello di flusso single-commodity senza vincoli di capacità e la tabella del simplesso associata al caso in figura, senza riportare le variabili artificiali.

b) Si costruisca per tentativi una prima soluzione basica ammissibile del problema, indicando la configurazione dei flussi e il costo totale della soluzione.

c) Qual è la struttura della soluzione?

d) Si descriva l'algoritmo del Simplesso su rete per la effettuazione di uno step a partire dalla prima s.b.a.