COMPITO DI RICERCA OPERATIVA

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

max x 1 + x 2 + x 3

x 1 − x ² + x 3 = −1

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

Lo si risolva con l’algoritmo che si ritiene pi` u opportuno (3 punti). Individuare almeno un’altra soluzione ottima del problema (2 punti). Si stabilisca in quale intervallo posso far variare la modifica ∆b 3 del termine noto del terzo vincolo senza che la base ottima (la prima che `e stata trovata) cambi (2 punti).

ESERCIZIO 2. (6 punti) Sia dato il seguente problema di PL:

max −2x ¹ − x ² + x 3

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

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

Se ne scriva il duale (1 punto). Si risolva il duale graficamente indicando soluzione ottima e valore ottimo del duale (2 punti). Utilizzando le condizioni di complementarit` a si determini una soluzione ottima del problema primale (2 punti). Di quanto deve essere modificato il coefficiente di x 3 nell’obiettivo in modo tale che il duale abbia regione ammissibile vuota? (1 punto)

ESERCIZIO 3. (5 punti) Si consideri il seguente problema di PLI:

max 5x 1

x 1 − 2x ² + x 3 = 1 2x 1 + 6x 2 + x 4 = 7

x 1 , x 2 , x 3 , x 4 ≥ 0 x 1 , x 2 , x 3 , x 4 ∈ I

La riformulazione rispetto alla base ottima B ^∗ = {x ¹ , x 2 } del suo rilassamento lineare `e la seguente max 10 − 3x ³ − x ⁴

x 1 = 2 − ³ 5 x 3 − ¹ 5 x 4

x 2 = ¹ ₂ + ¹ ₅ x 3 − 10 ¹ x 4

x 1 , x 2 , x 3 , x 4 ≥ 0

Si risolva il problema di PLI utilizzando l’algoritmo di taglio basato sui tagli di Gomory restituen- done una soluzione ottima e il valore ottimo.

ESERCIZIO 4. (6 punti) Siano A, B, C, D, E, F sei oggetti che vorreste portare con voi. Esistono per` o delle incompatibilit` a che impediscono di portare contemporaneamente certe coppie di oggetti.

1

Tali incompatibilit` a sono riportate nella seguente tabella insieme ai valori degli oggetti:

incompatibile con valore

A B, D 8

B A, E 7

C F 4

D A, E, F 11

E B, D 9

F C, D 6

Si sa inoltre che:

• se porto l’oggetto C, devo portare al massimo uno tra gli oggetti B e D;

• se non porto l’oggetto A e porto l’oggetto C, allora devo portare l’oggetto B.

Si formuli il modello matematico per il problema di scegliere quali oggetti portare con voi rispet- tando i vincoli dati e massimizzando il valore complessivo degli oggetti scelti.

ESERCIZIO 5. (6 punti) Rispondere a ciascuna delle seguenti domande motivando la risposta:

(1) ` E vero o falso che dato un problema di PLI e un taglio valido per esso, allora ogni soluzione ottima del rilassamento lineare del problema di PLI non soddisfa il taglio valido? (1 punto) (2) ` E vero o falso che dato un problema di PL e il suo duale, se quest’ultimo contiene almeno un punto nella propria regione ammissibile, allora il primale ha sicuramente almeno una soluzione ottima? (1 punto)

(3) ` E vero o falso che dato un problema di PL e una sua base ottima B ^∗ , se la variabile del duale associata a un certo vincolo del primale ha valore 0 nella soluzione ottima del duale, allora il valore ottimo non cambia in corrispondenza di modifiche del termine noto di tale vincolo del primale che non cambino la base ottima attuale? (1 punto)

(4) ` E vero o falso che dato un problema di PL con infinite soluzioni ottime, almeno due di queste sono sempre vertici della regione ammissibile? (1.5 punti)

(5) Se il duale di un problema di PL ha regione ammissibile non vuota e limitata, allora il problema primale ammette certamente soluzioni ottime? (1.5 punti)

ESERCIZIO 6. (3 punti) Dato un problema di PLI e il suo rilassamento lineare, si indichino con Z ^a e S ^a le rispettive regioni ammissibili e si dimostri che:

• se S ^a `e un politopo, allora Z ^a contiene un numero finito di punti;

• se S ^a `e una regione illimitata, allora Z <sup>a</sup> pu` o, a seconda dei casi, contenere un numero finito

oppure un numero infinito di punti.

Soluzioni 1. Impostando il problema di prima fase si ha

max z = −s soggetto a

−x ¹ +x 2 −x ³ +s = 1

−x ¹ −x ² +x 4 = 1

x 2 +x 5 = 2

x 1 , . . . , x 5 , s ≥ 0.

Partendo dalla base {s, x ⁴ , x 5 } si ottiene max z = −1 −x ¹ +x 2 −x ³

s = 1 +x 1 −1x ² +x 3

x 4 = 1 +x 1 +x 2

x 5 = 2 −x ²

x 1 , . . . , x 5 , s ≥ 0

= ⇒

max z = 0 −s

x 2 = 1 +x 1 −s +x ³ x 4 = 2 +2x 1 −s +x ³ x 5 = 1 −x ¹ +s −x ³ x 1 , . . . , x 5 , s ≥ 0

e quindi, trovata la base ammissibile {x ² , x 4 , x 5 }, max z = 1 +2x 1 +2x 3

x 2 = 1 +x 1 +x 3

x 4 = 2 +2x 1 +x 3

x 5 = 1 −1x ¹ −x ³ x 1 , . . . , x 5 , s ≥ 0

= ⇒

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

Avendo γ 3 = 0 `e possibile portare in base x 3 (esce x 1 ) e trovare un ottimo alternativo:

max z = 3 −2x ⁵ x 2 = 2 −x ⁵ x 4 = 3 −x ⁵ +x 1

x 3 = 1 −x ⁵ −x ¹ x 1 , . . . , x 5 ≥ 0.

La matrice di base inversa rispetto alla base B = {x ² , x 4 , x 1 } `e

A ⁻¹ B =





0 0 1 1 1 2 1 0 1





per cui la variazione ∆b 3 del terzo termine noto deve soddisfare le condizioni

∆b 3 ≥ −2 2∆b 3 ≥ −4

∆b 3 ≥ −1

e quindi l’intervallo di stabilit`a `e −1 ≤ ∆b ³ < + ∞.

2. Il problema duale `e min −u ¹ + u 2

soggetto a

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

OPT u 1

u 2

Dalla figura, l’ottimo risulta trovarsi nel punto (u ^∗ 1 = 2, u ^∗ 2 = 0). Dalle condizioni di comple- mentariet`a si ricava

−u ^{∗ 1} − u ^{∗ 2} = −2

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

e quindi la soluzione ottima primale deve soddisfare le condizioni

−x ^{∗ 1} + x ^∗ 2 + x ^∗ 3 = −1

−x ^{∗ 1} − x ^{∗ 2} + x ^∗ 4 = 1 x ^∗ 1 , x ^∗ 4 ≥ 0, x ^{∗ 2} = x ^∗ 3 = 0

= ⇒

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

Se c 3 > 2, si ha D ^a = ∅, quindi c ³ deve aumentare di una quantit` a strettamente maggiore di 1.

3. Dal secondo vincolo si genera il taglio 4

5 x 3 + 1 10 x 4 ≥ 1

2 ⇐⇒ 4

5 x 3 + 1

10 x 4 − y ¹ = 1

2 , y 1 ≥ 0 quindi si ottiene

max z = 10 −3x ³ −x ⁴ x 1 = 2 − ³ 5 x 3 − ¹ 5 x 4

x 2 = ¹ ₂ + ¹ ₅ x 3 − 10 ¹ x 4

y 1 = − ¹ 2 + ⁴ 5 x 3 + 10 ¹ x 4

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

= ⇒

max z = ⁶⁵ ₈ − ¹⁵ 4 y 1 − ⁵ 8 x 4

x 1 = ¹³ ₈ − ³ 4 y 1 − ¹ 8 x 4

x 2 = ⁵ ₈ + ¹ ₄ y 1 − ¹ 8 x 4

x 3 = ⁵ ₈ + ⁵ ₄ y 1 − ¹ 8 x 4

x 1 , . . . , x 4 , y 1 ≥ 0 e, generando dal primo vincolo il taglio

3 4 y 1 + 1

8 x 4 ≥ 5

8 ⇐⇒ 3

4 y 1 + 1

8 x 4 − y ² = 5

8 , y 2 ≥ 0 si ottiene

max z = ⁶⁵ ₈ − ¹⁵ 4 y 1 − ⁵ 8 x 4

x 1 = ¹³ ₈ − ³ 4 y 1 − ¹ 8 x 4

x 2 = ⁵ ₈ + ¹ ₄ y 1 − ¹ 8 x 4

x 3 = ⁵ ₈ + ⁵ ₄ y 1 − ¹ 8 x 4

y 2 = − ⁵ 8 + ³ ₄ y 1 + ¹ ₈ x 4

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

= ⇒

max z = 5 −5y ²

x 1 = 1 −y ²

x 2 = 0 +y ¹ −y ² x 3 = 0 +2y ¹ −y ² x 4 = 5 −6y ¹ +8y ²

x 1 , . . . , x 4 , y 1 , y 2 ≥ 0 che corrisponde a una soluzione ottima intera.

4. Siano A, B, . . . , F ∈ {0, 1} variabili binarie (ognuna ha valore 1 se e solo se si prende il corrispon- dente oggetto). Si pu` o formulare il seguente modello.

max 8A + 7B + 4C + 11D + 9E + 6F soggetto a

A + B ≤ 1 A + D ≤ 1 B + E ≤ 1 C + F ≤ 1 D + E ≤ 1 D + F ≤ 1 B + D + C ≤ 2 A + B ≥ C A, . . . , F ∈ {0, 1}

5. Risposte.

(1) Falso. Il taglio esclude almeno una soluzione ottima del rilassamento lineare ma non necessariamente tutte.

(2) Falso, il duale potrebbe essere illimitato, nel qual caso il primale non ha soluzioni ammis- sibili.

(3) Vero. In tal caso la soluzione ottima duale u ^∗ = c ^B A ⁻¹ _B

non cambia, e la variazione di funzione obiettivo `e ∆z = u ^∗ ∆b = 0, se varia solo la componente di b in corrispondenza della componente nulla di u ^∗ .

(4) Falso. Ci pu` o essere ad esempio il caso di una semiretta ottima, come in max {x ² : x 2 ≤ 2, x ¹ , x 2 ≥ 0} ,

dove solo (0, 2) `e un vertice.

(5) Vero. In questo caso il min {ub: uA ≥ c} esiste finito, e quindi anche l’ottimo primale 6. Per il primo caso, se S a `e un politopo allora `e limitato, e quindi `e contenuto in una sfera centrata

nell’origine e con un certo raggio R > 0. Quindi il numero di soluzioni di Z ^a non `e superiore a (2 ⌈R⌉ + 1) ⁿ , con n = numero di variabili.

Per il secondo caso, si pu` o osservare che

max {−x ¹ − 2x ² : x 1 + x 2 ≥ 4, x ¹ , x 2 ≥ 0, x ¹ , x 2 ∈ I}

ha un numero infinito di soluzioni ammissibili intere (ad es. x 1 = x 2 = k, k = 2, 3, . . . ) mentre max x 2 : x 2 = √

2x 1 , x 1 , x 2 ≥ 0, x ¹ , x 2 ∈ I

ha rilassamento lineare con S a illimitata ma Z a contiene la sola origine.