Problema di PL di PL

Metodi

Metodi matematicimatematici

per per ll’’economiaeconomia e la e la finanzafinanza Prof.ssa

Prof.ssa CristianaCristiana MammanaMammana

PROGRAMMA DEL CORSO PROGRAMMA DEL CORSO

1.1. ProgrammazioneProgrammazione LineareLineare

Definizione del problema ed applicazioni economico-finanziarie

2. IntroduzioneIntroduzione a Matlaba Matlab

Lavorare con vettori e matrici

Grafici di funzioni di una e due variabili Functions ed m-file

3. Programmazione3. Programmazione LineareLineare (segue)(segue)

Due variabili d’azione:

il metodo geometrico il metodo del simplesso il metodo delle due fasi

n variabili d’azione:

il metodo grafico

la tavola del simplesso Cenno alla teoria della dualità:

teoremi sulla dualità

interpretazione economica

Analisi di sensitività

4. PL con PL con MatlabMatlab

Metodo grafico Comando linprog

5. OttimizzazioneOttimizzazione liberalibera e vincolatae vincolata

Massimi e minimi liberi di una funzione di più variabili Condizioni del primo ordine e condizioni del secondo ordine

Massimi e minimi vincolati con vincoli di disuguaglianza Applicazioni economiche e finanziarie

(utilità e domanda, profitto e costo, ottimo paretiano, economia del benessere, modelli di risparmio ottimale, applicazioni al marketing)

6. OttimizzazioneOttimizzazione con con MatlabMatlab

Utilizzo del “Toolbox optimization”

comandi fminsearch, fmincon …

LA PROGRAMMAZIONE LINEARE LA PROGRAMMAZIONE LINEARE

∈ ℜ

≤ =

= =

≥ min ( ),

tale che (1) problema d

Si consideri il seguent i programmazione matematica:

funzione o ( ) 0, 1,...,

( ) 0, 1,..., e

è detta

0

b

n x

i

j

f x x

h x i m

g x

f

j k

x

≤ = ≥

i , 0, ( ) 0, 0 sono i

ettivo

vincoli.

i j

h g x x

∀ ∀ Se è lineare e , sono lineari , allora (1) è u problema di program

NB

mazione linear :

e n

i j

f h g i j

OSSERVAZIONE:

OSSERVAZIONE:

Il problema :

β

∈ ℜ

≥ =

= =

≥ =

max ( ),

tale che ( ) 0, 1,...,

( ) 0, 1,..., , 1,...,

n x

i j

l l

f x x

h x i m

g x j k

x l n

è EQUIVALENTE al problema (1) in quanto:

[ ]

β β

−

≥ ≤

≥ ^' ≥ ^' = −

i problemi e sono ,

vincoli con cambi

- - -

ando segno ai due membri il vincolo

max ( ) min ( ) si riconducono a

si traduce nel vinc

equivalenti

olo 0 ponendo

x x

l l l l l l

f x f x

x x x x

Possiamo considerare, quindi, problemi di PL formalizzati come in (1)

Un problemaproblema di di programmazioneprogrammazione linearelineare può essere formalizzato in una delle seguenti forme:

Problema

Problema di PL di PL

1 n

j=1

min

, 1,..., 0, 1,...,

n

j j j

ij j i

j

c x

a x b i m

x j n

=

⎧ ⎪

⎪ ⎪

≤ =

⎨ ⎪

⎪ ≥ =

⎪ ⎩

∑

∑

min

0

matrice ,

, ,

T x

n m

c x Ax b x

A m n

c x b

⎧ ⎪⎪ ≤

⎨ ⎪ ≥

⎪⎩

×

∈ \ ∈ \

o in forma matriciale:

Forma

Forma canonicacanonica

Forma standard Forma standard

1 n

j=1

min

, 1,..., 0, 1,...,

n

j j j

ij j i

j

c x

a x b i m

x j n

=

⎧ ⎪

⎪ ⎪

= =

⎨ ⎪

⎪ ≥ =

⎪ ⎩

∑

∑

min

0

matrice ,

, ,

T x

n m

c x Ax b x

A m n

c x b

⎧ ⎪⎪ =

⎨ ⎪ ≥

⎪⎩

×

∈ \ ∈ \

o in forma matriciale:

Forma

Forma mistamista

1 n

j=1 n

j=1

min

, 1,...,

, 1,..., 0, 1,...,

n

j j j

ij j i

ij j i

j

c x

a x b i m

d x e i k

x j n

=

⎧ ⎪

⎪ ⎪

≤ =

⎪ ⎨

⎪ ⎪ = =

⎪ ⎪ ≥ =

⎩

∑

∑

∑

min

0

matrice , matrice ,

, , ,

T x

n m k

c x Ax b D x e x

A m n

D k n

c x b e

⎧ ⎪

⎪ ≤

⎨ =

⎪ ⎪ ≥

⎩

×

×

∈ \ ∈ \ ∈ \

o in forma matriciale:

dove:

è la funzione obiettivo,

♦♦ _{1 1 2 2}

1

( ) ...

n

j j n n

j

f x c x c x c x c x

=

= ∑ = + + +

sono le variabili d’azione o decisionali,

♦♦

x i

, 1,..., = n

sono i vincoli.

♦♦ ^{1 1 2 2}

1 1 2 2

... 1,...,

... , 1,..., 0, 1,...,

i i in n i

i i in n i

j

a x a x a x b i m

d x d x d x e i k

x j n

+ + + ≤ =

+ + + = =

≥ =

NB: Dato un problema di PL è sempre possibile passare da una forma all’altra,

Infatti:

+ − =

+ − ≤ + − ≥

1 2 3

1 2 3 1 2 3

-

esemp

un eventuale si trasforma

in

(per il vincolo 2 3 6 è equivalente alla co

vincolo di uguaglianza due vin

ppia di vincoli

coli di disuguaglia

2 3 6 e 2 3 6

o

a

) z

i

n

x x x

x x x x x x

- Viceversa: un un vincolovincolo di di disuguaglianzadisuguaglianza sisi trasformatrasforma in in unouno di uguaglianzadi uguaglianza::

≤

≥ =

Se i vincoli sono del tipo ,

si può introdurre un vettore di componenti:

0 1,...,

dette , che rappresenta la quantità in difetto al

var

pri Il vincolo vien

mo membro.

iabili slack (scart e t

o)

j

Ax b s

s j m

Im

+ =

rasformato in : Ax s b

ogni problema di PL è riconducibile alla forma standard

Esempio

Esempio 1: PROBLEMA DEL CONSUMATORE1: PROBLEMA DEL CONSUMATORE

+

= −

−

∈ ℜ

i i

- Sia x (i 1,..., ) la del bene , - sia p il del bene ,

- sia il dell'individuo quantità do

,

- sia ( ) la , LINE

mandata prezzo

reddito disponibile

funzione di utilità del consumatore

n i esimo

i esimo R

U x ARE

α α α

= + + +

+ + + ≤

≥ ∀

1 1 2 2

1 1 2 2

i

Il problema della ricer massima uti

max ( ) ...

t

problema di PL in forma canonica lità con il vincolo d

ca della

è dato da:

e

.c. . i

d

..

x 0,

bilancio

è un !

x n n

n n

U x x x x

x p x p x p R

i

Esempio

Esempio 2: PROBLEMA DEL TRASPORTO2: PROBLEMA DEL TRASPORTO

quantità da spedire costo unitario di sp

- Sia la dall'origine alla destinazione ,

- sia il dall'origine alla destinazione , - s

edizione quantità richies

ia la ta dalla destinazione , - s

ij ij

j

x i j

c i j

q j

quantità totale p

ia la p_i rodotta nell'origine . i

problema di PL in forma

ed è

mi un

sta!

1 1

n

i=1 m

j=1

min

0

n m

T

ij ij

x i J

ij j

ij i

ij

c x c x

x q

x p

x

= =

⎧ =

⎪ ⎪

⎪ =

⎪ ⎨

⎪ ≤

⎪ ⎪

⎪ ≥ ⎩

∑∑

∑

∑

Il problema della minimizzazione dei costi di trasporto è dato da:

Esempio

Esempio 3: PRODUCTION PLANNING3: PRODUCTION PLANNING

−

− quantità di prodotto pianificata

quantità di prodotto che

- sia la per il mese ,

- sia y la per il mese ,

- sia

deve essere immagazzinata costo di produzione

il per unità di be e nen

i i i

x i esimo

i esimo

c −

−

−

l mese e

- sia il nel mese ,

- sia la

costo di immagazzinamento per unità di bene

capacità produttiva m nel mese ,

- sia la nel mes

assima dell'impianto domanda di prodotto e

i i i

i esimo

r i esimo

m i esimo

d −

0 disponibilità iniziale di pro

,

- sia la dotto in magazzino

i esimo M

minimizzazione del costo complessivo di produzione e di immagazziname

Il problema della

può essere formalizzato come s

nto egue:

problema di PL in forma

ed è un mista!

Esempio 4: GESTIONE DEL PORTAFOGLIO

tre titoli flussi fina

Dati che generano i seguenti alle scadenze 1 e 2 per un euro inves

nziari

tito:

Per ciascuno dei tre titoli offerti sul mercato, i flussi garantiti investendo una lira sono:

1 2 3

- Siano , , le quantità investite in ciascuno dei tre ti dotazione iniziale di capital

toli.

- sia la e pari a 3 euro.

x x x

vin Il

col

problema della

determinato dai flussi al tempo t=2,

- con il o che in t=1 sia disponibile almeno 1 eu - e con il

ro vincolo

massimizzazione dell'incass

, si

o fin

può f

di bi ormali

lanc zzar

io

ale

e come segue:

1

problema di PL in forma

ed è un mista!

Esercizio

Si trasformi il seguente problema di PL nella forma standard:

♦ Il problema può essere ricondotto alla forma canonica:

♦ e dalla forma canonica si passa alla forma standard, forma standard introducendo due variabilidue variabili slack:slack

Alcune

Alcune definizionidefinizioni

♦ Si definisce soluzionesoluzione ammissibileammissibile di un problema di PL ogni

∈ ℜ ≤ ≥

0 ⁿ che soddisfa i vincoli, cioè t.c. 0 e 0 0

x Ax b x

♦ Si definisce soluzionesoluzione ammissibileammissibile ottimaleottimale di un problema di PL ogni soluzione ammissibile in corrispondenza della quale la funzione obiettivo assume il valore minimo.

♦ Si definisce regioneregione ammissibileammissibile l’insieme delle soluzioni ammissibili.

Due variabili

Due variabili d'azione d'azione

Il metodo geometrico Il metodo geometrico

♦ La regione ammissibileregione ammissibile (o dominio dei vincoli) è un poligono convesso (perché intersezione di semipiani), chiuso ma non necessariamente limitato.

♦ Le curve di livello curve di livello z=kz=k della funzione obiettivo sono rette.

Soluzione

Soluzione per via per via graficagrafica del del problemaproblema:: 1. si rappresenta sul piano la regione ammissibile,

2. si traccia la retta di livello z=0, le linee di livello sono un fascio di rette parallele,

3. dall'andamento delle rette di livello (direzione in cui la quota aumenta) si deduce se la funzione ammette minimo.

Il puntoIl punto di minimodi minimo, se esiste, se esiste, , èè suisui vertici del poligonovertici del poligono

Per determinare il punto di minimo si calcola il valore della funzione obiettivo nei vertici del poligono,

il minimo di questi valori è il minimo della funzione.

Esempio 1: unica soluzione

Consideriamo la funzione: con

se ne vuole determinare il minimo.

se ne vuole determinare il minimo.

A

B C

D

z=20

z=6

Nella figura sono rappresentate le rette che

soddisfano i vincoli con il segno di uguaglianza

La regione ammissibileregione ammissibile è il poligono convesso di vertici

A(3,0), B(10,0), C(2,4), D(2,1)

I verticivertici sono i punti di intersezione dei lati che delimitano il poligono

le rette di livellorette di livello z=k sono date da

1

2 3

2

3 x

x = k −

cioè sono rette decrescenti che si allontanano dall'origine al crescere di si allontanano dall'origine al crescere di k k (la freccia(la freccia indicaindica la direzionela direzione in cui la quota aumentain cui la quota aumenta).).

NB:NB: L'intersezione tra le rette di livello e la regione ammissibile è non vuota.

La direzione ammissibile èè un vettoreun vettore uscenteuscente dada un verticeun vertice cheche “punta“punta”” verso la

verso la regioneregione ammissibile:ammissibile

A

B C

D

Riprendendo l’esempio, la la funzionefunzione assume ilassume il minimominimo in A(3,0)in A(3,0) al quale corrisponde il valore z=6.

In questo caso esiste un'unica soluzione

Infatti: nessunnessun latolato del poligono del poligono èè parallelo alle rette di livelloparallelo alle rette di livello, , quindi

quindi il minimo il minimo èè un vertice della regione ammissibile, punto un vertice della regione ammissibile, punto di intersezione di due

di intersezione di due vincolivincoli..

Esempio 2: infinite soluzioni

Al contrario: se un latose un lato del del poligonopoligono èè paralleloparallelo ad ad unauna rettaretta di di livello, allora la funzione ha infinitilivello infiniti minimiminimi o o massimimassimi (in tutti i punti del lato)

Esempio grafico di infiniti minimi

Esempio 3: problema impossibile

Consideriamo il problemaproblema: tale che

Esempio

Esempio 3: 3: problemaproblema impossibileimpossibile

Il dominio dei vincolidominio dei vincoli è costituito da

due regioni che hanno intersezione vuota, regioni che hanno intersezione vuota

non esiste quindi nessuna soluzione

non esiste quindi nessuna soluzione ammissibileammissibile..

Problemi di questo tipo si dicono impossibili

questi non ammettono soluzione poiché la regione ammissibile è vuota

Esempio 4:problema illimitato

Consideriamo il problemaproblema:

La regione ammissibile è illimitata ed esistono soluzioni ammissibiliesistono soluzioni ammissibili ma nessuna è ottima perché

la funzione obiettivo

la funzione obiettivo èè illimitataillimitata inferiormenteinferiormente nellanella regioneregione ammissibile.ammissibile

Problemi di questo tipo si dicono illimitati

questi

questi non non ammettonoammettono soluzionesoluzione!!

NB:NB: se la regione ammissibile è illimitata:

-I vertici del poligono vengono detti punti estremi

-un vettore uscente da un punto estremo che appartiene al ‘lato’

illimitato del poligono viene detto direzione estrema

Esempio

Esempio 5:regione illimitata5:regione illimitata, problema, problema limitatolimitato

N.B. Se la regione ammissibile Se la regione ammissibile èè illimitata allora non èillimitata allora non è necessariamentenecessariamente vero che il problema

vero che il problema èè illimitato.illimitato Esempio

Il dominio dei vincoli è la regione illimitataregione illimitata avente per contorno una spezzata aperta.

I punti estremipunti estremi sono:

) 0 , 6 ( 3 , , 4 3

10 B

A ⎟

⎠

⎜ ⎞

⎝

⎛

La La funzionefunzione ha minimo in Aha minimo in A con valore con valore

3

= 3 2 z

Esempio

Esempio 6:metodo del simplesso6:metodo del simplesso

Il metodo del simplesso Il metodo del simplesso

Il metodo del simplessometodo del simplesso è un algoritmo iterativoalgoritmo iterativo che permette di risolvere problemi di programmazione lineare nel caso in cui:

- il vettore dei termini noti ha tutte le componenti non negative - i vincoli si presentano tutti con il segno “=”

Definizione Definizione

Una soluzione ammissibile di base è una soluzione ammissibile con soluzione ammissibile con k-k-mm variabili nulle, dove kvariabili nulle, dove k èè il numero di variabili (decisionali e il numero di variabili (decisionali e ausiliarie) e

ausiliarie) e mm èè il numero dei vincoli.il numero dei vincoli.

Teorema Teorema

Condizione

Condizione necessarianecessaria e sufficientee sufficiente affinchaffinchéé xx siasia puntopunto estremoestremo (vertice(vertice)) della

della regioneregione ammissibileammissibile èè cheche siasia soluzionesoluzione di base ammissibiledi base ammissibile perper AxAx==bb

Esempio: dato il seguente problemaproblema in forma standard:in forma standard:

Per ilPer il teoremateorema precedente, siprecedente individuaindividua unauna soluzione ammissibilesoluzione ammissibile di basedi base e se ne cerca un'altraun'altra in corrispondenza della quale il valore assunto dalla in corrispondenza della quale il valore assunto dalla funzione obiettivo non risulti superiore al precedente

funzione obiettivo non risulti superiore al precedente.

Assegnando il valore zero alle variabili decisionalizero alle variabili decisionali, si determinano i valori delle variabili di slack (o variabili ausiliarie):

12

,

2

1

= s =

s

(0,0,2,12)

(0,0,2,12) èè unauna soluzionesoluzione ammissibileammissibile di base inizialedi base iniziale

Il valore della funzione obiettivo corrispondente a questa soluzione è z=0z=0

Risolvendo rispetto alle variabili ausiliarie, si ottiene:

Un sistema scritto in questa forma si chiama dizionario le variabili che sono a sinistra sono le variabili di base

le altre variabili non di base.

N.B. Le variabili non di base hanno valore corrente zero.

Considerando la funzione obiettivo

si vede che incrementando una delle variabili decisionaliincrementando una delle variabili decisionali il valore di z diminuisce:

- Le variabilivariabili decisionalidecisionali sono quindi candidate ad entrare in base, - le variabili variabili ausiliarieausiliarie (di slack) sono candidate ad uscirecandidate ad uscire.

La variabile entrante è quella che nell'espressione della funzione nell'espressione della funzione obiettivo ha coefficiente negativo di massimo modulo obiettivo ha coefficiente negativo di massimo modulo, la variabile uscente è quella che impone la limitazione piimpone la limitazione piùù stretta alla stretta alla crescita della variabile entrante:

crescita della variabile entrante:

2 2

: : s uscente variabile

x entrante variabile

Il nuovo dizionario è

La nuovanuova soluzione ammissibilesoluzione ammissibile di base è:di base

0 ,

5 ,

3 ,

0 _{2 1 2}

1 = x = s = s =

x

Il corrispondente valore della funzione obiettivo è z=-z=-4848 poiché

1 1 2 1 2

1 1

10 16 3 48 6 4

4 4

z = − x − ⎛⎜⎝ − x − s ⎞⎟⎠ = − − x + s

che è migliorato!

…Procedendo in modo analogo, all'iterazione successivaall'iterazione successiva risulta:

1 1

uscente variabile

entrante variabile

s x

La nuova soluzione ammissibile di basesoluzione ammissibile di base è

0 ,

0 ,

2 ,

4 _{2 1 2}

1 = x = s = s =

x

e le equazioni diventano

La funzione obiettivo è data da

Non Non èè possibile migliorare ancora la funzione obiettivo in quanto tutte possibile migliorare ancora la funzione obiettivo in quanto tutte le variabili presenti hanno coefficienti

le variabili presenti hanno coefficienti positivi!positivi!

quindi la soluzione ottima è

2 ,

4 ₂

1 = x =

x

con valore della funzione obiettivovalore della funzione obiettivo

−72

= z

Significato geometrico Significato geometrico

Regione ammissibile del problema considerato

•La prima soluzione prima soluzione ammissibileammissibile di basedi base corrisponde all'origineorigine e il valore della funzione obiettivo è zero.

•Dopo la prima iterazione abbiamo trovato un'altra soluzione ammissibile di base con valore minore della funzione obiettivo, a cui corrisponde il vertice (0,3)

(la linea di livello che passa per quel punto corrisponde ad una quota minore).

•L'iterazione successiva ci porta su un altro verticeun altro vertice e arriviamo alla soluzione ottima (arresto).

I passi fondamentali del metodo del simplesso sono:

1) passo di inizializzazione scelta di una soluzione ammissibile di base da cui partire

2) passo di iterazione scelta della variabile entrante e di quella uscente e applicazione dell'algoritmo.

- La variabile entrante è una variabile (non di base) che ha coefficiente negativo nell'espressione della funzione obiettivo.

Se più variabili sono candidate ad essere entranti, si sceglie quella con coefficiente più grande in valore assoluto.

Se non esistono variabili entranti (perché nessuna variabile ha coefficiente negativo), allora la soluzione trovata è ottima e l'algoritmo si arresta (criterio d'arresto).

- La variabile uscente è quella che impone la limitazione più stretta alla crescita della variabile entrante.

Se non esistono variabili uscenti allora il problema è illimitato.

3) passo di arresto verificare se la soluzione trovata è ottima.

Osservazione

Si noti che il software matematico MATLAB sceglie la variabile entrante e la variabile uscente in base alla regola del più piccolo indice:

se più variabili sono candidate ad essere entranti (o uscenti), si sceglie quella con indice più piccolo.

Il metodo delle due fasi

Se l'origine non è ammissibile si presenta il problema di determinare una soluzione di base iniziale.

Dato il problema

se qualche componente del vettore dei termini noti è negativa, allora l'origine non corrisponde a una soluzione ammissibile e quindi non può essere scelta come soluzione iniziale

Il problema viene risolto con il metodo delle due fasi Si introduce un problema ausiliario:

Le componenti del vettore

si chiamano variabili artificiali

Si noti che se il problema iniziale ha n variabili e m vincoli, quello ausiliario ha m variabili artificiali e m vincoli

Prima di introdurre il problema ausiliario, occorre:

• trasformare il problema iniziale in forma standard

• ricondursi a

≥ 0

b

Vale il seguente:

Teorema Il problema originale ha una soluzione ammissibile se e solo se il problema ausiliario ha una soluzione ottima con tutte le variabili artificiali uguali a zero.

Per il problema ausiliario esiste sempre una soluzione di base ammissibile iniziale:

b x

x =0 e ^a =

Il valore ottimo del problema ausiliario è sempre maggiore o uguale a zero, è zero se e solo se esiste una soluzione ammissibile per il problema originario.

I fase si risolve il problema ausiliario

II fase se il problema ausiliario ha una soluzione ottima con valore zero, allora questa è una soluzione ammissibile di base per il problema originario e si può applicare il metodo del simplesso. Altrimenti il problema è impossibile.

Esempio

Si trasforma il problema in forma standard e si moltiplica la seconda equazione per -1:

Il problema ausiliario è:

da cui

risolviamo con il metodo del simplesso

xa

x₂, variabileuscente ₂ entrante

variabile

xa

s₁, variabile uscente ₁ entrante

variabile

0 ,

0 con

ottima

soluzione x₁^a = x₂^a =

Il problema originale ammette, quindi, una soluzione ammissibile

Per individuarla, cancelliamo dalle equazioni trovate le variabili artificiali (perché hanno esaurito il loro ruolo) e scriviamo la funzione obiettivo rispetto alle variabili non in base:

Non esistono variabili uscenti, il problema è pertanto illimitato.

n variabili d'azione (n > 2)

Il metodo grafico

Un problema di PL in n variabili è riconducibile a un problema di PL in due variabili se nel sistema dei vincoli compaiono n - 2 equazioni dalle quali ricavare n – 2 variabili in funzione delle restanti due.

Esempio

1 2

1 2 3 1 2 3

300 500

, , , , 200 ,150 , 450

O O q q

D D D D D D q q q

Gli stabilimenti e producono e di merce che viene inviata

ai depositi . Le capienze di sono : .

Data la seguente matrice dei costi di trasporto per quintale, determinare il piano di trasporto ottimo

1 2 3 1 1 2 3

1 2 3 2 1 2 3

- , , , ,

- , , , ,

x x x O D D D

y y y O D D D

Siano :

le quantità prodotte in e inviate a le quantità prodotte in e inviate a

il problema ammette il seguente modello matematico :

Da cui

Risolviamo con il metodo geometrico

La regione ammissibile è il poligono di vertici:

O(0,0), A(200,0), B(200,100), C(150,150), D(0,150) z assume il minimo valore in B, con z(B)=9550