TeoriadellaDualit`a Capitolo4

(1)

Capitolo 4

Teoria della Dualit` a

4.1 Dualit` a per problemi in forma standard

Si consideri il seguente problema di programmazione lineare in forma standard:

z^∗ = max c^Tx s.a Ax = b

x ≥0,

(P_s)

dove A ∈ R^m×n, b ∈ R^m e c ∈ Rⁿ sono i dati del problema, x ∈ Rⁿ`e il vettore delle variabili e z^∗ indica il valore ottimo (se esiste).

Supponiamo di essere alla ricerca di upper-bound per il valore ottimo z^∗, cio`e di valori u tali che z^∗ ≤u. Si noti che, dato un qualunque vettore y ∈ R^m, ciascun vettore x che sia soluzione ammissibile di (Ps) soddisfa l’equazione

y^T(Ax) = y^Tb. (4.1)

Inoltre, assumendo che valga la relazione A^Ty ≥ c, poich´e x `e non-negativo vale la disuguaglianza c^Tx ≤(A^Ty)^Tx =(y^TA)x. Dunque, usando l’uguaglianza (4.1), si trova

c^Tx ≤(y^TA)x = y^T(Ax) = y^Tb = b^Ty. (4.2) Ricapitolando, dato un qualunque y ∈ R^m tale che A^Ty ≥ c, ogni x ammissibile per (Ps) soddisfa c^Tx ≤ b^Ty. Ne segue che z^∗≤b^Ty, dunque il valore b^Tyè un upper-bound per il valore ottimo z^∗. Se siamo alla ricerca del miglior upper-bound (cioè quello di valore minimo) che può essere ricavato con questa tecnica, dovremo determinare il valore ottimo d^∗ del programma lineare

d^∗ = min b^Ty

s.a A^Ty ≥ c. (D_s)

Quest’ultimo programma lineare `e detto il problema duale di (Ps), che `e invece chiamato problema primale.

Teorema 4.1 (Teorema di Dualit`a Debole – forma standard) Se x `e una soluzione ammissibile di (P_s) e y `e una soluzione ammissibile di (D_s), allora c^Tx ≤ b^Ty.

33

(2)

Dimostrazione. Vale la catena di relazioni (4.2), dove la prima disuguaglianza segue da A^Ty ≥ c e x ≥ 0, mentre la seconda uguaglianza vale perch´e Ax = b. ◻

Dal Teorema di Dualit`a Debole discende il seguente criterio di ottimalit`a.

Corollario 4.2 Siano x^∗ una soluzione ammissibile per (Ps) e y^∗ una soluzione ammissibile per (Ds). Se c^Tx^∗=b^Ty^∗, allora x^∗ e y^∗ sono soluzioni ottime dei rispettivi problemi.

Dimostrazione. Se x^∗non fosse ottima, allora esisterebbe un’altra soluzione ammissibile ¯xper il problema primale tale che c^Tx > c¯ ^Tx^∗=b^Ty^∗, contraddicendo il Teorema di Dualit`a Debole.

Analogamente, se y^∗ non fosse ottima, allora esisterebbe un’altra soluzione ammissibile ¯y per il problema duale tale che b^Ty < b¯ ^Ty^∗=c^Tx^∗, contraddicendo il Teorema di Dualità Debole. ◻ Corollario 4.3 Se uno dei problemi (Ps) e (Ds) è illimitato, allora l’altro è inammissibile.

Dimostrazione. Supponiamo che (Ds) abbia una soluzione ammissibile ¯y. Allora, per il Teorema di Dualità debole, c^Tx ≤ b^Ty¯ per ogni x che sia ammissibile per (Ps), pertanto quest’ultimo problema non è illimitato. L’altra metà del corollario si dimostra in modo

analogo. ◻

Enunciamo ora un risultato fondamentale, posponendone la dimostrazione alla Sezione 4.1.1.

Teorema 4.4 (Teorema di Dualit`a Forte – forma standard) Se (P_s) ha una soluzione ottima x^∗, allora (Ds) ha una soluzione ottima y^∗; inoltre, vale la relazione c^Tx^∗=b^Ty^∗.

Si noti che il teorema appena enunciato afferma che, nel caso di un programma lineare che ha una soluzione ottima, il miglior upper-bound che è possibile ricavare tramite la tecnica descritta sopra è in realtà il miglior upper-bound esistente in assoluto per il problema (Ps), cioè il suo valore ottimo.

4.1.1 Dualit`a, basi ottime e metodo del simplesso

Si considerino il problema (P_s) ed il suo duale (D_s). Sia B una base (non necessariamente ammissibile) per il problema (Ps). Come noto, la soluzione di base di (Ps) associata a B `e il vettore ¯x definito da

¯

x_N =0, x¯_B=A⁻_B¹b.

Definiamo

¯

y = A^−⊺_B c_B, dove A^−⊺_B =(A⁻B¹)^T =(A^TB)⁻¹. Si noti che

c^Tx = c¯ ^T_Bx¯_B=c^T_BA⁻_B¹b =(A^−⊺Bc_B)^Tb =y¯^Tb = b^Ty.¯

Pertanto, se ¯x`e ammissibile per (Ps) e ¯y `e ammissibile per (Ds), allora, per il Corollario 4.2,

¯

xe ¯y sono soluzioni ottime per i rispettivi problemi.

Cerchiamo dunque di capire quando ¯x e ¯y sono soluzioni ammissibili per i problemi (P_s) e (Ds) rispettivamente. Il vettore ¯x `e ammissibile per il problema primale se e solo se

¯b = A⁻_B¹b ≥0.

(3)

4.2. DUALIT `A PER PROBLEMI IN ALTRE FORME 35 Osserviamo che questa condizione `e sempre verificata durante l’esecuzione del metodo del simplesso (nella sua seconda fase).

Il vettore ¯y, invece, `e ammissibile per il duale se e solo se A^Ty ≥ c, cio`e se e solo se¯

A^T_By ≥ c¯ _B (4.3)

A^T_Ny ≥ c¯ _N. (4.4)

Poiché A^T_By = A¯ ^T_BA^−⊺_B cB=cB, la condizione (4.3) è sempre verificata. Dunque ¯yè ammissibile se e solo se A^T_NA^−⊺_Bc_B ≥c_N, cioè se e solo se

cN−A^T_NA^−⊺_BcB≤0.

Si noti che il primo membro di quest’ultima disequazione è precisamente il vettore ¯c_N definito in (3.7), cioè il vettore dei costi ridotti delle variabili non in base relativo alla base B. Pertanto possiamo affermare che ¯y è ammissibile se e solo se

¯ c_N ≤0.

Si noti che questa `e esattamente la condizione che si verifica quando il metodo del simplesso termina con una soluzione ottima.

Ricapitolando, ¯x e ¯y sono ammissibili per i rispettivi problemi se e solo se ¯b ≥ 0 e ¯cN ≤0.

Inoltre, come osservato sopra, se ¯x e ¯y sono ammissibili allora sono soluzioni ottime dei rispettivi problemi. Possiamo dunque affermare che, quando il metodo del simplesso termina con una soluzione ottima di base ¯x ed una base B che determina tale soluzione, il vettore

¯

y = A^−⊺_Bc_B `e una soluzione ottima del problema duale. Poich´e il metodo del simplesso con la regola di Bland termina sempre, la discussione svolta finora dimostra il Teorema 4.4.

Data una base B per il problema (Ps), B `e detta una base ammissibile nel primale se

¯b = A⁻_B¹b ≥0, cioè se ¯x è una soluzione ammissibile per il problema primale (P_s). B è detta una base ammissibile nel duale se ¯c_N = c_N −A^T_NA^−⊺_Bc_B ≤ 0, cioè se ¯y è ammissibile per il problema duale (Ds). Quanto visto sopra mostra che se B è una base ammissibile sia nel primale che nel duale, allora i corrispondenti vettori ¯x e ¯y sono soluzioni ottime dei rispettivi problemi. Per questo motivo, B è detta una base ottima se è ammissibile sia nel primale che nel duale.

Dunque, se (Ps) ha soluzione ottima, allora il metodo del simplesso (nella sua seconda fase) mantiene una base ammissibile nel primale ad ogni iterazione e termina quando raggiunge una base ammissibile anche nel duale, cio`e quando arriva ad una base ottima.

4.2 Dualit` a per problemi in altre forme

In questa sezione vediamo come sia possibile scrivere il problema duale anche per programmi lineari non in forma standard.

4.2.1 Forma canonica

Si consideri il seguente problema di programmazione lineare:

z^∗ = max c^Tx s.a Ax ≤ b

x ≥0.

(Pc)

(4)

(Problemi di questo tipo sono detti in forma canonica.) Vogliamo derivare il problema duale di (Pc).

Metodo 1 Come fatto per i problemi in forma standard, cerchiamo degli upper-bound per il valore ottimo z^∗. Dato un qualunque vettore y ∈ R^m tale che y ≥ 0, ogni vettore x che sia soluzione ammissibile del problema (Pc) soddisfa la disequazione

y^T(Ax) ≤ y^Tb.

(Si noti come qui sia fondamentale richiedere la non-negatività di y, a differenza del caso della forma standard, dove questa condizione non era necessaria.) Inoltre, se vale A^Ty ≥ c, allora, poiché x è non-negativo, vale la disuguaglianza c^Tx ≤(y^TA)x. Dunque otteniamo

c^Tx ≤(y^TA)x = y^T(Ax) ≤ y^Tb = b^Ty.

Ricapitolando, dato un vettore y ∈ R^m che soddisfi A^Ty ≥ c e y ≥ 0, si ha c^Tx ≤ b^Ty per ogni x ammissibile per (P_c). Ne segue che z^∗ ≤b^Ty. Il miglior upper-bound che `e possibile trovare in questo modo `e dato dal valore ottimo d^∗ del problema

d^∗ = min b^Ty s.a A^Ty ≥ c

y ≥0,

(Dc)

che `e detto il problema duale di (P_c).

Metodo 2 Scriviamo il problema (Pc) in forma standard aggiungendo variabili di scarto s =(s1, . . . , sm)^T ai vincoli del sistema Ax ≤ b:

max c^Tx +0^Ts s.a Ax + Is = b

x ≥0, s ≥ 0.

In base a quanto visto nella Sezione 4.1 per i problemi in forma standard, il duale di quest’ultimo programma lineare è precisamente (Dc). Possiamo dunque concludere che il Teorema di Dualità Debole (con i relativi corollari) ed il Teorema di Dualità Forte valgono anche per problemi in forma canonica.

4.2.2 Altre forme

Consideriamo ora un programma lineare in forma generica:

z^∗ = max c^Tx

s.a Ax ≤ b. (Pg)

Possiamo trasformare (Pg) in un problema equivalente in forma canonica sostituendo il vettore xcon l’espressione lineare x^′−x^′′, dove x^′e x^′′sono vettori di variabili non-negative in Rⁿ(la stessa idea era stata usata nella dimostrazione della Proposizione 1.2). Otteniamo dunque

max c^Tx^′−c^Tx^′′

s.a Ax^′−Ax^′′≤b x^′, x^′′≥0,

(5)

4.2. DUALIT `A PER PROBLEMI IN ALTRE FORME 37 il cui duale sappiamo essere

min b^Ty s.a A^Ty ≥ c

−A^Ty ≥ −c y ≥0, che `e equivalente a

min b^Ty s.a A^Ty = c

y ≥0.

(Dg)

Questo `e il duale del problema (Pg).

Possiamo dunque affermare che il Teorema di Dualit`a Debole (con i relativi corollari) ed il Teorema di Dualit`a Forte valgono per problemi generali di programmazione lineare.

Riportiamo qui soltanto il Teorema di Dualit`a Forte.

Teorema 4.5 (Teorema di Dualit`a Forte) Se il programma lineare (P_g) ha una soluzione ottima x^∗, allora il suo duale (Dg) ha una soluzione ottima y^∗; inoltre, vale la relazione c^Tx^∗=b^Ty^∗.

4.2.3 Duale del duale

Teorema 4.6 Dato un programma lineare (P ), il duale del duale di (P ) `e (equivalente a) (P ).

Dimostrazione. Consideriamo un problema di programmazione lineare in forma standard (Ps), il cui duale `e (D_s) (partiamo dalla forma standard, ma potremmo partire da una qualunque delle altre forme viste). Se scriviamo (Ds) nella forma equivalente

−max −b^Ty s.a −A^Ty ≤ −c,

sappiamo dalla Sezione 4.2.2 che il duale di quest’ultimo programma lineare `e il seguente:

−min −c^Tx s.a −Ax = −b,

x ≥0.

Quest’ultimo problema `e equivalente al problema primale di partenza (Ps). ◻ Il teorema precedente implica il seguente rafforzamento del Teorema di Dualit`a Forte enunciato in precedenza.

Teorema 4.7 (Teorema di Dualit`a Forte – versione rafforzata) Dati due programmi lineari (P ) e (D), l’uno il duale dell’altro, se uno dei due ha soluzione ottima, allora entrambi i problemi hanno soluzione ottima. Inoltre, date due soluzioni ottime x^∗ e y^∗ per (P ) e (D) rispettivamente, vale la relazione c^Tx^∗=b^Ty^∗.

(6)

Il teorema precedente ed il Corollario 4.3 implicano che ogni coppia primale/duale di problemi di programmazione lineare soddisfa una delle alternative rappresentate nella tabella seguente.

Primale

Sol. ottima Inammissibile Illimitato

Sol. ottima Possibile NO NO

Duale Inammissibile NO Possibile Possibile

Illimitato NO Possibile NO

Si noti, in particolare, che se i due problemi sono entrambi ammissibili, allora ammettono entrambi soluzione ottima (e i valori ottimi coincidono).

4.2.4 Dualit`a in generale

Abbiamo visto nelle sezioni precedenti che ogni problema di programmazione lineare ammette un problema duale, legato al primo dal Teorema di Dualit`a Forte. Proponiamo di seguito una

“ricetta” pi`u raffinata per formulare un problema duale a partire dal primale. A differenza di quanto visto nella sezione precedente, tale “ricetta” tiene conto di ciascun vincolo e di ciascuna variabile separatamente. Sia dunque A una matrice m × n con righe a^T₁, . . . , a^T_m e colonne A₁, . . . , A_n, siano b ∈ R^m e c ∈ Rⁿ e si consideri il seguente generico problema di programmazione lineare:

max c^Tx (4.5)

s.a a^T_ix ≤ b_i, i =1, . . . , h (4.6) a^T_ix ≥ b_i, i = h +1, . . . , k (4.7) a^T_ix = b_i, i = k +1, . . . , m (4.8)

xj ≥0, j =1, . . . , p (4.9)

xj ≤0, j = p +1, . . . , q (4.10) x_j libera, j = q +1, . . . , n. (4.11) Il problema duale avr`a tante variabili quante sono le righe di A e tanti vincoli quante sono le variabili del primale; inoltre valgono le relazioni indicate nella seguente tabella.

max c^Tx min b^Ty

a^T_ix ≤ bi yi≥0 i =1, . . . , h a^T_ix ≥ b_i y_i≤0 i = h +1, . . . , k a^T_ix = bi yi libera i = k +1, . . . , m

xj ≥0 A^T_jy ≥ cj j =1, . . . , p x_j ≤0 A^T_jy ≤ c_j j = p +1, . . . , q x_j libera A^T_jy = c_j j = q +1, . . . , n

(7)

4.3. SCARTI COMPLEMENTARI 39

La tabella si legge in entrambi i sensi: da sinistra a destra per ottenere il duale di un problema di massimo (che sar`a un problema di minimo) e da destra a sinistra per ottenere il duale di un problema di minimo. Il problema duale ottenuto utilizzando questa “ricetta”

coincide con (o `e equivalente a) quello che si otterrebbe tramite le tecniche viste nelle sezioni precedenti; il vantaggio consiste nel non doversi ridurre ad una forma particolare per scrivere il duale.

4.3 Scarti complementari

Teorema 4.8 (Teorema degli Scarti Complementari – forma standard) Sia (P) un programma lineare in forma standard e siano ¯x,y¯ soluzioni ammissibili rispettivamente per (P) e per il suo duale (D). Allora ¯x e ¯y sono ottime per i rispettivi problemi se e solo se valgono le condizioni degli scarti complementari:

Per ogni j ∈{1,... ,n}, ¯x^j =0 oppure ¯y soddisfa ad uguaglianza il corrispondente vincolo duale.

Dimostrazione. Il problema primale in forma standard ha la forma max c^Tx

s.a Ax = b x ≥0, mentre il duale `e il seguente:

min b^Ty s.a A^Ty ≥ c.

Dall’ammissibilit`a di ¯x e ¯y segue

c^Tx ≤¯ (A^Ty¯)^T¯x =y¯^TA¯x =y¯^Tb = b^Ty.¯ (4.12) Per il Teorema di Dualità Forte, ¯x e ¯y sono ottime per i rispettivi problemi se e solo se c^Tx = b¯ ^Ty, cioè se e solo se in (4.12) c’è uguaglianza ovunque. Ci`¯ o si verifica se e solo se c^Tx =¯ (A^Ty¯)^Tx¯ e dunque se e solo se(A^Ty − c¯ )^Tx =¯ 0. Scritta più esplicitamente, la condizione

`e n

∑

j=1

(A^Tjy − c¯ _j)¯x^j=0.

Poich´e ¯x_j ≥ 0 e A^T_jy − c¯ _j ≥ 0 per ogni j, questo avviene se e solo se tutti i termini della sommatoria sono nulli; in altre parole, se e solo se per ogni j ∈{1,... ,n} almeno uno tra ¯x^j

e A^T_jy − c¯ _j `e uguale a zero. ◻

Si noti che la discussione svolta nella Sezione 4.1.1 mostra che ad ogni iterazione del metodo del simplesso (nella sua seconda fase) le soluzioni primale e duale associate alla base corrente B soddisfano sempre le condizioni degli scarti complementari. Infatti, le uniche variabili ¯x_j che possono assumere valore positivo sono quelle tali che j ∈ B; ma allora il corrispondente vincolo duale fa parte del sottosistema (4.3), che, come visto, `e soddisfatto ad uguaglianza. Tuttavia,

(8)

le due soluzioni non sono ottime fintantoché non è garantita l’ammissibilità di entrambe, cosa che avviene solo dopo l’ultima iterazione.

Forniamo ora l’equivalente del Teorema 4.8 per programmi lineari generici. La dimostrazione, qui omessa, pu`o essere ricavata in modo simile lavorando direttamente sulla catena di uguaglianze e disuguaglianze analoga a (4.12) che `e possibile scrivere per il particolare problema in esame, oppure riconducendosi alla forma standard.

Teorema 4.9 (Teorema degli Scarti Complementari) Dato un programma lineare ge- nerico (4.5)–(4.11) e date una sua soluzione ammissibile ¯x ed una soluzione ammissibile ¯y per il suo duale, ¯x e ¯y sono ottime per i rispettivi problemi se e solo se valgono le condizioni degli scarti complementari:

Per ogni j ∈{1,... ,n}, ¯x^j =0 oppure ¯y soddisfa ad uguaglianza il corrispondente vincolo duale.

Per ogni i ∈{1,... ,m}, ¯yi =0 oppure ¯xsoddisfa ad uguaglianza il corrispondente vincolo primale.

Si noti che se una variabile primale è libera, allora il corrispondente vincolo duale è un vincolo di uguaglianza, dunque la corrispondente condizione di complementarietà è sempre verificata (perché assumiamo che le soluzioni siano ammissibili); simmetricamente, se una variabile duale è libera, allora il corrispondente vincolo nel primale è un vincolo di uguaglianza, dunque la corrispondente condizione è sempre verificata. (Per questo motivo, per i problemi in forma standard abbiamo omesso le condizioni relative alle variabili duali.)

4.4 Interpretazione economica della dualit` a

4.4.1 Mercato ombra

Quando un programma lineare descrive un problema di natura economica, anche il duale gene- ralmente ammette un’interpretazione economica. Tale interpretazione dipende dal problema specifico, ma di norma è possibile vedere il duale come il programma lineare che descrive il problema di un operatore intenzionato ad entrare nel mercato, il quale ci propone un’alter- nativa al nostro business (ci si riferisce a questa situazione come mercato ombra). I vincoli del duale possono essere letti come le condizioni che assicurano la concorrenzialità della proposta (cioè il fatto che l’offerta sia economicamente interessante per noi), mentre la funzione obiettivo del duale descriverà il tentativo dell’operatore di trarre il massimo profitto dalla sua entrata nel mercato. Illustriamo tutto ciò tramite un esempio.

Abbiamo a disposizione m risorse da utilizzare per la realizzazione di n tipologie di prodotti. Per ogni risorsa, è nota la quantità disponibile; per ogni tipologia di prodotto, è noto il profitto derivante dalla vendita; inoltre, per ogni tipologia di prodotto si sa anche quale quantità di ciascuna risorsa è necessaria per la realizzazione di una unità di prodotto (potremmo dire che è nota la “ricetta” del prodotto). Si chiede di utilizzare le risorse in modo da massimizzare il profitto totale, assumendo che il mercato sia sempre in grado di assorbire completamente la merce prodotta.

Indicizziamo con i = 1, . . . , m le m risorse e con j = 1, . . . , n le n tipologie di prodotto. Per ogni i, usiamo bi per indicare la quantit`a di risorsa i disponibile; per ogni j, indichiamo con

(9)

4.4. INTERPRETAZIONE ECONOMICA DELLA DUALIT À 41 c_j il profitto derivante dalla vendita di una unità di prodotto j; infine indichiamo con aij la quantità di risorsa i necessaria alla realizzazione di una unità di prodotto j.

Passiamo ora alla scelta delle variabili. Per ogni j, indichiamo con xj la quantit`a di prodotto j che si intende realizzare. Il modello sar`a allora:

max c₁x₁+ ⋅ ⋅ ⋅ + c_nx_n

s.a a_i1x₁+ ⋅ ⋅ ⋅ + a_inx_n ≤b_i, i =1, . . . , m x₁, . . . , x_n≥0.

La funzione obiettivo esprime il profitto totale. I vincoli assicurano che di ogni risorsa i venga usata al massimo una quantità bi per realizzare i vari prodotti. Si noti che è necessario includere nel modello anche le condizioni che impongono la non-negatività delle variabili, in quanto una produzione negativa non ha senso.

Il duale del programma lineare dato sopra `e

min b₁y₁+ ⋅ ⋅ ⋅ + b_my_m (4.13)

s.a a_1jy₁+ ⋅ ⋅ ⋅ + a_mjy_m ≥c_j, j =1, . . . , n (4.14)

y₁, . . . , y_m≥0. (4.15)

Mostriamo ora come tale programma lineare rappresenti una situazione di mercato ombra, come accennato sopra.

Immaginiamo che qualcuno si offra di acquistare le nostre risorse: il problema consiste dunque nello stabilire il prezzo di ciascuna risorsa. Indichiamo con yiil prezzo che l’acquirente

è disposto a pagare per ogni unità di risorsa i. Il costo totale per l’acquisto delle risorse ammonta allora a b₁y₁ + ⋅ ⋅ ⋅ +bmym, che è esattamente l’espressione che il duale tenta di minimizzare. Naturalmente, affinché la proposta possa suscitare il nostro interesse, l’offerta dell’acquirente dovrà essere in qualche modo concorrenziale. In altre parole, accetteremo di vendere le nostre risorse solo se questa operazione ci frutterà un guadagno maggiore di quello che otterremmo usando le risorse per produrre e vendere i prodotti. Possiamo dire che riterremo l’offerta interessante se, per ogni tipologia di prodotto j, ricaveremmo di più (o almeno tanto quanto) dalla vendita delle risorse necessarie a produrre una unità di prodotto j piuttosto che dall’utilizzo delle risorse stesse per la produzione e vendita di una unità del prodotto in questione: questa è esattamente la condizione imposta dal vincolo (4.14). Dunque il duale è il problema che si pone l’acquirente: decidere prezzi di acquisto per le risorse in modo che l’offerta sia conveniente per noi (altrimenti rifiuteremmo certamente) e il costo totale per l’acquisto sia il più piccolo possibile.

Si noti che il Teorema di Dualit`a Debole in questo caso afferma un concetto molto naturale:

una qualunque offerta concorrenziale propostaci dall’acquirente ci farebbe guadagnare non meno che vendere i prodotti realizzati secondo un qualunque piano produttivo. L’ottimalità si ha quando la scelta tra le due opzioni è indifferente (Teorema di Dualità Forte).

4.4.2 Variabili duali come prezzi di equilibrio

Le variabili duali hanno anche un’altra interessante interpretazione. Diamo qui l’enunciato per il caso della forma standard.

(10)

Proposizione 4.10 Si considerino un programma lineare in forma standard ed il suo duale:

max c^Tx min b^Ty

s.a Ax = b s.a A^Ty ≥ c.

x ≥0

Sia B una base ottima del problema primale e siano ¯x,y¯ le corrispondenti soluzioni ottime primale e duale. Allora ciascuna variabile duale ¯yi indica di quanto varierebbe il valore ottimo se il termine noto del corrispondente vincolo primale bi aumentasse di una unit`a e la base ottima restasse la stessa.

Dimostrazione. Si ricordi che ¯xB =A⁻_B¹b, ¯xN =0 e ¯y = A^−⊺_BcB (si veda la Sezione 4.1.1). Sia inoltre ¯z il valore ottimo del problema, cio`e

¯

z = c^Tx = c¯ ^T_Bx¯_B+c^T_Nx¯_N =c^T_BA⁻_B¹b.

Se il termine noto bi viene aumentato di una unità, otteniamo un nuovo vettore dei termini noti b^′ =b + e_i, dove e_i è l’i-esimo vettore della base canonica. Assumendo che la base B sia ottima anche per il problema perturbato, la nuova soluzione ottima primale sarà ¯x^′_B=A⁻_B¹b^′,

¯

x^′_N =0. Allora il nuovo valore ottimo z^′ sar`a

z^′=c^Tx¯^′=c^T_Bx¯^′_B+c^T_Nx¯^′_N =c^T_BA⁻_B¹b^′=c^T_BA⁻_B¹b + c^T_BA⁻_B¹e_i=z +¯ y¯_i,

dove l’ultima uguaglianza vale perch´e c^T_BA⁻_B¹e_i = e^T_iA^−⊺_B c_B = e^T_iy =¯ y¯_i. Dunque la variazione

del valore ottimo `e pari a z^′−z =¯ y¯_i. ◻

Si tenga ben presente che tale interpretazione delle variabili duali è valida solo se la base ottima rimane la stessa quando il termine noto del primale viene perturbato. Lo studio delle condizioni che garantiscono che la base ottima resti invariata a fronte di perturbazioni del termine noto o di altri parametri del problema è detto analisi della sensitività ed è oggetto di corsi più avanzati.

Alla luce della Proposizione 4.10, le variabili duali possono essere interpretate come prezzi di equilibrio: il valore di ¯yi ci dice quanto saremmo disposti a pagare per incrementare di una unità il termine noto b_i (ammesso che la base ottima resti la stessa): infatti, poiché il valore ottimo aumenterebbe esattamente di ¯y_i, non saremmo certo disposti a pagare più di ¯y_i per incrementare bi.

Con riferimento al problema della Sezione 4.4.1, il valore di ciascuna variabile y_i all’ottimo indica di quanto varierebbe il valore ottimo del primale (cioè il nostro profitto) se disponessimo di una unità in più di risorsa i (a patto che la base ottima resti la stessa). In altre parole, se qualcuno ci proponesse di venderci un’ulteriore unità di risorsa i, dato che il nostro profitto aumenterebbe di ¯y_i, noi saremmo disposti a pagare al massimo ¯y_i per avere questa unità in più.

4.5 Inammissibilit` a e Lemma di Farkas

Il Teorema di Dualità Forte implica che quando un programma lineare ha una soluzione ottima x^∗, il fatto che x^∗sia ottima può essere certificato esibendo una soluzione ammissibile duale y^∗ tale che c^Tx^∗ = b^Ty^∗. Alternativamente, l’ottimalità di x^∗ può essere dimostrata

(11)

4.5. INAMMISSIBILIT À E LEMMA DI FARKAS 43 esibendo una soluzione ammissibile duale y^∗ tale che x^∗ e y^∗ soddisfino le condizioni degli scarti complementari. La soluzione y^∗ può essere dunque vista come un “certificato” che prova l’ottimalità di x^∗.

Analogamente, quando un programma lineare non ammette soluzioni ammissibili, questo fatto pu`o essere provato esibendo un semplice certificato. Il risultato che garantisce l’esistenza di un tale certificato `e noto come Lemma di Farkas.

4.5.1 Forma standard

Teorema 4.11 (Lemma di Farkas) Il sistema lineare

Ax = b (4.16)

x ≥0 (4.17)

non ammette soluzioni se e solo se il seguente sistema ammette una soluzione:

A^Ty ≥0 (4.18)

b^Ty <0. (4.19)

Dimostrazione. Dimostriamo prima la sufficienza. Sia ¯y una soluzione del sistema (4.18)–

(4.19). Supponiamo per assurdo che il sistema (4.16)–(4.17) ammetta una soluzione ¯x. Allora 0 > b^Ty =¯ (¯x^TA^T)¯y = (¯y^TA)¯x ≥ 0,

dove l’ultima disuguaglianza discende dal fatto che ¯x ≥ 0 e A^Ty ≥¯ 0. Pertanto 0 > 0, un assurdo.

Per la necessit`a, vediamo due possibili dimostrazioni.

Prima dimostrazione. Consideriamo il programma lineare

max 0^Tx (4.20)

s.a Ax = b (4.21)

x ≥0. (4.22)

Poiché tale problema è per ipotesi inammissibile, il suo duale è o inammissibile oppure illimitato (si veda la tabella data nella Sezione 4.2.3). Il duale è

min b^Ty s.a A^Ty ≥0.

Poiché y = 0 è chiaramente una soluzione ammissibile, tale problema deve essere illimitato, cioè per ogni α esiste una soluzione ammissibile del duale ¯y tale che b^Ty ≤ α. Questo implica,¯ in particolare, che esiste una soluzione ammissibile del duale ¯y tale che b^Ty ≤ −1. Un tale ¯¯ y soddisfa il sistema (4.18)–(4.19).

Seconda dimostrazione. Se il programma lineare (4.20)–(4.22) è inammissibile, applicando la Fase I del metodo del simplesso scopriremo che il valore ottimo del problema ausiliario è w^∗<0. Si ricordi che il problema ausiliario è il seguente:

max −e^Tx_A s.a Ax + IxA=b

x ≥0, x_A≥0.

(12)

La Fase I del metodo del simplesso termina con una base ottima B^∗per il problema ausiliario.

Pertanto la soluzione ottima y^∗per il duale del problema ausiliario determinata da B^∗soddisfa b^Ty^∗=w^∗<0. Il duale del problema ausiliario `e il seguente:

min b^Ty s.a A^Ty ≥0

Iy ≥ −e,

pertanto A^Ty^∗≥0 e b^Ty^∗<0. Dunque y^∗ soddisfa il sistema (4.18)–(4.19). ◻ Abbiamo visto nella Sezione 4.1.1 che quando un programma lineare ammette ottimo, la base ottima B trovata dal metodo del simplesso permette di costruire immediatamente una soluzione ottima duale ¯y = A^−⊺_B c_B, cioè il certificato di ottimalità. La seconda dimostrazione del teorema precedente evidenzia che per problemi inammissibili la situazione è simile. Infatti, quando un sistema lineare (o un programma lineare) non ammette soluzioni, il certificato di inammissibilità (la cui esistenza è garantita dal Lemma di Farkas) può essere determinato eseguendo la Fase I del metodo del simplesso: il certificato cercato non è altro che la soluzione ottima del duale del problema ausiliario.

4.5.2 Altre forme

Il Lemma di Farkas per problemi in forma canonica `e il seguente.

Teorema 4.12 (Lemma di Farkas) Il sistema lineare

Ax ≤ b (4.23)

x ≥0 (4.24)

non ammette soluzioni se e solo se il seguente sistema ammette una soluzione:

A^Ty ≥0 (4.25)

y ≥0 (4.26)

b^Ty <0. (4.27)

Dimostrazione. Il sistema (4.23)–(4.24) non ha soluzioni se e solo se il sistema Ax + Is = b

x ≥0, s ≥ 0

non ha soluzioni, dove s è un vettore di variabili di scarto. Per il Lemma di Farkas (Teore- ma 4.11), questo avviene se e solo se il sistema (4.25)–(4.27) ha una soluzione. ◻ Una dimostrazione alternativa del risultato precedente può essere ottenuta facendo uso della dualità come nella dimostrazione del Teorema 4.11; si consiglia di scrivere tale dimostrazione come esercizio.

Per sistemi della forma Ax ≤ b, il Lemma di Farkas `e il seguente.

(13)

4.6. PROBLEMI ILLIMITATI 45 Teorema 4.13 (Lemma di Farkas) Il sistema lineare

Ax ≤ b

non ammette soluzioni se e solo il seguente sistema ammette una soluzione:

A^Ty =0 y ≥0 b^Ty <0.

Anche questo teorema pu`o essere dimostrato in almeno due modi: riducendosi alla forma canonica ed applicando il Lemma di Farkas valido per problemi di quel tipo, oppure utilizzando la dualit`a; anche in questo caso si consiglia di scrivere le dimostrazioni come esercizio.

A questo punto dovrebbe essere chiaro come formulare il Lemma di Farkas per sistemi lineari generici della forma (4.6)–(4.11): un sistema di questo tipo non ha soluzioni se e solo se esiste una soluzione ammissibile per un certo sistema, che `e costituito dai vincoli duali (con termini noti tutti nulli) pi`u la condizione b^Ty <0.

Teorema 4.14 (Lemma di Farkas) Il sistema lineare (4.6)–(4.11) non ammette soluzioni se e solo il seguente sistema ammette una soluzione:

A^T_jy ≥0 j =1, . . . , p A^T_jy ≤0 j = p +1, . . . , q A^T_jy =0 j = q +1, . . . , n

y_i ≥0 i =1, . . . , h yi ≤0 i = h +1, . . . , k yi libera i = k +1, . . . , m b^Ty <0.

4.6 Problemi illimitati

Anche quando un programma lineare `e illimitato, questo fatto pu`o essere provato esibendo un semplice certificato.

Teorema 4.15 Il programmazione lineare

max c^Tx (4.28)

s.a Ax = b (4.29)

x ≥0 (4.30)

`e illimitato se e solo `e ammissibile ed esiste r ∈ Rⁿ tale che

c^Tr >0 (4.31)

Ar =0 (4.32)

r ≥0. (4.33)

(14)

r

c

Figura 4.1: Regione ammissibile di un problema illimitato e un raggio r della regione ammissibile. Si noti che c^Tr >0.

Dimostrazione. Per la sufficienza, assumiamo che esista r soddisfacente (4.31)–(4.33) e sia

¯

x una soluzione ammissibile di (4.28)–(4.30). Per l’Esercizio 1 del terzo foglio di esercizi, r è un raggio della regione ammissibile, cioè per ogni t ≥ 0 il vettore x(t) = ¯x + tr è una soluzione ammissibile di (4.28)–(4.30). Inoltre, il valore della funzione obiettivo calcolata in x(t) è z(t) = c^Tx + tc¯ ^Tr. Poiché c^Tr >0, si ha lim_t→+∞z(t) = +∞, pertanto x(t) definisce una famiglia di soluzioni ammissibili di valore arbitrariamente grande. Ne segue che il problema (4.28)–(4.30) è illimitato.

Per la necessit`a, vediamo due possibili dimostrazioni.

Prima dimostrazione. Si applichi il metodo delle due fasi al problema (4.28)–(4.30). Poiché il problema è illimitato, siamo nel Caso 2 della Sezione 3.2. Sia r il vettore definito dalle condizioni (3.20)–(3.22). Come osservato appunto nella Sezione 3.2, r è un raggio della regione ammissibile. Inoltre, c^Tr =c¯k>0. Dunque r soddisfa il sistema (4.31)–(4.33) (si può di nuovo usare l’Esercizio 1 del terzo foglio di esercizi).

Seconda dimostrazione. Se (4.28)–(4.30) è illimitato, allora il suo duale è inammissibile (Corollario 4.3). Il duale è

min b^Ty s.a A^Ty ≥ c

e tale problema `e inammissibile se e solo se il sistema −A^Ty ≤ −cnon ammette soluzioni. Per il Lemma di Farkas (nella forma del Teorema 4.13), −A^Ty ≤ −c non ammette soluzioni se e

solo se esiste r che soddisfa (4.31)–(4.33). ◻

La Figura 4.1 fornisce un’illustrazione del Teorema 4.15.

Il Teorema 4.15 pu`o essere facilmente esteso a problemi di programmazione lineare in forma generica.

(15)

4.7. METODO DEL SIMPLESSO DUALE 47 Teorema 4.16 Il programma lineare

max c^Tx

s.a a^T_ix ≤ bi, i =1, . . . , h a^T_ix ≥ bi, i = h +1, . . . , k a^T_ix = b_i, i = k +1, . . . , m

`e illimitato se e solo `e ammissibile ed esiste r ∈ Rⁿ tale che c^Tr >0

a^T_ir ≤0, i =1, . . . , h a^T_ir ≥0, i = h +1, . . . , k a^T_ir =0, i = k +1, . . . , m.

La dimostrazione di questo risultato `e del tutto analoga a quella del Teorema 4.15.

4.7 Metodo del Simplesso duale

Come visto nel Capitolo 3 e nella Sezione 4.1.1, il metodo del simplesso (Fase II) mantiene ad ogni iterazione una base ammissibile nel primale, che però non è ammissibile nel duale (con l’eccezione dell’ultima iterazione, in cui, se il problema ha soluzione ottima, la soluzione primale e quella duale associate alla base corrente sono entrambe ammissibili per i rispettivi problemi). Ad ogni iterazione viene determinata una nuova base ammissibile nel primale tale che il valore della funzione obiettivo della soluzione associata sia maggiore o uguale al valore della soluzione precedente. Si ricordi anche che il metodo del simplesso può essere avviato solo quando è nota una base ammissibile primale, che può essere determinata tramite la Fase I.

In certe situazioni è immediatamente disponibile una base ammissibile del duale piuttosto che del primale. In tal caso, invece di applicare la Fase I e poi la Fase II, è possibile utilizzare direttamente il metodo del simplesso duale: tale procedura, partendo da una base ammissibile nel duale (ovvero una base per la quale i costi ridotti siano non-positivi), ad ogni iterazione cerca una nuova base ammissibile nel duale la cui soluzione di base associata abbia costo minore o uguale della precedente. L’algoritmo termina quando viene trovata una base che sia ammissibile anche nel primale: per quanto osservato nella Sezione 4.1.1, sappiamo infatti che una tale base è ottima. Al termine della procedura avremo dunque una soluzione ottima per il primale e una per il duale.

Dati una matrice A ∈ R^m×n di rango m e vettori b ∈ R^m, c ∈ Rⁿ, si consideri come al solito il problema

max c^Tx (4.34)

s.a Ax = b (4.35)

x ≥0, (4.36)

il cui duale `e

min b^Ty s.a A^Ty ≥ c.

(16)

Sia B = {B[1],... ,B[m]} una base ammissibile nel duale. Il problema in forma tableau rispetto a tale base `e il seguente:

max z

s.a z −c¯^T_Nx_N =z¯ x_B+ ¯A_Nx_N = ¯b

x ≥0.

Poiché B è ammissibile nel duale, ¯c_j ≤ 0 per ogni j ∈ N (si veda la Sezione 4.1.1). Si ricordi che la soluzione duale associata alla base B è ¯y = A^−⊺_B cBe che il valore di tale soluzione

`e ¯z = c^T_BA⁻_B¹b. La soluzione primale associata alla base B `e invece il vettore ¯xdefinito da

¯

x_B[i]= ¯b_i, i =1, . . . , m

¯ xN =0.

Se ¯bi≥0 per ogni i = 1, . . . , m, allora ¯xè ammissibile e quindi B è una base ammissibile nel primale e dunque ottima. In tal caso ¯xè una soluzione ottima e abbiamo risolto il problema.

Supponiamo dunque che esista h ∈{1,... ,m} tale che ¯b^h<0. Vogliamo far uscire di base la variabile x_B[h] e dobbiamo selezionare la variabile entrante in modo da ottenere una nuova base ammissibile nel duale. Abbiamo due casi.

Caso 1: a¯_hj≥0 per ogni j ∈ N .

Ogni soluzione ammissibile x per il primale soddisfa l’h-esimo vincolo del primale, cio`e x_B[h]+ ∑

j∈N

¯

a_hjx_j = ¯b_h.

Poich´e x ≥ 0 e ¯a_hj ≥ 0 per ogni j ∈ N , avremo x_B[h]+∑^j∈N¯a_hjx_j ≥ 0, e dunque ¯bh ≥ 0, che contraddice la scelta ¯b_h <0. Pertanto, in tal caso, il problema primale non ha soluzioni ammissibili e abbiamo terminato.

Caso 2: Esiste un indice j ∈ N tale che ¯a_hj<0.

Vogliamo determinare un indice k ∈ N tale che la base B^′ = B ∪{k} ∖ {B[h]} rimanga ammissibile nel duale. Questo avviene quando il vettore c^′ dei costi ridotti rispetto a B^′ è non-positivo. Sia N^′={1,... ,n}∖B^′. Come si può verificare osservando i tableau e le formule della Sezione 3.4, facendo un pivot rispetto alla posizione(h,k) del tableau relativo alla base B il vettore c^′ è dato da

c^′_B[h] = − ¯ck

¯ a_hk, c^′_j =¯c_j− ¯c_k

¯

a_hk¯a_hj, j ∈ N ∖{k}.

Poich´e ¯ck ≤0, si ha che c^′_B[h] ≤0 se e solo se ¯ahk <0. Dunque dobbiamo scegliere un indice k ∈ N tale che ¯a_hk <0. Inoltre, affinch´e B^′ sia ammissibile nel duale, deve valere c^′_j ≤0 per ogni j ∈ N ∖{k}.

Se ¯a_hj ≥0, allora la condizione `e verificata poich´e in tal caso c^′_j ≤c¯_j ≤0, dove la prima disuguaglianza discende dal fatto che_¯_a^c^¯^k

hk ¯a_hj≥0, mentre la seconda disuguaglianza vale perch´e B `e ammissibile nel duale.

(17)

4.7. METODO DEL SIMPLESSO DUALE 49 Se ¯a_hj<0, allora c^′_j ≤0 se e solo se

¯ c_k

¯ ahk

≤ c¯_j

¯ ahj

. Dobbiamo dunque scegliere k ∈ N tale che ¯a_hk<0 e

¯ c_k

¯ ahk

=min{ ¯c_j

¯ ahj

∶ j ∈ N,¯a_hj<0} .

Con una tale scelta di k, la base B^′ `e ammissibile nel duale. Inoltre (si veda ancora la Sezione 3.4), il valore della soluzione duale rispetto alla base B^′ `e

¯ z + c¯_k

¯

a_hk¯b_h≤z,¯ perch´e ¯c_k≤0, ¯a_hk<0 e ¯bh<0.

Ricapitolando, abbiamo trovato una base ammissibile nel duale la cui corrispondente soluzione duale ha valore minore o uguale della soluzione precedente. Visto che il problema duale

`e un problema di minimo, abbiamo dunque una soluzione duale migliore (o non peggiore, se

¯

c_k=0) rispetto alla precedente.

Riassumiamo qui sotto il metodo del simplesso duale.

Metodo del Simplesso Duale

Input: A ∈ R^m×n, b ∈ R^m, c ∈ Rⁿ ed una base ammissibile duale B = {B[1],... ,B[m]} per il sistema (4.35)–(4.36).

Output: Una soluzione ottima di base ¯x per il programma lineare (4.34)–

(4.36), oppure l’informazione che il problema `e inammissibile.

1. Si calcoli il tableau rispetto alla base B e la soluzione di base ¯x relativa a B.

2. Se ¯b ≥ 0, allora ¯x`e una soluzione ottima; STOP.

3. Altrimenti, si scelga un indice h ∈{1,... ,m} tale che ¯b^h<0.

4. Se ¯a_hj≥0 per ogni j ∈ N , allora il problema `e inammissibile; STOP.

5. Altrimenti, si scelga k ∈ N tale che

¯

a_hk<0 e ¯c_k

¯

a_hk =min{ c¯j

¯

a_hj ∶ j ∈ N,¯a_hj<0} . 6. Si ridefinisca B[h] ∶= k e si torni al Passo 1.

Si noti che il metodo del simplesso duale non restituirà mai l’informazione che il problema primale è illimitato; infatti, la base iniziale certifica che il problema duale è ammissibile e di conseguenza il primale non può essere illimitato (Corollario 4.3).

(18)

Per il metodo del simplesso duale si pongono le stesse questioni (ciclaggio, terminazione, scelta della base iniziale) che abbiamo evidenziato e risolto per il metodo del simplesso. `E possibile garantire che l’algoritmo termini attraverso la seguente regola di pivot:

Regola di Bland Ad ogni iterazione dell’algoritmo del simplesso duale, in caso vi siano due o pi`u variabili candidate ad entrare in base o ad uscire di base, si scelga quella con indice minimo.

Omettiamo i dettagli sulla correttezza di tale regola e sulla scelta della base iniziale.