Lezioni di Ricerca Operativa
Corso di Laurea in Informatica ed Informatica Applicata
Università di Salerno
Lezione n° 12: 21-22 Aprile 2009
Teoria della dualità:
- Coppia di Problemi Primale/Duale
- Regole di Trasformazione
- Teorema debole della dualità
Anno accademico 2008/2009
Prof. Cerulli – Dott.ssa Gentili
Teoria della Dualità
Ad ogni problema di PL (Primale) è associato un
problema Duale
Problema Primale (P)
Problema Duale (D)
min c1 x1    cn xn
max b1w1    bm wm
s.t.
s.t.
a11 x1    a1n xn  b1
a11w1    am1wm  c1

am1 x1    amn xn  bm

a1n w1    amn wm  cn
x0
(n variabili, m vincoli)
w0
(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.
In forma matriciale:
(P)
T
min c x
Ax  b
x0
x Rn
( D)
T
max b w
A wc
w0
T
w Rm
Duale di un Primale con vincoli di uguaglianza:
(P)
T
min c x
Ax  b
x0
x R
n
( D)
T
max b w
AT w  c
w var .libere
w Rm
Infatti:
Ax  b
Ax  b
Ax  b   Ax  b
equivale a
quindi si introducono 2m variabili duali, u e v
max(bT u  bT v)
ATu  AT v  c
u0 v0
m
u, v R
e sostituendo w= u - v si ottiene (D)
Dualità: regole di trasformazione generali
min
c
b
Ai x  bi
max
b
c
wi  0
Ai x  bi
wi  0
Ai x  bi
wi non vincol ata
xi  0
wAi  ci
xi  0
wAi  ci
xi non vincol ata
wAi  ci
La teoria della Dualità è importante perchè:


le soluzioni di P e D sono legate tra loro;
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 e l’Algoritmo Primale-Duale,
alternativi al Simplesso (Primale) utili per certe classi di
problemi;

la soluzione ottima del duale è un bound sulla
soluzione ottima del primale.

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
(P)
T
min c x
Ax  b
x0
( D)
T
max b w
AT w  c
w0
1. Teorema (debole) della dualità
Siano x e y soluzioni ammissibili rispettivamente per
(P) e (D), allora
T
T
c xb w
Dimostrazione:
w soluzione  AT w  c
x soluzione  A x  b
x  0( A w) x  c x
w  0( A x) T w  b w
T
T
T
T
c x  ( A w) x  x A w  ( A x) w  b w
T
T
T
T
T
T
T
Corollario
Se (P) è illimitato

(D) non è ammissibile
Se (D) è illimitato

(P) non è ammissibile
Se (P) ha soluzione
ottima finita

(D) ha soluzione ottima
finita
Se (D) ha soluzione
ottima finita

(P) ha soluzione ottima
finita