Prova scritta di Ricerca Operativa Corso di Laurea in
Ingegneria Informatica e Automatica
19 febbraio 2013
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. Dire quali delle seguenti affermazioni sono corrette.
(a) L’insieme {(x, y) ∈ IR2 | y = 3x2− 2x + 4, con x ∈ IR} `e un insieme convesso.
(b) Dati x0∈ IRn e d ∈ IRn, l’insieme {x ∈ IRn | x = x0+ λd, con λ ≥ 0} `e un insieme convesso e limitato.
(c) Un insieme convesso limitato `e un politopo.
(d) L’unione di due insiemi convessi `e un insieme convesso.
2. Dire quali delle seguenti affermazioni sono corrette.
(a) Un problema di Programmazione Lineare che ha regione ammissibile non vuota, ammette sempre soluzione ottima.
(b) Esistono problemi di Programmazione Lineare che ammettono esattamente due soluzioni ottime (distinte).
(c) Un problema di Programmazione Lineare pu`o ammettere infinite soluzioni ottime.
(d) Esistono problemi di Programmazione Lineare che ammettono un’unica soluzione ottima.
3. Dato un problema di Programmazione Lineare in forma standard, dire quali delle seguenti affermazioni sono corrette.
(a) Ad ogni Soluzione di Base Ammissibile corrisponde una e una sola matrice di base.
(b) Ad ogni Soluzione di Base Ammissibile corrisponde un vertice del poliedro definito dall’insieme ammissibile del problema di Programmazione Lineare e viceversa.
(c) Una matrice di base B di dice base ammissibile se `e non singolare.
(d) Poich´e il problema `e in forma standard, il rango della matrice dei vincoli `e sempre massimo.
4. In un’iterazione della fase II del metodo del simplesso (applicato ad un problema di minimiz- zazione) si ha
xB= (x5, x7, x6, x1)T, xN = (x8, x2, x3, x4)T,
γ =
2
−1 0 0
, B−1b =
1 2 2 1
.
Dire quali delle seguenti affermazioni sono corrette.
(a) La variabile x2 `e candidata ad entrare in base.
(b) La Soluzione di Base Ammissibile corrente non soddisfa il criterio di ottimalit`a.
(c) La Soluzione di Base Ammissibile corrente `e non degenere.
(d) Poich´e γ ha una componente positiva, il criterio di illimitatezza `e sicuramente non veri- ficato.
5. Dire quali delle seguenti affermazioni sono corrette.
(a) Il problema artificiale (ausiliario) che si risolve nella Fase 1 del metodo del simplesso `e illimitato se e solo se il problema originario `e inammissibile.
2
(b) Il problema originario `e ammissibile se e solo se il problema artificiale (ausiliario) che si risolve nella Fase 1 del metodo del simplesso ammette soluzione ottima.
(c) Il problema artificiale (ausiliario) che si risolve nella Fase 1 del metodo del simplesso ha un numero di variabili minore o uguale al numero delle variabili presenti nel problema originale.
(d) Condizione necessaria e sufficiente affinch´e il problema originario sia ammissibile `e che nessuna variabile artificiale sia rimasta in base alla fine della Fase 1.
6. Al termine della fase I del metodo del simplesso applicato alla soluzione di un problema di PL risulta xB = (α1, x1, α3, x3)T, xN = (x4, x2, α2, α4)T,
B−1N =
2 0 −5 7
0 0 0 −1
8 5 9 15
0 0 8 10
, B−1b =
0 1 0 1
.
Dire quali delle seguenti affermazioni sono corrette.
(a) Il 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, x1, x2, x3)T.
(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)T.
(d) Il problema originario `e inammissibile.
7. Si consideri il seguente poliedro definito da
βx1+ x2+ 2x4 ≤ 4 x1+ 3x3 ≤ 4 x2+ x4 ≤ 2 x1 ≥ 0 x4 ≥ 0 Dire quali delle seguenti affermazioni sono corrette.
(a) Per β = 1 il punto (1, 1, 1, 1)T `e vertice del poliedro.
(b) Il punto (0, 1, − 1, 1)T appartiene al poliedro per ogni valore di β.
(c) Esistono valori di β per cui l’origine degli assi (0, 0, 0, 0)T `e vertice del poliedro.
(d) Il poliedro non ammette vertici.
8. Si consideri il poliedro descritto dal seguente sistema x1+ x2 = 3 x1+ x2+ 2x3 = 5 x2+ x4 = 1
xi≥ 0, i = 1, . . . , 4 Dire quali delle seguenti affermazioni sono corrette.
3
(a) Il punto (2, 1, 1, 0)T `e vertice del poliedro.
(b) Il punto (2, 1, 1, 1)T `e vertice del poliedro.
(c) Il punto (1, 2, 1, − 1)T appartiene al poliedro.
(d) Poich´e il numero dei vincoli di uguaglianza `e minore del numero delle variabili, il poliedro non ammette vertici.
9. Sia dato il seguente problema di Programmazione Lineare:
max cTx Ax ≥ b Dire quali delle seguenti affermazioni sono corrette.
(a) Il suo duale `e
max bTu ATu = −c u ≥ 0 (b) Il suo duale `e
min bTu ATu ≤ c u ≥ 0 (c) Il suo duale `e
min bTu ATu = c
(d) Il problema duale del problema dato ha variabili vincolate in segno.
10. Dato il seguente problema di Programmazione Lineare min (2, 1, 1, 1, 0, 2) x
0 2 1 3 1 2
1 1 1 1 0 2
x =1 0
x ∈ IR6, x ≥ 0, dire quali delle seguenti affermazioni sono corrette.
(a) La soluzione di base associata alla base formata dalla terza e dalla quinta colonna `e soluzione di base ammissibile.
(b) La soluzione di base associata alla base formata dalla terza e dalla quinta colonna `e soluzione di base ottima.
(c) Il problema `e in forma canonica rispetto alla terza e prima variabile.
(d) La soluzione di base associata alla base formata dalla quinta e dalla sesta colonna `e soluzione di base ammissibile.
4
