01 10 14

Page 1

Fondamenti di Ricerca Operativa Esame 1/10/2014 Prima parte 1. Gi amministratori della citt` a pi` u bella del mondo vogliono installare un sistema di sensori sulle strade del centro per monitorare l’andamento del traffico in tempo reale. La rete stradale ` e rappresentata da un grafo orientato G = ( N, A), dove l’insieme dei nodi N rappresenta gli incroci e l’insieme degli archi le strade. I sensori possono venire installati sulle strade, quindi sugli archi del grafo. Gli amministratori conoscono anche l’insieme dei cammini utilizzati dai cittadini per muoversi per ogni possibile coppia origine-destinazione. sia D ={(sd, td) : d = 1, . . . r} l’insieme delle possibili coppie origine-destinazione e sia Pd l’insieme di tutti i possibili cammini da sd a td, d = 1, . . . , r, il problema consiste nel determinare l’insieme degli archi orientati dove piazzare un sensore in modo che il flusso su tutti i possibili cammini s p∈ Pd, d = 1, . . . , r si intercettato almeno una volta. L’obiettivo del problema ` e minimizzare il numero di sensori. Si fornisca una formulazione in termini di programmazione lineare intera. V arianteSi supponga che il budget disponibile consenta agli amministratori di piazzare al massimo k sensori. Conoscendo la stima del traffico fp p∈ Pd, d = 1 , . . . , r, il problema dienta la determinazione degli archi su cui posizionare un sensore in modo che venga massimizzata la quantit complessiva di traffico intercettato. Come si modifica la formulazione? 2. Uno zuccherificio ha una produzione ordinaria massima di Pt tonnellate e una produzione straordinaria di P ′ t tonnellate per il giorno t = 1, . . . T. La domanda di zucchero del mercato ` e didt tonnellate nel gionro t e deve essere soddisfatta esattamente entro la fine di ogni giorno t. Lo zuccherificio pu` o…