Programmazione lineare

Risultati immagini per 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.

 

 

 

 

Torna ad INDICE ARGOMENTI classe Quinta AH