Lezione n° 17

Lezione n° 17

Analisi di Post-Ottimalità:

-  Variazione dei coefficienti di costo -  Variazione dei termini noti

Lezioni di Ricerca Operativa

Corso di Laurea in Informatica Università di Salerno

Prof. Cerulli – Dott.ssa Gentili – Dott. Carrabs

Esempio: pianificare la produzione di una piccola azienda

  L’azienda produce due tipi di prodotti, il prodotto P ₁ ed il prodotto P ₂ , usando due materie prime indicate con A e B.

  La disponibilità al giorno di materia prima A è pari a 6 ton, mentre quella di materia prima B è di 8 ton.

  La quantità di A e B consumata per produrre una ton di prodotto P ₁ e P ₂ è riportata nella seguente tabella.

P ₁ P ₂ A 1 2 B 2 1 materie prime

Prodotti

  Si ipotizza che tutta la Quantità prodotta venga venduta.

  Il prezzo di vendita per tonnellata è Euro 3000 per P ₁ e Euro 2000 per P ₂ .

  L’azienda ha effettuato un’indagine di mercato con i seguenti esiti:

  la domanda giornaliera di prodotto P ₂ non supera mai di più di 1 ton quella di prodotto P ₁ ,

  la domanda massima giornaliera di prodotto P ₂ è di 2 ton

Problema:

determinare le quantità dei due prodotti che

debbono essere fabbricati giornalmente in

modo da rendere massimo il guadagno.

Esempio: formulare il modello matematico

Formulazione Matematica

Definizione delle variabili

Definizione Dell’obiettivo

Definizione dei vincoli Definizione delle variabili

Si introducono due variabili che rappresentano le quantità prodotte (e vendute) al giorno per P ₁ e P ₂ (ton):

  produzione di P ₁ : x ₁

  produzione di P ₂ : x ₂

Le due variabili sono continue.

Definizione dell’obiettivo

Il guadagno giornaliero (K€) è dato da z = 3 x ₁ + 2 x ₂

L’obiettivo è rappresentato da un’equazione lineare.

Definizione dei vincoli

  Vincoli (tecnologici) sull’uso delle materie prime (l’uso giornaliero delle materie prime non può eccedere la disponibilità):

8 2

) (

6 2

) (

2 1

2 1

≤ +

≤ +

x x

B

x x

A

  Vincoli conseguenti le indagini di mercato

2

1

2 2 1

≤

≤ +

−

x x x

  Non negatività delle variabili

0 0 ₂

1 ≥ x ≥

x

La formulazione definisce un Problema di Programmazione Lineare a variabili continue

) 6 ( 0

) 5 ( 0

) 4 ( 2

) 3 ( 1

) 2 ( 8 2

) 1 ( 6 2

2 3

max

2 1

2 2 1

2 1

2 1

2 1

≥

≥

≤

≤ +

−

≤ +

≤ +

+

=

x x

x x x

x x

x x

x x

z (5)

(1) (6)

x 2

8 7 6 5 4 3 2 1

1 2 3 4 5 6 -1

-2 x ₁

(2)

(3)

(4)

X

1 2 3 4 5 6 1

-2 -1

2 3

4 (2) (3)

(4)

(1) (5)

(6)

x

1

x

2

A F

E D

B

C Ottimo

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

E=(1,2) F=(0,1)

l’obiettivo per z=0

z=6 z=38/3

Esempio: sensitività della soluzione.

  Una volta determinata una soluzione ottima può essere interessante verificare quanto questa sia sensibile a variazioni nel modello.

  Ad esempio, può essere utile verificare cosa accadrebbe se si modificasse la disponibilità delle materie prime o se variasse il prezzo di vendita dei prodotti.

Variazioni rispetto la disponibilità delle risorse.

(a) come aumentare le risorse per migliorare la soluzione ottima;

(b) come ridurre le risorse disponibili lasciando invariata la soluzione ottima.

I vincoli del problema hanno tutti la seguente forma

quantità di risorsa usata ≤ disponibilità di risorsa

anche se solamente i vincoli (1) e (2) rappresentano

effettivamente il consumo delle materie prime A e B.

Poiché i vincoli (1) e (2) sono soddisfatti all’uguaglianza dalla soluzione ottima corrispondente al punto C=(10/3,4/3), il livello ottimo di produzione per i due prodotti è tale da utilizzare tutte le materie prime disponibili.

I vincoli (1) e (2) sono saturi, quindi le materie prime A e B sono utilizzate completamente, ovvero sono risorse scarse.

Vincolo saturo Risorsa scarsa

Vincolo non saturo Risorsa abbondante

  E’ possibile aumentare la disponibilità di una risorsa scarsa per migliorare la soluzione ottima (caso (a)).

  E’ possibile diminuire la disponibilità di una risorsa abbondante

senza variare la soluzione ottima (caso (b)).

Verifichiamo sino a che livello ha senso aumentare la materia prima A.

(1) 1

2

A F

E D

B C

x _E x _I

1 2 3 4

X

(2) (4)

K

z=38/3 ^z=13

Aumentando la

risorsa A il vincolo (1) si sposta e di

conseguenza varia il punto di ottimo.

Oltre K=(3,2) (intersezione di (2) e (4)) non ha più senso aumentare la risorsa A.

Il nuovo valore di A è 7.

Analoga verifica può essere fatta per la materia prima B.

1 2

A F

E D

B C

x _E x _I

X

(2) (4)

1 2 3 4 5 6 (1)

L (6)

z=38/3 z=18

Aumentando la risorsa B il vincolo (2) si sposta e di conseguenza varia il punto di ottimo.

Oltre L=(6,0) (intersezione di (1) e (6)) non ha più senso aumentare la risorsa B.

Il nuovo valore di B è 12.

Supponendo i vincoli (3) e (4) relativi al consumo di due ulteriori risorse abbondanti, è possibile verificare di quanto diminuirne la disponibilità senza modificare la soluzione ottima.

Per il vincolo (3)

(4)

(2)

(1) (3)

1 2

B C

x

1

x

2

1 2 3 4 A

F

E D

X

A F

E D

X’

2 1

1 + ≤

− x x

2 2

1 + ≤ −

− x x

Per il vincolo (4)

1 2

A F

B C

x

1

x

2

1 2 3 4 X

(2) (4)

(1) E D D

E

X’

2 ≤ 2 x

3 4

2 ≤

x

  Dopo aver verificato la convenienza di una possibile maggiore disponibilità delle risorse A e B, è interessante determinare quale sia la risorsa che di più convenga aumentare.

  Nell’esempio, l’azienda potrebbe avere una limitata disponibilità finanziaria che vorrebbe far fruttare al meglio, acquisendo un’ulteriore quantità di una delle risorse in modo da incrementare maggiormente i propri profitti.

  Questa informazione è ottenibile per mezzo della

Programmazione Lineare.

Si può calcolare il Valore di una Unità di Risorsa w _i :

i w _i z

risorsa della

variazione massima

di e variazion massima

=

Per la risorsa A: (K€/ton)

3 1 3

38 39

6 7

3 13 38

− =

− =

−

A = w

Per la risorsa B: (K€/ton)

3 4 4

3

38 54

8 12

3 18 38

=

−

− =

−

B = w

  La quantità w _i indica di quanto aumenta l’obiettivo in corrispondenza dell’acquisizione di un’ulteriore unità di risorsa.

  E’ evidente come nell’esempio convenga acquisire per prima

la risorsa B.

Variazioni del prezzo di vendita dei prodotti.

Si tratta di analizzare entro quali limiti di tolleranza possono

variare i prezzi di vendita senza alterare la soluzione ottima

(la produzione associata al punto C).

Variazioni del prezzo di vendita dei prodotti.

1 F

2

A

E D

B C

x

1

x

2

1 2 3 4 X

Variando c ₁ e c ₂ cambia la pendenza della funzione obiettivo:

c ₂ aumenta c ₁ diminuisce

(1)

Variazioni del prezzo di vendita dei prodotti

1 F 2

A

E D

B C

x

1

x

2

1 2 3 4 X

Variando c ₁ e c ₂ cambia la pendenza della funzione obiettivo:

c ₂ diminuisce c ₁ aumenta

(2)

Variando c ₁ e c ₂ il punto C

rimane soluzione ottima

fino a che la pendenza

della funzione obiettivo

diventa uguale a quella dei

vincoli (1) e (2).

19

Analisi di Post-Ottimalità

(Analisi della Sensitività della Soluzione)

Dato un problema di programmazione lineare

e data la soluzione ottima x ^* e la base ottima associata B, determinare come sia possibile variare certe caratteristiche del problema lasciando invariata la base ottima.

0 min

≥

= x

b x

A

x

c ^t

20

Cinque casi:

1) variazione nel vettore dei costi c;

2) variazione nel vettore dei termini noti b;

3) variazione nella matrice di vincoli A;

4) aggiunta di una nuova variabile;

5) aggiunta di un nuovo vincolo.

Caso 1: variazione nel vettore dei costi c.

Abbiamo due sottocasi:

caso 1.1) variazione di un coefficiente di costo relativo ad una variabile non in base;

caso 1.2) variazione di un coefficiente di costo relativo ad una variabile in base.

Data una soluzione di base ottima supponiamo che il coefficiente di una delle variabili sia cambiato da c _k a c’ _k .

L’effetto di questo cambio si ripercuoterà solo sui coefficienti di

costo ridotto.

Sia c _k , k∈N , il coefficiente che viene variato

Caso 1.1) variazione di un coefficiente di costo c _k relativo ad una variabile x _k non in base:

In questo caso c _B non subisce variazioni e quindi

j B

T B

j c A a

z = ^{− 1} rimane inalterato per ogni j ∈N.

k k c z −

Solo cambia in: z _k − c ' _k

c' _k = c _k − δ

Se ^z _k − ^c ' _k = ^z _k − ( ^c _k − δ ) = ( ^z _k − ^c _k ) + δ ≤ 0

La soluzione continua a rimanere ottima altrimenti occorre fare

entrare in base la variabile x _k con una nuova iter. del simplesso.

Caso 1.1) variazione di un coefficiente di costo c _k relativo ad una variabile x _k non in base:

z _k −c' _k = (z _k − c _k )

   ≤0  + δ ≤ 0 ⇒ δ ≤ −(z _k − c _k )

ma quale è l’intervallo di valori che può assumere δ affinchè la base attuale continui a rimanere ottima?

Quindi per ogni valore di δ nell’intervallo − ∞ ≤ δ ≤ − ( z − _k c _k )

la base continua a rimanere ottima.

24

sia c _Bi , i=1,...,m , il coefficiente che viene variato.

N j

c a

A c

c

z _j − _j = ^T _{B B} ⁻¹ _j − _j ∈

Tale variazione modifica i coefficienti di costo ridotto (negativi poichè la base è ottima) associati alle variabili fuori base

i B

B B

B c c c e

c ' i ← i − δ ⇒ ' ← − δ

dove ^{( esimo elemento )} 0

1 0

−

⎥ ⎥

⎥ ⎥

⎥ ⎥

⎦

⎤

⎢ ⎢

⎢ ⎢

⎢ ⎢

⎣

⎡

= i

e _i





Caso 1.2) variazione di un coefficiente di costo c _k

relativo ad una variabile in base:

25

j j

B T

i j

B T

B

j j

B T

i T

B j

j

c a

A e

a A

c

c a

A e

c c

z

−

−

=

=

−

−

=

−

−

−

−

1 1

) 1

( '

δ δ

dove e ^T _i A _B ^{− 1} = ( A _B ^{− 1} ) ⁱ è la riga i-esima di A _B ^-1 Le condizioni su δ si ottengono imponendo che

N j

a A

c z

c

z ' _j − _j = ( _j − _j ) − δ ( _B ^{− 1} ) ⁱ _j ≤ 0 ∀ ∈

Caso 1.2) variazione di un coefficiente di costo c _k

relativo ad una variabile in base:

26

Caso 2) variazione del termine noto di un vincolo .

Sia b _i , i=1,...,m , il termine noto del i-esimo vincolo che viene variato.

A causa di tale variazione si modificano i valori delle variabili di base:

i B B

i B

B i

i b x A b e A b A

b ' ← − δ ⇒ ' = ^{− 1} ( − δ ) = ^{− 1} − δ ( ^{− 1} )

i B B

B x A

x ' = − ( ^{− 1} )

⇒ δ

dove A _B ^{− 1} e _i = ( A _B ^{− 1} ) _i è la colonna i-esima di

Le condizioni su δ si ottengono imponendo che 0

) (

' _B = x _B − A _B ^{− 1} _i ≥

x δ

− 1

A B

Esempio: Analisi di Sensibilità.

0

4 2

6 2

min

2 1

3 2

1

3 2

1

≥

≤ +

−

≤ +

+

− +

−

x

x x

x x

x

x x

x

0

4 2

6 2

min

5 2

1

4 3

2 1

3 2

1

≥

= +

+

−

= +

+ +

− +

−

x

x x

x

x x

x x

x x

x

Base ottima: { } { } _⎥

⎦

⎢ ⎤

⎣

= ⎡

⎥ ⎦

⎢ ⎤

⎣

⎡

= −

=

= ⁻

1 1

0

; 1 1 1

0

; 1 4 , 3 , 2

; 5 ,

1 N A _B A _B ¹

B

Dato il seguente problema di P.L.

Infatti:

2

; 1

; 3

4 4

3 3

2 2

−

=

−

−

=

−

−

=

− c z

c z

c z

12

10 ; 6

1

*

5 1 1

−

=

=

⎥ ⎦

⎢ ⎤

⎣

= ⎡

⎥ ⎦

⎢ ⎤

⎣

= ⎡

=

−

−

b A

c z

x b x

A x

B T

B

B

B

Di quanto si può variare al più il coefficiente c ₂ prima di cambiare la base ottima?

Esempio: caso 1.1) variazione di un coefficiente di costo c _k relativo ad una variabile x _k non in base.

z ₂ − c' ₂ = (z ₂ − c ₂ ) + δ ≤ 0 ⇒ −3+ δ ≤ 0 ⇒ δ ≤ 3

Verifichiamo cosa succede se scegliamo un δ >3 per esempio δ ^=4.

Poiché x ₂ non è in base il valore z _j =c _B A _B ^-1 a _j non cambia per

nessun indice j ∈ N. L’unico coeff. di costo ridotto che cambia è:

z ₂ − c' ₂ = (z ₂ − c ₂ ) + δ = −3+ 4 = 1 > 0

Poiché z ₂ -c’ ₂ è maggiore di zero la soluzione non è più ottima.

Bisogna fare entrare in base x ₂ .

Esempio: caso 1.2) variazione di un coefficiente di costo c _k relativo ad una variabile x _k in base.

Di quanto si può variare al più il coefficiente c ₁ prima di cambiare la base ottima?

N j

a A

c z

c

z ' _j − _j = ( _j − _j ) − δ ( _B ^{− 1} ) ⁱ _j ≤ 0 ∀ ∈ ⎥

⎦

⎢ ⎤

⎣

= ⎡

−

1 1

0

1 1 A B

[ ] ^{1 0 1} ₂ ^{0 3 0 3}

) (

' _{2 2 2 2} ⎥ ≤ ⇒ − − ≤ ⇒ ≥ −

⎦

⎢ ⎤

⎣

− ⎡

−

=

− ^{c z c} δ δ δ

z

[ ] ^{1 0 1} ₀ ^{0 1 0 1}

) (

' _{3 3 3 3} ⎥ ≤ ⇒ − − ≤ ⇒ ≥ −

⎦

⎢ ⎤

⎣

− ⎡

−

=

− ^{c z c} δ δ δ

z

[ ] ^{1 0 1} ₀ ^{0 2 0 2}

) (

' _{4 4 4 4} ⎥ ≤ ⇒ − − ≤ ⇒ ≥ −

⎦

⎢ ⎤

⎣

− ⎡

−

=

− ^{c z c} δ δ δ

z

Poiché x ₁ è in base il valore z _j cambia per ciascun indice j ∈N

secondo la relazione: z ' _j − c _j = ( z _j − c _j ) − δ ( A _B ^{− 1} ) ⁱ a _j ≤ 0 ∀ j ∈ N

Verifichiamo cosa succede se scegliamo un δ < -1 per esempio δ ^{= -2.}

2 0

2 '

0

' _{1 2 2}

1 − = c = ⇒ = c − c = − + = −

c δ δ

[ ] ^{3 2 1 1}

2 0 1

, 1 2 3

' _{2 2} ⎥ = − + × = −

⎦

⎢ ⎤

⎣

+ ⎡

−

= z −c

[ ] ^{1 2 1 1}

0 0 1

, 1 2 1

' _{3 3} ⎥ = − + × =

⎦

⎢ ⎤

⎣

+ ⎡

−

= z −c

[ ^{1 , 0} ] ¹ ₀ ^{2 2 1 0}

2 2

' _{4 4} ⎥ = − + × =

⎦

⎢ ⎤

⎣

+ ⎡

−

=

z −c

Esempio: caso 2) variazione del termine noto di un vincolo.

i B B

i B

B i

i b x A b e A b A

b ' ← − δ ⇒ ' = ^{− 1} ( − δ ) = ^{− 1} − δ ( ^{− 1} )

i B B

B x A

x ' = − ( ^{− 1} )

⇒ δ

⎩ ⎨

⎧

≤

⇒

≥

−

≤

⇒

≥

= −

⎥ ⎦

⎢ ⎤

⎣

⎡

− + −

⎥ ⎦

⎢ ⎤

⎣

= ⎡

⎥ ⎦

⎢ ⎤

⎣

− ⎡

⎥ ⎦

⎢ ⎤

⎣

= ⎡

10 0

10

6 0

6 10

6 1

' 1

5 1

δ δ

δ δ

δ δ δ

x x _B x

Di quanto può variare al più il termine noto b ₁ prima di rendere inammissibile la base ottima?

Verifichiamo cosa succede se scegliamo δ ^{= 3.}

⎥ ⎦

⎢ ⎤

⎣

= ⎡

⎥ ⎦

⎢ ⎤

⎣

⎡

− + −

⎥ ⎦

⎢ ⎤

⎣

= ⎡

⎥ ⎦

⎢ ⎤

⎣

− ⎡

⎥ ⎦

⎢ ⎤

⎣

= ⎡

7 3 3

3 10

6 1

3 1 '

5 1

x x _B x

i B

B

B x A

x ' = − δ ( ^{− 1} )