• 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!
8
0
0

Testo completo

(1)

Prova scritta di Ricerca Operativa Corso di Laurea in

Ingegneria Informatica e Automatica

14 novembre 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

(2)

1. Dato il problema primale (P )

max cTx Ax = b.

Quali tra le seguenti affermazioni risultano corrette ?

(a) Ad ogni punto del poliedro ammissibile di (P ) corrisponde uno ed un solo punto dell’insieme ammissibile di (D).

(b) Se l’insieme ammissibile di (P ) `e vuoto allora il problema (D) non pu`o essere illimitato superiormente.

(c) Il relativo problema duale `e

min −bTy

−ATy = c.

(d) Il relativo problema duale `e

max bTy ATy = −c.

2. Dire quali affermazioni risultano esatte:

(a) L’insieme P = {x ∈ IR3 : x1+ x2− x3= 4} `e un poliedro.

(b) Se poliedro ha un numero finito di vertici allora contiene un numero finito di punti.

(c) La funzione f (x) = 2x −23 `e lineare.

(d) Il vettore (−20, 3)T `e ortogonale alle rette del fascio 5x134x2= c, con c ∈ IR.

3. Sia data la funzione continua f (x) con f : IRn→ IR e l’insieme S ⊆ IRn, allora risulta (a) Se S `e vuoto allora il problema minx∈Sf (x) `e illimitato inferiormente.

(b) Il problema minx∈Sf (x) `e un problema di Programmazione Matematica se e solo se S

`e convesso.

(c) maxx∈Sf (x) = minx∈S[f (−x)].

(d) Se S contiene almeno un punto allora `e convesso.

4. Sia dato il seguente problema di Programmazione Lineare (PL) min −x1+ 2x2

x2− 2x3+ x5= 2 3x1− 5x2+ x4− x6= 4 x ≥ 0.

Quali tra le seguenti affermazioni risultano corrette ?

(a) La SBA corrispondente non soddisfa il criterio di ottimalit`a e la variabile x1`e candidata ad entrare in base.

(b) Il punto (0, 0, 0, 4, 2, 0)T `e un vertice del poliedro ammissibile.

(c) PL `e in forma canonica e la SBA corrente `e degenere.

(d) La SBA corrispondente soddisfa il criterio di ottimalit`a.

5. Quali tra le seguenti affermazioni risultano corrette al termine della Fase I del metodo del Simplesso?

(a) Se il problema originale `e in forma canonica, allora il problema artificiale ha tante vari- abili quante il problema originale.

(3)

(b) Il problema originale `e ammissibile se e solo se il problema artificiale `e ammissibile.

(c) Il duale del problema artificiale `e il problema originale e viceversa.

(d) Il problema artificiale non pu`o ammettere l’origine come soluzione.

6. Si consideri il poliedro P : {x ∈ IR4 : Ax = b}, in cui A ∈ IR4×4. Dire quali delle seguenti affermazioni sono vere:

(a) Se rango(A) = 4 allora l’origine `e sicuramente ammissibile per P ed `e anche un vertice.

(b) Se rango(A) = 2 allora il poliedro non ammette vertici.

(c) P ammette sicuramente un vertice se rango(A) > 4.

(d) Se rango(A) < 4 allora P `e senz’altro un poliedro ma non un politopo.

7. Dire quali tra le seguenti affermazioni risultano corrette:

(a) L’intersezione di due politopi non pu`o contenere un numero infinito di punti.

(b) L’insieme ammissibile dato da P = {x ∈ IRn , a1x1 + · · · + anxn = 3}, con a = (a1· · · an) ∈ IRn, a 6= 0, non pu`o essere un politopo.

(c) Ogni insieme convesso non vuoto contiene sempre infiniti punti.

(d) Un poliedro che contiene un numero finito di punti `e senz’altro un politopo.

8. Si consideri la Fase II del metodo del simplesso per la soluzione di un problema di Program- mazione Lineare. Dire quali affermazioni risultano corrette:

(a) Il criterio di ottimalit`a fornisce una condizione solo necessaria.

(b) Se alla SBA corrente corrisponde il valore ottimo della funzione obiettivo, allora γ ≥ 0.

(c) Se la SBA corrente `e degenere e verifica il criterio di ottimalit`a, allora almeno una componente in base `e non nulla.

(d) Se P = {x ∈ IRn : Ax = b, x ≥ 0} `e l’insieme ammissibile e la SBA corrente verifica il criterio di ottimalit`a, allora nessuna colonna della matrice di A contiene solo elementi non positivi.

9. Si abbia al termine della Fase I del metodo del Simplesso la seguente SBA xB= (α2, x1, α3)T, xN = (α1, x2, x4, x3)T,

B−1N =

5 0 −1 9

3 1 1 −4

−1 −2 0 0

, B−1b =

 0 0 0

.

Dire quali affermazioni sono corrette:

(a) Il problema originale `e ammissibile.

(b) Il problema artificiale `e inammissibile.

(c) `E possibile effettuare uno scambio degenere tra la variabile α2 e la variabile x2. (d) L’origine `e una SBA del problema originale.

10. Sia dato il seguente poliedro P

−x1− 3x2+ 6x4+ x5= 4

−7x1− x2+ 2x3− 3x4+ x5= −2 x ≥ 0.

Quali tra le seguenti affermazioni risultano corrette ?

(4)

(a) Il punto (13, 0, 0, 0,133)T appartiene a P .

(b) Nell’origine vi sono 5 vincoli attivi linearmente indipendenti del poliedro.

(c) Il punto (0, 0, 0, 1, − 2)T `e vertice di P . (d) Il poliedro P ammette al pi`u

7!

2!(7 − 2)!

vertici.

(5)

Prova scritta di Ricerca Operativa Corso di Laurea in

Ingegneria Informatica e Automatica

14 novembre 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

(6)

1. Si consideri la Fase II del metodo del simplesso per la soluzione di un problema di Program- mazione Lineare. Dire quali affermazioni risultano corrette:

(a) Il criterio di ottimalit`a fornisce una condizione solo necessaria.

(b) Se la SBA corrente `e degenere e verifica il criterio di ottimalit`a, allora almeno una componente in base `e non nulla.

(c) Se P = {x ∈ IRn : Ax = b, x ≥ 0} `e l’insieme ammissibile e la SBA corrente verifica il criterio di ottimalit`a, allora nessuna colonna della matrice di A contiene solo elementi non positivi.

(d) Se alla SBA corrente corrisponde il valore ottimo della funzione obiettivo, allora γ ≥ 0.

2. Sia dato il seguente problema di Programmazione Lineare (PL) min −x1+ 2x2

x2− 2x3+ x5= 2 3x1− 5x2+ x4− x6= 4 x ≥ 0.

Quali tra le seguenti affermazioni risultano corrette ?

(a) Il punto (0, 0, 0, 4, 2, 0)T `e un vertice del poliedro ammissibile.

(b) PL `e in forma canonica e la SBA corrente `e degenere.

(c) La SBA corrispondente non soddisfa il criterio di ottimalit`a e la variabile x1`e candidata ad entrare in base.

(d) La SBA corrispondente soddisfa il criterio di ottimalit`a.

3. Quali tra le seguenti affermazioni risultano corrette al termine della Fase I del metodo del Simplesso?

(a) Il problema originale `e ammissibile se e solo se il problema artificiale `e ammissibile.

(b) Il duale del problema artificiale `e il problema originale e viceversa.

(c) Se il problema originale `e in forma canonica, allora il problema artificiale ha tante vari- abili quante il problema originale.

(d) Il problema artificiale non pu`o ammettere l’origine come soluzione.

4. Dire quali tra le seguenti affermazioni risultano corrette:

(a) Ogni insieme convesso non vuoto contiene sempre infiniti punti.

(b) Un poliedro che contiene un numero finito di punti `e senz’altro un politopo.

(c) L’intersezione di due politopi non pu`o contenere un numero infinito di punti.

(d) L’insieme ammissibile dato da P = {x ∈ IRn , a1x1 + · · · + anxn = 3}, con a = (a1· · · an) ∈ IRn, a 6= 0, non pu`o essere un politopo.

5. Si abbia al termine della Fase I del metodo del Simplesso la seguente SBA xB= (α2, x1, α3)T, xN = (α1, x2, x4, x3)T,

B−1N =

5 0 −1 9

3 1 1 −4

−1 −2 0 0

, B−1b =

 0 0 0

.

Dire quali affermazioni sono corrette:

(7)

(a) Il problema originale `e ammissibile.

(b) Il problema artificiale `e inammissibile.

(c) `E possibile effettuare uno scambio degenere tra la variabile α2 e la variabile x2. (d) L’origine `e una SBA del problema originale.

6. Sia dato il seguente poliedro P

−x1− 3x2+ 6x4+ x5= 4

−7x1− x2+ 2x3− 3x4+ x5= −2 x ≥ 0.

Quali tra le seguenti affermazioni risultano corrette ? (a) Il punto (13, 0, 0, 0,133)T appartiene a P .

(b) Nell’origine vi sono 5 vincoli attivi linearmente indipendenti del poliedro.

(c) Il punto (0, 0, 0, 1, − 2)T `e vertice di P . (d) Il poliedro P ammette al pi`u

7!

2!(7 − 2)!

vertici.

7. Dato il problema primale (P )

max cTx Ax = b.

Quali tra le seguenti affermazioni risultano corrette ?

(a) Ad ogni punto del poliedro ammissibile di (P ) corrisponde uno ed un solo punto dell’insieme ammissibile di (D).

(b) Se l’insieme ammissibile di (P ) `e vuoto allora il problema (D) non pu`o essere illimitato superiormente.

(c) Il relativo problema duale `e

min −bTy

−ATy = c.

(d) Il relativo problema duale `e

max bTy ATy = −c.

8. Dire quali affermazioni risultano esatte:

(a) L’insieme P = {x ∈ IR3 : x1+ x2− x3= 4} `e un poliedro.

(b) Se poliedro ha un numero finito di vertici allora contiene un numero finito di punti.

(c) La funzione f (x) = 2x −23 `e lineare.

(d) Il vettore (−20, 3)T `e ortogonale alle rette del fascio 5x134x2= c, con c ∈ IR.

9. Si consideri il poliedro P : {x ∈ IR4 : Ax = b}, in cui A ∈ IR4×4. Dire quali delle seguenti affermazioni sono vere:

(a) P ammette sicuramente un vertice se rango(A) > 4.

(b) Se rango(A) < 4 allora P `e senz’altro un poliedro ma non un politopo.

(8)

(c) Se rango(A) = 4 allora l’origine `e sicuramente ammissibile per P ed `e anche un vertice.

(d) Se rango(A) = 2 allora il poliedro non ammette vertici.

10. Sia data la funzione continua f (x) con f : IRn→ IR e l’insieme S ⊆ IRn, allora risulta (a) Se S `e vuoto allora il problema minx∈Sf (x) `e illimitato inferiormente.

(b) Il problema minx∈Sf (x) `e un problema di Programmazione Matematica se e solo se S

`e convesso.

(c) maxx∈Sf (x) = minx∈S[f (−x)].

(d) Se S contiene almeno un punto allora `e convesso.

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) 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

(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