6.14 Esercizio. Si risolva il seguente problema (sfruttando il problema duale) max

(1)

6.14 Esercizio. Si risolva il seguente problema (sfruttando il problema duale) max

n j=1

c

_j

x

_j

i j=1

x

j

≤ b

i

i := 1, . . . , n

x

j

≥ 0 j := 1, . . . , n

nell’ipotesi 0 ≤ b

1

≤ b

2

≤ . . . ≤ b

n

e 0 ≤ c

n

≤ c

n−1

≤ . . . ≤ c

1

. Si risolva nuovamente rimuovendo l’ipotesi.

Soluzione. Nell’ipotesi 0 ≤ b

1

≤ b

2

≤ . . . ≤ b

n

e 0 ≤ c

n

≤ c

n−1

≤ . . . ≤ c

1

il problema si pu` o risolvere agevolmente con un ragionamento diretto. Dato l’ordine dei coeﬃcienti della funzione obiettivo ` e pi` u conveniente assegnare il massimo valore possibile a x

1

. Dato l’ordine dei coeﬃcienti b

_i

tale valore `e b

₁

. Ora si procede ricorsivamente assegnando x

_i

:= b

_i

− b

i−1

per i := 2, . . . , n. L’ottimalit` a di questa soluzione pu` o essere provata costruendo il duale

min

n i=1

b

i

u

i

n i=j

u

i

≥ c

j

j := 1, . . . , n

u

i

≥ 0 i := 1, . . . , n

e notando che la soluzione u

i

:= c

i

− c

i+1

, per i := 1, . . . , n e ponendo per convenzione c

n+1

:= 0, `e ammissibile nel duale e che i valori dei due obiettivi sono uguali (si ponga per convenzione b

0

:= 0).

n i=1

c

_i

x

_i

=

n i=1

c

_i

(b

_i

− b

i−1

) =

n i=1

c

_i

b

_i

−

n+1

i=2

c

_i

b

_i−1

=

n i=1

c

i

b

i

−

n i=1

c

i+1

b

i

=

n i=1

(c

i

− c

i+1

) b

i

=

n i=1

u

i

b

i

Se si rimuove l’ipotesi sull’ordinamento dei coeﬃcienti, si pu` o notare come la relazione b

i+1

< b

i

implichi la ridondanza del vincolo i-mo. Infatti

i j=1

x

_j

≤

i+1 j=1

x

_j

≤ b

i+1

< b

_i

Quindi si pu` o eliminare tale vincolo e la variabile duale corrispondente. Analogamente nel problema duale la relazione c

j

< c

j+1

implica la ridondanza del vincolo j-mo del duale.

Infatti

n i=j

u

i

≥

n i=j+1

u

i

≥ c

j+1

> c

j

e quindi si pu` o eliminare tale vincolo insieme alla corrispondente variabile primale. L’eliminazione della variabile i-ma nel duale comporta la presenza di due vincoli uno dei quali diventa ridondante. Infatti, una volta posto ad esempio u

i

:= 0 si ha

n i=j+1

u

_i

≥ c

j

;

n i=j+1

u

_i

≥ c

j+1

1

(2)

Eliminato il vincolo duale corrispondente al minore dei due valori c

_j

e c

_j+1

si elimina la corrispondente variabile primale. Si procede allora ricorsivamente eliminando a turno nel problema duale e in quello duale variabili e vincoli ﬁno a creare un ciclo di variabili eliminate.

Esempio:

max 3 x

₁

+ 2 x

₂

+ 5 x

₃

+ 3 x

₄

x

1

≤ 3

x

₁

+ x

₂

≤ 4

x

₁

+ x

₂

+ x

₃

≤ 5 x

1

+ x

2

+ x

3

+ x

4

≤ 4 x

_i

≥ 0

min 3 u

₁

+ 4 u

₂

+ 5 u

₃

+ 4 u

₄

u

1

+ u

2

+ u

3

+ u

4

≥ 3

u

₂

+ u

₃

+ u

₄

≥ 2 u

3

+ u

4

≥ 5 u

₄

≥ 3 u

_i

≥ 0

Scandendo i coeﬃcienti b

i

si vede che il terzo vincolo primale `e ridondante. Allora u

3

:= 0.

Con questo assegnamento il quarto vincolo duale diventa ridondante e quindi x

₄

:= 0.

Questo assegnamento non provoca un ulteriore eliminazione perch´ e il terzo vincolo `e gi` a stato eliminato. Il problema `e quindi diventato

max 3 x

₁

+ 2 x

₂

+ 5 x

₃

x

1

≤ 3

x

₁

+ x

₂

≤ 4 x

1

+ x

2

+ x

3

≤ 4 x

_i

≥ 0

min 3 u

1

+ 4 u

2

+ 4 u

4

u

1

+ u

2

+ u

4

≥ 3 u

₂

+ u

₄

≥ 2 u

4

≥ 5 u

_i

≥ 0

Notiamo ora che il primo e secondo vincolo duale sono ridondanti, quindi x

₁

:= 0 e x

₂

:= 0.

Con questo assegnamento diventano ridondanti il primo e il secondo vincolo primale, da cui u

₁

:= 0 e u

₂

:= 0. la soluzione `e allora x

₃

:= 4 e ui

₄

:= 5.

Il problema pu` o allora essere risolto con una scansione dei coeﬃcienti ed eliminazione di vincoli e variabili nei due problemi. Alla ﬁne di questa operazione il nuovo problema rispetta l’ipotesi.

Basandosi su questa struttura `e facile ricavare un metodo diretto che con complessit` a O(n) trova la soluzione:

begin ˆ c := c

n

for j := n − 1 to 1 do if c

j

< ˆ c

then x

_j

:= 0 else ˆ c := c

_j

ˆb := b

n

for j := n − 1 to 1 do if b

_j

> ˆ c

then b

_j

:= ˆb else ˆb := b

j

for j := 1 to n do if x

_j

= 0

then x

_j

:= b

_j

−

i<j

x

_i

end

2