simplesso (nella sua seconda fase).
Il vettore ¯y, invece, `e ammissibile per il duale se e solo se ATy ≥ c, cio`e se e solo se¯
ATBy ≥ c¯ B (4.3)
ATNy ≥ c¯ N. (4.4)
Poich´e ATBy = A¯ TBA−⊺B cB=cB, la condizione (4.3) `e sempre verificata. Dunque ¯y`e ammissibile se e solo se ATNA−⊺BcB ≥cN, cio`e se e solo se
cN− ATNA−⊺BcB≤0.
Si noti che il primo membro di quest’ultima disequazione `e precisamente il vettore ¯cN definito in (3.7), cio`e il vettore dei costi ridotti delle variabili non in base relativo alla base B. Pertanto possiamo affermare che ¯y `e ammissibile se e solo se
¯ cN ≤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−⊺BcB `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−1Bb ≥0, cio`e se ¯x `e una soluzione ammissibile per il problema primale (Ps). B `e detta una base ammissibile nel duale se ¯cN = cN − ATNA−⊺BcB ≤ 0, cio`e se ¯y `e ammissibile per il problema duale (Ds). Quanto visto sopra mostra che se B `e 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 `e detta una base ottima se `e 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 cTx s.a Ax ≤ b
x ≥0.
(Pc)
(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 ∈ Rm tale che y ≥ 0, ogni vettore x che sia soluzione ammissibile del problema (Pc) soddisfa la disequazione
yT(Ax) ≤ yTb.
(Si noti come qui sia fondamentale richiedere la non-negativit`a di y, a differenza del caso della forma standard, dove questa condizione non era necessaria.) Inoltre, se vale ATy ≥ c, allora, poich´e x `e non-negativo, vale la disuguaglianza cTx ≤(yTA)x. Dunque otteniamo
cTx ≤(yTA)x = yT(Ax) ≤ yTb = bTy.
Ricapitolando, dato un vettore y ∈ Rm che soddisfi ATy ≥ c e y ≥ 0, si ha cTx ≤ bTy per ogni x ammissibile per (Pc). Ne segue che z∗ ≤bTy. Il miglior upper-bound che `e possibile trovare in questo modo `e dato dal valore ottimo d∗ del problema
d∗ = min bTy s.a ATy ≥ c
y ≥0,
(Dc)
che `e detto il problema duale di (Pc).
Metodo 2 Scriviamo il problema (Pc) in forma standard aggiungendo variabili di scarto s =(s1, . . . , sm)T ai vincoli del sistema Ax ≤ b:
max cTx+ 0Ts 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’ul-timo programma lineare `e precisamente (Dc). Possiamo dunque concludere che il Teorema di Dualit`a Debole (con i relativi corollari) ed il Teorema di Dualit`a Forte valgono anche per problemi in forma canonica.
4.2.2 Altre forme
Consideriamo ora un programma lineare in forma generica:
z∗ = max cTx
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 Rn(la stessa idea era stata usata nella dimostrazione della Proposizione 1.2). Otteniamo dunque
max cTx′− cTx′′
s.a Ax′− Ax′′≤b x′, x′′≥0,
4.2. DUALIT `A PER PROBLEMI IN ALTRE FORME 37 il cui duale sappiamo essere
min bTy s.a ATy ≥ c
−ATy ≥−c y ≥0, che `e equivalente a
min bTy s.a ATy = 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 (Pg) ha una soluzione ottima x∗, allora il suo duale (Dg) ha una soluzione ottima y∗; inoltre, vale la relazione cTx∗=bTy∗.
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 (Ds) (partiamo dalla forma standard, ma potremmo partire da una qualunque delle altre forme viste). Se scriviamo (Ds) nella forma equivalente
− max −bTy s.a −ATy ≤−c,
sappiamo dalla Sezione 4.2.2 che il duale di quest’ultimo programma lineare `e il seguente:
− min −cTx 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 cTx∗=bTy∗.
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 aT1, . . . , aTm e colonne A1, . . . , An, siano b ∈ Rm e c ∈ Rn e si consideri il seguente generico problema di programmazione lineare:
max cTx (4.5)
s.a aTix ≤ bi, i =1, . . . , h (4.6) aTix ≥ bi, i = h+ 1, . . . , k (4.7) aTix = bi, i = k+ 1, . . . , m (4.8)
xj ≥0, j =1, . . . , p (4.9)
xj ≤0, j = p+ 1, . . . , q (4.10) xj 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 cTx min bTy
aTix ≤ bi yi≥0 i =1, . . . , h aTix ≥ bi yi≤0 i = h+ 1, . . . , k aTix = bi yi libera i = k+ 1, . . . , m
xj ≥0 ATjy ≥ cj j =1, . . . , p xj ≤0 ATjy ≤ cj j = p+ 1, . . . , q xj libera ATjy = cj j = q+ 1, . . . , n