![2
Introduzione il problema della dieta
Alimento (x) Costo unitario Quantit massima Calorie Proteine Calcio
Pane (x1) 2 4 110 4 2
Latte (x2) 3 8 160 8 285
Uova (x3) 4 3 180 13 54
Carne (x4) 19 2 260 14 80
Dolce (x5) 20 2 420 4 22
Nutrimento Requisito
Calorie [cal] 200
Proteine [g] 50
Calcio [700 g] 700
Gabba Marco](https://image.slidesharecdn.com/gabba2011-13264525466394-phpapp01-120113050430-phpapp01/85/Gabba-2011-2-320.jpg)
Gabba 2011
- 1. Gabba Marco 750228 Programmazione Lineare - Confronti tra metodi esistenti e un metodo innovativo Relatore: Prof. Guido Buzzi Ferraris Correlatore: Ing. Flavio Manenti
- 2. 2 Introduzione il problema della dieta Alimento (x) Costo unitario Quantit massima Calorie Proteine Calcio Pane (x1) 2 4 110 4 2 Latte (x2) 3 8 160 8 285 Uova (x3) 4 3 180 13 54 Carne (x4) 19 2 260 14 80 Dolce (x5) 20 2 420 4 22 Nutrimento Requisito Calorie [cal] 200 Proteine [g] 50 Calcio [700 g] 700 Gabba Marco
- 3. 3 Introduzione il problema della dieta minimizzare 2 x1 3x2 4 x3 19 x4 20 x5 soggetta a: x1 4; x2 8; x3 3; x4 2; x5 2; 110 x1 160 x2 180 x3 260 x4 420 x5 200; 4 x1 8 x2 13x3 14 x4 4 x5 50; 2 x1 285 x2 54 x3 80 x4 22 x5 700; Costo 38.222 Costo 40 Alimento Quantit Alimento Quantit Pane 4 Pane 4 MILP Latte 8 Latte 8 Uova 1.5556 Uova 2 Carne 0 Carne 0 Dolce 0 Dolce 0 Gabba Marco
- 4. 4 Scopo del lavoro Confrontare le prestazioni del metodo dellAttico con quelle dei risolutori commerciali disponibili al fine di verificare lefficienza del metodo ed affinare le prestazioni, per valutare la possibilit di una futura applicazione ai problemi MILP Gabba Marco
- 5. Caso Studio 5 Ottimizzazione di una raffineria Gabba Marco
- 6. Caso Studio 6 Ottimizzazione di una raffineria Modello matematico Tipologie di variabili (61) Quantit di materiale straight-run e di riciclo alimentato ai forni. Componenti dei vari prodotti di miscelazione. Variabili di bilancio Tipologie di vincoli (26) Disponibilit e utilizzo di materie prime, prodotti straight- run e prodotti di cracking. Limitazioni di capacit delle apparecchiature Specifiche richieste sui prodotti di miscelazione Gabba Marco
- 7. Simplesso 7 minimizzare 2 x1 x2 minimizzare 2 x1 x2 8 8 soggetta a x1 x2 4 soggetta a x1 x2 x3 4 3 3 x1 x2 2 x1 x2 x4 2 2 x1 3 2 x1 +x 5 3 x0 x0 Gabba Marco
- 8. Interior Point 8 Klee - Minty n massimizzare 10 j 1 n j xj i 1 soggetta a: 210i j x j xi 100i j i 1,..., n j 1 xj 0 j 1,..., n Barrier Method n minimizzare c x-亮 logx j T T minimizzare c x Ax b j=1 soggetta a soggetta a Ax b x0 x0 Gabba Marco
- 9. Attico 9 ATTIC METHOD x2 BAttic BAttic Di solito si incontra un punto non vertice, DEGENERACY prevenendo problemi di degenerazione CSimplex SIMPLEX METHOD BSimplex A dmax CSimplex BSimplex x1 A Gabba Marco
- 10. Attico 10 Basi matematiche Condizioni di Karush, Kuhn, Tucker J T 了 s Jx b i 0 i 1,..., nQ Vincoli artificiali Fattorizzazione avanzata Vertici dellAttico Gabba Marco
- 11. Caso Studio 11 Linguaggi e solvers utilizzati AMPL SIMPO CPLEX MINOS 5.5 Gabba Marco
- 12. Caso Studio 12 Linguaggi e solvers utilizzati MATLAB Simplesso IP Gabba Marco
- 13. Caso Studio 13 Linguaggi e solvers utilizzati C++ Simplesso Attico Gabba Marco
- 14. Caso Studio 14 Ottimizzazione di una raffineria Gabba Marco
- 15. Ulteriore confronto 15 FIT1D Test della libreria Netlib/LP Dimensioni: 1026 variabili, 24 vincoli Confronto prestazioni 1200 1069 1000 800 N属 iterazioni SIMPO 600 CPLEX Attico 400 200 87 53 0 Gabba Marco
- 16. 16 Conclusioni Spostamenti allinterno dellarea accettabile con tecniche lineari: valutazione di meno vertici. Non richiesta forma standard: matrici pi湛 piccole Fattorizzazione stabile grazie ai vincoli artificiali TO DO Test sui tempi di calcolo (parametro industriale) Sviluppo algoritmo (pre-processore) Convalida su problema di supply chain management, 430000 variabili circa (prof. Bandoni, Plapiqui, UNS) Gabba Marco
- 17. 17 GRAZIE PER LATTENZIONE! Gabba Marco
- 18. Applicazioni Pratiche 18 MILP minimizzare 2 x1 3 y1 2 y2 3 y3 soggetta a x1 y1 y2 y3 2 10 x1 5 y1 3 y2 4 y3 0 x1 0 y1 , y2 , y3 0,1 Gabba Marco