Ottimizzazione

Università della Calabria

Dipartimento di ingegneria meccanica, energetica e gestionale

Appunti del corso di ottimizzazione

Piofrancesco Barone

Prof.ssa Maria Elena Bruni

Ingegneria energetica

A.A. 2020/2021

Ottobre Pagina 16

Ottobre 2020 (prof.ssa Bruni)

Martedì 6 ottobre 2020 11:30

Prof.ssa Maria Elena Bruni

Ufficio: Cube 41C, piano 8

Email: mariaelena.bruni@unical.it

Introduction

Course goals and project plan

• Understand main concepts and applications of formulating and solving business decision-making problems by utilizing quantitative analysis and quantitative methods
• Develop essential skills of analyzing and solving quantitative models with a computer software used in business
• Apply specific quantitative models and tools in various functional areas
• Search in the literature (that is, on the Internet) for formulations, solution algorithms for simplified problem
• Model the problem and recognize possible similar problems
• Formulate (mathematically) the problem
• Design solution algorithms
• Test experimentally

Soft skills: interpretare, conoscere, implementare e analizzare dei modelli di ottimizzazione. Si parlerà di come risolvere dei problemi complessi utilizzando dei modelli matematici.

Course material

• Supplementary Articles: will be indicated during the course
• Slides
• Class exercises (participatory discussion)

What is a mathematical model?

Okay, some quotes from Wikipedia:

• A mathematical model is a description of a system using mathematical concepts and language. The process of developing a mathematical model is termed mathematical modeling.

Hypothesis

• Mapping real-world entities/mechanisms/phenomenon to mathematical abstractions. (e.g. interaction in Newton’s theory)
• Developing the model with mathematical theories/tools

Advantages of computational modeling

• Drives conceptual clarification
• Highlights gaps in knowledge or understanding: during model formulation unspecified components or interactions must be determined
• Time and space may be stretched or compressed ad libitum
• Modeling is cheap compared to experiments
• Models do not harm! Helping to reduce ethical problems in experiments and pollution
• Modeling can assist experimentation: – test different conditions not accessible by experiment – Impose perturbations not feasible in the real system
• Make well-founded and testable predictions

Question: How should be a good mathematical model?

• Reasonable: reasonable mapping between the real and the math
• Mathematically sound/rigorous
• Generalizable: working on a general framework rather than too specific
• Simple: choose the simplest one that can solve your problem!
• Verifiable: how do you know your model is not wrong?

Esame: parte metodologica con prove intermedie scritte Valutazione delle soft skills con prova orale, progetto o decisioni prese dalla professoressa.

Common pitfalls

You are probably doing it wrong if you have any of these feelings:

• The model is not a math model at all!
• The model and solution are unrelated!
• The model is too complex or you do not know how to solve.

The modeling process

...is a series of steps taken to convert an idea first into a conceptual model and then into a quantitative model

• Get the system picture clearly in mind.
• Define the processes to be treated and the boundaries of the model.
• Write down the laws and the functions to be used.
• Put down very clearly the restrictive assumptions made.
• Write down initial and boundary conditions.
• Verify, validate the mathematical model.

Types of mathematical models

• Deterministic vs. Stochastic models
• Static vs. Dynamic Models
• Continuous vs. Discrete Models
• Mechanistic vs. Statistical Models

Mathematical models are used in:

• The natural sciences (such as physics, biology, earth science, meteorology)
• Engineering disciplines (e.g. computer science, artificial intelligence)
• Social sciences (such as economics, psychology, sociology, and political science)

I modelli di ottimizzazione sono dei modelli matematici addizionati a decisioni da prendere.

Optimization models

• Mathematical models designed to help institutions and individuals decide how to allocate scarce resources to activities.
• More generally, mathematical models designed to help us make “better” decisions.

Several other possible definitions:

Optimization models attempt to capture some key components to build a reasonable replica of the real situation and provide a systematic, quantitative way to evaluate and select decisions.

This is Operations Research!

• World War II led to the birth of OR: Scientists and engineers used mathematical tools to deploy, manage, and analyze military operations, e.g., deployment of the radar management of convoy and submarine operations
• Many important developments took place in this period. Most notably George Dantzig invented the simplex method for solving linear programs (LPs) in 1947
• After the War: Industrial boom led to a rapid increase in the size of corporations – growing need for systematic decision-making tools. Managers began to realize both, the modeling power of OR tools, and their potential to improve efficiency even under existing technology

Where is OR today?

• Immense computing power available readily and fairly cheaply, e.g., PCs
• Very good theoretical understanding
• Various software packages, e.g., CPLEX, LINDO, XPRESS-MP, being available that can be used “off-the-shelf”

Answer: OR is everywhere – from booking an airline ticket to checking into your hotel

Survey of real-world problems

• Production planning: Lo scheduling “dipende” dal tempo (impostare degli orari
• Sequencing rispetto a una serie di processi).
• Man power planning: Definisce l’istante di fine e l’istante di inizio delle attività.
• Scheduling: Lo scheduling contiene in se’ il sequenziamento.
• Allocation
• Distribution and logistics: Logistica = organizzazione dei processi che seguono un prodotto dall’inizio fino alla fine.
• Blending
• Selection and depot location: E’ la scienza che studia il flusso di materiali, servizi e persone che porta all’erogazione di un prodotto finale.
• Investment / de-investment
• Network design
• Financial optimization

What kind of decisions?

Any kind really... but here are some examples:

• How many cars to produce?
• What radiation intensity to use in cancer treatment?
• How many outpatients to schedule every day?
• Whether to start a new project?
• Whether to buy a stock?
• Which retirement plan to choose?
• How many medical service centers to open?
• Where, what, and how much supplies to stock in storage?
• How many nurses to employ?
• How to schedule flights?
• How to route traffic?
• How to respond to a natural disaster?

Modello matematico di ottimizzazione, modello di ottimizzazione e modello di programmazione matematica sono tutti sinonimi.

Variabili, vincoli e funzione obiettivo sono delle entità matematiche che derivano dal processo di astrazione e mappano quindi la realtà.

Le variabili sono la rappresentazione matematica le grandezze decisionali del nostro problema decisionale.

È una mappatura matematica della decisione da prendere. Potremmo avere molte decisioni da prendere, anche in modo interconnesso tra loro.

I vincoli definiscono il funzionamento e i limiti del nostro sistema.

La funzione obiettivo è ciò che vogliamo massimizzare o minimizzare nel nostro problema.

La soluzione di ottimo assoluto non sempre esiste, basti pensare al fatto che la ricerca operativa si basa su astrazioni a partire da ipotesi (anche) semplificative.

Possiamo avere una sola funzione obiettivo (funzione obiettivo scalare) o tante (funzione obiettivo vettoriale) e si parlerà quindi di problema di ottimizzazione a singolo obiettivo o multiobiettivo.

L'ottimalità della nostra soluzione è una decisione che è ammissibile per il nostro problema, in quanto nerispetta i vincoli.

L'Ottimalità è data in riferimento alla nostra funzione obiettivo. Una soluzione migliore dell'ottima (rispetto alla nostra funzione obiettivo) non esiste.

Se la soluzione non dovesse essere ammissibile, significherebbe che non è fisicamente realizzabile.

Una volta che abbiamo definito variabili, vincoli e funzioni obiettivo, per ottenere la soluzione di ottimo o comunque una ammissibile, abbiamo bisogno di strumenti risolutivi (=algoritmi) che risolvano il nostro problema.

Tali algoritmi sono diversificati in base al problema trattato: Linear problem, LP- Mixed integer linear problem, MILP- Non linear problem, NLP- Mixed integer non linear problem, MINLP-

L'elevata dimensionalità di un problema non ci permetterà di trovare la soluzione ottimale per dei limiti prettamente computazionale.

Non sempre è possibile acquisire dei dati. Ci sono dei dati che non sono estraibili in modo semplice, e soprattutto senza errori.

Optimization building blocks

• Data (Actual Situation and Requirements, Control Parameters) e.g., number of sites, unit capacities, demand forecasts, available resources
• Model (variables, constraints, objective function) e.g., how much to produce, how much to ship, (decision variables, unknowns) e.g., mass balances, network flow preservation, capacity constraints
• Optimization algorithm and solver e.g., simplex algorithm, B&B algorithm, SQP, outer approximation...

Ottobre Pagina 57

7 Ottobre 2020 (prof.ssa Bruni)

Mercoledì 7 ottobre 2020 16:30

Problemi di programmazione lineare

Mathematical programming is used to find the best or optimal solution to a problem that requires a decision or set of decisions about how best to use a set of limited resources to achieve a state goal of objectives.

Steps involved in mathematical programming:

• Conversion of stated problem into a mathematical model that abstracts all the essential elements of the problem.
• Exploration of different solutions of the problem.
• Finding out the most suitable or optimum solution.
• Linear programming requires that all the mathematical functions in the model be linear functions.

I modelli di programmazione lineare sono modelli di programmazione matematica in cui i vincoli e la funzione obiettivo sono funzioni lineari del vettore delle variabili.

Ovviamente non è l'unica possibilità: potrebbe capitare, ad esempio, che le variabili siano legate tra loro da legami non lineari. Se questo fosse il caso, parleremmo di modelli di programmazione non lineare.

Sappiamo che le variabili sono una mappatura di entità fisiche in un linguaggio matematico. Sono anche delle entità matematiche che vengono utilizzate per esprimere le decisioni, per rappresentare le decisioni che dobbiamo prendere all'interno del nostro problema di ottimizzazione.

Consideriamo x₁,...,x_n decisioni (=e quindi n variabili di decisione), rappresentate dal vettore x. Le variabili decisionali x₁,..., x_n rappresentano matematicamente le decisioni che vogliamo prendere in modo ottimo. Sono variabili scalari. La funzione obiettivo z è una funzione che lega le variabili decisionali tra loro.

Poiché stiamo trattando un modello di programmazione lineare, allora, tali variabili saranno legate tra loro in modo lineare.

Avremo dunque una combinazione lineare di variabili con pesi dati dal vettore C.

Abbiamo detto che la funzione obiettivo z è quindi scritta come combinazione lineare delle variabili decisionali con relativi pesi, la quale non è altro che il prodotto scalare tra i due vettori X e C, dove X e C devono essere ovviamente isodimensionali (entrambi stanno in Rⁿ).

Il prodotto scalare si indicherà con C^T X (T=trasposto), infatti C^T è un vettore riga, mentre X è un vettore colonna.

I vincoli possono essere espressi in forma estesa oppure in una forma compatta (=matriciale). Osserviamo che possiamo avere un insieme di m vincoli diversi. Di conseguenza, il vettore B dei termini noti avrà proprio dimensione m.

I coefficienti a_ij possono essere immagazzinati in una matrice di m righe ed n colonne chiamata matrice dei coefficienti tecnologici. Il doppio pedice indica la riga e la colonna a cui quel coefficiente si riferisce. Il pedice di colonna corrisponde anche al pedice associato alla variabile. Ad esempio, a₁₁ indica l'elemento in prima riga associato alla variabile x₁, e quindi alla prima colonna. Infatti, la generica variabile x_j sarà contenuta nella j-esima colonna.

Notiamo che possiamo avere, oltre a dei vincoli di disuguaglianza lineari, anche dei vincoli di non negatività delle variabili.

Ottobre Pagina 6

Volendo dare una forma leggermente meno estesa al modello di programmazione lineare, lo stesso modello che abbiamo visto prima può essere espresso utilizzando l'operatore di somma.

La combinazione lineare delle variabili x con pedice c può dunque essere scritta anche come una sommatoria di questo tipo: Abbiamo m vincoli. Con i indichiamo i vincoli, che scorrono da 1 a m. Ricordiamo che m è la dimensione del vettore dei termini noti B. Avremo tanti vincoli quant'è la dimensione del vettore B.

The decision variables, x₁, x₂, ..., x_n, represent levels of n competing activities. Supponiamo di avere tale problema di massimizzazione. La nostra azienda produce un certo numero di ciotole e tazze. Abbiamo i valori delle ore di lavoro e di argilla richieste per produrre una singola ciotola o una singola tazza. Materie prime e manodopera non sono ovviamente illimitate: sappiamo infatti che i problemi di ottimizzazione nascono per la scarsità di risorse, in questo caso rappresentate dai suddetti prodotti. L'azienda vuole massimizzare i profitti. Conosciamo inoltre i profitti unitari associati alla vendita di ciascun prodotto.

Massimizzare i profitti significa massimizzare i profitti derivanti dalla vendita del mix produttivo che l'azienda decide di produrre. A questo punto, possiamo intuire quali siano le decisioni da prendere e quindi come rappresentarle attraverso le variabili decisionali.

Ottobre Pagina 7

Vogliamo trovare i valori di x₁ e x₂ che ottimizzino il problema e che quindi, di fatto, lo massimizzino. Se non avessimo vincoli, sarebbe normale produrre all'infinito. Il problema è che abbiamo sempre risorse limitate, quindi dobbiamo stare sotto il livello minimo delle stesse. Ovviamente ci saranno dei limiti di non negatività perché la produzione deve essere positiva (=senso fisico). Le disequazioni rappresentano dei semipiani che possono essere individuati sul piano cartesiano. In particolare, x₁,x₂>=0 individuano il primo quadrante. Dall'intersezione delle condizioni vincolari, otterremo l'insieme di ammissibilità del problema, il quale può anche non esistere (=insieme vuoto). L'insieme di ammissibilità è l'insieme dei punti che soddisfano tutti i vincoli del problema. Nel nostro caso, abbiamo un insieme di ammissibilità che è dato dall'intersezione

A feasible solution does not violate any of the constraints:

Example:

x₁ = 5 bowls; x₂ = 10 mugs

Z = $40x₁ + $50x₂ = $700

Labor constraint check: 1(5) + 2(10) = 25 < 40 hours, within constraint

Clay constraint check: 4(5) + 3(10) = 50 < 120 pounds, within constraint

Ottobre Pagina 8

Tra questi infiniti punti, come facciamo a scegliere quello ottimale? Consideriamo innanzitutto il primo quadrante. Per definire i semipiani, e dunque le condizioni di vincolo, iniziamo col disegnare le rette che li rappresentano. Basterà individuare due punti sugli assi e tracciare la retta passante per tali due punti. N.B. Potrebbe capitare che la retta passi per l'origine, quindi basterà individuare il suo coefficiente angolare. Per capire quale semipiano scegliere, è sufficiente sostituire le coordinate di un punto all'interno della disequazione della retta: se è verificata, allora quel punto appartiene a quel determinato semipiano. Intersecando i due semipiani, otteniamo l'insieme di ammissibilità del nostro problema:

Ottobre Pagina 9

Non possiamo trovare soluzioni ottime al di fuori dell'area rossa perché una soluzione ottima deve innanzitutto essere ammissibile. Per punto di ottimo si intende che: Dato un certo x*, non esiste alcun altro x’ che abbia il valore di funzione obiettivo strettamente maggiore (=in quanto stiamo massimizzando) di quello di x*. Quindi z(x*)>=z(x’). Sulla scorta di quanto detto, possiamo avere più di una soluzione ottima. Teoricamente parlando, possiamo avere infinite soluzioni ottime, in quanto sono definite dalla linea di isoprofitto. Noi stiamo cercando la linea di isoprofitto ottimale (ovvero quello più grande possibile in relazione ai vincoli che abbiamo). Stiamo supponendo che x₁ e x₂ siano variabili reali (di fatto continue). Ovviamente, il numero di ciotole e di tazze dovrebbe essere intero. Nei nostri problemi assumiamo comunque variabili decisionali continue per semplicità. Su tale ipotesi, avremo infinite soluzioni ottimali. Se considerassimo le variabili intere, potrebbe esserci addirittura solo un’unica soluzione (in base a come è definita).