FONDAMENTI DI RICERCA OPERATIVA - Intranet...
Transcript of FONDAMENTI DI RICERCA OPERATIVA - Intranet...
Laurea Magistrale in Ingegneria Informatica
FONDAMENTI DI RICERCA OPERATIVA
Edoardo Amaldi
DEI - Politecnico di Milano
Pagina web del corso: http://home.dei.polimi.it/amaldi/FRO-Mi-13-14.html
1. INTRODUZIONE
La Ricerca Operativa (“Operations Research”) e la branca della matematica applicata in cui
problemi decisionali complessi
vengono analizzati e risolti mediante modelli matematici e metodi quantitativi avanzati (ot-
timizzazione, simulazione, teoria dei giochi,...).
Scopo: fornire un supporto alla presa di decisioni
A cavallo tra matematica applicata, informatica, economia ed ingegneria
1
1.1 Problemi decisionali
Problemi in cui si deve scegliere una soluzione tra un numero elevato di soluzioni alternative (ammis-
sibili) sulla base di uno o piu criteri
Esempi:
1) Problema di assegnamento: Datim jobs emmacchine, ogni job puo essere eseguito su qualsiasi
macchina e sia tij il tempo di esecuzione del job Ji sulla macchina Mj.
M1 M2 M3
J1 2 6 3
J2 8 4 9
J3 5 7 8
Tabella dei tempi di esecuzione (m = 3)
Decidere quale job assegnare ad ogni macchina in modo da minimizzare il tempo totale di esecuzione.
Ogni job dev’essere assegnato ad una macchina ed ogni macchina deve vedersi assegnare un job.
Numero di soluzioni alternative?
2
1.1 Problemi decisionali
Problemi in cui si deve scegliere una soluzione tra un numero elevato di soluzioni alternative (ammis-
sibili) sulla base di uno o piu criteri
Esempi:
1) Problema di assegnamento: Datim jobs emmacchine, ogni job puo essere eseguito su qualsiasi
macchina e sia tij il tempo di esecuzione del job Ji sulla macchina Mj.
M1 M2 M3
J1 2 6 3
J2 8 4 9
J3 5 7 8
Tabella dei tempi di esecuzione (m = 3)
Decidere quale job assegnare ad ogni macchina in modo da minimizzare il tempo totale di esecuzione.
Ogni job dev’essere assegnato ad una macchina ed ogni macchina deve vedersi assegnare un job.
Numero di soluzioni alternative? m! possibili assegnamenti (=numero di permutazioni)
3
2) Progetto di rete: Decidere come collegare n citta (uffici) tramite un insieme di collegamenti
possibili in modo da minimizzare il costo totale di collegamento.
Dato un grafo G = (V,E) con un nodo i ∈ V per ogni citta e un lato [i, j] ∈ E di costo cijper ogni collegamento, selezionare un sottoinsieme di lati di costo totale minimo che permetta il
collegamento tra tutte le coppie di nodi.
Numero di soluzioni alternative?
4
2) Progetto di rete: Decidere come collegare n citta (uffici) tramite un insieme di collegamenti
possibili in modo da minimizzare il costo totale di collegamento.
Dato un grafo G = (V,E) con un nodo i ∈ V per ogni citta e un lato [i, j] ∈ E di costo cijper ogni collegamento, selezionare un sottoinsieme di lati di costo totale minimo che permetta il
collegamento tra tutte le coppie di nodi.
Numero di soluzioni alternative: ≤ 2m dove m = |E|
5
2) Progetto di rete: Decidere come collegare n citta (uffici) tramite un insieme di collegamenti
possibili in modo da minimizzare il costo totale di collegamento.
Dato un grafo G = (V,E) con un nodo i ∈ V per ogni citta e un lato [i, j] ∈ E di costo cijper ogni collegamento, selezionare un sottoinsieme di lati di costo totale minimo che permetta il
collegamento tra tutte le coppie di nodi.
Numero di soluzioni alternative: ≤ 2m dove m = |E|
3) Cammini minimi: Dato un grafo che rappresenta una rete stradale con una lunghezza (tempo
di percorrenza) per ogni arco, determinare il cammino piu corto (rapido) tra due punti.
6
4) Pianificazione dei turni: Organizzare i turni del personale rispettando le varie esigenze e min-
imizzando il numero di persone coinvolte
5) Gestione di servizi: Determinare il numero di sportelli da aprire affinche il tempo medio di
attesa non superi un certo valore
6) Problema multicriterio: Decidere quale modello di PC portatile acquistare, tenendo conto del
prezzo, del peso, delle prestazioni
7
4) Pianificazione dei turni: Organizzare i turni del personale rispettando le varie esigenze e min-
imizzando il numero di persone coinvolte
5) Gestione di servizi: Determinare il numero di sportelli da aprire affinche il tempo medio di
attesa non superi un certo valore
6) Problema multicriterio: Decidere quale modello di PC portatile acquistare, tenendo conto del
prezzo, del peso, delle prestazioni
Problemi complessi affrontati con l’approccio modellistico (modelli matematici, algoritmi e loro
implementazioni)
8
1.2 Schema generale di uno studio di R.O.
Problema → Modello → Algoritmo → Programma
Fasi principali:
• definizione del problema
• costruzione del modello
• sviluppo dell’algoritmo
• realizzazione del programma
• analisi dei risultati
rimettendo anche in questione le fasi precedenti
Modello: rappresentazione semplificata della realta
Per definirlo bisogna individuare gli elementi fondamentali e le principali relazioni tra di loro
Algoritmo: dipende dal tipo di problema e di modello
9
1.3 Cenni storici: Ricerca Operativa
Origini durante la seconda guerra mondiale:
Gruppi di scienziati/ingegneri incaricati di assegnare in modo efficiente le risorse limitate alle diverse
operazioni (posizionamento dei radar, approvigionamento dei convogli, logistica...)
“Operations Research” sta per la ricerca del modo piu efficiente di condurre le operazioni
Nel dopoguerra, metodi analoghi applicati in ambito economico, industriale e sociale.
Il boom economico, ingrandendo le imprese e organizzazioni, poneva problemi decisionali sempre piu
complessi.
Circostanze favorevoli:
• Rapidi progressi teorici in Ricerca Operativa e in Calcolo Numerico
• Avvento e diffusione dei primi computer (potenza di calcolo disponibile e poi diffusione di software)
Ricerca Operativa = “Management Science”
10
Esempio 1: Mix produttivo
Una azienda produce tre tipi di apparecchiature elettroniche.
Le fasi critiche del ciclo produttivo: assemblaggio, finitura e controllo di qualita.
Minuti-uomo per ogni fase e prodotto:
A1 A2 A3
Assemblaggio 80 70 120
Finitura 70 90 20
Controllo qualita 40 30 20
Disponibilita produttiva nell’orizzonte di pianificazione espressa in minuti-uomo:
Assemblaggio Finitura Controllo qualita
30000 25000 18000
Margine lordo unitario espresso in KEuro:
A1 A2 A3
16 10 2
Si suppone che l’azienda possa vendere tutto cio che produce.
Formulare in termini matematici il problema di determinare un “piano” di produzione che
massimizzi il margine lordo complessivo.
11
Modello mix produttivo
Variabili di decisione:
xj = quantita di apparecchiatura Aj prodotta, con j = 1, 2, 3
Funzione obiettivo:
max z = 16x1 + 10x2 + 2x3
Vincoli: capacita produttiva per ogni fase
80x1 + 70x2 + 120x3 ≤ 30000 (assemblaggio)
70x1 + 90x2 + 20x3 ≤ 25000 (finitura)
40x1 + 30x2 + 20x3 ≤ 18000 (controllo qualita)
Non negativita delle variabili:
x1, x2, x3 ≥ 0 (anche valori frazionari)
12
Esempio 2: Pianificazione di investimenti
Una societa di investimenti finanziari deve decidere la composizione di un portafoglio di titoli.
Investimento Area Capitale [ cj ] (KEuro) Rendimento atteso [ rj ]
A (settore auto) Germania 150 11%
B (settore auto) Italia 150 9%
C (settore informatica) U.S.A. 60 13%
D (settore informatica) Italia 100 10%
E (settore elettrodomestici) Italia 125 8%
F (settore elettrodomestici) Francia 100 7%
G (titoli di stato a breve) Italia 50 3%
H (titoli di stato a lungo) Inghilterra 80 5%
Capitale a disposizione = 600 KEuro
Al massimo 5 investimenti per non frammentare troppo la gestione.
Diversificazione per area geografica: ≤ 3 investimenti in Italia e ≤ 3 all’estero.
Formulare in termini matematici il problema di selezione degli investimenti in modo tale da
massimizzare il ritorno atteso rispettando i vincoli che mirano a ridurre il rischio.
13
Modello di pianificazione di investimenti
Variabili di decisione:
xj = 1 se j-esimo investimento viene effettuato e xj = 0 altrimenti, con j = 1, . . . , 8
Funzione obiettivo:
max z =
8∑j=1
cj rj xj
Vincoli:
8∑j=1
cj xj ≤ 600 (capitale)
8∑j=1
xj ≤ 5 (max 5 investimenti)
x2 + x4 + x5 + x7 ≤ 3 (max 3 in Italia)
x1 + x3 + x6 + x8 ≤ 3 (max 3 all’estero)
Variabili binarie (intere): xj ∈ {0, 1} ∀j, 1 ≤ j ≤ 8
14
Variante: Per limitare il rischio, se si seleziona un investimento nel settore informatico si richiede di
selezionare anche un titolo di stato.
15
Variante: Per limitare il rischio, se si seleziona un investimento nel settore informatico si richiede di
selezionare anche un titolo di stato.
Modello:
max z =
8∑j=1
cj rj xj
8∑j=1
cj xj ≤ 600 (capitale)
8∑j=1
xj ≤ 5 (max 5 investimenti)
x2 + x4 + x5 + x7 ≤ 3 (max 3 in Italia)
x1 + x3 + x6 + x8 ≤ 3 (max 3 all’estero)x3 + x4
2≤ x7 + x8 (investimenti in titoli di stato)
xj ∈ {0, 1} ∀j, 1 ≤ j ≤ 8
16
Esempio 3: Problema di assegnamento
Il responsabile di un azienda di consulenza deve assegnare m = 3 progetti a m ingegneri sulla base delle
seguenti stime dei tempi che ciascuno impiega ad eseguire ogni progetto:
I1 I2 I3P1 2 6 3
P2 8 4 9
P3 5 7 8
Tabella dei tempi di esecuzione tij, 1 ≤ i, j ≤ 3
Formulare in termini matematici il problema di determinare quale progetto assegnare ad ogni
ingegnere in modo tale da minimizzare la somma dei tempi di completamento di tutti i progetti.
17
Modello di assegnamento
Variabili di decisione:
xij = 1 se i-esimo progetto viene assegnato al j-esimo ingegnere e xij = 0 altrimenti
∀ i, j con 1 ≤ i, j ≤ 3
Funzione obiettivo:
min z =
3∑i=1
3∑j=1
tijxij
Vincoli:
3∑i=1
xij = 1 j = 1, 2, 3 (ad ogni ingegnere j un’unico progetto)
3∑j=1
xij = 1 i = 1, 2, 3 (ogni progetto i ad un’unico ingegnere)
Variabili binarie (intere):
xij ∈ {0, 1} ∀i, j, 1 ≤ i, j ≤ 3
18
Esempio 4: localizzazione di impianti
Tre pozzi petroliferi, situati nei punti A, B e C, estraggono greggio.
Si deve localizzare una raffineria e collegarla ai tre pozzi tramite oleodotti di cui il costo e proporzionale
al quadrato della loro lunghezza.
La raffineria non puo essere costruita nel raggio di 100 km attorno al punto (citta) D = (100, 200).
Gli oleodotti possono invece attraversare la zona vietata.
Formulare in termini matematici il problema di decidere dove localizzare la raffineria in modo
da minimizzare il costo degli oleodotti.
19
Modello di localizzazione di impianti
Variabili di decisione:
x1, x2 coordinate cartesiane della raffineria
Funzione obiettivo:
min z =[(x1 − 0)2 + (x2 − 0)2
]+[(x1 − 300)2 + (x2 − 0)2
]+[(x1 − 240)2 + (x2 − 300)2
]Vincoli: √
(x1 − 100)2 + (x2 − 200)2 ≥ 100
Natura variabili:
x1, x2 reali
20
1.4 Caratteristiche dei problemi decisionali
• numero di decisori (chi decide?)
• numero degli obiettivi (in base a quali criteri decide?)
• grado di incertezza dei dati (con quali informazioni decide?)
Un decisore, un obiettivo ⇒ Programmazione matematica
Piu obiettivi ⇒ Programmazione multi-obiettivo
Grado di incertezza > 0 ⇒ Programmazione stocastica
Piu decisori ⇒ Teoria dei giochi
Numero didecisori
Uno Molti
Grado diincertezzaambiente
Certo
Incerto
Numero dicriteri
Uno
Molti
21
1.5 Programmazione matematica (PM)
Problemi decisionali con un solo decisore, un solo criterio di scelta e ambiente certo
opt f (x) con x ∈ X
• variabili di decisione x ∈ Rn : grandezze numeriche il cui valore individua una soluzione del
problema
• regione ammissibile X ⊆ Rn distingue le soluzioni ammissibili da quelle non ammissibili (me-
diante vincoli)
X =
x ∈ Rn : gi (x)
=
≤≥
0, i = 1, . . . ,m
• funzione obiettivo f : X → R esprime in modo quantitativo il gradimento o il costo di ciascuna
soluzione ammissibile
opt =
{min
max
}
Osservazione: max{f (x) : x ∈ X} = −min{−f (x) : x ∈ X}
22
Ottimi globali
Risolvere un problema di Programmazione (Ottimizzazione) Matematica consiste nell’individuare una
soluzione ammissibile globalmente ottima, ovvero un x∗ ∈ X tale che
f (x∗) ≤ f (x) ∀x ∈ X se opt = min
f (x∗) ≥ f (x) ∀x ∈ X se opt = max
Puo avvenire che:
1. il problema sia inammissibile (X = ∅)
2. il problema sia illimitato (∀c ∈ R,∃xc ∈ X tale che f (xc) ≤ c oppure f (xc) ≥ c)
3. vi sia un’unica soluzione ottima
4. vi sia un numero elevatissimo (anche infinito) di soluzioni ottime (con lo stesso valore ottimo!)
23
Ottimi locali
Talvolta ci si deve accontentare di una soluzione ammissibile localmente ottima, ovvero un x ∈ Xtale che
f (x) ≤ f (x) ∀x con x ∈ X e ||x− x|| ≤ ε se opt = min
f (x) ≥ f (x) ∀x con x ∈ X e ||x− x|| ≤ ε se opt = max
per ε > 0 opportuno
Un problema puo avere tanti ottimi locali!
24
Casi particolari di PM
• Programmazione Lineare (PL)
f (x) lineare
X =
x ∈ Rn : gi (x)
=
≤≥
0, i = 1, . . . ,m
con gi (x) lineari per ogni i
Esempio: Mix produttivo
• Programmazione Lineare Intera (PLI)
f (x) lineare
X =
x ∈ Rn : gi (x)
=
≤≥
0, i = 1, . . . ,m
∩ Zn con gi (x) lineari per ogni i
Esempi: Pianificazione investimenti e assegnamento di incarichi
PLI coincide con PL con in piu il vincolo di interezza delle variabili di decisione
25
• Programmazione Non Lineare (PNL)
f (x) convessa/regolare o non convessa/regolare
X =
x ∈ Rn : gi (x)
=
≤≥
0, i = 1, . . . ,m
con per ogni i gi (x) convesse/regolari o non
Esempio: Localizzazione di impianti (con gi convesse)
26
Cenni storici: Programmazione Matematica
1826/1827: Joseph Fourier presenta un metodo per la risoluzione di sistemi di disuguaglianze lineari
(Fourier-Motzkin) e discute alcuni programmi lineari con due o tre variabili
1939: Leonid Kantorovitch getta le basi della Programmazione Lineare (Premio Nobel 1975)
1947: George Dantzig propone indipendentemente la PL ed inventa l’algoritmo del simplesso
1958: Ralph Gomory propone il metodo dei piani di taglio per risolvere i problemi di PLI
Jean-Baptiste Joseph Fourier L.V. Kantorovitch G.B. Dantzig R.E. Gomory
(1786-1830) (1912-1986) (1914-2005) (1929-)
27
1.6 Programmazione a molti obiettivi
Vi sono vari approcci per tenere conto di piu obiettivi
Se si desidera minimizzare f1 (x) e massimizzare f2 (x) (esempio portatile: f1 costo e f2 prestazioni)
1. ricondursi al caso con un solo obiettivo convertendo i diversi obiettivi in unita di misura omogenee
min λ1f1 (x)− λ2f2 (x)
con adeguati scalari λ1 e λ2
2. ottimizzare l’obiettivo prioritario e ridurre quelli secondari a vincoli di qualita
maxx∈X
f2 (x) con X = {x ∈ X : f2 (x) ≤ c}
con una adeguata costante c
3. ottimizzazione lessicografica: tra tutte le soluzione che massimizzano f2, trovare quella che
minimizza f1
minx∈X
f1 (x) dove X = {x ∈ X : x = argmax f2 (x)} .
28
1.7 Programmazione matematica e simulazione
Entrambe richiedono la costruzione di un modello e lo sviluppo di un algoritmo
Programmazione matematica Simulazione
Problemi “ben” formalizzabili Problemi difficili da formalizzare
L’algoritmo fornisce una soluzione L’algoritmo riproduce il sistema reale e perme-
tte di sperimentare le prestazioni di soluzioni
diverse
I risultati sono “certi” I risultati sono da “interpretare”
29
1.8 Esempi di successi della R.O.
anno azienda settore effetto
90 Taco Bell turni personale 7.6M$ risparmio
(fast food) annuo
92 American Arlines nuovo sistema di tariffe, “overbooking” + 500M$
e coordinamento dei voli
92 Harris Corp. pianificazione 50%⇒ 95% ordini
(semiconduttori) produzione “on time”
95 GM - car rental utilizzo parco +50M$ annui
auto evitato fallimento
96 HP - stampanti riprogettata linea raddopiata
produttiva produzione
97 Bosques Arauco logistica taglio 5M$ risparmio
e trasporto annuo
99 IBM riorganizzata catena 750M$ risparmio
logistica annuo
La maggior parte dei manager delle “Fortune 500” dichiara di aver usato le metodologie della R.O.
Video: http://www.bnet.com/videos/operations-research-critical-applications-for-business/178846
30
Non solo per soldi! Ad esempio: progetto regionale con Centrale Operativa 118
Notevoli vantaggi non solo per le grandi aziende/enti/organizzazioni
R.O. utile ogniqualvolta si desidera razionalizzare l’uso di risorse limitate
In un contesto globalizzato e di crisi (caratterizzato da forte competitivita, rapida evoluzione, elevata
complessita ed incertezza) e indispensabile trovare ed implementare soluzioni efficienti.
L’“informatizzazione” e la crescente disponibilita di dati aprono nuovi orizzonti.
32