Lezione n° 7
- Cono di recessione.
- Teorema della rappresentazione.
R. Cerulli – F. Carrabs
Lezioni di Ricerca Operativa
Corso di Laurea in Informatica ed Informatica Applicata Università di Salerno
X
Vertici di un poliedro
Vertici del Poliedro X o PUNTI ESTREMI
Definizione
Un punto di un poliedro X è un punto estremo se e solo se non può essere espresso come combinazione convessa STRETTA di altri punti di X.
Teorema (no dim.)
(Proprietà dei punti estremi di un poliedro limitato)
Dato un poliedro X non vuoto e limitato con punti estremi x1, x2,…, xk, ogni punto y∈X può essere espresso come combinazione convessa dei punti estremi di X, cioè:
y =
λ
jx
j j=1 k∑
con
λ
j= 1 e
λ
j≥ 0 ∀j=1,..., k
j=1 k∑
Esempio
Voglio esprimere il vettore y come combinazione convessa dei vertici del politopo
( )
0,1
)
1
(
2+
-
Î
=
l
x
l
z
l
y
( )
0,1
)
1
(
4 5+
-
Î
=
µ
x
µ
x
µ
z
y
1x
2x
3x
4x
5x
z)
1
)(
1
(
)
1
(
5 4 2x
x
x
y
=
l
+
µ
-
l
+
-
µ
-
l
sostituisco: Nota che :λ
≥ 0
µ
(1−
λ
) ≥ 0 (1−
µ
)(1−
λ
) ≥ 0
1. 2.l
+
µ
(
1
-
l
)
+
(
1
-
µ
)(
1
-
l
)
=
l
+
(
1
-
l
)(
µ
+
1
-
µ
)
=
1
c.v.d.
Una combinazione convessa di x1, x2 x3 permette di ottenere tutti i punti di X’Ì X
X
X’ X
Quando un poliedro è illimitato?
In generale:
Bisogna considerare le sue direzioni estreme
1
x
2x
3x
Definizione.
Un RAGGIO R di vertice x0 e di direzione d è un insieme di punti della forma:
Raggi e direzioni di un poliedro
R = x
{
0+
λ
d :
λ
≥ 0
}
Definizione
Dato un poliedro X, il vettore d è una direzione di X se e solo se per ogni punto x0
∈
X, il raggioappartiene a X.
X
x0 d1 d2 d3 d1 NON è direzione d2 è direzione d3 NON è direzione0
,
0+
l
d
l
³
x
Come si calcolano le direzioni di un poliedro?
(Procedimento algebrico)
{
:
£
,
³
0
}
=
x
A
x
b
x
X
(poliedro)Dato un qualsiasi punto x Î X, il vettore d è una direzione del poliedro X se:
0
)
(
0
)
(
)
(
)
(
¹
³
+
£
+
d
iii
d
x
ii
b
d
x
A
i
l
l
0
)
(
0
)
(
)
(
)
(
¹
³
+
£
+
d
iii
d
x
ii
b
d
x
A
i
l
l
(i) poiché xÎ
X :Û
£
+
Û
£
+
d
b
A
x
A
d
b
x
A
(
l
)
l
Û
³
+
0
)
(
ii
x
l
d
Quindi le direzioni d del poliedro X sono tutti e soli i vettori tali che:
0
0
0
¹
³
£
d
d
d
A
Adesso vediamo un esempio poi vediamo come si interpretano geometricamenteλ
Ad ≤ 0 ⇔
A
d
£
0
0
³
Esempio 1
(
)
þ
ý
ü
î
í
ì
³
³
£
+
-£
+
-£
+
-=
0
,
0
8
2
,
2
,
2
3
:
2 1 2 1 2 1 2 1 2 1x
x
x
x
x
x
x
x
,x
x
X
L’insieme delle direzioni di X è dato dai vettori
÷÷
ø
ö
çç
è
æ
¹
÷÷
ø
ö
çç
è
æ
=
0
0
2 1d
d
d
(
)
þ
ý
ü
î
í
ì
³
³
=
+
£
+
-£
+
-£
+
-=
0
,
0
,
1
0
2
,
0
,
0
3
:
2 1 2 1 2 1 2 1 2 1 2 1d
d
d
d
d
d
d
d
d
d
,d
d
D
÷
÷
÷
÷
ø
ö
ç
ç
ç
ç
è
æ
=
3
1
3
2
'd
÷÷
ø
ö
çç
è
æ
=
0
1
''d
Coni Convessi
Un cono convesso è un insieme convesso che contiene raggi che partono dall’origine (perché?)
Definizione:
Un cono convesso C è un insieme convesso tale che se x∈C allora anche λx∈C ∀λ ≥ 0.
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 d1,d2,…,dk il cono convesso generato da questi vettori è dato da:
1
:
0
1 2
k j j j jC
l
d
l
j
, ,...,k
=ì
ü
=
í
³
=
ý
î
å
þ
C
d1 d2 d3 d4 d5Definizione.
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.
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
b1≠0 b2 ≠ 0 b3 ≠ 0 b2=0 b1=0 b3=0X
Direzioni estreme del poliedro (direzioni estreme del cono di recessione)
Teorema (di rappresentazione di poliedri)
(no dim.)Dato un poliedro X non vuoto con punti estremi xi con i=1,…,k e direzioni estreme dj con j=1,…,t , ogni punto x
∈
X può essereespresso come combinazione convessa dei punti estremi di X e combinazione lineare non negativa (conica) 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
=
³
=
³
=
+
=
å
å
å
= = =µ
l
l
µ
l
1
x
2
x
3
x
1
d
2
d
y
w
( )
0,1
)
1
(
3 2+
-
Î
=
l
x
l
x
l
y
w = y +
µ
d
1µ
≥ 0
w =
λ
x
2+ (1−
λ
)x
3+
µ
d
1quindi:
x
4Soluzione 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 = ³ = ³ = + =
å
å
å
= = =µ
l
l
µ
l
k ixi =1,2,..., punti estremi
d
jj
=
1
,
2
,...,
t
direzioni estreme0 s.t. min ³ = = x b x A x c z T
Possiamo trasformare il problema di PL in un nuovo problema con incognite: l1 ,l2 ,...lk e µ1, µ2,…, µt ,...,t , j μ ,...,k , i λ λ d c x c z j i k i i t j j j T k i i i T 2 1 0 2 1 0 1 ) ( ) ( min 1 1 1 = ³ = ³ = + =
å
å
å
= = =µ
l
Nota:1. se esiste una direzione djtale che cTd
j< 0 Þ l’ottimo del problema è illimitato
2. se cTd
j≥0 per ogni dj Þ
- le corrispondenti variabili µ1, µ2,…, µt sono scelte uguali a zero
- per minimizzare il resto della sommatoria basta calcolare tutti i valori
cTx
i , scegliere il minimo ad esempio cTxp e fissare lp=1e tutti gli altri
RIASSUMENDO:
1. la soluzione ottima di un problema di minimo è finita se e
solo se c
Td
j
≥ 0 per ogni d
j2. 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 2min
3
-
2
-
2 6
,
0
z
x
x
x x
x
x
x x
=
-+
£
+
£
³
1d
2d
X
Calcoliamo punti estremi e direzioni estreme
a
b
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 22 / 3,1/ 3
1,0
d
d
=
=
1 2 1 =( , ) 3 3 d 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 1 0 2 1 2 1 0 1 1 2 2 2 2 2 2 2 1 d d d d d d d d 3 1 0 £ d2 £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 Tz
x
x
c
c h
c b
c a
c d
c d
l
l
l
µ µ
l l l
l l l µ µ
=
-
Þ
=
-æ ö
æ ö
æ ö
= -
ç ÷
=
= -
ç ÷
= -
= -
ç ÷
=
-è ø
è ø
è ø
æ
ö
æ ö
= -
ç
÷
= -
= -
ç ÷
=
è
ø
è ø
-
-
-
+
+ + =
³
Soluzione dei problemi di PL: esempio(4)
Ottimo illimitato
(facendo tendere μ1 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
l
l
l
µ
µ
l
l
l
l l l µ µ
= - Þ = -æ ö æ ö æ ö = - ç ÷ = = - ç ÷ = - = - ç ÷ = è ø è ø è ø æ ö æ ö = - ç ÷ = = - ç ÷ = è ø è ø - + + + + + = ³Soluzione dei problemi di PL: esempio(5)
Ottimo finito di valore -2 in corrispondenza del vertice b
ottenuto assegnando alle variabili i valori
μ1, μ2,
