Dato il seguente problema di PLI:

APPELLO DEL 16/09/04

Esercizio 1

Dato il seguente problema di PLI:

max x 1 + 10x 2 − x 3

x 1 + 2x 2 + x 3 = 5

−x 1 + 4x 2 + x 4 = 4

x 1 , x 2 , x 3 , x 4 ≥ 0 x 1 , x 2 , x 3 , x 4 ∈ I 1) lo si risolva usando l’algoritmo Branch-and-Bound (10 punti)

2) Siete in grado di stabilire se tale problema ha soluzione ottima unica oppure no?

(1 punto)

Si consideri il rilassamento lineare del problema di PLI dato. Si determini: 3) l’inversa della matrice di base ottima di tale problema (2 punti)

4) il duale del problema (2 punti)

5) una soluzione ottima del duale utilizzando le condizioni di complementarit´ a (4 punti)

6) in quale intervallo posso far variare il coefficiente di x 3 nell’obiettivo senza che cambi la base ottima (2 punti)

7) in quale intervallo posso far variare il coefficiente di x 1 nell’obiettivo senza che cambi la base ottima (2 punti)

Esercizio 2

Sia dato un grafo non orientato completo con i seguenti pesi sugli archi:

a b c d e

a b c d e

− 11 15 12 21

− 14 16 5

− 3 16

− 7

−

Si calcoli un albero di supporto a costo minimo per tale grafo utilizzando il secondo algoritmo visto a lezione (4 punti)

Esercizio 3

(1) Sia dato un problema di PLI il cui rilassamento lineare ammette pi´ u soluzioni ottime. Per ciascuna delle seguenti affermazioni dire se ´e vera o falsa (MO- TIVANDO LE RISPOSTE)

a): un taglio valido per il problema di PLI non ´e soddisfatto da esatta- mente una delle soluzioni ottime del rilassamento lineare;

b): un taglio valido per il problema di PLI non ´e soddisfatto da tutte le soluzioni ottime del rilassamento lineare;

c): un taglio valido per il problema di PLI non ´e soddisfatto da un numero infinito di soluzioni ottime del rilassamento lineare.

1

(3 punti)

(2) Sia dato un problema di PL in forma standard che ammette soluzione ot-

tima e il cui duale ha tutte le variabili non negative. Si dimostri che in tal

caso ogni incremento del termine noto di un vincolo che lasci invariata la

base ottima non pu´ o diminuire il valore ottimo del problema (3 punti)

Soluzioni

1. (1) Il problema `e gi` a in forma standard. Partendo dalla base ammissibile B 0 = {x 3 , x 4 } e riformulando rispetto a questa, si ottiene la formulazione iniziale dalla quale si prosegue.

max z = −5 +2x 1 +12x 2

x 3 = 5 −x 1 −2x 2

x 4 = 4 +x 1 −4x 2

x 1 , . . . , x 4 ≥ 0.

B 0 = {x 3 , x 4 } ,

max z = 7 +5x 1 −3x 4

x 3 = 3 − ³ 2 x 1 + ¹ ₂ x 4

x 2 = 1 + ¹ ₄ x 1 − ¹ ₄ x 4

x 1 , . . . , x 4 ≥ 0,

B 1 = {x 3 , x 2 } ,

max z = 17 − ¹⁰ ₃ x 3 − ⁴ ₃ x 4

x 1 = 2 − ² ₃ x 3 + ¹ ₃ x 4

x 2 = ³ ₂ − ¹ ₆ x 3 − ¹ ₆ x 4

x 1 , . . . , x 4 ≥ 0,

B 2 = {x 1 , x 2 } .

La base B 2 risolve all’ottimo il rilassamento lineare del nodo radice. La variabile x 2 ha un valore non intero, quindi occorre effettuare un branch su x 2 . Si generano i seguenti nodi

Nodo 1:x 2 ≤ 1 =⇒ y 1 = − 1 2 + 1

6 x 3 + 1 6 x 4

Nodo 2:x 2 ≥ 2 =⇒ y 2 = − 1 2 − 1

6 x 3 − 1 6 x 4

Si pu` o osservare immediatamente che il nodo 2 risulta privo di soluzioni ammissibili;

valutando il nodo 1 si ottiene quanto segue.

max z = 17 − ¹⁰ ₃ x 3 − ⁴ ₃ x 4

x 1 = 2 − ² ₃ x 3 + ¹ ₃ x 4

x 2 = ³ ₂ − ¹ ₆ x 3 − ¹ ₆ x 4

y 1 = − ¹ ₂ + ¹ ₆ x 3 + ¹ ₆ x 4

x 1 , . . . , x 4 , y 1 ≥ 0

B 3 = {x 1 , x 2 , y 1 } ,

max z = 13 −2x 3 −8y 1

x 1 = 3 −x 3 +2y 1

x 2 = 1 −y 1

x 4 = 3 −x 3 +6y 1

x 1 , . . . , x 4 , y 1 ≥ 0,

B 4 = {x 1 , x 2 , x 4 } .

La riformulazione rispetto a B 4 d` a la soluzione intera (1) x 1 = 3, x 2 = 1, x 4 = 3, x 3 = 0.

Il nodo 1 viene chiuso per ottimalit` a, non ci sono altri nodi aperti e quindi la (1) `e la soluzione ottima intera.

(2) Tutti i costi ridotti fuori base sono strettamente negativi, quindi la soluzione ottima `e unica.

(3) Per ispezione della riformulazione finale (base B 2 ) risulta, leggendo la A ⁻¹ _B cambiata di segno nelle colonne di x 3 , x 4 :

A ⁻¹ _B

2

=

2 3 − ¹ ₃

1 6

1 6

mentre A B

= 1 2

−1 4 , e quindi A ⁻¹ _B

2

· A B

= I, come previsto.

(4) Il duale del rilassamento lineare `e il seguente.

min 5u 1 +4u 2

soggetto a

u 1 −u 2 ≥ 1 2u 1 +4u 2 ≥ 10

u 1 ≥ −1

u 2 ≥ 0

(5) All’ottimo, avendo x 1 , x 2 > 0, i primi due vincoli duali devono valere come uguaglianze, quindi

u ^∗ ₁ − u ^∗ ₂ = 1

2u ^∗ ₁ + 5u ^∗ ₂ = 10 =⇒

u ^∗ ₁ = 7 3 , u ^∗ ₂ = 4

3 . Si pu` o verificare che risulta

z ^∗ = 5u ^∗ ₁ + 4u ^∗ ₂ = 5 · 7 3 + 4 · 4

3 = 17, in accordo con il primale.

(6) In base al costo ridotto γ 3 = − ¹⁰ ₃ la variazione ∆ 3 `e limitata da

−∞ < ∆c 3 ≤ 10 3 .

(7) Incorporando la variazione di costo ∆ 1 x 1 nella funzione obiettivo riformulata si ottiene

z = (17 + 2∆ 1 ) −  10 3 + 2

3 ∆ 1



x 3 +  1 3 ∆ 1 − 4

3

 , da cui, imponendo la non positivit` a dei costi ridotti:

− 2

3 ∆ 1 − 10 3 ≤ 0 1

3 ∆ 1 − 4 3 ≤ 0

=⇒ −5 ≤ ∆ 1 ≤ 4.

2. In base ai costi dati l’algoritmo seleziona in sequenza, se il nodo di partenza `e a, gli archi

(a, b), (b, e), (e, d), (c, d);

l’albero ricoprente di costo minimo ha quindi costo pari a 26.

3. Sia

max

n

X

j=1

c j x j

soggetto a

n

X

j=1

a ij x j ≤ b i i = 1, . . . , m x 1 , . . . , x n ∈ I,

e sia

n

X

j=1

α j x j ≤ β

un qualunque taglio valido.

La (1) `e falsa. Per assurdo: siano x ^∗ e ¯ x soluzioni ottime distinte del rilassamento lineare; allora qualunque altra soluzione data da

˜

x = (1 − γ)x ^∗ + γ ¯ x, γ ∈ [0, 1]

`e ottima ed ammissibile. Si supponga per assurdo che il taglio sia incompatibile solo con x ^∗ ; allora deve essere

n

X

j=1

α j x ^∗ _j = β + δ (δ > 0),

n

X

j=1

α j x ¯ j ≤ β

e anche

(1 − γ)

n

X

j=1

α j x ^∗ _j + γ

n

X

j=1

α j x ¯ j ≤ β per ogni γ ∈ (0, 1].

L’ultima disuguaglianza implica per ogni γ ∈ (0, 1], tenendo conto delle due prece- denti:

(1 − γ)(b + δ) + γ

n

X

j=1

α j x ¯ j ≤ b =⇒ δ + γ





n

X

j=1

α j x ¯ j − β − δ



 ≤ 0

Il termine in parentesi quadre `e strettamente negativo, e quindi la disuguaglianza

`e falsa per tutti i γ tali che

0 ≤ γ < δ

| P n

j=1 α j ¯ x j − β − δ| 6= 0;

si `e quindi ottenuta una contraddizione.

La (2) `e falsa. Il PLI

max x 1 + x 2

2x 1 + 2x 2 ≤ 3 x 1 , x 2 ∈ I

ha soluzioni ottime del rilassamento in A(x 1 = 0, x 2 = ³ ₂ ), in B(x 1 = ³ ₂ , x 2 = 0) e sull’intero spigolo AB; il taglio x 1 ≤ 1 `e valido per il PLI, ma non `e incompatibile con l’intero spigolo.

La (3) `e vera, per argomenti analoghi a quelli usati per la (1).

(2) La variazione di funzione obiettivo conseguente ad un incremento ∆ > 0 dei termini noti `e data da

∆z = c B A ⁻¹ _B ∆ = u ^∗ ∆

e quindi ∆z ≥ 0, se u ^∗ ≥ 0 e ∆ ≥ 0.