1 Dualit´a Dato un problema di PL in forma canonica max c

(1)

1 Dualit´a

Dato un problema di PL in forma canonica max c^Tx

A^Tx≤ b x≥ 0

che chiameremo problema primale, possiamo associare ad esso un altro problema di PL, detto problema duale, definito come segue

min b^Tx Au≥ c

u≥ 0 Indichiamo con

Da ={u ∈ R^m : Au≥ c, u ≥ 0}

la regione ammissibile del problema duale e con

Dott={u^∗∈ Da : b^Tu^∗≤ b^Tu ∀ u ∈ Da}

l’insieme delle sue soluzioni ottime. Si pu´o notare che esiste una stretta relazione tra

• variabili del primale e vincoli del duale;

• vincoli del primale e variabili del duale.

In particolare notiamo che

1. nel primale ci sono n variabili esattamente come nel duale vi sono n vincoli. Inoltre, i coefficienti del j-esimo vincolo del duale coincidono con i coefficienti della variabile x_jnei vincoli del primale, mentre il termine noto del j-esimo vincolo del duale coincide con il coefficiente di x_jnell’obiettivo del primale.

2. Nel primale vi sono m vincoli esattamente come nel duale vi sono m variabili. Inoltre, i coefficienti dell’i-esima variabile ui del duale coincidono con i coefficienti dell’i-esimo vincolo del primale, mentre il coefficiente di uinell’obiettivo del duale coincide con il termine noto dell’i-esimo vincolo del primale.

Le soluzioni dei due problemi primale e duale sono fortemente legati tra loro come dimostra una serie di risultati.

Osservazione 1 Per ogni x0∈ Sa e per ogni u0∈ Da si ha che c^Tx0≤ b^Tu0.

(2)

Dimostrazione x₀∈ Sa implica

A^Tx0≤ b

o, equivalentemente, prendendo la trasposta di entrambi i membri

b^T ≥ x^T0A. (1)

Inoltre u0 ∈ Da implica u0 ≥ 0 e quindi, moltiplicando entrambi i membri di (1) per u0 si ottiene

b^Tu0≥ (x^T0A)u0= x^T₀(Au0). (2) Ma ancora u₀∈ Da implica anche

Au₀≥ c

da cui, moltiplicando entrambi i membri per x^T₀ (che ´e≥ 0 per l’appartenenza di x₀ a S_a), si ottiene

x^T₀(Au0)≥ x^T0c = c^Tx0

che, combinato con (2), dimostra il risultato.

Osservazione 2 Se x^∗∈ Sa e u^∗∈ Da ed inoltre c^Tx^∗= b^Tu^∗ allora x^∗∈ Sott e u^∗∈ Dott.

Dimostrazione In base all’Osservazione 1 si ha che

∀ x ∈ Sa c^Tx≤ b^Tu^∗. Ma essendo c^Tx^∗= b^Tu^∗ si ha anche

∀ x ∈ Sa c^Tx≤ c^Tx^∗

il che equivale a dire che x^∗∈ Sott. In modo del tutto analogo si dimostra che u^∗∈ Dott.

Osservazione 3 Se uno dei due problemi ha obiettivo illimitato, allora l’altro ha regione ammissibile vuota.

(3)

Dimostrazione Dimostriamo che se l’obiettivo primale ´e illimitato, allora D_a=

∅ (la dimostrazione che l’obiettivo duale illimitato implica Sa = ∅ ´e del tut- to analoga). Supponiamo per assurdo che Da 6= ∅ e sia u0 ∈ Da. In base all’Osservazione 1 si ha che

∀ x ∈ Sa c^Tx≤ b^Tu0

e quindi l’obiettivo del primale ´e limitato dal valore b^Tu0, il che contraddice l’illimitatezza di tale obiettivo.

Osservazione 4 Il duale del problema duale coincide con il problema primale.

Dimostrazione Per determinare il duale del problema duale dobbiamo prima trasformare quest’ultimo in forma canonica nel modo seguente

− max −b^Tu

−Au ≤ −c (3)

u≥ 0

(4) Il duale di (3) ´e il seguente

− min −c^Tx

−A^Tx≥ −b x≥ 0 o, equivalentemente,

max c^Tx A^Tx≤ b

x≥ 0 che, come si vede, coincide con il primale.

Dimostreremo ora il I teorema della dualit´a.

Teorema 1 Uno dei due problemi ha soluzioni ottime se e solo se anche l’altro ha soluzioni ottime. Formalmente, Sott 6= ∅ se e solo se Dott 6= ∅. Inoltre, i valori ottimi dei due problemi coincidono.

Dimostrazione Per dimostrare questo risultato dobbiamo dapprima notare che ad ogni base del primale ´e strettamente legata, nel senso che specificheremo, una

(4)

Tabella 1:

x^T u −A^T b

z c^T 0

Tabella 2:

u^T

x A −c

w −b^T 0

base del problema duale. Riscriviamo il primale con l’aggiunta delle variabili u per i vincoli come visto sino ad ora

max z = c^Tx u =−A^Tx + b

x≥ 0 u ≥ 0

Riscriviamo anche il duale (dopo averlo trasformato nella forma canonica (3)) con l’aggiunta di variabili x per i vincoli

− max w =−b^Tu x = Au− c u≥ 0 x ≥ 0

Si tenga sempre presente che le variabili x, u che compaiono nel primale sono diverse dalla variabili x, u che compaiono nel duale, ma in virt´u delle strette relazioni tra di esse conviene indicarle allo stesso modo.

Prendiamo ora la Tabella 1 relativa alla base{x1, . . . , xn} del primale e la Ta- bella 2 relativa alla base{u1, . . . , um} del duale. Posiiamo notare che la tabella della base{x1, . . . , xn} del primale coincide con la trasposta cambiata di segno della tabella relativa alla base{u1, . . . , um} del duale. Questa osservazione vale pi´u in generale. Si ha infatti che:

Data una base {y1, . . . , yn} del primale, la tabella relativa a tale base ´e uguale alla trasposta cambiata di segno della tabella relativa alla base{yn+1, . . . , yn+m} del duale.

Supponiamo oea di avere una base ottima {y1, . . . , y_n} per il primale. Nella relativa Tabella 3 avremo β_i ≥ 0, i = 1, . . . , m e γj ≤ 0, j = 1, . . . , n. La

(5)

Tabella 3:

y1 · · · yn

y_n+1 · · · · · · · · · β₁ ... ... ... ... ... yn+m · · · · · · · · · βm

z γ1 · · · γn γ0

Tabella 4:

yn+1 · · · yn+m

y1 · · · · · · · · · −γ1

... ... ... ... ... y_n · · · · · · · · · −γn

w −β1 · · · βm −γ0

soluzione ottima per il primale ´e

yj= 0, j = 1, . . . , n yn+i= βi i = 1, . . . , m

con valore ottimo pari a γ0. Consideriamo ora la Tabella 4 per la base{yn+1, . . . , yn+m} del duale, che, in base a quanto osservato precedentemente, coincide con la trasposta cambiata di segno della Tabella 3. Si pu´o notare che la soluzione di base corrsipondente, ovvero

y_j=−γj, j = 1, . . . , n y_n+i= 0 i = 1, . . . , m

´

e ammissibile poich´e

−γj≥ 0 j = 1, . . . , n ed ´e anche ottima poich´e

−βi≤ 0 i = 1, . . . , m.

Questo dimostra che nel momento in cui il simplesso restituisce una soluzione ottima per il primale, si pu´o immediatamente ottenere anche una soluzione ottima per il duale. Resta ancora da far vedere che i due valori ottimi coincidono.

Il valore ottimo del primale é γ0. Dalla Tabella 4 si ha che l’ottimo per il duale é pari a−γ0ma dobbiamo ricordare che abbiamo trasformato il duale nella forma canonica (3) il cui obiettivo é

− max −b^Tu

e quindi per ottenere l’esatto valore ottimo dell’obiettivo duale dobbiamo invertire di segno, ottenendo quindi il valore γ₀che coincide con il valore ottimo del

(6)

primale, come si voleva dimostrare.

Riassumiamo ora tutte le possibili relazioni tra primale e duale.

• In base al I teorema della dualit´a

Sott6= ∅ ⇔ Dott6= ∅

In base allo stesso teorema si ha anche che i valori ottimi coincidono.

• Se Sott =∅ in quanto l’obiettivo primale ´e illimitato, allora Da =∅ (per l’Osservazione 3).

• Se Dott = ∅ in quanto l’obiettivo duale ´e illimitato, allora Sa = ∅ (per l’Osservazione 3).

• Se Sa=∅, allora Da =∅ oppure l’obiettivo duale ´e illimitato.

• Se Da=∅, allora Sa =∅ oppure l’obiettivo primale ´e illimitato.

Il seguente ´e un esempio in cui sia S_a che D_a sono insiemi vuoti.

Esempio 1 Si consideri il seguente problema primale max 2x₁− x2

x1− x2≤ 1

−x1+ x₂≤ −2 x1, x2≥ 0

Si noti che Sa =∅. Si trovi ora il duale di tale problema:

min u₁− 2u2

u1− u2≥ 2

−u1+ u₂≥ −1 u1, u2≥ 0 in cui si pu´o notare che anche Da =∅.

Introduciamo ora il II teorema della dualit´a.

Teorema 2 Si ha che x^∗∈ Sott e u^∗∈ Dott se e solo se x^∗ e u^∗ appartengono rispettivamente a Sa e Da e soddisfano le condizioni di complementarit´a, cio´e

(b− A^Tx^∗)^Tu^∗= 0, (5)

e

(Au^∗− c)^Tx^∗= 0. (6)

(7)

Dimostrazione Se valgono (5) e (6), sommandole tra loro si ottiene b^Tu^∗− x^∗TAu^∗+ u^∗TA^Tx^∗− c^Tx^∗= 0

o, equivalentemente,

b^Tu^∗− x^∗TAu^∗+ x^∗TAu^∗− c^Tx^∗ = 0 da cui

b^Tu^∗= c^Tx^∗.

In base all’Osservazione 2, ci´o implica che le due soluzioni sono ottime.

Vediamo ora di dimostrare il viceversa, ovvero che se le due soluzioni sono ottime soddisfano le condizioni di complementarit´a. Per il I teorema della dualit´a sappiamo che

b^Tu^∗= c^Tx^∗. Ora, sommiamo e sottraiamo x^∗TAu^∗ ed otteniamo

b^Tu^∗− x^∗TAu^∗+ x^∗TAu^∗− c^Tx^∗ = 0 che possiamo riscrivere come segue

(b− A^Tx^∗)^Tu^∗+ (Au^∗− c)^Tx^∗= 0. (7) Ora, x^∗∈ Sa implica

b− A^Tx^∗≥ 0 x^∗≥ 0, mentre u^∗∈ Da implica

Au^∗− c ≥ 0 u^∗≥ 0.

Quindi avremo

(b− A^Tx^∗)^T

| {z }

≥0

u^∗

|{z}

≥0

≥ 0

(Au^∗− c)^T

| {z }

≥0

x^∗

|{z}

≥0

≥ 0

In base a (7) la somma di questi due termini deve essere uguale a 0. L’unica possibilitá é che entrambi i termini siano nulli, e cioé che siano soddisfatte le condizioni di complementaritá (5) e (6).

2 Il simplesso duale

Nel simplesso visto in precedenza, che chiameremo simplesso primale seguiamo il seguente schema

(8)

Tabella 5:

y1 · · · yn

y_n+1 · · · · · · · · · β₁ ... ... ... ... ... yn+m · · · · · · · · · βm

z γ1 · · · γn γ0

• cominciamo con una base ammissibile {y1, . . . , y_n} per il primale (tutti i β_i ≥ 0) ma con la base corrispondente del duale {yn+1, . . . , y_n+m} non ammisibile per il duale (qualche γ_j > 0);

• passiamo ad altre basi ammissibili per il primale ma con le corrispondenti basi duali non ammissibili;

• se esistono soluzioni ottime, ci arrestiamo quando abbiamo non solo una base ammissibile per il primale, ma anche la base corrispondente del duale anch’essa ammissibile (tutti i γj ≤ 0).

Si supponga ora di avere una base{y1, . . . , y_n} non ammissibile per il primale ma con la corrispondente base del duale{yn+1, . . . , y_n+m} ammissibile. Quindi, data la Tabella 5 relativa alla base{y1, . . . , yn} del primale, avremo che

∃ i ∈ {1, . . . , m} : βi< 0, (non ammissibilit´a della base primale) e

γj≤ 0, j = 1, . . . , n

(ammissibilit´a per il duale). Il simplesso duale non ´e altro che il simplesso applicato al problema duale, in cui seguiremo quindi il seguente schema

• cominciamo con una base ammissibile {yn+1, . . . , yn+m} per il duale (tutti i γj ≤ 0) ma con la base corrispondente del primale {y1, . . . , yn} non ammisibile per il primale (qualche βi< 0);

• passiamo ad altre basi ammissibili per il duale ma con le corrispondenti basi primali non ammissibili;

• se esistono soluzioni ottime, ci arrestiamo quando abbiamo non solo una base ammissibile per il duale, ma anche la base corrispondente del primale anch’essa ammissibile (tutti i βi≥ 0).

Nel simplesso duale si opera direttamente sulla tabella primale e quindi, ricor- dando che la tabella duale ´e la trasposta cambiata di segno di quella primale, dovremo tenere presente di invertire i ruoli di righe e colonne e di cambiare i segni. Un’iterazione del simplesso duale ´e la seguente.

(9)

Verifica di ottimalit´a Se

βi≥ 0 i = 1, . . . , m

allora la base corrente ´e ottima, la soluzione di base del primale yj= 0 j = 1, . . . , n yn+i= βi i = 1, . . . , m

´e ottima per il primale, mentre la soluzione di base

yj=−γj j = 1, . . . , n yn+i= 0 i = 1, . . . , m

´e ottima per il duale. Altrimenti si va al Passo 2.

Scelta della riga del cardine Scegli la riga k tale che β_k= min{βi} < 0

(per convenzione la prima dall’alto se il minimo ´e raggiunto su pi´u righe).

Verifica di illimitatezza del duale Se

αkj≤ 0 j = 1, . . . , n,

allora il duale ´e illimitato (e di conseguenza, in base all’Osservazione 3, per il primale si ha Sa=∅). Altrimenti si vada al Passo 4.

Scelta della colonna del cardine Tra le colonne j con αkj > 0 si scelga la colonna h tale che

− γh

αkh

= min

−γj

αkj

: αkj> 0

.

(nel caso il minimo sia raggiunto in pi´u colonne si sceglie, per convenzione, la prima da sinistra).

Operazione di cardine Si esegua l’operazione di cardine con cardine αkhe si ritorni al Passo 1.

3 Altre osservazioni sulla dualit´a

Una possibile domanda che ci si puó porre é la seguente. Se ho un vincolo a^T_ix ≤ bi di un prblema di PL il cui valore ottimo indicheremo con γ^∗, come varia il valore dell’ottimo se perturbo di una piccola quantitá ∆bi il termine noto del vincolo, ovvero trasformo il vincolo in a^T_ix ≤ bi+ ∆bi? La risposta

´

e strettamente legata alla soluzione del duale. Infatti, si prenda la soluzione ottima del duale e sia u^∗_i il valore nell’ottimo del duale della variabile legata al vincolo a^T_i x≤ bi del primale. Si pu´o dimostrare che se la soluzione ottima

(10)

del primale ´e non degenere, allora per piccole perturabzioni ∆b_i il nuovo valore ottimo sar´a γ^∗+ u^∗_i∆bi. Come verifica su un esempio, si determini la soluzione ottima del problema

max x₁− x2

x1+ x2≤ 2 x1≤ 1 x₁, x₂≥ 0

e del suo duale e si determini come cambia il valore ottimo del problema se il vincolo x1≤ 1 viene sostituito da x1≤ 1 + ∆, per ∆ sufficientemente piccolo.

Abbiamo visto sino ad ora come si determina il duale di un problema di PL in forma canonica. E possibile per´´ o determinare il duale anche di problemi di PL in forma piú generale. Come per i problemi in forma canonica, vi sará una stretta relazione tra le variabili di un problema ed i vincoli dell’altro. Piú precisamente avremo, come per la forma canonica, che:

1. nel primale ci sono n variabili esattamente come nel duale vi sono n vincoli. Inoltre, i coefficienti del j-esimo vincolo del duale coincidono con i coefficienti della variabile xjnei vincoli del primale, mentre il termine noto del j-esimo vincolo del duale coincide con il coefficiente di xjnell’obiettivo del primale.

2. Nel primale vi sono m vincoli esattamente come nel duale vi sono m variabili. INoltre, i coefficienti dell’i-esima variabile ui del duale coincidono con i coefficienti dell’i-esimo vincolo del primale, mentre il coefficiente di uinell’obiettivo del duale coincide con il termine noto dell’i-esimo vincolo del primale.

Rispetto alla forma canonica quello che puó cambiare sono i versi delle disequa- zioni ed i segni delle variabili. Per stabilire questi ci si puó rifare allo specchiet- to nella Tabella 6. Lo specchietto ci dice, per esempio, che se il primale é un problema di massimo ed una variabile é nel primale≥ 0, allora il vincolo corrispondente del duale é di≥, oppure che se il primale é un problema di minimo ed un vincolo del primale é di =, allora la variabile corrsipondente del duale é libera in segno (puó assumere sia valori negativi che positivi). Come esercizio, si usi lo specchietto per trovare il duale del seguente problema di PL.

min x1+ 2x2+ 3x3

x1+ x2− x3≤ 1 x₁− 2x2+ x₃≥ 2

x1− x2− x3= 4 x₁≥ 0, x2≤ 0, x3libera

(11)

Tabella 6:

min max

variabile≥ 0 vincolo≤ variabile≤ 0 vincolo≥ variabile libera vincolo = vincolo≥ variabile≥ 0 vincolo≤ variabile≤ 0 vincolo = variabile libera