COMPITO DI RICERCA OPERATIVA

ESERCIZIO 1. (9 punti) Il duale di un problema di PL in forma standard `e il seguente:

min 3u 1 + 5u 2 + u 3

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

u 1 ≥ 3 u 2 ≥ 0 u 3 ≥ 0

Si scriva il primale (2 punti). Si risolva il primale con l’algoritmo che si ritiene pi` u opportuno (3 punti). Si risolva il duale utilizzando le condizioni di complementarit` a (2 punti). Si stabilisca in quale intervallo posso far variare la modifica ∆b 3 del termine noto del terzo vincolo del primale senza che cambi la base ottima (2 punti).

ESERCIZIO 2. (8 punti) Si consideri il seguente problema di PLI:

max 4x 2 − x 1

−x 1 + 2x 2 ≤ ³ ₂ 2x 1 + x 2 ≤ 3

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

Dopo averlo trasformato in forma standard, si risolva il problema utilizzando l’algoritmo di Gomory restituendo soluzione ottima e valore ottimo del problema. Per il primo taglio, lo si scriva in funzione delle variabili originarie x 1 e x 2 .

ESERCIZIO 3. (7 punti) Una ditta pu` o produrre tre diversi prodotti A, B e C. La produzione di un’unit` a di ciascuno di questi prodotti richiede quantit` a diverse di tre risorse α, β, γ, come riportato nella tabella seguente, dove sono riportati anche il profitto per unit` a di prodotto e la disponibilit` a massima di ciascuna risorsa:

α β γ Profitto unitario

A 5 2 4 10

B 3 3 3 8

C 7 4 5 15

Disponibilit` a massima 20000 10000 15000

La ditta ha anche la possibilit` a di scegliere se acquistare o meno 5000 unit` a in pi` u di ciascuna delle tre risorse α, β, γ a un costo rispettivamente pari a 12000, 3000 e 6000. La ditta vuole scegliere quanti prodotti di ciascun tipo realizzare e per ciascuna risorsa se acquistare o meno le 5000 unit` a aggiuntive, in modo da massimizzare i propri profitti. Si scriva un modello matematico per questo problema.

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

(1) Se in un nodo di un albero di branch-and-bound ottengo una soluzione ottima del rilassa- mento lineare a coordinate non intere, allora tale nodo verr` a certamente selezionato a un certo punto per fare branching su di esso? (1 punto)

(2) Se il duale di un problema di PL ha regione ammissibile vuota, allora il corrispondente primale ha obiettivo illimitato? (1 punto)

1

(3) Se nell’obiettivo della riformulazione rispetto alla base ottima di un problema di PL in forma standard, ci sono due coefficienti di costo ridotto nulli, allora il problema di PL ha certamente almeno due soluzioni ottime? (1.5 punti)

(4) Siano dati un problema di PL in forma standard e il suo duale. Si supponga che il primale ammetta soluzioni ottime. Se al problema primale aggiungiamo un vincolo in modo tale che continui ad ammettere soluzioni ottime, allora `e vero che il valore ottimo del nuovo duale `e non superiore a quello originario? (1.5 punti)

(5) ` E possibile che dati due punti nella regione ammissibile S a di un problema di PL, esista un punto lungo il segmento che li congiunge che non appartiene a S a ? (1 punto)

ESERCIZIO 5. (3 punti) Sia dato un problema di PLI e il suo rilassamento lineare. Si supponga

che il valore ottimo del rilassamento lineare sia strettamente maggiore rispetto a quello del problema

di PLI. Si dimostri che all’interno del segmento che congiunge una soluzione ottima del problema

di PLI con una soluzione ottima del rilassamento lineare, non ci possono essere punti a coordinate

tutte intere.

Soluzioni 1. Il primale `e

max x 1 + 2x 2 + 3x 3

soggetto a

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

x 1 −x 2 +x 4 = 5

x 1 +x 5 = 1

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

Applicando il simplesso con base iniziale {x 3 , x 4 , x 5 } si ottiene max z = 9 +4x 1 −4x 2

x 3 = 3 +x 1 −2x 2

x 4 = 5 −x 1 +x 2

x 5 = 1 −x 1

x 1 , . . . , x 5 ≥ 0

=⇒

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

x 3 = 4 −x 5 −2x 2

x 4 = 4 +x 5 +x 2

x 1 = 1 −x 5

x 1 , . . . , x 5 ≥ 0

Dalla soluzione ottima del primale, usando le condizioni di complementariet`a, si hanno le condizioni x ^∗ ₁ > 0 =⇒ − u ^∗ 1 + u ^∗ 2 + u ^∗ 3 = 1

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



 

 

=⇒ u ^∗ 1 = 3, u ^∗ 2 = 0, u ^∗ 3 = 4.

La matrice di base inversa associata alla base ottima `e A ⁻¹ _B

=





1 0 1

0 1 −1

0 0 1





dalla quale per ∆b 3 si ottengono le condizioni

∆b ³ ≥ −4

−∆b 3 ≥ −4

∆b ³ ≥ −1



 

 

=⇒ −1 ≤ ∆b 3 ≤ 4

2. Il programma a variabili intere, in forma standard, `e il seguente.

max −x 1 + 4x 2

soggetto a

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

Per risolvere il rilassamento lineare si pu` o applicare il simplesso partendo dalla base ammissibile {x 3 , x 4 }.

max z = 0 −x 1 +4x 2

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

x 4 = 3 −2x 1 −x 2

x 1 , . . . , x 4 ≥ 0

=⇒

max z = 3 +x 1 −x 3

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

x 4 = ⁹ ₄ − ⁵ ₂ x 1 + ¹ ₄ x 3

x 1 , . . . , x 4 ≥ 0

=⇒

max z = ³⁹ ₁₀ − ² ₅ x 4 − ₁₀ ⁹ x 3

x 2 = ⁶ ₅ − ¹ ₅ x 4 − ¹ ₅ x 3

x 1 = ₁₀ ⁹ − ² ₅ x 4 + ₁₀ ¹ x 3

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

Generando un taglio di Gomory dalla prima riga si ha 1

5 x 4 + 1 5 x 3 ≥ 1

5 ⇐⇒ 1 5 x 4 + 1

5 x 3 − y 1 = 1

5 , y 1 ≥ 0 e quindi

max z = ³⁹ ₁₀ − ² ₅ x 4 − ₁₀ ⁹ x 3

x 2 = ⁶ ₅ − ¹ ₅ x 4 − ¹ ₅ x 3

x 1 = ₁₀ ⁹ − ² ₅ x 4 + ₁₀ ¹ x 3

y 1 = − ¹ ₅ + ¹ ₅ x 4 + ¹ ₅ x 3

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

=⇒

max z = ⁷ ₂ −2y 1 − ¹ ₂ x 3

x 2 = 1 −y 1

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

x 4 = 1 +5y 1 −x 3

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

Generando il taglio sulla seconda riga si ottiene 1

2 x 3 ≥ 1

2 ⇐⇒ 1

2 x 3 − y 2 = 1

2 , y 2 ≥ 0.

Riottimizzando si ha

max z = ⁷ ₂ −2y 1 − ¹ ₂ x 3

x 2 = 1 −y 1

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

x 4 = 1 +5y 1 −x 3

y 2 = − ¹ ₂ + ¹ ₂ x 3

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

=⇒

max z = 3 −2y 1 −y 2

x 2 = 1 −y 1

x 1 = 1 −2y 1 +y 2

x 4 = 0 +5y 1 −2y 2

x 3 = 1 +2y 2

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

L’ultima riformulazione corrisponde all’ottimo x ^∗ 1 = x ^∗ 2 = x ^∗ 3 = 1, x ^∗ 4 = 0.

Il primo taglio, in funzione dele variabili originarie x 1 e x 2 `e il seguente 1

5 x 3 + 1 5 x 4 = 1

5 (3 + 2x 1 − 4x 2 ) + 1

5 (3 − 2x 1 − x 2 ) ≥ 1 5 da cui

x 2 ≤ 1.

3. Si possono usare le variabili intere

x i = unit` a prodotte di i (i = A, B, C).

e le variabili binarie

y j = 1 ⇐⇒ si acquista la fornitura extra di j (j = α, β, γ).

Il modello risulta

max z = 10x A + 8x B + 15x C − 12000y α − 3000y β − 6000y γ

soggetto a

5x A + 3x B + 7x C ≤ 20000 + 5000y α

2x A + 3x B + 4x C ≤ 10000 + 5000y β

4x A + 3x B + 5x C ≤ 15000 + 5000y _γ x A , x B , x C ≥ 0, x A , x B , x C ∈ I, y A , y B , y C ∈ {0, 1} .

4. Risposte.

(1) No, potrebbe essere chiuso per bound prima di essere selezionato.

(2) No, si potrebbe anche avere S a = ∅.

(3) No, per garantirlo si dovrebbe anche sapere, ad esempio, che la base ottima non `e degenere.

(4) Vero. Siano

max {cx : x ∈ S a } , max {cx : x ∈ S _a ^′ }

il primale ed il primale con il vincolo aggiunto, per cui S _a ^′ ⊆ S a . Siano min u ^T b : u ∈ D a , min y ^T b : y ∈ D _a ^′

i rispettivi duali.

Se il problema originale e quello modificato ammettono entrambi soluzioni ottime, le ammettono anche i corrispondenti duali. Per la dualit` a forte e tenendo presente S _a ^′ ⊆ S _a si ha

min y ^T b: y ∈ D ^′ _a = max {cx: x ∈ S _a ^′ } ≤ max {cx : x ∈ S a } = min u ^T b: u ∈ D a . (5) No, per la convessit` a di S a .

5. Per assurdo. Con le notazioni viste a lezione, sia ¯ x ∈ S ott , x ^∗ ∈ Z ott , e si supponga di avere un punto ˆ x all’interno del segmento x ^∗ ¯ x a coordinate intere.

Il punto ˆ x `e esprimibile come ˆ

x = αx ^∗ + (1 − α)¯ x per un opportuno α ∈ (0, 1).

Poich´e x ^∗ , ¯ x ∈ S a , anche ˆ x ∈ S a , e quindi ˆ x ∈ Z a , visto che si suppone a coordinate intere. Ma allora in ˆ x la funzione obiettivo vale

c ^T x ˆ = αc ^T x ^∗ + (1 − α)c ^T x ¯ > αc ^T x ^∗ + (1 − α)c ^T x ^∗ = c ^T x ^∗ ,

contraddicendo l’ottimalit` a di x ^∗ .