Prova scritta di Ricerca Operativa Corso di Laurea in
Ingegneria Informatica e Automatica
3 luglio 2012
Compito A
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. Dire quali delle seguenti affermazioni sono corrette.
(a) Un poliedro `e un insieme convesso.
(b) Un insieme convesso `e limitato.
(c) L’insieme {x ∈ IR2| x1+ 2x2≤ 3, 5x1senφ + 4x2cosφ = 1}, dove φ `e un valore fissato in [0, π/2], `e un poliedro.
(d) L’insieme {x ∈ IR3 | x1+ x2+ x32 ≤ 5, 0 ≤ x1 ≤ 1, 0 ≤ x2 ≤ 1, 0 ≤ x3 ≤ 1} `e un politopo.
2. Dire quali delle seguenti affermazioni sono corrette.
(a) Un politopo non vuoto ammette sempre vertici.
(b) Un poliedro non vuoto ammette sempre vertici.
(c) Esistono poliedri che ammettono un numero infinito di vertici.
(d) Se un poliedro non contiene rette, allora ammette vertici.
3. Sia dato un problema di Programmazione Lineare nella forma
min cTx Ax = b x ≥ 0 Dire quali delle seguenti affermazioni sono corrette.
(a) Il problema `e in forma standard e quindi ammette sempre una soluzione ottima.
(b) Se il sistema
Ax = b x ≥ 0
ammette soluzione, allora il problema o `e illimitato, oppure ammette soluzione ottima.
(c) Il problema non pu`o essere inammissibile.
(d) Se la matrice A (m × n) ha rango m, allora il problema ammette sicuramente soluzione ottima.
4. Si consideri il poliedro descritto dal seguente sistema
x1+ τ x2+ x3+ x4 = 4 x1− 3x4 = 1 2x1+ x2+ x3 = 5 xi≥ 0, i = 1, . . . , 4 Dire quali delle seguenti affermazioni sono corrette.
(a) Per τ = 1 il punto (1, 1, 1, 0)T `e vertice del poliedro.
(b) Per τ = 1 il punto (1, 1, 1, 0)T appartiene al poliedro.
(c) Per τ = 0 il punto (4, − 1, − 1, 1)T appartiene al poliedro.
(d) Il punto (1, 1, 1, 1)T `e vertice del poliedro per ogni valore di τ .
5. Al termine della fase I del metodo del simplesso applicato alla soluzione di un problema di PL risulta xB = (x1, α2, α3, x4)T, xN = (x2, α1, x3, α4)T,
B−1N =
−1 11 17 3
0 −1 3 2
0 −2 0 0
2 3 5 9
, B−1b =
5 0 0 6
.
Dire quali delle seguenti affermazioni sono corrette.
(a) Il problema originario `e inammissibile.
(b) Il valore ottimo del problema artificiale `e 0.
(c) Una possibile base ammissibile per il problema originario dalla quale far partire la fase II corrisponde ad avere variabili di base xB= (x1, x3, x4)T
(d) Una possibile base ammissibile per il problema originario dalla quale far partire la fase II corrisponde ad avere variabili di base xB= (x1, x2, x3, x4)T
6. Si consideri il seguente problema di Programmazione Lineare
min cTx Ax = b x ≥ 0 con
A =0 1 1 2 0 1
2 0 1 1 1 2
, b =1 2
, c = (1, 2, 1, 4, 0, 1)T. Dire quali delle seguenti affermazioni sono corrette.
(a) La seconda e la terza colonna della matrice A formano una base ammissibile.
(b) La soluzione di base associata alla base formata dalla terza e dalla quinta colonna `e (0, 0, 1, 0, 1, 0)T.
(c) La soluzione di base associata alla base formata dalla terza e dalla quinta colonna `e ottima.
(d) Il problema `e illimitato inferiormente.
7. In un’iterazione della fase II del metodo del simplesso applicato ad un problema di PL in forma di minimizzazione si ha xB= (x1, x8, x5, x4)T e xN = (x3, x6, x2, x7)T, ed inoltre risulta γ = (1, −1, 0, −1)T.
B−1N =
5 −1 −4 1
−1 5 1 −1
−3 1 5 −2
11 −3 −1 4
, B−1b =
0 5 3 0
.
Dire quali delle seguenti affermazioni sono corrette.
(a) Supponiamo che x7 sia la variabile entrante. Allora la successiva Soluzione di Base Ammissibile sar`a degenere.
(b) Supponiamo che x6 sia la variabile entrante. Allora la successiva Soluzione di Base Ammissibile sar`a degenere.
(c) Se x6 `e la variabile entrante, allora x8`e l’unica variabile uscente.
(d) Supponiamo che x6sia la variabile entrante. Allora il valore di ¯ρ `e pari a 0.
8. Si consideri il seguente poliedro definito da
x1+ 2x2− 2x3 ≤ 5 2x1+ x2 ≤ 3 x2+ x3 ≤ 4 x1 ≥ 0 x3 ≥ 0 Dire quali delle seguenti affermazioni sono corrette.
(a) Il punto (0, − 2, 1)T appartiene al poliedro.
(b) Il punto (0, 3, 1)T `e vertice del poliedro.
(c) L’origine degli assi (0, 0, 0)T `e vertice del poliedro.
(d) Il poliedro non ammette vertici.
9. Si consideri il seguente problema di Programmazione Lineare:
(P)
min 3x1− 5x2+ 7x3+ x4
x1− 3x2+ 5x4≤ 9 4x1− 7x3+ x4= 3
−x1+ x2+ 3x3≥ 10 x1≥ 0, x3≥ 0 Dire quali delle seguenti affermazioni sono corrette.
(a) Il problema duale del problema (P) ha quattro variabili.
(b) Il problema duale del problema (P) ha tre variabili delle quali solo due vincolate in segno.
(c) La funzione obiettivo del problema duale del problema (P) `e 9u1+ 3u2+ 10u3. (d) Se l’insieme ammissibile del problema (P) `e vuoto, allora il problema duale pu`o essere
solamente inammissibile.
10. Dire quali delle seguenti affermazioni sono corrette.
(a) Il problema artificiale (ausiliario) che si risolve nella Fase 1 del metodo del simplesso `e un problema di PL che ammette sempre soluzione ottima.
(b) Se alla fine della Fase 1 qualche variabile artificiale `e rimasta in base, allora il problema originario `e inammissibile.
(c) Se il problema originiario `e ammissibile, allora il valore ottimo del problema artificiale (ausiliario) che si risolve nella Fase 1 `e pari a zero.
(d) La Fase 1 permette sempre di determinare una base ammissibile del problema originario che `e la base dalla quale far partire la Fase 2.
Prova scritta di Ricerca Operativa Corso di Laurea in
Ingegneria Informatica e Automatica
3 luglio 2012
Compito B
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. Si consideri il seguente problema di Programmazione Lineare:
(P)
min 3x1− 5x2+ 7x3+ x4 x1− 3x2+ 5x4≤ 9 4x1− 7x3+ x4= 3
−x1+ x2+ 3x3≥ 10 x1≥ 0, x3≥ 0 Dire quali delle seguenti affermazioni sono corrette.
(a) La funzione obiettivo del problema duale del problema (P) `e 9u1+ 3u2+ 10u3. (b) Il problema duale del problema (P) ha quattro variabili.
(c) Il problema duale del problema (P) ha tre variabili delle quali solo due vincolate in segno.
(d) Se l’insieme ammissibile del problema (P) `e vuoto, allora il problema duale pu`o essere solamente inammissibile.
2. Dire quali delle seguenti affermazioni sono corrette.
(a) Se il problema originiario `e ammissibile, allora il valore ottimo del problema artificiale (ausiliario) che si risolve nella Fase 1 `e pari a zero.
(b) La Fase 1 permette sempre di determinare una base ammissibile del problema originario che `e la base dalla quale far partire la Fase 2.
(c) Il problema artificiale (ausiliario) che si risolve nella Fase 1 del metodo del simplesso `e un problema di PL che ammette sempre soluzione ottima.
(d) Se alla fine della Fase 1 qualche variabile artificiale `e rimasta in base, allora il problema originario `e inammissibile.
3. Dire quali delle seguenti affermazioni sono corrette.
(a) L’insieme {x ∈ IR2| x1+ 2x2≤ 3, 5x1senφ + 4x2cosφ = 1}, dove φ `e un valore fissato in [0, π/2], `e un poliedro.
(b) L’insieme {x ∈ IR3 | x1+ x2+ x32 ≤ 5, 0 ≤ x1 ≤ 1, 0 ≤ x2 ≤ 1, 0 ≤ x3 ≤ 1} `e un politopo.
(c) Un poliedro `e un insieme convesso.
(d) Un insieme convesso `e limitato.
4. Al termine della fase I del metodo del simplesso applicato alla soluzione di un problema di PL risulta xB = (x1, α2, α3, x4)T, xN = (x2, α1, x3, α4)T,
B−1N =
−1 11 17 3
0 −1 3 2
0 −2 0 0
2 3 5 9
, B−1b =
5 0 0 6
.
Dire quali delle seguenti affermazioni sono corrette.
(a) Una possibile base ammissibile per il problema originario dalla quale far partire la fase II corrisponde ad avere variabili di base xB= (x1, x3, x4)T
(b) Il problema originario `e inammissibile.
(c) Il valore ottimo del problema artificiale `e 0.
(d) Una possibile base ammissibile per il problema originario dalla quale far partire la fase II corrisponde ad avere variabili di base xB= (x1, x2, x3, x4)T
5. Dire quali delle seguenti affermazioni sono corrette.
(a) Se un poliedro non contiene rette, allora ammette vertici.
(b) Un poliedro non vuoto ammette sempre vertici.
(c) Esistono poliedri che ammettono un numero infinito di vertici.
(d) Un politopo non vuoto ammette sempre vertici.
6. Sia dato un problema di Programmazione Lineare nella forma
min cTx Ax = b x ≥ 0 Dire quali delle seguenti affermazioni sono corrette.
(a) Il problema `e in forma standard e quindi ammette sempre una soluzione ottima.
(b) Se il sistema
Ax = b x ≥ 0
ammette soluzione, allora il problema o `e illimitato, oppure ammette soluzione ottima.
(c) Il problema non pu`o essere inammissibile.
(d) Se la matrice A (m × n) ha rango m, allora il problema ammette sicuramente soluzione ottima.
7. In un’iterazione della fase II del metodo del simplesso applicato ad un problema di PL in forma di minimizzazione si ha xB= (x1, x8, x5, x4)T e xN = (x3, x6, x2, x7)T, ed inoltre risulta γ = (1, −1, 0, −1)T.
B−1N =
5 −1 −4 1
−1 5 1 −1
−3 1 5 −2
11 −3 −1 4
, B−1b =
0 5 3 0
.
Dire quali delle seguenti affermazioni sono corrette.
(a) Se x6 `e la variabile entrante, allora x8`e l’unica variabile uscente.
(b) Supponiamo che x6sia la variabile entrante. Allora il valore di ¯ρ `e pari a 0.
(c) Supponiamo che x7 sia la variabile entrante. Allora la successiva Soluzione di Base Ammissibile sar`a degenere.
(d) Supponiamo che x6 sia la variabile entrante. Allora la successiva Soluzione di Base Ammissibile sar`a degenere.
8. Si consideri il poliedro descritto dal seguente sistema
x1+ τ x2+ x3+ x4 = 4 x1− 3x4 = 1 2x1+ x2+ x3 = 5 xi≥ 0, i = 1, . . . , 4 Dire quali delle seguenti affermazioni sono corrette.
(a) Per τ = 1 il punto (1, 1, 1, 0)T appartiene al poliedro.
(b) Per τ = 1 il punto (1, 1, 1, 0)T `e vertice del poliedro.
(c) Per τ = 0 il punto (4, − 1, − 1, 1)T appartiene al poliedro.
(d) Il punto (1, 1, 1, 1)T `e vertice del poliedro per ogni valore di τ . 9. Si consideri il seguente problema di Programmazione Lineare
min cTx Ax = b x ≥ 0 con
A =0 1 1 2 0 1
2 0 1 1 1 2
, b =1 2
, c = (1, 2, 1, 4, 0, 1)T. Dire quali delle seguenti affermazioni sono corrette.
(a) La soluzione di base associata alla base formata dalla terza e dalla quinta colonna `e ottima.
(b) La seconda e la terza colonna della matrice A formano una base ammissibile.
(c) La soluzione di base associata alla base formata dalla terza e dalla quinta colonna `e (0, 0, 1, 0, 1, 0)T.
(d) Il problema `e illimitato inferiormente.
10. Si consideri il seguente poliedro definito da
x1+ 2x2− 2x3 ≤ 5 2x1+ x2 ≤ 3 x2+ x3 ≤ 4 x1 ≥ 0 x3 ≥ 0 Dire quali delle seguenti affermazioni sono corrette.
(a) L’origine degli assi (0, 0, 0)T `e vertice del poliedro.
(b) Il poliedro non ammette vertici.
(c) Il punto (0, − 2, 1)T appartiene al poliedro.
(d) Il punto (0, 3, 1)T `e vertice del poliedro.
Prova scritta di Ricerca Operativa Corso di Laurea in
Ingegneria Informatica e Automatica
3 luglio 2012
Compito C
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. Al termine della fase I del metodo del simplesso applicato alla soluzione di un problema di PL risulta xB = (x1, α2, α3, x4)T, xN = (x2, α1, x3, α4)T,
B−1N =
−1 11 17 3
0 −1 3 2
0 −2 0 0
2 3 5 9
, B−1b =
5 0 0 6
.
Dire quali delle seguenti affermazioni sono corrette.
(a) Una possibile base ammissibile per il problema originario dalla quale far partire la fase II corrisponde ad avere variabili di base xB= (x1, x2, x3, x4)T
(b) Il problema originario `e inammissibile.
(c) Il valore ottimo del problema artificiale `e 0.
(d) Una possibile base ammissibile per il problema originario dalla quale far partire la fase II corrisponde ad avere variabili di base xB= (x1, x3, x4)T
2. Dire quali delle seguenti affermazioni sono corrette.
(a) La Fase 1 permette sempre di determinare una base ammissibile del problema originario che `e la base dalla quale far partire la Fase 2.
(b) Il problema artificiale (ausiliario) che si risolve nella Fase 1 del metodo del simplesso `e un problema di PL che ammette sempre soluzione ottima.
(c) Se il problema originiario `e ammissibile, allora il valore ottimo del problema artificiale (ausiliario) che si risolve nella Fase 1 `e pari a zero.
(d) Se alla fine della Fase 1 qualche variabile artificiale `e rimasta in base, allora il problema originario `e inammissibile.
3. Dire quali delle seguenti affermazioni sono corrette.
(a) L’insieme {x ∈ IR2| x1+ 2x2≤ 3, 5x1senφ + 4x2cosφ = 1}, dove φ `e un valore fissato in [0, π/2], `e un poliedro.
(b) Un poliedro `e un insieme convesso.
(c) L’insieme {x ∈ IR3 | x1+ x2+ x32 ≤ 5, 0 ≤ x1 ≤ 1, 0 ≤ x2 ≤ 1, 0 ≤ x3 ≤ 1} `e un politopo.
(d) Un insieme convesso `e limitato.
4. Sia dato un problema di Programmazione Lineare nella forma
min cTx Ax = b x ≥ 0 Dire quali delle seguenti affermazioni sono corrette.
(a) Il problema non pu`o essere inammissibile.
(b) Il problema `e in forma standard e quindi ammette sempre una soluzione ottima.
(c) Se il sistema
Ax = b x ≥ 0
ammette soluzione, allora il problema o `e illimitato, oppure ammette soluzione ottima.
(d) Se la matrice A (m × n) ha rango m, allora il problema ammette sicuramente soluzione ottima.
5. Si consideri il seguente problema di Programmazione Lineare:
(P)
min 3x1− 5x2+ 7x3+ x4
x1− 3x2+ 5x4≤ 9 4x1− 7x3+ x4= 3
−x1+ x2+ 3x3≥ 10 x1≥ 0, x3≥ 0 Dire quali delle seguenti affermazioni sono corrette.
(a) Il problema duale del problema (P) ha tre variabili delle quali solo due vincolate in segno.
(b) Se l’insieme ammissibile del problema (P) `e vuoto, allora il problema duale pu`o essere solamente inammissibile.
(c) La funzione obiettivo del problema duale del problema (P) `e 9u1+ 3u2+ 10u3. (d) Il problema duale del problema (P) ha quattro variabili.
6. In un’iterazione della fase II del metodo del simplesso applicato ad un problema di PL in forma di minimizzazione si ha xB= (x1, x8, x5, x4)T e xN = (x3, x6, x2, x7)T, ed inoltre risulta γ = (1, −1, 0, −1)T.
B−1N =
5 −1 −4 1
−1 5 1 −1
−3 1 5 −2
11 −3 −1 4
, B−1b =
0 5 3 0
.
Dire quali delle seguenti affermazioni sono corrette.
(a) Se x6 `e la variabile entrante, allora x8`e l’unica variabile uscente.
(b) Supponiamo che x6sia la variabile entrante. Allora il valore di ¯ρ `e pari a 0.
(c) Supponiamo che x7 sia la variabile entrante. Allora la successiva Soluzione di Base Ammissibile sar`a degenere.
(d) Supponiamo che x6 sia la variabile entrante. Allora la successiva Soluzione di Base Ammissibile sar`a degenere.
7. Dire quali delle seguenti affermazioni sono corrette.
(a) Se un poliedro non contiene rette, allora ammette vertici.
(b) Un politopo non vuoto ammette sempre vertici.
(c) Un poliedro non vuoto ammette sempre vertici.
(d) Esistono poliedri che ammettono un numero infinito di vertici.
8. Si consideri il poliedro descritto dal seguente sistema
x1+ τ x2+ x3+ x4 = 4 x1− 3x4 = 1 2x1+ x2+ x3 = 5 xi≥ 0, i = 1, . . . , 4 Dire quali delle seguenti affermazioni sono corrette.
(a) Il punto (1, 1, 1, 1)T `e vertice del
(b) Per τ = 1 il punto (1, 1, 1, 0)T appartiene al poliedro.
(c) Per τ = 0 il punto (4, − 1, − 1, 1)T appartiene al poliedro.
poliedro per ogni valore di τ .
(d) Per τ = 1 il punto (1, 1, 1, 0)T `e vertice del poliedro.
9. Si consideri il seguente poliedro definito da
x1+ 2x2− 2x3 ≤ 5 2x1+ x2 ≤ 3 x2+ x3 ≤ 4 x1 ≥ 0 x3 ≥ 0 Dire quali delle seguenti affermazioni sono corrette.
(a) Il punto (0, − 2, 1)T appartiene al poliedro.
(b) Il poliedro non ammette vertici.
(c) Il punto (0, 3, 1)T `e vertice del poliedro.
(d) L’origine degli assi (0, 0, 0)T `e vertice del poliedro.
10. Si consideri il seguente problema di Programmazione Lineare
min cTx Ax = b x ≥ 0 con
A =0 1 1 2 0 1
2 0 1 1 1 2
, b =1 2
, c = (1, 2, 1, 4, 0, 1)T. Dire quali delle seguenti affermazioni sono corrette.
(a) La soluzione di base associata alla base formata dalla terza e dalla quinta colonna `e (0, 0, 1, 0, 1, 0)T.
(b) La soluzione di base associata alla base formata dalla terza e dalla quinta colonna `e ottima.
(c) La seconda e la terza colonna della matrice A formano una base ammissibile.
(d) Il problema `e illimitato inferiormente.
Prova scritta di Ricerca Operativa Corso di Laurea in
Ingegneria Informatica e Automatica
8 giugno 2012
Compito D
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. In un’iterazione della fase II del metodo del simplesso applicato ad un problema di PL in forma di minimizzazione si ha xB= (x1, x8, x5, x4)T e xN = (x3, x6, x2, x7)T, ed inoltre risulta γ = (1, −1, 0, −1)T.
B−1N =
5 −1 −4 1
−1 5 1 −1
−3 1 5 −2
11 −3 −1 4
, B−1b =
0 5 3 0
.
Dire quali delle seguenti affermazioni sono corrette.
(a) Supponiamo che x7 sia la variabile entrante. Allora la successiva Soluzione di Base Ammissibile sar`a degenere.
(b) Se x6 `e la variabile entrante, allora x8`e l’unica variabile uscente.
(c) Supponiamo che x6sia la variabile entrante. Allora il valore di ¯ρ `e pari a 0.
(d) Supponiamo che x6 sia la variabile entrante. Allora la successiva Soluzione di Base Ammissibile sar`a degenere.
2. Si consideri il seguente problema di Programmazione Lineare:
(P)
min 3x1− 5x2+ 7x3+ x4
x1− 3x2+ 5x4≤ 9 4x1− 7x3+ x4= 3
−x1+ x2+ 3x3≥ 10 x1≥ 0, x3≥ 0 Dire quali delle seguenti affermazioni sono corrette.
(a) Il problema duale del problema (P) ha tre variabili delle quali solo due vincolate in segno.
(b) La funzione obiettivo del problema duale del problema (P) `e 9u1+ 3u2+ 10u3. (c) Il problema duale del problema (P) ha quattro variabili.
(d) Se l’insieme ammissibile del problema (P) `e vuoto, allora il problema duale pu`o essere solamente inammissibile.
3. Sia dato un problema di Programmazione Lineare nella forma
min cTx Ax = b x ≥ 0 Dire quali delle seguenti affermazioni sono corrette.
(a) Se il sistema
Ax = b x ≥ 0
ammette soluzione, allora il problema o `e illimitato, oppure ammette soluzione ottima.
(b) Il problema non pu`o essere inammissibile.
(c) Il problema `e in forma standard e quindi ammette sempre una soluzione ottima.
(d) Se la matrice A (m × n) ha rango m, allora il problema ammette sicuramente soluzione ottima.
4. Dire quali delle seguenti affermazioni sono corrette.
(a) Se il problema originiario `e ammissibile, allora il valore ottimo del problema artificiale (ausiliario) che si risolve nella Fase 1 `e pari a zero.
(b) Se alla fine della Fase 1 qualche variabile artificiale `e rimasta in base, allora il problema originario `e inammissibile.
(c) La Fase 1 permette sempre di determinare una base ammissibile del problema originario che `e la base dalla quale far partire la Fase 2.
(d) Il problema artificiale (ausiliario) che si risolve nella Fase 1 del metodo del simplesso `e un problema di PL che ammette sempre soluzione ottima.
5. Al termine della fase I del metodo del simplesso applicato alla soluzione di un problema di PL risulta xB = (x1, α2, α3, x4)T, xN = (x2, α1, x3, α4)T,
B−1N =
−1 11 17 3
0 −1 3 2
0 −2 0 0
2 3 5 9
, B−1b =
5 0 0 6
.
Dire quali delle seguenti affermazioni sono corrette.
(a) Il problema originario `e inammissibile.
(b) Una possibile base ammissibile per il problema originario dalla quale far partire la fase II corrisponde ad avere variabili di base xB= (x1, x3, x4)T
(c) Una possibile base ammissibile per il problema originario dalla quale far partire la fase II corrisponde ad avere variabili di base xB= (x1, x2, x3, x4)T
(d) Il valore ottimo del problema artificiale `e 0.
6. Dire quali delle seguenti affermazioni sono corrette.
(a) L’insieme {x ∈ IR3 | x1+ x2+ x32 ≤ 5, 0 ≤ x1 ≤ 1, 0 ≤ x2 ≤ 1, 0 ≤ x3 ≤ 1} `e un politopo.
(b) L’insieme {x ∈ IR2| x1+ 2x2≤ 3, 5x1senφ + 4x2cosφ = 1}, dove φ `e un valore fissato in [0, π/2], `e un poliedro.
(c) Un poliedro `e un insieme convesso.
(d) Un insieme convesso `e limitato.
7. Si consideri il poliedro descritto dal seguente sistema
x1+ τ x2+ x3+ x4 = 4 x1− 3x4 = 1 2x1+ x2+ x3 = 5 xi≥ 0, i = 1, . . . , 4 Dire quali delle seguenti affermazioni sono corrette.
(a) Per τ = 0 il punto (4, − 1, − 1, 1)T appartiene al poliedro.
(b) Il punto (1, 1, 1, 1)T `e vertice del poliedro per ogni valore di τ . (c) Per τ = 1 il punto (1, 1, 1, 0)T appartiene al poliedro.
(d) Per τ = 1 il punto (1, 1, 1, 0)T `e vertice del poliedro.
8. Dire quali delle seguenti affermazioni sono corrette.
(a) Esistono poliedri che ammettono un numero infinito di vertici.
(b) Se un poliedro non contiene rette, allora ammette vertici.
(c) Un poliedro non vuoto ammette sempre vertici.
(d) Un politopo non vuoto ammette sempre vertici.
9. Si consideri il seguente poliedro definito da
x1+ 2x2− 2x3 ≤ 5 2x1+ x2 ≤ 3 x2+ x3 ≤ 4 x1 ≥ 0 x3 ≥ 0 Dire quali delle seguenti affermazioni sono corrette.
(a) Il punto (0, 3, 1)T `e vertice del poliedro.
(b) L’origine degli assi (0, 0, 0)T `e vertice del poliedro.
(c) Il poliedro non ammette vertici.
(d) Il punto (0, − 2, 1)T appartiene al poliedro.
10. Si consideri il seguente problema di Programmazione Lineare
min cTx Ax = b x ≥ 0 con
A =0 1 1 2 0 1
2 0 1 1 1 2
, b =1 2
, c = (1, 2, 1, 4, 0, 1)T. Dire quali delle seguenti affermazioni sono corrette.
(a) La soluzione di base associata alla base formata dalla terza e dalla quinta colonna `e (0, 0, 1, 0, 1, 0)T.
(b) La soluzione di base associata alla base formata dalla terza e dalla quinta colonna `e ottima.
(c) La seconda e la terza colonna della matrice A formano una base ammissibile.
(d) Il problema `e illimitato inferiormente.
