(5 punti) Si consideri il problema di PLI dell’esercizio 2

(1)

ESERCIZIO 1. (4 punti) La riformulazione di un problema di PL rispetto alla base B = {x3, x4}

`e la seguente:

max 1 − x1+ x2

x3= 1 − x1− x2

x4= 2 − x1+ x2

x1, x2, x3, x4≥ 0

Per ciascuno dei seguenti punti modificate un solo coefficiente o termine noto della riformulazione in modo tale che il problema abbia:

(1) soluzione ottima unica;

(2) infinite soluzioni ottime;

(3) obiettivo illimitato;

(4) regione ammissibile vuota.

Dare in tutti i casi una breve motivazione della risposta.

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

max x2

6x1+ 4x2+ x3= 9

−x1+ x2+ x4= 1 x1, x2, x3, x4≥ 0 x1, x2, x3, x4∈ I

La riformulazione rispetto alla base ottima B^∗= {x1, x2} del suo rilassamento lineare `e la seguente:

max ³₂−₁₀¹x3−³₅x4

x1= ¹₂−₁₀¹x3+²₅x4

x2= ³₂−₁₀¹x3−³₅x4

x1, x2, x3, x4≥ 0

Si risolva il problema di PLI utilizzando l’algoritmo branch-and-bound.

ESERCIZIO 3. (5 punti) Si consideri il problema di PLI dell’esercizio 2. Avete la possibilità di utilizzare come equazione generatrice del taglio di Gomory nella riformulazione rispetto alla base ottima del suo rilassamento lineare sia quella relativa a x1 che quella relativa a x2. Spiegare perché in questo caso specifico è indifferente usare l’una o l’altra di queste due possibili equazioni generatrici del taglio. Quindi, risolvere il problema di PLI usando l’algoritmo di taglio di Gomory.

ESERCIZIO 4. (6 punti) Si consideri ancora il rilassamento lineare del problema di PLI dell’esercizio 2. Viene richiesto di:

(1) scriverne il duale (1 punto);

(2) risolvere il duale utilizzando le condizioni di complementarit`a (2 punti);

(3) determinare in quale intervallo posso far variare la modifica ∆b2 del termine noto del secondo vincolo senza che cambi la base ottima (2 punti);

(4) stabilire come varia il valore ottimo nell’intervallo individuato (1 punto).

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

a1= 50 a2= 30 b1= 40 b2= 20 b3= 20

1

(2)

e i seguenti costi unitari di trasporto lungo gli archi:

N1 N 2 N 3

D1 6 7 8

D2 2 5 3

Lo si risolva restituendone una soluzione ottima e il valore ottimo.

ESERCIZIO6. (5 punti) Per ciascuna delle seguenti affermazioni dire se `e vera o falsa motivando la risposta:

(1) l’insieme di soluzioni ottime di un problema di PL pu`o contenere esattamente due punti;

(2) dato un problema di PLI con obiettivo da massimizzare, il valore ottimo del suo rilassamento lineare `e sempre maggiore o uguale del valore ottimo del problema di PLI;

(3) dato un problema di PLI, l’aggiunta di un taglio valido non modifica la sua regione ammissibile ma modifica quella del suo rilassamento lineare;

(4) data una base ammissibile per un problema di PL, il fatto che i coefficienti di costo ridotto di tutte le variabili al di fuori di tale base siano minori o uguali a zero `e condizione necessaria e sufficiente per l’ottimalit`a della soluzione di base corrispondente;

(5) se il problema primale ha per regione ammissibile un politopo, allora anche il suo duale ha per regione ammissibile un politopo.

ESERCIZIO 7. (3 punti) Un generico problema del trasporto con m depositi e n negozi ha il seguente modello matematico:

min Pm i=1

Pn

j=1cijxij

Pn

j=1xij = ai i= 1, . . . , m Pm

i=1xij = bj j= 1, . . . , n

xij≥ 0 interi i= 1, . . . , m j = 1, . . . , n

Lo si modifichi nel caso in cui esista anche un costo fisso dij da pagare solo nel caso in cui venga inviata una quantit`a strettamente positiva di merce tra un deposito i e un negozio j.

(3)

Soluzioni 1.(1) Funzione obiettivo: z = 1 − x1− x2.

(2) Funzione obiettivo: z = 1 − x1; in questo modo sono ottime sia (x1 = x2 = 0, x3 = 1, x4= 2) che (x1= 0, x2= 1, x3= 0, x4= 3) e tutti i punti del segmento che li congiunge.

(3) : primo vincolo x3= 1 − x1+ x2, si vede la condizione di illimitatezza sulla colonna di x2. (4) Termine noto della prima uguaglianza: x3 = −1 − x1− x2, e l’uguaglianza `e incoerente con x1, x2, x3≥ 0.

2.Ricavato l’upper bound UB0= ³₂ si procede al branch sulla variabile x1.

Nodo 1:x1≤ 0 ⇐⇒ 1 2− 1

10x3+2 5x4≤ 0, da cui

1 2− 1

10x3+2

5x4+ y1= 0, y1≥ 0 max z= ³₂ −₁₀¹x3 −³₅x4

x1= ¹₂ −₁₀¹x3 +²₅x4

x2= ³₂ −₁₀¹x3 −³₅x4

y1= −¹₂ +₁₀¹x3 −²₅x4

x1, . . . , x4, y1≥ 0 max z= 1 −y1 −x4

x1= 0 −y1

x2= 1 −y1 −x4

x3= 5 +10y1 +4x4

x1, . . . , x4, y1≥ 0.

Si chiude il nodo 1 per ottimalit`a e si pone LB = 1.

Nodo 2:x1≥ 1 ⇐⇒ 1 2− 1

10x3+2 5x4≥ 1, 1

2− 1 10x3+2

5x4− y2= 1, y2≥ 0 max z= ³₂ −₁₀¹x3 −³₅x4

x1= ¹₂ −₁₀¹x3 +²₅x4

x2= ³₂ −₁₀¹x3 −³₅x4

y2= −¹₂ −₁₀¹x3 +²5x4

x1, . . . , x4, y2≥ 0 max z= ³₄ −¹₄x3 −³₂y2

x1= 1 +y2

x2= ³₄ −¹₄x3 −³₂y2

x4= ⁵₄ +¹₄x3 +⁵₂y2

x1, . . . , x4, y2≥ 0.

Il nodo 2 viene quindi chiuso per bound (UB2= ³₄ ≤ LB).

3.Poich´e mantissa(−²₅) = mantissa(³₅) = ³₅, entrambe le righe generano lo stesso taglio 1

10x3+3 5x4≥ 1

2;

(4)

ne segue 1 10x3+3

5x4≥ 1

2 ⇐⇒ 1 10x3+3

5x4− y1=1

2, y1≥ 0;

max z= ³₂ −₁₀¹x3 −³₅x4

x1= ¹₂ −₁₀¹x3 +²₅x4

x2= ³₂ −₁₀¹x3 −³₅x4

y1= −¹₂ +10¹x3 +³₅x4

x1, . . . , x4, y1≥ 0

max z= 1 −y1

x1= 0 −y1 +x4

x2= 1 −y1

x3= 5 +10y1 −6x4

x1, . . . , x4, y2≥ 0

ottimo.

4.(1) Il duale richiesto `e min 9u1+ u2

soggetto a

6u1− u2≥ 0 4u1+ u2≥ 1 u1, u2≥ 0

(2) Dalle condizioni di complementariet`a si ha x^∗₁>0 =⇒ 6u^∗1− u^∗2= 0

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

e quindi u^∗1=₁₀¹, u^∗2=³₅. Si pu`o verificare anche che z^∗= 9u^∗1+ u^∗2= ³₂, coincidente con il valore dell’ottimo primale.

(3) Ricavando la A⁻¹_B e imponendo l’ammissibilit`a della soluzione perturbata si hanno le condizioni

−2

5∆b2≥ −1 2 3

5∆b2≥ −3 2

=⇒ −5

2≤ ∆b2≤5 4.

(4) La variazione della funzione obiettivo nell’intervallo `e ∆z^∗= u^∗2∆b2= ³₅∆b2.

5.Il problema `e bilanciato; partendo dalla base individuata con il metodo dell’angolo di Nord-Ovest si ottiene

N1 N 2 N 3 D1 40⁻ 10⁺ 50 D2 + 10⁻ 20 30

40 20 20

con ¯c13= 3, ¯c21= −2; entra in base x21ed esce x22. N1 N 2 N 3

D1 30 20 50

D2 10 20 30

40 20 20

con ¯c13= 1, ¯c22= 2 (ottimo). Il valore ottimo `e pari a 400.

6. (1) Falso. Se x1, x2 ∈ Sott, con z^∗ = cx1 = cx2, per la linearit`a della funzione obiettivo risulta, per ogni ¯x= αx1+ (1 − α)x2 con α ∈ (0, 1),

c¯x= αcx1+ (1 − α)cx2= αz^∗+ (1 − α)z^∗= z^∗, e quindi ¯x∈ Sott.

(2) Vero, perch´e (Sa∩ Zⁿ+) ⊆ Sa.

(5)

(3) Vero, per definizione di taglio.

(4) Falso, è condizione sufficiente ma non necessaria. Si possono costruire esempi di basi (degeneri) per cui non è soddisfatta la condizione di ottimalità pur essendo la soluzione di base corripsondente già una soluzione ottima.

(5) Falso. Si consideri il problema

max {x2: x1+ x2≤ 2, x2≤ 1, x1, x2≥ 0}

che ha come regione ammissibile un politopo limitato. Il suo duale `e min {2u1+ u2: u1≥ 0, u1+ u2≥ 1, u1, u2≥ 0}

che ha come regione ammissibile un poliedro illimitato.

7.Il modello si pu`o estendere come segue, con una serie di variabili binarie yij ∈ {0, 1}.

min Xm i=1

Xn j=1

cijxij+ Xm i=1

Xn j=1

dijyij

soggetto a Xn j=1

xij = ai i= 1, . . . , m, Xm

i=1

xij = bj j= 1, . . . , n,

xij ≤ aiyij, i= 1, . . . , m, j = 1, . . . , n,

xij ≥ 0, interi, yij ∈ {0, 1} , i= 1, . . . , m, j = 1, . . . , n,