Prova scritta di Ricerca Operativa Corso di Laurea in
Ingegneria Informatica e Automatica
7 novembre 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. (a) Un iperpiano in <n`e un insieme convesso
(b) L’intersezione di due semispazi chiusi `e un insieme convesso che ammette sempre vertici.
(c) L’unione di due semispazi chiusi `e un insieme convesso che non ammette vertici.
(d) Se un insieme F ⊆ <n`e tale che esistono due punti x ∈ F , y ∈ F tali che λx + (1 − λ)y appartiene ad F per ogni λ ∈ [0, 1], allora F `e convesso.
2. Sia dato l’insieme H = {x ∈ <n| Ax ≥ b, x ≥ 0} con A matrice m × n e b ∈ <me supponiamo che H sia non vuoto.
(a) H pu`o essere l’insieme ammissibile di un problema di Programmazione Lineare.
(b) H ammette sempre l’origine come vertice.
(c) H ammette vertici se e solo se A ha rango massimo.
(d) Se P `e un poliedro non vuoto tale che P ⊆ H allora ammette sempre vertici.
3. Sia dato un problema di PL
min cTx x ∈ P con P poliedro di <n.
(a) Se P `e un politopo allora il problema ammette sempre soluzione ottima.
(b) Se supponiamo che P sia non vuoto, allora dato un punto ¯x di P che non `e vertice, `e sempre possibile determinare un altro punto di P tale che il numero dei vincoli attivi linearmente indipendenti nel nuovo punto sia maggiore che in ¯x
(c) Condizione necessaria affinch´e il problema sia illimitato `e che P non sia un politopo.
(d) Se esiste una semiretta di punti interamente contenuta in P allora il problema pu`o essere illimitato.
4. Dato il poliedro definito dal sistema
2x1+ x2− x4 ≥ 3
−x1− x3 ≤ −1 x2+ 3x3+ 2x4 ≥ 3
x ≥ 0
(a) Il punto (1, 1, 0, 1)T `e un vertice del poliedro.
(b) L’origine `e un vertice del poliedro.
(c) Il punto (2, 0, 1, 1)T `e un vertice del poliedro.
(d) Il punto (4, 0, 2, 0)T appartiene al poliedro.
5. Sia dato un problema di Programmazione Lineare al quale si applica il metodo del simplesso.
(a) Se la Fase I si arresta perch´e il problema aritificiale `e illimitato, allora il problema originario non `e ammissibile.
(b) Se non si utilizzano regole anticiclaggio, la Fase I pu`o ciclare.
(c) Il problema artificiale che si risolve nella Fase I `e il duale del problema originario.
(d) Il numero delle variabile artificiali che si utilizzano nella Fase I `e minore o uguale al numero dei vincoli del problema originario.
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) Se il criterio di illimitatezza non `e soddisfatto allora esiste almeno un indice i tale che risulti γi< 0 e πi > 0.
(b) Se il criterio di ottimalit`a non `e soddisfatto allora esiste alemno un indice i tale che γi< 0.
(c) Le colonne di B sono lineramente indipendenti.
(d) Nel criterio del rapporto minimo pu`o risultare ¯ρ = 0 solamente se la SBA corrente `e degenere.
7. Arrivati all’ottimo del problema artificiale che si risolve nella Fase I del metodo del simplesso abbiamo che risulta xB= (x4, α2, α3, x3), xN = (x2, α1, x1, α4),
B−1b =
1 τ 0 0
, B−1N =
5 2 7 1
0 −τ 5 7
1 0 1 0
0 0 0 2
Conτ ∈ <. Allora
(a) Il problema originario `e ammissibile se e solo se risulta τ = 0.
(b) Se τ = 0 allora il problema il problema originario ha 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= (x4, x1, x2, 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 = (x4, x1, x2, x3).
8. Ad una iterazione della Fase II del metodo del simplesso applicato ad un problema di mini- mizzazione si ha: xB= (x2, x3, x6)T,
xN = (x4, x1, x5)T,
B−1N =
−1 0 3
0 5 7
−3 1 9
.
Il vettore dei costi ridotti `e γ = (−1, 0, 2)T. Sia ¯x = (0, 1, 1, 0, 0, 1)T la soluzione base ammissibile corrente in cui la funzione obiettivo vale 10.
(a) La SBA corrente soddisfa il criterio di ottimalit`a.
(b) Il valore della funzione obiettivo nel punto ammissibile ¯y = (0, 1, 1, 1, 1, 1)T`e maggiore di 10.
(c) La funzione obiettivo del problema `e illimitata inferiormente.
(d) Non sono forniti gli elementi necessari per determinare il valore della funzione obiettivo nel punto ammissibile ¯y = (0, 1, 1, 1, 1, 1)T
9. Sia dato il seguente poliedro
x1+ 2x2+ x3 = 3 x1+ βx2 = 3 x2+ 2x3+ x4 = 8
x ≥ 0 (a) Per β = 1 il punto (2, 1, 1, 5)T `e un vertice.
(b) Esistono valori di β per i quali il punto (2, 1, 1, 0)T `e una SBA (c) Il punto (3, 0, 0, 8)T `e una SBA per ogni valore di β.
(d) Il punto (0, 1, 1, 5)T `e una SBA per ogni valore di β.
10. Sia dato il problema
(P )
max cTx Ax ≥ b (a) Il suo duale `e
max bTu ATu = −c u ≥ 0
(b) Se (P) `e inammissibile, allora il suo duale non pu`o essere inammissibile.
(c) Data una coppia primale/duale e due punti ¯x e ¯u ammissibili per i rispettivi problemi, allora la funzione obiettivo del primale calcolata in ¯x coincide con la funzione obiettivo calcolata in ¯u.
(d) Se un problema di PL ammette almeno una soluzione ammissibile, allora anche il suo duale `e ammissibile.
Prova scritta di Ricerca Operativa Corso di Laurea in
Ingegneria Informatica e Ingegneria Automatica
7 novembre 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) Le colonne di B sono lineramente indipendenti.
(b) Se il criterio di illimitatezza non `e soddisfatto allora esiste almeno un indice i tale che risulti γi< 0 e πi > 0.
(c) Se il criterio di ottimalit`a non `e soddisfatto allora esiste alemno un indice i tale che γi< 0.
(d) Nel criterio del rapporto minimo pu`o risultare ¯ρ = 0 solamente se la SBA corrente `e degenere.
2. Ad una iterazione della Fase II del metodo del simplesso applicato ad un problema di mini- mizzazione si ha: xB= (x2, x3, x6)T,
xN = (x4, x1, x5)T,
B−1N =
−1 0 3
0 5 7
−3 1 9
.
Il vettore dei costi ridotti `e γ = (−1, 0, 2)T. Sia ¯x = (0, 1, 1, 0, 0, 1)T la soluzione base ammissibile corrente in cui la funzione obiettivo vale 10.
(a) La funzione obiettivo del problema `e illimitata inferiormente.
(b) La SBA corrente soddisfa il criterio di ottimalit`a.
(c) Il valore della funzione obiettivo nel punto ammissibile ¯y = (0, 1, 1, 1, 1, 1)T`e maggiore di 10.
(d) Non sono forniti gli elementi necessari per determinare il valore della funzione obiettivo nel punto ammissibile ¯y = (0, 1, 1, 1, 1, 1)T
3. Sia dato il problema
(P )
max cTx Ax ≥ b (a) Il suo duale `e
max bTu ATu = −c u ≥ 0
(b) Se un problema di PL ammette almeno una soluzione ammissibile, allora anche il suo duale `e ammissibile.
(c) Se (P) `e inammissibile, allora il suo duale non pu`o essere inammissibile.
(d) Data una coppia primale/duale e due punti ¯x e ¯u ammissibili per i rispettivi problemi, allora la funzione obiettivo del primale calcolata in ¯x coincide con la funzione obiettivo calcolata in ¯u.
4. (a) Se un insieme F ⊆ <n`e tale che esistono due punti x ∈ F , y ∈ F tali che λx + (1 − λ)y appartiene ad F per ogni λ ∈ [0, 1], allora F `e convesso.
(b) Un iperpiano in <n`e un insieme convesso
(c) L’intersezione di due semispazi chiusi `e un insieme convesso che ammette sempre vertici.
(d) L’unione di due semispazi chiusi `e un insieme convesso che non ammette vertici.
5. Arrivati all’ottimo del problema artificiale che si risolve nella Fase I del metodo del simplesso abbiamo che risulta xB= (x4, α2, α3, x3), xN = (x2, α1, x1, α4),
B−1b =
1 τ 0 0
, B−1N =
5 2 7 1
0 −τ 5 7
1 0 1 0
0 0 0 2
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= (x4, x1, x2, x3).
(b) Il problema originario `e ammissibile se e solo se risulta τ = 0.
(c) Se τ = 0 allora il problema il problema originario ha un vincolo ridondante.
(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 = (x4, x1, x2, x3).
6. Sia dato l’insieme H = {x ∈ <n| Ax ≥ b, x ≥ 0} con A matrice m × n e b ∈ <me supponiamo che H sia non vuoto.
(a) H ammette sempre l’origine come vertice.
(b) H pu`o essere l’insieme ammissibile di un problema di Programmazione Lineare.
(c) H ammette vertici se e solo se A ha rango massimo.
(d) Se P `e un poliedro non vuoto tale che P ⊆ H allora ammette sempre vertici.
7. Sia dato il seguente poliedro
x1+ 2x2+ x3 = 3 x1+ βx2 = 3 x2+ 2x3+ x4 = 8
x ≥ 0
(a) Il punto (3, 0, 0, 8)T `e una SBA per ogni valore di β.
(b) Per β = 1 il punto (2, 1, 1, 5)T `e un vertice.
(c) Esistono valori di β per i quali il punto (2, 1, 1, 0)T `e una SBA (d) Il punto (0, 1, 1, 5)T `e una SBA per ogni valore di β.
8. Dato il poliedro definito dal sistema
2x1+ x2− x4 ≥ 3
−x1− x3 ≤ −1 x2+ 3x3+ 2x4 ≥ 3
x ≥ 0
(a) Il punto (2, 0, 1, 1)T `e un vertice del poliedro.
(b) Il punto (1, 1, 0, 1)T `e un vertice del poliedro.
(c) L’origine `e un vertice del poliedro.
(d) Il punto (4, 0, 2, 0)T appartiene al poliedro.
9. Sia dato un problema di Programmazione Lineare al quale si applica il metodo del simplesso.
(a) Il problema artificiale che si risolve nella Fase I `e il duale del problema originario.
(b) Se la Fase I si arresta perch´e il problema aritificiale `e illimitato, allora il problema originario non `e ammissibile.
(c) Se non si utilizzano regole anticiclaggio, la Fase I pu`o ciclare.
(d) Il numero delle variabile artificiali che si utilizzano nella Fase I `e minore o uguale al numero dei vincoli del problema originario.
10. Sia dato un problema di PL
min cTx x ∈ P con P poliedro di <n.
(a) Se supponiamo che P sia non vuoto, allora dato un punto ¯x di P che non `e vertice, `e sempre possibile determinare un altro punto di P tale che il numero dei vincoli attivi linearmente indipendenti nel nuovo punto sia maggiore che in ¯x
(b) Se P `e un politopo allora il problema ammette sempre soluzione ottima.
(c) Condizione necessaria affinch´e il problema sia illimitato `e che P non sia un politopo.
(d) Se esiste una semiretta di punti interamente contenuta in P allora il problema pu`o essere illimitato.
Prova scritta di Ricerca Operativa Corso di Laurea in
Ingegneria Informatica e Ingegneria Automatica
7 novembre 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 il seguente poliedro
x1+ 2x2+ x3 = 3 x1+ βx2 = 3 x2+ 2x3+ x4 = 8
x ≥ 0
(a) Il punto (3, 0, 0, 8)T `e una SBA per ogni valore di β.
(b) Per β = 1 il punto (2, 1, 1, 5)T `e un vertice.
(c) Esistono valori di β per i quali il punto (2, 1, 1, 0)T `e una SBA (d) Il punto (0, 1, 1, 5)T `e una SBA per ogni valore di β.
2. Sia dato il problema
(P )
max cTx Ax ≥ b (a) Il suo duale `e
max bTu ATu = −c u ≥ 0
(b) Se (P) `e inammissibile, allora il suo duale non pu`o essere inammissibile.
(c) Se un problema di PL ammette almeno una soluzione ammissibile, allora anche il suo duale `e ammissibile.
(d) Data una coppia primale/duale e due punti ¯x e ¯u ammissibili per i rispettivi problemi, allora la funzione obiettivo del primale calcolata in ¯x coincide con la funzione obiettivo calcolata in ¯u.
3. Sia dato un problema di PL
min cTx x ∈ P con P poliedro di <n.
(a) Se supponiamo che P sia non vuoto, allora dato un punto ¯x di P che non `e vertice, `e sempre possibile determinare un altro punto di P tale che il numero dei vincoli attivi linearmente indipendenti nel nuovo punto sia maggiore che in ¯x
(b) Se P `e un politopo allora il problema ammette sempre soluzione ottima.
(c) Condizione necessaria affinch´e il problema sia illimitato `e che P non sia un politopo.
(d) Se esiste una semiretta di punti interamente contenuta in P allora il problema pu`o essere illimitato.
4. Sia dato un problema di Programmazione Lineare al quale si applica il metodo del simplesso.
(a) Il problema artificiale che si risolve nella Fase I `e il duale del problema originario.
(b) Il numero delle variabile artificiali che si utilizzano nella Fase I `e minore o uguale al numero dei vincoli del problema originario.
(c) Se la Fase I si arresta perch´e il problema aritificiale `e illimitato, allora il problema originario non `e ammissibile.
(d) Se non si utilizzano regole anticiclaggio, la Fase I pu`o ciclare.
5. (a) L’intersezione di due semispazi chiusi `e un insieme convesso che ammette sempre vertici.
(b) L’unione di due semispazi chiusi `e un insieme convesso che non ammette vertici.
(c) Un iperpiano in <n`e un insieme convesso
(d) Se un insieme F ⊆ <n`e tale che esistono due punti x ∈ F , y ∈ F tali che λx + (1 − λ)y appartiene ad F per ogni λ ∈ [0, 1], allora F `e convesso.
6. Dato il poliedro definito dal sistema
2x1+ x2− x4 ≥ 3
−x1− x3 ≤ −1 x2+ 3x3+ 2x4 ≥ 3
x ≥ 0
(a) L’origine `e un vertice del poliedro.
(b) Il punto (1, 1, 0, 1)T `e un vertice del poliedro.
(c) Il punto (2, 0, 1, 1)T `e un vertice del poliedro.
(d) Il punto (4, 0, 2, 0)T appartiene al poliedro.
7. Sia dato l’insieme H = {x ∈ <n| Ax ≥ b, x ≥ 0} con A matrice m × n e b ∈ <me supponiamo che H sia non vuoto.
(a) H ammette sempre l’origine come vertice.
(b) H pu`o essere l’insieme ammissibile di un problema di Programmazione Lineare.
(c) H ammette vertici se e solo se A ha rango massimo.
(d) Se P `e un poliedro non vuoto tale che P ⊆ H allora ammette sempre vertici.
8. Sia dato un problema di PL in forma standard, e sia B una base ammissibile e N la matrice delle colonne fuori base.
(a) Se il criterio di ottimalit`a non `e soddisfatto allora esiste alemno un indice i tale che γi< 0.
(b) Se il criterio di illimitatezza non `e soddisfatto allora esiste almeno un indice i tale che risulti γi< 0 e πi > 0
(c) Le colonne di B sono lineramente indipendenti.
(d) Nel criterio del rapporto minimo pu`o risultare ¯ρ = 0 solamente se la SBA corrente `e degenere.
9. Ad una iterazione della Fase II del metodo del simplesso applicato ad un problema di mini- mizzazione si ha: xB= (x2, x3, x6)T,
xN = (x4, x1, x5)T,
B−1N =
−1 0 3
0 5 7
−3 1 9
.
Il vettore dei costi ridotti `e γ = (−1, 0, 2)T. Sia ¯x = (0, 1, 1, 0, 0, 1)T la soluzione base ammissibile corrente in cui la funzione obiettivo vale 10.
(a) La funzione obiettivo del problema `e illimitata inferiormente.
(b) La SBA corrente soddisfa il criterio di ottimalit`a.
(c) Il valore della funzione obiettivo nel punto ammissibile ¯y = (0, 1, 1, 1, 1, 1)T`e maggiore di 10.
(d) Non sono forniti gli elementi necessari per determinare il valore della funzione obiettivo nel punto ammissibile ¯y = (0, 1, 1, 1, 1, 1)T
10. Arrivati all’ottimo del problema artificiale che si risolve nella Fase I del metodo del simplesso abbiamo che risulta xB= (x4, α2, α3, x3), xN = (x2, α1, x1, α4),
B−1b =
1 τ 0 0
, B−1N =
5 2 7 1
0 −τ 5 7
1 0 1 0
0 0 0 2
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= (x4, x1, x2, 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 = (x4, x1, x2, x3).
(c) Il problema originario `e ammissibile se e solo se risulta τ = 0.
(d) Se τ = 0 allora il problema il problema originario ha un vincolo ridondante.
Prova scritta di Ricerca Operativa Corso di Laurea in
Ingegneria Informatica e Ingegneria Automatica
7 novembre 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 un problema di Programmazione Lineare al quale si applica il metodo del simplesso.
(a) Se non si utilizzano regole anticiclaggio, la Fase I pu`o ciclare.
(b) Se la Fase I si arresta perch´e il problema aritificiale `e illimitato, allora il problema originario non `e ammissibile.
(c) Il problema artificiale che si risolve nella Fase I `e il duale del problema originario.
(d) Il numero delle variabile artificiali che si utilizzano nella Fase I `e minore o uguale al numero dei vincoli del problema originario.
2. Arrivati all’ottimo del problema artificiale che si risolve nella Fase I del metodo del simplesso abbiamo che risulta xB= (x4, α2, α3, x3), xN = (x2, α1, x1, α4),
B−1b =
1 τ 0 0
, B−1N =
5 2 7 1
0 −τ 5 7
1 0 1 0
0 0 0 2
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= (x4, x1, x2, x3).
(b) Il problema originario `e ammissibile se e solo se risulta τ = 0.
(c) Se τ = 0 allora il problema il problema originario ha un vincolo ridondante.
(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 = (x4, x1, x2, x3).
3. Sia dato il seguente poliedro
x1+ 2x2+ x3 = 3 x1+ βx2 = 3 x2+ 2x3+ x4 = 8
x ≥ 0
(a) Il punto (3, 0, 0, 8)T `e una SBA per ogni valore di β.
(b) Il punto (0, 1, 1, 5)T `e una SBA per ogni valore di β.
(c) Per β = 1 il punto (2, 1, 1, 5)T `e un vertice.
(d) Esistono valori di β per i quali il punto (2, 1, 1, 0)T `e una SBA
4. Ad una iterazione della Fase II del metodo del simplesso applicato ad un problema di mini- mizzazione si ha: xB= (x2, x3, x6)T,
xN = (x4, x1, x5)T,
B−1N =
−1 0 3
0 5 7
−3 1 9
.
Il vettore dei costi ridotti `e γ = (−1, 0, 2)T. Sia ¯x = (0, 1, 1, 0, 0, 1)T la soluzione base ammissibile corrente in cui la funzione obiettivo vale 10.
(a) Il valore della funzione obiettivo nel punto ammissibile ¯y = (0, 1, 1, 1, 1, 1)T`e maggiore di 10.
(b) La funzione obiettivo del problema `e illimitata inferiormente.
(c) Non sono forniti gli elementi necessari per determinare il valore della funzione obiettivo nel punto ammissibile ¯y = (0, 1, 1, 1, 1, 1)T
(d) La SBA corrente soddisfa il criterio di ottimalit`a.
5. (a) L’intersezione di due semispazi chiusi `e un insieme convesso che ammette sempre vertici.
(b) L’unione di due semispazi chiusi `e un insieme convesso che non ammette vertici.
(c) Se un insieme F ⊆ <n`e tale che esistono due punti x ∈ F , y ∈ F tali che λx + (1 − λ)y appartiene ad F per ogni λ ∈ [0, 1], allora F `e convesso.
(d) Un iperpiano in <n`e un insieme convesso
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) Se il criterio di ottimalit`a non `e soddisfatto allora esiste alemno un indice i tale che γi< 0.
(b) Se il criterio di illimitatezza non `e soddisfatto allora esiste almeno un indice i tale che risulti γi< 0 e πi > 0.
(c) Le colonne di B sono lineramente indipendenti.
(d) Nel criterio del rapporto minimo pu`o risultare ¯ρ = 0 solamente se la SBA corrente `e degenere.
7. Sia dato un problema di PL
min cTx x ∈ P con P poliedro di <n.
(a) Condizione necessaria affinch´e il problema sia illimitato `e che P non sia un politopo.
(b) Se esiste una semiretta di punti interamente contenuta in P allora il problema pu`o essere illimitato.
(c) Se P `e un politopo allora il problema ammette sempre soluzione ottima.
(d) Se supponiamo che P sia non vuoto, allora dato un punto ¯x di P che non `e vertice, `e sempre possibile determinare un altro punto di P tale che il numero dei vincoli attivi linearmente indipendenti nel nuovo punto sia maggiore che in ¯x
8. Dato il poliedro definito dal sistema
2x1+ x2− x4 ≥ 3
−x1− x3 ≤ −1 x2+ 3x3+ 2x4 ≥ 3
x ≥ 0
(a) L’origine `e un vertice del poliedro.
(b) Il punto (1, 1, 0, 1)T `e un vertice del poliedro.
(c) Il punto (2, 0, 1, 1)T `e un vertice del poliedro.
(d) Il punto (4, 0, 2, 0)T appartiene al poliedro.
9. Sia dato il problema
(P )
max cTx Ax ≥ b (a) Il suo duale `e
max bTu ATu = −c u ≥ 0
(b) Se (P) `e inammissibile, allora il suo duale non pu`o essere inammissibile.
(c) Data una coppia primale/duale e due punti ¯x e ¯u ammissibili per i rispettivi problemi, allora la funzione obiettivo del primale calcolata in ¯x coincide con la funzione obiettivo calcolata in ¯u.
(d) Se un problema di PL ammette almeno una soluzione ammissibile, allora anche il suo duale `e ammissibile.
10. Sia dato l’insieme H = {x ∈ <n| Ax ≥ b, x ≥ 0} con A matrice m × n e b ∈ <me supponiamo che H sia non vuoto.
(a) H ammette vertici se e solo se A ha rango massimo.
(b) H pu`o essere l’insieme ammissibile di un problema di Programmazione Lineare.
(c) H ammette sempre l’origine come vertice.
(d) Se P `e un poliedro non vuoto tale che P ⊆ H allora ammette sempre vertici.
