Prova scritta di Ricerca Operativa Corso di Laurea in
Ingegneria Informatica e Automatica
14 settembre 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. Dato il seguente problema (P) di programmazione matematica max
x∈S f (x) Dire quali tra le seguenti affermazioni risultano corrette.
(a) Se S = {x ∈ IR : x ≤ −1} ed f (x) = costante, ∀x ∈ S, allora (P) `e illimitato inferior- mente.
(b) Se (P) ammette la soluzione x∗, questa `e anche soluzione del problema
− min
x∈S[−f (x)]
(c) Se S `e limitato allora (P) `e limitato.
(d) Se f (x) = costante, ∀x ∈ S, allora (P) ammette un’unica soluzione.
2. Quali tra le seguenti affermazioni risultano corrette.
(a) La funzione reale di variabile reale f (x) = x + |x| `e lineare.
(b) La funzione reale di variabile reale f (x, y) = cos(π)xy + 3x `e lineare.
(c) La funzione f (x) = 0, ∀x ∈ IR `e una funzione lineare.
(d) Siano dati a ∈ IR2 e la costante c ∈ IR.
aTx = c
rappresenta una famiglia di rette ortogonali al vettore a.
3. Dire quali delle seguenti affermazioni sono corrette:
(a) L’insieme {(x, y) ∈ IR2 : y > |x|, y ≤ 3} `e un insieme convesso.
(b) L’insieme {(x, y) ∈ IR2 : y > x} non contiene rette.
(c) L’unione e l’intersezione di un insieme convesso con l’insieme vuoto sono sempre convesse.
(d) Un insieme convesso pu`o ammettere un numero infinito di vertici, un poliedro no.
4. Dire quali delle seguenti affermazioni sono corrette:
(a) L’intersezione di due semirette distinte `e un poliedro.
(b) L’insieme ammissibile di un problema di PL `e sempre un politopo.
(c) L’intersezione di un poliedro ed un politopo `e un poliedro.
(d) L’intersezione di un poliedro ed un politopo `e un politopo.
5. Sia dato l’insieme P = {x ∈ IRn : Ax ≥ b}, con A ∈ IRm×n. Dire quali delle seguenti affermazioni sono vere:
(a) Se b = 0 allora P contiene certamente rette.
(b) Per alcuni valori dei coefficienti di A, P non `e convesso.
(c) Se P contiene almeno un vertice allora `e senz’altro m ≥ n.
(d) Se P contiene rette allora `e senz’altro m ≤ n.
6. Dire quali delle seguenti affermazioni sono vere:
(a) L’insieme delle soluzioni di un problema di PL `e convesso.
(b) Dato un problema di PL in cui il poliedro ammissibile `e non vuoto, se esso non ammette soluzione ottima allora il poliedro ammissibile non ammette vertici.
(c) Un poliedro non vuoto ammette sempre almeno un vertice.
(d) Se l’insieme ammissibile di un problema di PL contiene semirette allora non contiene vertici.
7. Si consideri la Fase I del metodo del Simplesso per un problema in forma Standard. Quali tra le seguenti affermazioni risultano corrette ?
(a) Il problema originale ed il problema ausiliario non possono essere entrambi inammissibili.
(b) Il problema originale ed il problema ausiliario non possono essere entrambi illimitati.
(c) Se il problema originale `e inammissibile allora il problema ausiliario ammette soluzione ottima.
(d) In un numero finito di iterazioni della Fase II del metodo del Simplesso, applicata al prob- lema ausiliario, `e possibile calcolare il rango della matrice dei coefficienti del problema originale.
8. Sia dato il seguente poliedro P
x1− 2x2− 3x3= 0 x2+ x3− 6x4= −12 5x2= 0
x ≥ 0.
Quali tra le seguenti affermazioni risultano corrette ? (a) P `e vuoto.
(b) Nell’origine sono attivi esattamente sei vincoli.
(c) Il punto (0, 0, 0, 2)T `e un vertice di P . (d) Il punto (1, 1, 0, 2)T `e un vertice di P .
9. Si consideri l’iterazione corrente della Fase II del metodo del simplesso, per un problema di Programmazione Lineare in forma di minimizzazione. Siano xB = (x1, x7, x3) e xN = (x4, x2, x6, x5):
B−1N =
−τ 3 − τ 1 −τ2
τ 2 −6 −τ4
0 0 1 − τ 0
, B−1b =
1 0 τ2
, γ =
0
−τ2 1
−τ2
,
dove τ `e un parametro reale. Quali delle seguenti affermazioni sono corrette ? (a) Per ogni valore di τ la SBA corrente soddisfa il criterio di ottimalit`a.
(b) La SBA corrente `e degenere se e solo se τ = 0.
(c) `E possibile concludere che per τ = 0 il problema `e illimitato inferiormente.
(d) Se τ < 0 non `e soddisfatto il criterio di ottimalit`a.
10. Al termine della Fase I del metodo del Simplesso si ha la seguente SBA xB = (α1, α2, α3)T, xN = (x2, x1, α4, x3)T,
B−1N =
1.5 14 −1.5 1
0 0 0 1
3 −4 11 1
, B−1b =
0 0 0
. Dire quali affermazioni sono corrette:
(a) Esiste un solo vincolo ridondante.
(b) Esiste una SBA di partenza per la Fase II del metodo del Simplesso.
(c) Il problema ausiliario ammette soluzione ottima.
(d) Il problema originale `e ammissibile.
Prova scritta di Ricerca Operativa Corso di Laurea in
Ingegneria Informatica e Automatica
14 settembre 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. Quali tra le seguenti affermazioni risultano corrette.
(a) La funzione f (x) = 0, ∀x ∈ IR `e una funzione lineare.
(b) Siano dati a ∈ IR2 e la costante c ∈ IR.
aTx = c
rappresenta una famiglia di rette ortogonali al vettore a.
(c) La funzione reale di variabile reale f (x) = x + |x| `e lineare.
(d) La funzione reale di variabile reale f (x, y) = cos(π)xy + 3x `e lineare.
2. Dire quali delle seguenti affermazioni sono corrette:
(a) L’unione e l’intersezione di un insieme convesso con l’insieme vuoto sono sempre convesse.
(b) Un insieme convesso pu`o ammettere un numero infinito di vertici, un poliedro no.
(c) L’insieme {(x, y) ∈ IR2 : y > |x|, y ≤ 3} `e un insieme convesso.
(d) L’insieme {(x, y) ∈ IR2 : y > x} non contiene rette.
3. Dato il seguente problema (P) di programmazione matematica maxx∈S f (x)
Dire quali tra le seguenti affermazioni risultano corrette.
(a) Se S `e limitato allora (P) `e limitato.
(b) Se f (x) = costante, ∀x ∈ S, allora (P) ammette un’unica soluzione.
(c) Se S = {x ∈ IR : x ≤ −1} ed f (x) = costante, ∀x ∈ S, allora (P) `e illimitato inferior- mente.
(d) Se (P) ammette la soluzione x∗, questa `e anche soluzione del problema
− min
x∈S[−f (x)]
4. Dire quali delle seguenti affermazioni sono corrette:
(a) L’intersezione di un poliedro ed un politopo `e un poliedro.
(b) L’intersezione di un poliedro ed un politopo `e un politopo.
(c) L’intersezione di due semirette distinte `e un poliedro.
(d) L’insieme ammissibile di un problema di PL `e sempre un politopo.
5. Dire quali delle seguenti affermazioni sono vere:
(a) Un poliedro non vuoto ammette sempre almeno un vertice.
(b) Se l’insieme ammissibile di un problema di PL contiene semirette allora non contiene vertici.
(c) L’insieme delle soluzioni di un problema di PL `e convesso.
(d) Dato un problema di PL in cui il poliedro ammissibile `e non vuoto, se esso non ammette soluzione ottima allora il poliedro ammissibile non ammette vertici.
6. Si consideri la Fase I del metodo del Simplesso per un problema in forma Standard. Quali tra le seguenti affermazioni risultano corrette ?
(a) Se il problema originale `e inammissibile allora il problema ausiliario ammette soluzione ottima.
(b) In un numero finito di iterazioni della Fase II del metodo del Simplesso, applicata al prob- lema ausiliario, `e possibile calcolare il rango della matrice dei coefficienti del problema originale.
(c) Il problema originale ed il problema ausiliario non possono essere entrambi inammissibili.
(d) Il problema originale ed il problema ausiliario non possono essere entrambi illimitati.
7. Sia dato l’insieme P = {x ∈ IRn : Ax ≥ b}, con A ∈ IRm×n. Dire quali delle seguenti affermazioni sono vere:
(a) Se P contiene almeno un vertice allora `e senz’altro m ≥ n.
(b) Se P contiene rette allora `e senz’altro m ≤ n.
(c) Se b = 0 allora P contiene certamente rette.
(d) Per alcuni valori dei coefficienti di A, P non `e convesso.
8. Si consideri l’iterazione corrente della Fase II del metodo del simplesso, per un problema di Programmazione Lineare in forma di minimizzazione. Siano xB = (x1, x7, x3) e xN = (x4, x2, x6, x5):
B−1N =
−τ 3 − τ 1 −τ2
τ 2 −6 −τ4
0 0 1 − τ 0
, B−1b =
1 0 τ2
, γ =
0
−τ2 1
−τ2
,
dove τ `e un parametro reale. Quali delle seguenti affermazioni sono corrette ? (a) `E possibile concludere che per τ = 0 il problema `e illimitato inferiormente.
(b) Se τ < 0 non `e soddisfatto il criterio di ottimalit`a.
(c) Per ogni valore di τ la SBA corrente soddisfa il criterio di ottimalit`a.
(d) La SBA corrente `e degenere se e solo se τ = 0.
9. Al termine della Fase I del metodo del Simplesso si ha la seguente SBA xB = (α1, α2, α3)T, xN = (x2, x1, α4, x3)T,
B−1N =
1.5 14 −1.5 1
0 0 0 1
3 −4 11 1
, B−1b =
0 0 0
. Dire quali affermazioni sono corrette:
(a) Il problema ausiliario ammette soluzione ottima.
(b) Il problema originale `e ammissibile.
(c) Esiste un solo vincolo ridondante.
(d) Esiste una SBA di partenza per la Fase II del metodo del Simplesso.
10. Sia dato il seguente poliedro P
x1− 2x2− 3x3= 0 x2+ x3− 6x4= −12 5x2= 0
x ≥ 0.
Quali tra le seguenti affermazioni risultano corrette ?
(a) Il punto (0, 0, 0, 2)T `e un vertice di P . (b) Il punto (1, 1, 0, 2)T `e un vertice di P . (c) P `e vuoto.
(d) Nell’origine sono attivi esattamente sei vincoli.
