Ottimizzazione su rete - Esercizi

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

Corso di Ottimizzazione su Rete (Prof. Antonio Sforza)

Prova scritta del 19.6.2009

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 dati con liste a puntatore

Esercizio n. 3

1. Si illustri la classificazione nota dei problemi di ottimizzazione su rete

Esercizio n. 4

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.

1. 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. 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. Si determini la soluzione ottima del problema in figura, utilizzando l'algoritmo del simplesso su rete.

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

Corso di Ottimizzazione su Rete (Prof. Antonio Sforza)

Prova scritta del 19.6.2009

Esercizio n. 1

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

1. Qual è la densità del grafo?
2. Il grafo è pieno?
3. Il grafo è completo?
4. È 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 dati con liste a puntatore

Esercizio n. 3

Si illustri la classificazione nota dei problemi di ottimizzazione su rete

Esercizio n. 4

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.

1. 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.
2. Per quale motivo e sotto quali circostanze la soluzione di un modello di flusso single-commodity è intera anche se non si impone esplicitamente il vincolo di interezza delle variabili?
3. Si determini la soluzione ottima del problema in figura, utilizzando l'algoritmo del simplesso su rete.