Settembre 2006

COMPITO DI RICERCA OPERATIVA
ESERCIZIO 1.
(5 punti) Sia dato il seguente problema di PL:
−x1 + x2
min
x1 + x 2 ≤ 3
x1 + x 2 ≥ 2
2x1 + x2 ≤ 3
x1 ≤ 0
x2 ≥ 0
Si trasformi questo problema in forma standard e lo si risolva con l’algoritmo più
opportuno.
ESERCIZIO 2.
(6 punti) Dato il problema di PL con due variabili:
max
x1 + 2x2
x1 + x 2 ≤ 3
x1 ≤ 2
x2 ≤ 2
x1 , x 2 ≥ 0
lo si risolva graficamente restituendo soluzione ottima e valore ottimo. Si discuta
poi come varia la soluzione ottima dello stesso problema se il vincolo x1 + x2 ≤ 3
viene trasformato nel vincolo x1 + x2 ≤ 3 + t al variare di t tra −∞ e +∞.
ESERCIZIO 3.
(3 punti) Il problema di PL:
max
5x1 + 3x2
x1 + 2x2 + x3 = 4
2x1 + x2 + x4 = 4
x1 , x 2 , x 3 , x 4 ≥ 0
ha soluzione ottima:
x∗1 =
4
3
x∗2 =
4
3
x∗3 = 0 x∗4 = 0.
Si scriva il duale di questo problema e se ne determini una soluzione ottima utilizzando la condizioni di complementarità.
ESERCIZIO 4.
(4 punti) Sia dato il seguente problema di PLI:
max
x1
3x1 + x2 = 8
2x1 − x3 = 5
x1 , x 2 , x 3 ≥ 0 x 1 , x 2 , x 3 ∈ I
1
2
COMPITO DI RICERCA OPERATIVA
La riformulazione rispetto alla base ottima B ∗ = {x1 , x3 } del rilassamento lineare
di questo problema è la seguente:
8
3
max
− 31 x2
x1 =
8
3
1
3
− 13 x2
x3 = − 23 x2
x1 , x 2 , x 3 ≥ 0
Si risolva il problema di PLI usando l’algoritmo Branch-and-Bound.
(5 punti) Una ditta ha tre operai cui può affidare la realizzazione
di tre prodotti. È noto che:
(1) i tre operai non possono lavorare contemporaneamente e le ore complessive
di tutti e tre in un giorno sono al massimo 8;
(2) di ogni prodotto c’è una richiesta minima giornaliera, mentre ognuno dei
tre operai produce una certa quantità dei due prodotti ogni ora e ha un
certo costo orario. Tutti questi dati sono riassunti nella tabella seguente:
ESERCIZIO 5.
Prod. 1
Prod. 2
Costo orario
Op.1 Op.2 Op.3
5
7
8
9
6
4
18
16
12
Richiesta minima
25
30
Scrivete un modello matematico per decidere quante ore giornaliere di lavoro assegnare a ciascuno dei tre operai per minimizzare il costo totale, tenendo conto del
numero massimo di ore giornaliere e delle richieste minime giornaliere di prodotti.
ESERCIZIO 6.
(4 punti) Sia data la rete con i seguenti valori bi , i = 1, . . . , 6 :
b1 = 3 b2 = 0 b3 = 0 b4 = −3
e i seguenti costi unitari di trasporto lungo gli archi:
c12 = −1 c14 = 7 c24 = 2 c31 = 3 c43 = −5.
Si dimostri che la base B = {x14 , x24 , x43 } è ammissibile e partendo da questa si
risolva il problema di flusso a costo minimo usando il metodo del simplesso per tale
problema.
ESERCIZIO 7. (4 punti) Il rilassamento lineare di un problema di PLI ha la
seguente riformulazione rispetto alla base ottima B ∗ = {x3 , x4 }:
max
5 − 32 x1 − 12 x2
x3 =
7
3
5
3
− 4x1 − x2
x4 = + x1 − 2x2
x1 , x 2 , x 3 , x 4 ≥ 0
Dalla sola osservazione di questa riformulazione, si spieghi perché il problema di
PLI ha regione ammissibile vuota.
ESERCIZIO 8. (4 punti) Dato un problema di PLI e il suo rilassamento lineare,
si indichino, facendo opportuni esempi grafici, tutte le possibili relazioni che legano
Za , Zott (rispettivamente, regione ammissibile e insieme delle soluzioni ottime del
problema di PLI) e Sa , Sott (rispettivamente, regione ammissibile e insieme delle
soluzioni ottime del rilassamento lineare).
COMPITO DI RICERCA OPERATIVA
3
Soluzioni
1. Il problema posto in forma standard è
max −x01 − x2
soggetto a
−x01 + x2 + x3 = 3
−x01 + x2 − x4 = 2
−2x01 + x2 + x5 = 3
x01 , x2 , x3 , x4 , x5 ≥ 0
con x01 = −x1 . Riformulando rispetto alla base {x3 , x4 , x5 } si ottiene
max
z
x3
x4
x5
=
0 −x01
−x2
=
3 +x01
−x2
= −2 −x01 +1x2
=
3 +2x01
−x2
0
x1 , . . . , x 5 ≥ 0
max
=⇒
z
x3
x2
x5
= −2 −2x01
=
1
=
2 +x01
=
1 +x01
0
x1 , . . . , x 5 ≥ 0
−x4
−x4
+x4
−x4
(applicando il simplesso duale).
2. La regione ammissibile del problema è racchiusa tra gli assi coordinati e le rette
x1 = 2, x2 = 2, x1 + x2 = 3.
x2
OPT
0
x1
Le rette isoprofitto sono perpendicolari alla direzione del vettore (2, 1). L’ottimo è
il punto (x∗1 = 1, x∗2 = 2). Per t ∈ (−∞, +∞), risulta
−1 ≤ t ≤ 1 =⇒
x∗1 = 1 + t, x∗2 = 2;
1 < t < +∞ =⇒
x∗1 = 2, x∗2 = 2;
−3 ≤ t < −1 =⇒
x∗1 = 0, x∗2 = 3 − t;
infine per t < −3 il problema risulta privo di soluzioni ammissibili.
3. Il problema duale è
min 4u1 + 4u2
soggetto a
u1 + 2u2 ≥ 5
2u1 + u2 ≥ 3
u1 ≥ 0
u2 ≥ 0
4
COMPITO DI RICERCA OPERATIVA
All’ottimo, per le condizioni di complementarietà, risulta:

4

x∗1 = > 0 =⇒ u∗1 + 2u∗2 = 5
1
7
3
=⇒ u∗1 = , u∗2 = .
4

3
3
∗
∗
∗
x2 = > 0 =⇒ 2u1 + u2 = 3
3
Risulta inoltre, come previsto da risultati noti,
4
4
32
1
7
z∗ = 5 · + 3 · =
=4· +4· .
3
3
3
3
3
4. Si effettua l’operazione di branch su x1 , ricavando due nodi per i quali rispettivamente si impone x1 ≤ 2 e x1 ≥ 3.
Per il nodo 1 risulta
1
2
8 1
− x2 ≤ 2 =⇒ − x2 + y1 = − , y1 ≥ 0.
x1 ≤ 2 =⇒
3 3
3
3
Per il nodo 2 si prova immediatamante l’assenza di soluzioni ammisiibili in quanto
8 1
1
1
x1 ≥ 3 =⇒
− x2 ≥ 3 =⇒ − x2 − y2 = , y2 ≥ 0.
3 3
3
3
Sviluppando il nodo 1 si ottiene quanto segue.
max
z
x1
x3
y1
8
=
− 13 x2
3
8
=
− 13 x2
3
1
=
− 23 x2 =⇒
3
2
= − 3 + 31 x2
x1 , x 2 , x 3 , y 1 ≥ 0
max
z
x1
x3
x2
=
2 −y1
=
2 −y1
= −1 −2y1
=
2 +3y1
x1 , x 2 , x 3 , y 1 ≥ 0
L’ultima riformulazione prova che anche il nodo 1 è privo di soluzioni ammissibili.
L’intero problema ha quindi Za = ∅.
5. Dette x1 , x2 , x3 le ore lavorate dall’operaio 1, 2 e 3 rispettivamente, si può scrivere
il seguente modello.
min 18x1 + 16x2 + 12x3
soggetto a
x1 + x 2 + x 3 ≤ 8
5x1 + 7x2 + 8x3 ≥ 25
9x1 + 6x2 + 4x3 ≥ 30
x1 , x2 , x3 ≥ 0.
6. La base {x14 , x24 , x43 } è ammissibile, con associati
x14 = 3
c̄12 = −6
x24 = x43 = 0
c̄31 = 5
Entra in base x12 , con valore di flusso pari a 3, esce x14 . Per la nuova base
{x12 , x24 , x43 } si ottiene
x12 = x24 = 3
x43 = 0
c̄14 = 6
c̄31 = −1
dove si riconosce la condizione di illimitatezza (ciclo 1 → 2 → 4 → 3 → 1) per il
problema dato.
7. Dal primo vincolo si puó dedurre x1 = 0, x2 ≤ 2, x3 ≤ 2, e dal secondo — tenendo
conto che x1 = 0 — si ottiene x4 ≤ 1, x2 = 0. Avendo ricavato x1 = x2 = 0, l’unica
soluzione che soddisfa i vincoli é x1 = x2 = 0, x3 = 37 , x4 = 53 , e non é intera.
8. Per Sa , Sott si puó avere:
• Sa = ∅ e quindi Sott = ∅;
COMPITO DI RICERCA OPERATIVA
5
• Sa 6= ∅ e Sott = ∅ (problema illimitato);
• Sa 6= ∅ e Sott 6= ∅ (ottimo finito, eventualmente con infinite soluzioni
ottime).
Per esempi grafici, si consideri (a parte il caso Sa = ∅) quelli relativi alla regione di
ammissibilità
Sa = {x1 + x2 ≥ 1, x1 , x2 ≥ 0}
con funzioni obiettivo come z = 2x1 (problema illimitato), z = −x1 (unico ottimo
finito), z = −x1 − x2 (infinite soluzioni ottime). Situazioni analoghe si verificano
per Za , Zott .