Programmazione lineare
PROGRAMMAZIONE LINEARE
Si parla di PROGRAMMAZIONE LINEARE quando si
e' in presenza di: · una funzione lineare 2 o più variabili
indipendenti che si deve massimizzare (se si tratta di funzione ricavo o
profitto) oppure minimizzare (se si tratta di funzione costi); · un insieme di vincoli (tecnici) nelle suddette variabili indipendenti date
da equazioni o disequazioni lineari a 2 o più variabili; · un insieme di vincoli di segno che esprimono la non-negatività delle variabili
presenti essendo esse grandezze economiche. I vincoli di segno limitano la
ricerca delle soluzioni al primo quadrante del corrispondente piano
cartesiano. Si tratta ancora di ottimizzare una funzione sottoposta
a dei vincoli che sono una disequazione o un sistema di disequazioni.
Tuttavia, se la
funzione obiettivo è lineare, non si e seguono le fasi b) e c) relativi al
precedente paragrafo poiché una
funzione lineare non ha max e min assoluti all'interno della regione ammissibile, né
sulla frontiera. Quindi il massimo ed il minimo di una funzione lineare
soggetta a vincoli espressi da equazioni e/o da disequazioni lineari, se
esistono, si trovano sui vertici della regione ammissibile, e non al suo
interno. Metodo grafico Per cercare i MASSIMI o MINIMI di
una FUNZIONE lineare in 2 variabili conviene eseguire attentamente i seguenti
passaggi: · Dopo aver tracciato tutte le rette associate
alle disequazioni ed equazioni del sistema dei vincoli, se l’intersezione
derivante non è un insieme vuoto, si otterrà un poligono (o una regione
illimitata) detto regione ammissibile, perché contiene tutte le coppie
(x, y) che
soddisfano le disequazioni e/o le equazioni del sistema. · se il dominio dei vincoli e' un poligono si calcolano i valori della funzione data nei vertici del poligono e tra essi il valore massimo se la funzione data si deve massimizzare, oppure il valore minimo se la funzione data si deve minimizzare. Nel caso particolare in cui, in corrispondenza di due vertici consecutivi, si ottienga lo stesso valore della funzione obiettivo, la teoria della programmazione lineare dimostra che lo stesso valore si ottiene in corrispondenza di un qualsiasi punto compreso tra i due vertici suddetti. · se il dominio dei vincoli e' illimitato si
esaminano alcune linee di livello all'interno del dominio dei vincoli per
capire se esiste un punto che ottimizza la funzione data. Infine se i valori delle variabili x e y devono essere
numeri interi (esempio: numero di pezzi prodotti alla settimana), si
considerano nella regione ammissibile solo i punti aventi per coordinate
numeri interi. |
Esempio: Sia data una funzione ricavo di equazione: z =16000 x1 +
10000 x2 Vogliamo cercare il massimo valore della
funzione sottoposta ai vincoli:
x1+ 2 x2 £ 40
3 x1 + 2 x2 £ 60 x1 £ 18 x1 ³ 0 vincolo di segno x2 ³ 0 vincolo di segno Da una semplice rappresentazione scaturisce
che il dominio dei vincoli e' un poligono di vertici: O(0,0)
A(18,0) B(18,3) C(10,15) D(0,20). Per il Teorema Fondamentale della
Programmazione lineare il Massimo è da ricercare nei Vertici del Poligono Il calcolo del valore di questi vertici nella funzione data
porta ai seguenti risultati: z(O)=0;
z(A)=288000;
z(B)=318000; z(C)=310000;
z(D)=200000 Da tali risultati si deduce che la funzione
ricavo data si ottimizza nel vertice B ovvero producendo 18 pezzi di x1 e 3 pezzi di x
2. |