Compito di Ricerca Operativa del 11/07/2002
Esercizio 1 (11 punti)
Sia dato il seguente problema P di PL
min 4x1+ 2x2+ x3+ 6x4
x1+ x2+ x3+ x4≥ 2 2x1+ 3x2+ x3+ 4x4≥ 4
x1, x2, x3, x4≥ 0
1) Perch´e `e possibile affermare immediatamente che se esiste un vertice ottimo del problema, questo ha almeno due delle quattro variabili x1, x2, x3, x4 pari a 0?
2) Si scriva il duale D del problema P e lo si risolva graficamente.
3) Osservando il duale `e gi`a possibile affermare che nella soluzione ottima del primale si ha x1= 0?
4) Dopo aver trasformato il problema P in forma canonica, lo si risolva con l’algoritmo del simplesso.
Esercizio 2 (12 punti)
Sia data la rete in Figura 1 con
b1= 1 b2=−5 b3= 4 b4= 2 b5=−2 e
c15=−3 c21= 1 c32= 2 c34=−5 c41= 7 c45= 4 c52= 3 c53= 2
1) Si formuli il problema di flusso a costo minimo su tale rete come problema di PLI con un numero minimo di vincoli e
b b
b b
b
Z Z
Z Z
"
"
"
"
"
1 2
4 3
5
Figure 1:
si scriva la matrice dei vincoli.
2) L’arco (1, 5) fa certamente parte della base ottima e di ogni base ammissibile. Perch´e?
3) Siano dati i seguenti insiemi di 4 archi
(5, 3) (3, 4) (2, 1) (1, 5) (5, 3) (3, 2) (2, 1) (1, 5) (5, 3) (3, 2) (4, 1) (1, 5)
Per ciascuno dei tre insiemi stabilire se rappresenta o meno una base e, in caso di risposta affermativa, se sia ammissibile.
4) Usando la risposta del punto precedente si risolva il problema tramite il simplesso su rete. Possono esistere altre soluzioni ottime oltre a quella trovata?
5) `E possibile modificare il costo di un solo arco in modo tale da rendere il problema illimitato?
6) Si scriva il duale del rilassamento lineare del problema e se ne determini una soluzione.
1
Esercizio 3 (6 punti)
Sia dato il grafo G = (V, A) rappresentato in Figura 2.
1) Applicando la procedura vista a lezione, stabilire se il grafo `e bipartito oppure no.
2) Dimostrare che il grafo non contiene come sottografi una K5 o una K33. 3) Determinare una base di cicli del grafo con una delle procedure viste a lezione.
bb b
bb bb
b
%
%
%
%
% e
e e
e e
e
@
@
@
@
@
@
a b
c d e
f
g
h
i
Figure 2:
Esercizio 4 (6 punti)
Si risponda alle seguenti domande.
1) Sia dato un insieme di depositi DEP OSIT I e un insieme di negozi N EGOZI. Si associ:
• una variabile ad ogni deposito, che indica la quantit`a di prodotto inviata da quel deposito;
• una variabile ad ogni negozio, che indica la quantit`a di prodotto ricevuta da quel negozio.
Dopo aver dichiarato in AMPL gli opportuni insiemi e variabili si esprima, sempre in AMPL, il vincolo che la quantit`a totale di prodotto inviata dai depositi (ovvero la somma delle quantit`a inviate dai singoli depositi) deve essere pari alla quantit`a totale di prodotto ricevuta dai negozi (ovvero la somma delle quantit`a ricevute dai singoli negozi)
2) Mostrare un problema di PL il cui duale abbia soluzioni ottime multiple.
3) Dire tra le seguenti affermazioni quali sono vere e quali sono false motivando le risposte.
1. Un problema di PL pu`o avere un qualsiasi numero finito di soluzioni ottime.
2. Un problema di PLI pu`o avere un numero infinito di soluzioni ottime.
3. Un problema di PLI pu`o avere un qualsiasi numero finito di soluzioni ottime.
4. Un problema di PL pu`o avere un numero infinito di soluzioni ottime.
2
