Lezione n° 13
Teoria della dualità:
- Coppia di Problemi Primale/Duale - Regole di Trasformazione
- Teorema debole della dualità
Lezioni di Ricerca Operativa
Corso di Laurea in Informatica Università degli Studi di Salerno
R. Cerulli – F. Carrabs
Teoria della Dualità
Ad ogni problema di PL (Primale) è associato un problema Duale
Problema Primale (P) Problema Duale (D)
(n variabili, m vincoli) (m variabili, n vincoli)
Il problema D ha tante variabili quanti sono i vincoli di P e tanti vincoli quante sono le variabili di P.
min c
1x
1++ c
nx
ns.t.
a
11x
1++ a
1nx
n³ b
1
a
m1x
1++ a
mnx
n³ b
mx³ 0 0
. . max
1 1
1 1
1 11
1 1
³
+
+
+
+
+ +
w
c w
a w
a
c w
a w
a t s
w b w
b
n m
mn n
m m
m m
Teoria della Dualità
33 32
31
23 22
21
13 12
11
a a
a
a a
a
a a
a
3 2
1
c c c
3 2 1
b b b
3 2
1
x x x
3 2 1
w w w
0 . .
min
3 3
33 2
32 1
31
2 3
23 2
22 1
21
1 3
13 2
12 1
11
3 3 2
2 1
1
³
³ +
+
³ +
+
³ +
+
+ +
x
b x
a x
a x
a
b x
a x
a x
a
b x
a x
a x
a t s
x c x
c x
c
t s
w b w
b w
.
b
max
1 1+
2 2+
3 31 3
31 2
21 1
11
w a w a w c
a + +
0 ,
0 ,
0
2 31
3 3
33 2
23 1
13
2 3
32 2
22 1
12
³
³
³
+
+
+
+
w w
w
c w
a w
a w
a
c w
a w
a w
a
In forma matriciale:
Problema Primale (P) Problema Duale (D)
n T
x x
b x
A x c (P)
R
³
³ 0
min
m T
T
w w
c w
A w b
D
R
³
0
max )
(
min c
1x
1++ c
nx
ns.t.
a
11x
1++ a
1nx
n³ b
1
a
m1x
1++ a
mnx
n³ b
mx³ 0 0
. . max
1 1
1 1
1 11
1 1
³
+
+
+
+
+ +
w
c w
a w
a
c w
a w
a t s
w b w
b
n m
mn n
m m
m m
Teoria della Dualità
0 5
1
1 4
2 1 2
4 3
7 2 3
2 1
x x
3 2 1
w w w
0 ,
7 5
1
2 4
3 2
1 2
. .
4 3
min
2 1
1 2 1
2 1
2 1
³
³
³ +
³ +
+
x x
x x x
x x
t s
x x
t s
w w
w .
7 2
3
max
1+
2+
33 5
1 4
2 w
1+ w
2+ w
3 0 ,
0 ,
0
4 2
1
3 2
1
2 1
³
³
³
+
w w
w
w
w
Duale del problema duale
Il duale di questo problema è:
Il duale del problema duale è il problema primale.
- -
T- w
x
( P) max b
Tw A
Tw c
w³ 0 w R
m-min - b
Tw -A
Tw³ -c
w³ 0 w R
m-max -c
Tx - Ax -b
x³ 0 x R
n( D) min c
Tx Ax³ b
x³ 0
x R
nTrasformiamo i vincoli di uguaglianza in vincoli di maggiore o uguale come segue:
equivale a
Duale di un Primale con vincoli di uguaglianza
n T
R x
x
b x
A x c (P)
³
0
min
b x
A
b x
A b
x A
b x
A
-
³ -
³
quindi si introducono 2m variabili duali, u e v
m T T
T T
R v
, u
v u
c v
A u
A
) v b u
b (
³
³
-
- 0 ,
0 max
n T
R x
x
b x
A
b x
A x c (P)
³
-
³ -
³ 0
min
b b A -
A - v
u
c
x
e sostituendo w= u - v si ottiene (D)
m T T
T T
R v
, u
v u
c v
A u
A
) v b u
b (
³
³
-
- 0 ,
0 max
m T
T
R w
v n w
c w
A w b (D)
. . max
n T
R x
x
b x
A x c (P)
³
0
min
• Dato un generico problema di PL, sarebbe
possibile trasformarlo in uno equivalente in forma canonica di min/max per calcolarne il duale
• In realtà, questo non è necessario, in quanto è sempre possibile calcolare direttamente il duale del problema dato
Calcolo del problema duale
Teoria della Dualità
1 8
- 9
12 7 0
8 - 4 1
0 3
5
7 4 2
3 2
1
x x x
3 2 1
w
w
w
Coefficienti f.o.
Termini noti vincoli
Coefficienti vincoli
Dualità: regole di trasformazione generali
Coefficienti f.o.
Termini noti vincoli Coefficienti vincoli
i-mo vincolo (i=1…m)
i-ma variabile (i=1…m)
j-ma variabile (j=1...n)
j-mo vincolo (j=1...n)
min max
c
Tc
b b
TA A
T³ ³ 0
0
n.v.
³ 0
0 ³
n.v.
La teoria della Dualità è importante perchè:
le soluzioni di (P) e (D) sono legate tra loro;
la soluzione ottima del duale è un bound sulla soluzione ottima del primale.
le soluzioni duali hanno un’interpretazione economica utile per l’analisi di sensitività (post-ottimalità);
sulla teoria della dualità sono basati algoritmi, quali il Simplesso Duale, l’Algoritmo Primale-Duale, il Delayed Column Generation alternativi al Simplesso (Primale) utili per certe classi di problemi;
può in certi casi essere conveniente risolvere D al posto di P
(conviene risolvere il problema con il minor numero di vincoli)
Risultati fondamentali della Teoria della Dualità
Siano dati i problemi
1. Teorema (debole) della dualità
Siano x e w soluzioni ammissibili rispettivamente per (P) e (D), allora
0
min
³
³ x
b x
A x c
(P)
T0
max )
(
³
w
c w A
w b D
T T
w b
x
c
T³
TDimostrazione:
0
min
³
³ x
b x
A x c
(P)
T0
max )
(
³
w
c w A
w b D
T T
Risultati fondamentali della Teoria della Dualità
Corollario 1
Se x è una soluzione ammissibile per (P) e w una soluzione
ammissibile per (D) tali che c
Tx=b
Tw allora x e w sono soluzioni ottime dei rispettivi problemi.
Dimostrazione.
Supponiamo per assurdo che x non sia ottimo per (P). Quindi esiste un’altra soluzione ammissibile x* di (P) tale che cTx*< cTx. Ma poiché per ipotesi
cTx=bTw si ha che cTx*<bTw. Assurdo perchè va contro la tesi del teorema debole della dualità.
Risultati fondamentali della Teoria della Dualità
Corollario 2
Se il problema primale (P) è illimitato inferiormente allora il duale (D) è inammissibile. Viceversa se il duale (D) è illimitato
superiormente il primale (P) è inammissibile.
Dimostrazione.
Supponiamo che il valore ottimo del primale (P) sia - e che il problema duale ammetta una soluzione w. Dal teorema della dualità debole si ha che cTx≥bTw per una qualsiasi soluzione ammissibile x di (P). Questo implica che bTw ≤ -. Assurdo.
Risultati fondamentali della Teoria della Dualità
Il corollario 2 stabilisce che l’illimitatezza di un problema implica l’inammissibilità del suo duale. Tuttavia questa non è una
proprietà simmetrica ossia se un problema è inammissibile non è detto che il suo duale sia illimitato. Per esempio:
Calcolare il duale di (P) e
risolvere entrambi i problemi graficamente
0 1
1
min
2 1
2 1
2 1
2 1
