Appunti completi Ricerca operativa PDF

Preview

Summary

PROGRAMMA RICERCA OPERATIVA1. INTRODUZIONE ED ESEMPI Il problema del commesso viaggiatore: i circuiti Hamiltoniani, l’insieme ammissibile, la funzione ottima e la soluzione ottima; l’insieme inammissibile e i problemi illimitati Presentazione in generale di un problema di ottimizzazione matematica 1...

Description

PROGRAMMA RICERCA OPERATIVA 1. INTRODUZIONE ED ESEMPI 1.1. Il problema del commesso viaggiatore: i circuiti Hamiltoniani, l’insieme ammissibile, la funzione ottima e la soluzione ottima; l’insieme inammissibile e i problemi illimitati 1.2. Presentazione in generale di un problema di ottimizzazione matematica 1.2.1. Problemi con e senza priorità 1.3. Alcuni esempi di problemi: del mix produttivo, della dieta, del trasporto e della pianificazione multiperiodo 1.3.1. Commento sulla pianificazione multiperiodo: le scorte 2. LA RISOLUZIONE GEOMETRICA DEI PROBLEMI 2.1. Le forme dei modelli matematici: generale, standard e mista 2.2. Strategie di cambio tra le formulazioni: le variabili di slack e di surplus 2.3. L’insieme convesso, poliedro, politopo, punti estremi, curva isolivello 2.4. La caratterizzazione delle soluzioni 2.4.1. Dove si trovano le soluzioni ottimali e che cosa sono le soluzioni ottimali multiple 2.4.2. Come si presentano problemi ammissibili, inammissibili ed illimitati 2.4.3. La relazione tra la presenza di una regione ammissibile illimitata e l’illimitatezza di un problema 2.4.4. Nomenclatura dei vincoli 2.4.4.1. I vincoli attivi, inattivi e ridondanti 2.4.4.2. Il legame tra i vincoli attivi e inattivi e le variabili di slack o di surplus 2.4.5. Le soluzioni di base 2.4.5.1. Presentazione del problema: un sistema in n variabili, ma di m equazioni, dove 𝑛 > 𝑚 2.4.5.2. Le soluzioni di base ammissibili e inammissibili 2.4.5.3. Considerazioni geometriche sulle soluzioni di base: la suddivisione della matrice A in due sottomatrici 2.4.5.4. Definizione geometrica delle variabili di base e delle soluzioni di base inammissibili e ammissibili 2.4.5.5. La cardinalità dell’insieme delle soluzioni di base 2.4.5.6. Le basi adiacenti e le soluzioni degeneri 2.4.5.7. Le variabili di lower e di upper bound: le soluzioni di base quando si utilizzano variabili di questo tipo 2.4.6. Ricapitolazione attraverso i teoremi più importanti 2.4.6.1. Il teorema degli esiti ➔ rappresentazioni grafiche dei problemi di natura organizzativa 2.4.6.2. Il teorema di corrispondenza ➔ rappresentazioni grafiche dei problemi di natura organizzativa, le soluzioni di base 2.4.6.3. Il teorema fondamentale dell’ottimizzazione lineare 3. L’ALGORITMO DEL SIMPLESSO 3.1. Da dove nasce il problema: l’enumerazione delle soluzioni di base 3.2. La fase 2 3.2.1. La descrizione sintetica del funzionamento dell’algoritmo 3.2.2. Il passaggio alla forma canonica 3.2.3. Comprendere una condizione di ottimalità attraverso i coefficienti di costo ridotto 3.2.3.1. Dimostrazione del punto precedente 3.2.4. Comprensione dell’illimitatezza di un problema grazie a delle grandezze algebriche nella formula canonica 3.2.5. La presenza di soluzioni degeneri nei problemi: il ciclaggio dell’algoritmo 3.2.5.1. Come ovviare al problema del ciclaggio: la regola di Bland 3.3. La fase 1 3.3.1. A che cosa corrisponde la fase 1 3.3.2. Il problema ausiliario: dimostrazione della sua utilità

4.

5.

6.

7.

3.3.3. Come si procede nella risoluzione di un problema di ottimizzazione quando si usa il problema ausiliario 3.4. Digressioni sul simplesso 3.4.1. Come mi comporto nello svolgimento del simplesso quando utilizzo delle variabili con lower e upper bound 3.4.2. La complessità computazionale del simplesso L’ANALISI DELLA SENSITIVITA’ 4.1. Qual è la domanda di fondo da cui genera l’analisi 4.2. Commento grafico 4.2.1. Il cambiamento dei coefficienti nella funzione obiettivo 4.2.2. Il cambiamento dei termini noti 4.3. Commento analitico 4.3.1. Commento mettendo a confronto i riscontri matematici con quelli grafici 4.4. Riflessioni sul valore 𝜆 4.4.1. Esempio economico che rispecchia le riflessioni fatte 4.5. Riflessioni sui coefficienti di costo ridotto 4.5.1. Esempio economico 4.5.2. Il costo opportunità LA DUALITA’ 5.1. La natura del… 5.2. …duale del mix produttivo 5.3. …duale del problema della dieta 5.4. …duale del trasporto 5.5. Definizioni fondamentali sui duali sia nel caso specifico di un problema di massimo sia nel caso generale 5.6. Il duale di un duale è il primale 5.7. Il duale di un problema con vincoli di uguaglianza 5.8. Teoremi e lemmi fondamentali della teoria della dualità 5.8.1. Il lemma dei segni discordi 5.8.2. Il teorema della dualità debole 5.8.2.1. Primo e secondo corollario del teorema della dualità debole 5.8.3. Il teorema della dualità forte 5.8.4. Il teorema degli scarti complementari L’OTTIMIZZAZIONE INTERA 6.1. Esempi di modelli interi 6.1.1. Problema dello zaino 6.1.2. Problema dei lotti minimi 6.1.3. Problemi dei costi fissi di attrezzaggio 6.1.4. Problema di localizzazione degli impianti 6.1.5. Problema di scheduling: i vincoli either-or e i vincoli disgiuntivi 6.1.6. Problema di assegnazione 6.2. Che cos’è un rilasciamento e a cosa serve 6.3. Le relazioni tra i rilasciamenti e la regione ammissibile intera a cui si riferiscono 6.4. Gli algoritmi per la risoluzione dei problemi di ottimizzazione intera 6.4.1. Algoritmi esatti e approssimati: le differenze 6.4.2. Il metodo dei tagli: i tagli di Gomory 6.4.3. Il metodo di Branch and Bound e il fathoming delle sottoregioni L’OTTIMIZZAZIONE NEI GRAFI 7.1. Caratteristiche e definizioni fondamentali di un grafo 7.2. I tagli 7.3. I sottografi 7.4. L’albero di supporto

7.5. Il problema dell’albero di supporto di costo minimo 7.5.1. L’algoritmo di Kruskal 7.5.2. L’algoritmo di Prim 7.6. Il problema del cammino minimo 7.6.1. L’algoritmo di Dijkstra 7.6.2. L’algoritmo di Floyd-Warshall 7.7. I problemi di flusso 7.7.1. Che cos’è un flusso ammissibile: i vincoli del problema 7.7.2. Il problema di flusso massimo e di costo minimo: il loro legame 7.7.3. L’algoritmo di Ford Fulkerson 7.7.3.1. La rete incrementale e il significato degli archi inversi 7.7.3.2. I cammini aumentanti 7.8. I problemi di taglio 7.8.1. Che cos’è la capacità di un taglio 7.8.2. Teorema sul legame tra il flusso massimo e il taglio minimo 7.8.3. Teorema: il problema del taglio minimo è il duale del problema di flusso massimo 8. PROJECT MANAGEMENT 8.1. Cos’è un progetto 8.2. I problemi che verranno analizzati: di tempificazione e di controllo 8.3. I problemi di tempificazione 8.3.1. Primo metodo di rappresentazione grafica: i grafi 8.3.2. L’ottimizzazione a risorse illimitate: rappresentazione matematica del problema 8.3.3. Il latest start time e l’earliest start time 8.3.4. Il concetto di cammino critico 8.3.5. Secondo metodo di rappresentazione grafica: i Diagrammi di Gantt 8.3.6. La tempificazione nel caso in cui non sia ben chiara la durata delle attività 8.3.7. L’ottimizzazione di questi problemi nel caso in cui si volesse velocizzare le attività 8.4. I problemi di controllo 8.4.1. Lo studio periodo per periodo dei flussi di cassa con i Diagrammi di Gantt 8.4.2. Il profilo dei flussi di cassa 8.4.3. Il controllo dei costi lungo un certo periodo 8.4.4. Il controllo dell’assorbimento delle risorse 8.5. Un problema di ottimizzazione volendo rispettare sia la durata prevista del progetto (problema di tempificazione), sia la capacità produttiva 9. LA TEORIA DELLE DECISIONI 9.1. La differenza fondamentale tra un problema di ottimizzazione e uno decisionale 9.2. Gli elementi fondamentali di un problema di decisione: le alternative, gli stati di natura, il guadagno e la funzione di valutazione 9.3. Scelta in condizione di rischio 9.3.1. Il Valore Atteso Monetario 9.3.2. Il Valore Atteso della Perdita di Opportunità 9.3.3. L’equivalenza tra VAM e VAPO 9.3.4. Il termine di paragone tra VAM e VAPO: il Valore Atteso Monetario con Perfetta Informazione 9.3.5. Il Valore Atteso della Perfetta Informazione 9.3.6. Il Valore Atteso dell’Informazione Campionaria e l’Efficienza dell’Informazione Campionaria 9.4. Scelta in condizione di incertezza 9.4.1. La differenza dal caso precedente 9.4.2. Criterio di equiprobabilità 9.4.3. Criterio MaxiMax: ottimismo 9.4.4. Criterio MaxiMin: pessimismo 9.4.5. Criterio del realismo 9.4.6. Criterio MiniMax

9.5. Gli alberi di decisione e l’uso delle tabelle di contingenza 9.6. La teoria dell’utilità 10. LA TEORIA DEI GIOCHI 10.1. Perché essa può essere intesa come la teoria decisionale in condizione di conflitto 10.2. Gli elementi fondamentali nella teoria dei giochi: i giocatori, le strategie, i profili strategici, la funzione di payoff 10.3. Tassonomia dei tipi di giochi 10.4. Il dilemma del prigioniero: la differenza tra la strategia individuale e collettiva 10.5. L’ottimo paretiano: come nel dilemma del prigioniero l’ottimo paretiano coincide con la strategia collettiva vincente 10.6. Il profilo strategico dominante: il profilo strategico che per qualsiasi giocatore risulta il migliore, data una qualsiasi strategia avversaria ➔ in questo profilo strategico ogni giocatore ha la migliore risposta alla strategia avversaria 10.7. L’equilibrio di Nash: la strategia che soddisfa utilitaristicamente ogni giocatore, pur sapendo che ogni giocatore può cambiare strategia 10.8. Grazie alla dualità è possibile concludere che ogni gioco a strategie miste ha un equilibrio di Nash I PRINCIPALI MODELLI DI OTTIMIZZAZIONE ANALIZZATI OTTIMIZZAZIONE CONTINUA - Mix produttivo - Dieta - Trasporto - Multi-periodo OTTIMIZZAZIONE INTERA - Knapsack:  Molto semplice nella struttura: funzione obiettivo che massimizza l’utilità complessiva del contenuto dello zaino e un solo vincolo sulla capacità dello zaino - Lotti minimi:  L’obiettivo di questo problema è quello di minimizzare i costi di produzione e di mantenimento a scorte  Le limitazioni e le condizioni da rispettare sono quelle sulla consistenza logica tra quanto produco, quante scorte produco e quante scorte uso per poter poi soddisfare la domanda; quelle sulla capacità in ogni periodo di ogni tipo di materiale che ho; quello sul lotto minimo. L’assorbimento di materie prime viene dato da un coefficiente che associa ad ogni materiale i usato il prodotto j che viene prodotto. Attenzione al vincolo che forza la binaria!!! - Costi di attrezzaggio:  Come i lotti minimi, ma senza il vincolo di lotto minimo, con l’aggiunta di una binaria nella funzione obiettivo sui costi per l’utilizzo di attrezzi - Localizzazione:  Il problema si rifà a quello del trasporto, con la differenza che bisogna valutare quali origini aprire!  Vanno minimizzati i costi che includono anche gli investimenti fatti nell’aprire una determinata origine (si considera quindi una variabile binaria in più); i due vincoli sono sempre gli stessi: di domanda nelle destinazioni e di capacità nelle origini (dove ovviamente deve ricomparire la binaria). - Scheduling:  È il problema alla base dei problemi di tempificazione, quindi l’obiettivo sarà semplicemente quello di minimizzare la durata complessiva della sequenza di attività  I vincoli sono:

-

o Durata delle attività sull’ultima macchina: l’ultima attività sull’ultima macchina deve terminare entro la deadline o La durata massima accettabile di ciascuna attività deve essere rispettata o Vincoli sulla successione delle attività: si introduce una binaria sull’evento “l’attività j precede quella k sul macchinario i”. Attenzione che anche qua si introduce un valore gamma grande e che i vincoli sono due perché sono di either-or. o Importante anche l’ultimo vincolo sulla coerenza logica della successione della stessa attività in macchine diverse Assegnazione:  Va minimizzata la spesa nell’assegnazione di un’attività ad una certa persona  I vincoli puntano ad associare ad una persona un’attività sola e ad un’attività una sola persona

CON I GRAFI - Problema dell’albero di supporto minimo ➔ l’obiettivo è quello di minimizzare il costo degli archi scelti; il vincolo fondamentale è quello sul numero degli archi scelti, parti a n-1; inoltre può esserci un altro vincolo, da scegliere tra: o Uno basato sui tagli: per ogni taglio deve esistere necessariamente un arco del taglio (nessun nodo deve risultare isolato) o Uno basato sull’eliminazione dei sottocicli: per ogni sottoinsieme di nodi scelto, il numero degli archi scelti deve risultare pari a 𝑐𝑎𝑟𝑑 (𝑈) − 1 Questi due criteri ritornano anche nella formulazione del commesso viaggiatore - Problema di cammino minimo ➔ l’obiettivo è lo stesso dei problemi degli alberi di costo minimo  In questo caso bisogna fare attenzione al tipo di costi che sono associati agli archi; qualora vi fossero archi a costo negativo, allora sarebbe necessario introdurre i vincoli che impediscono la formazione di sottocicli, perché se si venissero a formare, l’algoritmo creerebbe un loop; qualora non vi fossero archi a costo negativo, i vincoli sono ridondanti e ha senso mantenere solo i vincoli sul bilancio “archi entranti e uscenti”  LA CARDINALITA’ DELL’INSIEME DEI VINCOLI SUI SOTTOCICLI E’ 𝟐𝒏 − 𝟐 - Problema di flusso massimo ➔ vincoli di bilancio nei nodi; vincoli di capacità sugli archi - Problema di taglio minimo (duale del precedente) - Problema del commesso viaggiatore ➔ l’obiettivo è quello innanzitutto di creare un circuito, cioè affermare che da ogni nodo del circuito entra ed esce uno e un solo arco. Il vincolo successivo può essere scelto come nel caso dell’albero di supporto minimo - Ottimizzazione tempi-costi ➔ INTRODUZIONE ALLA RICERCA OPERATIVA La ricerca operativa è una disciplina che si propone di risolvere un problema complesso, caratterizzato da un certo numero di variabili e da un certo numero di vincoli di varia natura che influenzano i range di accettabilità di tali variabili, attraverso modellizzazioni matematiche e tecniche risolutive che si avvalgono spesso di algoritmi. In generale possiamo individuare tre tipi di modelli: - Modelli iconici: rappresentano la realtà fisica attraverso riproduzioni “in scala” - Modelli analogici: rappresentano la realtà grazie a strumenti che la riproducono per analogia - Modelli simbolici: rappresentano la realtà con un linguaggio allo stesso tempo semplice, ma intuibile Inutile specificare che la ricerca operativa si avvale dei modelli simbolici, in quanto in essi compaiono variabili di natura matematica. In un qualunque problema di ottimizzazione, così si chiamano anche i problemi di ricerca operativa, possiamo trovare questi elementi fondamentali: - Una FUNZIONE OBIETTIVO: essa rappresenta la funzione matematica in 𝑛 variabili che va massimizzata o minimizzata, a seconda del tipo di problema che affrontiamo - Un INSIEME AMMISSIBILE: rappresenta l’insieme di tutti quegli elementi 𝑠 che rendono accettabile il risultato della funzione obiettivo

La funzione obiettivo difatti collega un insieme ammissibile con l’insieme dei numeri reali

𝑆→ℝ L’obiettivo ultimo della risoluzione di un problema di𝑓:ottimizzazione è trovare quell’elemento dell’insieme ∗ ∗ ammissibile 𝑠 , la cui immagine 𝑓(𝑠 ) è il minimo 𝑓(𝑠) possibile. L’elemento 𝑠 ∗ è detto SOLUZIONE OTTIMALE. Esistono però situazioni particolari: - Un problema di ottimizzazione può non avere soluzioni, perché non esiste un insieme ammissibile e in tal caso il problema si dice INAMMISSIBILE - Un problema di ottimizzazione può avere infinite soluzioni ammissibili, nessuna delle quali però è in grado di massimizzare o minimizzare il valore della funzione obiettivo; in questo caso il problema si dice ILLIMITATO L’ultimo ingrediente fondamentale presente in ogni problema di ottimizzazione prende il nome di VINCOLO. Un vincolo è una funzione che restringe l’insieme dei valori ammissibili che possono assumere le variabili. Un vincolo tendenzialmente si trova in forma di disequazione, perché appunto pone dei limiti strutturali ai valori accettabili, ma può presentarsi anche sotto forma di equazione: quest’ultimo è il caso dei VINCOLI DI CONSISTENZA LOGICA. Un vincolo di consistenza logica viene introdotto quando si vuole stabilire un legame stretto tra una combinazione di variabili e una variabile particolare. Ricapitolando, un problema di ottimizzazione si compone di: 1. Un insieme di variabili decisionali 2. Una funzione obiettivo che ha come variabili le variabili decisionali, prese una per una oppure presentate attraverso altre variabili per via di vincoli di consistenza logica; questa funzione va massimizzata o minimizzata 3. Un insieme di vincoli, funzioni del tipo 𝑔𝑖 (𝑥), che restringono la regione ammissibile del problema; la regione ammissibile può essere descritta quindi come 𝐾 = {𝑥 ∈ ℝ𝑛 : 𝑔𝑖 (𝑥) ≤ 0 ∀𝑖} 𝑛 N.B. Compare 𝑅 in quanto le soluzioni sono vettori di 𝑛 dimensioni ALCUNI ESEMPI DI PROBLEMI DI OTTIMIZZAZIONE LINEARE CONTINUA In questo documento analizzeremo cinque diversi problemi di ottimizzazione, ciascuno dei quali caratterizzato da una richiesta di fondo diversa e vincoli di diversa natura. L’OTTIMIZZAZIONE MULTI-OBIETTIVO Un problema di questo tipo tiene conto di due obiettivi che vanno minimizzati con un certo grado di PRIORITA’. Se indichiamo con 𝑓(𝑥) e 𝑔(𝑥) rispettivamente il primo e il secondo obiettivo, possiamo identificare problemi… - Senza priorità, dove i due obiettivi compaiono in un’unica formula, che in pratica è una somma pesata - Con priorità: in questi problemi generalmente si procede prima alla ricerca della soluzione ottimale per il primo obiettivo e, successivamente, si cerca di ottimizzare il secondo obiettivo a partire dagli elementi 𝑥 trovati nel passaggio precedente. In particolare, si hanno due funzioni obiettivo 𝑓(𝑥), 𝑔(𝑥) e supponiamo che la f abbia una priorità superiore rispetto alla g e inoltre che sia f che g vadano minimizzate; questo significa che innanzitutto va minimizzata f(x), scegliendo quegli elementi x che inoltre soddisfano il vincolo 𝑔(𝑥) ≤ 𝐺, dove G è la soglia massima ammissibile per g(x); a questo punto, se esistono valori di x che soddisfano anche la relazione 𝑔(𝑥) ≤ 𝐺, si procede con la minimizzazione di g(x) che però ha come vincolo il fatto che ogni valore di x non faccia variare il valore della funzione obiettivo raggiunto nel passaggio

precedente

min 𝑔(𝑥) 𝑐𝑜𝑛 𝑥 ∈ 𝐻 , 𝑑𝑜𝑣𝑒 𝐻 = {𝑥 ∈ 𝐾: 𝑓(𝑥) = 𝑧∗ 𝑓}

IL PROBLEMA DI MIX PRODUTTIVO In questi problemi l’obiettivo è quello di massimizzare i profitti (o qualunque cosa rappresenti la funzione obiettivo), sapendo che i prodotti che la compongono hanno dei vincoli di natura tecnologica: tali vincoli si riferiscono per esempio al fatto che le risorse sono limitate… Per esempio nel problema delle farfalle e dei rigatoni il problema di fondo è che ci sono dei limiti nelle varie fasi della produzione e in ogni fase io produco solo un tot di farfalle o rigatoni. IL PROBLEMA DELLA DIETA Questo problema è molto simile al precedente, con la differenza che i costi ora vanno minimizzati: è necessario combinare un certo numero di ingredienti, che tra l’altro devono trovarsi in quantità minime in un certo prodotto finito, volendo però spendere il minimo possibile. Al contrario del problema di mix produttivo, in un problema della dieta è necessario minimizzare la funzione obiettivo. LA PIANIFICAZIONE MULTIPERIODO Un problema di pianificazione multiperiodo deve tenere conto di una “grandezza economica” che non è ancora comparsa negli altri problemi: LE SCORTE. In un problema di questo tipo infatti è necessario tenere conto che in alcuni periodi in cui viene suddiviso il nostro orizzonte temporale (per esempio la fine di una settimana, di un mese ecc.) può diventare utile tenere da parte una parte del prodotto, appunto le scorte, che poi potranno essere usate nei periodi successivi. La formula fondamentale in questo caso è 𝑃𝑡 + 𝐼𝑡−1 − 𝐼𝑡 = 𝐷𝑡

, dove: - 𝑃𝑡 è la produzione effettiva nel periodo 𝑡 - 𝐼𝑡 , 𝐼𝑡−1 sono rispettivamente l’inventory (la scorta) del periodo precedente che possiamo usare nella vendita e la scorta messa da parte nel periodo corrente - 𝐷𝑡 la vendita effettiva nel periodo 𝑡 N.B. In un orizzonte temporale composto per esempio da tre fasi 1,2,3 NON HA SENSO: - Inserire le scorte da aggiungere da un periodo precedente nel computo della produzione in 1, perché non esiste formalmente un periodo 0 - Inserire le scorte del periodo 3, perché nella formulazione del problema non menzioniamo altri periodi dopo il terzo IL PROBLEMA DEL TRASPORTO In questo caso il problema viene compreso alla perfezione (se non possiede troppe variabili) grazie ai grafi: dei punti vengono connessi e le linee di congiungimento sono il trasporto da un punto 𝑖 ad un punto 𝑗. Il problema del trasporto si propone di: - Minimizzare i costi d...