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

Lezione n°7

- Cono di recessione.

- Teorema della rappresentazione.

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

Lezioni di Ricerca Operativa

Corso di Laurea in Informatica ed Informatica Applicata

Università di Salerno

Coni Convessi

Un cono convesso è un insieme convesso che contiene raggi che partono dall’origine (perché?)

Definizione:

Un cono convesso C è un insieme convesso con la seguente proprietà

0

^{ogni x} ∈ ^C ⇒ λ ^x ∈ ^C λ ≥

per

C

In generale:

un cono convesso può essere espresso in funzione dei suoi raggi

C

Solo alcuni raggi sono sufficienti (detti RAGGI ESTREMI) perché gli altri sono espressi come combinazione conica di questi

Nota:

alcuni raggi possono essere espressi

come combinazione conica di altri

Coni Convessi

Dato un insieme di vettori d₁,d₂,…,d_k il cono convesso generato da questi vettori è dato da:

1

: 0 1 2

k

j j j

j

C λ d λ j , ,...,k

=

 

=  ≥ = 

 ∑ 

C

d₁ d₂

d₃

d₄

d₅

Definizione

Una direzione d di un poliedro X, è una direzione estrema di X se e solo se non è esprimibile come

combinazione conica di altre direzioni di X.

Direzioni estreme di un poliedro

Come si calcolano le direzioni di un poliedro?

(Procedimento geometrico)

{ ^{: ≤ , ≥ 0} }

= x A x b x

X ^(poliedro)

Abbiamo visto che d è una a direzione del poliedro se:

0 0

0

≠

≥

≤ d

d d A

Questo è un sistema omogeneo che definisce un cono poliedrico ( detto CONO di RECESSIONE) ottenuto traslando gli iperpiani che definiscono X

parallelamente a se stessi fino all’origine

X

Cono di recessione contenente tutte le direzioni del poliedro,

ossia tutte le direzioni che soddisfano il sistema:

Ad ≤ 0

d ≥ 0

d ≠ 0

X

Direzioni estreme del poliedro (direzioni estreme del cono di recessione)

Teorema (di rappresentazione di poliedri)

Dato un poliedro X non vuoto con punti estremi

k i

x

= 1 , 2 ,...,

e direzioni estreme

Ogni punto x ∈ X può essere espresso come combinazione convessa dei punti estremi di X e combinazione lineare

non negativa delle sue direzioni estreme:

t j

d

= 1 , 2 ,...,

t j

k i

d x

x

j

i k

i

i

t

j

j j k

i

i i

,..., 2 , 1

0

,..., 2 , 1

0

1

1

1 1

=

≥

=

≥

=

+

=

∑

∑

∑

=

=

=

µ

λ λ

µ

λ

1

x

2

x

3

x

1

d

2

d

y

z

( ) ^0,1

)

1

(

2

+ − ∈

= λ ^x λ ^x λ y

0

1

≥

+

= ^y µ ^d µ

z

)

1

(

2

x d

x

z = λ + − λ + µ

quindi:

x

Soluzione dei problemi di PL

Consideriamo il problema (PL) in Forma Standard

Ogni punto x∈ X può essere espresso come combinazione convessa dei punti estremi di X e combinazione lineare non negativa delle sue direzioni estreme:

t j

k i

d x

x

j i

k

i

i

t

j

j j k

i

i i

,..., 2 , 1

0

,..., 2 , 1

0

1

1

1 1

=

≥

=

≥

=

+

=

∑

∑

∑

=

=

=

µ λ

λ

µ λ

k i

x

= 1 , 2 ,...,

d

j = 1 , 2 ,..., t

0

s.t.

min

≥

=

= x

b x

A

x c

z

Possiamo trasformare il problema di PL in un nuovo problema con incognite:

λλλλ₁ ,λλλλ₂ ,...λλλλ_k e µµµµ₁, µµµµ₂,…, µµµµ_t

,...,t ,

j µ

,...,k ,

i λ

λ

d c x

c z

j i

k

i

i

t

j

j j k T

i

i i T

2 1 0

2

1 0

1

) (

)

(

min

1

1 1

=

≥

=

≥

=

+

=

∑

∑

∑

=

=

=

µ λ

Nota:

1. se esiste una direzione d_jtale che c^Td_j< 0 ⇒⇒⇒⇒ l’ottimo del problema è illimitato 2. se c^Td_j≥0 per ogni d_j ⇒⇒⇒⇒

- le corrispondenti variabili µµµµ₁^, µµµµ₂^,…, µµµµ_t sono scelte uguali a zero

- per minimizzare il resto della sommatoria basta calcolare tutti i valori c^Tx_i , scegliere il minimo ad esempio c^Tx_p e fissare λλλλ_p=1e tutti gli altri uguali a zero

RIASSUMENDO:

1. la soluzione ottima di un problema di programmazione lineare è finito se e solo se c

d

≥ 0 per ogni d

2. in questo caso una soluzione ottima si trova su uno dei vertici del poliedro

3. se esistono più vertici ottimi allora ogni combinazione

convessa di questi punti è una soluzione ottima

Soluzione dei problemi di PL: esempio

1 2

1 2

1 2

1 2

min 3 - 2 - 2 6 , 0

z x x

x x

x x

x x

= − + ≤

+ ≤

≥

d

d

X

Calcoliamo punti estremi e direzioni estreme

a b

h

1 2 1 2 2 1

1 2 1 2 2 1

1 2 2 1

1 2 1 1 1 2

- = 2 ; x = 0 x = 2; x = 0 x = -2 - 2 = 6; x = 0 x = 3; x = 0 x = -6

- = 2 2

- 2 = 6 4 2 6 2, 4

x x

x x

x x x x

x x x x x x

+ ⇒ ⇒

+ ⇒ ⇒

+ ⇒ = +

 

+ ⇒ − + + = ⇒ = =



X

Soluzione dei problemi di PL: esempio(2)

(-2,0) (-6,0)

(0,3) a = ( 2 , 4 ) )

2 , 0

= ( b

(0, 0)

h =

X

Soluzione dei problemi di PL: esempio(3)

( )

( )

1

2

2 / 3,1/ 3 1,0

d d

=

=

=( , ) d 3 3

2 (1, 0) d =









≥

≥

= +

≤ +

−

≤ +

= −

0 ,

0

1 ,

0 2

, 0 :

) , (

2 1

2 1

2 1

2 1

2 1

d d

d d

d d

d d d

D d















≤

≤ ⇒ +

+

−

≤

≤ ⇒ +

+

−

−

=

3 0 1

2 1

2 0 1

1 1

2 2

2

2 2

2 2 1

d d

d

d d

d d d

3 0 ≤ d₂ ≤ 1

1 2

1 2

1 2 3 1 2

1 2 3

1 2 3, 1 2

min 3 (1, 3)

0 0 2

(1, 3) 0; (1, 3) 6; (1, 3) 10;

0 2 4

2 / 3 1

(1, 3) 1/ 3; (1, 3) 1;

1/ 3 0

min 0 6 10 1/ 3

1

, , , 0

T

T T T

T T

z x x c

c h c b c a

c d c d

λ λ λ µ µ

λ λ λ λ λ λ µ µ

= − ⇒ = −

     

= −   = = −   = − = −   = −

     

   

= −   = − = −   =

   

− − − +

+ + =

≥

Soluzione dei problemi di PL: esempio(4)

Ottimo illimitato

(facendo tendere µ

a ∞ la f.o. tende a - ∞

indipendentemente dai valori

scelti per le altre variabili)

1 2

1 2

1 2 3 1 2

1 2 3

1 2 3, 1 2

min 4 (4, 1)

0 0 2

(4, 1) 0; (4, 1) 2; (4, 1) 4;

0 2 4

2 / 3 1

(4, 1) 7 / 3; (4, 1) 4;

1 / 3 0

min 0 2 4 7 / 3 4

1

, , , 0

T

T T T

T T

z x x c

c h c b c a

c d c d

λ λ λ µ µ

λ λ λ λ λ λ µ µ

= − ⇒ = −

     

= −   = = −   = − = −   =

     

   

= −   = = −   =

   

− + + +

+ + =

≥

Soluzione dei problemi di PL: esempio(5)

Ottimo finito di valore -2 in corrispondenza del vertice b

ottenuto assegnando alle variabili i valori

µ

µ

λ

λ

=0, λ

=1

Consideriamo una differente funzione obiettivo