RICERCA OPERATIVA GRUPPO A soluzione della prova scritta del 12 Dicembre 2005
1. Sia U un insieme finito di interi e ℑ la famiglia di tutti i sottoinsiemi X di U tale che
Σ z < b
z∈X
per un certo b∈ IR fissato. Indicare quale tra le seguenti affermazioni è vera:
(A) ℑ non è subclusiva e non gode della proprietà di scambio (B) ℑ gode della proprietà di scambio
(C) ℑ è subclusiva.
2. Scrivere il duale del problema
min x1 – x3 + 2x4 max –y1 – y2 + 2y3
x1 + x4 < 1 – y1 < 1
2x3 + x4 = – x2 – 1 y2 + y3 < 0
x2 – x3 > 2 2y2 – y3 < –1
x1, x2, x3 > 0 –y1 + y2 = 2 y1, y3 > 0
3. Applicando il metodo di Fourier-Motzkin, si determini, se esiste, il valore ottimo di z per il problema
max z = 2x1 + x2 – x3 + x4
–x1 – x2 – x4 > – 2 x2 + x3 + x4 < 2 – x2 + x3 < 1 –x1 – x3 > –2 – x3 < 3
xi ∈ IR, i = 1, …, 4
3 0 1 0 0 0
2 0 1 0 1 0
1 0 1 1 0 0
2 1 1 1 0 0
2 1 0 1 1 0
0 1 1 1 2 1
0 1 1 1 2 1
4 3 2 1
−
−
−
−
−
−
−
x ≤ x x x z
3 0 1 0 0 0
2 0 1 0 1 0
1 0 1 1 0 0
2 0 2 0 2 1
2 0 1 0 1 1
0 0 0 0 0 0
4 3 2 1
−
−
−
−
x ≤ x x x z
3 1 0 0 0
1 1 1 0 0
6 4 0 0 1
4 2 0 0 1
3 2 1
−
− x ≤ x x z
4 0 1 0
18 0 0 1
10 0 0 1
3 2
− x ≤ x z
Il valore della soluzione ottima è 10.
4. Sia (P) un problema di PL e Q il poliedro che rappresenta la regione ammissibile. Dire quale delle seguenti affermazioni è vera:
(A) una soluzione ottima di (P) può trovarsi solo su un vertice di Q
(B) una soluzione ottima di (P) può trovarsi solo su uno degli iperpiani che definiscono Q (C) una soluzione ottima di (P) può non trovarsi su una faccia di Q
5. Alta val di Susa
Un treno ad alta velocità, partito all’istante t0, percorre un tratto lungo s1 = 120 km a velocità v1, al termine del quale giunge in stazione. Un secondo treno parte anch’esso all’istante t0 e dopo un tratto lungo s2 = 80 km percorso a velocità v2 giunge nella medesima stazione. Sulla tratta percorsa dal primo treno la massima velocità consentita è di 240 km/h, su quella percorsa dal secondo (che è diversa da quella percorsa dal primo) è invece di 330 km/h. Secondo l’orario, il secondo treno dovrà giungere in stazione contemporaneamente al primo. Indagini di mercato fanno ritenere che la clientela del primo treno, composta di manager e veline, apprezzi molto di più la velocità della clientela del secondo treno, composta di massaie e pendolari. Facendo infatti un calcolo di costi e benefici si è scoperto che aumentare di 1 km/h la velocità del primo treno comporta un vantaggio quantificabile in 15 centesimi di euro, mentre aumentare della stessa quantità la velocità del secondo non comporta alcun vantaggio, bensì un costo secco di 12 centesimi di euro per maggiori consumi. Usando il metodo del simplesso si scelgano le velocità v1 e v2 in modo che il costo complessivo sia minimizzato nel rispetto dei vincoli descritti.
I due treni partono nel medesimo istante t0, e il treno k giunge in stazione all’istante t0 + sk/vk. L’orario richiede che si abbia
t0 + s1/v1 = t0 + s2/v2 cioè s1v2 – s2v1 = 0 Inoltre deve aversi
v1 < 240 v2 < 330 L’obiettivo si scrive
min – 15v1 + 12v2
Passando a risolvere con il metodo del simplesso, scriviamo tabella iniziale
v1 v2 w1 w2
–15 12
–80 120 0
1 1 240
1 1 330
Per rendere canonica questa tabella risolviamo il problema ausiliario:
v1 v2 w0 w1 w2
1
–80 120 1 0
1 1 240
1 1 330
Rendiamo canonica anche questa tabella sottraendo la riga 1 alla riga 0:
v1 v2 w0 w1 w2
80 –120
–80 120 1 0
1 1 240
1 1 330
Pur avendo coefficienti della riga 0 non positivi, la tabella è ottima in quanto in corrispondenza alla base trovata (che è degenere) la funzione obiettivo vale 0. Tuttavia per ottenere una prima base del problema di partenza occorre far uscire la variabile ausiliaria w0 dalla base; eseguiamo quindi un’operazione di pivot in riga 1 e colonna 2:
v1 v2 w0 w1 w2
1
–2/3 1 1/120 0
1 1 240
2/3 – 1/120 1 330
Trasformiamo ora la tabella eliminando la colonna w0 e sostituendo alla riga 0 i coefficienti della funzione obiettivo originale:
v1 v2 w1 w2
–15 12
–2/3 1 0
1 1 240
2/3 1 330
Rendiamo canonica anche questa tabella sommando alla riga 0 la riga 1 moltiplicata per –12
v1 v2 w1 w2
–7
–2/3 1 0
1 1 240
2/3 1 330
Si può ottenere una base non peggiore di quella corrente eseguendo un’operazione di pivot in riga 2 e colonna 1:
v1 v2 w1 w2
7 1.680
1 2/3 160
1 1 240
–2/3 1 170
Questa base è evidentemente ottima. Il primo treno dovrà muoversi a v1*
= 240 km/h, il secondo a v2*
= 160 km/h.
6. Blocchi
Dato un insieme A = {a1, …, an} di interi positivi, definiamo blocco un B ⊆ A i cui elementi possono essere divisi in due sottoinsiemi, B1 e B2, in modo che la somma degli elementi in B1 è uguale alla somma di quelli in B2. Ad esempio, se A = {2, 5, 5, 7, 13, 14, 18}, B = {5, 5} costituisce un blocco. Vogliamo trovare il massimo numero di blocchi di quest’insieme A che contengano al più 3 elementi e, presi a due a due, non abbiano elementi in comune. Formulare il problema come massima clique su un grafo opportuno (e disegnarlo qui sotto).
Nell’insieme A = {a1, …, a7} sono presenti i seguenti blocchi con meno di 4 elementi: {a2, a3}, {a1, a2, a4}, {a1, a3, a4}, {a2, a5, a7}, {a3, a5, a7}. Il grafo dovrà avere un nodo per ognuno di questi blocchi, e un arco tra due nodi se e solo se i due blocchi hanno intersezione vuota:
a1, a2
a1, a2, a4
a1, a3, a4
a2, a5, a7
a3, a5, a7
