COMPITO DI RICERCA OPERATIVA

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

max 2x 1 + x 2

2x 1 + x 2 ≥ 1 x 1 + 3x 2 ≤ 6 x 1 , x 2 ≥ 0

Lo si risolva graficamente (2 punti). Lo si trasformi poi in forma standard (1 punto). Si risolva il problema trasformato in forma standard con il metodo due fasi aggiungendo il mior numero possibile di variabili nel problema di I fase (3 punti). Durante la risoluzione del problema di II fase indicare sul grafico i vertici visitati dall’algoritmo del simplesso (1 punto).

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

max x 1 − 3x 2

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

Lo si risolva con il metodo che si ritiene pi` u opportuno (2 punti). Se ne scriva il duale (1 punto).

Si risolva il duale utilizzando le condizioni di complementarit` a (2 punti). In quale intervallo pu` o variare la modifica ∆b 2 del termine noto del secondo vincolo senza che cambi la base ottima? (2 punti)

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

max x 2

−2x 1 + x 2 + x 3 = −2 10x 1 + 2x 2 + x 4 = 31

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 1 , x 2 } del suo rilassamento lineare `e la seguente max 3 − ⁵ ₇ x 3 − ¹ ₇ x 4

x 1 = ⁵ ₂ + ¹ ₇ x 3 − ₁₄ ¹ x 4

x 2 = 3 − ⁵ ₇ x 3 − ¹ ₇ x 4

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

Si risolva il problema di PLI utilizzando l’algoritmo branch-and-bound restituendone una soluzione ottima e il valore ottimo.

ESERCIZIO 4. (5 punti) Sia dato il problema del trasporto con 3 depositi e 4 negozi in cui:

a 1 = 20 a 2 = 20 a 3 = 25 b 1 = 10 b 2 = 15 b 3 = 10 b 4 = 30

1

e i seguenti costi unitari di trasporto tra depositi e negozi:

N 1 N 2 N 3 N 4

D1 5 10 11 1

D2 12 3 10 3

D3 4 0 0 0

Determinare una base ammissibile iniziale utilizzando la regola dell’angolo nord-ovest (1 punto).

Risolvere il problema restituendone una soluzione ottima e il valore ottimo (4 punti).

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

(1) ` E vero o falso che se un problema di PLI ha regione ammissibile vuota, allora anche il suo rilassamento lineare ha regione ammissibile vuota? (1 punto)

(2) Se `e stata individuata una soluzione ammissibile del problema duale, pu` o accadere che il primale abbia obiettivo illimitato? (1 punto)

(3) Pu`o accadere che l’algoritmo del simplesso partendo da un vertice non degenere ne visiti altri e a un certo punto ritorni in quello di partenza? (1.5 punti)

(4) ` E sempre vero che se riduco il coefficiente nell’obiettivo di una variabile al di fuori della base ottima di un problema di PL, questa non cambia? (1 punto)

(5) Se a un problema primale che ammette soluzione ottima viene aggiunto un vincolo, pu` o accadere che tale aggiunta renda illimitato l’obiettivo del duale? (1.5 punti)

ESERCIZIO 6. (3 punti) Dato un problema di PL in forma canonica con S ott 6= ∅, si supponga che un suo vincolo a i x ≤ b i sia fortemente ridondante, ovvero che per ogni ¯ x ∈ S a si abbia

a i x < b ¯ i .

Dopo aver trasformato il problema in forma standard, si dimostri che la variabile del duale associata

al vincolo fortemente ridondante ha sicuramente valore nullo in una soluzione ottima del duale

(SUGGERIMENTO: ci si pu` o arrivare sia attraverso le condizioni di complementarit` a sia attraverso

l’analisi di sensitivit` a).

Soluzioni

1. Disegnando la regione ammissibile nel piano (x 1 , x 2 ) si osserva che l’ottimo `e localizzato nel punto (x ^∗ ₁ = 6, x ^∗ ₂ = 0).

x 1

x 2

OPT

Il problema posto in forma standard `e max 2x 1 + x 2

soggetto a

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

Per impostare il problema di prima fase `e necessaria una sola variabile artificiale, s 1 : max −s 1

soggetto a

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

Partendo dalla base {s 1 , x 4 } si ottiene

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

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

x 4 = 6 −x 1 −3x 2

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

=⇒

max z = 0 −s 1

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

x 4 = ¹¹ ₂ + ¹ ₂ s 1 − ⁵ ₂ x 2 − ¹ ₂ x 3

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

La II fase parte quindi dalla base {x 1 , x 4 }.

max z = 1 +x 3

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

x 4 = ¹¹ ₂ − ⁵ ₂ x 2 − ¹ ₂ x 3

x 1 , . . . , x 4 ≥ 0

=⇒

max z = 12 −5x 2 −2x 4

x 1 = 6 −3x 2 −x 4

x 3 = 11 −5x 2 −2x 4

x 1 , . . . , x 4 ≥ 0

Graficamente i punti visitati durante la II fase sono il vertice (1/2, 0) e il vertice ottimo (6, 0).

2. Il problema `e gi` a in forma standard. Le variabili x 3 , x 4 , x 5 formano gi`a una base ammissibile, per cui si pu` o procedere applicando l’algoritmo del simplesso.

max z = 0 +x 1 −3x 2

x 3 = 1 +x 1 −x 2

x 4 = 1 −1x 1 +x 2

x 5 = 2 −x 1 −x 2

x 1 , . . . , x 4 ≥ 0

=⇒

max z = 1 − x 4 −2x 2

x 3 = 2 − x 4

x 1 = 1 − x 4 +x 2

x 5 = 1 + x 4 −2x 2

x 1 , . . . , x 4 ≥ 0

Il problema duale `e min u 1 + u 2 + 2u 3

soggetto a

−u 1 + u 2 + u 3 ≥ 1 u 1 − u 2 + u 3 ≥ −3 u 1 ≥ 0

u 2 ≥ 0 u 3 ≥ 0.

Dalle condizioni di complementariet`a risulta che per l’ottimo duale u ^∗ 1 , u ^∗ 2 , u ^∗ 3 si deve avere:

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

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

e quindi u ^∗ ₁ = u ^∗ ₃ = 0, u ^∗ ₂ = 1.

La matrice di base inversa per la base ottima B ^∗ = {x 3 , x 1 , x 5 } `e

A ⁻¹ _B

=





1 1 0

0 1 0

0 −1 1





e quindi la variazione ∆b 2 `e limitata dalle condizioni

∆b 2 ≥ −2

∆b 2 ≥ −1

−∆b 2 ≥ −1

=⇒ −1 ≤ ∆b 2 ≤ 1.

3. Effettuando il branch sulla variabile x 1 si ottengono due nodi.

P 1 : x 1 ≤ 2 ⇐⇒ 1 7 x 3 − 1

14 x 4 + y 1 = − 1

2 , y 1 ≥ 0.

P 2 : x 1 ≥ 3 ⇐⇒ 1 7 x 3 − 1

14 x 4 − y 2 = 1

2 , y 2 ≥ 0.

Per il nodo 1 si ottiene

max z = 3 − ⁵ ₇ x 3 − ¹ ₇ x 4

x 1 = ⁵ ₂ + ¹ ₇ x 3 − ₁₄ ¹ x 4

x 2 = 3 − ⁵ ₇ x 3 − ¹ ₇ x 4

y 1 = − ¹ ₂ − ¹ ₇ x 3 + 14 ¹ x 4

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

=⇒

max z = 2 −x 3 −2y 1

x 1 = 2 −y 1

x 2 = 2 −x 3 −2y 1

x 4 = 7 +2x 3 +14y 1

x 1 , . . . , x 4 , y 1 ≥ 0, ottenendo cos`ı una soluzione intera e LB = 2 (nodo chiuso).

Per il nodo 2 risulta

max z = 3 − ⁵ ₇ x 3 − ¹ ₇ x 4

x 1 = ⁵ ₂ + ¹ ₇ x 3 − ₁₄ ¹ x 4

x 2 = 3 − ⁵ ₇ x 3 − ¹ ₇ x 4

y 2 = − ¹ ₂ + ¹ 7 x 3 − ₁₄ ¹ x 4

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

=⇒

max z = ¹ ₂ −5y 2 − ¹ ₂ x 4

x 1 = 3 +y 2

x 2 = ¹ ₂ −5y 2 − ¹ ₂ x 4

x 3 = ⁷ ₂ +7y 2 + ¹ ₂ x 4

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

chiuso perch´e UB(P 2 ) ≤ LB. La soluzione ottima `e quindi x ^∗ ₁ = 2, x ^∗ ₂ = 2, x ^∗ ₃ = 0, x ^∗ ₄ = 7.

4. Il problema `e bilanciato. Il metodo dell’angolo NW fornisce la base iniziale {x 11 , x 12 , x 22 , x 23 , x 24 , x 25 }.

Si procede poi come segue.

x ij

N 1 N 2 N 3 N 4 a i

D1 10 10 ⁻ + 20

D2 5 ⁺ 10 5 ⁻ 20

D3 25 25

10 15 10 30

N 1 N 2 N 3 N 4

D1 0 0 −6 −9

D2 14 0 0 0

D3 9 0 −7 0

¯ c ij

x ij

N 1 N 2 N 3 N 4 a i

D1 10 5 ⁻ 5 ⁺ 20

D2 10 ⁺ 10 ⁻ 20

D3 + 25 ⁻ 25

10 15 10 30

N 1 N 2 N 3 N 4

D1 0 0 −6 0

D2 14 0 0 9

D3 0 −9 −16 0

¯ c ij

x ij

N 1 N 2 N 3 N 4 a i

D1 10 10 20

D2 15 5 ⁻ + 20

D3 5 ⁺ 20 ⁻ 25

10 15 10 30

N 1 N 2 N 3 N 4

D1 0 16 10 0

D2 −2 0 0 −7

D3 0 7 0 0

¯ c ij

x ij

N 1 N 2 N 3 N 4 a i

D1 10 10 20

D2 15 5 20

D3 10 15 25

10 15 10 30

N 1 N 2 N 3 N 4

D1 0 9 10 0

D2 5 0 7 0

D3 0 0 0 0

¯ c ij

5. Risposte.

(1) Falso. Si consideri ad esempio

max {z = x 1 + x 2 : 1 ≤ 4x 1 ≤ 3, 1 ≤ 4x 2 ≤ 3, x 1 , x 2 ∈ I} , che ha Z a = ∅, ma S a 6= ∅.

(2) No, il valore della soluzione duale stabilisce un limite superiore per i valori delle soluzioni primali.

(3) No, il ciclaggio coinvolge necessariamente basi degeneri.

(4) Vero, in tal caso il costo ridotto di tale variabile k, γ k = c k − u ^∗ a k pu` o solo scendere.

(5) S`ı, ad esempio si pu` o verificare che, preso un problema max {z = cx : Ax = b, x ≥ 0}

con ottimo finito z ^∗ , un vincolo che crea la situzione descritta `e cx ≥ z ^∗ + 1.

In generale, l’aggiunta di qualsiasi vincolo che rende vuota la regione ammissibile del primale, rende illimitato l’obiettivo del duale (la regione ammissibile del duale non viene resa vuota perch`e qualsiasi soluzione ammissibile del duale originario pu` o essere estesa a una soluzione ammissibile del nuovo duale fissando a 0 il valore della variabile duale associata al nuovo vincolo).

6. Il problema in forma standard sar`a max {z = cx : Ax + y = b, x ≥ 0}

con variabili di slack y = (y 1 , . . . , y m ). Il problema duale sar`a min {ub : uA ≥ c, u ≥ 0.}

Per ipotesi, all’ottimo primale deve essere a i x ^∗ < b i ⇐⇒ y i > 0. Allora le condizioni di

complementariet`a tra la variabile primale y i e il vincolo duale u i ≥ 0 implicano che si deve avere

u i = 0.