Lezione n ° ° ° ° 8: Esercitazione
- Variazione del gradiente
- Introduzione di vincoli nel problema - Calcolo delle direzioni estreme
Lezioni di Ricerca Operativa
Corso di Laurea in Informatica ed Informatica Applicata Università di Salerno
Dato il seguente problema di programmazione lineare:
1
X
-1 6
1 (1)
(3) (2)
Gradiente (3,1)
Punto di ottimo (1,0)
A B
C
Valore ottimo ?
1
X
-1 6
1 (1)
(3) (2)
b) Determinare una nuova funzione obiettivo che abbia ottimo illimitato
1
X
-1 6
1 (1)
(3) (2)
c) Determinare una nuova funzione obiettivo che abbia infiniti punti di ottimo
1
X
-1 6
1 (1)
(3) (2)
c) Determinare una nuova funzione obiettivo che abbia infiniti punti di ottimo
1
X
-1 6
1 (1)
(3) (2)
d) Determinare una nuova funzione obiettivo che renda C punto di ottimo unico
A B
C
1
X
-1 6
1 (1)
(3) (2)
e) Aggiungere un vincolo RIDONDANTE
A B
C
NO
1
X
-1 6
1 (1)
(3) (2)
e) Aggiungere un vincolo RIDONDANTE
A B
C
1
X
-1 6
1 (1)
(3) (2)
f) Aggiungere un vincolo che renda in sistema INAMMISSIBILE
A B
C
1
X
-1 6
1 (1)
(3) (2)
A B
C
f) Aggiungere un vincolo che renda in sistema INAMMISSIBILE
1
X
-1 6
1 (1)
(3) (2)
A B
C
g) Aggiungere un vincolo affinchè il punto C diventi punto di ottimo
4
1 6 -1
1 (1)
(3) (2)
A B
C
f) Aggiungere un vincolo che renda la regione ammissibile un politopo.
X
8 8
X
ED
1
X
-1 6
1 (1)
(3) (2)
A B
C
g) Riscrivere il problema applicando il teorema della rappresentazione e risolverlo
Punto di ottimo (1,0) Valore ottimo
1
X
6
-3 -2
-1 1 (1)
(3) (2)
A B
C
Calcoliamo punti estremi e le direzioni estreme A= (1,0)
B= (6,0) C= ?
A= (1,0) , B= (6,0) , C= (3,4)
{
: ≤ , ≥ 0}
= x Ax b x
X (poliedro)
Abbiamo visto che d è una a direzione di X se:
0 0
0
≠
≥
≤ d
d
d
A
A= (1,0) B= (6,0) C= (3,4)
∑
∑
= =+
= t
j
j j k T
i
i i
T x c d
c z
1 1
) (
)
(
min λ µ
+
+
+
+
+
=
2 1
2 ) 1
1 3 3 (
1 3 ) 2
1 3 (
4 ) 3 1 3 0 (
) 6 1 3 0 (
) 1 1 3 (
min
2 1
3 2
1
µ µ
λ λ
λ z
1
3 2 13 7
18 3
min
3 2
1
2 1
3 2
1
= +
+
+ +
+ +
= λ λ
λ
µ µ
λ λ
λ z
t 1,2,..., j
0
k 1,2,..., i
0
, 1
1 1
=
≥
=
≥
∑
==
j i k
i
µ λ λ
1
3 2 13 7
18 3
min
3 2
1
2 1
3 2
1
≥
= +
+
+ +
+ +
= λ λ λ
λ λ
λ
µ µ
λ λ
λ z
A= (1,0) B= (6,0) C= (3,4)
minimo
Valore ottimo
∑
∑
= =+
= t
j
j j k T
i
i i
T x c d
c z
1 1
) (
)
(
min λ µ
1 0
>
d
cT cT d2 > 0
t 1,2,..., j
0
k 1,2,..., i
0
, 1
1 1
=
≥
=
≥
∑
==
j i k
i
µ λ λ
1
X
-1 6
1 (1)
(3) (2)
A B
C
Punto di ottimo (1,0) Valore ottimo
Dato il seguente problema di programmazione lineare:
