• Non ci sono risultati.

Prova scritta di Ricerca Operativa Corso di Laurea in Ingegneria Informatica e Automatica

N/A
N/A
Protected

Academic year: 2021

Condividi "Prova scritta di Ricerca Operativa Corso di Laurea in Ingegneria Informatica e Automatica"

Copied!
16
0
0

Testo completo

(1)

Prova scritta di Ricerca Operativa Corso di Laurea in

Ingegneria Informatica e Automatica

11 luglio 2011

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

(2)

1. Sia dato l’insieme Π = {x ∈ IRn | aTx = b} con a ∈ IRn e b ∈ IR, a 6= 0, b 6= 0. Dire quali delle seguenti affermazioni sono corrette.

(a) Π `e un insieme convesso.

(b) Π `e un politopo.

(c) Π non ammette vertici.

(d) Π pu`o essere l’insieme ammissibile di un problema di Programmazione Lineare.

2. Dire quali delle seguenti affermazioni sono corrette.

(a) Un poliedro che contiene semirette non pu`o ammettere vertici.

(b) Non esistono poliedri che contengono rette.

(c) L’unione di due poliedri `e un insieme convesso.

(d) L’intersezione di due poliedri `e un insieme convesso.

3. Sia dato un problema di Programmazione Lineare nella forma min cTx

Ax = b x ≥ 0,

(con A matrice m × n) e si supponga che il problema sia ammissibile e che risulti rango(A) = m. Dire quali delle seguenti affermazioni sono corrette.

(a) Se il problema non `e illimitato inferiormente la Fase II del metodo del simplesso, in un numero finito di iterazioni, converge alla soluzione ottima.

(b) Se supponiamo che ogni soluzione di base ammissibile sia non degenere, allora non pu`o verificarsi il fenomeno del ciclaggio per la Fase II del metodo del simplesso.

(c) Nella sequenza delle basi generate durante la Fase II del metodo del simplesso una ripetizione non pu`o verificarsi se supponiamo che ogni soluzione di base ammissibile sia non degenere.

(d) Il numero delle iterazioni necessarie alla Fase II del metodo del simplesso per convergere ad una soluzione ottima `e minore o uguale ad m.

4. Sia dato un problema di Programmazione Lineare in forma standard. Dire quali delle seguenti affermazioni sono corrette.

(a) La Fase I del metodo del simplesso permette di determinare se il problema `e ammissibile e se ci sono vincoli ridondanti.

(b) Il problema artificiale che si risolve nella Fase I del metodo del simplesso `e un problema di Programmazione Lineare che ammette soluzione ottima se e soltanto se il problema originario `e ammissibile.

(c) La funzione obiettivo del problema artificiale che si risolve nella Fase I del metodo del simplesso all’ottimo vale sempre zero.

(d) Se il problema originario `e illimitato allora il problema artificiale `e inammissibile.

(3)

5. Sia dato il seguente problema

min 3x1+ 2x2+ x1x2 x1+ 2x2= 0 x1≥ 0, x2≥ 0.

Dire quali delle seguenti affermazioni sono corrette.

(a) L’insieme ammissibile del problema `e un poliedro che ammette sempre almeno un vertice.

(b) Si tratta di un problema di Programmazione Lineare che ammette soluzione ottima.

(c) L’insieme ammissibile del problema `e costituito da infiniti punti distinti.

(d) Il problema non `e un problema di Programmazione Lineare.

6. Al termine della Fase I del metodo del simplesso applicato alla soluzione di un problema di Programmazione Lineare risulta xB = (α1, x2, α3, x4)T, xN = (α4, x3, x1, α2)T,

B−1N =

0 0 1 0

2 0 0 −1

5 9 3 7

3 −3 2 12

, B−1b =

 0 11

0 2

 .

Dire quali delle seguenti affermazioni sono corrette.

(a) Il problema originario `e ammissibile.

(b) Il problema originario ha un vincolo ridondante.

(c) Una possibile base ammissibile per il problema originario dalla quale far partire la Fase II corrisponde ad avere variabili di base xB= (x3, x2, 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.

7. Si consideri il poliedro descritto dal seguente sistema x1+ x2− x4 = 2

−x1+ x3+ x4 = 0 x1+ x2+ 7x3− x4 = 9

xi≥ 0, i = 1, . . . , 4 Dire quali delle seguenti affermazioni sono corrette.

(a) Il punto (1, 1, 1, 0)T `e vertice del poliedro.

(b) Il punto (3, 0, 2, 1)T `e vertice del poliedro.

(c) Il punto (0, 0, 1, − 2)T `e vertice del poliedro.

(d) Il poliedro non ammette vertici.

8. Si consideri il poliedro descritto dal seguente sistema

−τ x1+ 2x2+ x3 ≥ τ 2x1− τ x2− x3 ≥ −2

x1 ≥ 0 x3 ≥ 0, con τ ∈ IR. Dire quali delle seguenti affermazioni sono corrette.

(4)

(a) Per τ = 1 il punto (0, − 1, 3)T `e vertice del poliedro.

(b) Per τ = 2 il punto (0, − 1, 0)T `e vertice del poliedro.

(c) Per τ = 0 l’origine degli assi `e vertice del poliedro.

(d) L’origine degli assi `e vertice del poliedro per ogni valore di τ ∈ IR.

9. Sia dato un problema di Programmazione Lineare in forma standard con A =

 2 1 3 0 1 0

1 0 5 2 1 1



, c = (0, 1, 3, 1, 0, 1)T, b = (δ, 1)T Dire quali delle seguenti affermazioni sono corrette.

(a) La base formata dalla 2a e dalla 6a colonna `e una base ammissibile per ogni valore di δ ∈ IR.

(b) Per δ = 0 la base formata dalla 2a e dalla 5a colonna `e una base ammissibile.

(c) Il punto ¯x = (1, δ − 2, 0, 0, 0, 0)T soddisfa il criterio di ottimalit`a per ogni valore di δ ≥ 2.

(d) Non esiste nessuna base ammissibile in corrispondenza della quale il criterio di illimi- tatezza `e soddisfatto.

10. Si consideri il seguente problema di Programmazione Lineare (P):

max cTx Ax ≥ b,

con A matrice m × n. Dire quali delle seguenti affermazioni sono corrette.

(a) Il problema duale del problema (P) `e

max bTu ATu = c u ≥ 0

(b) Il problema duale del problema (P) `e un problema di Programmazione Lineare con m variabili.

(c) Se l’insieme ammissibile del problema (P) `e vuoto, allora anche l’insieme ammissibile del problema duale `e vuoto.

(d) Se il problema (P) ammette ottimo (finito), il suo duale non pu`o essere illimitato.

(5)

Prova scritta di Ricerca Operativa Corso di Laurea in

Ingegneria Informatica e Automatica

11 luglio 2011

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

(6)

1. Al termine della Fase I del metodo del simplesso applicato alla soluzione di un problema di Programmazione Lineare risulta xB = (α1, x2, α3, x4)T, xN = (α4, x3, x1, α2)T,

B−1N =

0 0 1 0

2 0 0 −1

5 9 3 7

3 −3 2 12

, B−1b =

 0 11

0 2

 .

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= (x3, x2, x4)T.

(b) 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.

(c) Il problema originario `e ammissibile.

(d) Il problema originario ha un vincolo ridondante.

2. Sia dato un problema di Programmazione Lineare in forma standard con A =

 2 1 3 0 1 0

1 0 5 2 1 1



, c = (0, 1, 3, 1, 0, 1)T, b = (δ, 1)T Dire quali delle seguenti affermazioni sono corrette.

(a) Il punto ¯x = (1, δ − 2, 0, 0, 0, 0)T soddisfa il criterio di ottimalit`a per ogni valore di δ ≥ 2.

(b) La base formata dalla 2a e dalla 6a colonna `e una base ammissibile per ogni valore di δ ∈ IR.

(c) Per δ = 0 la base formata dalla 2a e dalla 5a colonna `e una base ammissibile.

(d) Non esiste nessuna base ammissibile in corrispondenza della quale il criterio di illimi- tatezza `e soddisfatto.

3. Sia dato un problema di Programmazione Lineare in forma standard. Dire quali delle seguenti affermazioni sono corrette.

(a) Il problema artificiale che si risolve nella Fase I del metodo del simplesso `e un problema di Programmazione Lineare che ammette soluzione ottima se e soltanto se il problema originario `e ammissibile.

(b) La funzione obiettivo del problema artificiale che si risolve nella Fase I del metodo del simplesso all’ottimo vale sempre zero.

(c) Se il problema originario `e illimitato allora il problema artificiale `e inammissibile.

(d) La Fase I del metodo del simplesso permette di determinare se il problema `e ammissibile e se ci sono vincoli ridondanti.

4. Si consideri il seguente problema di Programmazione Lineare (P):

max cTx Ax ≥ b,

con A matrice m × n. Dire quali delle seguenti affermazioni sono corrette.

(7)

(a) Il problema duale del problema (P) `e

max bTu ATu = c u ≥ 0

(b) Se il problema (P) ammette ottimo (finito), il suo duale non pu`o essere illimitato.

(c) Il problema duale del problema (P) `e un problema di Programmazione Lineare con m variabili.

(d) Se l’insieme ammissibile del problema (P) `e vuoto, allora anche l’insieme ammissibile del problema duale `e vuoto.

5. Sia dato l’insieme Π = {x ∈ IRn | aTx = b} con a ∈ IRn e b ∈ IR, a 6= 0, b 6= 0. Dire quali delle seguenti affermazioni sono corrette.

(a) Π non ammette vertici.

(b) Π `e un insieme convesso.

(c) Π `e un politopo.

(d) Π pu`o essere l’insieme ammissibile di un problema di Programmazione Lineare.

6. Si consideri il poliedro descritto dal seguente sistema

−τ x1+ 2x2+ x3 ≥ τ 2x1− τ x2− x3 ≥ −2

x1 ≥ 0 x3 ≥ 0, con τ ∈ IR. Dire quali delle seguenti affermazioni sono corrette.

(a) Per τ = 2 il punto (0, − 1, 0)T `e vertice del poliedro.

(b) Per τ = 1 il punto (0, − 1, 3)T `e vertice del poliedro.

(c) Per τ = 0 l’origine degli assi `e vertice del poliedro.

(d) L’origine degli assi `e vertice del poliedro per ogni valore di τ ∈ IR.

7. Dire quali delle seguenti affermazioni sono corrette.

(a) L’unione di due poliedri `e un insieme convesso.

(b) L’intersezione di due poliedri `e un insieme convesso.

(c) Un poliedro che contiene semirette non pu`o ammettere vertici.

(d) Non esistono poliedri che contengono rette.

8. Si consideri il poliedro descritto dal seguente sistema x1+ x2− x4 = 2

−x1+ x3+ x4 = 0 x1+ x2+ 7x3− x4 = 9

xi≥ 0, i = 1, . . . , 4 Dire quali delle seguenti affermazioni sono corrette.

(8)

(a) Il punto (0, 0, 1, − 2)T `e vertice del poliedro.

(b) Il punto (1, 1, 1, 0)T `e vertice del poliedro.

(c) Il punto (3, 0, 2, 1)T `e vertice del poliedro.

(d) Il poliedro non ammette vertici.

9. Sia dato un problema di Programmazione Lineare nella forma min cTx

Ax = b x ≥ 0,

(con A matrice m × n) e si supponga che il problema sia ammissibile e che risulti rango(A) = m. Dire quali delle seguenti affermazioni sono corrette.

(a) Nella sequenza delle basi generate durante la Fase II del metodo del simplesso una ripetizione non pu`o verificarsi se supponiamo che ogni soluzione di base ammissibile sia non degenere.

(b) Se il problema non `e illimitato inferiormente la Fase II del metodo del simplesso, in un numero finito di iterazioni, converge alla soluzione ottima.

(c) Se supponiamo che ogni soluzione di base ammissibile sia non degenere, allora non pu`o verificarsi il fenomeno del ciclaggio per la Fase II del metodo del simplesso.

(d) Il numero delle iterazioni necessarie alla Fase II del metodo del simplesso per convergere ad una soluzione ottima `e minore o uguale ad m.

10. Sia dato il seguente problema

min 3x1+ 2x2+ x1x2 x1+ 2x2= 0 x1≥ 0, x2≥ 0.

Dire quali delle seguenti affermazioni sono corrette.

(a) L’insieme ammissibile del problema `e costituito da infiniti punti distinti.

(b) Il problema non `e un problema di Programmazione Lineare.

(c) L’insieme ammissibile del problema `e un poliedro che ammette sempre almeno un vertice.

(d) Si tratta di un problema di Programmazione Lineare che ammette soluzione ottima.

(9)

Prova scritta di Ricerca Operativa Corso di Laurea in

Ingegneria Informatica e Automatica

11 luglio 2011

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

(10)

1. Sia dato un problema di Programmazione Lineare in forma standard. Dire quali delle seguenti affermazioni sono corrette.

(a) La funzione obiettivo del problema artificiale che si risolve nella Fase I del metodo del simplesso all’ottimo vale sempre zero.

(b) Se il problema originario `e illimitato allora il problema artificiale `e inammissibile.

(c) La Fase I del metodo del simplesso permette di determinare se il problema `e ammissibile e se ci sono vincoli ridondanti.

(d) Il problema artificiale che si risolve nella Fase I del metodo del simplesso `e un problema di Programmazione Lineare che ammette soluzione ottima se e soltanto se il problema originario `e ammissibile.

2. Al termine della Fase I del metodo del simplesso applicato alla soluzione di un problema di Programmazione Lineare risulta xB = (α1, x2, α3, x4)T, xN = (α4, x3, x1, α2)T,

B−1N =

0 0 1 0

2 0 0 −1

5 9 3 7

3 −3 2 12

, B−1b =

 0 11

0 2

 .

Dire quali delle seguenti affermazioni sono corrette.

(a) Il problema originario ha un vincolo ridondante.

(b) Il problema originario `e ammissibile.

(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) Una possibile base ammissibile per il problema originario dalla quale far partire la Fase II corrisponde ad avere variabili di base xB= (x3, x2, x4)T.

3. Si consideri il seguente problema di Programmazione Lineare (P):

max cTx Ax ≥ b,

con A matrice m × n. Dire quali delle seguenti affermazioni sono corrette.

(a) Il problema duale del problema (P) `e un problema di Programmazione Lineare con m variabili.

(b) Il problema duale del problema (P) `e

max bTu ATu = c u ≥ 0

(c) Se l’insieme ammissibile del problema (P) `e vuoto, allora anche l’insieme ammissibile del problema duale `e vuoto.

(d) Se il problema (P) ammette ottimo (finito), il suo duale non pu`o essere illimitato.

(11)

4. Si consideri il poliedro descritto dal seguente sistema x1+ x2− x4 = 2

−x1+ x3+ x4 = 0 x1+ x2+ 7x3− x4 = 9

xi≥ 0, i = 1, . . . , 4 Dire quali delle seguenti affermazioni sono corrette.

(a) Il punto (3, 0, 2, 1)T `e vertice del poliedro.

(b) Il punto (0, 0, 1, − 2)T `e vertice del poliedro.

(c) Il punto (1, 1, 1, 0)T `e vertice del poliedro.

(d) Il poliedro non ammette vertici.

5. Sia dato l’insieme Π = {x ∈ IRn | aTx = b} con a ∈ IRn e b ∈ IR, a 6= 0, b 6= 0. Dire quali delle seguenti affermazioni sono corrette.

(a) Π non ammette vertici.

(b) Π pu`o essere l’insieme ammissibile di un problema di Programmazione Lineare.

(c) Π `e un insieme convesso.

(d) Π `e un politopo.

6. Dire quali delle seguenti affermazioni sono corrette.

(a) Non esistono poliedri che contengono rette.

(b) L’unione di due poliedri `e un insieme convesso.

(c) Un poliedro che contiene semirette non pu`o ammettere vertici.

(d) L’intersezione di due poliedri `e un insieme convesso.

7. Sia dato il seguente problema

min 3x1+ 2x2+ x1x2 x1+ 2x2= 0 x1≥ 0, x2≥ 0.

Dire quali delle seguenti affermazioni sono corrette.

(a) L’insieme ammissibile del problema `e costituito da infiniti punti distinti.

(b) L’insieme ammissibile del problema `e un poliedro che ammette sempre almeno un vertice.

(c) Si tratta di un problema di Programmazione Lineare che ammette soluzione ottima.

(d) Il problema non `e un problema di Programmazione Lineare.

8. Sia dato un problema di Programmazione Lineare nella forma min cTx

Ax = b x ≥ 0,

(con A matrice m × n) e si supponga che il problema sia ammissibile e che risulti rango(A) = m. Dire quali delle seguenti affermazioni sono corrette.

(12)

(a) Se supponiamo che ogni soluzione di base ammissibile sia non degenere, allora non pu`o verificarsi il fenomeno del ciclaggio per la Fase II del metodo del simplesso.

(b) Nella sequenza delle basi generate durante la Fase II del metodo del simplesso una ripetizione non pu`o verificarsi se supponiamo che ogni soluzione di base ammissibile sia non degenere.

(c) Se il problema non `e illimitato inferiormente la Fase II del metodo del simplesso, in un numero finito di iterazioni, converge alla soluzione ottima.

(d) Il numero delle iterazioni necessarie alla Fase II del metodo del simplesso per convergere ad una soluzione ottima `e minore o uguale ad m.

9. Si consideri il poliedro descritto dal seguente sistema

−τ x1+ 2x2+ x3 ≥ τ 2x1− τ x2− x3 ≥ −2

x1 ≥ 0 x3 ≥ 0, con τ ∈ IR. Dire quali delle seguenti affermazioni sono corrette.

(a) Per τ = 2 il punto (0, − 1, 0)T `e vertice del poliedro.

(b) Per τ = 0 l’origine degli assi `e vertice del poliedro.

(c) Per τ = 1 il punto (0, − 1, 3)T `e vertice del poliedro.

(d) L’origine degli assi `e vertice del poliedro per ogni valore di τ ∈ IR.

10. Sia dato un problema di Programmazione Lineare in forma standard con A =

 2 1 3 0 1 0

1 0 5 2 1 1



, c = (0, 1, 3, 1, 0, 1)T, b = (δ, 1)T Dire quali delle seguenti affermazioni sono corrette.

(a) Il punto ¯x = (1, δ − 2, 0, 0, 0, 0)T soddisfa il criterio di ottimalit`a per ogni valore di δ ≥ 2.

(b) La base formata dalla 2a e dalla 6a colonna `e una base ammissibile per ogni valore di δ ∈ IR.

(c) Per δ = 0 la base formata dalla 2a e dalla 5a colonna `e una base ammissibile.

(d) Non esiste nessuna base ammissibile in corrispondenza della quale il criterio di illimi- tatezza `e soddisfatto.

(13)

Prova scritta di Ricerca Operativa Corso di Laurea in

Ingegneria Informatica e Automatica

11 luglio 2011

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

(14)

1. Sia dato un problema di Programmazione Lineare nella forma min cTx

Ax = b x ≥ 0,

(con A matrice m × n) e si supponga che il problema sia ammissibile e che risulti rango(A) = m. Dire quali delle seguenti affermazioni sono corrette.

(a) Il numero delle iterazioni necessarie alla Fase II del metodo del simplesso per convergere ad una soluzione ottima `e minore o uguale ad m.

(b) Se il problema non `e illimitato inferiormente la Fase II del metodo del simplesso, in un numero finito di iterazioni, converge alla soluzione ottima.

(c) Se supponiamo che ogni soluzione di base ammissibile sia non degenere, allora non pu`o verificarsi il fenomeno del ciclaggio per la Fase II del metodo del simplesso.

(d) Nella sequenza delle basi generate durante la Fase II del metodo del simplesso una ripetizione non pu`o verificarsi se supponiamo che ogni soluzione di base ammissibile sia non degenere.

2. Sia dato l’insieme Π = {x ∈ IRn | aTx = b} con a ∈ IRn e b ∈ IR, a 6= 0, b 6= 0. Dire quali delle seguenti affermazioni sono corrette.

(a) Π `e un politopo.

(b) Π non ammette vertici.

(c) Π `e un insieme convesso.

(d) Π pu`o essere l’insieme ammissibile di un problema di Programmazione Lineare.

3. Sia dato il seguente problema

min 3x1+ 2x2+ x1x2 x1+ 2x2= 0 x1≥ 0, x2≥ 0.

Dire quali delle seguenti affermazioni sono corrette.

(a) Si tratta di un problema di Programmazione Lineare che ammette soluzione ottima.

(b) L’insieme ammissibile del problema `e costituito da infiniti punti distinti.

(c) L’insieme ammissibile del problema `e un poliedro che ammette sempre almeno un vertice.

(d) Il problema non `e un problema di Programmazione Lineare.

4. Dire quali delle seguenti affermazioni sono corrette.

(a) L’unione di due poliedri `e un insieme convesso.

(b) Un poliedro che contiene semirette non pu`o ammettere vertici.

(c) Non esistono poliedri che contengono rette.

(d) L’intersezione di due poliedri `e un insieme convesso.

5. Sia dato un problema di Programmazione Lineare in forma standard. Dire quali delle seguenti affermazioni sono corrette.

(15)

(a) La funzione obiettivo del problema artificiale che si risolve nella Fase I del metodo del simplesso all’ottimo vale sempre zero.

(b) La Fase I del metodo del simplesso permette di determinare se il problema `e ammissibile e se ci sono vincoli ridondanti.

(c) Il problema artificiale che si risolve nella Fase I del metodo del simplesso `e un problema di Programmazione Lineare che ammette soluzione ottima se e soltanto se il problema originario `e ammissibile.

(d) Se il problema originario `e illimitato allora il problema artificiale `e inammissibile.

6. Al termine della Fase I del metodo del simplesso applicato alla soluzione di un problema di Programmazione Lineare risulta xB = (α1, x2, α3, x4)T, xN = (α4, x3, x1, α2)T,

B−1N =

0 0 1 0

2 0 0 −1

5 9 3 7

3 −3 2 12

, B−1b =

 0 11

0 2

 .

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= (x3, x2, x4)T.

(c) Il problema originario `e ammissibile.

(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.

7. Si consideri il seguente problema di Programmazione Lineare (P):

max cTx Ax ≥ b,

con A matrice m × n. Dire quali delle seguenti affermazioni sono corrette.

(a) Il problema duale del problema (P) `e un problema di Programmazione Lineare con m variabili.

(b) Se l’insieme ammissibile del problema (P) `e vuoto, allora anche l’insieme ammissibile del problema duale `e vuoto.

(c) Se il problema (P) ammette ottimo (finito), il suo duale non pu`o essere illimitato.

(d) Il problema duale del problema (P) `e

max bTu ATu = c u ≥ 0 8. Si consideri il poliedro descritto dal seguente sistema

x1+ x2− x4 = 2

−x1+ x3+ x4 = 0 x1+ x2+ 7x3− x4 = 9

xi≥ 0, i = 1, . . . , 4 Dire quali delle seguenti affermazioni sono corrette.

(16)

(a) Il punto (0, 0, 1, − 2)T `e vertice del poliedro.

(b) Il punto (3, 0, 2, 1)T `e vertice del poliedro.

(c) Il punto (1, 1, 1, 0)T `e vertice del poliedro.

(d) Il poliedro non ammette vertici.

9. Sia dato un problema di Programmazione Lineare in forma standard con A =

 2 1 3 0 1 0

1 0 5 2 1 1



, c = (0, 1, 3, 1, 0, 1)T, b = (δ, 1)T Dire quali delle seguenti affermazioni sono corrette.

(a) Per δ = 0 la base formata dalla 2a e dalla 5a colonna `e una base ammissibile.

(b) Il punto ¯x = (1, δ − 2, 0, 0, 0, 0)T soddisfa il criterio di ottimalit`a per ogni valore di δ ≥ 2.

(c) La base formata dalla 2a e dalla 6a colonna `e una base ammissibile per ogni valore di δ ∈ IR.

(d) Non esiste nessuna base ammissibile in corrispondenza della quale il criterio di illimi- tatezza `e soddisfatto.

10. Si consideri il poliedro descritto dal seguente sistema

−τ x1+ 2x2+ x3 ≥ τ 2x1− τ x2− x3 ≥ −2

x1 ≥ 0 x3 ≥ 0, con τ ∈ IR. Dire quali delle seguenti affermazioni sono corrette.

(a) Per τ = 0 l’origine degli assi `e vertice del poliedro.

(b) L’origine degli assi `e vertice del poliedro per ogni valore di τ ∈ IR.

(c) Per τ = 1 il punto (0, − 1, 3)T `e vertice del poliedro.

(d) Per τ = 2 il punto (0, − 1, 0)T `e vertice del poliedro.

Riferimenti

Documenti correlati

• Per ogni affermazione VERO/FALSO NON correttamente individuata viene assegnato un punteggio negativo pari a -0.25 punti7. Supera la prova chi totalizza un punteggio pari ad almeno

• Per ogni affermazione VERO/FALSO NON correttamente individuata viene assegnato un punteggio negativo pari a -0.25 punti7. Supera la prova chi totalizza un punteggio pari ad almeno

(c) Il problema originario ` e ammissibile se e solo se il problema artificiale che si risolve nella Fase I del metodo del simplesso ammette ottimo finito. (d) Se ad una

(b) La regole anticiclaggio applicate alla Fase II garantiscono che in un numero finito di iterazioni ` e soddisfatto o il criterio di illimitatezza o il criterio di ottimalit` a..

• 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

• 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

(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

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