Prova scritta di Ricerca Operativa Corso di Laurea in
Ingegneria Informatica e Automatica
12 aprile 2012
Istruzioni
• Usate i fogli bianchi allegati per calcoli, ragionamenti e quanto altro reputiate necessario fare per rispondere alle 10 domande seguenti.
• Per ciascuna delle 10 domande indicare in corrispondenza di ciascuna delle affermazioni a), b), c) e d) se essa `e VERA o FALSA, apponendo un segno sul rettangolo VERO o sul rettangolo
FALSO sul foglio risposte.
• Ricordatevi di scrivere su tale foglio risposte tutte le informazioni richieste ed in particolare il vostro nome e cognome (i fogli senza nome e cognome saranno cestinati e dovrete ripetere l’esame in un’altra sessione).
• Avete un’ora esatta di tempo per svolgere gli esercizi. Al termine del tempo dovete consegnare il solo foglio risposte (potete tenere il testo delle domande e i fogli bianchi).
• Ricordatevi di segnare esattamente sui fogli che rimarranno a voi le risposte che avete dato in modo da potervi autovalutare una volta che vi verr`a fornita la soluzione.
• Scaduta l’ora rimanete seduti. Passeremo a raccogliere i fogli risposte. Chi non consegna immediatamente il foglio al nostro passaggio non avr`a altra possibilit`a di consegna e dovr`a ripetere l’esame in un altro appello.
• ATTENZIONE. Durante la prova di esame:
– Non `e possibile parlare, per nessuna ragione, con i vostri colleghi.
– Non `e possibile allontanarsi dall’aula.
– Non si possono usare telefoni cellulari
– Non si possono usare calcolatrici, palmari o simili – Non `e possibile usare dispense, libri o appunti.
Chi contravviene anche a una sola di queste regole dovr`a ripetere la prova di esame in altro appello.
Valutazione
• Per ogni affermazione VERO/FALSO correttamente individuata viene assegnato 1 punto
• Per ogni affermazione VERO/FALSO non risposta vengono assegnati 0 punti
• Per ogni affermazione VERO/FALSO NON correttamente individuata viene assegnato un punteggio negativo pari a -0.25 punti
Supera la prova chi totalizza un punteggio pari ad almeno 28 punti
1
1. (a) L’insieme {(x, y) ∈ <2 | y ≥ x2, y ≤ 4} `e un poliedro;
(b) i punti (−2, 4), (2, 4), (0, 0) sono tutti e soli i vertici dell’insieme {(x, y) ∈ <2 | y ≥ x2, y ≤ 4};
(c) l’intersezione di un poliedro e di un insieme convesso `e un insieme convesso, ma non necessariamente un poliedro;
(d) l’intersezione di due iperpiani `e un insieme convesso.
2. Sia dato il poliedro P = {x ∈ <n | Ax ≥ b} con A matrice m × n e b ∈ <m; siano aTi le righe di A e I(¯x) l’insieme dei vincoli attivi in ¯x.
(a) Un punto ¯x ∈ P `e vertice di P se il rango della matrice {aTi, i ∈ I(¯x)} `e pari a n;
(b) se m < n, allora P non ammette vertici;
(c) se il numero dei vincoli attivi in un punto ¯x `e minore di n, allora deve esistere d ∈ <n, d 6= 0 tale che aTi d = 0 per ogni i ∈ I(¯x);
(d) se ¯x `e vertice di P allora la matrice A non pu`o avere rango minore di n.
3. Sia dato un problema di PL
min cTx Ax ≥ b.
Allora
(a) Se l’insieme ammissibile `e non vuoto, allora comunque si sceglie M ∈ <, M > 0, allora
`e possibile trovare un punto x ammissibile tale che cTx ≤ −M ;
(b) il problema pu`o essere illimitato (inferiormente) se e solo se l’insieme ammissibile `e illimitato;
(c) se il problema non ammette soluzione ottima, allora l’insieme ammissibile pu`o essere vuoto oppure non vuoto;
(d) se la funzione obiettivo cTx viene sostituita da una funzione non lineare, il Teorema Fon- damentale continua a valere, ma la soluzione ottima pu`o non essere un vertice dell’insieme ammissibile.
4. Dato il poliedro definito dal sistema
x1− 2x2 ≤ 1 x1+ x3 ≤ 2 x2+ 2x3− x4 ≤ 3
x ≥ 0
(a) Il punto (1, 0, 1, 0)T `e un vertice del poliedro;
(b) Il punto (3, 1, 1, 0)T non appartiene al poliedro;
(c) Il punto (0, 0, 2, 1)T `e un vertice del poliedro;
(d) L’origine `e un vertice del poliedro.
5. Sia dato un problema di Programmazione Lineare e si consideri la Fase I nella quale si risolve il problema artificiale.
2
(a) L’applicazione della Fase II al problema articificiale porta sempre ad indentificare un punto di ottimo del problema artificiale;
(b) se non si pu`o applicare la Fase II al problema artificiale allora il problema originario non
`e ammissibile;
(c) se la matrice dei vincoli del problema originario ha rango massimo, allora non `e necessario effettuare la Fase I;
(d) se il problema artificiale ammette soluzione ottima allora il valore all’ottimo della fun- zione obiettivo `e zero.
6. Sia dato un problema di PL in forma standard, e sia B una base ammissibile e N la matrice delle colonne fuori base.
(a) Se qualche componente di B−1b `e negativa allora non `e soddisfatto il criterio di otti- malit`a;
(b) se risulta γi= 0 e (B−1N )i≤ 0, allora `e soddisfatto il criterio di illimitatezza;
(c) il vettore xB = B−1b `e univocamente determinato;
(d) si possono sempre scrivere i vincoli di uguaglianza del problema nella forma BxB+N xn= b.
7. Arrivati all’ottimo del problema artificiale che si risolve nella fase I del metodo del simplesso abbiamo che risulta xB= (x4, α2, α3, x2), xN = (x1, α1, x3, α4),
B−1b =
0 0 0 0
, B−1N =
5 13 1 1
0 5 −1 6
1 −4 2 4
0 5 0 9
Allora
(a) Poich´e il vettore B−1b `e tutto a componenti nulle, la matrice dei vincoli del problema originario ha un vincolo ridondante;
(b) una possibile base ammissibile per il problema originario dalla quale far partire la Fase II corrisponde ad avere variabili di base xB= (x4, x3, x1, x2);
(c) una possibile base ammissibile per il problema originario dalla quale far partire la Fase II corrisponde ad avere variabili di base xB= (x4, x1, x3, x2);
(d) se non si fosse a conoscenza di quali variabili sono in base (ovvero non fosse noto xB), sapendo che il vettore B−1b `e tutto a componenti nulle, si pu`o comunque dedurre che il problema originario `e ammissibile.
8. Ad una iterazione della fase II del metodo del simplesso si ha: xB= (x3, x5, x1)T, xN = (x2, x6, x4)T,
B−1N =
σ −1 0
3 0 −1
5 0 0
, B−1b =
σ 1 1
Se la funzione obiettivo (da minimizzare) `e f (x1, x2, x3, x4, x5, x6) = x3+ x6 allora
3
(a) se σ < 0, la SBA corrente soddisfa il criterio di ottimalit`a;
(b) per σ > 0 la variabile x6`e una variabile candidata ad entrare in base;
(c) non esistono valori di σ per il quali il criterio di illimitatezza `e soddisfatto;
(d) per σ > 0 allora x1`e una variabile candidata a uscire dalla base.
9. Sia dato il seguente poliedro
x1− x2 = 0 2x1+ τ x3 = 2 x1+ x3+ x4 = 1
x ≥ 0
(a) il punto (1, 1, 0, 0)T `e un vertice del poliedro per ogni valore di τ ; (b) esistono valori di τ per i quali il punto (1, 1, 1, − 1)T `e una SBA;
(c) per τ = 2 il punto (0, 0, 1, 0)T `e una SBA;
(d) per τ = 0 l’origine `e un vertice del poliedro.
10. Sia dato il seguente problema di Programmazione Lineare:
min cTx Ax = 0 x ≥ 0 (a) Il suo duale `e
max cTu ATu ≤ c
(b) un problema di PL e il suo duale possono essere entrambi inammissibili;
(c) il numero delle variabili di un problema duale `e pari al numero dei vincoli del problema primale;
(d) dati due punti ¯x ammissibile per il primale e ¯u ammissibile per il duale. Se il valore della funzione obiettivo del problema primale calcolata in ¯x coincide con il valore della funzione obiettivo del problema duale calcolata in ¯u, allora i due punti sono soluzioni ottime per i rispettivi problemi.
4