PROGRAMMAZIONE LINEARE:

1)CONCETTO

2)METODO GRAFICO

3)METODO ALGEBRICO

4)METODO DEL SIMPLESSO (LINPROGR)

a cura del Prof.Sampognaro Giuseppe

1)CONCETTO DI PROGRAMMAZIONE LINEARE

Si parla di PROGRAMMAZIONE LINEARE quando si e' in presenza di:

a) una FUNZIONE LINEARE A 2 O PIU' VARIABILI INDIPENDENTI che si deve MASSIMIZZARE(se si tratta di FUNZIONE RICAVO o PROFITTO) oppure MINIMIZZARE(se si tratta di FUNZIONE COSTI);

b) un INSIEME DI VINCOLI nelle suddette VARIABILI INDIPENDENTI date da EQUAZIONI o DISEQUAZIONI LINEARI A 2 O PIU' VARIABILI;

c) un INSIEME DI VINCOLI DI SEGNO,di norma POSITIVO,che esprimono la NON-NEGATIVITA' delle VARIABILI presenti essendo esse GRANDEZZE ECONOMICHE.

Se la FUNZIONE LINEARE e' a 2 VARIABILI INDIPENDENTI allora e' conveniente utilizzare il METODO GRAFICO e lo stesso metodo e' consigliabile quando la FUNZIONE LINEARE ha piu' di 2 VARIABILI,ma si puo' ridurre a 2 VARIABILI se nell'INSIEME DEI VINCOLI vi e'qualche equazione che riduce(come vedremo) il numero delle VARIABILI.

Se la FUNZIONE LINEARE e' a 3 o piu' VARIABILI INDIPENDENTI conviene usare il METODO ALGEBRICO o il METODO DEL SIMPLESSO.

2)METODO GRAFICO

Quando si sono studiate le FUNZIONI A 2 VARIABILI (vedi relativa tesina al paragrafo N 11) si sono cercati i MASSIMI E MINIMI DI UNA FUNZIONE A 2 VARIABILI CON VINCOLI DATI DA DISEQUAZIONI LINEARI.

In questa sede si trattera' lo stesso argomento,ma sara' in parte esemplificato essendo in presenza di FUNZIONI ECONOMICHE.

Infatti per cercare i MASSIMI o MINIMI di una FUNZIONE ECONOMICA A 2 VARIABILI conviene esguire attentamente i seguenti passaggi:

a) si determina il DOMINIO DEI VINCOLI (o REGIONE DEL PIANO Ox1x2 DELLE SOLUZIONI AMMISSIBILI)

b) se il DOMINIO DEI VINCOLI e' un POLIGONO si calcolano i VALORI DELLA FUNZIONE DATA NEI VERTICI del POLIGONO e si tra essi il VALORE MASSIMO se la FUNZIONE DATA si deve MASSIMIZZARE, oppure il VALORE MINIMO se la FUNZIONE DATA si deve MINIMIZZARE.

c) se il DOMINIO DEI VINCOLI e' ILLIMITATO si esaminano alcune LINEE DI LIVELLO nell'interno del DOMINIO DEI VINCOLI per capire se esiste un punto che ottimizza la FUNZIONE ECONOMICA DATA.

ESEMPIO PRATICO:

Sia data una FUNZIONE RICAVO data dalla equazione:

Z=16000 x1 + 10000 x2

Vogliamo cercare il MASSIMO VALORE della suddetta FUNZIONE nei VINCOLI:

x1 + 2x2<=40

3x1 + 2x2<=60

x1<=18

x1>=0

x2>=0

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).

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 x2.

N.B)Da quanto detto prima il METODO GRAFICO si puo' utilizzare se la FUNZIONE e' a 2 VARIABILI,ma possiamo usare tale metodo anche se la FUNZIONE e' a 3 VARIABILI e nei vincoli vie' una equazione.Infatti da tale equazione possiamo calcolare il valore di una VARIABILE rispetto le altre e quindi sostituito tale valore nella FUNZIONE data e negli altri VINCOLI DISEQUAZIONALI ritroveremo una FUNZIONE a 2 VARIABILI con VINCOLI a 2 VARIABILI.

In generale si puo' utilizzare il METODO GRAFICO se la FUNZIONE e' ad n VARIABILI e vi sono m equazioni vincolari e risulta n-m=2.

3)METODO ALGEBRICO

Tale metodo risolve un PROBLEMA DI PROGRAMMAZIONE LINEARE se la FUNZIONE ECONOMICA e' a 3 o piu' VARIABILI INDIPENDENTI non riducibili in alcun modo a 2.

Si procede eseguendo attentamente i seguenti passaggi:

a)Si introducono tante VARIABILI AUSILIARIE o DI SCARTO quante sono le DISEQUAZIONI VINCOLARI in modo che ciascuna di esse diventi EQUAZIONE VINCOLARE

b)Si determinano tutte le SOLUZIONI DI BASE,che vengono determinate da punti aventi n+m coordinate(dove n e' il numero delle VARIABILI INIZIALI,o D'AZIONE ed m e' il numero delle VARIABILI AUSILIARIE o DI SCARTO).Tra queste n+m coordinate n devono essere sempre nulle.

c)Per determinare il numero delle SOLUZIONI DI BASE basta calcolare il numero delle COMBINAZIONI di n+m elementi presi ad n ad n.

d)Si scelgono tra le SOLUZIONI DI BASE le SOLUZIONI AMMISSIBILI DI BASE date dai punti precedenti che hanno le coordinate tutte positive poiche' le VARIABILI sono GRANDEZZE ECONOMICHE e quindi positive.

d)Si sostituiscono le coordinate di tali punti nella FUNZIONE data e si sceglie quel punto che porta al valore MASSIMO oppure MINIMO come si desidera dal genere della FUNZIONE data.

ESEMPIO PRATICO:

Si desidera massimizzare LA FUNZIONE ECONOMICA:

Z= 5x1 + 3x2 + x3 nei vincoli

x1+2x2-x3<=15

2x1-x2+x3<=10

xi>=0

a)Si introducono le VARIABILI AUSILIARIE (x4)ed(x5) e quindi i VINCOLI diventano

x1+2x2-x3+(x4)=15

2x1-x2+x3+(x5)=10

xi>=0

c)Il numero delle SOLUZIONI DI BASE sono C(5/3)=10

b)Le SOLUZIONI DI BASE si trovano attribuendo alle 5 coordinate dei rispettivi punti aternativamente 3(quante le VARIABILI d'AZIONE) zeri e calcolando le rimanenti 2 coordinate attraverso la FUNZIONE ECONOMICA DATA ed attraverso le due EQUAZIONI VINCOLARI.

Si avranno in questo caso i seguenti 10 Punti:

A1(0,0,0,15,10);A2(7,4,0,0,0);A3(25/3,0,-20/3,0,0);A4(5,0,0,10,0);

A5(15,0,0,0,-20);-A6(0,25,35,0,0);A7(0,10,0,35,0);A8(0,15/2,0,0,35/2);

A9(0,0,10,25,0);A10(0,0,-15,0,25).

Notare che dei punti precedenti si devono scartare i punti A3,A5,A10 contenendo nelle loro coordinate valori negativi delle xi che sappiamo devono essere positive essendo grandezze economiche ed escludere anche A8 non potendo essere una grandezza economica numero frazionario.

d)Sostituiti i suddetti punti nella FUNZIONE DATA si trova il MASSIMO che si trova in A5 con Z(A5)=110.

4)METODO DEL SIMPLESSO

Questo metodo serve per risolvere un PROBLEMA DI PROGRAMMAZIONE LINEARE dove la FUNZIONE ECONOMICA da MASSIMIZZARE o da MINIMIZZARE e' a 3 o piu' VARIABILI come le DISEQUAZIONI VINCOLARI.

Il METODO DEL SIMPLESSO si puo' sviluppare in alcuni metodi diversi.

In questa sede si segue il METODO DI ELIMINAZIONE.

Si eseguono attentamente i seguenti passaggi:

a)Come per il METODO ALGEBRICO si introducono le VARIABILI AUSILIARIE o DI SCARTO trasformando le DISEQUAZIONI VINCOLARI in EQUAZIONI.

b)Si fissa la PRIMA SOLUZIONE AMMISSIBILE DI BASE che e' data dalla SOLUZIONE BANALE che risulta quella in cui si annullano le 3 o piu' VARIABILI d'AZIONE.Per essa si calcola il VALORE sulla FUNZIONE DATA che normalmente risulta ZERO.

c)Si inizia a cercare la SECONDA SOLUZIONE AMMISSIBILE DI BASE cercando nella FUNZIONE DATA ,se la si vuole MASSIMIZZARE( MINIMIZZARE ) la VARIABILE di coefficente MAGGIORE (MINORE) e si pone tale VARIABILE uguale ad un parametro t,mentre le altre VARIABILI presenti nella FUNZIONE DATA vengono poste uguali a ZERO.

d)Si sostituiscono tali valori nelle EQUAZIONI VINCOLARI e si impongono le VARIABILI AUSILIARIE ad essere POSITIVE.Dalla risoluzione del sistema relativo scaturisce il valore di t e quindi i valori delle coordinate della SECONDA SOLUZIONE AMMISSIBILE.

e)Si sostituiscono le coordinate di questa SOLUZIONE AMMISSIBILE nalla FUNZIONE DATA e si trova il nuovo valore di essa.

f)Dai valori delle coordinate trovate nella SECONDA SOLUZIONE AMMISSIBILE si deduce la VARIABILE ENTRANTE data dalla VARIABILE d'AZIONE avente in essa il valore MAGGIORE (MINORE) e la VARIABILE USCENTE data dalla VARIABILE AUSILIARIA avente in essa il valore MINORE (MAGGIORE ).

g)Si cerca tra le EQUAZIONI VINCOLARI quella in cui vi e' sia la VARIABILE ENTRANTE che la VARIABILE USCENTE e si calcola in essa il valore della VARIABILE ENTRANTE in funzione delle altre VARIABILI e si sostituisce il valore trovato nella FUNZIONE DATA e quindi si ricomincia dal punto c) al punto g).

Il problema di ricerca delle SOLUZIONI AMMISSIBILI DI BASE termina o se i coefficenti delle VARIABILI della FUNZIONE DATA sono tutti NEGATIVI (POSITIVI) o se si ritrova la VARIABILE ENTRANTE o se la FUNZIONE DATA CRESCE (DECRESCE) indefinitivamente.

ESEMPIO PRATICO:

Sia Z=2x1+5x2+x3 la FUNZIONE da MASSIMIZZARE.

Siano x1+x2<=10

2x1-x2+x3<=8

xi>=0 le DISEQUAZIONI VINCOLARI che con l'aggiunta delle VARIABILI AUSILIARIE (x4) e (x5) diventano:

x1+x2+(x4)=10

2x1-x2+x3+(x5)=8

Trascurando la SOLUZIONE BANALE pongo x2=t (avendo in Z coefficente maggiore) ed anche x1=0 ed x3=0.

Sostituisco tali valori nelle EQUAZIONI VINCOLARI e trovo

0+t+(x4)=10 (x4)=10-t>=0

0-t+(x5)=8 ovvero (x5)=8+t>=0 Risolto tale sistema trovo t=10 e quindi x1=0;x2=10;x3=0;(x4)=0;(x5)=18

Da tali valori x2=VARIABILE ENTRANTE e (x4)=VARIABILE USCENTE

Inoltre sostituiti tali valori nella Z trovo Z=50.

Dalla prima EQUAZIONE VINCOLARE trovo x2=10-x1-(x4) che sostituisco in Z e trovo alla fine Z=-3x1+x3-5(x4)+50.

Ricomincio e pongo x3=t ed esegundo gli stessi passaggi trovo la nuova SOLUZIONE AMMISSIBILE di BASE x1=0;x2=10;x3=18;(x4)=0;(x5)=0

per la quale Z=68.

Nel successivo passaggio ritrovo lo stesso valore precedente per cui l'esercizio termina con la soluzione OTTIMALE trovata per ultima.

N>B)La SOLUZIONE OTTIMALE si poteva trovare anche col METODO ALGEBRICO ma con un procedimento piu' lungo.