COMPITO DI RICERCA OPERATIVA

COMPITO DI RICERCA OPERATIVA

ESERCIZIO 1. (9 punti) Si consideri il seguente problema di PL:

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

x 1 , . . . , x 4 ≥ 0

Lo si risolva con il metodo pi` u opportuno (2 punti). Scriverne il duale e risolverlo con le condizioni di complementarit` a (3 punti). Determinare l’inversa della matrice associata alla base ottima e la si usi per individuare in quale intervallo si pu` o far variare una perturbazione ∆a 22 del coefficiente della variabile x 2 nel secondo vincolo di uguaglianza (3 punti) e si dica se il problema ammette ancora soluzioni ottime per il valore ∆a 22 = −1 (1 punto).

ESERCIZIO 2. (7 punti) Un’azienda pu` o pianificare la realizzazione di tre prodotti P1, P2 e P3 che richiedono l’uso di quattro risorse R1, R2, R3 e R4. Nella tabella seguente sono specificate le quantit` a di ciascuna risorsa richieste per la realizzazione di una singola unit` a di ciascuno dei tre prodotti, insieme al profitto per unit` a di prodotto (ultima colonna) e alla disponibilit` a massima delle quattro risorse (ultima riga):

R1 R2 R3 R4 Profitto unitario

P 1 5 6 2 6 10

P 2 3 8 4 6 12

P 3 4 7 5 4 11

Disponibilit` a massima 20500 28000 20000 25000

Si sa inoltre che non sono accettabili soluzioni in cui esista una o pi` u risorse inutilizzate (rispetto alla disponibilit` a massima) per pi` u del 10%. Si formuli il modello matematico per pianificare la produzione dei prodotti in modo che il profitto complessivo dell’azienda sia il pi` u elevato possibile.

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

max −x 3 − 2x 4

4x 1 + 6x 2 − 5x 3 = 6 8x 1 + 2x 2 − 5x 4 = 7

x 1 , . . . , x 4 ≥ 0 x 1 , . . . , x 4 ∈ I

La riformulazione rispetto alla base ottima del rilassamento lineare di questo problema `e la seguente:

max −x ³ − 2x ⁴ x 1 = ³ ₄ − ¹ ₄ x 3 + ³ ₄ x 4

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

x 1 , . . . , x 4 ≥ 0

Risolvere il problema di PLI con l’algoritmo di taglio basato sui tagli di Gomory.

ESERCIZIO 4. (9 punti) Rispondere a ciascuna delle seguenti domande.

(1) Sia dato un problema di PL

max cx

Ax = b x ≥ 0

1

2 COMPITO DI RICERCA OPERATIVA

con il relativo duale

max ub

uA ≥ c

Indichiamo con S a la regione ammissibile del primale e con D a quella del duale. Si dimostri che dati x 0 ∈ S a a u 0 ∈ D a , vale

cx ₀ ≤ u 0 b (3 punti).

(2) Si descrivano i tre casi in cui un nodo foglia di un albero di branch-and-bound pu` o essere cancellato (3 punti).

(3) Nell’ analisi di sensitivit` a si spieghi, motivando la risposta, quale algoritmo si pu` o utilizzare per ottenere la nuova soluzione ottima di un problema di PL, nel caso in cui la modifica del coefficiente di una variabile nell’obiettivo faccia perdere l’ottimalit` a della base ottima del problema non modificato (3 punti).

ESERCIZIO 5. (3 punti) Un upper bound per un problema `e calcolabile risolvendone il rilassa- mento lineare. Si spieghi perch´e, nel caso in cui la risoluzione del rilassamento lineare non consenta di risolvere anche il problema di PLI stesso, un upper bound ancora migliore (o, comunque, non peggiore) `e dato dalla somma del valore ottimo del rilassamento lineare con il pi` u grande dei coefficienti di costo ridotto della variabili al di fuori della base ottima del rilassamento lineare.

Formalmente, si richiede di dimostrare che, data la riformulazione rispetto alla base ottima del rilassamento lineare

max γ 0 + P n−m

j=1 γ j x i

x i

= β 1 + P n−m

j=1 α 1j x i

· · · x i

= β k + P n−m

j=1 α kj x i

· · · x i

= β m + P n−m

j=1 α mj x i

x 1 , . . . , x n ≥ 0

con i valori β i , i = 1, . . . , m, non tutti interi, un upper bound migliore (o, comunque, non peggiore) di γ 0 , `e dato da

γ 0 + max

j=1,...,n−m {γ j }.

COMPITO DI RICERCA OPERATIVA 3

Soluzioni

1. La base {x 3 , x 4 } risulta ammissibile, quindi si ottiene, con una iterazione di simplesso:

max z = 0 +3x 1 + x 2

x 3 = 3 −x 1 +x 2

x 4 = 4 −2x 1 −x 2

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

=⇒

max z = 6 − ³ ₂ x 4 − ¹ ₂ x 2

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

x 1 = 2 − ¹ ₂ x 4 − ¹ ₂ x 2

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

Il duale del problema dato `e il seguente.

max w = 3u 1 + 4u 2

soggetto a

u 1 + 2u 2 ≥ 3

−u 1 + u 2 ≥ 1 u 1 ≥ 0 u 2 ≥ 0.

Avendo nell’ottimo primale x ^∗ 1 , x ^∗ 3 > 0, all’ottimo duale si deve avere u ^∗ 1 + 2u ^∗ 2 = 3

u ^∗ 1 = 0 )

=⇒ u ^∗ 1 = 0, u ^∗ 2 = 3 2 . La matrice di base corrispondente a B ^∗ = {x 3 , x 1 } `e

A B

= 1 1 0 2



con inversa A B

= 1 − ¹ ₂ 0 ¹ ₂

 .

Da questa si pu` o ricavare

u ^∗ 1 u ^∗ 2
= 0 3
· 1 − ¹ ₂ 0 ¹ 2



= 0 ³ 2
,

in accordo con quanto ricavato dalle condizioni di complementariet`a. Perturbando a 22 si perturba il costo ridotto γ 2 trasformandolo in

γ 2 = − 1 2 − 3

2 ∆a 22 ,

che per preservare l’ottimalit` a richiede

− 1

3 ≤ ∆a ²² < +∞.

Per il valore ∆a 22 = −1 il coefficiente di costo ridotto di x 2 diventa positivo, mentre nei vincoli della riformulazione i coefficienti di x 2 saranno

 3/2

−1/2



− (−1)

 −1/2 1/2



=

 1 0



Essendo questi tutti non negativi, il problema ha obiettivo illimitato e quindi non ha soluzioni ottime.2. Definendo tre variabili x 1 , x 2 , x 3 dove x i = unit` a prodotte di P i , si pu` o formulare il seguente modello.

max z = 10x 1 + 12x 2 + 11x 3

4 COMPITO DI RICERCA OPERATIVA

soggetto a

5x 1 + 3x 2 + 4x 3 ≤ 20500 (R 1 )

6x ¹ + 8x ² + 7x ³ ≤ 28000 (R ² )

2x 1 + 4x 2 + 5x 3 ≤ 20000 (R 3 )

6x 1 + 6x 2 + 4x 3 ≤ 25000 (R 4 )

5x 1 + 3x 2 + 4x 3 ≥ 20500 × 0.9 (R ^′ 1 )

6x 1 + 8x 2 + 7x 3 ≥ 28000 × 0.9 (R ^′ 2 )

2x 1 + 4x 2 + 5x 3 ≥ 20000 × 0.9 (R ^′ 3 )

6x 1 + 6x 2 + 4x 3 ≥ 25000 × 0.9 (R ^′ 4 )

x 1 , x 2 , x 3 ≥ 0.

I vincoli R 1 , . . . R 4 impongono di non sforare la disponibilit` a massima di risorse, mentre R ^′ 1 , . . . , R ^′ 4

impongono di usare per ogni risorsa non meno del 90% dell’ammontare disponibile.

3. Dalla riformulazione ottima

max z = 0 −x 3 −2x 4

x 1 = ³ ₄ − ¹ ₄ x 3 + ³ ₄ x 4

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

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

si ottiene, calcolando il taglio di Gomory sulla prima riga:

1 4 x 3 + 1

4 x 4 ≥ 3

4 ⇐⇒ 1 4 x 3 + 1

4 x 4 − y 1 = 3

4 , y 1 ≥ 0.

Si prosegue quindi con

max z = 0 −x 3 −2x 4

x 1 = ³ ₄ − ¹ ₄ x 3 + ³ ₄ x 4

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

y 1 = − ³ ₄ + ¹ 4 x 3 + ¹ ₄ x 4

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

=⇒

max z = −3 −4y 1 −x 4

x 1 = 0 −y 1 +x 4

x 2 = ⁷ ₂ +4y 1 − ³ ₂ x 4

x ³ = 3 +4y ¹ −x ⁴ x 1 , . . . , x 4 , y 1 ≥ 0.

Effettuando ancora un taglio sulla seconda riga si ottiene 1

2 x 4 ≥ 1

2 ⇐⇒ 1

2 x 4 − y 2 = 1

2 , y 2 ≥ 0.

e quindi

max z = −3 −4y 1 −x 4

x 1 = 0 −y 1 +x 4

x 2 = ⁷ ₂ +4y 1 − ₂ ³ x 4

x 3 = 3 +4y 1 −x 4

y 2 = − ¹ ₂ + ¹ 2 x 4

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

=⇒

max z = −4 −4y 1 −2y 2

x 1 = 1 −y 1 +2y 2

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

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

x 4 = 1 +2y 2

x 1 , . . . , x 4 , y 1 , y 2 ≥ 0 4. Si vedano le dispense.

5. Sia ¯ x la soluzione ottima di base del rilassamento lineare, e x ^∗ la soluzione ottima intera del PLI.

Poich´e ¯ x `e una soluzione di base, essa `e l’unico punto di S a con tutte le variabili fuori base a valore nullo.

Poich´e x ^∗ `e un punto di S a distinto da ¯ x, essa deve avere almeno una tra le x ^∗ _i

, . . . , x ^∗ _i

a valore non nullo; inoltre, poich´e x ^∗ `e ammissibile per il PLI, almeno una tra tali variabili avr` a un valore ≥ 1. Quindi risulter` a

z ^∗ = γ 0 +

n−m

X

j=1

γ j x ^∗ _i

≤ γ 0 + max

j {γ j }.