Compito di Ricerca Operativa del 27/06/2002
Esercizio 1 (12 punti)
Sia dato il seguente problema di PLI
max 3x1+ x2 x1+ x2≥ 3/2 x1+ x2≤ 7/2
x1≤ 5/2 x1, x2≥ 0, x1, x2∈ I
1) Si risolva graficamente il rilassamento lineare di tale problema ed il problema stesso.
2) Si determini una soluzione ottima del problema di PLI tramite l’algoritmo di Gomory rappresentando graficamente i vincoli via via ottenuti. Oltre a quella trovata esistono altre soluzioni ottime?
3) Si scriva il primo taglio generato dall’algoritmo di Dantzig. Sulla base del risultato ottenuto e aiutandosi con la risoluzione grafica, ´e possibile affermare che l’algoritmo di Dantzig introdurr´a per questo esempio un numero di tagli superiore rispetto all’algoritmo di Gomory?
4) ´E possibile modificare la funzione obiettivo in modo tale da rendere l’insieme delle soluzioni ottime del problema di PLI Zott = ∅? ´E possibile eliminare un solo vincolo in modo tale da rendere sempre Zott = ∅? E aggiungere un solo vincolo in modo da mantenere la regione ammissibile del rilassamento lineare non vuota ma Zott=∅? In caso di risposta affermativa mostrare come.
Esercizio 2 (11 punti)
Sia data la rete in Figura 1 con
b1= 5 b2= 1 b3= 4 b4=−10 b5=−1 b6= 1 e
c12= 1 c14=−10 c23= 2 c34= 3 c35= 8 c56= 1 c64= 5
1) Si formuli il problema di flusso a costo minimo su tale rete come problema di PLI con un numero minimo di vincoli e
2
1
3
4
5
6
Figure 1:
si scriva la matrice dei vincoli.
2) Siano dati i seguenti insiemi di 3 archi
(2, 3) (3, 5) (5, 6) (6, 4) (3, 4) (1, 2) (1, 4) (3, 4) (5, 6) (6, 4) (1, 2) (2, 3) (3, 4) (3, 5) (6, 4)
Per ciascuno dei tre insiemi stabilire se rappresenta o meno una base e, in caso di risposta affermativa, se sia ammissibile.
3) Usando la risposta del punto precedente si risolva il problema tramite il simplesso su rete.
1
4) Si scriva il duale del rilassamento lineare del problema e se ne determini una soluzione.
5) `E possibile modificare un singolo valore bi in modo tale che il problema non ammetta soluzioni ammissibili? Ed `e possibile modificare il verso di un singolo arco in modo da rendere il problema illimitato? Motivare le risposte.
Esercizio 3 (6 punti)
Sia dato il grafo G = (V, A) rappresentato in Figura 2.
HH HH
HH
c c
c c
c c
c
a
b
c
d
e f g
h
Figure 2:
1) Verificare, applicando la procedura vista a lezione, che ´e bipartito ed individuare le due classi di bipartizione.
2) Dimostrare che non contiene come sottografi una K5 e una K33. 3) Trovare, con uno dei metodi visti a lezione, una base di cicli del grafo.
Esercizio 4 (6 punti)
Si risponda alle seguenti domande.
1) Siano xi (i = 1, 2, 3) tre variabili binarie. Si esprima con un singolo vincolo il fatto che x1 = 1 e x2 = 1 implicano x3= 1.
2) Per ognuna delle seguenti affermazioni dire se `e vera oppure falsa motivando la risposta 1. un grafo bipartito `e certamente connesso
2. un grafo connesso `e certamente bipartito
3. un grafo bipartito e connesso `e certamente planare 3) Si consideri il seguente problema di PL
min x1− x2
x1+ x2≤ 4 x1≥ 3 x1, x2≥ 0
Si pu`o verificare che il punto (3, 0) ´e soluzione ottima, unica e non degenere, di tale problema. Qual `e il valore della variabile u1associata al vincolo x1+ x2≤ 4 nella soluzione ottima del duale?
2
