21 07 17

Pagina 1

Politecnico di Milano Corso di Laurea in Ingegneria Gestionale Proff. E. Amaldi e M. Bruglieri METODI DI OTTIMIZZAZIONE DELLA RICERCA OPERATIVA Appello del 21 Luglio 2017 Parte II Cognome: Nome: Matricola: Usare solo i fogli allegati. Indicare le risposte nei punti appositamente previsti. Motivare tutti i passaggi sul retro della pagina precedente. Si raccomandano chiarezza, precisione e concisione nelle risposte. Non si possono consultare libri, appunti, ecc. Problema 3 Si consideri la seguente rete di telecomunicazione in cui il primo numero riportato accanto ad ogni arco corrisponde alla quantit` a iniziale di dati (in Gbit/s) che lo attraversa al secondo e il secondo numero alla sua capacit` a(in Gbit/s). Determinare la quantit` a massima di dati che si pu` o inviare per unit` a di tempo dal nodos al nodo t, partendo dal flusso ammissibile di valore 4 riportato in figura. a) Indicare la rete con il flusso ammissibile di valore massimo trovato, precisando sia il valore complessivo del flusso che la quantit` adi dati inviata attraverso ogni arco della rete per unit` a di tempo. Riportare tutti i passaggi sul retro della pagina precedente . b) Indicare un taglio di capacit` a minima sulla rete del punto a). c) Spiegare quale legame esiste tra un flusso di valore massimo e un taglio di capacit` a minima, motivando la risposta. d) Come varia il flusso ammissibile di valore massimo se la capacit` a dell’arco (1 , 4) viene ridotta da 3 a 1? Cosa succede se invece l’arco (3 , 2) viene rimosso dal grafo? Problema 4 Si consideri il seguente problema di Programmazione Lineare Intera: max x1 −x1 + x2 ≥ − 2 x1 + 3x2 ≤ 12 x1, x2 ≥ 0 intere a) Determinare per via grafica la soluzione ottima del rilassamento continuo sul retro della pagina precedente. Indicare qui sia i valori delle…