Lezioni di Ricerca Operativa
Corso di Laurea in Informatica ed Informatica Applicata
Università di Salerno
Lezione n° 6: 23-24 Marzo 2009
- Cono di recessione.
- Teorema della rappresentazione.
Anno accademico 2008/2009
Prof. Cerulli – Dott.ssa Gentili
Come si calcolano le direzioni di un poliedro?
(Procedimento geometrico)
X   x : Ax  b, x  0
(poliedro)
Abbiamo visto che è una a direzione del poliedro se:
Ad  0
d 0
d 0
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
Coni Convessi
Definizione:
Un cono convesso C è un insieme convesso con la seguente proprietà
per ogni x  C   x  C
 0
C
Un cono convesso è un insieme convesso che contiene raggi che
partono dall’origine (perché?)
Nota:
alcuni raggi possono essere espressi come
combinazione lineare di altri
C
In generale:
un cono convesso può essere espresso in funzione dei suoi raggi
Solo alcuni raggi sono sufficienti (detti RAGGI ESTREMI) perché gli
altri sono espressi come combinazione lineare di questi
Coni Convessi
Dato un insieme di vettori d1,d2,…,dk il cono convesso generato da
questi vettori è dato da:
k

C    j d j :  j  0 j  1,2 ,...,k 
 j 1

d1
d2
d3
C
d4
d5
Cono poliedrale
Il CONO POLIEDRALE è un particolare tipo di cono definito
dall’intersezione di un numero finito di semispazi che passano
per l’origine ed è descritto tramite il sistema:
Ax  0
Direzioni estreme di un poliedro
Definizione
Una direzione d di un poliedro X, è una direzione
estrema di X se e solo se non è esprimibile come
combinazione lineare di altre direzioni di X.
X
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 i  1,2,..., k
e direzioni estreme d j j  1,2,..., t
Ogni punto xX può essere espresso come combinazione
convessa dei punti estremi di X e combinazione lineare
non negativa delle sue direzioni estreme:
k
t
i 1
j 1
x   i x i    j d j
k
 1
i 1
i
i  0 i  1,2,..., k
 j  0 j  1,2,..., t
x2
z
x1
y
x3
d1
d2
x4
y   x 2  (1   ) x 3
z  y  d1
quindi:
  0,1
 0
z   x 2  (1   ) x3   d 1
Soluzione dei problemi di PL
Consideriamo il problema (PL) in Forma Standard
min z  c x
s.t. A x  b
x  0
T
xi i  1,2,..., k punti estremi
d j j  1,2,..., t 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:
k
t
i 1
j 1
x   i x i    j d j
k
 1
i 1
i
i  0 i  1,2,..., k  j  0 j  1,2,..., t
Possiamo trasformare il problema di PL in un nuovo problema con incognite:
1 ,2 ,...k e 1, 2,…, t
k
t
i 1
j 1
min z   (c xi ) i   (cd j ) j
k
λ i  1
i 1
λ i  0 i  1,2,...,k μ j  0 j  1,2,...,t
Nota:
1. se esiste una direzione dj tale che cdj< 0  l’ottimo del problema è illimitato
2. se cdj>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
cxj , scegliere il minimo ad esempio cxp e fissare p=1 e tutti gli altri uguali
a zero
RIASSUMENDO:
1. la soluzione ottima di un problema di
programmazione lineare è finito se e solo se cdj > 0 per
ogni dj
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
min z  x1  3 x2
Calcoliamo punti estremi
- x1  x2  2
e direzioni estreme
- x1  2 x2  6
x1 , x2  0
a
b
h
d
X
1
d
2
Soluzione dei problemi di PL: esempio(2)
- x1  x2 = 2; x1 =0  x 2 =2; x 2 =0  x1 =-2
- x1  2 x2 = 6; x1 =0  x 2 =3; x 2 =0  x1 =-6
- x1  x2 = 2  x2  2  x1

- x1  2 x2 = 6   x1  4  2 x1  6  x1  2, x2  4
(0,3)
(-6,0)
(-2,0)
a  (2,4)
b  (0,2)
h  (0,0)
X
Soluzione dei problemi di PL: esempio(3)

( d1 , d 2 ) : -d1  d 2  0, - d1  2d 2  0, d1  d 2  1
D

d

0,
d

0

2

 1
d1  1  d 2  1  d 2  d 2  0,1  d 2  2d 2  0  d 2  1/ 3
0  d 2  1/ 3, d1  1  d 2 
d   2 / 3,1/ 3
1
d  1,0 
2
X
2 1
1
d =( , )
3 3
d  (1,0)
2
Soluzione dei problemi di PL: esempio(4)
min z  x1  3x2  c  (1, 3)
T
 0
0
2
T
T
c h  (1, 3)    0; c b  (1, 3)    6; c a  (1, 3)    10;
 0
2
4
 2 / 3
1 
T 1
T 2
c d  (1, 3) 
 1/ 3; c d  (1, 3)    1;

 1/ 3 
 0
T
min 01  62  103  1/ 31  2
1  2  3  1
1 , 2 , 3, 1 , 2  0
Ottimo illimitato
(facendo tendere μ1 a ∞ la
f.o. tende a - ∞
indipendentemente dai valori
scelti per le altre variabili)
Soluzione dei problemi di PL: esempio(5)
Consideriamo una differente funzione obiettivo
min z  4x1  x2  c  (4, 1)
T
 0
0
 2
T
T
c h  (4, 1)    0; c b  (4, 1)    2; c a  (4, 1)    4;
 0
 2
4
 2 / 3
1 
T 1
T 2
c d  (4, 1) 
 7 / 3; c d  (4, 1)    4;

 1/ 3 
 0
T
min 01  22  43  7 / 31  4 2
1  2  3  1
1 , 2 , 3, 1 , 2  0
Ottimo finito di valore -2 in
corrispondenza del vertice b,
ottenuto assegnando alle
variabili i valori
μ1, μ2, λ1, λ3=0, λ2=1