Programmazione lineare
Definizione : la programmazione lineare serve per determinare l’allocazione ottimale di risorse
disponibili in quantità limitata, per ottimizzare il raggiungimento di un obiettivo prestabilito, in
condizioni di certezza
Tipi di problemi risolubili con le tecniche della programmazione lineare (P.L.) : problemi
economici, problemi di distribuzione delle risorse, problemi di trasporto e di assegnazione, ecc.
Modello
matematico :
Ottimizzare funzione obiettivo f(x) , x vettore
Vincoli di segno
Vincoli tecnici : eguaglianze o diseguaglianze
deboli
Tutte le funzioni presenti nel modello sono lineari
Metodi risolutivi:
a) Metodo grafico
b) Metodo algebrico
c) Metodo del simplesso
Problemi di P.L. in due variabili – metodo grafico
Problema 1
Un ‘industria produce due prodotti A e B e utilizza due macchinari M e N . Per ogni unità di A
sono necessarie 1 ora di M e 3 ore di N , per ogni unità di B sono necessarie 2 ore di M e 2
ore di N. Inoltre A non può essere prodotto in più di 18 pezzi settimanali , la macchina M non
può lavorare per più di 40 ore alla settimana , mentre B per non più di 60.
Determinare qual è la combinazione produttiva più conveniente, sapendo che ogni unità di A
viene venduta a 16.000 u.m. e ogni unità di B a 10.000 u.m. , nell’ipotesi che ogni quantità
prodotta sia venduta.
Schema risolutivo
A
B
Ore disponibili
M
1
2
40
N
3
2
60
x = quantità di A
y = quantità di B
z = funzione obiettivo = ricavo
Modello matematico
max
z = 16000 x + 10000 y
x + 2y  40
vincolo n°1
3x + 2y  60
vincolo n°2
0  x  18
vincoli n°3 – n° 4
y0
vincolo n°5
In generale il problema si schematizza :
Ottimizzare funzione obiettivo
z=mx + ny
soggetta ai vincoli
ax+byc
:
:
Modello
matematico
dx+eyf
:
:
x0
y 0
Passi per determinare la soluzione
• Si rappresenta graficamente il sistema dei vincoli nel piano Oxy ottenendo la regione delle
soluzioni ammissibili ( o dominio dei vincoli )
Se l’insieme non è vuoto, tale area può essere rappresentata da un poligono, o da una regione
poligonale illimitata, che possono eventualmente ridursi ad una semiretta, ad un segmento o ad un
punto.
P(x,y)
x
x
Ogni coppia (x,y) appartenente al dominio dei vincoli si dice soluzione ammissibile e tra queste
si cercherà la soluzione ottima.
• Si rappresentano le linee di livello della funzione obiettivo (rette, in quanto la f.o. è un piano
nello spazio).
Si rappresenta la linea di livello corrispondente a z = 0 (retta guida ), che divide il piano in due
parti in una delle quali z > 0 e nell’altra z < 0.
Il semipiano in cui z > 0 può essere facilmente individuato in quanto è quello che contiene il
punto P(m,n) . Infatti il valore assunto da z in P(m,n) è m m + n n = m2 + n2. Unendo l’origine O
con il punto P e disegnando la freccia avente verso da O a P si individua il semipiano in cui z > 0.
Questa freccia che prende il nome di vettore di origine O ed estremo P, risulta sempre
perpendicolare al piano z = mx + ny. Il vettore OP indica il verso di crescita della funzione
obiettivo z = mx + ny.
P(1,3)
z =x + 3y
z>0
z<0
z=3
z=0
z=-1
z=1
• Dall’andamento delle linee di livello nel dominio si deduce se la funzione ammette massimo o
minimo.
z=3
z=0
z=1
z=-1
z = z2 max
z = z1 min
Esempi di regioni ammissibili
y
y
D
D
E
E
A
A
C
B
O
C
B
x
Minimo in A e massimo in D
O
Minimo in D e massimo in A
x
y
A
A
B
B
O
O
x
x
Minimo in A e nessun massimo
Nessun minimo e massimo in A
y
y
D
E
D
E
A
C
A
B
O
C
B
x
Infiniti minimi nel segmento AB e un massimo
in D
O
x
Un massimo in D e infiniti massimi nel segmento AB
Osservazione
In un problema di programmazione lineare se l’insieme delle soluzioni ammissibili è un poligono
chiuso, allora è un poligono chiuso convesso.
Teorema ( Weierstrass + teo fondamentale P.L. )
Se l’insieme delle soluzioni ammissibili è un poligono convesso, il massimo e il minimo esistono e
si trovano in un vertice del poligono
Osservazione
Per determinare i punti estremi basta calcolare i valori della funzione obiettivo nei vertici del
dominio, se questo è un poligono chiuso. Se il dominio dei vincoli è illimitato si esamina invece
l’andamento delle curve di livello per determinare, se esiste, un punto che ottimizza la funzione
obiettivo
Osservazione
Se in due vertici consecutivi la f.o. assume lo stesso valore, essa assume quello stesso valore in
tutti i punti del segmento che li unisce.
Soluzione problema 1
D
C
10
B
O
10
A
L’area ammissibile è data dal
poligono OABCD, con O(0,0),
A(18,0), B(18,3), C(10,15), D(0,20).
Poiché il dominio dei vincoli è un
poligono chiuso, calcoliamo i valori
della f.o. nei vertici :
z(O) = 0
z(A) = 288.000
z(B) = 318.000
z(C) = 310.000
z(D) = 200.000
La f.o. ha un massimo in B con una
produzione settimanale x =18, y =3.
Il vincolo su N è soddisfatto al massimo della sua disponibilità, mentre le ore di lavorazione per M
sono solo 24 delle 40 disponibili.
Osservazione : importanza della rappresentazione grafica
La soluzione di un problema di P.L. a due variabili è semplice in quanto è possibile la
rappresentazione grafica del campo di scelta che permette di individuare con rapidità i vertici tra i
quali deve essere ricercato l’ottimo. Ma se si tralasciasse di fare tale rappresentazione la mole dei
calcoli sarebbe notevolmente superiore.
Nell’esempio precedente i punti O,A,B,C,D sono i punti che risolvono le coppie dei vincoli
espressi come eguaglianze :
O:
3
5
4
5
A:
2
4
B:
C:
G
D
C
E
10
B
O
10
A
F
H
1
2
D:
1
3
G
Se,invece, non viene
rappresentata preliminarmente
la regione ammissibile, si
devono risolvere anche i
sistemi relativi alle altre
possibili coppie di vincoli
espressi come eguaglianza :
D
C
E
10
B
O
10
E:
A
1
4
F
H
F:
1
5
G:
2
3
H:
2
5
I:
3
4
Dovremmo quindi calcolare la funzione obiettivo anche in questi punti, che sono comunque
vertici, ma non del campo di scelta.
Notare che 10 =
 5
 
 2
 
Osservazione : caratterizzazione dei vertici
G
D
C
E
10
H
B
O
10
A
F
I vertici ammissibili sono quelli che sono
intersezione di due vincoli intesi come
eguaglianze e soddisfano le altre
disuguaglianze.
Quindi se non si avesse la rappresentazione
grafica occorrerebbe risolvere tutti i sistemi
e fare le opportune verifiche per accertare
quali sono i vertici della regione
ammissibile.
H
Su queste considerazioni si basano i metodi
per risolvere problemi P.L. in n variabili.
Problemi di P.L. in tre o più variabili riconducibili a due : metodo grafico
Un problema di P.L. è riconducibile ad un problema di P.L. in 2 variabili e quindi risolubile con
metodo grafico, se nel sistema dei vincoli compaiono n –2 equazioni da cui è possibile ricavare n–2
variabili in funzione delle altre 2.
Problema 2
max
z = 6 x1 + 3 x2 + 4 x3
x1 + x2 + x3 = 10
3 x1 + x2 +2 x3  26
x1 + 3 x3  18
x1  0
x2  0
x3  0
Soluzione problema 2: dal primo vincolo si ricava x3
e sostituendo si ottiene
max
z = 40 + 2 x1 - x2
x1 - x2  6
2 x1 +3 x2  12
x1 + x2  10
x1  0
x2  0
C
Si ottiene un max in (8,2,0) con z = 54
D
2
B
A
O
2
H
6
10
Problemi di P.L. in tre variabili : metodo grafico
Problema 3
Un agricoltore vuole coltivare nel suo terreno tre prodotti P,Q,R. La superficie massima
utilizzabile è di 40 ettari. Per ogni ettaro coltivato a P occorrono 20 giornate di lavoro, per ognuno
coltivato a Q: 10, per ognuno coltivato a R : 15. In un anno dispone di 600 giornate di lavoro di
operai. La coltivazione di R non può superare i 20 ettari. Per P si ha un utile di 300.000 u.m. per
ettaro, per Q si ha un utile di 200.000 u.m. per ettaro, per R si ha un utile di 300.000 u.m. per
ettaro. Determinare come utilizzare il terreno per conseguire il massimo utile
max
z = 300 x1 + 200 x2 + 350x3
x1 + x2 + x3  40
20 x1 +10 x2 +15 x3 600
x3  20
x1  0
x2  0
x3  0
Soluzione problema 3
max
z = 300 x1 + 200 x2 + 350x3
x1 + x2 + x3  40
20 x1 +10 x2 +15 x3 600
x3  20
E
x1  0
x2  0
x3  0
G
D
F
0
A
C
C
B
Si rappresentano i piani
x1 + x2 + x3 = 40
4 x1 +2 x2 +3 x3 = 120
x3 = 20
Risolvendo il sistema formato dalle equazioni dei piani si ottengono i punti :
O(0,0,0),A(30,0,0), B(20,20,0),C(0,40,0),D(0,0,20),E(15,0,20),F(10,10,20),G(0,20,20)
L’utile massimo è in F con z = 12.000.000.
Il metodo grafico è un po’ laborioso e non applicabile a più di tre variabili : si può applicare
il metodo algebrico
Problemi di P.L. in n variabili : metodo algebrico
Ottimizzare
z = c1 x1 + c2 x2 + …+ cn xn
a11 x1 + a12 x2 +… a1n xn  b1
a21 x1 + a22 x2 +… a2n xn  b2
………………………………..
am1 x1 + am2 x2 +… amn xn  bm
xi  0
(i =1…n)
Per determinare i vertici, essendo m+n i vincoli e n le variabili occorre risolvere un numero di
sistemi lineari di n equazioni (ottenute dai vincoli espressi con l’eguaglianza) in n incognite.
m  n


n


Tutti i possibili sistemi sono 
.
m  n
Non è detto che le soluzioni trovate siano tutte ammissibili, ma  n  è un estremo superiore e ci


assicura che la soluzione ottima , se esiste, può essere trovata, per enumerazione, in un numero finito
di passi.
Per ciascuno dei sistemi risolti occorre poi sostituire gli n valori trovati delle variabili nelle rimanenti
m diseguaglianze per vedere se sono soddisfatte, scartando le n-uple che non caratterizzano un
vertice.
Ad esempio con n =10 variabili e 6 vincoli tecnici ( in totale 6+10 vincoli ) dovremmo
risolvere
16 
 
10 
 
= 8008 sistemi 1010, e per ognuna delle 8008 decuple ottenute,
scartare quelle che non soddisfano le restanti 6 diseguaglianze.
Nel problema n° 3 si dovrebbero risolvere
soluzioni.
 6
 
 3
 
= 10 sistemi e testarne poi le
Problemi di P.L. in n variabili : metodo del simplesso
La tecnica algebrica di ricerca dell’ottimo è semplice, ma inefficiente per problemi in cui
l’insieme ammissibile ha molti vertici : l’algoritmo del simplesso è una procedura efficiente che
risolve il problema.
L’algoritmo del simplesso,in effetti, risolve problemi in cui tutti i vincoli tecnici sono
rappresentati da equazioni : i vincoli sono quindi m equazioni ed n disequazioni di positività delle
variabili.
E’ possibile comunque applicarlo ad un problema generale trasformando le disequazioni in
equazioni : si aggiungono delle variabili fittizie, dette variabili slack con coefficiente zero nella
funzione obiettivo.
Problema 3
Problema 3 trasformato con variabili slack
max
max
z = 300 x1 + 200 x2 + 350x3
z = 300 x1 + 200 x2 + 350x3 + 0 x4 + 0 x5 + 0 x6
x1 + x2 + x3  40
x1 + x2 + x3 + x4 = 40
4 x1 +2 x2 +3 x3 120
4 x1 +2 x2 +3 x3 + x5 = 120
x3  20
x3 + x6 = 20
x1  0
xi  0
x2  0
x3  0
(i =1…6)
Il metodo del simplesso, invece di calcolare il valore della funzione obiettivo in tutti i vertici
ammissibili, permette di calcolare il valore della funzione in un dato vertice e di scegliere il
successivo in modo che la funzione obiettivo “migliori” e così via fino a giungere all’ottimo più
velocemente .
Algoritmo “grafico” del simplesso
1.
Si considera un vertice iniziale ammissibile.
2.
Si confronta il vertice prescelto con quelli ad esso adiacenti.
3.
Se tra questi ultimi vertici se ne trova uno “migliore” si prende in considerazione
quest’ultimo e si ripete il confronto tornando al punto 2.
4.
In caso contrario l’ultimo vertice considerato è quello ottimo.
Il numero di vertici che occorre percorrere è presumibilmente inferiore al n° totale , poiché ad
ogni iterazione ci si avvicina alla soluzione ottimale e quindi molti vertici vengono esclusi dalla
necessità di esame.
Soluzione problema 3 con metodo del simplesso
Passo1 (Scelta di una prima soluzione ammissibile)
Posti x1 = x2 = x3 = 0, dal sistema dei vincoli si ricava x4 =40, x5 =120, x6 = 20 e si ha la prima
soluzione ammissibile di base : (0,0,0,40,120,20) che corrisponde al valore z = 0.
Passo2
Si vuole ora passare ad un’altra soluzione ammissibile che aumenti il valore di z in modo che
una variabile fra quelle prima nulle prenda valore positivo ed un’altra tra quelle prima positive
diventi nulla . Il sistema dei vincoli risolto rispetto a x 4, x5 ,x6 è
x4 = 40 - x1 -x2 - x3
x5 = 120 - 4 x1 -2 x2 -3 x3
x6 = 20 - x3
Dall’esame di z = 300 x1 + 200 x2 + 350x3 + 0 x4 + 0 x5 + 0 x6 , si vede che il massimo incremento
di z si ha incrementando x3 e dall’esame dei vincoli si vede che il massimo valore attribuibile a
x3 è 20, da cui x6 = 0 ( si deve rispettare la condizione xi  0 (i =1…6) ).
Si ricava quindi la seconda soluzione ammissibile (0,0,20,20,60,0) con z = 300 x 1 + 200 x2 + 350
(20–x6) +0 x4 + 0 x5 + 0 x6=7000.
Si dice che x3 è entrata nella base e x6 è uscita dalla base.
Le variabili della base sono quelle non nulle è cioè x3, x4, x5. Cerchiamo ora di passare da questa
soluzione ad una ad essa adiacente che aumenti il valore di z. Una soluzione di base è adiacente
ad un'altra se ha le stesse variabili di base della precedente tranne una; dobbiamo fare in modo che
una fra x3, x4, x5 diventi nulla (esce dalla base), inserendo nella nuova base x 1, x2 o x6 .
Passo3
Esaminando z = 300 x1 + 200 x2 + 350 (20–x6) +0 x4 + 0 x5 + 0 x6=7000+300x1 +200 x2 –350 x6, si
sceglie, tra le variabili, quella che migliora la funzione obiettivo e quindi x 1. Ci chiediamo ora qual
è il massimo valore attribuibile a x1 affinché una fra x3, x4, x5 si annulli, lasciando però  0 tutte le
altre.
Si riscrive il sistema dei vincoli ricavando x 3, x4, x5 rispetto alle variabili fuori dalla base,
ottenendo
x3 = 20 – x6
x4 = 40 + x6 –x1 – x2
x5 = 60 - 4 x1 -2 x2 +3 x3
individuando la terza soluzione ammissibile (15,0,20,5,0,0) con z = 11.500+50 x 2 -75 x5 –125 x6.
Passo4
Entra nella base x2. Scriviamo il sistema dei vincoli esprimendo x1, x3, x4 rispetto alle variabili
fuori dalla base e si determina il valore migliore x 2=10. Si ottiene la quarta soluzione
ammissibile (10,10,20, 0, 0,0) con z = 12000 - 100 x4 -50 x5 –100 x6 .
Il valore di z non si può migliorare ulteriormente poiché tutti i coefficienti sono negativi e le
variabili entrando nella base ridurrebbero il valore di z. Quindi (10,10,20,0,0,0) è la soluzione
ottima.
Sequenza dei vertici
O(0,0,0,40,120,20)
D(0,0,20,20,60,0)
E(15,0,20,5,0,0)
F(10,10,20,0,0,0)
G
D
E
F
0
C
A
B
Nella figura è evidenziato il cammino seguito dall’algoritmo per ottimizzare la funzione
obiettivo.
Schema algebrico del simplesso
1. individuazione di una prima soluzione di base ammissibile
Se tale soluzione non è ottima:
2. scrittura del sistema dei vincoli in funzione di tale base.
3. ricerca di una nuova soluzione di base ammissibile mediante individuazione della variabile
entrante nella base e di quella uscente dalla base.
4. determinazione della nuova soluzione di base ammissibile.
5. valutazione della funzione per stabilire se si è trovata la soluzione ottima.
Si ripetono i passi da 2 a 5 fino a che si trova la soluzione ottimale