I Costruzione del problema duale

Dualit` a nella Programmazione Lineare

I Problema duale: definizione e motivazioni

I Dualit` a nella PL

I Costruzione del problema duale

BT 4.1, 4.2;

Problema duale

Dato un problema di minimo, detto primale, del tipo:

z ^∗ = min f (x) x ∈ X

costruiamo un nuovo problema, in forma di massimo, detto duale:

w ^∗ = max g(p) p ∈ S per cui, se X 6= ∅, S 6= ∅ risulti

z ^∗ ≥ w ^∗

(relazione di dualit` a debole)

Condizioni di ottimalit` a

I Siano ¯ x ∈ X, ¯ p ∈ S. La dualit` a debole implica che, se

f (¯ x) = g(¯ p) (1)

allora ¯ x e ¯ p sono ottime per i rispettivi problemi

I per alcune classi di problemi si riesce a definire un problema duale per cui

z ^∗ = w ^∗ (relazione di dualit` a forte)

I in questo caso la condizione (1) ` e necessaria e sufficiente di

ottimalit` a

Dualit` a nella PL

Iniziamo con un problema z ^∗ = min{c ^T x : Ax = b, x ≥ 0} in forma standard, assumiamo che esista una soluzione ottima x ^∗ Introduciamo un vettore p ∈ R ^m di moltiplicatori di Lagrange e definiamo il nuovo problema:

g(p) = min c ^T x + p ^T (b − Ax) x ≥ 0

Proposizione

Per ogni vettore p di moltiplicatori, si ha g(p) ≤ z ^∗ Infatti:

g(p) = min

x≥0 c ^T x + p ^T (b − Ax) ≤ c ^T x ^∗ + p ^T (b − Ax ^∗ ) = c ^T x ^∗

Problema duale

La migliore limitazione inferiore del valore ottimo primale z ^∗ si ottiene risolvendo problema:

p∈R max

g(p) no vincoli

questo ` e scelto come problema duale (la dualit` a debole segue dalla

Proposizione)

Struttura del problema duale

g(p) = min _x≥0 c ^T x + p ^T (b − Ax) = p ^T b + min _x≥0 (c ^T − p ^T A)x Analizziamo il secondo termine

min x≥0 (c ^T − p ^T A)x =

( 0 se c ^T − p ^T A ≥ 0 ^T

−∞ altrimenti

Volendo massimizzare g(p), imponiamo il vincolo che esclude il secondo caso:

p∈R max

g(p) no vincoli

⇒ max p ^T b

p ^T A ≤ c ^T

ancora un PL!

PL in forma generale

Trasformiamo il problema in forma standard e ripetiamo la derivazione precedente:

min c ^T x Ax ≥ b

⇒ min c ^T x

Ax − Is = b s ≥ 0 g(p) = min

x free, s≥0

c ^T x + p ^T (b − Ax+Is) =

= p ^T b + min

x free, s≥0

(c ^T − p ^T A)x + p ^T s

PL in forma generale

quindi,

min

x free (c ^T − p ^T A)x =

( 0 se c ^T − p ^T A=0 ^T

−∞ altrimenti

min s≥0 p ^T s =

( 0 se p ^T ≥ 0 ^T

−∞ altrimenti da cui il problema duale:

max p ^T b

p ^T A = c ^T

p ≥ 0

Riassumendo

primale

min c ^T x Ax = b x ≥ 0

duale

max p ^T b p ^T A ≤ c ^T

min c ^T x Ax ≥ b

max p ^T b p ^T A = c ^T

p ≥ 0

Regole di costruzione

primale duale

min c ^T x max p ^T b a ^T _i x ≥ b i , i ∈ M 1 p i ≥ 0, i ∈ M 1

vincoli a ^T _i x ≤ b i , i ∈ M 2 p i ≤ 0, i ∈ M 2 variabili a ^T _i x = b _i , i ∈ M ₃ p _i libero, i ∈ M ₃

x j ≥ 0, j ∈ N 1 p ^T A j ≤ c _j , j ∈ N 1

variabili x _j ≤ 0, j ∈ N ₂ p ^T A _j ≥ c _j , j ∈ N ₂ vincoli

x j libero, j ∈ N 3 p ^T A j = c j , j ∈ N 3