Appunti Teoria ed esercizi - Laboratorio di Ricerca operativa

Laboratorio di Ricerca Operativa

Laboratorio di Ricerca Operativa - M. Carbone, P. De Rosa, M. Osso

Indice

• Ricerca Operativa
• Problemi di decision making 4
• Il problema di ottimizzazione 4
• Tipologie di Problemi 4
• Mix produttivo ottimale: risorse concorrenti 5
• Mix produttivo ottimale: risorse alternative 5
• Esempio 1.1: Mix produttivo ottimale: risorse concorrenti 6
• Esempio 1.2: Mix produttivo ottimale: risorse alternative 6
• Problema di Miscelazione 7
• Esempio 2.1: Miscelazione 8
• Problema di trasporto 9
• Esempio 3.1: Trasporto 11
• Esempio 3.2: Trasporto con min-max 12
• Geometria della PL 13
• Insieme convesso: 13
• Iperpiani e semispazi 14
• Risoluzione Grafica 17
• Forma Standard di un problema di PL 19
• Da PL alla forma Standard 20
• Significato delle variabili di slack e surplus 20
• I vertici di un problema in FS 21
• Soluzioni ammissibili di base per PFS: 21
• Teorema fondamentale della PL 22
• Teorema fondamentale della PL in termini geometrici 23
• Caratterizzazione Algebrica e Geometrica delle sab 23
• Forma Canonica 23
• Algoritmo del Simplesso 24
• Come calcolo una sab di partenza? 24
• Soluzioni e Ottimalità 25
• Condizioni di ottimalità 25
• Cambio base 26
• Note aggiuntive simplesso 26
• Condizione necessaria di ottimalità 26
• Appunti su Esercizi con Simplesso 27
• Ammissibilità 27

1 Laboratorio di Ricerca Operativa - M. Carbone, P. De Rosa, M. Osso

• Ottimalità 28
• Cambio base: 29
• Condizione sufficiente di ottimalità per s.a.b. : 30
• Condizione sufficiente di illimitatezza: 30
• Teoria della Dualità 31
• Esempio Primale-Duale 32
• Teorema di Dualità debole 34
• Corollario 1: 34
• Corollario 2: 36
• Teorema di Dualità forte 38
• Scarti complementari 40
• Determinare l’ottimo mediante la dualità 42
• Fase 1: Calcolo del duale 42
• Fase 2: Scrivere le relazioni di complementarietà 42
• Programmazione Lineare Numeri Interi (PLI) 44
• Rilassato di un problema intero 45
• Proprietà di interezza 45
• Matrice totalmente unimodulare 46
• Branch and Bound 47
• Algoritmo B&B: 48
• Ottimizzazione su Rete 59
• Teoria dei grafi 59
• Flusso di Costo Minimo 62
• Massimo Flusso 66
• Ford-Fulkerson 68
• Problema di Trasporto (Forma Standard) 71
• Condizione di ammissibilità 71
• Problema dell’Assegnamento 74
• Knapsack Intero 80
• Change Making 81
• Subset Sum 81
• Knapsack Multiplo 82
• Bin Packing 82
• Assegnamento Generalizzato 83
• Recap Problemi 83
• Copertura 84
• Plant Location non capacitato 86
• Plant Location Capacitato 87
• OPL 88

2 Laboratorio di Ricerca Operativa - M. Carbone, P. De Rosa, M. Osso

• Esercitazione 1 91
• Esercitazione 2 92
• Esercitazione 4 93
• Esercitazione 5 94
• Modello dieta 95
• Modello PCentro 96
• Assegnamento 97
• Flusso di Costo Minimo 98
• Flusso di Costo Minimo - Versione 2 99
• Trasporto 100
• Bin Packing 101
• Bin Packing Generalizzato 102
• Surgelati 103
• Modello Commesso Viaggiatore - MTZ (Miller-Zemlin-Tucker) 105
• Modello Commesso Viaggiatore - MTZ (Miller-Zemlin-Tucker) 106

3 Laboratorio di Ricerca Operativa - M. Carbone, P. De Rosa, M. Osso

Cos’è la ricerca operativa?

La ricerca operativa (teoria delle decisioni, scienza della gestione o, in inglese, operations research (“Operational Research” in Europa)) è la branca della matematica applicata in cui problemi decisionali complessi vengono analizzati e risolti mediante modelli matematici e metodi quantitativi avanzati come supporto alle decisioni stesse.

La ricerca operativa riveste un ruolo importante nelle attività decisionali perché permette di operare le scelte migliori per raggiungere un determinato obiettivo rispettando i vincoli che sono imposti dall’esterno e non sono sotto il controllo di chi deve compiere le decisioni.

L’obiettivo è dunque quello di fornire un supporto alla presa di decisioni. Per giungere a questo scopo, la ricerca operativa fornisce strumenti matematici di supporto alle attività decisionali in cui occorre gestire e coordinare attività e risorse limitate al fine di massimizzare o minimizzare una funzione obiettivo.

Problemi di decision making

• Bisogna prendere decisioni quando le alternative sono molte.
• Le decisioni devono essere ottime: Dato un insieme di alternative disponibili e un criterio di valutazione, si vuole determinare l’alternativa più vantaggiosa rispetto al criterio assegnato.

Il problema di ottimizzazione Ω

In un problema di ottimizzazione, sull’insieme ammissibile (spazio delle alternative) viene definita f: Ω→R una funzione obiettivo che fornisce il costo o il beneficio associato ad ogni soluzione; la soluzione del problema è un elemento di Ω che rende minima, oppure massima, la funzione obiettivo.

4 Laboratorio di Ricerca Operativa - M. Carbone, P. De Rosa, M. Osso

Tipologie di problemi

• Modelli di allocazione ottima di risorse (scelta del mix produttivo ottimale): come ▶ utilizzare, in modo “ottimo”, le risorse limitate a disposizione e come distribuirle tra diverse alternative di produzione
• Modelli di miscelazione: come combinare, in modo “ottimo”, le risorse limitate in maniera ▶ tale che il prodotto finale soddisfi i requisiti richiesti
• Modelli di trasporto: come trasportare merci da un dato numero di origini ad un dato ▶ numero di destinazioni al costo minimo (in modo “ottimo”)

Mix produttivo ottimale: risorse concorrenti

5 Laboratorio di Ricerca Operativa - M. Carbone, P. De Rosa, M. Osso

Mix produttivo ottimale: risorse alternative

6 Laboratorio di Ricerca Operativa - M. Carbone, P. De Rosa, M. Osso

Esempio 1.1: Mix produttivo ottimale: risorse concorrenti

Quantità di Tablet Economico 900 + 1220 + 2000 1 2 3 1 Quantità di Tablet Standard 10 + 22 + 34 ≤ 480 1 2 3 2 Quantità di Tablet Lusso 15 + 25 + 30 ≤ 480 1 2 3 310 + 22 + 31 ≤ 3001 2 3 480 = 8h/gg (Tempo lavoro R1,R2) ≤ 0. 3 * ( + + )3 1 2 3 300 = 5h/gg (Tempo di lavoro R3) ≥ 0. 5 * ( + + )1 1 2 3 , , ≥ 01 2 3

Mix produttivo ottimale: risorse alternative

Esempio 1.2: Discrimino i robot, scegliendo quale si occupi di un determinato tipo di tablet 900 + 1220 + 2000 11 21 31 12 22 32 13 23 33 i = robot10 + 22 + 34 ≤ 48011 12 13 j = tablet15 + 25 + 30 ≤ 48021 22 2310 + 22 + 31 ≤ 30031 32 33 3 3( + + ) ≤ 0. 3 * ∑ ∑ 13 23 33 =1 =13 3( + + ) ≥ 0. 5 * ∑ ∑ 11 21 3 =1 =1 ≥ 0

7 Laboratorio di Ricerca Operativa - M. Carbone, P. De Rosa, M. Osso

Problema di miscelazione

Non è richiesta la ripartizione delle risorse ma la loro combinazione. Come miscelare le risorse (gli ingredienti) al costo minimo per ottenere una miscela che abbia una determinata qualità (che dipende dai componenti presenti negli ingredienti);

8 Laboratorio di Ricerca Operativa - M. Carbone, P. De Rosa, M. Osso

Esempio 2.1: Miscelazione

n° porzione di pane5 1∑ oppure oppure 2 + 3 + 4 + 19 + 20 n° porzione di latte 1 2 3 4 5 =1 2 n° porzione di uova110 + 160 + 180 + 260 + 420 ≥ 2000 1 2 3 4 5 3 n° porzione di carne4 + 8 + 13 + 14 + 4 ≥ 50 1 2 3 4 5 4 n° porzione di dolce2 + 285 + 54 + 80 + 22 ≥ 700 1 2 3 4 5 5p porzione massima0 ≤ ≤ 4 , 0 ≤ ≤ 8 i1 2 giornaliera i-esimo0 ≤ ≤ 3 , 0 ≤ ≤ 2 , 0 ≤ ≤ 23 4 5 alimento

9 Laboratorio di Ricerca Operativa - M. Carbone, P. De Rosa, M. Osso

Problema di trasporto

10 Laboratorio di Ricerca Operativa - M. Carbone, P. De Rosa, M. Osso

11 Laboratorio di Ricerca Operativa - M. Carbone, P. De Rosa, M. Osso

Esempio 3.1: Trasporto

i = i-esimo fornitore 10 + 8 + 21 + 12 + 20 + 1411 12 13 21 22 23 j = j-esimo richiedente3 3 ∑ ∑ oppure oppure =1 =1 + + ≤ 18011 12 13 + + ≤ 22021 22 23 + = 8011 21 + = 11012 22 + = 21013 23 ≥ 0

12 Laboratorio di Ricerca Operativa - M. Carbone, P. De Rosa, M. Osso

Esempio 3.2: Trasporto con min-max

f 0, 5 + 0, 7 + 1 = () 11 21 31 1 min max x { 0, 8 + 2 + 0, 5 = () Libri che trasporto12 22 32 21 + 0, 7 + 1, 5 = () dal deposito i alla13 23 33 4 libreria j1, 5 + 0, 5 + 0, 6 = ()14 24 34 4 + + + ≤ 5011 12 13 14 Vincoli di disponibilità dei dep. + + + ≤ 10021 22 23 24 + + + ≤ 10021 22 23 24 + + ≥ 3011 21 23 Vincoli di richieste delle lib. + + ≥ 7012 22 32 + + ≥ 4513 23 33 + + ≥ 4514 24 34 ≥ 0

Introducendo la variabile ausiliaria , necessito di questi vincoli = { (), (), (), ()}1 2 3 4 ≥ () , ≥ () , ≥ () , ≥ () ∈1 2 3 4

13 Laboratorio di Ricerca Operativa - M. Carbone, P. De Rosa, M. Osso

Geometria della PL

Def: Siano dati i punti , ed un vettore ( direzione in ) ∈ ℝ∈ ℝ ℝ

• L'insieme dei punti = { | = + } ∈ ℝ , ∈ ℝ è una retta passante per e parallela a .
• L’insieme dei punti i cui prese- L'insieme dei punti = { | = + } ∈ ℝ , ≥0 è una semiretta con origine in e parallela a .
• L'insieme dei punti , = { | = +1 − , 0≤ ≤1 } ∈ ℝ è un segmento (chiuso) di estremi e .

Insieme convesso

Un insieme si definisce convesso, se prendo due punti x e x generici che appartengono A B (sono contenuti) all'insieme X e il segmento che li unisce (insieme dei punti che va da x a x ) A B appartiene anch’esso all’insieme.

In altre parole presa una terza x che appartiene al C segmento, essa si muove al suo interno proporzionalmente ad un valore .

Se = 0 x = x se = 1 x = x . C A C B Nel caso di valori compresi tra 0 e 1 x si trova non agli estremi del segmento. CL’intersezione di due insiemi convessi risulta in un insieme convesso.

14 Laboratorio di Ricerca Operativa - M. Carbone, P. De Rosa, M. Osso

Se x è un punto frontiera di un insieme convesso allora non è possibile tracciare un C segmento interamente contenuto nell’insieme convesso che abbia x come punto interno al C segmento.

Iperpiani e semispazi

L’iperpiano H è una retta (un insieme di punti) che soddisfa un'equazione lineare e = separa i punti rimanenti dell'intero spazio su cui giace la retta in due semispazi: + −= { | ≥ = { | ≤ } ∈ ℝ } ∈ ℝ

Il vettore è detta vettore normale all’iperpiano. + -I semispazi H e H sono l'insieme dei punti che stanno al di sopra (o esattamente) e al di sotto (o esattamente) della retta.

+ -L’intersezione(∩) di H e H è esattamente H.- +H⊂H , H⊂HDalle definizioni di iperpiano e semispazio deduciamo:

Teorema: L'intersezione di un numero finito di semispazi chiusi è un insieme chiuso.

Teorema: Un semispazio chiuso è un insieme convesso.

Corollario: Un iperpiano è un insieme chiuso e convesso.

15 Laboratorio di Ricerca Operativa - M. Carbone, P. De Rosa, M. Osso

L’insieme ammissibile di un problema di PL è L’insieme di punti che soddisfano un numero finito di vincoli. (insieme finito di equazioni o disequazioni lineari)

In altre parole, tracciamo iperpiani che soddisfano per uguaglianza le rette relative ai vincoli e generano dei semispazi.

La regione ammissibile sarà data dall’intersezione di tutti i semispazi che soddisfano Ω(P) tutti i vincoli per disuguaglianza (≤ o ≥ a seconda del vincolo).

La regione ammissibile è chiusa, in quanto i punti sulla frontiera appartengono alla Ω(P) regione stessa.

È convessa: presi due punti qualsiasi della il segmento che li congiunge appartiene Ω(P), interamente alla regione ammissibile.

Un insieme chiuso e convesso è detto poliedro.

Il poliedro può essere:

• Illimitato: se partendo da un punto generico è possibile tracciare una semiretta Ω(P)∈ interamente contenuta in Ω(P)
• Limitato o politopo: Se non vale il criterio di illimitatezza, ovvero non contiene semirette.

16 Laboratorio di Ricerca Operativa - M. Carbone, P. De Rosa, M. Osso

Punti della regione ammissibile

Un vincolo è attivo, quando soddisfatta l’equazione lineare associata per uguaglianza.

Un punto è: ∈ Ω(P)

• Vertice se q(n-m) vincoli linearmente indipendenti sono attivi nel punto .
• Punto della frontiera se almeno uno dei vincoli è attivo nel punto .
• Punto interno se nessun vincolo di P è attivo.
• Tutti i poliedri che sono regioni ammissibili di problemi di PL , se non vuoti, hanno almeno un vertice.
• Se un problema P di PL ammette soluzione ottima, allora esiste almeno un vertice di che è Ω ottimo

Esempio:

17 Laboratorio di Ricerca Operativa