Compito di Ricerca Operativa del 19/09/2002
Esercizio 1 (11 punti)
Sia dato il seguente problema di PL
max 3x1+ 2x2+ 4x3
x1+ x2− 2x3= 2 x1+ x2+ 2x3= 4
x1+ x2≤ 3 x1− x3≤ 2 x1, x2, x3≥ 0
1) Per ciascuno dei seguenti tre punti (1, 2, 1/2), (0, 3, 1/2) e (3, 0, 1/2) si stabilisca se ´e un vertice della regione ammissibile Sa oppure no.
2) Sulla base della risposta al primo quesito e sulla base dei vincoli del problema, si dica qual ´e la forma di Sa. Pu´o succedere che Sott=∅? (Sott denota l’insieme delle soluzioni ottime) Quali delle seguenti affermazioni sono vere:
a) Sa non contiene vertici.
b) Sa contiene un solo vertice.
c) Sa contiene almeno due vertici.
d) Sa contiene uno spigolo illimitato.
3) Si risolva il problema di PL con l’algoritmo del simplesso.
4) Si scriva il duale del problema di PL. Possiamo affermare, senza risolverlo, che la soluzione ottima del duale soddisfa come uguaglianza il vincolo del duale associato alla variabile x1 del duale? (Motivare la risposta)
Esercizio 2 (11 punti)
Sia data la rete in Figura 1 con
b1= 4 b2=−7 b3= 1 b4= 2 e
c12=−1 c13= 1 c23= 2 c34=−3 c41= 1 c42= 4
1) Si formuli il problema di flusso a costo minimo su tale rete come problema di PLI con un numero minimo di vincoli e si scriva la matrice dei vincoli.
2) Pu´o esistere una base ammissibile che contenga come unico arco incidente sul nodo 2 l’arco (2, 3)?
3) Siano dati i seguenti insiemi di 3 archi
(1, 2) (1, 3) (2, 3) (1, 2) (4, 2) (3, 4) (4, 1) (1, 3) (2, 3)
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.
5) Si scriva il duale del rilassamento lineare del problema. Che cosa si pu´o dire, ancor prima di risolverlo, sul problema duale?
Esercizio 3 (6 punti)
Sia dato il grafo G = (V, A) rappresentato in Figura 2.
1) Verificare, applicando la procedura vista a lezione se ´e bipartito o meno.
2) Dimostrare che il grafo non contiene una K5o una K3,3.
3) Determinare un albero di supporto del grafo e con questo trovare una base di cicli del grafo.
1
Z
Z Z
Z Z
Z Z
Z Z
Z Z
Z Z
Z
1 2
3 4
Figure 1:
J J
J J
J J
J J
J J
J J
a b c
d e f
g h i
Figure 2:
Esercizio 4 (6 punti)
Si risponda alle seguenti domande.
1) Un cliente ha a disposizione una quantit´a budget di soldi e deve scegliere quali prodotti acquistare in un certo insieme P RODOT T I, dove il costo del prodotto i ´e pari a costoi. Si introducano in AMPL tutte le componenti necessarie per poter esprimere il vincolo che il cliente non pu´o superare il budget a disposizione ed esprimere il vincolo stesso in AMPL.
2) Siano date le tre variabili binarie x1, x2, x3. Esprimere con un solo vincolo la seguente condizione: se x1= 0 e x3= 0, allora x2= 1.
3) Siano Sa e Sott rispettivamente la regione ammissibile e l’insieme di soluzioni ottime di un problema di PL. Quali tra le seguenti affermazioni sono sempre vere? MOTIVARE LE RISPOSTE.
1. Se Sa ´e un troncone, allora Sott=∅.
2. Se Sa ´e un troncone, allora Sott´e un insieme illimitato.
3. Se Sa ´e un poliedro convesso, Sott´e un insieme finito.
4. L’insieme Sott pu´o contenere un numero infinito di vertici ottimi.
2
