Post on 19-Jan-2016
description
transcript
La Programmazione Lineare
Un Esempio
Il ProblemaIl caseificio “Fior di Latte” produce due tipi di formaggio: i formaggi A e B. L’azienda casearia deve decidere quante tonnellate produrre di ciascun tipo di formaggio.
L’azienda trasforma esclusivamente il latte proveniente da alcune stalle della zona che possono garantire ogni anno 2880 tonnellate di latte.
Da un punto di vista della trasformazione, i due formaggi si differenziano per la quantità di latte e per il lavoro necessari alla produzione di un’unità di prodotto trasformato.
Infatti per produrre 1 tonn. di formaggio A sono necessari 12 tonn. di latte e 9 ore di lavoro; mentre, per produrre 1 tonn. di formaggio B servono 16 tonn. di latte e 6 ore di lavoro.
Il caseificio ha una capacità massima di 200 tonnellate di formaggio. Le ore di lavoro disponibili sono 1566.
Il profitto che può ricevere il caseificio dalla vendita del formaggio è pari a 350 euro per il formaggio A e 300 euro per il formaggio B.
La domanda è: quanto formaggio A e B deve produrre il caseificio per poter ottenere il massimo profitto?
Economia delle Supply Chain
I problemi di scelta
In qualsiasi contesto economico dove le risorse da utilizzare sono disponibili in quantità limitata, si pone un problema di scelta della quantità e combinazioni di fattori da impiegare per ottenere il migliore risultato possibile.
Ad esempio, l’attività imprenditoriale ha come motivazione principale la continuità della propria impresa e la remunerazione dei fattori della produzione. L’imprenditore compie la sua attività di organizzazione al fine di individuare quella combinazione di fattori in grado di fornire il profitto più elevato.
Nel campo della logistica dei trasporti, l’obiettivo è trovare la strada più breve per raggiungere un certo luogo o il sistema di trasporto delle merci che riesca a minimizzare i costi dell’impresa.
Economia delle Supply Chain
La formulazione del problema
Per risolvere ogni tipo di problema di programmazione lineare, prima di tutto bisogna cercare di formularlo in termini algebrici seguendo queste regole:
1. Comprendere il problema;
2. Identificare le variabili di decisione;
3. Individuare la funzione obiettivo come combinazione lineare delle variabili decisionali;
4. Formulare i vincoli del problema come combinazione lineare delle variabili di decisione.
Economia delle Supply Chain
Comprendere il problema
Prima di cimentarsi con la formulazione matematica di ogni problema è fondamentale soffermarsi sul contesto in cui dovremo sviluppare un modello di programmazione matematica e domandarci:
1) Qual è l’obiettivo a cui dovremmo rispondere attraverso lo sviluppo di un modello di programmazione matematica?
2) Esistono delle variabili decisionali che possono influenzare l’obiettivo?
3) Quali sono i fattori o le risorse disponibili impiegati nel processo di trasformazione tecnico-economica?
4) Quali sono i tempi richiesti per dare un supporto al processo decisionale?
5) E’ realmente necessario sviluppare un modello di programmazione matematica?
Economia delle Supply Chain
Identificare le variabili decisionali
Se abbiamo compreso i termini del problema, allora possiamo individuare le variabili decisionali, cioè quelle grandezze che attraverso l’uso delle risorse disponibili in quantità limitata determinano i risultati del problema. Le variabili sono quegli elementi del problema che devono essere calcolati in modo da ottenere il miglior risultato possibile.
Solitamente le variabili di un problema di PL sono individuate dalle lettere X1, X2, X3, … , Xn
Nel nostro esempio, le variabili decisionali sono implicite nella domanda finale: quante tonnellate di formaggio A e B bisogna produrre per ottenere il massimo profitto?
Le variabili sono:
Formaggio A X1
Formaggio B X2
Variabili decisionali del problema di PL
Economia delle Supply Chain
La Funzione Obiettivo
Dopo aver individuato le variabili decisionali del problema, bisogna formulare in termini matematici l’obiettivo che ci poniamo attraverso la costruzione e risoluzione di un problema di PL. Domanda: cosa deve essere massimizzato/minimizzato? La funzione obiettivo rappresenta in termini algebrici l’obiettivo di chi vuole ottimizzare una certa situazione attraverso un modello di PL.
Nel nostro esempio la funzione obiettivo è data dalla massimizzazione del profitto totale del caseificio, vale a dire:
Profitto Totale = 350 X1 + 300 X2
Obiettivo= massimizzare (max) il Profitto Totale
Funzione Obiettivo = max Profitto Totale = max 350 X1 + 300 X2
Economia delle Supply Chain
I Vincoli
In ogni problema di scelta esistono dei limiti ai valori che possono assumere le variabili decisionali. In particolare, in ogni problema di PL bisogna tener conto dei fattori limitanti, ovvero delle risorse disponibili in quantità limitata. Inoltre, in molti problemi di scelta è necessario considerare i vincoli tecnologici, ovvero i legami esistenti tra variabili e tra le variabili e i fattori limitanti.Nel problema di PL assunto come esempio possiamo individuare 3 vincoli principali.
I vincolo. La capacità del caseificio
Ogni anno il caseificio può contenere sino ad un massimo di 200 tonnellate di formaggio. Quindi:
X1 + X2 ≤ 200
La quantità prodotta del formaggio A sommata alla quantità del formaggio B non può superare le 200 tonnellate prodotte.
Economia delle Supply Chain
I Vincoli
II vincolo. Il vincolo tecnologico di disponibilità di latte
Il caseificio utilizza il latte di alcuni allevatori per produrre i due tipi di formaggi, cioè:
12X1 + 16X2 ≤ 2880
Per produrre un’unità (tonnellata) di formaggio A occorrono 12 tonnellate di latte; mentre per produrre il formaggio B occorrono 16 tonnellate di latte. La quantità di latte che può entrare nel ciclo produttivo ogni anno è pari a 2880 tonnellate di latte.
III vincolo. Il vincolo della disponibilità di lavoro
L’ammontare massimo di ore che possono essere destinate all’attività di trasformazione costituisce un ulteriore vincolo al problema. Infatti:
9X1 + 6X2 ≤ 1566
Sono 9 le ore che devono essere destinate alla produzione di 1 t. di formaggio A e 6 quelle necessarie alla produzione del formaggio B.
Economia delle Supply Chain
I Vincoli
Infine, per dare coerenza alle soluzioni del problema con la realtà osservata ed evitare soluzioni inverosimili, ai problemi di PL si aggiungono i cosiddetti vincoli di non-negatività riferiti alle variabili del problema.
Così nel nostro esempio sarebbe alquanto strano ottenere soluzioni con valori negativi delle variabili decisionali. Per tale ragione, il problema è integrato dai seguenti 2 vincoli:
X1 ≥ 0
X2 ≥ 0
I due vincoli assicurano che la risoluzione del problema restituisca valori realistici ancorché ottimi.
Vincoli di
non-negatività
Economia delle Supply Chain
1 21 2
,
1 2
1 2
1 2
1
2
max 350 300
200
12 16 2880
9 6 1566
0
0
x xx x
x x
x x
x x
x
x
Il Problema di PL
Ora siamo in grado di poter scrivere il problema di PL in modo completo, nella formulazione algebrica seguente:
Soggetto a
F. Obiettivo
V. Capacità caseificio
V. Latte fornito
V. Lavoro
V. non-negatività 1
V. non-negatività 2
Attività 1 Attività 2
Economia delle Supply Chain
1 21 2
,
1 2
1 2
1 2
1
2
max 350 300
200
12 16 2880
9 6 1566
0
0
x xx x
x x
x x
x x
x
x
Soluzione Grafica
I vincoli di un problema di PL definiscono l’insieme delle soluzioni ammissibili, cioè la regione delle soluzioni ammissibili del problema (feasible region). Il nostro compito è di determinare quale punto della regione ammissibile corrisponde al valore ottimo della funzione obiettivo.
Soggetto a
Economia delle Supply Chain
Soluzione Grafica
Rappresentiamo il primo vincolo
1 2 200x x
50
100
150
200
0 50 100 150 200
x2
x1
(200,0)
(0,200)
Economia delle Supply Chain
Soluzione Grafica
Rappresentiamo il primo vincolo
1 2 200x x
50
100
150
200
0 50 100 150 200
x2
x1
(200,0)
(0,200)
Linea del limite superiore della capacità del
caseificio
Economia delle Supply Chain
Soluzione Grafica
Rappresentiamo il secondo vincolo
1 212 16 2880x x
50
100
150
200
0 50 100 150 200
x2
x1
(240,0)
(0,180)
Linea del limite superiore della disponibilità di latte
250
250
Economia delle Supply Chain
Soluzione Grafica
Rappresentiamo il secondo vincolo
1 212 16 2880x x
50
100
150
200
0 50 100 150 200
x2
x1
(240,0)
(0,180)
Linea del limite superiore della disponibilità di latte
250
250
Economia delle Supply Chain
Soluzione Grafica
Rappresentiamo il secondo vincolo
1 29 6 1566x x
50
100
150
200
0 50 100 150 200
x2
x1
(174,0)
(0,261)
Linea del limite superiore della disponibilità di
lavoro
250
250
Economia delle Supply Chain
Soluzione Grafica
Rappresentiamo il secondo vincolo
1 29 6 1566x x
50
100
150
200
0 50 100 150 200
x2
x1
(174,0)
(0,261)
Linea del limite superiore della disponibilità di
lavoro
250
250
Regione Ammissibile
(Feasible region)
Economia delle Supply Chain
Soluzione Grafica
La regione ammissibile rappresenta la nuvola dei punti rispetto ai quali il valore assunto dalle variabili non contrasta con i vincoli del problema.
50
100
150
200
0 50 100 150 200
x2
x1
250
250
Regione Ammissibile
Economia delle Supply Chain
Soluzione Grafica
La regione ammissibile offre una infinita nuvola di punti nella quale dovremo individuare la coppia di valori che producono il massimo profitto.
Per tale ragione esistono un infinito numero di valori della funzione obiettivo che soddisfa i vincoli del problema. Tuttavia, solo un punto restituisce il valore massimo della funzione obiettivo.
La ricerca di questo punto deve seguire il criterio di saturazione della disponibilità dei fattori, cioè è necessario individuare quella soluzione che riesca ad utilizzare pienamente le risorse scarse.
Per tale ragione, la soluzione del nostro problema dovrà essere cercata nelle zone più estreme della regione ammissibile.
Questi punti in PL, si trovano all’intersezione delle rette dei vincoli, vale a dire nei punti d’angolo (corner point) della regione ammissibile.
Economia delle Supply Chain
Soluzione Grafica
Procediamo per tentativi e partiamo dal seguente valore della funzione obiettivo: 350x1 + 300x2 = 35000
Graficamente:
50
100
150
200
0 50 100 150 200
x2
x1
250
250
Funzione obiettivo
(100,0)
(0,116.67)
Economia delle Supply Chain
Soluzione Grafica
Il valore della funzione obiettivo precedente soddisfa i vincoli, ma non massimizza il risultato perché abbiamo ancora disponibilità di fattori. Proviamo ora con un valore di FO pari a 52500 euro. Graficamente:
50
100
150
200
0 50 100 150 200
x2
x1
250
250
Nuova Funzione obiettivo
(150,0)
(0,175)
Economia delle Supply Chain
Soluzione Grafica
Spostando la funzione obiettivo agli estremi della regione ammissibile il risultato economico continua ad aumentare. Il punto al di là del quale non è più possibile spostare la FO corrisponde al punto di ottimopunto di ottimo.
50
100
150
200
0 50 100 150 200
x2
x1
250
250
Soluzione ottima
(122,78)
Economia delle Supply Chain
Soluzione Grafica
Per cercare la soluzione ottimale di un problema di PL è necessario studiare i punti d’angolo e determinare per ciascun punto il valore della funzione obiettivo. Il punto che restituisce il valore della FO più alto coincide con il punto di ottimo.
50
100
150
200
0 50 100 150 200
x2
x1
250
250
(0,0) FO=0€
(174,0) FO=60900€
(0,180) FO=54000€
(80,120) FO=64000€
(122,78) (122,78) FO=66100€FO=66100€
Economia delle Supply Chain
Problema di PL
Risolvere graficamente il seguente problema di Programmazione Lineare.
Soggetto a
1 21 2
,
1 2
1 2
1 2
1
2
max 450 300
200
12 16 2880
9 6 1566
0
0
x xx x
x x
x x
x x
x
x
Economia delle Supply Chain
Soluzione Grafica
Alcuni problemi di PL possono presentare delle soluzioni ottime multiple.
50
100
150
200
0 50 100 150 200
x2
x1
250
250
(0,0) FO=0€
(174,0) (174,0) FO=78300€FO=78300€
(0,180) FO=54000€
(80,120) FO=72000€
(122,78) (122,78) FO=78300€FO=78300€
Economia delle Supply Chain
Problema di PL
Risolvere graficamente il seguente problema di Programmazione Lineare.
Soggetto a
1 21 2
,
1
2
1 2
1
2
max 3 4
12
10
4 6 72
0
0
x xx x
x
x
x x
x
x
Economia delle Supply Chain
Soluzione
Rappresentiamo il primo vincolo:
1 12x
4
8
12
16
0 4 6 10 14
x2
x1
2
6
10
14
18
20
2 5 8 12 1816 20
(12,0)
Economia delle Supply Chain
Soluzione
Rappresentiamo il secondo vincolo:
2 10x
4
8
12
16
0 4 6 10 14
x2
x1
2
6
10
14
18
20
2 5 8 12 1816 20
(0,10)
Economia delle Supply Chain
Soluzione
Rappresentiamo il terzo vincolo:
1 24 6 72x x
4
8
12
16
0 4 6 10 14
x2
x1
2
6
10
14
18
20
2 5 8 12 1816 20
(0,12)
(18,0)
Economia delle Supply Chain
Soluzione
Calcoliamo le soluzioni d’angolo per individuare la soluzione ottima.
4
8
12
16
0 4 6 10 14
x2
x1
2
6
10
14
18
20
2 5 8 12 1816 20
(0,0) FO=0€
(12,0) FO=36€
(12,4) FO=52€
(3,10) FO=49€
(0,10) FO=40€
Soluzione Ottima
Economia delle Supply Chain