MATEMATICA PER L’ECONOMIA - PROGRAMMAZIONE MATEMATICA

Clicca per effettuare il download della relazione (formato Word).

Sommario: 1. Il problema. - 1.1 Condizione necessaria. - 2. Condizioni di Kuhn-Tucker. - 3. Teorema del punto di sella di Kuhn-Tucker. - 4. La programmazione lineare. - 4.1 Metodi risolutivi. - 4.1.1 Metodo grafico. - 4.1.2 Metodo del simplesso.

1. Il problema.

Il problema della programmazione matematica è quello di ottimizzare una funzione obiettivo sottoposta a un sistema di vincoli espressi da disuguaglianze. Esso può essere formulato in modo sintetico:

f(x) = Max

j (x) £ b

x ³ 0

sapendo che f(x) rappresenta la funzione obiettivo di cui si ricerca il massimo condizionato da p vincoli j i(x) £ bi (i = 1, 2, ..., p) e da m vincoli di non negatività delle variabili xi ³ 0 (i = 1, 2, ...., m).

Questa è una formulazione generale del problema visto che l’obiettivo di minimizzare una f può sempre ricondursi alla ricerca del massimo di -f; così come se il vincolo è espresso nella forma j i(x) ³ bi può sempre riscriversi come -j i(x) £ -bi moltiplicando per -1 entrambi i membri della disuguaglianza e cambiandone il verso.

La soluzione del sistema dei vincoli è detta area ammissibile o regione delle soluzioni ammissibili. Un punto x ³ 0 tale che j (x) £ b, appartenente quindi alla regione ammissibile, è ottimo se massimizza la f.

 

1.1. Condizione necessaria.

La ricerca della soluzione del problema è in genere complicata dall’esistenza di numerosi vincoli non lineari che rendono difficile la ricerca della regione ammissibile. Esaminando il problema per gradi successivi, è possibile, in un primo passo, determinare una condizione necessaria per l’esistenza di un massimo della f in x0 soggetta al solo vincolo x ³ 0.

Consideriamo che x0 sia un punto interno della regione delle soluzioni ammissibili, cioè che x0>0; in questo caso, in ipotesi di regolarità della f, condizione necessaria per l’esistenza di un massimo è che Ñ f(x0)=0 cioè che si annullino tutte le derivate parziali prime.

 Se, invece, x0 è un punto di frontiera della regione delle soluzioni ammissibili, cioè se x0 ma non è né x0>0, né x0=0, il problema è ricondotto alla ricerca del massimo nell’insieme dei punti del sottospazio individuato dalle componenti non nulle di x0. Quindi, condizione necessaria per la sua esistenza è l’ortogonalità del gradiente con tale sottospazio, cioè <Ñ f(x0), x0>=0 e la direzione del gradiente verso l’esterno della regione ammissibile, cioè Ñ f(x00.

Se, infine, x0=0 deve essere Ñ f(00 perché altrimenti spostandosi lungo la direzione del gradiente la f assumerebbe valori maggiori di quelli assunti in 0.

In generale, la condizione necessaria per l’esistenza di un massimo della f soggetta al solo vincolo x³ 0 può esprimersi:

Ñ f(x00 e <Ñ f(x0), x0>=0

 2. Condizioni di Kuhn-Tucker.

Il problema diviene più complicato quando si aggiungono ai vincoli di non negatività delle variabili ulteriori vincoli espressi dalle disuguaglianze j (xb. In ogni caso, è ancora possibile estendere le conclusioni raggiunte nel paragrafo precedente per determinare le nuove condizioni necessarie per l’esistenza di soluzioni al problema. Queste condizioni sono dette di Kuhn-Tucker:

Ñ L(x0; <Ñ L(x), x>=0; x³ 0

j (xb; l T Ÿ [b-j (x)]=0; l ³ 0

dove L(x) è la Lagrangiana del problema definita come:

L(x) = f(x) + l T Ÿ [b-j (x)]

Le condizioni della prima riga sono analoghe a quelle del paragrafo precedente. Per le condizioni della seconda riga, osserviamo che considerando l ³ 0 ne segue che l T Ÿ [b-j (x)]=0 è vera se e solo se sono nulle le componenti di b-j (x) corrispondenti a componenti non nulle di l .

Se consideriamo la Lagrangiana una funzione anche di l il problema può riscriversi nella forma:

L(x,l ) = f(x) + l T Ÿ [b-j (x)]

e le condizioni di esistenza sono:

L0; Lx=0; x³ 0

Ll £ 0; Ll Ÿ l =0; l ³ 0

dove Lx e Ll sono i vettori riga contenenti rispettivamente le n derivate parziali rispetto alle xi e le p derivate parziali rispetto alle l i.

Il punto di ottimo soluzione del problema dipende, ovviamente, dal vettore dei termini noti b che appare nel vincolo. E’ possibile allora costruire una funzione che associa ad ogni vettore b il valore f*(b) del massimo e, è possibile dimostrare, che Ñ f*(b)=l 0, cioè il valore dell’i-esimo moltiplicatore di Lagrange relativo al punto di ottimo coincide con j f*/j bi. Questo consente di conoscere quanto varia il punto di ottimo al variare infinitesimale di b.

 3. Teorema del punto di sella di Kuhn-Tucker.

Se x0 e l 0 sono tali che:

L(x, l 0) £ L(x0, l 0) £ L(x0, l )

per ogni x³ 0 e l ³ 0, allora x0 è soluzione del problema di ottimo. La condizione predetta è sufficiente per caratterizzare (x0, l 0) come un punto di sella di L(x,l ) in quanto esprime il fatto che esso è un punto di massimo della Lagrangiana tra tutti gli x ammissibili ed è invece un punto di minimo tra tutti i l ammissibili.

 4. La programmazione lineare.

Il problema di programmazione lineare in n variabili consiste nel determinare l’ottimo di una funzione lineare in n variabili soggette a vincoli espressi da equazioni o da disequazioni lineari oltre ai vincoli di non negatività. Il problema può essere posto nella forma:

f(x) = cT Ÿ x = Max

j (x) = Ax £ b

x ³ 0

dove c e x sono vettori di En, per cui f(x) = cT Ÿ x = c1x1 + c2x2 + ... + cnxn è una funzione lineare e A=[aij] è una matrice p*n e quindi anche j (x) = Ax è una funzione lineare.

La soluzione del sistema dei vincoli individua un iperpiano dello spazio Sn e la soluzione del problema si trova sempre sulla frontiera della regione ammissibile ed in particolare è unica se corrisponde ad un suo vertice, altrimenti non è unica.

 4.1 Metodi risolutivi.

4.1.1. Metodo grafico.

Per determinare i massimi ed i minimi di una funzione lineare, con dominio dei vincoli un poligono, è sufficiente calcolare il valore della funzione nei vertici del poligono. Il massimo di questi valori rappresenta il punto in cui la f assume valore massimo viceversa per il minimo.

Riassumendo il metodo grafico si applica percorrendo i seguenti passi:

  • determinare la regione delle soluzioni ammissibili mediante la rappresentazione grafica dei vincoli sul piano;

  • se il dominio dei vincoli è un poligono calcolare il valore della funzione obiettivo nei vertici e ricavare il vertice in cui la funzione assume valore massimo; se la regione delle soluzioni è illimitata, esaminare l’andamento delle linee di livello per desumere se esiste un vertice che ottimizza la funzione.

Nelle definizioni appena date si è ipotizzato che la funzione obiettivo sia in due variabili: il metodo può applicarsi anche a problemi più complessi con lo svantaggio però di aumentare notevolmente la difficoltà di rappresentazione grafica e di risoluzione del sistema.

1. Esempio.

Un’industria ha in lavorazione due prodotti P1 e P2 per la cui produzione utilizza due macchine M1 e M2. Per ogni unità di P1 sono necessarie 1 ora della macchina M1 e 3 ore della M2; per ogni unità di P2 sono necessarie 2 ore della M1 e 2 ore della M2. Inoltre il prodotto P1 viene rifinito manualmente, e, al massimo, se ne rifiniscono 18 pezzi alla settimana. La macchina M1 può lavorare al massimo per 40 ore alla settimana e la M2 per 60 ore alla settimana. A parità di costi si vuole conoscere quale sia la combinazione produttiva più conveniente sapendo che ogni unità di P1 è venduta a £ 16.000 e ogni unità di P2 a £ 10.000, nell’ipotesi che ogni quantità prodotta sia venduta.

Dette x1 e x2 le quantità di P1 e P2 è possibile costruire il seguente modello matematico:

z = 16.000x1 + 10.000x2 Þ Max

x1 + 2x2 £ 40

3x1 +2x2 £ 60

x1 £ 18

x1 ³ 0

x2 ³ 0

che è rappresentabile:

 

L’area ammissibile è data dal poligono di vertici OABCD dove: O(0,0), A(18,0), B(18,3), C(10,15), D(0,20). Queste coppie di valori rappresentano le soluzioni ammissibili di base e il valore della funzione nei vertici del poligono è:

z(O)= 0

z(A)=288.000

z(B)=318.000

z(C)=310.000

z(D)=200.000

La funzione z è massima nel vertice B, perciò risulta che l’ottimo della funzione obiettivo si ha con una produzione settimanale di 18 unità di P1 e 3 unità di P2; il ricavo sarà di £ 318.000.

4.1.2. Metodo del simplesso.

Il metodo del simplesso, dovuto al matematico G.B. Dantzig, è un algoritmo che permette, attraverso un numero finito di iterazioni, di passare da una soluzione ammissibile di base alla soluzione ottima (naturalmente se il problema ammette soluzione, ossia se i vincoli sono compatibili e quindi l’insieme delle soluzioni ammissibili non è vuoto).

Il procedimento è il seguente:

  • si determina una prima soluzione ammissibile di base e si calcola il corrispondente valore di z;

  • si passa da questa prima soluzione ad una seconda soluzione ammissibile di base che migliori il valore di z, modificando i valori delle incognite della prima soluzione in modo che una variabile, che prima era nulla, entri nella base e ne esca un’altra;

  • si procede successivamente finché si arriva alla soluzione ottima.

Consideriamo una funzione obiettivo di n variabili:

z = f(x1, x2, ..., xn) = c1x1 + c2x2 + ... + cnxn

soggetta a:

a11x1 + a12x2 + ... + amnxn £ b1

a21x1 + a22x2 + ... + amnxn £ b2

....

am1x1 + am2x2 + ... + amnxn £ bm

x³ 0

tale sistema di disequazioni si può trasformare in un sistema di m equazioni aggiungendo m variabili supplementari:

a11x1 + a12x2 + ... + a1nxn + xn+1 = b1

a21x1 + a22x2 + ... + a1nxn + xn+2 = b2

....

am1x1 + am2x2 + ... + amnxn + xn+m = bm

x³ 0

Le variabili supplementari, anch’esse non negative, rappresentano le differenze tra i secondi e i primi membri delle disuguaglianze e sono perciò dette anche variabili scarto o slack variables.

 

  1. Esempio.

Applichiamo il metodo del simplesso all’esempio proposto nel paragrafo precedente che era stato così definito:

z = 16.000x1 + 10.000x2 Þ Max

che è possibile scrivere come:

z - 16.000x1 - 10.000x2 = 0 Þ Max

 

x1 + 2x2 £ 40

3x1 +2x2 £ 60

x1 £ 18

x1 ³ 0

x2 ³ 0

  • Introduzione delle slack variables al fine di trasformare le disequazioni in equazioni senza che venga alterato il significato dei vincoli:

x1 + 2x2 + x3 = 40

3x1 + 2x2 + + x4 = 60

x1 + + x5 = 18

xi ³ 0 (per i= 1, 2, ...5)

  • Determinazione della prima soluzione ammissibile di base ponendo uguali a zero le prime n variabili:

x1 = 0, x2 = 0

  • Determinazione del corrispondente valore delle slack variables:

x3 = 40, x4 = 60, x5= 18

Si ha quindi:

x1 = 0

x2 = 0

x3 = 40

x4 = 60

x5= 18

a cui corrisponde un valore di z = 0, il peggiore possibile in questo caso. Ora proseguiremo spostandoci su vertici della regione ammissibile individuata dai vincoli che rendono via via la funzione obiettivo sempre maggiore. La soluzione O(0,0) costituisce la prima soluzione ammissibile di base o di partenza.

  • Costruzione della tabella:

V.B.

z

x1

x2

...

xn

xn+1

xn+2

...

xn+m

bi

bi/air

z

1

c1

c2

...

cn

0

0

0

0

 

 

xi1

0

a11

a12

...

a1n

1

0

...

0

b1

b1/a1r

xi2

0

a21

a22

...

a2n

0

1

...

0

b2

b2/a2r

...

...

...

...

...

...

...

...

...

...

 

 

xim

0

am1

am2

...

amn

0

0

...

1

bm

bm/amr

che nel caso specifico equivale:

V.B.

z

x1

x2

x3

x4

x5

bi

bi/air

Z

1

-16.000

-10.000

0

0

0

 

 

x3

0

1

2

1

0

0

40

40/1

x4

0

3

2

0

1

0

60

60/3

x5

0

1

0

0

0

1

18

18/1

Per migliorare la soluzione occorre determinare una nuova soluzione ammissibile di base. Occorre cioè determinare il minimo dei coefficienti negativi delle variabili di z (-16.000) al fine di determinare la variabile entrante (x1). Per determinare la variabile uscente occorre determinare il minimo dei rapporti tra i termini noti e i coefficienti della variabile entrante. Abbiamo così determinato che la variabile entrante è x1 e la variabile uscente è x5.

Applichiamo ora il metodo del pivot dividendo per il pivot tutti gli elementi della riga e mediante combinazioni lineari della riga del pivot con le altre, si fanno diventare zero tutti gli elementi della colonna del pivot: tutto ciò per eliminare la variabile entrante in base dal sistema dei vincoli e dalla funzione obiettivo.

V.B.

z

x1

x2

x3

x4

x5

bi

bi/air

Z

1

0

-10.000

0

0

16.000

 

 

x3

0

0

2

1

0

-1

22

22/2

x4

0

0

2

0

1

-3

6

6/2

x1

0

1

0

0

0

1

18

18/0

Questa volta, la variabile entrante è x2 e quella uscente è x4:

V.B.

z

x1

x2

x3

x4

x5

bi

bi/air

Z

1

0

0

0

5.000

1.000

 

 

x3

0

0

0

1

-1

-4

16

 

x2

0

0

1

0

1/2

-3/2

3

 

x1

0

1

0

0

0

1

18

 

A questo punto il procedimento termina in quanto i coefficienti delle variabili non base sono positivi o nulli.

La soluzione è data da:

x1= 18

x2= 3

x3= 16

x4= 0

x5= 0

che comporta il valore massimo di z = 318.000.

I valori di x3, x4, x5, rappresentano la differenza tra primo e secondo membro dei vincoli. In particolare il primo vincolo rappresenta la capacità produttiva della prima macchina (M1) che non risulta, quindi, completamente sfruttata. Il secondo vincolo rappresenta la capacità produttiva della seconda macchina (M2) che ha raggiunto, invece, livelli di saturazione. Il terzo vincolo, invece rappresenta la capacità produttiva per la rifinitura del primo prodotto (P1): anch’essa appare saturata.

BIBLIOGRAFIA

BLASI, Alessandro Matematica per le applicazioni economiche e finanziarie, Roma, Kappa, 1996.

DE ANGELIS, Vanda Metodi della ricerca operativa. Parte prima, Roma, Dipartimento di statistica, probabilità e statistiche applicate: università di Roma "La Sapienza", 1993.

MASON, Francesco Metodi quantitativi per le decisioni, Torino, Giappichelli, 1992.