PROGRAMMAZIONE LINEARE
La programmazione lineare (P.L.) è una parte importante della ricerca operativa (R.O.) e deve il suo
nome al fatto che essa viene utilizzata per risolvere problemi economici relativi a un programma di
attività, sulla base di un modello matematico contenente relazioni tutte lineari. I problemi economici
oggetto della P.L. sono principalmente quelli che richiedono di minimizzare i costi e massimizzare gli
utili. Ciò avviene attraverso un modello matematico costituito da:
1) una funzione obiettivo lineare di n variabili Z 21 1 , dette
ar ta t amm
variabili di azione, della quale si vuole determinare il massimo o il minimo.
2) un sistema di m vincoli tecnici espressi da equazioni o disequazioni lineari nelle n variabili
7,7 In
3) un sistema di n vincoli di segno che garantiscono la non negatività delle variabili.
i 70
Fra i vari metodi utilizzati per risolvere i problemi di P.L., prenderemo in considerazione il metodo
gra co, che consiste nel risolvere il sistema di disequazioni lineari costituito dalla funzione obiettivo,
dai vincoli tecnici e dai vincoli di segno sullo stesso piano cartesiano. La soluzione del sistema è
rappresentata dalla parte di piano, detta regione ammissibile o dominio dei vincoli, che soddisfa tutti i
vincoli esistenti.
Esempio: un laboratorio di pasticceria produce ogni settimana confezioni di due tipi di biscotti A e B,
che vende rispettivamente al prezzo di € 2 e € 4. Per ciascuna confezione di tipo A sono necessari
150 g di farina e 100 g di zucchero; per ciascuna confezione di tipo B sono necessari 250 g di farina
e 350 g di zucchero. Supponendo che le quantità di farina e zucchero impiegate per tale produzione
settimanale non possano superare rispettivamente 9000 e 8750 g, determiniamo il numero di
confezioni del tipo A e del tipo B da produrre per ottenere il massimo ricavo settimanale.
numero di confezioni di biscotti A
numero di confezioni di biscotti B
Z 2
hy funzione obiettivo
150 2504 9000 vincoli tecnici
100 350 a 8750
y
so
vincoli di segno
yo
1 150 9000 250 150 9000
2504 y
y 3 36
2 100 350 8750 350 100 8750
y y
25
y
36
y 3 36
Y
Y yay
A 0 36 C 0 25
B 60 O 725 0 50
Dyyy
PUNTI DI PROVA Ix
i
0,0 10
o 36 9000 V
0 10 20 30 40 50 60 70 80 90
YO
2 25 c 8750 U
010,0 a
3 P 130 U
1,1
4 P 1 11 170
Consideriamo la funzione obiettivo z
ora 2x
44
ottengono al variare del valore
Le rette che si
di z sono dette linee di livello e formano
un fascio
improprio di rette tutte parallele a
2 0 _2 che
1 2
retta
viene detta
guida del fascio
A partire dalla retta
guida si possono tracciare
le linee di livello
per individuare
il massimo
e il minimo della funzione all'interno
della ammissibile Tale
regione regioni forma
un
poligono di cui conosciamo le
vertici coord nate già
dei 010,0 0 25 B 60 D
Calcoliamo ora le coordinate del vertice a
Y 3 36 36 25
25 25
YE
25 10 11
36
3 213
4
1 111 35
4 4 2s
35
io
E
Zio
[Link] Q 35 15
Q
10
iI
0 0
20 10
Imponendo il passaggio delle rette parallele
alla retta z dai vertici del
guida y poligono
abbiamo
0 25 2 o 25 2 25
B 60 0 2 60 0 Z 30
Q 35 15 5
Z 35
EI
Dopo avertracciato le linee di livello
ai diversi corrispo denti
valori di Z si vede che
nel rispetto dei vincoli il valore minimo
della funzione è 2 0 assunto nel punto
poi e cresce fino i
0,0 a
raggiungere
valore massimo in Z 652 in corrispondenza
del punto Q 35 15