Rete di flusso 3

Page 1

Esercitazione MORO - 11 Gennaio 2017 Esercizio 1. Calcolare il cammino minimo tra tutte le coppie di nodi sul se guente grafo: 1 2 3 4 6 5 10 3 -2 3-2 -4 -3 -5 12 Esercizio 2. Determinare il flusso ammissibile di valore massimo dal nodo 1 al nodo 7 nel seguente grafo, in cui sono indicati, per ogni arco, la quantit` a iniziale di prodotto che lo attraversa e la capacit` a. Illustrare i passi dell’algoritmo applicato e indicare un taglio di cap acit` a minima. 1 2 4 3 5 6 7 3,6 5,10 6,6 3,3 0,3 4,4 5,5 4,5 2,7 7,9 2,8 Esercizio 3. Si determini un flusso di valore massimo dal nodo 1 al nodo 7 nel la rete G = ( N, A) sotto riportata, con capacit` a qij sugli archi in A. Si indichi anche un taglio di capacit` a minima. 6 6 1 3 3 7 1 1 4 5 4 1 2 3 4 5 6 7 Esercizio 4. Come si pu` o tener conto anche dei limiti di capacit` a su cert i nodi (ad esempio, per modellizzare il numero di porte in un nodo di una rete di comunicazione)? Si trovi un flusso ammissibile massimo nella rete dell’esercizio 2 ipotizzando una capacit` a pari a 2 nel nodo 6. Esercizio 5. Una Software House deve stabilire se tre progetti possono es sere completati durante i prossimi quattro mesi rispettando il seguente calendario: il proget to P1, che pu` o iniziare solo dopo il primo mese, deve essere terminato entro il terzo mese, i progetti P2 e P3, che possono iniziare subito, devono essere completati rispettivamente entro il quarto e il secondo mes e. I progetti richiedono rispettivamente 8, 10 e 12 mesi uomo. Ogni mese sono disponibili otto ingegneri a tempo pieno, per` o solo sei di essi possono lavorare contemporaneamente su uno stesso progetto. `E possibile terminare i tre progetti in tempo? Si spieghi com e ricondurre il problema in esame ad un problema di flusso massi mo. [Suggerimento: esiste un flusso…