1

Teoria della Dualità:I – Introduzione

Daniele VigoD.E.I.S. – Università di Bologna

dvigo@deis.unibo.it

rev. 1.2 – Maggio 2004

Dual-I.2D. Vigo

Dualità• Per ogni problema PL, detto primale, ne esiste un

altro, detto duale, costruito utilizzando gli stessi coefficienti (trasposti)

• Le soluzioni dei due problemi sono tra loro strettamente legate

• La soluzione del problema duale fornisce informazioni sulla soluzione del problema primale

2

Dual-I.3D. Vigo

Dualità (2)• Problema primale (in forma standard)

min {cTx : A x = d, x ≥ 0}• Criterio di ottimalità del problema primale:

x*T = ( xB | 0 ) è ottimo solo se c’T ≥ 0 dove c’T = cT– cB B–1 A =[ cT

B – cTB B–1 B | cT

F – cTB B–1F]

cT – cB B–1 A ≥ 0

0 cTF´

Dual-I.4D. Vigo

Dualità (3)• Costruzione del problema duale• cT, A dati di ingresso• uT vettore di m variabili corrispondenti alla scelta

di una base B per il primale: uT = cB B–1

• la base ottima si ha u*T = cB B–1 che è soluzione ammissibile di

uTA ≤ cT, u libera • Utilizzando come funzione obiettivo uTd si ha che

u*T d = cBB–1d = cTx*

• Problema duale: max{ uTd: uTA ≤ cT, u libera }

3

Dual-I.5D. Vigo

Dualità (4)

• Problema primale (in forma standard):min {cTx : A x = d, x ≥ 0}

sol. ottima

sol. amm.

• Problema duale:max{ uTd: uTA ≤ cT, u libera} sol.

amm.

z

Dual-I.6D. Vigo

Dualità (5)• tabella per Primale in forma di minimo

Primale Duale z = min cTx w = max uTd

ai x ≥ di ui ≥ 0ai x ≤ di ui ≤ 0ai x = di ui libera

xj ≥ 0 uTAj ≤ cj

xj ≤ 0 uTAj ≥ cj

xj libera uTAj = cj

4

Dual-I.7D. Vigo

Esempio 1• Consideriamo un problema primale, lo risolviamo

e ricaviamo una soluzione del duale

min z = 2x1 +3x2 + x3

2x1 + x2 = 1 x1 + x3 = 4x1, x2, x3, ≥ 0

Dual-I.8D. Vigo

Esempio 1 (2)

1014x3

0121x2

00–5–7–zx3x2x1

A

1–1/207/2x3

01/211/2x1

05/20–9/2–zx3x2x1

Y

5

Dual-I.9D. Vigo

Esempio 1 (3)

⎥⎥⎦

⎤

⎢⎢⎣

⎡=

−

−

10

21

21

1B

⎥⎦

⎤⎢⎣

⎡=

1102

Bmin z = 2x1 +3x2 + x3

2x1 + x2 = 1 x1 + x3 = 4x1, x2, x3, ≥ 0

cTB Y = [2 1] Y = [2 1/2 1]

c’ T = c – cTB Y = [2 3 1] – [2 1/2 1] = [0 5/2 0]

B–1 A = Y

Dual-I.10D. Vigo

Esempio 1 (4)min z = 2x1 +3x2 + x3

2x1 + x2 = 1 x1 + x3 = 4x1, x2, x3, ≥ 0

max w = u1 + 4u2

2u1 + u2 ≤ 2u1 ≤ 3

u2 ≤ 1u1 , u2 libera

uT = cTB B–1 = [1/2 1]

1

1

u2

u13

6

Dual-I.11D. Vigo

Esempio 2 • risolviamo un Primale ed il suo Dualemin z = 2x1 +x2 +x3

x1 +x3 = 4 x2 +2x3 ≥ 2

x1, x2, ≥ 0

x3 libera

min z = 2x1 +x2 +x3+ –x3

–

x1 +x3+ –x3

– = 4 x2 +2x3

+ –2x3– − x4 = 2

x1, x2, x3+, x3

–, x4 ≥ 0

Dual-I.12D. Vigo

Esempio 2 (2)0 2 1 1 –1 0

x1 x2 x3+ x3

– x4

–z –10 0 0 –3 3 1

0

–1

x1 4 1 0 1 –1

x2 2 0 1 2 –2x1 x2 x3

+ x3– x4

–z –7 0 3/2 0 0 –1/2

1/2

–1/2

x1 3 1 –1/2 0 0

x3+ 1 0 1/2 1 –1

7

Dual-I.13D. Vigo

Esempio 2 (3)

Soluzione: z = 4 ; x1 = x2 = 0 ; x3 = 4

x1 x2 x3+ x3

– x4

–z –4 1 1 0 0 0

1

0

x4 6 2 –1 0 0

x3+ 4 1 0 1 –1

Dual-I.14D. Vigo

Esempio 2 (4)• Duale:

max w = 4u1 +2u2u1 ≤ 2 (ridondante)

u2 ≤ 1u1 +2u2 = 1u1 libera

u2 ≥ 0

–min –w = – 4u1+ +4u1

– – 2u2

u2 +u3 = 1u1

+ – u1– +2u2 = 1

u1+, u1

–, u2 , u3 ≥ 0

8

Dual-I.15D. Vigo

Esempio 2 (5)

0 –4 4 –2 0u1

+ u1– u2 u1

s

–z 4 0 0 6 0

1

0

u1s 1 0 0 1

u1+ 1 1 –1 2

Soluzione : w = 4 ; u1 = 1; u2 = 0

( N.B. w = z )

Dual-I.16D. Vigo

Proprietà fondamentaliTh. Il duale del duale è il primale

Dim.a) partiamo da un primale in forma generale

(P) z = min cT xai

T x = d i ∈ Mai

T x ≥ d i ∈ M’xj ≥ 0 j ∈ N

xj libera j ∈ N’

9

Dual-I.17D. Vigo

Il duale del duale è il primale (2)b) ne facciamo il duale

(D) w = max uT dui libera i ∈ M

ui ≥ 0 i ∈ M’uT Aj ≤ cj j ∈ NuT Aj = cj j ∈ N’

c) lo riscriviamo in forma “primale”

– min (– dT )uui liberaui ≥ 0(– Aj

T ) u ≥ –cj

(– Aj T ) u = –cj

Dual-I.18D. Vigo

Il duale del duale è il primale (3)d) ne facciamo il duale usando la variabile x

– max xT (– c ) xj ≥ 0 j ∈ N

xj libera j ∈ N’(– aj

T) x ≤ –di i ∈ M(– ai

T) x = –di i ∈ M’

da cui si ottiene il primale

z = min cT xxj ≥ 0xj liberaai

T x = dai

T x ≥ d

10

Dual-I.19D. Vigo

Proprietà “debole” della dualitàTh. (Dualità debole):

Data una coppia Primale–Duale min {cTx :A x ≥ d, x ≥ 0}, max{uTd: uTA ≤ cT, u ≥ 0}sia X la regione ammissibilità di P ed U quella di D, per ogni x∈X ed u∈U risulta:

cT x ≥ uT dDim.

Ax ≥ d, u ≥ 0 → uT Ax ≥ uT duTA ≤ cT, x ≥ 0 → uT Ax ≤ cT xda cui si ottiene cTx ≥ uT Ax ≥ uT d

Dual-I.20D. Vigo

Proprietà “forte” della dualitàTh. (Dualità forte):Se il primale ha soluzione ottima finita,

1) anche il suo duale ha soluzione ottima finita;2) i valori della due soluzioni sono uguali.

Dim. punto 1) :x, u = sol. ammissibili di (P) e (D)dualità debole ⇒ costo primale ≥ costo duale⇒(D) non può avere soluzione illimitata.

(D) ha la soluzione ammissibile uT = cBT B–1

(B= base ottima di (P), che ha sol. ottima finita)⇒(D) non è impossibile ed ha una sol. ottima finita

11

Dual-I.21D. Vigo

Proprietà “forte” della dualità (2)Dim. punto 2) :

la soluzione ammissibile di (D) uT* = cBT B–1

ha costo uT*d= cB

T B–1 d = cTx*

uguale al costo della soluzione ottima di (P)

Dual-I.22D. Vigo

Possibili Coppie Primale-Duale

(P) ↓ (D)→ Ottimo finito Illimitato Impossibile

Ottimo finito Si(1) NO(a) NO(a)

Illimitato NO(a) NO(b) SI(3)

Impossibile NO(a) SI(3) SI(2)

(P) min {cTx :A x ≥ d, x ≥ 0}, (D) max{uTd: uTA ≤ cT, u ≥ 0}

SI(1) e NO(a) verificati nel teorema della dualità forte

12

Dual-I.23D. Vigo

Possibili Coppie Primale-Duale (2)(P) min {cTx :A x ≥ d, x ≥ 0}(D) max {uTd: uTA ≤ cT, u ≥ 0}

Verifichiamo NO(b)

• Se il primale ha soluzione illimitata (= –∞) , • il duale non può avere soluzione illimitata (= +∞)

(per la dualità debole: cTx ≥ uTd)

Dual-I.24D. Vigo

Possibili Coppie Primale-Duale (3)• Verifichiamo che il caso SI(2) può verificarsi:

min x1

x1 + x2 ≥ 1– x1 – x2 ≥ 1

x1 , x2 libere(primale impossibile)

max u1 + u2

u1 – u2 = 1 u1 – u2 = 0u1 , u2 ≥ 0

(duale impossibile) ⇒ SI(2)

13

Dual-I.25D. Vigo

Possibili Coppie Primale-Duale (4)• Verifichiamo che il caso SI(3) può verificarsi:

min x1

x1 + x2 ≥ 1– x1 – x2 ≥ 1

x1 , x2 ≥ 0(primale impossibile)

max u1 + u2

u1 – u2 ≤ 1u1 – u2 ≤ 0u1 , u2 ≥ 0

(duale illimitato) ⇒ SI(3)

Dual-I.26D. Vigo

Teorema degli scarti complementari• Definisce la condizione di ottimalità per una

coppia Primale-DualeTh.

Una coppia (x, u) di soluzioni ammissibili per una coppia Primale-Duale è ottima se e solo se valgono le seguenti condizioni di ortogonalità:

• ti = ui (aiT x – di) = 0 ∀ i (α )

• vj = (cj – uT Aj) xj = 0 ∀ j (β )

14

Dual-I.27D. Vigo

Teorema degli scarti complementari (2)Dim.ti ≥ 0 ∀ i ( se ai

Tx = di ⇒ ti = 0 ,se ai

Tx ≥ di⇒ ui ≥ 0 ⇒ ti ≥ 0 ) vj ≥ 0 ∀ j ( analogamente)siano inoltre:

01

≥= ∑=

m

iitt 0

1≥= ∑

=

n

jjvv

e si noti che t = v = 0 ⇔ tutte le (α) e (β) valgono

Dual-I.28D. Vigo

Teorema degli scarti complementari (3)

quindi tutte le (α ),(β ) valgono ⇔ uTd = cTx⇔ (x, u) sono ottime

01 111

=⎟⎠

⎞⎜⎝

⎛−+⎟⎟

⎠

⎞⎜⎜⎝

⎛−=+ ∑ ∑∑∑

= ===

n

jj

m

iijij

n

jijij

m

ii xaucdxauvt

da cui t + v = 0 ⇔ tutte le (α) e (β ) valgono

0=−= duxc TT

15

Dual-I.29D. Vigo

Teorema degli scarti complementari (4)• Conseguenze delle condizioni di ortogonalità1. ∀ vincolo j non soddisfatto all’uguaglianza dalla

soluzione ottima di (D) (uTAj < cj), nella soluzione ottima di (P) la corrispondente variabile deve essere xj = 0, e viceversa.

2. ∀ variabile j non nulla (xj > 0) nella soluzione ottima di (P), il corrispondente vincolo di (D) deve essere soddisfatto in modo stretto (uTAj = cj ) dalla soluzione ottima di (D)

• Relazioni analoghe tra i vincoli primali e variabili duali

Dual-I.30D. Vigo

Esempio 1• Consideriamo una coppia Primale-Duale nota• Data la soluzione di (P) ricaviamo quella di (D) dal

teorema degli scarti complementari• ti = ui (ai

T x – di) = 0 ∀ i (α )• vj = (cj – uT Aj) xj = 0 ∀ j (β )

min z = 2x1 + x2 + x3 x1 + x3 = 4 → 1a cond. (α) OK

x2 +2x3 ≥ 4 x1, x2, ≥ 0

x3 libera

16

Dual-I.31D. Vigo

Esempio 1 (2)• Soluzione ottima di (P)• z = 4• x1 = x2 = 0 → 1a e 2a cond. (β ) OK; x3 = 4 • 2a cond. (α): u2 ( x2 + 2x3 – 2 ) = 0 ⇒ u2 = 0• 3a cond. (β ): (1 – u1 + 2u2 ) x3 = 0 ⇒ u1 = 1• soluzione ottima del duale u1 = 1, u2 = 0, w = 4

Dual-I.32D. Vigo

Esempio 2• Dato il primalemin z = x1 + x2 + x3 + x4 + x5

3 x1 +2x2 + x3 = 15x1 + x2 + x3 + x4 = 32 x1 +5x2 + x3 + x5 = 4 x1 , x2 , x3 , x4 , x5 ≥ 0

Forma standard ⇒ tutte le condizioni (α) OKSoluzione ottima: z = 9/2

x1 = x3 = 0 ⇒ 1a e 3a cond. (β ) OKx2 = 1/2, x4 = 5/2, x5 = 3/2

17

Dual-I.33D. Vigo

Esempio 2 (2)Duale: max w = u1 + 3u2 + 4u3

3u1 + 5u2 + 2u3 ≤ 12u1 + u2 + 5u3 ≤ 1

u1 + u2 + u3 ≤ 1u2 ≤ 1

u3 ≤ 1u1 , u2 , u3 libere

• 4a cond. (β ): 1 = u2 ; 5a cond. (β ): 1 = u3

• 2a cond. (β ): 1 = 2u1 + u2 + 5u3 ⇒ u1 = – 5/2• w = 9/2

Dual-I.34D. Vigo

Esempio 3Primale: Duale:min x1 + x2 max –2u1 + 12u2

x1 – x2 ≥ 2 – u1 + 3u2 ≥ 1 3x1 – 2 x2 ≥ 12 u1 – 2u2 ≥ 0

x1 , x2 ≥ 0 u1 , u2 ≥ 0

• Risolviamo il primale per via grafica

18

Dual-I.35D. Vigo

Esempio 3 (2)

x1

x2

x1 = 16/5, x2 = 6/5

min x1 + x2

x1 – x2 ≥ 23x1 – 2 x2 ≥ 12x1 , x2 ≥ 0

6

4

Dual-I.36D. Vigo

Esempio 3 (3)• Ricaviamo la soluzione ottima duale con il

teorema degli scarti complementari

x1 – x2 = 2 → u1 ≠ 0 3x1 + 2 x2 = 12 → u2 ≠ 0x1=16/5 > 0 → – u1 + 3u2 = 1 x2= 6/5 > 0 → u1 – 2u2 = 1

u1 = 1/5 , u2 = 2/5

19

Dual-I.37D. Vigo

Interpretazione economica del duale(P) min cTx (D) max uTd

A x ≥ d uTA ≤ cT

x ≥ 0 u ≥ 0

Base ottima B → z* = cBT B–1d = u*d

∗−∗

==∂∂ uBc

dz T

B1

Dual-I.38D. Vigo

Interpretazione economica (2)• ui

* è la variazione della funzione obiettivo che si ottiene se il termine noto dell’ i–esimo vincolo primale cambia di un unità

• Le variazioni duali u* sono i prezzi ombra del vettore dei termini noti

• Dato un problema primale in forma canonica in cui cTx rappresenta il costo necessario a produrre xunità, ui

* è il costo incrementale che dobbiamo pagare per avere un unità in più della risorsa i–esima.

20

Dual-I.39D. Vigo

Esempio• Problema della dieta:

• Almeno 9 unità giornaliere di vitamina A• Almeno 19 unità giornaliere di vitamina C

Alimenti

A)C)

Prezzo unitario

x1 x2 x3 x4 x5 x6 Fabbisogno

1 0 2 2 1 2 ≥ 90 1 3 1 3 2 ≥19

35 30 60 50 27 22

Dual-I.40D. Vigo

Esempio (2)Problema della dieta (Primale)

min 35x1 + 30x2 + 60x3 + 50x4 + 27x5 + 22x6 x1 + 2x3 + 2x4 + x5 + 2x6 ≥ 9

x2 + 3x3 + x4 + 3x5 + 2x6 ≥ 19x1 ,……. , x6, ≥ 0

21

Dual-I.41D. Vigo

Esempio (3)Duale del problema della dieta

max 9u1 + 19u2

u1 ≤ 35u2 ≤ 30

2u1 + 3u2 ≤ 602u1 + u2 ≤ 50

u1 + 3u2 ≤ 272u1 + 2u2 ≤ 22

u1 , u2 ≥ 0

Dual-I.42D. Vigo

Esempio (4)• Interpretazione del duale:

• 1 variabile per ogni sostanza nutritiva • f. obiettivo: max 9u1 + 19u2

• 1 vincolo per ogni alimento : 2u1 + u2 ≤ 60 Problema del produttore di pillole:Definire il prezzo di pillole ciascuna contente un’unità di una sostanza in modo che • il ricavo complessivo ottenibile dalla dieta sia massimo • il prezzo del contenuto di sostanze di un alimento

somministrato con pillole sia competitivo con il prezzo dell’alimento

22

Dual-I.43D. Vigo

Esempio (5)max 9u1+19u2

u1 ≤ 35u2 ≤ 30

2u1 +3u2 ≤ 602u1 + u2 ≤ 50u1 +3u2 ≤ 272u1 +2u2 ≤ 22u1 , u2 ≥ 0

u1* = 3 , u2

* = 840

30

20

10

u2

10 20 30 40 u1

Dual-I.44D. Vigo

Esempio (6)• u1

* = 3 , u2* = 8: prezzo che si deve pagare se

nella dieta aumenta di un unità la quantità di vitamina A e C, rispettivamente

• Risolviamo il primale con il teorema degli scarti complementari (uT ( Ax – b ) = 0 ) ) :

u > 0 ⇓

x1 + 2x3 + 2x4 + x5 + 2x6 = 9x2 + 3x3 + x4 + 3x5 + 2x6 = 19

23

Dual-I.45D. Vigo

Esempio (6)• Sostituendo la soluzione duale nei vincoli si vede

che i primi quattro non sono soddisfatti all’uguaglianza

• Scarti complementari: (uTA –cT ) x = 0 uTAj < cj , j = 1,…, 4 ⇒ x1,…, x4 = 0

x5 + 2x6 = 93x5 + 2x6 = 19

⇓x5 = 5, x6 = 2