Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Ricerca Operativa G. Liuzzi1 Luned´ı 24 Febbraio 2014 1 Istituto di Analisi dei Sistemi ed Informatica IASI - CNR Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Notizie utili Giampaolo Liuzzi IASI (CNR), Viale Manzoni 30 (00185, Roma) didattica: http://www.iasi.cnr.it/∼liuzzi/teachita.htm (utilissimo) email: [email protected] (utile) Tel: 06 7716439 (poco utile) Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Notizie utili Ricerca operativa per Ingegneria Informatica e Automatica (BIAR) Ingegneria dei Sistemi Informatici (BSIR) Luned´ı 14:00-17:15 (c’`e la pausa), Gioved´ı 14:00 15:30 Ricevimento: Gioved`ı 16:00-17:00 presso IASI Materiale didattico: http://www.dis.uniroma1.it/ roma/didattica/RO1213/materiale.htm Modalit`a d’esame: test di conoscenza generale (1 ora) che consente di accedere alla successive due prove soluzione di un esercizio riguardante la parte di modellazione (1/2 ora) prova orale Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Il nome Ricerca Operativa `e la traduzione letterale dell’inglese (britannico) “operational research” o (americano) “operations research”, ovvero “ricerca sulle operazioni” Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Il nome Ricerca Operativa (RO) `e la traduzione letterale dellinglese (britannico) “operational research” o (americano) “operations research”, ovvero “ricerca sulle operazioni militari” Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Il nome Ricerca Operativa (RO) `e la traduzione letterale dellinglese (britannico) “operational research” o (americano) “operations research”, ovvero “ricerca sulle operazioni militari” entrambi sono spesso abbreviati con la sigla OR Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Il nome Ricerca Operativa (RO) `e la traduzione letterale dellinglese (britannico) “operational research” o (americano) “operations research”, ovvero “ricerca sulle operazioni militari” entrambi sono spesso abbreviati con la sigla OR altri nomi speso utilizzati sono “Management Science” (MS) e (molto meno freq.) “Decision Analysis” (DA) o “Decision Science” (DS) Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Cosa `e? Ricerca operativa = Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Cosa `e? Ricerca operativa = matematica operativa Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Cosa `e? Ricerca operativa = matematica operativa matematica utile Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Cosa f`a? Un po’ di esempi Uno alla portata di tutti (Il problema del bagaglio a mano) Uno alla portata di molti (Foto in condizioni di scarsa luminosit`a) Uno alla portata di pochi (Il problema dei ponti di K¨onigsberg) Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Il problema del bagaglio a mano dal sito di ALITALIA: Puoi portare 1 bagaglio a mano del peso massimo di 8 kg e avere dimensioni che non superino: 55 cm ALTEZZA 35 cm LARGHEZZA 25 cm SPESSORE Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Il problema del bagaglio a mano dal sito di ALITALIA: Puoi portare 1 bagaglio a mano del peso massimo di 8 kg e avere dimensioni che non superino: 55 cm ALTEZZA 35 cm LARGHEZZA 25 cm SPESSORE Obiettivo: Massimizzare l’utilit`a complessiva degli oggetti nel bagaglio rispettando le regole di Alitalia Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Fotografia in condizioni di scarsa luminosit`a Cosa vogliamo ottenere? ... Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Fotografia in condizioni di scarsa luminosit`a Cosa vogliamo ottenere? ... una bella foto! Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Fotografia in condizioni di scarsa luminosit`a Cosa vogliamo ottenere? ... una bella foto! Un foto ben bilanciata, garantendo assenza di mosso buona definizione buona profondit`a di campo Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Fotografia in condizioni di scarsa luminosit`a Su cosa possiamo intervenire? tempo di posa (basso, ma non troppo!) apertura (grande, ma non troppo!) sensibilit`a (alta, ma non troppo!) Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Il problema dei ponti di K¨onigsberg K¨onigsberg (Prussia) ovvero l’attuale Kaliningrad (Russia) aveva la seguente particolarit`a Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Il problema dei ponti di K¨onigsberg Problema: Determinare un percorso nella citt`a che attraversi ciascuno dei sette ponti una ed una sola volta. Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Il problema dei ponti di K¨onigsberg Problema: Determinare un percorso nella citt`a che attraversi ciascuno dei sette ponti una ed una sola volta. Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Il problema dei ponti di K¨onigsberg Problema: Determinare un percorso nella citt`a che attraversi ciascuno dei sette ponti una ed una sola volta. Obiettivo: Esiste un cammino nel grafo che tocca ogni arco una ed una sola volta? Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Il problema del ciclo Hamiltoniano ... a Vigata Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Il problema del ciclo Hamiltoniano ... a Vigata Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Il problema del ciclo Hamiltoniano ... a Vigata Andrea Camilleri Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Il problema del ciclo Hamiltoniano ... a Vigata Andrea Camilleri “La prima indagine di Montalbano” “Sette Luned`ı” Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Un problema esempio [...] “Adesso facciamo cos`ı. Tu, Mim´ı, vai all’ufficio anagrafe e ti fai dare l’elenco di tutti quelli il cui cognome principia con la vocale O. Non saranno centomila.” [...] [...] Mim´ı Augello gli sbatt´ı sulla scrivania, con un’ariata sdignosa, una decina di fogli scritti fitti fitti. “Questo `e l’elenco di tutti quelli il cui cognome principia per O. Per tua conoscenza, si tratta di quattrocentodue persone, tra mescoli, fimmine, picciotti, picciotteddre, vecchi, picciliddri e neonati.” [...] [...] “Quindi ora voi sapete dove abitano. Mim´ı, ti devi mettere a un’opera fina, ma camurriosa. Fai un segno di croce, sullo stradario di Vigata, per indicare dove stanno di casa questi che hanno il cognome che principia con la O. Quindi traccia un percorso ideale, il piu’ breve, perch´e al momento opportuno noi possiamo avvertire tutti nel minor tempo possibile.” Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Un problema esempio Problema del Commesso Viaggiatore o problema del ciclo Hamiltoniano di lunghezza minima Dato un insieme di citt`a, determinare il percorso di lunghezza minima che passa una e una sola volta per tutte le citt`a. ` uno dei problemi pi` E u difficili della RO. Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Storicamente ... Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Il problema di assegnamento ` stato formulato (per la prima volta) negli anni 50 da uno E psicologo!!!, R.L. Thorndike, Presidente della Division on Evaluation and Measurement, American Psychological Association. Vediamo in che termini: Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Il problema di assegnamento ` stato formulato (per la prima volta) negli anni 50 da uno E psicologo!!!, R.L. Thorndike, Presidente della Division on Evaluation and Measurement, American Psychological Association. Vediamo in che termini: “Given: A set of job categories with N vacancies to be filled, and N individuals to be used in filling them. Required: To assign the individuals to the jobs in such a way that the average success of all the individuals in all the jobs to which they are assigned will be a maximum.” (“The problem of classication of personnel”, Psychometrica, 1950). Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Il problema di assegnamento Q: In quanti modi `e possibile assegnare i lavoratori ai lavori ? Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Il problema di assegnamento Q: In quanti modi `e possibile assegnare i lavoratori ai lavori ? A: N(N − 1)(N − 2) · · · 2 = N! cio`e pari al numero di permutazioni di N elementi. Quindi abbiamo un numero finito (anche se grande) di soluzioni ! Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Il problema di assegnamento “There are, as has been indicated, a finite number of permutations in the assignment of men to jobs. When the classification problem as formulated above was presented to a non-OR-expert, he pointed to this fact and said that from the point of view of the mathematician there was no problem. Since the number of permutations was finite, one had only to try them all and choose the best. He dismissed the problem at that point. This is rather cold comfort to the psychologist, however, when one considers that only ten men and ten jobs mean over three and a half million permutations. Trying out all the permutations may be a mathematical solution to the problem, it is NOT an operational solution.” Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Enumerazione esaustiva delle soluzioni Questo esempio ` e dovuto a G.B. Dantzig - Linear Programming the story about it began: some legends, a little about historical significance, and comments about where its many mathematical programming extensions may be headed in History of Mathematical programming - a collection of personal reminiscences, J.K. Lenstra, A.H.G. Rinnooy Kan and A. Schrijver eds., North Holland (1991). Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Enumerazione esaustiva delle soluzioni Questo esempio ` e dovuto a G.B. Dantzig - Linear Programming the story about it began: some legends, a little about historical significance, and comments about where its many mathematical programming extensions may be headed in History of Mathematical programming - a collection of personal reminiscences, J.K. Lenstra, A.H.G. Rinnooy Kan and A. Schrijver eds., North Holland (1991). Supponiamo che sia N = 70 Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Enumerazione esaustiva delle soluzioni Questo esempio ` e dovuto a G.B. Dantzig - Linear Programming the story about it began: some legends, a little about historical significance, and comments about where its many mathematical programming extensions may be headed in History of Mathematical programming - a collection of personal reminiscences, J.K. Lenstra, A.H.G. Rinnooy Kan and A. Schrijver eds., North Holland (1991). Supponiamo che sia N = 70 Le capacit`a lavorative di ogni singolo dipendente sono diverse, dunque non `e indifferente per l’azienda come effettuare l’assegnamento. Sia vij una quantificazione del beneficio che si ottiene assegnando la persona i-esima alla mansione j-esima. Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Enumerazione esaustiva delle soluzioni Questo esempio ` e dovuto a G.B. Dantzig - Linear Programming the story about it began: some legends, a little about historical significance, and comments about where its many mathematical programming extensions may be headed in History of Mathematical programming - a collection of personal reminiscences, J.K. Lenstra, A.H.G. Rinnooy Kan and A. Schrijver eds., North Holland (1991). Supponiamo che sia N = 70 Le capacit`a lavorative di ogni singolo dipendente sono diverse, dunque non `e indifferente per l’azienda come effettuare l’assegnamento. Sia vij una quantificazione del beneficio che si ottiene assegnando la persona i-esima alla mansione j-esima. I vincoli sono ciascun dipendente deve essere assegnato ad un solo lavoro ciascuna mansione deve essere svolta esattamente da un dipendente Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Esempio di Dantzig Dunque, abbiamo 2 × 70 vincoli e 70! possibili assegnamenti. Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Esempio di Dantzig Dunque, abbiamo 2 × 70 vincoli e 70! possibili assegnamenti. Il problema consiste nel confrontare le 70!(> 10100 ) possibilit`a, per selezionare quella migliore. Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Esempio di Dantzig Dunque, abbiamo 2 × 70 vincoli e 70! possibili assegnamenti. Il problema consiste nel confrontare le 70!(> 10100 ) possibilit`a, per selezionare quella migliore. Supponiamo di disporre di un calcolatore capace di effettuare 106 confronti al secondo e che sia in funzione da 15 miliardi di anni (circa il tempo trascorso dal Big Bang ad oggi); Avrebbe, questo calcolatore, oggi (nell’anno 2014) esaminato tutte le 70! combinazioni possibili ? Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Esempio di Dantzig Dunque, abbiamo 2 × 70 vincoli e 70! possibili assegnamenti. Il problema consiste nel confrontare le 70!(> 10100 ) possibilit`a, per selezionare quella migliore. Supponiamo di disporre di un calcolatore capace di effettuare 106 confronti al secondo e che sia in funzione da 15 miliardi di anni (circa il tempo trascorso dal Big Bang ad oggi); Avrebbe, questo calcolatore, oggi (nell’anno 2014) esaminato tutte le 70! combinazioni possibili ? La risposta e NO! Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Esempio di Dantzig La risposta `e ancora NO, anche se disponessimo di tanti calcolatori che lavorano in parallelo sufficienti a coprire la superficie terrestre e che possano effettuare 109 assegnamenti ogni 10−6 secondi. Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Esempio di Dantzig La risposta `e ancora NO, anche se disponessimo di tanti calcolatori che lavorano in parallelo sufficienti a coprire la superficie terrestre e che possano effettuare 109 assegnamenti ogni 10−6 secondi. In certe situazioni `e dunque assolutamente impossibile esaminare tutti i casi possibili per determinare qual’`e il migliore. “ad hoc” ground-rule approach: affidarsi al buon senso di persone guidate dall’esperienza che stabiliscano regole “ad hoc” di base che dovrebbero essere seguite per risolvere il problema approccio modellistico-ottimizzatorio: approccio introdotto dalla RO Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Esempio di Dantzig A tutt’oggi il “metodo” di confronto di tutte le soluzioni possibili `e praticabile solo per N < 20 Eppure Si risolvono all’ottimo problemi con N = 150(!!) Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Un problema di Capital Budgeting Un piccolo investitore deve stabilire come investire il proprio capitale potendo scegliere tra 6 differenti investimenti. L’investitore dispone di un budget di 100000e e conosce i costi di attivazione nonch´e il Net Present Value (NPV) di ciascuno di essi come riportato nella tabella che segue: inv.1 inv.2 inv.3 inv.4 inv.5 inv.6 Ricerca Operativa costo ×1000e 100 50 45 20 10 5 NPV 40 35 18 4 10 2 G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Formalizzazione matematica P insieme delle scelte possibili P = {1, 2, 3, 4, 5, 6} Per ogni i ∈ P, siano wi e pi rispettivamente il costo ed il NPV associati ad i. Sia C = 100000 il budget disponibile. Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Formalizzazione matematica P insieme delle scelte possibili P = {1, 2, 3, 4, 5, 6} Per ogni i ∈ P, siano wi e pi rispettivamente il costo ed il NPV associati ad i. Sia C = 100000 il budget disponibile. Dato che un investimento pu` o solo essere attivato per intero o non essere attivato, introduciamo, per ogni i ∈ P, le variabili: 1 se l’inv. i `e attivato xi = 0 altrimenti. Percui una selezione di investimenti `e rappresentata da un vettore x ∈ {0, 1}6 o vettore di incidenza. N.B. Non tutte le possibili selezioni di investimenti sono ammissibili. Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Formalizzazione matematica Ad esempio: il vettore (1, 0, 0, 0, 0, 0) rapp. una scelta ammissibile; il vettore (1, 0, 0, 0, 0, 1) rapp. una scelta NON ammissibile; In totale ci sono 26 = 64 possibili scelte (solo 48 ammissibili)! il vettore (1, 0, 0, 0, 0, 0) da un NPV pari a 40; il vettore (0, 0, 0, 1, 1, 1) da un NPV pari a 16; Problema: Tra tutte le scelte ammissibili determinare quella che da il NPV totale maggiore. Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Formalizzazione matematica Ancora non vogliamo risolvere il problema. Vogliamo rappresentarlo in forma compatta (mediante relazioni matematiche) quali sono le scelte ammissibili; quale `e il NPV totale di una generica scelta di investimenti. Come fareste ? Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione NPV totale Esiste una funzione che, dato un vettore di incidenza x di un piano di investimenti, fornisce il NPV totale associato ad x ? Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione NPV totale Esiste una funzione che, dato un vettore di incidenza x di un piano di investimenti, fornisce il NPV totale associato ad x ? NPVtot = f (x) = Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione NPV totale Esiste una funzione che, dato un vettore di incidenza x di un piano di investimenti, fornisce il NPV totale associato ad x ? NPVtot = f (x) = 40x1 + Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione NPV totale Esiste una funzione che, dato un vettore di incidenza x di un piano di investimenti, fornisce il NPV totale associato ad x ? NPVtot = f (x) = 40x1 + 35x2 + 18x3 + 4x4 + 10x5 + 2x6 . f (x) = 6 X pi x i i=1 Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Costo totale Esiste una funzione che, dato un vettore di incidenza x di un piano di investimenti, fornisce il Costo totale associato ad x ? Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Costo totale Esiste una funzione che, dato un vettore di incidenza x di un piano di investimenti, fornisce il Costo totale associato ad x ? Ctot = g (x) = Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Costo totale Esiste una funzione che, dato un vettore di incidenza x di un piano di investimenti, fornisce il Costo totale associato ad x ? Ctot = g (x) = 100x1 + Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Costo totale Esiste una funzione che, dato un vettore di incidenza x di un piano di investimenti, fornisce il Costo totale associato ad x ? Ctot = g (x) = 100x1 + 50x2 + 45x3 + 20x4 + 10x5 + 5x6 . g (x) = 6 X wi xi ≤ C = 100 i=1 Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Problema di Programmazione Matematica max x s.t. 6 X pi x i i=1 6 X wi xi ≤ C i=1 x ∈ {0, 1}6 . Tutte le variabili xi possono assumere solo valore 0 o 1 quindi si parla di Programmazione 0/1 o Programmazione binaria Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Problema del Commesso Viaggiatore Problema: Dato un insieme di citt`a, determinare il percorso di lunghezza minima che passa una e una sola volta per tutte le citt`a. In termini pi` u generali: Dato un grafo G = (V , E ), con V = {1, 2, . . . , n} e E = V × V , e assegnate delle lunghezze δij ad ogni arco (i, j) ∈ E , si vuole determinare il ciclo di lunghezza minima che passa una ed una sola volta per ogni nodo del grafo. Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Problema del Commesso Viaggiatore Problema: Dato un insieme di citt`a, determinare il percorso di lunghezza minima che passa una e una sola volta per tutte le citt`a. In termini pi` u generali: Dato un grafo G = (V , E ), con V = {1, 2, . . . , n} e E = V × V , e assegnate delle lunghezze δij ad ogni arco (i, j) ∈ E , si vuole determinare il ciclo di lunghezza minima che passa una ed una sola volta per ogni nodo del grafo. Un ciclo che passa una ed una sola volta per ogni nodo di G `e detto ciclo HAMILTONIANO Il numero di soluzioni ammissibili del problema (ovvero di cicli Hamiltoniani nel grafo) `e finito e pari a Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Problema del Commesso Viaggiatore Problema: Dato un insieme di citt`a, determinare il percorso di lunghezza minima che passa una e una sola volta per tutte le citt`a. In termini pi` u generali: Dato un grafo G = (V , E ), con V = {1, 2, . . . , n} e E = V × V , e assegnate delle lunghezze δij ad ogni arco (i, j) ∈ E , si vuole determinare il ciclo di lunghezza minima che passa una ed una sola volta per ogni nodo del grafo. Un ciclo che passa una ed una sola volta per ogni nodo di G `e detto ciclo HAMILTONIANO Il numero di soluzioni ammissibili del problema (ovvero di cicli Hamiltoniani nel grafo) `e finito e pari a n! numero di permutazioni di n oggetti. Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Rappresentazione del problema Sia G = (V , E ) con V = {1, 2, 3, 4, 5}. Graficamente abbiamo: 4 3 2 5 1 Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Rappresentazione del problema Sia G = (V , E ) con V = {1, 2, 3, 4, 5}. Il ciclo corrsipondente alla permutazione dei nodi {1, 3, 2, 4, 5} `e evidenziato in rosso 4 3 2 5 1 Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Formulazione matematica del problema Passo 1. Scelta delle variabili: Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Formulazione matematica del problema Passo 1. Scelta delle variabili: 1 se (i, j) appartiene ad un ciclo xij = 0 altrimenti Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Formulazione matematica del problema Passo 1. Scelta delle variabili: 1 se (i, j) appartiene ad un ciclo xij = 0 altrimenti Quindi, per il ciclo di prima, se indichiamo con E¯ = {(1, 3), (3, 2), (2, 4), (4, 5), (5, 1)} l’insieme degli archi che compongono il ciclo, abbiamo: 4 x13 = x32 = x24 = x45 = x51 = 1 xij = 1, xij = 0, 3 ∀(i, j) ∈ E¯ , ∀(i, j) ∈ E \ E¯ . 2 5 1 Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Formulazione matematica del problema Passo 2. Funzione obiettivo: min X δij xij . (i,j)∈E Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Formulazione matematica del problema Passo 3. Vincoli: xij ∈ {0, 1}, ∀ (i, j) ∈ E Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Formulazione matematica del problema Passo 3. Vincoli: xij ∈ {0, 1}, ∀ (i, j) ∈ E Servono dei vincoli (delle relazioni) che IMPONGANO che xij = 1, se (i, j) appartiene ad un ciclo Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Formulazione matematica del problema Passo 3. Vincoli: xij ∈ {0, 1}, ∀ (i, j) ∈ E Servono dei vincoli (delle relazioni) che IMPONGANO che xij = 1, se (i, j) appartiene ad un ciclo Concentriamoci sul nodo 4 Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Formulazione matematica del problema Passo 3. Vincoli: xij ∈ {0, 1}, ∀ (i, j) ∈ E Servono dei vincoli (delle relazioni) che IMPONGANO che xij = 1, se (i, j) appartiene ad un ciclo 4 Concentriamoci sul nodo 4 e notiamo che 2 5 un solo arco ENTRA in 4 un solo arco ESCE da 4 3 1 Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Formulazione matematica del problema Passo 3. Vincoli: xij ∈ {0, 1}, ∀ (i, j) ∈ E Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Formulazione matematica del problema Passo 3. Vincoli: xij ∈ {0, 1}, ∀ (i, j) ∈ E X xik = 1, ∀k ∈ V , (i,k)∈E Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Formulazione matematica del problema Passo 3. Vincoli: xij ∈ {0, 1}, ∀ (i, j) ∈ E X xik = 1, ∀k ∈ V , xkj = 1, ∀k ∈ V , (i,k)∈E X (k,j)∈E Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Pianificazione ottima della produzione Un colorificio produce 2 tipi di coloranti C1 e C2 utilizzando 3 preparati base P1, P2 e P3. La tabella riporta: (a) le quantit`a (in litri) di preparati base necessari per produrre un litro di ciascun tipo di colorante; (b) le disponibilit`a massime (in litri/mese) di preparati base; (c) il prezzo di vendita (in eur/litro) dei due coloranti. P1 P2 P3 prezzo C1 1 1 0 7 C2 1 2 1 10 q.max 750 1000 400 Determinare la strategia ottima di produzione mensile. Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Formulazione matematica del problema Passo 1: Scelta delle variabili di decisione x1 : indica la quantit`a in litri/mese di C1 prodotto; x2 : indica la quantit`a in litri/mese di C2 prodotto; Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Formulazione matematica del problema Passo 1: Scelta delle variabili di decisione x1 : indica la quantit`a in litri/mese di C1 prodotto; x2 : indica la quantit`a in litri/mese di C2 prodotto; Passo 2: Funzione obiettivo max 7x1 + 10x2 Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Formulazione matematica del problema Passo 1: Scelta delle variabili di decisione x1 : indica la quantit`a in litri/mese di C1 prodotto; x2 : indica la quantit`a in litri/mese di C2 prodotto; Passo 2: Funzione obiettivo max 7x1 + 10x2 Passo 3: Vincoli x1 + x2 ≤ 750 x1 + 2x2 ≤ 1000 x2 ≤ 400 x1 , x2 ≥ 0 Ricerca Operativa disp. di P1 disp. di P2 disp. di P3 non negativit`a G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Interpretazione geometrica ` possibile evidenziare, mediante semplici considerazioni di E geometria analitica, la regione del piano R 2 costituita da punti che soddisfano tutti i vincoli del problema. x2 x1 , x2 ≥ 0 quindi i p.ti ammissibili appartengono all’ortante positivo x1 Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Interpretazione geometrica ` possibile evidenziare, mediante semplici considerazioni di E geometria analitica, la regione del piano R 2 costituita da punti che soddisfano tutti i vincoli del problema. x2 x1 , x2 ≥ 0 quindi i p.ti ammissibili appartengono all’ortante positivo x2 ≤ 400 750 400 x2=400 x1 Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Interpretazione geometrica ` possibile evidenziare, mediante semplici considerazioni di E geometria analitica, la regione del piano R 2 costituita da punti che soddisfano tutti i vincoli del problema. x2 750 50 =7 +x 2 x1 x1 , x2 ≥ 0 quindi i p.ti ammissibili appartengono all’ortante positivo x2 ≤ 400 400 x2=400 x1 + x2 ≤ 750 x1 Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Interpretazione geometrica ` possibile evidenziare, mediante semplici considerazioni di E geometria analitica, la regione del piano R 2 costituita da punti che soddisfano tutti i vincoli del problema. x2 750 x1 + x2 ≤ 750 x1 + 2x2 ≤ 1000 Ricerca Operativa 50 500 x2 ≤ 400 =7 +x 2 x1 x1 , x2 ≥ 0 quindi i p.ti ammissibili appartengono all’ortante positivo x2=400 400 x+ 1 2x = 2 100 0 x1 750 1000 G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Un problema di miscelazione Un’industria conserviera produce succhi di frutta (SF ) mescolando polpa di frutta (P) e dolcificante (D). Il prodotto finale deve soddisfare alcuni requisiti sul contenuto di Vitamina C (V ), Sali minerali (S) e Zucchero (Z ). P D SF costo [ecent /hg] 40 60 V [mg/hg] 140 – ≥ 70 S [mg/hg] 20 10 ≥ 30 Z [g/hg] 25 50 ≥ 75 Problema: Determinare le quantit`a ottime di P e D da miscelare. Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Formulazione matematica Passo 1: Scelta delle variabili di decisione x1 : indica la quantit`a in hg di P; x2 : indica la quantit`a in hg di D; Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Formulazione matematica Passo 1: Scelta delle variabili di decisione x1 : indica la quantit`a in hg di P; x2 : indica la quantit`a in hg di D; Passo 2: Funzione obiettivo min 40x1 + 60x2 Ricerca Operativa G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Formulazione matematica Passo 1: Scelta delle variabili di decisione x1 : indica la quantit`a in hg di P; x2 : indica la quantit`a in hg di D; Passo 2: Funzione obiettivo min 40x1 + 60x2 Passo 3: Vincoli 140x1 ≥ 70 Ricerca Operativa req. su V G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Formulazione matematica Passo 1: Scelta delle variabili di decisione x1 : indica la quantit`a in hg di P; x2 : indica la quantit`a in hg di D; Passo 2: Funzione obiettivo min 40x1 + 60x2 Passo 3: Vincoli 140x1 ≥ 70 20x1 + 10x2 ≥ 30 Ricerca Operativa req. su V req. su S G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Formulazione matematica Passo 1: Scelta delle variabili di decisione x1 : indica la quantit`a in hg di P; x2 : indica la quantit`a in hg di D; Passo 2: Funzione obiettivo min 40x1 + 60x2 Passo 3: Vincoli 140x1 ≥ 70 20x1 + 10x2 ≥ 30 25x1 + 50x2 ≥ 75 Ricerca Operativa req. su V req. su S req. su Z G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Formulazione matematica Passo 1: Scelta delle variabili di decisione x1 : indica la quantit`a in hg di P; x2 : indica la quantit`a in hg di D; Passo 2: Funzione obiettivo min 40x1 + 60x2 Passo 3: Vincoli 140x1 ≥ 70 20x1 + 10x2 ≥ 30 25x1 + 50x2 ≥ 75 x1 , x2 ≥ 0 Ricerca Operativa req. su V req. su S req. su Z non negativit`a G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Interpretazione geometrica ` possibile evidenziare, mediante semplici considerazioni di E geometria analitica, la regione del piano R 2 costituita da punti che soddisfano tutti i vincoli del problema. x1 , x2 ≥ 0 quindi i p.ti ammissibili appartengono all’ortante positivo 2 x2 1 0.5 x1 0.5 Ricerca Operativa 1 2 G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Interpretazione geometrica ` possibile evidenziare, mediante semplici considerazioni di E geometria analitica, la regione del piano R 2 costituita da punti che soddisfano tutti i vincoli del problema. x1 , x2 ≥ 0 quindi i p.ti ammissibili appartengono all’ortante positivo 2 x2 x1 ≥ 70/140 1 140x1 ≥ 70 0.5 x1 0.5 Ricerca Operativa 1 2 G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Interpretazione geometrica ` possibile evidenziare, mediante semplici considerazioni di E geometria analitica, la regione del piano R 2 costituita da punti che soddisfano tutti i vincoli del problema. x1 , x2 ≥ 0 quindi i p.ti ammissibili appartengono all’ortante positivo 2 x2 x1 ≥ 70/140 1 140x1 ≥ 70 20x1 + 10x2 ≥ 30 0.5 20x1 + 10x2 ≥ 30 0.5 Ricerca Operativa 1 x1 2 G. Liuzzi Introduzione Approccio modellistico Formulazione Pianificazione della produzione Problema di miscelazione Interpretazione geometrica ` possibile evidenziare, mediante semplici considerazioni di E geometria analitica, la regione del piano R 2 costituita da punti che soddisfano tutti i vincoli del problema. x1 , x2 ≥ 0 quindi i p.ti ammissibili appartengono all’ortante positivo 2 x2 x1 ≥ 70/140 1 140x1 ≥ 70 20x1 + 10x2 ≥ 30 25x1 + 50x2 ≥ 75 Ricerca Operativa 25x1 + 50x2 ≥ 75 0.5 20x1 + 10x2 ≥ 30 0.5 1 x1 2 G. Liuzzi
© Copyright 2024 ExpyDoc
