Prova scritta di Ricerca Operativa Corsi di Laurea in
Ingegneria Informatica e Ingegneria Automatica
8 settembre 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
1. Sia a ∈ <n e b ∈ <.
(a) L’insieme {x ∈ <n | aTx = b} `e un iperpiano
(b) Se n = 2 e F = {x ∈ <2| 2x1− 3x2= 5}, F rappresenta una retta e il vettore (−4 , 6)T
`e ortogonale alla retta F .
(c) Data la funzione f (x1, x2) = c1x1+ c2x2, il vettore (c1, c2)T rappresenta una direzione di crescita per la funzione f .
(d) L’insieme {x ∈ <n | aTx = b} `e un poliedro.
2. Sia dato l’insieme H = {x ∈ <n | Ax = b, x ≥ 0} con A matrice m × n e b ∈ <m.
(a) H `e un poliedro che rappresenta l’insieme ammissibile di un problema di PL in forma standard se e solo A ha rango massimo.
(b) `E sempre possibile scrivere l’insieme ammissibile di un problema di PL come l’insieme H.
(c) H non pu`o contenere semirette.
(d) Se H `e non vuoto, allora ammette sempre almeno un vertice.
3. Sia dato un problema di minimizzazione
min f (x) x ∈ P con P poliedro di <n e f : <n→ <.
(a) Se f (x) =Pn
i=1cixi, con ci∈ <, allora al problema si applica il teorema fondamentale della programmazione lineare
(b) Se P `e un politopo, allora il problema ammette sempre soluzione ottima.
(c) Se P `e non vuoto e non contiene rette, allora esiste sempre un vertice di P che `e soluzione ottima del problema.
(d) Se n = 3 e f (x) = 3x1+ 2x1x2− 3x3 e P `e un politopo, allora il problema ammette sempre soluzione ottima.
4. Dato il poliedro definito dal sistema
3x1+ x2− x4 ≥ 2
−x2− 2x3 ≤ −2 x1+ 2x2+ x3 ≥ 2
x ≥ 0
(a) Il punto (1, 0, 1, 1)T `e un vertice del poliedro.
(b) L’origine `e un vertice del poliedro.
(c) Il punto (1, 0, 0, 1)T `e un vertice del poliedro.
(d) Il punto (1, 2, 1, 1)T appartiene al poliedro.
5. Sia dato un problema di Programmazione Lineare al quale si applica il metodo del simplesso.
(a) Le regole anticiclaggio applicate nella Fase II garantiscono che se il problema non `e illimitato, allora in un numero finito di iterazioni si ha convergenza alla soluzione ottima.
(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.
(c) Il criterio di ottimalit`a `e solo sufficiente e quindi se una soluzione di base corrente non
`e ottima allora il criterio non pu`o essere soddisfatto.
(d) La Fase I del metodo del simplesso permette sempre di ottenere una base ammissibile dalla quale far partire la Fase II.
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) Si ha sempre B−1b − B−1N xN ≥ 0.
(b) Lo scalare ¯ρ che si calcola nel criterio del rapporto minimo `e nullo se e solo se la SBA corrente `e degenere.
(c) Nell’ipotesi di non degeneratezza, data una base B esiste un’unica SBA associata e viceversa.
(d) Se per ogni i = 1, . . . , m risulta πi ≥ 0, allora il problema non pu`o essere illimitato inferiormente.
7. Arrivati all’ottimo del problema artificiale che si risolve nella Fase I del metodo del simplesso abbiamo che risulta xB= (α1, x1, α3, x3), xN = (α2, x2, α4, x4),
B−1b =
0 1 β 1
, B−1N =
3 0 7 β
0 −1 15 17
12 0 12 19
1 1 0 3
Conβ ∈ <. Allora
(a) Il problema originario `e ammissibile se e solo se risulta β = 0 e si ha che nel problema originario c’`e un vincolo ridondante.
(b) Non esistono valori di β per cui il problema originario non `e ammissibile.
(c) Se β 6= 0, allora una possibile base ammissibile per il problema originario dalla quale far partire la Fase II corrisponde ad avere variabili di base xB= (x1, x4, x3).
(d) Se il problema orginario `e ammissibile, una possibile base ammissibile per il problema originario dalla quale far partire la Fase II corrisponde ad avere variabili di base xB = (x1, x4, x3).
8. Ad una iterazione della Fase II del metodo del simplesso applicato ad un problema di mini- mizzazione si ha: xB= (x1, x3, x5)T, xN = (x4, x2, x6)T,
B−1N =
1 0 −1
3 1 0
2 0 −3
.
Il vettore dei costi ridotti `e γ = (1, − 1, 0)T. Sia ¯x = (1, 0, 1, 1, 0, 0)T la soluzione base ammissibile corrente in cui la funzione obiettivo vale 25.
(a) La SBA corrente soddisfa il criterio di ottimalit`a.
(b) La SBA corrente soddisfa il criterio di illimitatezza.
(c) Il valore della funzione obiettivo nel punto ammissibile ¯y = (1, 0, 1, 1, 1, 1)T`e maggiore di 25.
(d) Vale cTBB−1b = 25.
9. Sia dato il seguente poliedro
2x1+ x2− x4 = 1 x1+ 3x3 = 4 τ x2+ x3+ x4 = 2
x ≥ 0
(a) Il punto (1, 0, 1, 1)T `e un vertice per ogni valore di τ .
(b) Esistono valori di τ per i quali il punto (1, 1, 1, 1)T `e una SBA (c) Per τ = −1 il punto (1, − 1, 1, 0)T `e una SBA.
(d) L’origine `e una SBA.
10. Sia dato il problema
(P )
min cTx Ax ≤ b x ≥ 0 (a) Il suo duale `e
min bTu
−ATu ≤ c u ≥ 0
(b) Se entrambi i problemi (primale e duale) ammettono soluzioni ammissibili, allora nessuno dei due problemi potr`a essere illimitato.
(c) Se il problema (P) `e inammissibile allora il suo duale `e illimitato.
(d) Non pu`o accadere che entrambe i problemi (primale e duale) siano inammissibili.
Prova scritta di Ricerca Operativa Corsi di Laurea in
Ingegneria Informatica e Ingegneria Automatica
8 settembre 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
1. Sia dato un problema di PL in forma standard, e sia B una base ammissibile e N la matrice delle colonne fuori base.
(a) Si ha sempre B−1b − B−1N xN ≥ 0.
(b) Lo scalare ¯ρ che si calcola nel criterio del rapporto minimo `e nullo se e solo se la SBA corrente `e degenere.
(c) Nell’ipotesi di non degeneratezza, data una base B esiste un’unica SBA associata e viceversa.
(d) Se per ogni i = 1, . . . , m risulta πi ≥ 0, allora il problema non pu`o essere illimitato inferiormente.
2. Ad una iterazione della Fase II del metodo del simplesso applicato ad un problema di mini- mizzazione si ha: xB= (x1, x3, x5)T, xN = (x4, x2, x6)T,
B−1N =
1 0 −1
3 1 0
2 0 −3
.
Il vettore dei costi ridotti `e γ = (1, − 1, 0)T. Sia ¯x = (1, 0, 1, 1, 0, 0)T la soluzione base ammissibile corrente in cui la funzione obiettivo vale 25.
(a) Il valore della funzione obiettivo nel punto ammissibile ¯y = (1, 0, 1, 1, 1, 1)T`e maggiore di 25.
(b) Vale cTBB−1b = 25.
(c) La SBA corrente soddisfa il criterio di ottimalit`a.
(d) La SBA corrente soddisfa il criterio di illimitatezza.
3. Sia dato il seguente poliedro
2x1+ x2− x4 = 1 x1+ 3x3 = 4 τ x2+ x3+ x4 = 2
x ≥ 0
(a) Esistono valori di τ per i quali il punto (1, 1, 1, 1)T `e una SBA (b) Il punto (1, 0, 1, 1)T `e un vertice per ogni valore di τ .
(c) Per τ = −1 il punto (1, − 1, 1, 0)T `e una SBA.
(d) L’origine `e una SBA.
4. Sia a ∈ <n e b ∈ <.
(a) L’insieme {x ∈ <n | aTx = b} `e un iperpiano (b) L’insieme {x ∈ <n | aTx = b} `e un poliedro.
(c) Se n = 2 e F = {x ∈ <2| 2x1− 3x2= 5}, F rappresenta una retta e il vettore (−4 , 6)T
`e ortogonale alla retta F .
(d) Data la funzione f (x1, x2) = c1x1+ c2x2, il vettore (c1, c2)T rappresenta una direzione di crescita per la funzione f .
5. Dato il poliedro definito dal sistema
3x1+ x2− x4 ≥ 2
−x2− 2x3 ≤ −2 x1+ 2x2+ x3 ≥ 2
x ≥ 0
(a) Il punto (1, 0, 0, 1)T `e un vertice del poliedro.
(b) Il punto (1, 2, 1, 1)T appartiene al poliedro.
(c) Il punto (1, 0, 1, 1)T `e un vertice del poliedro.
(d) L’origine `e un vertice del poliedro.
6. Arrivati all’ottimo del problema artificiale che si risolve nella Fase I del metodo del simplesso abbiamo che risulta xB= (α1, x1, α3, x3), xN = (α2, x2, α4, x4),
B−1b =
0 1 β 1
, B−1N =
3 0 7 β
0 −1 15 17
12 0 12 19
1 1 0 3
Conβ ∈ <. Allora
(a) Se β 6= 0, allora una possibile base ammissibile per il problema originario dalla quale far partire la Fase II corrisponde ad avere variabili di base xB= (x1, x4, x3).
(b) Se il problema orginario `e ammissibile, una possibile base ammissibile per il problema originario dalla quale far partire la Fase II corrisponde ad avere variabili di base xB = (x1, x4, x3).
(c) Il problema originario `e ammissibile se e solo se risulta β = 0 e si ha che nel problema originario c’`e un vincolo ridondante.
(d) Non esistono valori di β per cui il problema originario non `e ammissibile.
7. Sia dato l’insieme H = {x ∈ <n | Ax = b, x ≥ 0} con A matrice m × n e b ∈ <m.
(a) H `e un poliedro che rappresenta l’insieme ammissibile di un problema di PL in forma standard se e solo A ha rango massimo.
(b) H non pu`o contenere semirette.
(c) Se H `e non vuoto, allora ammette sempre almeno un vertice.
(d) `E sempre possibile scrivere l’insieme ammissibile di un problema di PL come l’insieme H.
8. Sia dato un problema di minimizzazione
min f (x) x ∈ P con P poliedro di <n e f : <n→ <.
(a) Se P `e non vuoto e non contiene rette, allora esiste sempre un vertice di P che `e soluzione ottima del problema.
(b) Se f (x) =Pn
i=1cixi, con ci∈ <, allora al problema si applica il teorema fondamentale della programmazione lineare
(c) Se P `e un politopo, allora il problema ammette sempre soluzione ottima.
(d) Se n = 3 e f (x) = 3x1+ 2x1x2− 3x3 e P `e un politopo, allora il problema ammette sempre soluzione ottima.
9. Sia dato un problema di Programmazione Lineare al quale si applica il metodo del simplesso.
(a) Il criterio di ottimalit`a `e solo sufficiente e quindi se una soluzione di base corrente non
`e ottima allora il criterio non pu`o essere soddisfatto.
(b) La Fase I del metodo del simplesso permette sempre di ottenere una base ammissibile dalla quale far partire la Fase II.
(c) Le regole anticiclaggio applicate nella Fase II garantiscono che se il problema non `e illimitato, allora in un numero finito di iterazioni si ha convergenza alla soluzione ottima.
(d) 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.
10. Sia dato il problema
(P )
min cTx Ax ≤ b x ≥ 0 (a) Il suo duale `e
min bTu
−ATu ≤ c u ≥ 0
(b) Non pu`o accadere che entrambe i problemi (primale e duale) siano inammissibili.
(c) Se entrambi i problemi (primale e duale) ammettono soluzioni ammissibili, allora nessuno dei due problemi potr`a essere illimitato.
(d) Se il problema (P) `e inammissibile allora il suo duale `e illimitato.
Prova scritta di Ricerca Operativa Corsi di Laurea in
Ingegneria Informatica e Ingegneria Automatica
8 settembre 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
1. Sia dato un problema di minimizzazione
min f (x) x ∈ P con P poliedro di <n e f : <n→ <.
(a) Se f (x) =Pn
i=1cixi, con ci∈ <, allora al problema si applica il teorema fondamentale della programmazione lineare
(b) Se n = 3 e f (x) = 3x1+ 2x1x2− 3x3 e P `e un politopo, allora il problema ammette sempre soluzione ottima.
(c) Se P `e un politopo, allora il problema ammette sempre soluzione ottima.
(d) Se P `e non vuoto e non contiene rette, allora esiste sempre un vertice di P che `e soluzione ottima del problema.
2. Sia dato il seguente poliedro
2x1+ x2− x4 = 1 x1+ 3x3 = 4 τ x2+ x3+ x4 = 2
x ≥ 0
(a) Il punto (1, 0, 1, 1)T `e un vertice per ogni valore di τ . (b) L’origine `e una SBA.
(c) Esistono valori di τ per i quali il punto (1, 1, 1, 1)T `e una SBA (d) Per τ = −1 il punto (1, − 1, 1, 0)T `e una SBA.
3. Dato il poliedro definito dal sistema
3x1+ x2− x4 ≥ 2
−x2− 2x3 ≤ −2 x1+ 2x2+ x3 ≥ 2
x ≥ 0
(a) Il punto (1, 0, 1, 1)T `e un vertice del poliedro.
(b) Il punto (1, 2, 1, 1)T appartiene al poliedro.
(c) L’origine `e un vertice del poliedro.
(d) Il punto (1, 0, 0, 1)T `e un vertice del poliedro.
4. Sia dato un problema di PL in forma standard, e sia B una base ammissibile e N la matrice delle colonne fuori base.
(a) Lo scalare ¯ρ che si calcola nel criterio del rapporto minimo `e nullo se e solo se la SBA corrente `e degenere.
(b) Si ha sempre B−1b − B−1N xN ≥ 0.
(c) Nell’ipotesi di non degeneratezza, data una base B esiste un’unica SBA associata e viceversa.
(d) Se per ogni i = 1, . . . , m risulta πi ≥ 0, allora il problema non pu`o essere illimitato inferiormente.
5. Sia a ∈ <n e b ∈ <.
(a) L’insieme {x ∈ <n | aTx = b} `e un iperpiano (b) L’insieme {x ∈ <n | aTx = b} `e un poliedro.
(c) Se n = 2 e F = {x ∈ <2| 2x1− 3x2= 5}, F rappresenta una retta e il vettore (−4 , 6)T
`e ortogonale alla retta F .
(d) Data la funzione f (x1, x2) = c1x1+ c2x2, il vettore (c1, c2)T rappresenta una direzione di crescita per la funzione f .
6. Sia dato un problema di Programmazione Lineare al quale si applica il metodo del simplesso.
(a) Le regole anticiclaggio applicate nella Fase II garantiscono che se il problema non `e illimitato, allora in un numero finito di iterazioni si ha convergenza alla soluzione ottima.
(b) Il criterio di ottimalit`a `e solo sufficiente e quindi se una soluzione di base corrente non
`e ottima allora il criterio non pu`o essere soddisfatto.
(c) La Fase I del metodo del simplesso permette sempre di ottenere una base ammissibile dalla quale far partire la
(d) 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.
Fase II.
7. Sia dato l’insieme H = {x ∈ <n | Ax = b, x ≥ 0} con A matrice m × n e b ∈ <m. (a) H non pu`o contenere semirette.
(b) Se H `e non vuoto, allora ammette sempre almeno un vertice.
(c) H `e un poliedro che rappresenta l’insieme ammissibile di un problema di PL in forma standard se e solo A ha rango massimo.
(d) `E sempre possibile scrivere l’insieme ammissibile di un problema di PL come l’insieme H.
8. Arrivati all’ottimo del problema artificiale che si risolve nella Fase I del metodo del simplesso abbiamo che risulta xB= (α1, x1, α3, x3), xN = (α2, x2, α4, x4),
B−1b =
0 1 β 1
, B−1N =
3 0 7 β
0 −1 15 17
12 0 12 19
1 1 0 3
Conβ ∈ <. Allora
(a) Non esistono valori di β per cui il problema originario non `e ammissibile.
(b) Se β 6= 0, allora una possibile base ammissibile per il problema originario dalla quale far partire la Fase II corrisponde ad avere variabili di base xB= (x1, x4, x3).
(c) Se il problema orginario `e ammissibile, una possibile base ammissibile per il problema originario dalla quale far partire la Fase II corrisponde ad avere variabili di base xB = (x1, x4, x3).
(d) Il problema originario `e ammissibile se e solo se risulta β = 0 e si ha che nel problema originario c’`e un vincolo ridondante.
9. Ad una iterazione della Fase II del metodo del simplesso applicato ad un problema di mini- mizzazione si ha: xB= (x1, x3, x5)T, xN = (x4, x2, x6)T,
B−1N =
1 0 −1
3 1 0
2 0 −3
.
Il vettore dei costi ridotti `e γ = (1, − 1, 0)T. Sia ¯x = (1, 0, 1, 1, 0, 0)T la soluzione base ammissibile corrente in cui la funzione obiettivo vale 25.
(a) La SBA corrente soddisfa il criterio di illimitatezza.
(b) La SBA corrente soddisfa il criterio di ottimalit`a.
(c) Il valore della funzione obiettivo nel punto ammissibile ¯y = (1, 0, 1, 1, 1, 1)T`e maggiore di 25.
(d) Vale cTBB−1b = 25.
10. Sia dato il problema
(P )
min cTx Ax ≤ b x ≥ 0 (a) Il suo duale `e
min bTu
−ATu ≤ c u ≥ 0
(b) Non pu`o accadere che entrambe i problemi (primale e duale) siano inammissibili.
(c) Se entrambi i problemi (primale e duale) ammettono soluzioni ammissibili, allora nessuno dei due problemi potr`a essere illimitato.
(d) Se il problema (P) `e inammissibile allora il suo duale `e illimitato.
Prova scritta di Ricerca Operativa Corsi di Laurea in
Ingegneria Informatica e Ingegneria Automatica
8 settembre 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
1. Sia dato l’insieme H = {x ∈ <n | Ax = b, x ≥ 0} con A matrice m × n e b ∈ <m.
(a) H `e un poliedro che rappresenta l’insieme ammissibile di un problema di PL in forma standard se e solo A ha rango massimo.
(b) Se H `e non vuoto, allora ammette sempre almeno un vertice.
(c) `E sempre possibile scrivere l’insieme ammissibile di un problema di PL come l’insieme H.
(d) H non pu`o contenere semirette.
2. Sia a ∈ <n e b ∈ <.
(a) L’insieme {x ∈ <n | aTx = b} `e un iperpiano
(b) Data la funzione f (x1, x2) = c1x1+ c2x2, il vettore (c1, c2)T rappresenta una direzione di crescita per la funzione f .
(c) L’insieme {x ∈ <n | aTx = b} `e un poliedro.
(d) Se n = 2 e F = {x ∈ <2| 2x1− 3x2= 5}, F rappresenta una retta e il vettore (−4 , 6)T
`e ortogonale alla retta F .
3. Sia dato un problema di PL in forma standard, e sia B una base ammissibile e N la matrice delle colonne fuori base.
(a) Si ha sempre B−1b − B−1N xN ≥ 0.
(b) Nell’ipotesi di non degeneratezza, data una base B esiste un’unica SBA associata e viceversa.
(c) Lo scalare ¯ρ che si calcola nel criterio del rapporto minimo `e nullo se e solo se la SBA corrente `e degenere.
(d) Se per ogni i = 1, . . . , m risulta πi ≥ 0, allora il problema non pu`o essere illimitato inferiormente.
4. Arrivati all’ottimo del problema artificiale che si risolve nella Fase I del metodo del simplesso abbiamo che risulta xB= (α1, x1, α3, x3), xN = (α2, x2, α4, x4),
B−1b =
0 1 β 1
, B−1N =
3 0 7 β
0 −1 15 17
12 0 12 19
1 1 0 3
Conβ ∈ <. Allora
(a) Non esistono valori di β per cui il problema originario non `e ammissibile.
(b) Il problema originario `e ammissibile se e solo se risulta β = 0 e si ha che nel problema originario c’`e un vincolo ridondante.
(c) Se β 6= 0, allora una possibile base ammissibile per il problema originario dalla quale far partire la Fase II corrisponde ad avere variabili di base xB= (x1, x4, x3).
(d) Se il problema orginario `e ammissibile, una possibile base ammissibile per il problema originario dalla quale far partire la Fase II corrisponde ad avere variabili di base xB = (x1, x4, x3).
5. Dato il poliedro definito dal sistema
3x1+ x2− x4 ≥ 2
−x2− 2x3 ≤ −2 x1+ 2x2+ x3 ≥ 2
x ≥ 0
(a) L’origine `e un vertice del poliedro.
(b) Il punto (1, 0, 1, 1)T `e un vertice del poliedro.
(c) Il punto (1, 0, 0, 1)T `e un vertice del poliedro.
(d) Il punto (1, 2, 1, 1)T appartiene al poliedro.
6. Ad una iterazione della Fase II del metodo del simplesso applicato ad un problema di mini- mizzazione si ha: xB= (x1, x3, x5)T, xN = (x4, x2, x6)T,
B−1N =
1 0 −1
3 1 0
2 0 −3
.
Il vettore dei costi ridotti `e γ = (1, − 1, 0)T. Sia ¯x = (1, 0, 1, 1, 0, 0)T la soluzione base ammissibile corrente in cui la funzione obiettivo vale 25.
(a) La SBA corrente soddisfa il criterio di ottimalit`a.
(b) La SBA corrente soddisfa il criterio di illimitatezza.
(c) Vale cTBB−1b = 25.
(d) Il valore della funzione obiettivo nel punto ammissibile ¯y = (1, 0, 1, 1, 1, 1)T`e maggiore di 25.
7. Sia dato il seguente poliedro
2x1+ x2− x4 = 1 x1+ 3x3 = 4 τ x2+ x3+ x4 = 2
x ≥ 0 (a) Per τ = −1 il punto (1, − 1, 1, 0)T `e una SBA.
(b) Il punto (1, 0, 1, 1)T `e un vertice per ogni valore di τ .
(c) Esistono valori di τ per i quali il punto (1, 1, 1, 1)T `e una SBA (d) L’origine `e una SBA.
8. Sia dato il problema
(P )
min cTx Ax ≤ b x ≥ 0 (a) Il suo duale `e
min bTu
−ATu ≤ c u ≥ 0
(b) Se entrambi i problemi (primale e duale) ammettono soluzioni ammissibili, allora nessuno dei due problemi potr`a essere illimitato.
(c) Non pu`o accadere che entrambe i problemi (primale e duale) siano inammissibili.
(d) Se il problema (P) `e inammissibile allora il suo duale `e illimitato.
9. Sia dato un problema di minimizzazione
min f (x) x ∈ P con P poliedro di <n e f : <n→ <.
(a) Se P `e non vuoto e non contiene rette, allora esiste sempre un vertice di P che `e soluzione ottima del problema.
(b) Se n = 3 e f (x) = 3x1+ 2x1x2− 3x3 e P `e un politopo, allora il problema ammette sempre soluzione ottima.
(c) Se f (x) =Pn
i=1cixi, con ci∈ <, allora al problema si applica il teorema fondamentale della programmazione lineare
(d) Se P `e un politopo, allora il problema ammette sempre soluzione ottima.
10. Sia dato un problema di Programmazione Lineare al quale si applica il metodo del simplesso.
(a) Il criterio di ottimalit`a `e solo sufficiente e quindi se una soluzione di base corrente non
`e ottima allora il criterio non pu`o essere soddisfatto.
(b) La Fase I del metodo del simplesso permette sempre di ottenere una base ammissibile dalla quale far partire la Fase II.
(c) Le regole anticiclaggio applicate nella Fase II garantiscono che se il problema non `e illimitato, allora in un numero finito di iterazioni si ha convergenza alla soluzione ottima.
(d) 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.
