SVOR logo  SATW logo

Concorso di Ottimizzazione 2010

Concorso riservato agli studenti del ginnasio della Svizzera

 

Descrizione del concorso

in italiano (pdf), in italiano (doc)

 

Locandina del concorso

in italiano (pdf), in italiano (ppt)

 

Download

  • Il problema
  • Modulo per sottoporre le soluzioni trovate

    •  

     

    Introduzione

     

    La ricerca di un piano di spedizioni ottimali su una rete è un problema complesso, che implica la scelta di una soluzione tra un numero molto elevato di possibili alternative. In effetti, mentre in certi casi è facile trovare una soluzione possibile, trovare quella ottima è un problema difficile.

    Il problema di organizzare delle spedizioni su una rete di persone ottenuta da Facebook è un problema affrontato dalla Ricerca Operativa. Per risolvere questi problemi, si potrebbe pensare ad enumerare tutte le soluzioni, ma questo funziona solo per problemi molto piccoli. La Ricerca Operativa vi permette di risolverli all’ottimo senza bisogno di provarle tutte.

    La Ricerca Operativa è una scienza che si situa tra l’Informatica e la Matematica e che raggruppa un insieme di metodi di supporto alle decisioni per risolvere problemi di ottimizzazione, come quello di trovare un piano di spedizioni a costo minimo.

    Con l’obiettivo di promuovere la Ricerca Operativa per i futuri studenti universitari Svizzeri, la Società Svizzera di Ricerca Operativa (ASRO) organizza quest’anno un concorso che si basa su una rete di relazioni ricavata da Facebook.

     

    Formulazione del concorso

     

    Michel e Emma sono amici su Facebook. Prossimamente ci sarà il compleanno di Emma e Michel desidera organizzare una festa. Michel utilizza Facebook per identificare i 16 amici che lui ed Emma hanno in comune. Utilizzando il visualizzatore di relazioni che si trova sul sito

    http://danielmclaren.net/node/77

    Michel ottiene il grafo in Figura 1.

    Lo scopo di Michel è di trovare un regalo interessante per Emma. Siccome Michel sta viaggiando in Africa trova sul mercato locale una collezione di maschere africane di cui Emma è una appassionata collezionista.

    Il regalo è trovato! Per ottenere un effetto spettacolare Michel vuole che ogni invitato si presenti alla festa indossando una delle maschere.

    Sfortunatamente Michel non riesce a portare tutte le maschere in Svizzera con l’aereo e quindi decide di spedirle per posta.

    Figure 1: Grafo delle relazioni tra gli amici comuni di Miche e Emma. Due persone sono in relazione tra di loro se c’è un arco diretto che le collega.

     

    Michel vuole anche risparmiare e ha paura che qualche maschera venga persa quindi non vuole fare 16 spedizioni dirette. Michel decide allora di inviare un unico pacchetto a uno degli amici comuni che avrà poi l’incarico di rispedire le maschere a ciascuno degli altri invitati.

    Come di vede dal grafo, comunque, non tutti gli invitati si conoscono tra di loro. Michel vuole organizzare la spedizione in modo tale che le persone che ridistribuiscono le maschere lo facciano solo tra gente che conoscono. (vedere l’esempio qui sotto).

    Evidentemente, se questa ripartizione non è ben organizzata andrà a costare anch’essa una fortuna!. Michel si trova a risolvere un problema di ottimizzazione. Dovrà decidere a chi inviare il pacchetto con le 16 maschere e spiegare a questa persona come organizzare la ri-distribuzione, in modo da spendere il meno possibile.

    Ciascun amico abita in una zona che ha una certa tariffa postale : zona grigia (G), zona gialla (J) e zona viola (M). I costi di spedizione sono illustrati qui sotto :

     

    Michel deve quindi decidere a chi spedire le 16 maschere e anche come questa persona deve rispedirle in modo tale che tutti arrivino alla festa con la propria maschera e che il costo delle spedizioni sia minima.

    Formalmente i punti che Michel deve prendere in considerazione per la sua decisione sono i seguenti :

    1.      il pacchetto che parte dall’Africa contiene tulle e 16 le maschere.

    2.      un invio tra due persone può essere fatto solo se queste si conoscono su Facebook, vale a dire se esiste un arco tra le persone nella Figura 1.

    3.      i regali non sono nominativi, quindi non importa chi riceve quale maschera.

    4.      più spedizioni della stessa maschera sono eventualmente possibili.

    5.      una persona può inviare un pacchetto ad un’altra persona contente anche più maschere.  

    6.      il costo di un pacchetto dipende dalla zona di partenza e dalla zona di arrivo e dal numero di maschere (ad esempio un pacchetto con tre maschere che parte dalla zona « J » alla zona « M » costa 6€) ;

    7.      il costo totale è la somma della spesa di tutte le persone..

     

    Domanda Principale :   A chi Michel deve inviare il pacchetto con le 16 maschere e quale è il piano di spedizione successivo con il costo minimo ?

    Domanda secondaria : Quante reti saranno segnate in totale durante la coppa del mondo di calcio in Sud Africa? Attenzione le reti segnate su calcio di rigore dopo i tempi supplementari non contano!

     

    Esempio

    Un possibile piano di spedizione epr le 16 maschere è il seguente e costa 145€. Esiste un piano che costa di meno? Sì … spetta a voi trovarlo !

     

    Spedisce

    Gruppo

    Riceve

    Gruppo

    Nr. Di maschere

    Costo

    Michel

     

    Moshe

    G

    16

    32 €

    Moshe

    G

    Eric

    M

    3

    9 €

    Moshe

    G

    Maya

    G

    12

    36 €

    Maya

    G

    Carolina

    J

    9

    27 €

    Maya

    G

    Charisma

    J

    1

    3 €

    Maya

    G

    Matteo

    M

    1

    3 €

    Carolina

    J

    Gautier

    G

    3

    9 €

    Carolina

    J

    Benjamin

    M

    3

    6 €

    Carolina

    J

    Javier

    M

    2

    4 €

    Eric

    M

    Mogens

    M

    2

    2 €

    Gautier

    G

    Antonio

    M

    1

    3 €

    Gautier

    G

    Jelena

    J

    1

    3 €

    Benjamin

    M

    Jacques

    G

    1

    3 €

    Benjamin

    M

    Fafa

    J

    1

    2 €

    Javier

    M

    Veronica

    J

    1

    2 €

    Mogens

    M

    Sebastian

    M

    1

    1 €

     

     

     

     

     

     

     

     

     

     

    Costo Totale

    145 €

     

     

    Organizzazione del concorso.

    Il documento completo con i dati del problema sono depositati sul www.asro.ch.

     

    La vostra soluzione (domanda principale) e la risposta alla domanda secondaria devono essere inviate all’indirizzo email info@asro.ch per mezzo del file Excel Solution_Concours_ASRO_2010.xls, disponibile sul sito. Vogliate indicare anche i vostri dati e le vostre coordiante oltre a descrivere il metodo di soluzione La scadenza per l’invio è domenica 6 giugno 2010.

     

    Regolamento

    Il concorso è riservato agli studenti(esse) dei ginnasi Svizzeri .

    L'ASRO incoraggia gli studenti(esse) ad implementare un modello matematico o un programma per computer per calcolare la soluzione. In ogni caso una soluzione « manuale » è anche possibile.

    Solo le risposte arrivate in tempo sono da considerarsi valide.

    L'ASRO premia le prime cinque soluzioni ammissibili con il costo più basso (domanda principale). In caso di soluzioni uguali si considera la risposta alla domanda secondaria. In caso di ulteriore parità si procede con un’estrazione a sorte.

     

    Premi

    Il concorso è dotato di cinque premi per un totale di 2'000 CHF.

    1mo premio:                    600 CHF

    2ndo premio:                   500 CHF

    3o    premio:                   400 CHF

    4o    premio:                   300 CHF

    5o    premio:                   200 CHF

    L’ASRO contatterà il vincitore durante il mese di luglio 2010.