RICERCA OPERATIVA GRUPPO A prova scritta del 21 luglio 2011
1. Capace di tutto
Per essere eletto, il sindaco di Parentopoli ha promesso di realizzare un sistema di condutture che porti grappa alle case del paese. Le elezioni sono andate bene, e una promessa è debito: così, in via sperimentale, il sindaco dispone la costruzione di un sistema che va dall’enoteca di suo nipote (0) alle case del segretario comunale (1), del farmacista (2) e del capo dei vigili del fuoco (3). Come traccia per lo sviluppo della rete si ha il grafo di figura, e si deve decidere lungo quali archi posare i tubi. Un tubo costa 1 tallero per ogni metro di lunghezza e per ogni litro/ora di portata: quindi ad esempio 3 metri di tubo da 2 litri/ora costano 6 talleri.
Progettate una rete di costo minimo capace di spedire 100 litri/ora al segretario, 50 litri/ora al farmacista e 150 litri/ora al capo dei vigili, tenendo conto che le distanze tra i luoghi sono quelle riportate sugli archi. Mostrate poi come sia possibile trovare la rete ottima con il simplesso su reti.
Iniziamo con l’indicare con qij la capacità del tubo che va dal nodo i al nodo j della rete, con xij il flusso che lo attraversa e con di la domanda del nodo i. Si ha d0 = –300, d1 = 100, d2 = 50, d3 = 150. I vincoli del problema sono:
– x01 – x02 = –300 x01 – x12 – x13 = 100 x02 + x12 – x23 = 50 x23 + x33 = 150 per la conservazione del flusso di grappa, e 0 < xij < qij per ij = 01, 02, 12, 13, 23. I costi per unità di capacità sono gli stessi per tutti i tubi, quindi il costo finale del tratto di tubo da i a j dipenderà linearmente dalla sua capacità e dalla distanza tra i e j. L’obiettivo si scrive dunque:
min 6q01 + 8q02 +7q12 +5q13 +3q23
Si tratta di un problema di programmazione lineare che può essere risolto con il simplesso su reti osservando che in una soluzione ottima si avrà certamente xij* = qij* per ogni arco ij: infatti siccome i costi sono positivi se in una soluzione ottima si avesse xab* < qab* per qualche arco ab, la si potrebbe migliorare riducendo qab fino a farlo diventare uguale a xab*. Di conseguenza le variabili qij possono eliminarsi insieme ai vincoli di capacità, e l’obiettivo riscriversi
min 6x01 + 8x02 +7x12 +5x13 +3x23
E’ facile comprendere che risolvere il problema equivale a determinare l’albero dei percorsi minimi dal nodo 0 a tutti gli altri nodi del grafo.
2. Simplesso espresso
Il problema di programmazione lineare min z(x) = 2x1 + 3x2 + 6x3 + x4 3x1 – 2x2 + x3 > 2
4x1 + 6x2 – 5x4 > 6 x1, x2, x3, x4 > 0
ammette soluzione ottima x* di valore z*. Si vuole sapere se dopo l’aggiunta del vincolo x1 + 3x2 + x4 > 4 si avrà un peggioramento della soluzione ottima, o se invece il suo valore resterà inalterato.
Si può rispondere più agevolmente alla domanda facendo ricorso alla teoria della dualità. Infatti siccome il problema ammette ottimo finito, anche il suo duale
max 2y1 + 6y2
3y1 + 4y2 < 2 –2y1 + 6y2 < 3 y1 < 6 – 5y2 < 1 y1, y2 > 0
ammette ottimo finito di valore z*. Il calcolo di z* attraverso la soluzione di questo problema è più semplice, perché è immediato determinare la tabella canonica:
1
0
2
3
6 8
7
5 3
y1 y2 u1 u2 u3 u4
2 6 0 0 0 0 0
3 4 1 0 0 0 2
–2 6 0 1 0 0 3
1 0 0 0 1 0 6
0 –5 0 0 0 1 1
Con un’operazione di pivot in colonna 2 otteniamo subito la tabella ottima
y1 y2 u1 u2 u3 u4
–5/2 0 –3/2 0 0 0 –3
3/4 1 1/4 0 0 0 ½
–13/2 0 –3/2 1 0 0 0
1 0 0 0 1 0 6
15/4 0 5/4 0 0 1 7/2
dalla quale deduciamo z* = 3. Consideriamo ora l’insieme S delle x ottime per il primale, cioè delle soluzioni ammissibili per le quali si ha z(x) = 3, e osserviamo che per xi > 0 (i = 1, …, 4) il primo membro del vincolo aggiunto non supera mai la funzione obiettivo. Quindi
x1 + 3x3 + x4 < 2x1 + 3x2 +6x3 + x4 = 3 per x ∈ S
La disuguaglianza scritta implica che la condizione x1 + 3x3 + x4 > 4 è incompatibile con l’appartenenza a S, quindi non esiste alcuna soluzione x di valore 3 che soddisfi il vincolo aggiunto.
3. L’intersezione fa la debolezza
Siano dati i due poliedri P1) 2x1 + 3x2 + 6x3 + x4 > 6 P2) 4x1 + 2x2 – x4 > 3 2x2 – x3 + x4 > 1 x1 – 2x2 – 5x4 > 5 Applicate il metodo di Fourier-Motzkin e stabilite se P1 ∩ P2 è vuoto oppure no.
Il poliedro P1 ∩ P2 è formato dalle x∈IR4 che soddisfano il sistema 2x1 + 3x2 + 6x3 + x4 > 6
2x2 – x3 + x4 > 1 4x1 + 2x2 – x4 > 3 x1 – 2x2 – 5x4 > 5
E’ immediato riconoscere che il poliedro ottenuto proiettando P1 ∩ P2 nello spazio di x2, x3, x4 è costituito dalle x∈IR3 che soddisfano 2x2 – x3 + x4 > 1, e questa disequazione ammette banalmente soluzione. Dunque P1 ∩ P2 non è vuoto.
4. Dire quale delle seguenti affermazioni è vera e quale è falsa V F
a. Se x∈IRn è combinazione convessa di u, v, w∈IRn allora è combinazione affine di u, v∈IRn b. Se x∈IRn è combinazione affine di u, v∈IRn allora è combinazione affine di u, v, w∈IRn c. Se x∈IRn è combinazione convessa di u, v∈IRn allora è combinazione conica di u, v, w∈IRn 5. Il duale del problema max 7x1 + 6x2 – x3 può scriversi min 5y1 + 6y2 + 5
4x2 – 2x3 < 6 – 2y1 + 4y2 = 4 7x1 – 2x2 + x3 = 5 y1 – 2y2 > –2 x1, x3 > 0 y1, y2 > 0 Vero o falso? Perché?
Vero. Il duale del problema dato si scrive min 6z1 + 5z2
7z2 > 7 4z1 – 2z2 = 6 –2z1 + z2 > –1 z1 > 0
Osserviamo che il primo vincolo si può riscrivere z2 > 1. Eseguendo il cambio di variabile y1 = z2 – 1, cioè z2 = y1 + 1, e z1 = y2 si ottiene il problema del testo, del tutto equivalente al duale scritto.
RICERCA OPERATIVA GRUPPO B prova scritta del 21 luglio 2011
1. Capace di tutto
Per essere eletto, il sindaco di Parentopoli ha promesso di realizzare un sistema di condutture che porti grappa alle case del paese. Le elezioni sono andate bene, e una promessa è debito: così, in via sperimentale, il sindaco dispone la costruzione di un sistema che va dall’enoteca di suo nipote (0) alle case del segretario comunale (1), del farmacista (2) e del capo dei vigili del fuoco (3). Come traccia per lo sviluppo della rete si ha il grafo di figura, e si deve decidere lungo quali archi posare i tubi. Un tubo costa 1 tallero per ogni metro di lunghezza e per ogni litro/ora di portata: quindi ad esempio 3 metri di tubo da 2 litri/ora costano 6 talleri.
Progettate una rete di costo minimo capace di spedire 80 litri/ora al segretario, 70 litri/ora al farmacista e 90 litri/ora al capo dei vigili, tenendo conto che le distanze tra i luoghi sono quelle riportate sugli archi.
Mostrate poi come sia possibile trovare la rete ottima con il simplesso su reti.
Vedi soluzione gruppo A, cambia solo il vettore di domanda.
2. Simplesso espresso
Il problema di programmazione lineare min z(x) = 2x1 + 3x2 + 6x3 + x4 3x1 – 2x2 + x3 > 2
4x1 + 6x2 – 5x4 > 6 x1, x2, x3, x4 > 0
ammette soluzione ottima x* di valore z*. Si vuole sapere se dopo l’aggiunta del vincolo 7x1 + 3x2 + 6x3
+ 2x4 > 3 si avrà un peggioramento della soluzione ottima, o se invece il suo valore resterà inalterato.
Vedi soluzione gruppo A, con la differenza che in questo caso il primo membro della disuguaglianza aggiunta è, per xi > 0, sempre > della funzione obiettivo. Visto che il termine noto è proprio pari a z*, la disuguaglianza è verificata da tutte le soluzioni ottime del problema.
3. L’unione fa la forza
Siano dati i due poliedri P1) 2x1 + 2x2 < 5 P2) 2x1 + 3x2 + 6x3 + x4 > 6 x1 – x2 < 1 2x2 – x3 + x4 < 1 2x1 – 2x2 > 5
x1 + x2 > 4
Applicate il metodo di Fourier-Motzkin e stabilite se P1 ∪ P2 è vuoto oppure no.
Indipendentemente dal fatto se P1 sia vuoto o no, è facile riconoscere che P2 non è vuoto: infatti la sua proiezione nello spazio delle variabili x1, x2, x4 è data dall’intero IR3. Quindi neppure P1 ∪ P2 è vuoto.
4. Dire quale delle seguenti affermazioni è vera e quale è falsa V F
a. Se x∈IRn è combinazione convessa di u, v∈IRn allora è combinazione affine di u, v, w∈IRn b. Se x∈IRn è combinazione affine di u, v∈IRn allora è combinazione convessa di u, v, w∈IRn c. Se x∈IRn è combinazione convessa di u, v, w∈IRn allora è combinazione conica di u, v∈IRn 5. Il duale del problema max – 2x1 + 3x2 – x3 può scriversi min 4y1 + 8y2 – 16
– 2x2 + x3 < 4 – 2y1 + 4y2 > 11 x1 + 4x2 – x3 = 8 y1 + y2 = 1 x1, x2 > 0 y1, y2 > 0 Vero o falso? Perché?
1
0
2
3
6 8
7
5 3
Vero. Il duale del problema dato si scrive min 4z1 + 8z2
z2 > –2 – 2z1 + 4z2 > 3 z1 –z2 = –1 z1 > 0
Eseguendo il cambio di variabile y2 = z2 + 1, cioè z2 = y2 – 2, e z1 = y1 si ottiene il problema del testo, del tutto equivalente al duale scritto.
