Ricerca Operativa: un problema di tutti i giorni

n. 6
Quaderni del Liceo Ferraris
giugno
2011
Ricerca Operativa,
un problema di
tutti i giorni…
Ivano Capozza
Marianna Miola
Quaderni del Liceo Ferraris
numero 6 - giugno 2011
Capozza Ivano
Miola Marianna
La Ricerca Operativa,
un problema di tutti i giorni…
Il lavoro di due studenti di Quinta Liceo Scientifico presentato
in questo quaderno sintetizza un interessante percorso di studio
compiuto entro la cornice del “Piano Lauree Scientifiche (PLS)”,
svolto in parte a Taranto in parte presso l’Università del Salento..
In esso sono illustrati con chiarezza gli aspetti elementari
della Ricerca Operativa - strumento matematico-informatico per
la risoluzione di problemi decisionali.
Un “problema decisionale” è un problema in cui uno o più
decisori si trovano a dover effettuare delle scelte fra diverse
alternative, rispetto a determinati obiettivi.
La prima fase della Ricerca Operativa consiste nell’esame
della situazione reale e nella raccolta delle informazioni nel modo
più ampio e approfondito possibile. Segue poi la formulazione del
problema, che comporta l’individuazione delle variabili e la scelta
della funzione da massimizzare o da minimizzare.
La Ricerca Operativa trova numerose applicazioni in differenti
ambiti: industriale, economico, di trasporto, ecc..
Gli estensori del quaderno si sono rivolti alla scoperta di una
nuova disciplina con l’entusiasmo di chi scopre “come tutto, o
quasi, intorno a noi è MATEMATICA!”
Ivano Capozza e Marianna Miola si sono diplomati brillantemente
nel luglio 2011, al termine del corso di liceo scientifico P.N.I.
(Piano Nazionale dell’Informatica)
RICERCA OPERATIVA:
UN PROBLEMA DI TUTTI I GIORNI…
Autori:
Ivano Capozza, Marianna Miola
Introduzione:
Salvatore Spinelli
Introduzione
Il presente “Quaderno del Liceo Ferraris” nasce dall’adesione
del nostro Liceo al Piano Lauree Scientifiche (PLS) 2010/2011 ed è
frutto del lavoro svolto da alcuni ragazzi che hanno attivamente
partecipato ai laboratori di Matematica.
Il PLS è un piano nazionale nato nel 2004 grazie alla collaborazione del Ministero dell’Università e dell’Istruzione, della Conferenza Nazionale dei Presidi di Scienze e Tecnologie e di Confindustria,
ispirato dalla motivazione iniziale di incrementare il numero di iscritti
ai corsi di laurea in Chimica, Fisica, Matematica e Scienza dei
materiali. A tal fine il PLS si è concentrato su tre obiettivi principali:
•
migliorare la conoscenza e la percezione delle discipline scientifiche nella Scuola secondaria di secondo grado, offrendo agli
studenti degli ultimi tre anni di partecipare ad attività di laboratorio curriculari ed extracurriculari stimolanti e coinvolgenti;
•
avviare un processo di crescita professionale dei docenti di
materie scientifiche in servizio nella Scuola secondaria a
partire dal lavoro congiunto tra Scuola e Università per la
progettazione, realizzazione, documentazione e valutazione
dei laboratori sopra indicati;
•
favorire l'allineamento e l'ottimizzazione dei percorsi formativi
dalla Scuola all'Università e nell'Università per il mondo del
lavoro, potenziando ed incentivando attività di stages e
tirocinio presso Università, Enti di ricerca pubblici e privati,
Imprese impegnate in ricerca e Sviluppo.
Nell’ambito del PLS il Liceo Scientifico “Galileo Ferraris” ha
partecipato con ventuno alunni (quattro di 5aA, uno di 4aC, quattro di
5aC, due di 5aD, otto di 5aE e due di 5aH) e 3 docenti di matematica e
fisica (Donatella Aquaro, Concetta Basanisi e Salvatore Spinelli) ai
laboratori di Matematica organizzati dal Dipartimento di Matematica
dell’Università del Salento, al termine dei quali gli alunni hanno tutti
superato con profitto la prova di verifica finale.
Le attività di tali laboratori, frutto di un’attenta e proficua
pianificazione congiunta Scuola-Università, si sono tenute sia presso
il nostro Istituto sia, nell’arco d’una giornata intera, a Lecce presso il
Dipartimento di Matematica della stessa Università ed hanno
riguardato le seguenti attività:
•
Crittografia e teoria dei codici (tenuto dal prof. Montinaro), che
ha trattato i messaggi criptati partendo dal codice di Cesare
fino ad arrivare al cifrario RSA e i codici di controllo, con
l'obiettivo di far apprendere e utilizzare l'aritmetica modulare, i
relativi teoremi di Eulero, alcuni test di primalità e le tecniche di
correzione di errori in un messaggio trasmesso;
Ricerca Operativa: un problema di tutti i giorni… – pag.
2
•
Cartografia matematica (tenuto dalla prof.ssa Mangino), che
ha trattato il problema delle cartine geografiche, con l'obiettivo
di far apprendere le proprietà delle figure appartenenti ad una
superficie sferica e a riconoscere nella sfera un modello di
geometria non euclidea;
•
Ricerca operativa (tenuto dal prof. Triki), che ha trattato il
“problema del commesso viaggiatore” e l’ottimizzazione delle
soluzioni nelle applicazioni della ricerca operativa in finanza.
Ed è a quest’ultimo tema che si è rivolta l’attenzione di due
studenti coinvolti, da annoverare tra i partecipanti più curiosi e
produttivi. Invero, la partecipazione di tutti gli studenti è stata sempre
attiva anche perché i temi trattati sono risultati stimolanti ed
inconsueti ed hanno permesso di avvicinare gli studenti ad alcuni
concetti matematici utilizzando una didattica innovativa e coinvolgente, impegnandoli in attività diverse rispetto a quelle tradizionali, in
modo da suscitare interesse, curiosità e motivazioni nello studio.
Trattasi di caratteristiche metodologiche di cui la Scuola deve
fare tesoro, puntando a ravvivare l’insegnamento curricolare per
renderlo sempre più efficace anche e soprattutto in matematica: la
quale può essere tutt’altro che una disciplina arida ed ostica!
Inoltre, i laboratori hanno riguardato problemi ed argomenti interdisciplinari, sì da scoprire i legami della matematica con altre discipline, scientifiche e non, nonché le sue svariate applicazioni tecnologiche. Insomma, se vista con occhi diversi, anche la matematica
può risultare più facile, accattivante e coinvolgente di quanto si pensi.
Ricerca Operativa: un problema di tutti i giorni… – pag.
3
LA RICERCA OPERATIVA
1. Che cosa è?
La Ricerca Operativa, nota anche come teoria delle decisioni,
scienza della gestione o, in inglese “Operations Research”, fornisce
strumenti matematici di supporto alle attività decisionali, in cui occorre
gestire e coordinare attività con risorse limitate, al fine di massimizzare o minimizzare una funzione obiettivo. Si occupa di formalizzare un problema in un modello matematico e calcolare una soluzione ottima, quando possibile, o approssimata. Essa costituisce un
approccio scientifico alla risoluzione di problemi complessi e si può
ricondurre all'ambito della matematica applicata, all'informatica,
all'economia e alla finanza, all'ingegneria ed altro. Inoltre la ricerca
operativa ha molte applicazioni commerciali soprattutto negli ambiti
economico, infrastrutturale, logistico, militare, della progettazione di
servizi e di sistemi di trasporto e nelle tecnologie.
Nel caso particolare di problemi di carattere economico, la funzione da massimizzare può coincidere con il massimo profitto ottenibile o con il minor costo da sostenere.
La ricerca operativa riveste un ruolo importante nelle attività
decisionali perché permette di operare le scelte migliori per
raggiungere un determinato obiettivo, rispettando vincoli che sono
imposti dall'esterno e non sono sotto il controllo di chi deve compiere
le decisioni.
Ricerca Operativa: un problema di tutti i giorni… – pag.
4
2. Quando è nata?
La nascita della ricerca operativa è dovuta ad esigenze di tipo
militare insorte durante la seconda guerra mondiale. Prima e durante
il conflitto, infatti, si erano costituiti in alcuni Paesi alleati gruppi di
ricerca orientati alla soluzione di importanti problemi di ordine
strategico e tattico, collegati alla difesa nazionale.
Nel 1935 il Regno Unito lavorò sul progetto “Bawdsey
Research Station radar” sulla difesa antiaerea, era tuttavia importante
che fosse efficiente la localizzazione e la successiva intercettazione e
rientro a terra dei velivoli inglesi. Apparve quindi indispensabile
l'ottimizzazione della distribuzione delle apparecchiature radar sul
territorio ed, inoltre, che fosse mandata via radio la segnalazione ad
opportune località. Nacque così il "Biggin Hill Experiment".
Fu in una relazione tecnica conclusiva del progetto del 1938
del sopraintendente Rowe che comparve per la prima volta
l'espressione "Operational Research".
Nel 1939, Patrick Maynard Stuart Blackett, fisico e professore
presso l’Università di Manchester, fu chiamato a costituire un gruppo
di ricerca composto da scienziati e militari, impegnato nella lotta
contro i sommergibili tedeschi.
Nel corso della seconda guerra mondiale furono complessivamente impegnati nel Regno Unito, in Canada e negli USA, oltre 700
scienziati in tale settore; il termine del conflitto dunque determinò una
"riconversione" dell'approccio, fino ad allora usato per soli fini bellici,
orientandolo verso problematiche di tipo civile (come la localizzazione
Ricerca Operativa: un problema di tutti i giorni… – pag.
5
dei depositi industriali, il mixing di carico di un servizio di
autotrasporto).
Nei settori più propriamente civili, la ricerca operativa riprese
tecniche note nel settore industriale, migliorandole ed arricchendole
con l'uso di strumenti matematici e di conoscenze organizzative: si
occupò della standardizzazione della produzione, di problemi connessi alla pianificazione e programmazione industriale. Nel Regno Unito
la riconversione avvenne prevalentemente nel settore pubblico, con
studi relativi ai trasporti ferroviari, stradali ed urbani.
In Italia, tali tecniche giunsero con una decina di anni di ritardo.
Nel 1961, un gruppo di ricercatori, tecnici e dirigenti d'azienda fondò
l'AIRO, l'Associazione Italiana della Ricerca Operativa, avente lo
scopo di promuovere studi teorici ed applicazioni pratiche della
disciplina.
3. Una classificazione della Ricerca Operativa
La ricerca operativa si divide in numerose sotto-branche. La
prima, e più importante, classificazione distingue tra:
•
Ottimizzazione, detta anche approccio “what-is-best”: si
occupa di formalizzare il problema in un modello matematico
(tipicamente un modello di programmazione matematica o un
grafo di flusso) ed individuare per esso una soluzione ottima o
subottima
•
Simulazione, detta anche approccio “what-if”: che si occupa di
problemi "difficili" da risolvere per ottimalità, spesso i cosiddetti
problemi “NP Ardui” (“termine impiegato nella teoria della
complessità”). Queste tecniche prevedono la formalizzazione
Ricerca Operativa: un problema di tutti i giorni… – pag.
6
del problema in un modello matematico e la determinazione di
"buoni" parametri mediante metodi statistici o di teoria dei
giochi
•
Processi Stocastici: si occupano di realizzare modelli
probabilistici al fine di determinare i comportamenti dei sistemi.
Questa branca, non ancora sufficientemente sviluppata in
Italia, risulta essere alla base dell'Ingegneria Finanziaria e
della Ottimizzazione Stocastica.
4. Le fasi di uno studio di Ricerca Operativa
L'elaborazione del problema è suddivisa in passaggi obbligatori:
•
Esame della situazione reale e raccolta delle informazioni
•
Formulazione del problema: individuazione delle variabili
controllabili
•
Costruzione del modello matematico, che ha lo scopo di dare
una buona rappresentazione del problema, fornendo tutte le
informazioni per poter assumere una decisione il più idonea
possibile.
•
Ricerca della soluzione
•
Analisi e verifica delle soluzioni ottenute: si controlla se la
funzione teorica offre vantaggi attesi e si verifichi la
rappresentatività del modello;
•
Interpretazione dei risultati
Ricerca Operativa: un problema di tutti i giorni… – pag.
7
5. Formulazioni del modello matematico: un esempio
Formulazione matematica :
•
Definizioni delle variabili
•
Definizioni della Funzione obiettivo
•
Definizione dei vincoli
ESEMPIO : Problema di decisione
Un’azienda automobilistica produce due modelli di auto, uno a benzina B che
vende al prezzo di 10 mila euro e uno diesel D che vende a 12 mila euro.
Ogni autovettura è realizzata da due robot R1 e R2.
I tempi di lavorazione dei robot in ore per realizzare le auto sono:
La disponibilità al giorno di R1 è di 24 ore, mentre quella di R2 è di 10 ore.
1. Definizione delle variabili: Si introducono due variabili che rappresentano
le quantità prodotte (e vendute) ogni giorno per i due modelli di auto.
Variabili: x : Numero di auto a benzina
y : Numero di auto diesel
L’azienda ha effettuato un’indagine di mercato con i seguenti esiti:
• la domanda giornaliera di B è al più il doppio di quella della macchina D
• la domanda minima giornaliera di auto è di 4.
Determinare le quantità dei due modelli di auto che devono essere prodotte
giornalmente in modo da rendere massimo il guadagno.
(Supponiamo che tutte le auto prodotte siano vendute).
2. Definizione della funzione obiettivo: Cosa voglio massimizzare?
Ricerca Operativa: un problema di tutti i giorni… – pag.
8
Il guadagno giornaliero dipende (è funzione) dalla decisione di quante auto D
e B voglio produrre. La funzione obiettivo :
F(x,y)=10x+12y
è una funzione lineare!
Evidenziamo le restrizioni sulle variabili:
Vincoli sul tempo di utilizzo dei robot:
2 x +3 y ≤ 24
2 x + y ≤ 10
Vincoli conseguenti l’indagine di mercato:
2y≥x
x+y≥4
Non si può produrre un numero negativo di auto:
x≥0
y≥0
Formulazione del problema : ricercare Max F(x,y)=10x+12y soggetto a:
2 x +3 y ≤ 24
2 x + y ≤ 10
2y≥x
x+y≥4
x≥0
y≥0
NOTA: I problemi che hanno per modello matematico sistemi di disequazioni (o
equazioni) lineari, vincoli abbinati ad una funzione lineare da massimizzare o
minimizzare funzione obiettivo, prendono il nome di problemi di Programmazione
Lineare (PL).
Qual è la soluzione del problema?
Quante auto a benzina e diesel si devono produrre?
Qual è il guadagno massimo?
Come si lavora con questi sistemi di disequazioni?
3. Definizione dei vincoli: metodo grafico: lo trattiamo per esteso, in
relazione all’esempio posto, nel paragrafo successivo
Ricerca Operativa: un problema di tutti i giorni… – pag.
9
6. Definizione dei vincoli: metodo grafico
Un problema di PL in due variabili può essere risolto attraverso semplici considerazioni di tipo geometrico, a partire dall’individuazione su
di un piano cartesiano del poligono ammissibile (Regione Ammissibile) determinata dai vincoli.
Ricordiamo che:
Ogni retta f(x,y)= ax + by + c = 0 divide il piano cartesiano in due semipiani
rappresentati dalle disequazioni:
ax + by + c < 0
ax + by + c > 0
Per individuare il semipiano: f(x, y) = ax + by + c > 0 si sceglie P(x’, y’) non
appartenente alla retta;
• Se f(x’, y’) > 0 → il semipiano che contiene il punto P è quello cercato;
• Se f(x’, y’) < 0 → il semipiano che non contiene il punto P è quello cercato.
Ogni vincolo del problema rappresenta un semipiano o una retta e, siccome tutti i
vincoli devono essere rispettati, la soluzione apparterrà alla parte di piano che è
intersezione di tutti i semipiani.
Per trovare la Regione Ammissibile del nostro problema, cerchiamo dove si
intersecano i semipiani. Ma questo vuol dire risolvere un sistema di disequazioni!
Iniziamo quindi ad esaminare le varie disequazioni nell’esempio scelto.
Ricerca Operativa: un problema di tutti i giorni… – pag. 10
Max F(x,y)=10 x+12 y soggetto a :
•
vincoli : x ≥ 0, y ≥ 0 ;
•
aggiunta del vincolo: 2 x +3 y ≤ 24
•
aggiunta del vincolo: 2x + y ≤ 10
Ricerca Operativa: un problema di tutti i giorni… – pag. 11
•
aggiunta del vincolo: 2y ≥ x
•
aggiunta del vincolo conclusivo: x + y ≥ 4
7. Natura della Regione Ammissibile
La regione ammissibile è una figura convessa
(infatti è intersezione di semipiani, che sono figure convesse;
e l’intersezione di regioni convesse è convessa)
La soluzione di sistemi di disequazioni lineari in due incognite
coincide con la parte di piano comune ai semipiani individuati dalle
singole disequazioni. Questa regione può essere limitata o illimitata.
Ricerca Operativa: un problema di tutti i giorni… – pag. 12
Se le disequazioni del sistema non hanno soluzioni comuni (i
semipiani non si intersecano) il sistema è detto impossibile. Es.:
Con problemi in più di 2 variabili:
La regione ammissibile è un poliedro
(o un iperpoliedro nel caso di più di 3 variabili)
8. Ricerca di massimi o minimi
Risolvere un problema di PL significa determinare se il problema è :
Inammissibile
(il sistema di disequazioni è impossibile)
Illimitato inferiormente o superiormente
(ammette una soluzione ottima che massimizza o minimizza la funzione obiettivo)
Ricerca Operativa: un problema di tutti i giorni… – pag. 13
Se il problema di PL ammette minimo o massimo, allora la funzione
obiettivo: F(x, y) = ax+by+c assume il suo valore massimo o minimo
solo su un VERTICE o su tutti i punti di un LATO della frontiera della
regione ammissibile.
•
Metodo enumerativo
Determinata la regione ammissibile:
a) calcolare le coordinate dei vertici del poligono;
b) calcolare il valore della funzione obiettivo su ogni vertice.
La soluzione è data dalle coordinate del vertice che rende massima o minima la
funzione obiettivo.
F(0,8)=10*0+12*8=96 → F(3/2,7)=10*3/2+12*7=99
F(4,2)=10*4+12*2=64
F(8/3,4/3)=10*8/3+12*4/3=42,7
F(0,4)=10*0+12*4=48
•
Il metodo del Simplesso
Il metodo del simplesso è un algoritmo che permette attraverso un numero finito di
iterazioni, di passare, se il problema ammette soluzione, da un qualsiasi vertice del
poliedro al vertice ottimo.
L'algoritmo del Simplesso, ideato dall'americano George Dantzig nel 1947, è un
metodo numerico per risolvere problemi di PL.
•
Il metodo informatico: il software LINGO
LINGO è un pacchetto software che consente di formulare e risolvere problemi di
ottimizzazione (Programmazione Lineare e non) anche a grandi dimensioni, e di
analizzarne le rispettive soluzioni.
9. Casi di problemi di ricerca operativa
La Ricerca Operativa è utilizzata per risolvere numerosi
quesiti legati al mondo dell'azienda, relativi ad esempio alla “gestione
Ricerca Operativa: un problema di tutti i giorni… – pag. 14
del personale” , problemi del “Commesso Viaggiatore” e problemi del
“Trasporto”.
Obiettivo comune a tali quesiti è la massimizzazione del
profitto e la minimizzazione dei tempi di produzione.
Esempi di problemi :
Ottimizzazione
Una fabbrica produce n prodotti i, ognuno dei quali genera un profitto pi e richiede
un certo quantitativo di risorse ri,j. La fabbrica dispone di una quantità limitata per
alcune risorse rj. Alcuni prodotti non possono essere realizzati in una quantità
minore di mi e non superiore a Mi. Si chiede quali prodotti produrre e in che quantità
per ottenere il massimo profitto, rispettando tutti i vincoli.
Pianificazione
Immaginando di dover consegnare della merce a n destinatari diversi usando m
corrieri, sapendo che ognuno dei destinatari è reperibile soltanto in una determinata
fascia oraria e che un corriere non può caricare più di l lotti, individuare i percorsi
che devono eseguire i corrieri al fine di minimizzare i chilometri percorsi e consegnare tutti i pacchi.
10. Un secondo esempio: il problema dello zaino…
Decisione da prendere:
Quali materie preparare :
• avendo a disposizione un totale di 27 giorni
• volendo massimizzare il profitto?
Strategia (algoritmo) massimo profitto :
• scelgo le materie più remunerative (rispettando il vincolo di 27
giorni)
Ricerca Operativa: un problema di tutti i giorni… – pag. 15
tempo: 27 giorni profitto: 47,50
Materia
Giorni prep.
Profitto
Italiano
10
20,00
Latino
12
22,50
Greco
15
25,00
Inglese
9
15,00
Fisica
7
12,50
Scienze
6
12,50
Storia
6
12,00
Geografia
6
12,00
Disegno
4
7,50
____________________________
Strategie minimo tempo :
• scelgo le materie che richiedono meno tempo di preparazione
Materia
Giorni prep.
Profitto
Italiano
10
20,00
Latino
12
22,50
Greco
15
25,00
Inglese
9
15,00
Fisica
7
12,50
Scienze
6
12,50
Storia
6
12,00
Geografia
6
12,00
Disegno
4
7,50
____________________________
Ricerca Operativa: un problema di tutti i giorni… – pag. 16
Scegliere le cose più importanti, rinunciare a quelle più
pesanti e sistemare il tutto nella valigia in modo da
occupare tutto lo spazio disponibile: questo è ciò che si
propone ciascuno di noi prima di ogni partenza.
Si tratta di un vero e proprio problema
di Ricerca Operativa!
Ricerca Operativa: un problema di tutti i giorni… – pag. 17