Compito di Ricerca Operativa I del 17/01/2005 Esercizio 1 (5 punti). Sia dato il seguente problema di PL: max 5x

Compito di Ricerca Operativa I del 17/01/2005 Esercizio 1 (5 punti). Sia dato il seguente problema di PL:

max 5x

1

+ 2x

2

+ 3x

3

x

1

− 2x

2

+ x

4

= 2

−2x

1

+ x

2

+ x

3

= 3 x

2

+ 2x

3

= 7 x

1

, x

2

, x

3

, x

4

≥ 0

Si imposti il problema di I fase associato a questo problema di PL e si esegua una singola iterazione dell’algoritmo di risoluzione del problema di I fase.

Esercizio 2 (3 punti). Sia data la seguente riformulazione di un problema di PL rispetto alla base B = {x

1

, x

4

, x

5

}:

max 5 − 2x

2

− 3x

3

+ 4x

6

x

1

= −1 + x

2

+ x

3

− 2x

6

x

4

= 5 + 2x

2

− 4x

3

+ x

6

x

5

= −3 + 6x

2

− 2x

3

+ 3x

6

x

1

, x

2

, x

3

, x

4

, x

5

, x

6

≥ 0

Solamente analizzando la riformulazione data, quale di queste affermazioni risulta essere vera:

(1) la regione ammissibile del problema di PL ´e vuota;

(2) la regione ammissibile del problema di PL ´e un politopo (poliedro limitato);

(3) la regione ammissibile del problema di PL ´e un poliedro illimitato.

Esercizio 3 (5 punti). Sia dato il seguente problema di PL:

max 5x

1

+ 2x

2

+ 3x

3

+ x

4

x

1

+ x

3

+ x

4

= 5 x

1

+ x

2

+ 2x

3

= 6

x

1

, x

2

, x

3

, x

4

≥ 0

Se ne ricavi il duale. La soluzione ottima del duale risulta essere u

^∗1

= 3, u

^∗2

= 2. Utilizzando le condizioni di complementarit´ a, determinare la soluzione ottima del primale.

Esercizio 4 (5 punti). Sia dato il seguente problema di PL:

max x

1

− 12x

2

x

1

+ x

2

− 3x

3

+ x

4

= 2

−x

1

− 5x

2

+ 4x

3

+ x

5

= 2

−5x

1

− 22x

2

+ 18x

3

+ x

6

= 7 x

1

, x

2

, x

3

, x

4

, x

5

, x

6

≥ 0

Risolvendo tale problema si arriva alla seguente riformulazione rispetto alla base ottima B

^∗

= {x

1

, x

3

, x

6

}:

max 14 − x

2

− 4x

4

− 3x

5

x

1

= 14 + 11x

2

− 4x

4

− 3x

5

x

3

= 4 + 4x

2

− x

4

− x

5

x

6

= 5 + 5x

2

− 2x

4

+ 3x

5

x

1

, x

2

, x

3

, x

4

, x

5

, x

6

≥ 0

In quale intervallo posso far variare la modifica ∆c

2

del coefficiente nell’obiettivo della variabile x

2

senza perdere l’ottimalit´a della base B

^∗

? E in quale intervallo posso far variare la modifica ∆c

1

del coefficiente nell’obiettivo della variabile x

1

senza perdere l’ottimalit´a della base B

^∗

? In entrambi i casi dire come cambia il valore ottimo del problema nell’intervallo in cui B

^∗

rimane base ottima.

1

2

Esercizio 5 (4 punti). Nella modellizzazione di un problema di PL avete individuato tre variabili x

A

, x

B

, x

C

che indicano il numero di ore in cui decidete di utilizzare tre diversi computer A, B e C. ´ E noto che il numero di processi che ciascuno di questi computer ´e in grado di elaborare in un’ora ´e pari a 5 per A, 7 per B e 8 per C (si suppone che tutti i processi abbiano gli stessi tempi di esecuzione se eseguiti su una stessa macchina). Avete bisogno di elaborare almeno 80 processi.

Come esprimereste tale vincolo con le variabili ed i dati a disposizione? Motivare la risposta.

Esercizio 6 (4 punti). Voglio risolvere un problema di PLI con l’algoritmo di taglio di Gomory.

Risolvendo il rilassamento lineare del problema di PLI, arrivo alla seguente riformulazione rispetto alla base ottima: B

^∗

= {x

1

, x

2

}:

max 4 − 4x

3

− 2x

4

x

1

=

⁷₄

+

¹₄

x

3

−

¹₂

x

4

x

2

= 2 − x

3

+ x

4

x

1

, x

2

, x

3

, x

4

≥ 0

Introducete un taglio di Gomory e risolvete il solo rilassamento lineare del problema ottenuto con l’aggiunta di tale taglio (NB: non si richiede di arrivare alla soluzione del problema di PLI).

Esercizio 7 (4 punti). Durante la risoluzione di un problema di PLI con l’algoritmo Branch- and-Bound ad una data iterazione si ha il lower bound LB = 4 e si ´e deciso di suddividere il sottoproblema P

k

, con upper bound U (P

k

) =

¹⁵₂

, in due sottoproblemi P

k+1

e P

k+2

. La situazione

´e riassunta nella seguente figura:

LB = 4, U(P

k

) = 15

2 .

Per ciascuna di tali affermazioni dire se ´e vera o falsa, moptivando la risposta:

a): Almeno uno dei due sottoproblemi P

k+1

e P

k+2

pu´ o avere soluzione ottima del suo rilassamento lineare a coordinate tutte intere e con valore ottimo pari a 8.

b): Almeno uno dei due sottoproblemi P

k+1

e P

k+2

pu´ o avere il duale del suo rilassamento lineare con obiettivo illimitato.

c): Se almeno uno dei due sottoproblemi P

k+1

e P

k+2

ha soluzione ottima del suo rilassamento lineare a coordinate tutte intere, allora aggiorner´ o certamente il valore del lower bound LB.

Esercizio 8 (4 punti). Sia dato un grafo non orientato con i seguenti pesi sugli archi:

a b c d e f

a ∞ 6 2 3 ∞ 7

b − ∞ ∞ 12 11 5

c − − ∞ 4 9 8

d − − − ∞ 8 ∞

e − − − − ∞ 10

f − − − − − ∞

Utilizzando il secondo algoritmo visto a lezione, si determini un albero di supporto a peso minimo

per tale grafo.

3

1. Soluzioni 1. Il problema di prima fase si scrive come

max −s

1

−s

2

soggetto a x

1

−2x

2

+x

4

= 2

−2x

1

+x

2

+x

3

+s

1

= 3

x

2

+2x

3

+s

2

= 7

x

1

, . . . , x

4

, s

1

≥ 0.

La base iniziale B

0

= {x

4

, s

1

, s

2

} `e immediatamente disponibile, e da questa si ottiene max z = −10 −2x

1

+2x

2

+3x

3

x

4

= 2 −x

1

+2x

2

s

1

= 3 +2x

1

−x

2

−1x

3

s

2

= 7 −x

2

−2x

3

x

1

, . . . , x

4

, s

1

, s

2

≥ 0. B

1

= B

0

− {s

1

} ∪ {x

3

} max z = −4 +4x

1

−x

2

−3s

1

x

4

= 2 −x

1

+2x

2

x

3

= 3 +2x

1

−x

2

−s

1

s

2

= 1 −4x

1

+x

2

+2s

1

x

1

, . . . , x

4

, s

1

, s

2

≥ 0.

2. Osservando che nella riformulazione data tutti i coefficienti di x

2

sono non negativi, si pu` o identificare la semiretta

x

1

= −1 +x

2

x

4

= 5 +2x

2

x

5

= −3 +6x

2

x

2

= t

t ≥ 0, x

3

= x

4

= 0.

I punti di questa semiretta sono ammissibili per ogni valore di t ≥ 1, quindi la regione ammissibile del programma in esame `e un poliedro illimitato. L’unica affermazione vera `e quindi la 3.

3. Il duale del problema dato `e max 5u

1

+6u

2

u

1

+u

2

≥ 5 u

2

≥ 2 u

1

+2u

2

≥ 3

u

1

≥ 1

La soluzione duale data u

^∗1

= 3, u

^∗2

= 2 soddisfa i vincoli duali come segue u

^∗1

+u

^∗2

= 5

u

^∗2

= 2 u

^∗1

+2u

^∗2

> 3 u

^∗1

> 1

In base alle conizioni di complementariet`a (u

^∗

A −c)x

^∗

= 0, le due disuguaglianze strette implicano, all’ottimo primale, x

^∗3

= x

^∗4

= 0. Quindi l’ottimo primale deve soddisfare

x

^∗3

= x

^∗4

= 0, x

^∗₁

= 5 x

^∗₁

+ x

^∗2

= 5

=⇒ x

^∗1

= 5, x

^∗2

= 1, x

^∗3

= x

^∗4

= 0.

Si noti che risulta z

^∗

= 5u

^∗1

+ 6u

^∗2

= 5x

^∗1

+ 2x

^∗2

= 27, come previsto dalla teoria.

4. La variabile x

2

`e, all’ottimo, fuori base con costo ridotto γ

2

= −1. La sua variazione pu` o quindi essere

−∞ < ∆c

2

≤ 1.

All’interno di tale intervallo, la variazione non comporta cambiamenti nel valore dell’ottimo z

^∗

, in

quanto l’ottimalit`a di B

^∗

viene preservata e quindi x

2

= 0.

4

Ogni variazione di x

1

perturba invece la funzione obiettivo riformulata come z = (14 + 14∆c

1

) + (11∆c

1

− 1)x

2

+ (−4 − 4∆c

1

)x

4

+ (−3 − 3∆c

1

)x

5

.

Imponendo le condizioni di ottimalit`a (tutti i costi ridotti devono rimanere non positivi) si ottiene 11∆c

1

− 1 ≤ 0

−4 − 4∆c

1

≤ 0

−3 − 3∆c

1

≤ 0

=⇒ −1 ≤ ∆c

1

≤ 1 11 .

Per ogni valore di ∆c

1

in questo intervallo, la base B

^∗

rimane ottima; la variazione nel valore della funzione obiettivo `e data da

∆z

^∗

= 14∆c

1

,

come risulta dalla funzione obiettivo riformulata.

5. Il numero di processi che ogni macchina pu` o eseguire in un’ora `e 5, 7, 8 per A, B, C rispettiva- mente, quindi si pu` o imporre

5x

A

+ 7x

B

+ 8x

C

≥ 80.

6. Il taglio di Gomory associato alla riga di x

1

`e

− 3 4 + 3

4 x

3

+ 1

2 x

4

≥ 0 =⇒ 3 4 x

3

+ 1

2 x

4

− y

1

= 3

4 y

1

≥ 0.

Quindi risulta

max z = 4 −4x

3

−2x

4

x

1

=

⁷₄

+

¹₄

x

3

−

¹₂

x

4

x

2

= 2 −x

3

+x

4

y

1

= −

³₄

+

³₄

x

3

+

¹₂

x

4

x

1

, . . . , x

4

, y

1

≥ 0.

max z = 1 −x

3

−4y

1

x

1

= 1 +x

3

−y

1

x

2

=

⁷₂

−

⁵₂

x

3

+2y

1

x

4

=

³₂

−

³₂

x

3

+2y

1

x

1

, . . . , x

4

, y

1

≥ 0.

7. (a) NO, poich´e deve essere

U (P

k+1

), U (P

k+2

) ≤ U (P

k

) = 15 2 < 8.

(b) Questa eventualit`a non pu` o essere esclusa, in quanto il rilassamento lineare di uno dei due sottoproblemi pu´ o avere regione ammissibile vuota. Quindi SI.

(c) NO, perch´e nulla garantisce che tali soluzioni abbiano z > LB = 4.

8. Nell’ipotesi di partire dal nodo a, l’applicazione dell’algoritmo porta a selezionare, nell’ordine, (a, c), (a, d), (a, b), (b, f ), (d, e),

che definiscono un albero di peso totale 24.