prova scritta del 21 febbraio 2001
Dobbiamo
risolvere il seguente problema di ottimizzazione:
(1) min c(x) = c(x1, x2)
3x1 + x2 < 6
2x1
- 3x2 <
9
x1, x2 >
0
ma non conosciamo la funzione obiettivo. Tuttavia, facendo un test in certi punti, scopriamo che questa assume i valori riportati nella tabella che segue
x1
|
x2 |
c(x) |
1
|
2 |
60 |
|
2 |
0 |
40 |
|
-1 |
-1 |
80 |
|
0 |
3 |
60 |
Valori assunti dalla funzione obiettivo in alcuni punti.
Perbacco,
è evidentemente non lineare… e noi non abbiamo che il simplesso. Un'idea può
essere quella di approssimare la c(x) con un'altra funzione f(x),
stavolta lineare, che abbia distanza minima dai punti riportati in
tabella.
Dando
un'opportuna definizione di distanza della f(x) dai punti
prescritti, formulate in termini di PL il problema di determinarla.
Supponiamo
poi che qualcuno, mosso a compassione, ci dica che f(x) = -13x1 - 2x2 + 65. E' veramente la soluzione
ottima? E qual è la soluzione ottima del problema (1) con la nuova funzione?
Calcolatela usando il metodo del simplesso.
Soluzione
Una
funzione lineare in due variabili individua un piano Q in R3
avente equazione y = a1x1 + a2x2
+ b. Definiamo distanza di tale piano da un punto P di coordinate
note (p1, p2, c(p1,
p2)) come:
d(P, Q)
= | c(p1,
p2) - a1x1 - a2x2 - b |
Definiamo
ora come distanza del piano Q da un insieme di punti la somma delle
distanze del piano dai singoli punti che costituiscono l'insieme (tale scelta,
come del resto quella adottata per d(P, Q) non è l'unica
possibile: si potrebbe ad esempio definire come distanza del piano dai punti il
massimo valore di d(P, Q) conseguito al variare di P
nell'insieme dato).
Ciò
posto, il problema di determinare i coefficienti a1, a2,
b che individuano il piano Q di minima distanza dai punti P1,
…, P4 riportati nella tabella si formula come segue:
min z1
+ z2 + z3 + z4
60
- a1 - 2a2 - b < z1
40
- 2a1 - b < z2
80
+ a1 + a2 - b < z3
60 - 3a2 - b < z4
-60 + a1 + 2a2 + b <
z1
-40 + 2a1 + b
< z2
-80 - a1 - a2 + b < z3
-60 + 3a2
+ b < z4
dove per semplicità di scrittura si è posto zi
= d(Pi, Q). Riordinando le variabili il
problema si riscrive:
min z1 + z2
+ z3 + z4
z1
+ a1 + 2a2 + b >
60
z2
+ 2a1 + b > 40
z3
- a1 - a2 + b > 80
z4 + 3a2 + b > 60
z1
- a1 - 2a2 - b > -60
z2
- 2a1 - b >
-40
z3
+ a1 + a2 - b >
-80
Quindi il piano da essa
individuato dista z1 + z2 + z3 +
z4 = 37 dai quattro punti assegnati.
z1 + a1 + 2a2 + b > 60
z2 + 2a1 + b > 40
z3 - a1 - a2
+ b > 80
z4 + 3a2 + b > 60
z1 - a1 - 2a2 - b > -60
z2 - 2a1 - b > -40
z3 + a1
+ a2 - b > -80
|
a1 |
a2 |
b |
z1 |
z2 |
z3 |
z4 |
|
|
1 |
2 |
1 |
|
|
|
|
60 |
|
2 |
|
1 |
|
1 |
|
|
40 |
|
-1 |
-1 |
1 |
|
|
1 |
|
60 |
|
|
3 |
1 |
|
|
|
1 |
80 |
|
-1 |
-2 |
-1 |
1 |
|
|
|
-60 |
|
-2 |
|
-1 |
|
1 |
|
|
-40 |
|
1 |
1 |
-1 |
|
|
1 |
|
-60 |
|
|
-3 |
-1 |
|
|
|
1 |
-80 |
|
|
|
|
-1 |
-1 |
-1 |
-1 |
-37 |
(i coefficienti in rosso
indicano le diseguaglianze strette). Eliminando z1 si ottiene
|
a1 |
a2 |
b |
z2 |
z3 |
z4 |
|
|
1 |
2 |
1 |
|
|
|
60 |
|
2 |
|
1 |
1 |
|
|
40 |
|
-1 |
-1 |
1 |
|
1 |
|
60 |
|
|
3 |
1 |
|
|
1 |
80 |
|
-1 |
-2 |
-1 |
-1 |
-1 |
-1 |
-97 |
|
-2 |
|
-1 |
1 |
|
|
-40 |
|
1 |
1 |
-1 |
|
1 |
|
-60 |
|
|
-3 |
-1 |
|
|
1 |
-80 |
Eliminando z2
si ha poi
|
a1 |
a2 |
b |
z3 |
z4 |
|
|
1 |
2 |
1 |
|
|
60 |
|
1 |
-2 |
|
-1 |
-1 |
-57 |
|
-1 |
-1 |
1 |
1 |
|
60 |
|
|
3 |
1 |
|
1 |
80 |
|
-3 |
-2 |
-2 |
-1 |
-1 |
-137 |
|
1 |
1 |
-1 |
1 |
|
-60 |
|
|
-3 |
-1 |
|
1 |
-80 |
Passando ora a eliminare z3
ricaviamo
|
a1 |
a2 |
b |
z4 |
|
|
1 |
2 |
1 |
|
60 |
|
|
-3 |
1 |
|
3 |
|
2 |
-1 |
-1 |
|
-117 |
|
|
3 |
1 |
1 |
80 |
|
-2 |
-1 |
-3 |
|
-197 |
|
-4 |
-3 |
-1 |
|
-77 |
|
|
-3 |
-1 |
1 |
-80 |
La colonna z4
può ora essere direttamente eliminata:
|
a1 |
a2 |
b |
|
|
1 |
2 |
1 |
60 |
|
|
-3 |
1 |
3 |
|
2 |
-1 |
-1 |
-117 |
|
|
3 |
1 |
80 |
|
-2 |
-1 |
-3 |
-197 |
|
-4 |
-3 |
-1 |
-77 |
|
|
-3 |
-1 |
-80 |
Nel sistema ottenuto possiamo
pensare di proiettare la variabile a1. Così facendo otteniamo
|
a2 |
b |
|
|
3 |
-1 |
-77 |
|
5 |
3 |
163 |
|
-3 |
1 |
3 |
|
-2 |
-4 |
-314 |
|
-5 |
-3 |
-194 |
|
3 |
1 |
80 |
|
-3 |
-1 |
-80 |
Si tratta dunque di vedere se
esistono punti interni al poliedro:
-3a2 + b <
77
5a2
+ 3b > 163
-3a2 + b >
3
2a2
+ 4b < 314
5a2
+ 3b < 194
che soddisfino l'eguaglianza
3a2 + b = 80. Ricavando da quest'ultima b
= 80 - 3a2 e sostituendo nelle
diseguaglianze che definiscono il poliedro si ha il sistema di intervalli
dell'asse reale
6a2 > 3 Þ a2 > 1/2 = 0.5
4a2 < 77 Þ a2 < 77/4 = 19.25
6a2 < 77 Þ a2 < 77/6 > 12.83
10a2
> 6 Þ a2 > 3/5 = 0.6
4a2 > 46 Þ a2 > 23/2 = 11.5
Poiché l'intervallo aperto
(11.5, 12.83) è non vuoto, segue che la funzione f(x)
proposta non è quella a distanza minima dai punti prescritti.