Date post: | 15-Feb-2019 |
Category: |
Documents |
Upload: | nguyenhuong |
View: | 218 times |
Download: | 0 times |
Ricerca Operativa
Ricerca Operativa – p. 1/26
Ricerca Operativa
Disciplina basata sulla modellizzazione e la risoluzionetramite strumenti automatici di problemi di decisionecomplessi.
In tali problemi la complessità è determinata dall’ampiezzadello spazio delle scelte possibili.
Ricerca Operativa – p. 2/26
I passi da compiere
Nell’affrontare un problema di decisione il ricercatoreoperativo tipicamente compie questi passi principali:
individuare le componenti del problema di decisione;
creare un modello matematico del problema;
individuare un algoritmo di risoluzione;
validare il modello.
Ricerca Operativa – p. 3/26
Problema di decisione : componenti
Dati - tutto ciò che è noto a priori e non è sotto ilcontrollo del decisore
Variabili - le quantità sotto il diretto controllo del decisore
Vincoli - condizioni che limitano le possibili scelte deldecisore
Obiettivo - criterio attraverso cui le scelte del decisorevengono confrontate
Ricerca Operativa – p. 4/26
Un (banale) esempio
In casa con voi avete:
una borsa del valore di 25 Euro
una macchina fotografica del valore di 100 Euro
un libro del valore di 10 Euro
Potete portare fuori di casa al massimo un oggetto. Voleteportare con voi il massimo valore possibile
Ricerca Operativa – p. 5/26
Un (banale) esempio - continua
Dati - i valori dei tre oggetti
Variabili - per ogni oggetto dovete decidere se portarlocon voi oppure no
Vincolo - potete portare con voi al massimo uno dei treoggetti
Obiettivo - il valore che portate con voi, da massimizzare
Ricerca Operativa – p. 6/26
Variabili
Borsa =
{
NO non porto la borsa con meSI porto la borsa con me
Simile per Macchina Foto e per Libro.
Ricerca Operativa – p. 7/26
Scelte possibili
Borsa Macchina Foto Libro
NO NO NO
SI NO NO
NO SI NO
NO NO SI
SI SI NO
SI NO SI
NO SI SI
SI SI SI
Ricerca Operativa – p. 8/26
Scelte accettabili
Borsa Macchina Foto Libro V alore
NO NO NO 0
SI NO NO 25
NO SI NO 100
NO NO SI 10
Ricerca Operativa – p. 9/26
Un esempio più complesso
Farina Acqua Medicinali UtilitàTIPO I 10 10 30 14TIPO II 30 20 10 5TIPO III 20 40 5 4
Disp.max 5100 8000 1805
Problema: individuare quanti pacchi di ciascun tiporealizzare, tenuto conto delle disponibilità massime dirisorse, in modo da massimizzare l’utilità totale dei pacchirealizzati.
Ricerca Operativa – p. 10/26
Un esempio più complesso - continua
Dati - i valori nella tabella
Variabili - per ogni tipo di pacco dovete decidere quantipacchi di quel tipo realizzare
Vincoli - non superare la disponibilità massima di risorsedisponibili
Obiettivo - il valore di utilità totale, da massimizzare
Ricerca Operativa – p. 11/26
Creare un modello matematico
Problemi di decisione come quello precedentementedescritto possono essere riformulati in modelli diProgrammazione Matematica. Un modello diProgrammazione Matematica è una traduzione delproblema di decisione in linguaggio matematico
Ricerca Operativa – p. 12/26
Variabili - ad ogni variabile viene associata una variabilematematica (ad esempio x1, x2, . . . , xn se abbiamo n
variabili). Alcune di queste (diciamo le prime k)possono assumere valori reali, altre potrebbero esserevincolate ad assumere solo valori interi.
Vincoli - I vincoli vengono espressi tramite equazioni edisequazioni in cui compaiono variabili e dati delproblema
gi(x1, . . . , xn) ≤ (o ≥ o =) 0.
Obiettivo - L’obiettivo viene tradotto in una funzionematematica f(x1, . . . , xn) delle n variabili del problema.
Ricerca Operativa – p. 13/26
Prog. Matematica : il problema generico
max (o min) f(x1, . . . , xn)
gi(x1, . . . , xn) ≤ 0 i ∈ I1
gi(x1, . . . , xn) ≥ 0 i ∈ I2
gi(x1, . . . , xn) = 0 i ∈ I3
x1, . . . , xk ∈ R
xk+1, . . . , xn ∈ Z
Ricerca Operativa – p. 14/26
Regione ammissibile
L’insieme dei punti che soddisfano tutti i vincoli vienechiamato regione ammissibile del problema e nel seguitoverrà indicato con S. Abbiamo quindi:
S = { (x1, . . . , xn) : gi(x1, . . . , xn) ≤ 0, ∀ i ∈ I1
gi(x1, . . . , xn) ≥ 0, ∀ i ∈ I2
gi(x1, . . . , xn) = 0, ∀ i ∈ I3
x1, . . . , xk ∈ R
xk+1, . . . , xn ∈ Z}
Ricerca Operativa – p. 15/26
Risolvere il modello
Risolvere il problema di Programmazione Matematica vuoldire determinare un punto (x∗
1, . . . , x∗
n) ∈ S, che verrà dettosoluzione ottima del problema, tale che
f(x∗
1, . . . , x∗
n) ≤ f(x1, . . . , xn) ∀ (x1, . . . , xn) ∈ S,
se il problema è di minimo, oppure
f(x∗
1, . . . , x∗
n) ≥ f(x1, . . . , xn) ∀ (x1, . . . , xn) ∈ S,
se il problema è di massimo.
Ricerca Operativa – p. 16/26
I problemi lineari
La Programmazione Matematica comprende un grandenumero di problemi. Tra questi una particolare rilevanzahanno i problemi di Programmazione Lineare (PL) eProgrammazione Lineare Intera (PLI).
In entrambi tutte le funzioni (quella obiettivo e quelle chedefiniscono i vincoli) sono funzioni lineari. La soladifferenza tra PL e PLI è rappresentata dal fatto che nellaPL sono presenti solo variabili reali, mentre nella PLI sonopresenti solo variabili che possono assumere valori interi (sipossono avere anche casi misti con alcune varaibili reali ealtre intere ma qui non ce ne occuperemo visto che letecniche risolutive per questi sono analoghe a quelle per iproblemi di PLI).
Ricerca Operativa – p. 17/26
Problemi di PL e PLI
Il generico problema di PL avrà la seguente forma:
max (o min)∑n
j=1cjxj
∑nj=1
aijxj ≤ bi i ∈ I1
∑nj=1
aijxj ≥ bi i ∈ I2
∑nj=1
aijxj = bi i ∈ I3
x1, . . . , xn ∈ R
Nei problemi di PLI la sola differenza sarà rappresentatadal vincolo sulle variabili che sarà
x1, . . . , xn ∈ Z
Ricerca Operativa – p. 18/26
Importanza di PL e PLI
I problemi lineari sono molto importanti perchè:
molti problemi reali hanno un modello di PL o PLI;
per quanto riguarda la PL, la relativa semplicità dirisoluzione di tali problemi implica che anche metodi dirisoluzione per problemi più complessi (tra cui anchequelli di PLI, come avremo modo di vedere) si basanosulla risoluzione multipla di problemi di PL.
Ricerca Operativa – p. 19/26
Il modello dell’esempio
Dati - i valori numerici nella tabella
Variabili - xi =quantità di pacchi di tipo i che decidete direalizzare (i = 1, 2, 3)
Vincoli -
10x1 + 30x2 + 20x3 ≤ 5100 (disp. max farina)
10x1 + 20x2 + 40x3 ≤ 8000 (disp. max acqua)
30x1 + 10x2 + 5x3 ≤ 1805 (disp. max medicinali)
x1, x2, x3 ≥ 0 quantità di pacchi non negativa
Obiettivo -
14x1 + 5x2 + 4x3
Ricerca Operativa – p. 20/26
Modello matematico dell’esempio
max 14x1 + 5x2 + 4x3
tenuto conto che10x1 + 30x2 + 20x3 ≤ 5100
10x1 + 20x2 + 40x3 ≤ 8000
30x1 + 10x2 + 5x3 ≤ 1805
x1, x2, x3 ≥ 0
Si tratta quindi di un modello di PL (o PLI se volessimoimporre anche la non frazionabilità dei pacchi).
Ricerca Operativa – p. 21/26
Perché i modelli matematici?
Una volta che abbiamo a disposizione il modellomatematico del problema non abbiamo ancora risolto ilproblema stesso, lo abbiamo semplicemente tradotto in unaltro linguaggio. Ma perché allora abbiamo fatto questatraduzione?
Sostanzialmente perché una volta trasportato il nostroproblema reale nel mondo astratto della matematica,possiamo utilizzare tutti gli strumenti che ci fornisce questadisciplina per studiarlo.
Questo vuol dire che possiamo studiare la teoria dei modellimatematici e attraverso questa, arivare infine alladefinizione di algoritmi di risoluzione per essi, ovveroprocedure che ricevono in input i modelli e ne restituisconole soluzioni.
Ricerca Operativa – p. 22/26
Individuare un algoritmo di risoluzione
I modelli di programmazione matematica includonomoltissime sottoclassi che possono differire parecchio traloro per quanto riguarda:
le proprietà della funzione obiettivo;
le proprietà delle funzioni che definiscono i vincoli;
il numero e la natura (continue o discrete) delle variabili.
Tali differenze implicano a loro volta differenze per quantoriguarda:
la complessità dei problemi;
gli algoritmi di risoluzione.
Ricerca Operativa – p. 23/26
Quindi ...
... una volta costruito il modello matematico, occorrericonoscere a quale classe appartiene e di conseguenza,scegliere un opportuno algoritmo di risoluzione.
Durante il corso avremo modo di presentare algoritmi perdiversi problemi, con una particolare attenzione per i giàcitati problemi di PL e PLI.
Ricerca Operativa – p. 24/26
Validazione del modello
Quando applichiamo l’algoritmo di risoluzione otteniamo lasolzuione del modello matematico.
È bene rimarcare che questa può non coincidere con lasoluzione del problema di decisione. Infatti, non dobbiamodimenticare che un modello è una rappresentazione dellarealtà, non la realtà stessa.
Tale rappresentazione potrebbe non essere aderente allarealtà. Per esempio, potremmo aver dimenticato unaqualche variabile di decisione e/o un qualche vincolo delproblema.
Ricerca Operativa – p. 25/26
Occorre quindi sempre effettuare, anche dopo aver risoltoun modello, un’analisi critica del modello stesso e capire sesia o meno necessario correggerlo. Nel caso sianecessario, si dovrà tornare a risolvere il modelloaggiornato.
Durante il corso non ci occuperemo oltre di questa fasedetta di validazione del modello, ma teniamo semprepresente che è un’operazione importante da compiere.
Ricerca Operativa – p. 26/26