Dispensa Progettazione Lineare Fersini Olivieri PDF

Preview

Summary

Cattedra diMetodi Quantitativi per ilManagement e la FinanzaParte I:appuntidiPROGRAMMAZIONE LINEAREP. Fersini, G. Foschini, G. Olivieria. 2009-Indice 1 INTRODUZIONE 2 IL PROBLEMA GENERALE DI ASSEGNAZIONE 3 LA DETERMINAZIONE DELLE SOLUZIONI 4 LA LOGICA DEL SIMPLESSO 5 LA SOLUZIONE GRAFICA 6 LA DETERM...

Description

Cattedra di

Metodi Quantitativi per il Management e la Finanza

Parte I:

appunti

di

PROGRAMMAZIONE LINEARE

P. Fersini, G. Foschini, G. Olivieri a.a. 2009-2010

1

Indice 1

INTRODUZIONE

3

2

IL PROBLEMA GENERALE DI ASSEGNAZIONE

4

3

LA DETERMINAZIONE DELLE SOLUZIONI

7

4

LA LOGICA DEL SIMPLESSO

9

5

LA SOLUZIONE GRAFICA

6

LA DETERMINAZIONE DELLE SOLUZIONI IN EXCEL 16

7

QUALCHE RICHIAMO TEORICO

8

ALCUNE COMPLICAZIONI NELL’USO DEL SIMPLES-

12

SO 9

28

PRIMALE E DUALE 9.1

22

Analisi di sensibilità

31 . . . . . . . . . . . . . . . . . . . . . . .

10 Esercizi proposti

38

40

2

1 INTRODUZIONE La programmazione lineare è parte della “programmazione matematica”, ovvero quell’insieme di regole e di tecniche che hanno la …nalità di ottimizzare determinate attività da svolgere con risorse limitate, come ad es., la produzione di un bene in cui le risorse (materie prime, ore lavorative, capitali, etc.) sono limitate. La programmazione matematica si pone l’obiettivo di trovare la combinazione ottima di risorse che permettono di ottenere il massimo pro…tto per l’azienda, o il minimo costo, e così via. La programmazione matematica può essere:



con funzioni di tipo continuo (funzioni continue di variabili continue)



con funzioni lineari o non lineari, a seconda se godono o meno della



statica, se si studia il problema a sé stante, o dinamica, se lo studio si



deterministica, se tutti gli elementi del problema sono noti o deter-

o discrete1 ;

proprietà di proporzionalità;

evolve nel tempo;

minabili a priori o probabilistica altrimenti.

La diversa combinazione di tali argomenti identi…ca diverse branche della programmazione matematica. Ci occuperemo in questa sede di programmazione lineare, che risolve i problemi lineari, continui, statici e deterministici di ottimizzazione2 . In generale, in un problema di ottimizzazione si cerca di massimizzare (o minimizzare) una speci…ca quantità (obiettivo) che dipende da un numero …nito di variabili di input, che possono essere dipendenti o indipendenti fra loro o possono essere collegate da uno o più vincoli.

Esempio 1 il problema sotto i vincoli

1

min Z = x12 + x22



x1  x2 = 3 x2  2

Particolare interesse riveste il cosiddetto “programma intero”, in cui le variabili di

input possono assumere solo valori interi. 2 Ricordiamo che una funzione f (x) è lineare se dove

f (x) = f (x) e f (x + y) = f (x)+ f (y),

x e y indicano dei vettori con n componenti.

3

è un problema di ottimizzazione rispetto all’obiettivo Z . Le variabili di input sono x1 e x2 e i vincoli speci…cano che la variabile x1 deve sempre essere maggiore di due unità rispetto alla seconda variabile, che deve comunque essere non minore di 2.

In ogni programma matematico si cerca

una

soluzione.

Se esiste una

serie di soluzioni ugualmente ottimali esse sono tutte ammissibili (solo la formulazione dei vincoli può assegnare una speci…ca preferenza).

2

IL PROBLEMA GENERALE DI ASSEGNAZIONE

Può essere esempli…cato attraverso la determinazione di quali macchine dovrebbero essere impiegate per ottenere i prodotti che richiedono l’uso alternativo di insiemi di risorse. Consideriamo, ad esempio, una fabbrica che produce in quantità da determinare

x1 ; x2 ; :::; xn

n

di¤erenti prodotti

utilizzando varie combinazioni di

m

di¤erenti macchinari. Ogni unità del prodotto con

j

= 1; 2; : : : n;

ed

i

j

richiede

= 1; 2; : : : ; m.

(di tempo) per la prima macchina è per l’

i

esima è

bi ,

prodotto venduto è



ai;j

b1 ,

. . . , per l’m esima è cj .

unità di tempo sulla macchina i,

L’ammontare totale della disponibilità per la seconda macchina è bm .

b2 ; : : : ;

Il guadagno per ogni unità di

Appare subito chiaro che il modello è una rappresentazione astratta della realtà in quanto presuppone che il guadagno sia direttamente proporzionale alla quantità venduta, qualunque essa sia. Inoltre la materia prima, in questo caso l’uso delle macchine, per ogni processo è proporzionale al suo livello di utilizzo (non esistono economie di scala). Possiamo riassumere le informazioni in una tabella, detta schema generale di assegnazione.

4

Tabella 1: Lo schema generale di assegnazione

Prodotti

numero di ore disponibili*

1

2

...

j

...

n

R

1

a11

a12

...

a 1j

...

a 1n

b1

I

2

a21

a22

...

a 2j

...

a 2n

b2

S

3 ...

a31

a32

...

a 3j

...

a 3n

b3

i

ai1

a12

...

aij

...

ain

bi

a m1

a m2

...

amj

...

amn

bm

c1

c2

...

cj

...

cn

O R S

...

E

m

.. .

...

.. .

...

.. .

.. .

...

...

...

Guadagno Unitario

*nel periodo considerato Nella Tabella 1 l’elemento

2 66 =6 4

3 77 7 5

aij

indica la quantità di risorsa “i” necessaria a

produrre il prodotto “j ”; la colonna

j;

il vettore

c =c =



b =b

b1 b2

.. .



j

è lo schema di produzione del prodotto

indica la disponibilità delle risorse; il vettore

bm c1

c2

:::

cn

è il vettore dei coe¢cienti della funzione obiettivo

(ad esempio il guadagno associato alla vendita di ciascun prodotto). Sia il nostro obiettivo quello di massimizzare il guadagno totale (funzione obiettivo-FO). La FO è una funzione lineare, indichiamo con dipendente e con

xj

Z

la variabile

le variabili indipendenti:

X n

max Z =

cj  xj

(1)

j =1

o, in termini matriciali, indicando con

c

il vettore (riga) dei coe¢cienti

della FO e con x il vettore (colonna) delle quantità di produzione dei prodotti:

max Z = c  x

(2)

La FO, espressa dalla (1) o dalla (2) è soggetta a vincoli di disuguaglianza lineari:

5

8 > > > > > < > > > > :

a11 x1 a21 x1

ai1 x1

a m1 x 1

+ a12 x2 + ::: + a1j xj + ::: + a1n xn + a22 x2 + ::: + a2j xj + ::: + a2n xn

 b1  b2

+ ai2 x2 + ::: + aij xj + ::: + ain xn

b

.. .

.. .

+ am2 x2 + ::: + amj xj + ::: + amn xn

(3)

i

b

m

Inoltre, poiché le quantità dei prodotti da produrre non possono essere negative, si devono aggiungere anche i “vincoli di non negatività”:

8 x1  0 > > x2  0 > > < ... x  0 > > .. > > > : . x  0

(4)

j

n

Indicando con

A

la matrice dei coe¢cienti tecnici:

2 66 66 A =6 66 4

a11

a12

...

a 1j

...

a 1n

a21

a22

...

a 2j

...

a 2n

ai1

a12

...

aij

...

ain

a m1

a m2

...

amj

...

amn

.. .

.. .

.. .

.. .

.. .

.. .

...

...

3 77 77 77 7 5

i vincoli (3) e (4) possono essere scritti in forma matriciale (5):



Ax b x  0

Il sistema (3) (4) o (5) prende il nome di

2

(5)

sistema dei vincoli.

L’insieme

dei valori x Rn che soddisfa il sistema (3) prende il nome di soluzione del problema. Se l’insieme delle soluzioni soddisfano anche i vincoli di non negatività, si parla di soluzione equazioni

m

possibile.

Generalmente il numero delle dis-

è minore del numero delle variabili

n;

se ciò non accade non

possiamo essere certi che esista una soluzione possibile. Il primo passo per trovare la soluzione ottima è quello di formalizzare il problema, ovvero pervenire alla scrittura della Tabella 1, del sistema dei vincoli e della FO.

6

Esempio 2 Un’azienda produce su commessa due tipologie di agende da regalo: il tipo “traveler” –di design sportivo- e il tipo “executive” –di design elegante. La lavorazione del tipo traveler richiede la metà delle ore lavorative richieste per la produzione del tipo executive. Se si producessero solo agende traveler, la capacità produttiva sarebbe di 800 agende al giorno. L’azienda ha a disposizione cuoio per produrre non più di 600 agende in totale, ciascuna tipologia di agenda richiede la stessa quantità impiegata di cuoio. L’azienda committente fornisce le altre materie prime e paga executive e

e3,00 per ogni agenda traveler.

e5,00

per ogni agenda

Formalizzare matematicamente

il problema, sapendo che l’azienda ha l’obiettivo di massimizzare il proprio guadagno. prodotti

cuoio ore lavorative

E

T

1

1

600

2

1

800

5

3

quindi il problema diviene:

8 > < > :

max Z = 5x1 + 3x2 x1 + x2  600 2x1 + x2  800 x1  0 x2  0

3

LA DETERMINAZIONE DELLE SOLUZIONI

Un problema di PL è costituito da un sistema di disequazioni, che non può essere risolto in modo “automatico”: occorre trasformare le disequazioni in equazioni, introducendo delle “variabili aggiuntive” o variabili xn+2 ; :::; xn+m ,

8 >> >> < >> >>:

slack, xn+1 ;

una per ciascuna disequazione del sistema dei vincoli:

a11 x1 a21 x1

ai1 x1

a m1 x 1

+ a12 x2 + ::: + a1j xj + ::: + a1n xn + xn+1 = b1 + a22 x2 + ::: + a2j xj + ::: + a2n xn + xn+2 = b2 .. .

+ ai2 x2 + ::: + aij xj + ::: + ain xn + xn+i = bi .. .

+ am2 x2 + ::: + amj xj + ::: + amn xn + xn+m = bm 7

(6)

Le

m

variabili

slack

rappresentano le quantità even-

xn+1 ; xn+2 ; :::; xn+m

tualmente non utilizzate delle

m

risorse.

I vincoli sono ora rappresentati da un sistema di 3; 4

incognite, lineari: il sistema è dunque inde…nito sceglieremo (casualmente)

m

equazioni in

n

+m

. Per trovare la soluzione

incognite e calcoleremo la soluzione. Se otte-

niamo una soluzione, essa prende il nome di m

m

soluzione di base, è costituita da

variabili, le altre sono poste pari a zero. Se la soluzione di base soddisfa

soluzione di base ammissibile. n + m variabili tali che la

anche i vincoli di non negatività essa si dice In altri termini, una base è un insieme di matrice dei coe¢cienti

A

m

delle

del relativo sistema di equazioni sia non singolare5

(il sistema cioè abbia soluzioni). Le variabili che formano la soluzione di base ammissibile si dicono variabili di base e le altre

n

variabili si dicono variabili

non di base. Si osservi in…ne che per le funzioni lineari possiamo scrivere:

max f (x) =

 min [

f

(x)]

f (x) si può parlare di soluzione di base possibile ottima è una soluzione di

Per esse invece di massimizzare o minimizzare la ottimizzare la

( ):

f x

una

base possibile che rende ottima la funzione obiettivo. Date le

m

equazioni nelle

n

+m

incognite esistono in…nite soluzioni al

sistema considerato poiché abbiamo meno equazioni che incognite. Ma quante soluzioni di base esistono? combinazioni di

(n + m)

elementi a gruppi di Cn+m;m

=

Sono “solo” tutte le possibili m,

ovvero

(n + m)! m! n!



3 Il teorema di Rouché-Capelli stabilisce che, a¢nché un sistema di equazioni lineari sia compatibile (ovvero ammetta soluzioni), occorre e basta che il rango della matrice dei

coe¢cienti sia uguale al rango della matrice completa, quella cioè che si ottiene orlando la matrice dei coe¢cienti con il vettore dei termini noti. Supponiamo che tale rango sia

p.

Indichiamo con

n il numero delle incognite del sistema. Se p =nnpil sistema ammette p  n il sistema è inde…nito, ammettendo 1 soluzioni.

un’unica soluzione, se 4

Il sistema (6) è un sistema in cui il numero delle incognite è sicuramente maggiore del numero delle equazioni. Poichè tali equazioni rappresentano dei vincoli (ad esempio di produzione) possiamo ragionevolmente supporre le equazioni del sistema (6) non siano tra loro linearmente dipendenti (altrimenti saremmo in presenza di vincoli ridondanti) nè che il sistema dei vincoli sia incompatibile (se infatti stiamo esaminando un problema relativo ad una impresa che

già

produce un certo numero di beni è ovvio che almeno

una combinazione produttiva deve essere fattibile). Il rango massimo della matrice dei

m; n + m) ovvero il minimo tra il numero m di righe della n + m) delle variabili, e così anche il rango della matrice completa

coe¢cienti è (ovviamente) il min( matrice ed il numero (

(dimensionalmenta essa ha infatti solo una riga in più della precedente). Dunque i due

A6

ranghi dovranno essere uguali e il sistema ammetterà soluzioni. 5 Quindi det ( ) = 0.

8

soluzioni di base6 .

C

Basterebbe quindi calcolare queste

n

+m;m soluzioni e per ognuna calco-

lare la funzione obiettivo, per decidere quale di esse ottimizza la funzione obiettivo.

n

Risulta evidente che già con 5 variabili ( ) e 5 equazioni (

m) è necessario

risolvere 252 sistemi lineari di 5 equazioni in 5 incognite e man mano che

crescono i vincoli questo numero aumenta notevolmente e anche i più potenti calcolatori faticano a determinare la soluzione cercata.

4 LA LOGICA DEL SIMPLESSO Analizziamo con un semplice esempio come si può pervenire alla soluzione ottima senza dover risolvere tutti i possibili sistemi.

Esempio 3

Consideriamo il seguente problema di programmazione lineare:

min Z = x1 + x2 con vincoli:

8 2x + x  2 > > < x  2x  2 x +x 5 > > : x 0 1

2

1

2

1

2

(7)

1

x2  0

trasformiamo le disequazioni del sistema (7) in equazioni mediante l’inserimento delle variabili slack:

8 2x + x + x = 2 >> >> x  2x + x = 2 >< x + x + x = 5 x 0 x 0 >> x 0 >> x 0 >: x 0 1

1

1

2

2

2

1 2

3

4

5

(8)

3 4 5

6

Ad esempio, se consideriamo una classe di 20 alunni, in quanti modi gli alunni possono

sedersi a gruppi di 2? Dobbiamo calcolare le combinazioni di 20 elementi a gruppi di 2: 20! = 190, quindi esistono 190 modi possibili diversi per far sedere i 20 alunni nei 10 2!18! banchi da 2 posti.

9

Una soluzione possibile di base è data da:



x1 = 0 variabili fuori base x2 = 0 9 x3 = 2 = x4 = 2 ; variabili in base x5 = 5 Esprimiamo sia le equazioni che rappresentano i vincoli sia la funzione obiettivo esplicitando le variabili di base. Pertanto il sistema (8) diviene:

8 x = 2 + 2x  x < : xx ==25xx +2xx 3

1

4

1

5

e la funzione obiettivo:

min Z =

Z

x

2 2

1

2

1

+ x2

Z

Il valore di con la soluzione possibile di base appena trovata è = 0. Poiché dobbiamo minimizzare (quindi determinare il valore più piccolo

Z

Z

Z

possibile di ), osservando la forma funzionale di ci accorgiamo che, aumentando il valore di 1 possiamo diminuire : infatti il coe¢ciente della

x



x

Z

x

variabile 1 è 1 per cui, aumentando il valore della variabile 1 , il valore di diminuisce. Non possiamo però aumentare il valore di 1 senza tener

Z

x

conto dei vincoli: occorre veri…care che l’aumento del valore di le altre variabili negative. E’ immediato veri…care che: aumentando 1 aumenta 3

x ! x aumentando x1 ! diminuisce x4 aumentando x1 ! diminuisce x5 x4 diventa negativo quando x1  2; x5

x1 non renda

x



diventa negativo quando 1 5. Dei due vincoli il primo è più “stringente”, per cui 1 può aumentare …no al

x

valore “2”. Quindi conviene “far entrare” in base la variabile Il sistema diventa:

x4 .

8 x = 2 + 2x  x >> >> x = 2 + 2x  x >< x = 5  x  x x 0 x 0 >> x 0 >> x 0 >: x 0 3

1

2

1

2

4

5

1

1 2 3 4 5

10

x1 e far uscire

2

(9)

Esprimiamo le variabili in base (x1 ; x3 ; x5 ) in funzione delle sole variabili fuori base (x2 ; x4 ). Il sistema (9) diviene quindi:

8> >> >> < >> >> >:

 

= 6 + 3x2 2x4 = 2 + 2x2 x4...