Lezione n ° ° ° ° 6
- Definizione di Iperpiano.
- Insiemi convessi.
- Politopi e poliedri.
- Punti estremi di un poliedro.
- Direzioni estreme di un poliedro.
Lezioni di Ricerca Operativa
Corso di Laurea in Informatica Università di Salerno
Prof. Cerulli – Dott.ssa Gentili – Dott. Carrabs
Iperpiano: generalizzazione della retta
{ x p x k }
H = :
T=
o equivalentemente
{ x p x p x p x k }
H = :
1 1+
2 2+ ... +
n n=
Il vettore p ≠ 0 è detto gradiente o normale dell’iperpiano, ed è la direzione di crescita dell’iperpiano
p è un vettore e k è uno scalare Definizione:
Un insieme geometrico H è un iperpiano se e solo se:
Iperpiano: in particolare
se due vettori hanno prodotto interno nullo allora sono perpendicolari
sottraendo:
Consideriamo un punto x
0di H ed il gradiente p. L’iperpiano H è l’insieme dei vettori x tali che il vettore x-x
0è perpendicolare a p
H
x 0 ∈ p T x 0 = k
H
x ∈ p T x = k 0 )
( x − x 0 =
p T
Esempio in E
2{ x x p x p x k }
H = ( 1 , 2 ) : 1 1 + 2 2 =
x
0p
x
0−
x
Fissiamo un punto x0 ∈ H, e verifichiamo che un qualunque vettore x∈ H è tale che: x-x0 è perpendicolare a p
H
Un iperpiano H divide lo spazio E
ncui appartiene in due semispazi
{ x p x k }
H = : T =
{ x p x k }
S 1 = : T ≥ S 2 = { x : p T x ≤ k }
Gradiente p
Iperpiano H
Esempio
90 °
{ x p x k }
S 1 = :
T≥
{ x p x k }
S 2 = : T ≤
Insieme convesso
[ ] 0,1
)
1
( − ∈
+
= λ x λ y λ
z
Def: Un insieme X è convesso se e solo se dati due punti, x,y ∈ X ogni punto z generato come loro combinazione convessa:
è tale che z ∈ X
x y
z
x y
z
Alcuni insiemi convessi
{ x A x b }
X = : =
Dim.
Dobbiamo dimostrare che un qualunque punto y∈ X può essere espresso come combinazione convessa di due altri punti di X
Consideriamo x, y ∈ X generici.
b y
A X
y
b x
A X
x
⇒ =
∈
⇒ =
∈
Considero il punto z espresso come combinazione convessa di x ed y
y x
z = λ + ( 1 − λ )
Dobbiamo verificare che z appartiene ad X
λ ∈ 0,1 [ ]
Alcuni insiemi convessi:
y x
z = λ + ( 1 − λ )
Premoltiplico per la matrice Ay A x
A z
A = λ + ( 1 − λ )
b b
b b
b b
z
A = λ + ( 1 − λ ) = λ + − λ =
Poiché x ed y appartengono ad X
{ x A x b }
X = : =
Un Iperpiano è un insieme convesso
Un Semispazio è un insieme convesso
L ’ intersezione di iperpiani/semispazi produce un insieme convesso
Altri insiemi convessi
Un poliedro è l ’intersezione di un numero finito di semispazi
Un poliedro X è un insieme convesso
poliedro chiuso e limitato (Politopo)
poliedro illimitato
X Insieme convesso
Esempio: politopo
x y
z
X
Esempio: poliedro illimitato
Insieme convesso
x y
z
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.
Esempio Teorema
Voglio esprimere y come combinazione convessa dei vertici del politopo
( ) 0,1
)
1
2
+ ( − ∈
= λ x λ z λ
y
( ) 0,1
)
1
(
45
+ − ∈
= µ x µ x µ
z
y x
1x
2x
3x
4x
5z
)
1 )(
1 ( )
1
(
5 42
x x
x
y = λ + µ − λ + − µ − λ
sostituisco:
Nota che :
0
) 1
)(
1 ( 0
) 1
(
0 µ − λ ≥ − µ − λ ≥
≥ λ
1.
2.
λ + µ ( 1 − λ ) + ( 1 − µ )( 1 − λ ) = λ + ( 1 − λ )( µ + 1 − µ ) = 1
c.v.d.
la combinazione convessa di permette di ottenere tutti i punti di X ’⊂ X
x
1X
X’’’’
X
Quando un poliedro è illimitato?
In generale:
x
2x
3Bisogna considerare le sue direzioni estreme
x
1x
2x
3d x 0 + λ
Def. Un RAGGIO di vertice x
0e di direzione d è un insieme di punti della forma:
Raggi e direzioni di un poliedro
{ =
0+ : ≥ 0 }
= x x λ d λ
R
x
0d
Raggi e direzioni di un poliedro
X
x
0d
1d
2d
3d
1NON è direzione
d
2è direzione
d
3NON è direzione
0
0
+ λ d , λ ≥ x
Definizione
Dato un poliedro X, il vettore d è una direzione di X se e solo se per ogni punto x
0nell’insieme, il raggio
appartiene a X
Come si calcolano le direzioni di un poliedro?
(Procedimento algebrico)
{ : ≤ , ≥ 0 }
= x A x b x
X (poliedro)
Considerato un qualunque punto x ∈
X:d
è una direzione del poliedro se
0
)
(
0
) (
) (
) (
≠
≥ +
≤ +
d iii
d x
ii
b d
x A i
λ λ
da cui:
0
)
(
0
) (
) (
) (
≠
≥ +
≤ +
d iii
d x
ii
b d
x A i
λ λ
(i) poiché x ∈ X :
⇔
≤ +
⇔
≤
+ d b A x A d b x
A ( λ ) λ
⇔
≥
+ 0
)
( ii x λ 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
⇔
≤ 0 d
λ A A d ≤ 0
≥ 0
d
Esempio 1
( )
≥
≥
≤ +
−
≤ +
−
−
≤ +
= −
0
, 0
8 2
, 2
, 2 3
:
2 1
2 1
2 1
2 1
2 1
x x
x x
x x
x x
,x X x
L’insieme delle direzioni di X è dato dai vettori
≠
=
0 0
2 1
d d d
( )
≥
≥
= +
≤ +
−
≤ +
−
≤ +
= −
0
, 0
, 1
0 2
, 0
, 0 3
:
2 1
2 1
2 1
2 1
2 1
2 1
d d
d d
d d
d d
d d
,d D d
= 3 1 3 2
d
'
= 0
''
1
d
Esempio 2
( )
{
1 2:
1− 2
2≥ − 6
1−
2≥ − 2
1≥ 0
2≥ 1 }
= x ,x x x x x x x
X
L’insieme delle direzioni di X è dato dai vettori
≥
≥
≥
−
≥
−
1 0
0
0 2
2 1
2 1
2 1
d d
d d
d d
≥
≥
≥
≥
1 0 2
2 1
2 1
2 1
d d
d d
d d
≠
=
0 0
2 1
