Lezioni di Ricerca Operativa
Corso di Laurea in Informatica ed Informatica Applicata
Università di Salerno
Lezione n° 5: 17- 18 Marzo 2009
Definizione di Iperpiano.
- Insiemi convessi.
- Politopi e poliedri.
- Punti estremi di un poliedro.
- Direzioni estreme di un poliedro.
Anno accademico 2008/2009
Prof. Cerulli – Dott.ssa Gentili
Iperpiano: generalizzazione della retta
Definizione:
Un insieme geometrico H è un iperpiano se e solo se:

H  x: p x  k
T

o equivalentemente
H  x : p1 x1  p2 x2  ...  pn xn  k 
p è un vettore e k è uno scalare
Il vettore p  0 è detto gradiente o normale
dell’iperpiano, ed è la direzione di crescita
dell’iperpiano
Iperpiano: in particolare
Considerando un punto x0 di H e la direzione p, l’iperpiano H è
l’insieme dei vettori x tali che x-x0 è perpendicolare a p
x0  H
p x0  k
xH
p xk
sottraendo:
T
T
p ( x  x0 )  0
T
se due vettori hanno prodotto interno nullo allora
sono perpendicolari
Esempio in E2

H  ( x1, x2 ) : p1x1  p2 x2  k
Fissiamo un punto x0  H, e
verifichiamo che un qualunque
vettore x H è tale che: x-x0 è
perpendicolare a p
x
p
 x0
H
x0

Un iperpiano H divide lo spazio En cui appartiene in
due semispazi

H  x: p x  k

S1  x : p x  k
T
T



S2  x : p x  k
T

Esempio

Direzione p
S1  x : p x  k
T

90°
Iperpiano H

S2  x : p x  k
T

Insieme convesso
Def: Un insieme X è convesso se e solo se dati due punti, x,y X
ogni punto z generato come loro combinazione convessa:
  0,1
z  x  (1  ) y
è tale che z X
z
x
x
y
z
y
Alcuni insiemi convessi
X   x : Ax  b
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.
x  X  Ax  b
y  X  Ay  b
Considero il punto z espresso come combinazione lineare di x ed y
z   x  (1   ) y
Dobbiamo verificare che z appartiene ad X
X   x : Ax  b
Alcuni insiemi convessi:
z   x  (1   ) y
Premoltiplico per la matrice A
A z  A x  (1   ) A y
Poiché x ed y appartengono ad X
Az  b  (1   )b  b  b  b  b
Verificare che
X
 x , x  :
è un insieme convesso
1
2
2
x1

2
x2

1
Altri insiemi convessi

Un Iperpiano è un insieme convesso

L’intersezione di semispazi è un insieme convesso
Un poliedro è l’intersezione di un numero finito di semispazi
Un poliedro X è un insieme convesso
poliedro chiuso e limitato
(Politopo)
poliedro illimitato
Esempio: politopo
X
x
Insieme convesso
y
z
Esempio: poliedro illimitato
X
y
x
z
Insieme convesso
Vertici di un poliedro
Vertici del Poliedro X o
PUNTI ESTREMI
X
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)
Dato X poliedro chiuso non vuoto con punti estremi
x1, x 2 ,..., x k
ogni punto y  X può essere espresso
come combinazione convessa dei punti estremi di X:
k
y   i x i
i 1
k
con

i 1
i  1
i  0 i  1,2,..., k
Esempio Teorema
Voglio esprimere y come combinazione convessa dei vertici del politopo
y   x 2  (1   ) z
x2
x1
x3
z   x5  (1   ) x 4
  0,1
  0,1
y
sostituisco:
x5
z
x4
y   x 2   (1   ) x 5  (1   )(1   ) x 4
Nota che :
1.
2.
0
(1  )  0
(1  )(1  )  0
  (1  )  (1  )(1  )    (1  )(  1  )  1
c.v.d.
In generale:
la combinazione convessa di x1 x 2 x 3
permette di
ottenere tutti i punti di X’X
x1
x2
X’
X
x3
Quando un poliedro è illimitato?
Bisogna considerare le sue direzioni estreme
Raggi e direzioni di un poliedro
Def. Un RAGGIO di vertice x0 e di direzione d è un
insieme di punti della forma:
R   x  x 0   d :   0
d
x0
x0   d
Raggi e direzioni di un poliedro
 x
Definizione

X

x

 d

X


0.
Dato un poliedro X, il vettore d è una direzione di X se e solo
se per ogni punto x0 nell’insieme, il raggio
x0   d ,   0
appartiene ad X
d1 NON è direzione
d1
x0
X
d2
d3
d2 è direzione
d3 NON è direzione
Come si calcolano le direzioni di un poliedro?
(Procedimento algebrico)
X   x : Ax  b, x  0
(poliedro)
Considerato un qualunque punto x  X:
d è una direzione del poliedro se
(i ) A( x   d )  b
(ii ) x   d  0
(iii )
d 0
da cui:
(i ) A( x   d )  b
(ii ) x   d  0
(iii )
d 0
(i) poiché x  X :
A( x   d )  b  Ax  Ad  b  Ad  0  Ad  0
(ii )
x  d  0  d  0
Quindi le direzioni d del poliedro X sono tutti e soli i vettori tali che:
Ad  0
d 0
d 0
Adesso vediamo un esempio
poi vediamo come si
interpretano
geometricamente
Esempio 1
x1,x2  : 3x1  x2  2,  x1  x2  2,  x1  2 x2  8
X 

 x1  0, - x2  2, x2  0

L’insieme delle direzioni di X è dato dai vettori
 d1   0 
d      
 d2   0 
d1,d 2  : 3d1  d 2  0,  d1  d 2  0,  d1  2d 2  0
D

d1  d 2  1, d1  0, d 2  0

2
 
'
3

d 
1 
 
3
d
''
1 
  
 0
Esempio 2
X   x1,x2 : x1  2x2  6 x1  x2  2 x1  0 x2  1
L’insieme delle direzioni di X è dato dai vettori
 d1   0 
d      
 d2   0 
 x1 
tali che considerato un generico punto x    : x   d  X
 x2 
 x1  d1  2( x2  d 2 )  6
 x  d  x  d  2
 1
1
2
2

 x1  d1  0
 x2  d 2  1
 x1  d1  2( x2  d 2 )  6
 x  d  x  d  2
 1
1
2
2

 x1  d1  0
 x2  d 2  1
Da cui deriva:
d1  0
d  0
 2

d1  2d 2
d1  d 2
 x1  2 x2  (d1  2d 2 )  6
 x  x  (d  d )  2
 1 2
1
2

 x1  d1  0
 x2  d 2  1