ESERCIZIO 1. (5 punti) Sia dato il seguente problema di PL:

ESERCIZIO 1. (5 punti) Sia dato il seguente problema di PL:

max x 1 + x ² x ¹ + x ² ≤ 2

x 1 ≤ 1

−x ¹ + x ² + x ³ ≤ −3 x 1 , x 2 , x 3 ≥ 0

Lo si trasformi in forma standard e si dimostri, usando il metodo due fasi con l’aggiunta del minor numero possibile di variabili, che esso ha regione ammissibile vuota.

ESERCIZIO 2. (4 punti) Sia dato la seguente riformulazione rispetto alla base B = {x 3 , x 4 , x 5 } di un problema di PL:

max 5 − x 1 + x 2

x 3 = 2 + x ¹ − x 2

x ⁴ = 3 − 2x ² x 5 = 4 + 2x ² x 1 , x 2 , x 3 , x 4 , x 5 ≥ 0

Solamente guardando questa riformulazione, per ciascuna delle seguenti affermazioni dire se `e vera o falsa (MOTIVARE LA RISPOSTA):

(1) la base B ´e ammissibile per il primale ma non per il duale;

(2) la soluzione di base del primale associata a B ´e degenere;

(3) il problema ha regione ammissibile illimitata ma non necessariamente obiettivo illimitato;

(4) se esiste il valore ottimo del primale e del duale, questo `e strettamente maggiore di 5.

ESERCIZIO 3. (5 punti) Il seguente problema di PL max x 1 + 2x ² + x ³

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

x ¹ , x ² , x ³ , x ⁴ ≥ 0 ha soluzione ottima

x ^∗ 1 = 0 x ^∗ 2 = 3 x ^∗ 3 = 1 x ^∗ 4 = 0.

Se ne scriva il duale e, utilizzando le condizioni di complementarit´ a, si ricavi la soluzione ottima del duale.

ESERCIZIO 4. (4 punti) Il seguente problema di PL max x 1 + x ² + 2x ⁴

x 1 − x 2 + x 3 = 1

−x 1 − x 2 + x ⁴ = 2

−x 1 + 2x 2 + x 5 = 3 x 1 , x 2 , x 3 , x 4 , x 5 ≥ 0

ha la seguente riformulazione rispetto alla base ottima B ^∗ = {x ¹ , x 4 , x 2 }:

max 31 − 9x ³ − 6x 5

x ¹ = 5 − 2x ³ − x ⁵ x 4 = 11 − 3x ³ − 2x 5

x 2 = 4 − x ³ − x ⁵ x 1 , x 2 , x 3 , x 4 , x 5 ≥ 0

1

In quale intervallo posso far variare la modifica ∆b 1 del termine noto del primo vincolo senza che cambi la base ottima? E in quale intervallo posso far variare la modifica ∆c 1 del coefficiente di x 1

nell’obiettivo senza che cambi la base ottima?

ESERCIZIO 5. (4 punti) Sia data la seguente riformulazione rispetto alla base ottima B ^∗ = {x 3 , x 4 } del rilassamento lineare di un problema di PLI:

max ¹⁵ 2 − ¹ ₂ x 1 − ³ ₂ x 2

x 3 = ⁵ ₃ − ⁵ ₃ x 1 + ⁴ ₃ x 2

x ⁴ = ⁸ 3 + ¹ 3 x ¹ − ² 3 x ² x 1 , x 2 , x 3 , x 4 ≥ 0 Si risolva il problema di PLI utilizzando l’algoritmo di Gomory.

ESERCIZIO 6. (4 punti) Sia data la rete seguente

1

2

3

4

con i seguenti valori b ⁱ , i = 1, . . . , 4 :

b 1 = 2 b ² = 2 b ³ = −1 b ⁴ = −3 e i seguenti costi unitari di trasporto lungo gli archi:

c 12 = 6 c 13 = 9 c 14 = 3 c 23 = 15 c 24 = 8 c 43 = 8.

Si verifichi che le variabili x 12 , x 13 , x 24 formano una base ammissibile per il problema di flusso a costo minimo su tale rete e si determini quindi a partire da tale base una soluzione ottima e il valore ottimo del problema.

ESERCIZIO 7. (3 punti) Si ricorda che dato un insieme C, questo si dice convesso se:

per ogni x ¹ , x 2 ∈ C, per ogni λ ∈ (0, 1) si ha che λx 1 + (1 − λ)x ² ∈ C.

Applicando tale definizione si dimostri che l’insieme S ^ott delle soluzioni ottime di un problema di PL ´e un insieme convesso.

ESERCIZIO 8. (5 punti) Si consideri un generico problema di PLI indicato con P :

max cx

Ax = b

x ≥ 0 x ∈ I ⁿ

Si supponga di volerlo risolvere con l’algoritmo branch-and-bound. Si richiede di:

(1) dire come viene calcolato una limitazione superiore (upper bound) U (P ⁱ ) per ciascuno dei sottoproblemi P i in cui viene suddiviso il problema originario P ;

(2) definire cosa sia e come si trovi una limitazione inferiore (lower bound) LB per il valore ottimo del problema P ;

(3) descrivere le tre regole per la cancellazione di sottoproblemi.

Soluzioni 1. Il problema, posto in forma standard, `e il seguente.

max x ¹ +x ² soggetto a

x ¹ +x ² +x ⁴ = 2

x 1 +x ⁵ = 1

x 1 −x ² −x ³ −x ⁶ = 3 x 1 , . . . , x 6 ≥ 0.

Formulando il problema di prima fase si ottiene max −s 1

soggetto a

x 1 +x ² +x ⁴ = 2

x 1 +x 5 = 1

x 1 −x 2 −x 3 −x 6 +s 1 = 3 x 1 , . . . , x 6 , s 1 ≥ 0,

e quindi

max z = −3 +x 1 −x 2 −x 3 −x 6

x 4 = 2 −x ¹ −x 2

x ⁵ = 1 −1x ¹

s 1 = 3 −x 1 +x 2 +x 3 +x 6

x 1 , . . . , x 6 , s 1 ≥ 0 max z = −2 −x ⁵ −x ² −x ³ −x ⁶

x ⁴ = 1 +x ⁵ −x ² x 1 = 1 −x ⁵

s ¹ = 2 +x ⁵ +x ² +x ³ +x ⁶ x 1 , . . . , x 6 , s 1 ≥ 0

L’ottimo per la prima fase ha s ^∗ 1 > 0, e quindi il problema originale `e privo di soluzioni ammissibili (S ^a = ∅).

2. (1) Vero. Ammissibilit` a duale implicherebbe γ ¹ , γ ² ≤ 0, mentre invece γ ² > 0.

(2) Falso. Nessuna delle variabili in base ha valore nullo.

(3) Vero. Dalla riformulazione si pu` o osservare che la semiretta x 3 = 2 + x 1

x 4 = 3 x 5 = 4 x 1 = t x ² = 0

t ≥ 0

`e costituita da soluzioni ammissibili.

(4) Vero. La variabile x ² pu` o entrare in base con valore ³ 2 , e quindi z ^∗ ≥ 5 + ³ 2 . 3. Il problema duale risulta

min 4u 1 +2u 2

soggetto a

u ¹ +2u ² ≥ 1 u ¹ +u ² ≥ 2 u 1 −u ² ≥ 1 u 1 −u ² ≥ 0

(con u ¹ , u 2 variabili libere). Utilizzando le condizioni di complementariet` a si deduce:

x ^∗ 2 > 0 =⇒ u ^∗ 1 + u ^∗ 2 = 2

x ^∗ 3 > 0 =⇒ u ^∗ 1 − u ^∗ 2 = 1

e quindi u ^∗ 1 = ³ ₂ , u ^∗ 2 = ¹ ₂ . Si pu` o verificare che z ^∗ = 4u ^∗ 1 + 2u ^∗ 2 = 4 · 3

2 + 2 · 1

2 = 7 = x ^∗ 1 + 2x ^∗ 2 + x ^∗ 3 . 4. Dalla riformulazione si pu` o leggere direttamente

A ⁻¹ B

=





2 0 1 3 1 2 1 0 1



 .

Per valutare l’intervallo nel quale pu` o variare ∆b <sup>1</sup> si impone la condizione di ammissibilit` a, che in questo caso si scrive come





2 0 1 3 1 2 1 0 1









∆b 1

0 0



 ≥





−5

−11

−4



 =⇒

2∆b ¹ ≥ −5 3∆b ¹ ≥ −11

∆b ¹ ≥ −4 e quindi − ⁵ 2 ≤ ∆b ¹ < +∞.

Per valutare l’intervallo nel quale pu` o variare ∆c ¹ si valuta la variazione della funzione obiettivo riformulata:

z = 31 − 9x ³ − 6x ⁵ + ∆c ¹ x ¹

= (31 + 5∆c 1 ) − (9 + 2∆c 1 )x 3 − (6 + ∆c 1 )x 5 . Imponendo le condizioni di ottimalit` a γ ³ ≤ 0, γ ⁵ ≤ 0 si ottiene

−9 − 2∆c ¹ ≤ 0

−6 − ∆c 1 ≤ 0 e quindi − ⁹ ₂ ≤ ∆c 1 < +∞.

5. Lavorando sulla riga di x ³ si ottiene il taglio 2

3 x 1 + 2 3 x 4 ≥ 2

3 , cio`e 2 3 x 1 + 2

3 x 4 − y 1 = 2

3 , y 1 ≥ 0.

Inserendo il nuovo taglio nella riformulazione si ha max z = ¹⁵ 2 − ¹ ₂ x 1 − ³ ₂ x 2

x 3 = ⁵ 3 − ⁵ ₃ x 1 + ⁴ 3 x 2

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

y ¹ = − ² 3 + ² ₃ x ¹ + ² 3 x ² x 1 , . . . , x 4 , y 1 ≥ 0 max z = 7 − ³ 4 y 1 −x 2

x 3 = 0 − ⁵ ₂ y 1 + ⁸ ₃ x 2

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

x 1 = 1 + ³ 2 y 1 −x ² x 1 , . . . , x 4 , y 1 ≥ 0

6. L’insieme di archi {(1, 2), (1, 3), (2, 4)} costituisce un albero spanning del grafo dato. Inoltre, impostando le equazioni di conservazione del flusso ristrette alle variabili in base si ottiene quanto segue.

x 12 + x ¹³ = 2

−x ¹³ = −1 x 24 − x 12 = 2

−x ²⁴ = −3

=⇒

x ¹² = 1 x 13 = 1 x 24 = 3

1

2

3

4 1

1 3

Costi ridotti

¯

c ²³ = 15 − 9 + 6 = 12

¯

c 43 = 8 − 9 + 6 + 8 = 13

¯

c ¹⁴ = 3 − 8 − 6 = −11

La base data `e quindi ammissibile ma non ottima. Facendo entrare in base la variabile x 14 con valore di flusso ∆ = min {1, 3} = 1 si passa alla base {x 13 , x 14 , x 24 }, che risulta ottima.

1

2

3

4 1

1 3

∆

=⇒ 1

2

3

1 4

1 2

Costi ridotti

¯

c 12 = 6 + 8 − 3 = 11

¯

c 23 = 15 − 9 + 3 − 8 = 1

¯

c 43 = 8 − 9 + 3 = 2 Il costo di questa soluzione `e

z ^∗ = 1 · 9 + 1 · 3 + 2 · 8 = 28.

7. Sia S a l’insieme delle soluzioni ammissibili del problema di PL considerato, e z ^∗ = max {cx : x ∈ S a } il valore dell’ottimo. S ott contiene tutte e sole le x ∈ S a aventi cx = z ^∗ . Ora, siano x 1 , x 2 ∈ S ott ; allora per qualunque λ ∈ (0, 1) e x ³ = λx ¹ + (1 − λ)x ² vale

cx 3 = c[λx 1 + (1 − λ)x 2 ] = λcx 1 + (1 − λ)cx 2 = λz ^∗ + (1 − λ)z ^∗ = z ^∗ ; quindi x ³ ∈ S ott .

8. Vedere gli appunti.