Problem Solving Matematico

Titolo: Problem

solving matematico

di Francesco Manu

1 Francesco Manu Skype: manufrancesco · http://it.linkedin.com/in/francescomanu www.francescomanu.it · [email protected]

INDICE: 1. Hai un problema? ................................................................... 3 2. Come approcciare un problema ............................................. 4 2.1. 2.2. 2.3.

Programmazione Lineare (PL) ................................................................................. 7 Teorema fondamentale della Programmazione Lineare ........................................ 8 Algoritmo di Simplesso ............................................................................................. 9

3. Problematiche aziendali reali ................................................ 9 3.1. 3.2. 3.3.

Caso: lanificio ............................................................................................................ 9 Caso: azienda telefonica.......................................................................................... 10 Caso: raffinazione materie prime............................................................................ 11

4. Bibliografia .......................................................................... 13

2 Francesco Manu Skype: manufrancesco · http://it.linkedin.com/in/francescomanu www.francescomanu.it · [email protected]

1. Hai un problema? Incognita, dubbio, incertezza, dilemma... O semplicemente "problema". Ma è così semplice risolvere questo problema? Ha una o più soluzioni?

Risolvere un problema è portare a una soluzione o un risultato che siano i migliori possibili o ipotizzabili.

Questo obiettivo, o resa, può essere associato ad un dispositivo, programma, processo produttivo o organizzazione di un'impresa. Un campo della matematica applicata, nello specifico l'analisi numerica, studia teoria e metodi per la ricerca dei punti di massimo e minimo di una funzione ottenendo così modelli matematici che traducono in termini e dati un determinato problema, cercando l'ottimizzazione e la risoluzione dello stesso. Non sempre è possibile risolvere con "Si/No" o "Fatto/Non fatto"... Ottimizzare è un'idea più diffusa di quanto ci si immagina ed è innata nel nostro modo di vivere cercando di ottenere il massimo risultato con il minimo sforzo. Ottimizzare dal punto di vista matematico: Un'istanza di un problema di ottimizzazione è rappresentata da una coppia dove è un insieme detto regione ammissibile del problema e c è una funzione definita su e a valori reali:

detta "funzione obiettivo" del problema. Lo scopo di un problema di ottimizzazione è determinare un elemento

se il problema `e di minimo, oppure un elemento

se il problema è di massimo. In entrambi i casi il punto

viene detto ottimo globale del problema, quindi la "soluzione".

3 Francesco Manu Skype: manufrancesco · http://it.linkedin.com/in/francescomanu www.francescomanu.it · [email protected]

Classe Problemi di decisione o di esistenza Problemi di ricerca Problemi di enumerazione Problemi di ottimizzazione

Descrizione Si richiede di verificare se esiste o meno una certa soluzione per l’istanza del problema Si richiede di costruire ed esibire una soluzione per l’istanza del problema Si richiede di costruire ed esibire tutte le soluzioni per l’istanza del problema Si richiede di costruire le soluzioni ottimali in base ad un determinato criterio

2. Come approcciare ad un problema Un aspetto molto particolare delle funzioni convesse sono le funzioni lineari. Se la funzione obiettivo ed i vincoli del problema di ottimizzazioni sono funzioni lineari, allora il problema di programmazione matematica che si ottiene è un problema di Programmazione Lineare (PL). Il matematico americano George Dantzig, nel 1947, osserva che se la funzione obiettivo è lineare, allora i suoi punti di minimo o di massimo si trovano sicuramente sulla frontiera avendo soluzioni ammissibili. Su questo si basa il celebre metodo per la risoluzione di problemi di programmazione lineare proposto noto come algoritmo del simplesso. L’algoritmo di Dantzig opera su di un simplesso, ossia un politopo in dimensioni con vertici (esempio: in uno spazio dimensionale , un simplesso è un tetraedro, il poliedro con il minor numero di vertici). I vincoli del problema di ottimizzazione definiscono la regione ammissibile, cioè l’insieme dei punti che soddisfano tutti i vincoli del problema. Nel caso della programmazione lineare la regione ammissibile è un politopo (un poligono nel piano, un poliedro nello spazio), che può essere vuoto (nel caso in cui non esistono soluzioni al problema), limitato o illimitato. La funzione obiettivo che deve essere minimizzata o massimizzata esplicita il “costo” per ogni soluzione tenendo conto dei vincoli (ossia calcolando la soluzione all’interno del poliedro). Con l'algoritmo del simplesso si è in grado di determinare la tipologia del poliedro e di individuare la soluzione ottima, che è, con opportune ipotesi, un vertice del poliedro, nel caso in cui il problema abbia una soluzione ottimale finita. Il problema di programmazione lineare diventa un problema di ottimizzazione combinatoria se tutte le variabili sono vincolate ad assumere soltanto valori interi. Un'azienda produttrice di profumi, con le tre essenze di rosa, mughetto e viola, riesce a realizzare due nuove fragranze. Per la realizzazione di un decalitro di fragranza "uno" sono richiesti 1,5 litri di rosa, 1 litro di mughetto e 0,3 litri di viola. Per realizzare un decalitro di fragranza "due" sono richiesti 1 litro di rosa, 1 litro di mughetto e 0,5 litri di viola. La disponibilità totale in magazzino per le tre essenze è di 27, 21 e 9 litri per rosa, mughetto e viola rispettivamente. Sapendo che l'azienda realizza un prodotto di €130 e €100 per ogni decalitro venduto di fragranza uno e due rispettivamente, determinare le quantità a ottimali delle due fragranze da produrre. 4 Francesco Manu Skype: manufrancesco · http://it.linkedin.com/in/francescomanu www.francescomanu.it · [email protected]

Un modello di programmazione matematica è composto dai seguenti elementi: - Insiemi: raggruppano gli elementi del sistema. Nell'esempio si possono individuare due insiemi, quello delle essenze e quello delle fragranze - Parametri: sono i dati stessi del problema e rappresentano delle quantità fissate che dipendono dai diversi elementi del sistema. Nell'esempio, i parametri sono i profitti, definiti per ogni fragranza (€130 per ogni decalitro di fragranza uno e €100 per decalitro di fragranza due), le disponibilità del magazzino, definite per ogni essenza (27, 21 e 9 litri per le essenze rosa, mughetto e viola), e le richieste di essenza per ogni unità a di fragranza, definite per ogni coppia essenza-fragranza (ad esempio, 1 litro di mughetto per ogni decalitro di fragranza uno, 0,5 litri di viola per ogni decalitro di fragranza due etc.). - Variabili decisionali o di controllo: sono le grandezze del sistema di cui non conosciamo il valore (assimilabili a delle incognite) e sulle quali possiamo agire per determinare diverse soluzioni alternative del problema. Nell'esempio, le variabili decisionali sono la quantità, in decalitri, delle due fragranze da produrre (che chiamiamo e ) - Vincoli: sono delle relazioni matematiche che descrivono le condizioni di ammissibilità delle soluzioni. Servono quindi per discriminare le combinazioni di valori delle variabili decisionali che rappresentano soluzioni accettabili al problema, da quelle che non lo sono. Ad esempio, tutte le soluzioni ammissibili non possono utilizzare più di 27 litri di essenza rosa, relazione esprimibile come - Funzione obiettivo: è la quantità da massimizzare (max) o minimizzare (min), espressa come funzione delle variabili decisionali. Nell'esempio si vuole massimizzare il prodotto in euro, esprimibile come La soluzione di un problema di ottimizzazione formulato con un modello di programmazione matematica consiste nella determinazione dei valori delle variabili che soddisfano tutti i vincoli e massimizzano o minimizzano il valore della funzione obiettivo. Un modello di Programmazione Lineare è un modello di programmazione matematica in cui - la funzione obiettivo è un'espressione lineare delle variabili decisionali; - i vincoli sono determinati da un sistema di equazioni e/o disequazioni lineari. In base alla natura o dominio delle variabili decisionali, si parla di - Modelli di Programmazione Lineare (in senso stretto, PL) se tutte le variabili possono assumere valori reali; - Modelli di Programmazione Lineare Intera (PLI) se tutte le variabili possono assumere valori interi; 5 Francesco Manu Skype: manufrancesco · http://it.linkedin.com/in/francescomanu www.francescomanu.it · [email protected]

- Modelli di Programmazione Lineare Intera Mista (PLIM) se alcune variabili possono assumere valori reali e altre valori interi. Il problema descritto nell'esempio può quindi essere formulato con il seguente modello di Programmazione Lineare (in senso stretto):

funzione obiettivo vincolo disponibilità Rosa vincolo disponibilità Mughetto vincolo disponibilità Viola domini delle variabili

E' conveniente esprimere i modelli in termini generali, sfruttando le opportune notazioni algebriche, in modo che lo stesso modello rappresenti una descrizione di più istanze (o casi) dello stesso problema, inteso come classe di problemi definiti allo stesso modo. Con lo scopo, una volta definiti gli insiemi e dei relativi indici, si può generalizzare la definizione dei parametri e delle variabili e, quindi, della funzione obiettivo e dei vincoli. Nell'esempio, potremmo definire il problema dell'ottimizzazione della produzione dove si vuole determinare la quantità di prodotti per massimizzare i profitti, sotto vincoli legati alla disponibilità di risorse. Indicando con:

il modello per il problema (generale) si può formulare come segue:

6 Francesco Manu Skype: manufrancesco · http://it.linkedin.com/in/francescomanu www.francescomanu.it · [email protected]

L'istanza descritta nell'esempio è ottenuta ponendo , e fissando gli opportuni valori dei parametri , e . Fissando insiemi e/o parametri ad altri valori si ottengono diverse istanze dello stesso problema per le quali il modello continua a essere valido.

2.1.

Programmazione Lineare, PL

Il metodo del simplesso è un algoritmo generale per la risoluzione di problemi di programmazione lineare. La sua rilevanza, oltre che storica, anche dal punto di vista applicativo, è fondata proprio sulla generalità dell’approccio, piuttosto che sulla sua efficienza: l’algoritmo del simplesso permette di risolvere qualsiasi problema di ottimizzazione formulato come problema di programmazione lineare, anche se computazionalmente è piuttosto pesante. Possiamo riformulare un problema di programmazione lineare partendo dall’espressione classica, formalizzandolo come segue: data una matrice e i vettori colonna , , si chiede di trovare un vettore colonna sia minimo (problema in forma di minimizzazione). Naturalmente il vettore rappresenta il “costo” associato a ciascuna variabile della soluzione del problema (o il “profitto”, nel caso di problemi in forma di massimizzazione) e la funzione obiettivo è espressa quindi come . La matrice è la matrice dei coefficienti delle disequazioni lineari con cui viene definito l’insieme delle soluzioni ammissibili del problema. L’espressione può così essere riformulata come segue:

L’insieme di disequazioni lineari definisce un poliedro come intersezione dei semispazi definiti da ciascuna disequazione. È all’interno di che sono da ricercare le soluzioni ottime del problema, tra tutte le soluzioni ammissibili. Esistono due casi degeneri per un problema di programmazione lineare: il caso in cui il problema non ammette nessuna soluzione, quando cioè i vincoli producono un poliedro nullo, , o il caso in cui il problema ammette infinite soluzioni, quando il poliedro è illimitato. Quando il problema di programmazione lineare è ben posto e dunque non è né nullo, né illimitato, diremo che è un politopo. Un simplesso, il termine che dà il nome all’algoritmo di Dantzig, è un politopo di vertici in n dimensioni: un segmento in dimensione 1, un triangolo in dimensione 2 e un tetraedro in dimensione 3. Cerchiamo di formalizzare meglio questi concetti. Innanzi tutto chiamiamo vertice di un poliedro un punto tale che non esistono altri due punti con e . Non tutti i poliedri ottenuti come intersezioni di semispazi definiti mediante disequazioni lineari hanno almeno un vertice. Ad esempio se consideriamo un unico semispazio di , questo non ha vertici. Dunque il poliedro non ha vertici se la matrice ha un numero di 7 Francesco Manu Skype: manufrancesco · http://it.linkedin.com/in/francescomanu www.francescomanu.it · [email protected]

righe minore di n: in tal caso non è possibile trovare n vincoli linearmente indipendenti che circoscrivano un poliedro chiuso. Un poliedro non ha vertici se contiene rette: diremo che un poliedro esiste un punto e un vettore non nullo

2.2.

contiene una retta se .

Teorema fondamentale della Programmazione Lineare

Supponiamo che il poliedro seguenti tre affermazioni è vera:

non contenga rette. Allora una e una sola delle

L’algoritmo del simplesso non consiste altro che in una “visita intelligente” dei vertici di ; il teorema fondamentale della programmazione lineare garantisce infatti che la soluzione ottimale del problema, se esiste, è situata in uno di questi vertici. Muovendosi sugli spigoli del poliedro, da un vertice ad un altro, il metodo del simplesso cerca di individuare una soluzione ottima, che massimizzi o minimizzi la funzione obiettivo. Consideriamo la matrice se è un insieme di indici di riga di , indichiamo con la sottomarine di composta con le sole righe in ; analogamente se è un vettore, indichiamo con il sottovettore composto dalle sole componenti di indice in . Indichiamo con la riga e con . Utilizzando queste notazioni formalizziamo il Metodo del Simplesso con lo pseudo codice dell’Algoritmo. È possibile dimostrare che l’Algoritmo del Simplesso termina al massimo dopo iterazioni del ciclo 2–13. Se l’algoritmo restituisce e al passo 4, allora e sono i vettori che rappresentano le soluzioni ottime per i seguenti problemi di programmazione lineare, con :

Infine, se l’algoritmo restituisce il vettore programmazione lineare è illimitato.

al passo 9, allora

8 Francesco Manu Skype: manufrancesco · http://it.linkedin.com/in/francescomanu www.francescomanu.it · [email protected]

e il problema di

Il problema di programmazione lineare espresso da viene chiamato problema primale, mentre il problema di programmazione lineare , associato al precedente, viene chiamato problema duale.

2.3.

Algoritmo di Simplesso

INPUT: Una matrice di coefficienti , un vertice

, il vettore dei termini noti

OUTPUT: Un vertice (il poliedro è illimitato)

, oppure un vettore

, il vettore dei costi con

e

3. Problematiche aziendali reali

3.1.

Caso: Lanificio

Un lanificio produce filato di tipo standard e di tipo speciale utilizzando 3 diverse macchine, le cui produzioni orarie sono le seguenti: Macchina A: 3 matasse standard e 1 speciale Macchina B: 2 matasse standard e 2 speciali Macchina C: 2 matasse standard e 1 speciale

9 Francesco Manu Skype: manufrancesco · http://it.linkedin.com/in/francescomanu www.francescomanu.it · [email protected]

Il mercato richiede almeno 60 matasse standard e 40 di tipo speciale al giorno. I costi orari delle due macchine sono: €90 euro per la A, €80 per B, €60 per C. Determinare la produzione giornaliera di costo minimo. (Non occorre imporre il vincolo che le ore giornaliere non superino 24)

Svolgimento: Durante un’ora di funzionamento, ciascuna macchina, se attiva, ha una produzione fissa di matasse, indicata prima. Dunque, il problema non riguarda decidere cosa produrre, bensì per quanto tempo tenere in funzione le tre macchine. Dunque, le variabili di decisione sono , , , pari alle ore di funzionamento delle tre macchine. Considerando che ogni ora di Macchina A costa € 90, e produce 3 matasse standard e una speciale, avremo dunque che il contributo alla funzione obiettivo sarà 90 , mentre il contributo al soddisfacimento della domanda dei due tipi di matasse sarà rispettivamente 3 e . Ripetendo il discorso anche per le altre due macchine, otteniamo la formulazione

3.2.

Caso: Azienda telefonica

Un'azienda di telefonia mobile deve installare delle antenne per la copertura di sei zone sul territorio. Sono stati individuati cinque siti possibili per l'installazione delle antenne. In seguito a delle simulazioni, è stato possibile determinare il livello del segnale captato nelle diverse zone e proveniente da un'antenna installata nei vari siti. Tali livelli sono riportati nella seguente tabella:

Sito A Sito B Sito C Sito D Sito E

Zona 1

Zona 2

Zona 3

Zona 4

Zona 5

Zona 6

10 0 21 16 21

20 12 8 15 13

16 18 5 15 17

25 23 6 8 17

0 11 23 14 18

10 6 19 18 22

I ricevitori sono sensibili ai segnali di livello almeno 18. Inoltre, non è possibile avere più di un segnale sopra la soglia in una stessa zona, altrimenti il segnale risulterebbe disturbato e il ricevitore non riuscirebbe a sintonizzarsi. Infine, l'installazione di un'antenna nel sito E è subordinata all'installazione di un'antenna nel sito D, che faccia da ponte. L'azienda di telefonia vuole determinare dove installare le antenne per coprire il maggior numero di zone. 10 Francesco Manu Skype: manufrancesco · http://it.linkedin.com/in/francescomanu www.francescomanu.it · [email protected]

Svolgimento:

Una possibile formulazione, dove:

3.3.

Caso: Raffinazione materie prime

Il prodotto finale di una fabbrica è ottenuto raffinando materie prime grezze e miscelandole insieme. Queste materie prime possono essere di due categorie: naturali e sintetizzate. In particolare, sono disponibili tre materie prime naturali e due materie prime sintetizzate . Le materie prime naturali e quelle sintetizzate richiedono differenti linee di produzione. Ogni settimana è possibile raffinare non più di 500 quintali di materie prime naturali e non più di 300 quintali di materie prime sintetizzate. Si assume che non ci sia perdita di peso durante la raffinazione e che si possa trascurare il costo di raffinazione. Inoltre esiste una restrizione tecnologica sulla gradazione del prodotto finale: nell’unità di misura in cui questa gradazione è misurata, essa deve essere tra 2 e 7; si assume che tale gradazione nella miscela finale dipenda linearmente dalle singole gradazioni delle materie prime componenti. Nella tabella che segue è riportato il costo (in migliaia di euro) per quintale e la gradazione delle materie prime grezze. 11 Francesco Manu Skype: manufrancesco · http://it.linkedin.com/in/francescomanu www.francescomanu.it · [email protected]

Costo Grad.

300 6.0

190 1.9

250 8.5

200 5.0

230 3.5

Il prodotto finale viene venduto a 350 mila euro per quintale. Determinare come va pianificata la produzione settimanale per massimizzare il profitto netto.

Svolgimento: - Variabili: introduciamo le variabili di decisione rappresentanti le quantità (in quintali) di che devono essere comprate e raffinate in una settimana. Inoltre introduciamo una ulteriore variabile che indica la quantità di prodotto finale che deve essere fabbricato. - Funzioni obiettivo: la funzione obiettivo da massimizzare sarà data dal profitto netto cioè da

- Vincoli: sono presenti tre tipi di vincoli - capacità di raffinamento

- limitazioni sulla gradazione

- vincolo di continuità

Questo vincolo di continuità esprime il fatto che il peso finale del prodotto deve essere uguale alla somma dei pesi degli ingredienti. Inoltre si devono esplicitare i vincoli di non negatività delle variabili.

12 Francesco Manu Skype: manufrancesco · http://it.linkedin.com/in/francescomanu www.francescomanu.it · [email protected]

La formulazione finale risulta quindi:

4. Bibliografia       

Aleksander Schrijver - Theory of Linear and Integer Programming, J.Wiley Evgenij S. Levitin - Perturbation Theory in Mathematical Programming and its Applications, J.Wiley, L. De Giovanni - Metodi e Modelli per l'Ottimizzazione Combinatoria F. Maffioli “Elementi di Programmazione Matematica" Ricerca operativa Ingegneria Gestionale - prof. Roma, prof. Lucidi, prof. Facchinei, prof.ssa Palagi Marco Liverani, Qual è il problema? Metodi, strategie risolutive, algoritmi, Mimesis Antonio Sassano, Modelli e algoritmi della Ricerca Operativa, Franco Angeli

13 Francesco Manu Skype: manufrancesco · http://it.linkedin.com/in/francescomanu www.francescomanu.it · [email protected]