Prova scritta di Ricerca Operativa Corso di Laurea in
Ingegneria Informatica e Automatica
30 gennaio 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’intersezione di due politopi `e un insieme convesso
(b) Un politopo non contiene rette, ma pu`o contenere semirette (c) Se un poliedro contiene semirette, allora pu`o contenere vertici
(d) Il numero dei vertici di un poliedro di <nnon pu`o superare n poich´e il massimo numero di vettori linearmente indipendenti che si possono trovare in <n `e proprio pari ad n.
2. Sia dato l’insieme di <n: 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) P `e un poliedro se e solo se la matrice A ha rango massimo
(b) Se il rango della matrice {aTi, i ∈ I(¯x)} `e pari a m allora ¯x ∈ P `e un vertice di P (c) L’insieme P ∩ {x ∈ <n | x ≥ 0} sicuramente non contiene rette
(d) L’insieme P ∩ {x ∈ <n | Pn
i=1x2i} `e un poliedro.
3. Sia dato un problema di PL
min cTx Ax = b x ≥ 0.
Allora
(a) In un punto di ottimo del problema sono attivi e linearmente indipendenti almeno n vincoli
(b) Il problema ammette sempre una soluzione ammissibile
(c) Un punto ˆx ammissibile per il problema `e vertice se e solo se le colonne della matrice A corrispondenti alle componenti positive di ˆx sono linearmente indipendenti
(d) Poich´e il problema `e in forma standard, si pu`o sempre applicare al problema direttamente la Fase II del metodo del simplesso.
4. Dato il poliedro definito dal sistema
x2+ x3 ≤ 2 x1− x2+ 2x4 ≤ 5 x2− 3x4 ≤ 0
x ≥ 0
(a) Il punto (0, 1, 1, 0)T `e un vertice del poliedro;
(b) Il punto (0, 1/2, 3/2, 0)T non appartiene al poliedro;
(c) Il punto (0, 0, 2, 0)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.
(a) Il problema artificiale, poich´e `e ammissibile e non `e illimitato inferiormente, ammette sempre un punto di ottimo in cui la funzione obiettivo vale zero
2
(b) Se alla fine della Fase I tutte le variabili artificiali sono fuori base, allora il problema originario `e ammissibile
(c) Se il problema originario `e in forma canonica, allora non `e necessario effettuare la Fase I (d) La Fase I permette di determinare se la matrice del problema originario ha rango mas-
simo.
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 la matrice B−1N ha una riga con tutti elementi strettamente positivi, allora il criterio di illimitatezza non `e soddisfatto
(b) Se la matrice B−1N ha una colonna con tutti elementi negativi, allora il criterio di illimitatezza `e soddisfatto
(c) B ha rango massimo
(d) Se γ = 0, allora non si pu`o dire nulla circa l’ottimalit`a della soluzione.
7. Arrivati all’ottimo del problema artificiale che si risolve nella fase I del metodo del simplesso abbiamo che risulta xB= (α1, x3, α3, x1), xN = (x2, α2, α4, x4),
B−1b =
0 1 0 1
, B−1N =
1 1 2 0
5 3 4 6
0 5 6 0
9 7 8 10
Allora
(a) La matrice dei vincoli di uguaglianza del problema originario ha rango massimo (b) una possibile base ammissibile per il problema originario dalla quale far partire la Fase II
corrisponde ad avere variabili di base xB= (x2, x3, x1);
(c) Il problema originaio `e inammissibile
(d) una possibile base ammissibile per il problema originario dalla quale far partire la Fase II corrisponde ad avere variabili di base xB= (x2, x3, x4, x1);
8. Ad una iterazione della Fase II del metodo del simplesso si ha: xB= (x3, x2, x5)T, xN = (x1, x6, x4)T,
B−1N =
−1 β −3
5 3 0
1 −1 0
, B−1b =
0 β 1
Se la funzione obiettivo (da minimizzare) `e f (x1, x2, x3, x4, x5, x6) = x1+ x2 allora (a) Se β < 1 allora `e soddisfatto il criterio di ottimalit`a
(b) Se β > 1 l’unica variabile candidata ad entrare in base `e x6
(c) Esistono valori di β per i quali `e soddisfatto il criterio di ottimalit`a (d) Se β > 1 allora l’unica variabile candidata ad uscire dalla base `e x5.
3
9. Sia dato il seguente poliedro
x1− x3 = 1 3x2+ σx4 = 4 x1+ x2+ x4 = 4
x ≥ 0
(a) il punto (2, 1, 1, 1)T non `e un vertice del poliedro per nessun valore di σ;
(b) esistono valori di σ per i quali l’origine `e vertice del poliedro (c) per σ = 4 il punto (3, 0, 2, 1)T `e una SBA;
(d) per σ = 1/3 il punto (0, 1, − 1, 3)T `e un vertice del poliedro.
10. Sia dato il seguente problema di Programmazione Lineare:
min cTx Ax ≤ b x ≥ 0 (a) Il suo duale `e
max −bTu ATu ≥ −c u ≥ 0
(b) un problema di PL e il suo duale non possono essere entrambi illimitati;
(c) il problema primale ammette almeno una soluzione ammissibile se e solo se esiste soluzione ottima per il suo duale
(d) date ¯x e ¯u soluzioni ammissibili rispettivamente per un problema P e per il suo duale, allora ¯x e ¯u non possono coincidere
4
