Prova scritta di Ricerca Operativa Corso di Laurea in
Ingegneria Informatica e Automatica
21 febbraio 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. Sia P un poliedro di <n. (a) P `e un insieme convesso
(b) Se P `e limitato allora `e un politopo (c) P pu`o non ammettere vertici
(d) P pu`o essere sempre espresso nella forma P = {x ∈ <n | Ax ≤ b} con A matrice m × n e b ∈ <m.
2. Sia dato l’insieme di <n: P = {x ∈ <n | Ax ≥ b} con A matrice m × n e b ∈ <m. (a) Se b = 0 allora l’origine `e un vertice di P
(b) I vertici di P sono al pi`u mn
(c) Se m < n P non pu`o ammettere vertici
(d) L’insieme P ∩ {x ∈ <n | x ≥ 0} ammette sicuramente l’origine come vertice.
3. Sia dato un problema di PL in forma standard e sia A la matrice dei coefficienti dei vincoli di uguaglianza. Allora
(a) Se A `e a rango massimo si pu`o applicare direttamente la Fase II del metodo del simplesso, senza la necessit`a di applicare prima la Fase I
(b) Se il problema ammette soluzione ottima, esiste sempre almeno un punto tale che le colonne della matrice della matrice A corrispondenti alle componenti positive di questo punto sono linearmente indipendenti
(c) Il problema ammette sempre soluzione ottima
(d) La funzione obiettivo del problema pu`o essere illimitata.
4. Dato il poliedro definito dal sistema
x1+ x2 ≤ 3 x1+ x3+ x4 ≤ 5 x3+ 2x4 ≤ 4
x ≥ 0
(a) Il punto (1, 2, 4, 0)T `e un vertice del poliedro;
(b) Il punto (1, 2, 4, 1)T `e un vertice del poliedro;
(c) Il punto (1, 2, 3, 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) Se alla fine della Fase I la funzione obiettivo del problema artificiale `e non nulla, allora il problema originario `e inammissibile
(b) Alla fine della Fase I tutte le varibili artificiali sono sempre fuori base
(c) Se il problema artificiale `e inammissibile, allora il problema originario `e illimitato (d) Se alla fine della Fase I `e rimasta una variabile artificiale in base, si procede sempre con
uno scambio degenere.
2
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 per un certo indice h risulta γh < 0 ed inoltre B−1N
h = 0, allora il problema `e illimitato inferiormente
(b) B ed N devono avere lo stesso numero di righe
(c) Risulta γ ≥ 0 se e soltanto se la soluzione di base corrente `e ottima (d) B `e una sottomatrice di A, m × m non singolare
7. Arrivati all’ottimo del problema artificiale che si risolve nella fase I del metodo del simplesso abbiamo che risulta xB= (x2, α2, x4, α4), xN = (x1, α1, x3, α3),
B−1b =
0 σ 1 0
, B−1N =
3 6 29 16
0 12 0 22
7 31 73 12 66 38 0 27
Allora
(a) Il problema originario `e ammissibile se e solo se σ = 0
(b) Se σ = 0, allora il problema originario `e ammissibile e una possibile base ammissibile per il problema originario dalla quale far partire la Fase II corrisponde ad avere variabili di base xB = (x2, x4, x1)
(c) Se σ = 0, allora il problema originario `e ammissibile e 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)
(d) Se σ = −1 allora la matrice dei vincoli dei uguaglianza del problema originario ha rango massimo.
8. Ad una iterazione della Fase II del metodo del simplesso si ha: xB= (x2, x1, x4)T, xN = (x3, x6, x5)T,
B−1N =
1 −δ −3
7 0 6
2 1 1
, B−1b =
1 1 δ
Se la funzione obiettivo (da minimizzare) `e f (x1, x2, x3, x4, x5, x6) = x2+ x4 allora (a) Non esistono valori di δ tali che la SBA corrente soddisfi il criterio di ottimalit`a (b) Se δ > 2 allora l’unica variabile candidata ad entrare in base `e x3
(c) Se δ = 1 allora l’unica variabile candidata d uscire dalla base `e x4
(d) Se δ < 0 allora la seconda variabile fuori base pu`o entrare in base.
9. Sia dato il seguente poliedro
2x1+ τ x4 = 3 x2+ x3 = 0 x1+ x2+ x3 = 1
x ≥ 0
3
(a) Per τ = 1 il punto (1, 0, 0, 1)T `e un vertice del poliedro (b) Esistono valori di τ per i quali l’origine `e vertice del poliedro (c) Per τ = 1 il punto (1, 1, − 1, 1)T `e una SBA;
(d) per τ = −1 il punto (2, 0, 0, 1)T `e un vertice del poliedro.
10. Sia dato il seguente problema di Programmazione Lineare:
max cTx Ax ≥ b x ≥ 0 (a) Il suo duale `e
max bTu
−ATu ≥ c u ≤ 0
(b) Un problema di PL ammette soluzione ottima se e solo se il suo duale ammette soluzione ottima con valore nullo
(c) Il problema primale pu`o ammettere almeno una soluzione ammissibile se e solo se esiste soluzione ottima per il suo duale
(d) Se il problema primale `e illimitato allora il suo duale `e illimitato oppure inammissibile.
4
