Ricerca operativa

Martina Contestabile Ingegneria Informatica - II anno A.A. 2021/2022

Ricerca operativa

Martina Contestabile Ingegneria Informatica - II anno A.A. 2021/2022

Indice

Introduzione al corso 11

Perché studiare Ricerca Operativa? 11

Obiettivi del corso 11

Applicazione di metodi scientifici a problemi decisionali 11

Il processo dell’analisi quantitativa consta di 4 passaggi chiave 12

Perché utilizzare la programmazione matematica per trattare problemi reali complessi? 12

Esempi di problemi di ottimizzazione 12

Gestione della logistica di ultimo miglio 12

Minimizzazione della distanza e dei tempi di percorrenza 12

Minimizzazione della distanza e dei tempi di percorrenza 12

Identificazione dei vincitori nelle Aste Combinatorie 13

Massimizzazione del profitto 13

Perforazione di supporto ceramico per moduli multi-chip (644 fori) 14

Minimizzazione dei tempi di lavoro 14

Assegnamento di lavori con vincoli di precedenza su più macchine senza tempi di attesa 14

Minimizzare il tempo di lavoro complessivo 14

Metodologie risolutive (algoritmi) 14

Definizioni e concetti preliminari — Programmazione convessa 16

Problema di ottimizzazione 16

Modello 16

Classificazione I 16

Esempio 16

Classificazione II 17

Problemi e metodologie risolutive 17

Programmazione convessa 17

Insiemi convessi 17

Combinazione convessa 17

Insieme convesso 18

Proposizione 18

Funzione convessa 18

Intorni e ottimi (minimi) locali e globali 19

Ottimo locale 19

Intorno esatto 19

Convessità e intorno euclideo 19

Teorema 19

Funzioni concave 19

Funzione concava 19

Cominciamo ad esercitarci 19

Programmazione lineare 21

Modelli a risoluzione grafica 21

2fi fiéé fifi fifi fi ù

Martina Contestabile Ingegneria Informatica - II anno A.A. 2021/2022

Problema di produzione (tipo I) 21

Problema di produzione (tipo II) 22

Attenzione 23

Cominciamo ad esercitarci! 23

Principi e fondamenti 23

Possibili formulazioni di un problema di programmazione lineare 23

Formulazioni alternative riconducibili alla forma standard 25

Soluzioni di base 25

Soluzione di base 26

Soluzione di base ammissibile 26

Soluzione di base degenere 26

Esempio di determinazione delle soluzioni di base in un problema di programmazione lineare 26

Tipico esercizio di teoria 29

Ragionando 29

Politopi convessi e teoremi 31

Politopi convessi 31

Definizione — Iperpiano 31

Definizione — Semispazio 31

Definizione — punto estremo 31

Definizione — poliedro 31

Definizione — politopo 31

Teorema di Minkowski-Weyl 31

Teorema 32

Teorema di equivalenza 32

Enunciato 32

Teorema fondamentale della PL 33

Enunciato 33

Riassumendo 34

Algoritmo del simplesso 35

Algoritmo del Simplesso — Un esempio introduttivo 35

Qual è il valore massimo che può assumere? 36

Le interpretazioni dell’algoritmo del simplesso 39

Operazione di pivot (cardine) 39

Attenzione! 40

Scelta del pivot (in un problema di minimo) 40

Come scegliere la colonna? 40

Scelta del pivot: come evitare la degenerazione ciclante? 40

Casi particolari e complessità 41

Problema a soluzione illimitata 41

Problema con soluzione ottima multipla 42

3fififififi Martina Contestabile Ingegneria Informatica - II anno A.A. 2021/2022

Soluzioni degeneri e degenerazione ciclante 43

Esempio di simplesso con soluzioni di base degeneri 44

Che complessità ha l’algoritmo del simplesso? 45

Il cubo di Klee-Minty 45

Algoritmo del Simplesso — Soluzione iniziale 46

Problema con vincoli di minore-uguale 47

Problema con vincoli di maggiore-uguale 47

Cosa possiamo fare? 47

Metodo delle due fasi 48

Prima fase 48

Teorema 48

Seconda fase 49

Metodo delle due fasi — Pseudocodice 51

Metodo di penalizzazione — Metodo del big M 52

L’algoritmo del simplesso in forma matriciale 52

Definizione 9 — Coefficienti di costo ridotto 52

Esempio di utilizzo del simplesso matriciale 53

Schema riassuntivo 55

Teoria della dualità — teoremi fondamentali 56

Il problema duale 56

Corrispondenze primale/duale 56

Regole generali per costruire il duale di un problema di Min 57

Esempio 1 57

Esempio 2 57

Proprietà fondamentali 58

Proposizione 1 58

Importanti osservazioni 59

Teorema di dualità in forma debole 59

Enunciato 59

Conseguenze dualità debole 59

Teorema di dualità in forma forte 59

Enunciato 59

Caso 60

Condizioni di ortogonalità — Complementary slackness 61

Condizioni di ottimalità 61

Teorema di Complementary Slackness 62

Esempio — Applicazione di Complementary Slackness 62

Come calcolo le variabili di slack del duale? 63

E la soluzione di base ottima del primale? 63

Interpretazione del duale e prezzi ombra 64

4fi à à àà à ffi à

Martina Contestabile Ingegneria Informatica - II anno A.A. 2021/2022

Dualità e prezzi ombra — Un esempio 64

Il modello matematico 64

Risoluzione con Gurobi I 65

Gurobi II — Calcolo soluzione ottima del duale 65

Risultati 65

Significato dei prezzi ombra 65

Interpretazione economica del duale 66

Analisi di sensitività 67

Modificare i dati di un problema impone la sua riottimizzazione? 67

Variazione dei termini noti 67

Esempio dell’utilizzo dell’analisi di sensitività 68

Esempio sulla variazione del vettore dei termini noti 68

Variazione dei costi delle variabili fuori base 69

Esempio 69

Variazione dei costi delle variabili in base 69

Esempio 70

Algoritmo del simplesso duale 71

Il simplesso duale 71

Aggiunta di vincoli ad una soluzione ottima 71

Simplesso primale vs Simplesso duale 73

Pivot nel simplesso duale 73

Programmazione lineare intera 74

Introduzione e concetto di convex hull 74

Problema di ottimizzazione discreta (di minimo) 74

Applicazioni 74

Programmazione Lineare Intera (PLI) 74

Programmazione Lineare Mista Intera (PLMI) 75

Il rilassamento continuo 75

La regione ammissibile di un problema di PLI 75

Rappresentazione geometrica di X e P 75

Lower Bound e Upper Bound 76

Soluzione PL versus soluzione PLI 76

Proposizione 76

Convex Hull e formulazione ideale 76

Rappresentazione geometrica del Convex Hull 77

Come possiamo risolvere un problema di PLI? 77

Esempio — Algoritmo naif di arrotondamento 77

Matrici unimodulari e totalmente unimodulari 78

Totale unimodularità 78

Definizione 1 78

5fi fifi à Martina Contestabile Ingegneria Informatica - II anno A.A. 2021/2022

Teorema 1 78

Definizione 2 79

Teorema 2 79

Come si dimostra che una matrice A è TUM? 80

Condizione necessaria (non sufficiente) affinché A sia TUM 80

Condizione sufficiente (non necessaria) affinché A sia TUM 80

Teorema 3 80

Proposizione 1 80

Problema del trasporto 81

Tecniche di modellazione 82

Strategie nella formulazione di modelli di PLMI 82

Scelta binaria 82

Il problema dello zaino 0-1 82

Formulazione 83

Applicazione 83

Rilassamento continuo del problema dello zaino 0-1 83

Come possiamo risolvere il problema dello zaino? 83

Algoritmi greedy [ euristici ] per il problema dello zaino 83

Criteri di ordinamento 84

Greedy con ordinamento A — Analisi caso peggiore 84

Soluzione euristica 84

Soluzione ottima 84

Stima dell’errore commesso dall’algoritmo A 84

Greedy con ordinamento C — Analisi caso peggiore 85

Soluzione euristica 85

Soluzione ottima 85

Stima dell’errore commesso dall’algoritmo C 85

Selezione da un insieme 85

Problema di Set Covering 86

Dati 86

Variabili decisionali 86

Formulazione 86

Matrice tecnologica dei vincoli 86

Esempio numerico 86

Problema di Set Covering in forma matriciale 87

Problemi di Set Partitioning e Set Packing 87

Decisioni dipendenti 87

Problema a carico fisso — Fixed Charge Problem 88

Funzione di costo 88

Formulazione iniziale del problema 88

6fi ffi fi ffi ffiffi

Martina Contestabile Ingegneria Informatica - II anno A.A. 2021/2022

Formulazione finale 88

Problema di Plant (Facility) Location 89

Notazione 89

Formulazione matematica 89

Esempio numerico 89

Problema di single item lot-size 90

Parametri 90

Vincoli decisionali 90

Modello dynamic lot-size — Wagner-Whitin 90

Vincoli disgiuntivi — Caso con due vincoli 91

Vincoli disgiuntivi — Generalizzazione al caso con più vincoli 91

Esempio sull’utilizzo di vincoli disgiuntivi 91

Usando PL 92

Usando PLI 92

Problema di sequencing su macchine singola 92

Parametri 93

Variabili 93

Vincoli 93

Modellizzazione 94

Esempio numerico 94

Variabili con dominio discreto numerabile 94

Funzioni lineari a tratti 94

Formulazione I 95

Formulazione II 96

Preprocessing 96

Esempio — Bound stringenti 96

Esempio — Fixing variabili [ problema di minimo ] 97

Esempio — Disuguaglianze logiche 97

Soluzione 98

Algoritmi risolutivi 100

Algoritmi risolutivi 100

Classificazione 100

Algoritmi esatti di PLI 100

Algoritmi di Cutting Planes — Piani di Taglio 100

Algoritmi di Cutting Planes — Piani di Taglio 100

Piano di taglio 100

Definizione 100

Algoritmo di Cutting Planes 100

Tipi di tagli 101

Tagli general-purpose 101

7fi fi fi Martina Contestabile Ingegneria Informatica - II anno A.A. 2021/2022

Tagli specifici 101

Tagli Zero-Half 101

Taglio di Gomory 101

Introduzione 101

Formulazione 102

Algoritmo di Branch-and-Bound 108

Branch-and-Bound 108

Operazioni di branching 109

Criteri di Fathoming 110

Criterio di bounding 110

Strategie di esplorazione dell’albero di ricerca 111

Strategie di accelerazione [ problema di minimo ] 111

Alcune osservazioni sul metodo 111

Branch-and-Bound — Metodo del simplesso 111

Branch-and-Bound — Risoluzione grafica 114

Teoria dei Grafi 115

Grafi non orientati 115

Grafo non orientato 115

Grado di un vertice 115

Grafo completo 115

Cammino 116

Cammino semplice e cammino elementare 116

Vertici connessi 116

Grafo connesso 116

Sottografo 116

Albero di supporto 116

Grafi bipartiti 117

Grafo bipartito 117

Proprietà elementari dei grafi 117

Teorema 1 117

Corollario 117

Cammini e cicli hamiltoniani 118

Cammini e cicli hamiltoniani 118

Grafi hamiltoniani 118

Cammini e cicli euleriani 118

Cammini e cicli euleriani 118

Grafi euleriani 118

Teorema di Eulero — Grafi indiretti 118

Grafi orientati 118

Grafo orientato 118

8fififififi fi fi fi fi fi

Martina Contestabile Ingegneria Informatica - II anno A.A. 2021/2022

Nodi raggiungibili 119

Grafo connesso 119

Gradi di un nodo 119

Grafo fortemente connesso 119

Esempio 119

Rappresentazione di grafi mediante matrici 120

Matrice di incidenza vertici-lati 120

Matrice di incidenza per un grafo non orientato 120

Matrice di incidenza nodi-archi 120

Matrice di incidenza per un grafo orientato 120

Matrici di adiacenza 121

Matrice di adiacenza 121

Traveling salesman problem 122

Il problema del commesso viaggiatore — Traveling Salesman Problem [ TSP ] 122

Complessità del TSP 122

Notazione 123

Esempio 123

Grafi non orientati 123

Grafi orientati 123

Modello matematico TSP1 124

Osservazioni 124

Modello matematico TSP1 124

Osservazioni 125

Esempio — SEC vs CC 125

Trivia time 125

Esempio con vincoli CC 125

Vincoli Miller-Tucker-Zemlin (MTZ) 127

Albero Ricoprente a costo minimo 128

Alberi 128

Proprietà degli alberi 128

Teorema 128

Teorema dello scambio 128

Il problema di albero ricoprente a costo minimo — Minimum Spanning Tree - MST 128

Notazione 128

Applicazioni 129

Modellizzazione matematica MST1 129

Modellizzazione matematica MST2 129

Osservazioni 129

Algoritmo di Kruskal — 1956 129

Algoritmo di Kruskal 130

9fifi fi

Martina Contestabile Ingegneria Informatica - II anno A.A. 2021/2022

Esempio di utilizzo dell’algoritmo di Kruskal 130

Algoritmo di Prim 130

Problema di Cammino Minimo 131

Shortest Path Problem — SPP 131

Definizione di SPP 131

Applicazioni del problema di cammino minimo 131

Problema di cammino minimo 131

Proprietà 131

Complessità 132

Grafi aciclici 132

Teorema 132

Numerazione topologica 132

SPP con costi non negativi 132

Modellizzazione matematica — Caso con cij ≥ 0, (i, j)∈A 132

Esempio numerico 133

Modellizzazione matematica — Caso con cicli negativi 134

Algoritmo di Dijkstra [ 1956 ] 134

Notazione pseudocodice 134

Teorema 135

Esempio di utilizzo dell’algoritmo di Dijkstra 135

Osservazione 136

Esempio 136

Esempi di quesiti di teoria 137

Quesito I 137

Quesito II 137

Quesito III 137

Quesito IV 138

Quesito V 138

Quesito VI 138

Quesito VII 138

Quesito VIII 139

Quesito IX 139

Quesito X 139

Quesito XI 139

Quesito XII 139

Quesito XIII 139

Quesito XIV 140

Quesito XV 140

Quesito XVI 140

Quesito XVII 140

10fi fi Martina Contestabile Ingegneria Informatica - II anno A.A. 2021/2022

Introduzione al corso

Ricerca operativa

Il nome deriva dall’inglese operative research ed è una branca recente, nata nella seconda guerra mondiale per la necessità di combinare diverse branche di studio per risolvere problemi complessi. Il suo luogo di nascita è l’Inghilterra anche grazie a Churchill, si voleva stabilire come piazzare la contraerea, i radar erano costosissimi e si voleva avere la certezza che ciascuno coprisse determinate regioni, però sempre mettendone il minor numero ed avendo la maggior copertura possibile. L’unico problema è che la risoluzione non è polinomiale, quindi è necessaria un’apertura trasversale a più competenze.

Ricerca operativa è la branca della matematica applicata che analizza e risolve problemi decisionali complessi in presenza di risorse scarse.

Problema decisionale

Il problema decisionale è il problema in cui si deve compiere una scelta (decisione) tra più soluzioni valide, secondo uno o più criteri. Quindi, tra il potenziale infinito numero di soluzioni tutte valide, qual è la migliore? Serve una soluzione che ottimizzi una funzione obiettivo. È impossibile, però, mettersi a valutare ogni soluzione, è una scelta esaustiva pessima che riconduce ad un assurdo, non si può fare, ci si può esclusivamente affidare all’utilizzo della programmazione matematica.

La programmazione matematica — o ottimizzazione — è la teoria e metodi per la ricerca di punti di massimo o di minimo di una funzione matematica su un insieme definito.

Perché studiare Ricerca Operativa?

«Il laureato in Ingegneria Informatica possiede solide competenze tecnico-scientifiche di base in diversi settori (matematica, fisica, chimica, ricerca operativa, elettronica, economia applicata all’ingegneria) […] I corsi sono orientati al problem solving dove la capacità di trovare soluzioni in modo autonomo e di giustificare le scelte fatta fortemente incentivata» (dalla Scheda Unica Annuale del Corso di Studio di Ingegneria Informatica)

Operations research analysts use advanced mathematical and analytical methods to help organizations solve problems and make better decisions. Operations research analysts typically do the following: identify and solve problems in areas such as logistics, health care, finance, telecommunication networks or other fields; examine information to figure out what is relevant to a problem and what methods might be used to analyze it; use statistical analysis and mathematical models and develop algorithms to solve problems. (da The Operational Research Society - www.theorsociety.com)

Obiettivi del corso

Cosa impareremo? A risolvere problemi reali complessi.

Come? Attraverso la loro formulazione matematica e lo sviluppo di algoritmi efficaci ed efficienti.

Sommario del corso:

• Programmazione Lineare (PL), circa il 45% del corso.
• Programmazione Lineare Intera (PLI), circa il 35% del corso.
• Ottimizzazione su grafo, circa il 20% del corso.

Applicazione di metodi scientifici a problemi decisionali

Efficace è la qualità della soluzione, efficiente è il tempo computazionale della soluzione.

L’istanza è il caso particolare del problema. Si può sempre partire da istanze piccole, ma quella piccola deve saper risolvere quella grande.

11fi é fi ù fi fi ffi fi ù fi è fi fi à fi ffi fi fi ffi

Martina Contestabile Ingegneria Informatica - II anno A.A. 2021/2022

Il processo dell’analisi quantitativa consta di 4 passaggi chiave

• 1. Descrizione del problema — identificazione dei parametri e dei loro intervalli di variazione.
• 2. Costruzione del modello matematico o problema di ottimizzazione — variabili di decisione, criterio di valutazione, vincoli.
• 3. Risoluzione — algoritmi.
• 4. Applicazione dei risultati con eventuale revisione del modello — feedback.

Perché utilizzare la programmazione matematica per trattare problemi reali complessi?

Permette di applicare il metodo scientifico ai problemi di decisione.

Fornisce un metodo quantitativo facile da usare e controllare.

Le azioni di feedback possono essere facilmente analizzate ed implementate.

I più efficaci ed efficienti metodi risolutivi sfruttano le formulazioni matematiche dei problemi.

Esempi di problemi di ottimizzazione

Gestione della logistica di ultimo miglio

Minimizzazione della distanza e dei tempi di percorrenza

Una nota azienda di e-commerce deve ottimizzare il suo servizio di consegna ultra rapida nell’area metropolitana di Milano: se i clienti non ricevono la merce all’