Gara AIRO di Ricerca Operativa

Fase locale - esercizi

Tra parentesi quadre sono indicati i punti ottenibili per ogni domanda,

Esercizio 1: Il pronto soccorso

Nel pronto soccorso di un piccolo ospedale sono di turno due medici per volta. Le richieste dei pazienti vengono classificate in "urgenti" e "non urgenti". Si vuole che non capiti mai che entrambi i medici siano impegnati simultaneamente con due pazienti "non urgenti" e che quindi non ci sia nessuno disponibile per trattare un eventuale paziente "urgente". Infatti, una volta che il trattamento di un paziente ha avuto inizio, non può essere interrotto. Quindi il pronto soccorso funziona così: quando entrambi i medici sono liberi, qualunque tipo di paziente viene subito preso in carico; quando uno dei due medici è già impegnato, il successivo paziente in arrivo viene preso in carico immediatamente solo se è urgente, altrimenti viene fatto aspettare in sala d'attesa. Per evitare che la coda di pazienti si allunghi, il pronto soccorso avverte in tempo reale il sistema 118 in modo da dirottare altrove i nuovi pazienti in arrivo. In particolare non vengono più accettati altri pazienti urgenti se i due medici sono entrambi occupati e nemmeno altri pazienti non urgenti se ce n'è già uno in attesa. Quando gli arrivi non sono dirottati altrove, i pazienti non-urgenti arrivano con una frequenza media pari ad un paziente ogni quarto d'ora; i pazienti urgenti invece arrivano mediamente con una frequenza pari a uno ogni tre quarti d'ora. Tutti i trattamenti durano mediamente venti minuti, sia per i pazienti urgenti che non.

Il direttore sanitario vuole sapere:

Domanda 1 [10]: Per quale frazione di tempo il pronto soccorso risulta saturo per i pazienti urgenti?

Domanda 2 [1]: Per quale frazione di tempo il pronto soccorso risulta saturo per i pazienti non urgenti?

Domanda 3 [2]: Qual è la percentuale di utilizzo della forza-lavoro dei medici di turno?

Domanda 4 [2]: Qual è la probabilità che un paziente non urgente venga messo in coda?

Domanda 5 [5]: Come cambierebbero gli indicatori suddetti se i medici servissero sempre subito tutti i pazienti in arrivo?

Domanda 6 [5]: Come cambierebbero gli indicatori suddetti se i medici fossero tre, mantenendo la politica attuale di non occupare l'ultimo medico disponibile se l'ultimo paziente arrivato non è urgente?

Esercizio 2: La legge di Ohm

Nel laboratorio di Fisica un gruppo di studenti ha fatto esperimenti sulla prima legge di Ohm: V = R I, dove V è la tensione applicata ai capi di un resistore, R è la sua resistenza e I è l'intensità di corrente che attraversa il resistore.

Gli studenti lavorano su un resistore di cui vogliono determinare la resistenza. A questo scopo ogni studente del gruppo applica una tensione ai morsetti del resistore, la misura con un voltmetro e poi misura con un amperometro anche l’intensità di corrente che attraversa il resistore. L'amperometro è preciso, ma il voltmetro è affetto da errori di misura. Perciò gli studenti ottengono valori di tensione e intensità di corrente che non hanno tutti esattamente lo stesso rapporto, come riportato nella Tabella 2.1.

Tabella 2.1: Misurazioni compiute dagli studenti.

Si tratta quindi di stabilire il valore della resistenza che rende minima una funzione dell’errore di misura causato dal voltmetro.

L’insegnante propone tre criteri:
a) minimizzare il massimo errore (considerando gli errori in valore assoluto)
b) minimizzare il valor medio degli errori (sempre considerando gli errori in valore assoluto)
c) minimizzare l’errore quadratico medio,

Domanda 1 [5+5+5]: Qual è il valore stimato della resistenza in ciascuno dei tre casi?

Esercizio 3: Il tracciato dell'elettrodotto

Per portare la corrente elettrica in una valle sperduta, l'azienda elettrica deve decidere il tracciato di un elettrodotto. Lungo la valle, che si biforca anche in due valli laterali minori, ci sono vari paesini che devono essere elettrificati e l'elettrodotto deve raggiungerli in sequenza, per altitudine crescente, come mostrato in Figura 3.1.

Figura 3.1: Schema dell'elettrodotto. Il sito A indica l'impianto produttivo.

Nei pressi di ogni paesino verrà installata una cabina di trasformazione da alta tensione alla normale tensione di 220 Volt. Ogni cabina di trasformazione verrà poi collegata ad una centralina nel corrispondente paese tramite cavi elettrici interrati. L'azienda elettrica deve sostenere i costi per l'installazione dell'elettrodotto ad alta tensione, che deve collegare con dei segmenti rettilinei ogni cabina di trasformazione alla successiva, e per gli scavi, anch'essi rettilinei, per collegare ogni cabina di trasformazione alla centralina del suo paese. Le posizioni delle centraline nei vari paesi sono date (v. Tabella 3.1, dove sono espresse in chilometri in un dato sistema di riferimento cartesiano) ed è data anche la posizione dell'impianto a fondo-valle (località indicata con "A") da cui l'elettodotto deve partire. La posizione delle cabine di trasformazione invece può essere scelta liberamente, purché ogni cabina di trasformazione non disti dalla centralina del suo paese più di due chilometri.

Tabella 3.1: Posizioni delle cabine di trasformazione.

Due managers, Tizio e Caio, nell'azienda elettrica hanno opinioni diverse sul tracciato dell'elettrodotto: Tizio sostiene che sia necessario minimizzare la lunghezza complessiva delle linee interrate, mentre Caio sostiene che sia necessario minimizzare la lunghezza complessiva dei cavi ad alta tensione.

Domanda 1 [15]: Sapreste dire quale sarebbe la lunghezza complessiva degli scavi e quale la lunghezza complessiva dell'elettrodotto nei due casi e dove andrebbero costruite nei due casi le cabine di trasformazione?

Domanda 2 [5]: Il super-manager Sempronio decide che l'elettrodotto debba essere costruito in modo da minimizzare i costi complessivi, Sapendo che ogni km di scavo costa una volta e mezzo un km di elettrodotto, sapreste dire dove devono essere realizzate le cabine di trasformazione?

[E' consentito trascurare il dislivello dovuto alla diversa altitudine dei paesi e risolvere il problema in sole due dimensioni.]

Esercizio 4: Il cassiere

Un cassiere ha a disposizione 10 banconote da 100 €, 100 banconote da 50 €, 200 banconote da 20 €, 1,000 banconote da 10 € e 10,000 banconote da 5 €.

Domanda 1 [5]: Per ottenere l’importo di 1545 € utilizzando il numero minimo di banconote, quante e quali banconote deve usare?

Domanda 2 [2]: Risolvere con il seguente vincolo aggiuntivo: se si utilizza almeno una banconota da 20 €, allora si deve utilizzare almeno una banconota da 10 €. Determinare la soluzione ottima corrispondente.

Domanda 3 [2]: Risolvere con un secondo vincolo aggiuntivo: se si utilizzano banconote da 50 €, allora non si possono utilizzare banconote da 20 €. Determinare la soluzione ottima corrispondente.

Esercizio 5: I libri scolastici

Una casa editrice ha stampato alcune copie del libro “Manuale di Ricerca Operativa” utilizzato in alcune scuole italiane e le ha lasciate nel magazzino dei suoi tre stabilimenti ubicati a Torino, Napoli e Palermo, rispettivamente nelle seguenti quantità: 1200, 1400 e 800. I distributori che hanno richiesto questo libro si trovano nelle città di Milano, Bologna, Roma e Bari. Ciascuno ha richiesto rispettivamente le seguenti quantità: 1000, 1200, 700 e 500.

Per avvalersi della consegna la casa editrice utilizza un corriere chiamato “Tutto Trasporti A” che rende disponibile sui propri furgoncini uno spazio diverso per ciascuna coppia di città poiché la parte rimanente del furgoncino è già stata assegnata ad altri servizi. Le quantità di libri che è possibile spedire tra ciascuna coppia di città sono indicate nella Tabella 5.1 (riga = origine; colonna = destinazione).

Tabella 5.1: Capacità disponibili per il trasporto.

Il costo di spedizione per ciascun libro è indicato nella Tabella 5.2 (costi in Euro per ogni libro).

Tabella 5.2: Costi unitari di spedizione.

Domanda 1 [10]: Quanti libri bisogna spedire da ciascun deposito in modo tale da soddisfare il maggior numero possibile di richieste dei distributori?

Domanda 2 [1]: Nel caso non sia possibile soddisfare tutte le richieste, quanti sono i libri che possono essere consegnati?

Domanda 3 [5]: Come è possibile soddisfare il massimo numero di ordini minimizzando i costi di spedizione?

Considerare una seconda società di trasporti “Tutto Trasporti B” che lavora con le stesse capacità precedenti ma attua una politica di prezzo che tende a scoraggiare il massimo utilizzo della capacità secondo la funzione di costo seguente:

C = P / (1 – q/Q)

dove per ogni coppia origine-destinazione C è il costo unitario di spedizione di un libro, P è il prezzo base indicato nella Tabella 5.3, q è la quantità spedita e Q è la capacità riportata nella Tabella 5.1.

Tabella 5.3: Prezzi-base del trasportatore "Tutto Trasporti B".

Domanda 4 [5]: In questo caso è possibile soddisfare tutte le richieste e a quali costi?

Domanda 5 [1]: Di quanto è migliore la scelta di una società rispetto all’altra?

Esercizio 6: Noleggio auto

Il gestore di un piccolo autonoleggio in un'isola del Mediterraneo riceve via Internet un insieme di richieste dalle agenzie-viaggi con cui è convenzionato e periodicamente deve comunicare all'agenzia quali intende soddisfare e quali no. Infatti, poiché ha soltanto quattro automobili, non è sempre in grado di soddisfare tutte le richieste dei turisti e quindi ne scarta alcune, che l'agenzia provvede ad assegnare ad altri noleggiatori. Il profitto che l'autonoleggio ricava da ogni servizio effettuato è dato da una quota fissa di 20 Euro più una quota proporzionale alla durata del noleggio (espressa sempre in giorni interi) pari a 40 Euro al giorno. La Tabella 6.1 riporta un insieme di richieste che il noleggiatore ha ricevuto dall'agenzia-viaggi, relative al prossimo mese (che ha 30 giorni),

Tabella 6.1: Richieste di noleggio (giorno iniziale e finale sono inclusi). Quelle indicate con l'asterisco terminano nei primi giorni del mese successivo.

Domanda 1 [15]: Sapreste aiutarlo a scegliere quali richieste accettare e quali no?

Domanda 2 [1]: Qual è il massimo ricavo ottenibile da queste richieste?

Domanda 3 [5]: Noleggiare temporaneamente da un collega una quinta automobile per il periodo considerato costerebbe al noleggiatore 1000 Euro. Gli conviene farlo o no e perché?

Esercizio 7: Energia eolica

Si vuole progettare un impianto di generazione di energia eolica per alimentare una piccola azienda agricola. Il generatore di energia eolica produce energia in quantità variabile nel tempo a seconda delle condizioni mereologiche. Anche il fabbisogno di energia dell'azienda agricola è variabile nel tempo. Quando la produzione di energia elettrica eccede la quantità consumata, l'energia residua viene conservata in un accumulatore. Viceversa, quando la produzione di energia non è sufficiente al fabbisogno, l'energia mancante viene prelevata dall'accumulatore. L'accumulatore ha una capacità limitata: quando è completamente carico, l'eventuale energia residua non più accumulabile viene persa.

Da studi meteorologici si hanno a disposizione le previsioni sulla produzione attesa di energia elettrica per le 52 settimane dell'anno; anche il fabbisogno medio dell'azienda agricola è stato stimato per ciascuna delle 52 settimane (Tabella 7.1). Si supponga di poter trascurare le oscillazioni (sia nella produzione che nel fabbisogno) che avvengono nel corso di ogni singola settimana.

Tabella 7.1: Produzione e fabbisogno di energia elettrica settimanale nell'arco di un anno (KWh).

L'eventuale produzione in eccesso può essere smaltita, disperdendo l'energia prodotta (o fermando l'impianto) in qualunque periodo.

Per realizzare l'accumulatore sono disponibili diversi tipi di batterie a diversi prezzi, come indicato nella Tabella 7.2.

Tabella 7.2: Batterie.

Domanda 1 [10]: Che capacità deve avere l'accumulatore, come minimo, affinché l'impianto sia in grado di alimentare l'azienda lungo tutto l'anno?

Domanda 2 [5]: Come è possibile ottenere un valore sufficiente di capacità dell'accumulatore spendendo il meno possibile per l'acquisto delle batterie che lo compongono?

Domanda 3 [5]: In quale periodo dell'anno deve essere effettuata la dispersione di energia elettrica in eccesso?

Con l'uso e col passare del tempo le batterie si deteriorano. A causa del deterioramento l'energia nell'accumulatore si disperde al passare del tempo (fenomeno detto "autoscarica"): quindi dell'energia accumulata in una settimana solo una certa frazione risulta disponibile nella settimana successiva.

Domanda 4 [5]: Volendo che l'impianto continui ad essere in grado di alimentare l'azienda agricola per tutto l'anno, qual è il valore minimo a cui tale frazione può scendere?

Domanda 5 [5]: In corrispondenza di tale valore di autoscarica delle batterie, quanta capacità bisogna aggiungere agli accumulatori rispetto al dimensionamento ipotizzato inizialmente? Con quali costi?

Esercizio 8: Rete sociale

I membri di una rete sociale (social network, come ad esempio Facebook) stabiliscono tra loro relazioni "uno a uno", rappresentabili come in Figura 8.1. Queste relazioni indicano conoscenza, amicizia, interazione tra coppie di persone.

Figura 8.1: Un esempio di rete sociale con 34 individui legati da relazioni di amicizia.

Spesso all'interno di una rete sociale si individuano delle "comunità"', cioè dei gruppi di persone caratterizzati da un elevato livello di interazione tra i membri del gruppo e da un basso livello di interazione tra i membri del gruppo e le persone esterne al gruppo.

Si vuole quindi trovare il modo migliore di partizionare un dato insieme di persone, caratterizzate da relazioni di amicizia, in sottinsiemi corrispondenti a comunità. La partizione deve essere tale che ogni persona appartenga ad una e una sola comunità. Ogni possibile partizione dell'insieme in comunità ha un valore e si vuole trovare la partizione di valore massimo, cioè quella che rappresenta meglio le comunità.

Il valore di una partizione è dato da contributi positivi e negativi, sommati tra loro: danno un contributo pari a +k tutte le coppie di persone che interagiscono (cioè sono in relazione di amicizia) e sono incluse nella stessa comunità, mentre danno un contributo pari a -1 tutte le coppie di persone che non interagiscono e sono incluse nella stessa comunità e tutte le coppie di persone che interagiscono e non sono incluse nella stessa comunità.

Domanda 1 [12]: Data la rete sociale rappresentata in figura, trovare quante e quali sono le comunità che definiscono la partizione di valore massimo per diversi valori interi di k=1,...,5.

Domanda 2 [3]: Qual è il valore delle partizioni trovate?

Domanda 3 [5]: Esiste un valore di k per cui la partizione ottima del caso in esame degenera in un'unica comunità?

[L'elenco delle relazioni di amicizia è contenuto in questo file di testo.]

Esercizio 9: Piano di emergenza

Una valle ai piedi di un vulcano ancora in attività è scossa frequentemente da terremoti, è attraversata da un fiume che durante i periodi delle piogge causa allagamenti; inoltre frequenti abusi edilizi hanno reso fragili diverse pareti montuose causando rischi di frane e smottamenti. Gli enti territoriali devono quindi stabilire un piano di emergenza, da mettere in atto in caso di calamità. A questo scopo il territorio è stato suddiviso in venti zone, in modo che in ciascuna di esse sia possibile installare all'occorrenza un sito di emergenza, che comprende una tendopoli con un ospedale da campo. Il numero di abitanti di ogni zona è riportato nella Tabella 9.1, mentre la distanza in chilometri da percorrere per spostarsi da una zona all'altra è riportata nella Tabella 9.2.

Tabella 9.1: Caratteristiche delle zone: abitanti, costi di installazione (espressi in Euro), coefficiente di rischio.

Ogni sito di emergenza può ospitare fino a 500 persone, dovunque sia ubicato, e si ipotizza che la frazione di popolazione che sarebbe necessario alloggiare in caso di calamità sarebbe pari al 25% degli abitanti di ogni zona. Il costo di installazione dei siti di emergenza dipende dalle zone in cui vengono posizionati, come descritto nella Tabella 9.1. Il costo del trasporto di ogni persona (e dei suoi effetti personali) da una zona al sito di emergenza di un'altra zona è proporzionale alla distanza tra le due zone attraverso un coefficiente di costo, che tiene conto del consumo di carburante e del costo per l'uso dei veicoli: tale coefficiente è stato stimato in 3 euro al chilometro per ogni persona da trasportare.

Tabella 9.2: Distanza tra le zone (Km).

Domanda 1 [15]: Decidere dove installare i siti di emergenza e quali zone assegnare a ciascun sito, in modo da minimizzare la somma tra i costi di installazione e i costi di trasporto, assicurandosi che il 25% della popolazione di ogni zona sia assegnata ad un sito, senza eccedere la capacità  ricettiva di nessun sito. E' possibile assegnare gli abitanti di una stessa zona a siti diversi.

Le autorità competenti hanno fatto una valutazione del rischio in ognuna delle venti zone della valle. Nella Tabella 9.1 è riportato per ogni zona un coefficiente di rischio che rappresenta la probabilità  che un evento naturale renda inutilizzabile il sito di emergenza eventualmente installato in quella zona. Se un sito diventa inservibile, tutta la popolazione assegnata a quel sito non può più essere soccorsa. Il rischio associato al piano di emergenza è quindi valutato come il valor medio (da calcolare su tutta la popolazione alloggiata nei siti di emergenza) dell'indice di rischio per ogni abitante e questo a sua volta è pari al coefficiente di rischio del sito di emergenza a cui l'abitante è allocato.

Domanda 2 [5]: Rivedere le decisioni prese al passo precedente in modo da assicurare che l'indice di rischio del piano di emergenza non superi il valore limite 0,05.

Degli esperti in gestione del rischio affermano che sarebbe possibile mettere in sicurezza le zone della valle al costo di 1000000 Euro per ogni zona.

Domanda 3 [15]: Sapendo che gli enti locali hanno un budget disponibile di 3000000 Euro, decidere dove installare i siti di emergenza, quali zone assegnare a ciascuno ed eventualmente quali zone mettere in sicurezza, senza eccedere il budget disponibile e minimizzando l'indice di rischio complessivo del piano di emergenza.

Esercizio 10: Test diagnostico

In un laboratorio di biomedicina si stanno facendo esperimenti su tessuti sani e malati a scopo diagnostico. I tessuti in esame sono caratterizzati dalla presenza di due sostanze, indicate da X e Y, in concentrazioni diverse da individuo a individuo. I campioni disponibili per l'esame sono stati prelevati sia da tessuti sani che da tessuti malati e in ciascuno di essi sono state misurate le concentrazioni delle due sostanze, come riportato nella Tabella 10.1.

Tabella 10.1: Valori di concentrazione (microgrammi/cc) di sostanze X e Y nei campioni di tessuti sani e malati.

Da questi dati si vuole ora estrapolare un modello che serva da aiuto per la diagnosi: si vorrebbe cioè trovare un metodo per classificare automaticamente un dato tessuto come "sano" o "malato" a seconda della concentrazione di X e di Y in esso. A questo scopo i campioni esaminati sono stati riportati come punti in un piano cartesiano e si vuole trovare una retta che separi i punti corrispondenti ai campioni sani da quelli corrispondenti ai campioni malati.

Domanda 1 [10]: E' possibile? Se sì, qual è la retta? Nel caso non sia possibile, è lecito trascurare un limitato numero di campioni, considerandoli affetti da errore di misura. Qual è il minimo numero di campioni da trascurare per poter trovare la retta cercata?

Domanda 2 [10]: Tra tutte le rette possibili che separano i campioni "sani" da quelli "malati", trascurando il minimo numero possibile di campioni dati, si vuole trovare la retta che rende massima la minima distanza tra sè e i campioni considerati.

20 Ottobre 2009