Prova scritta di Ricerca Operativa Corso di Laurea in
Ingegneria Informatica e Automatica
21 giugno 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. Dire quali delle seguenti affermazioni sono corrette.
(a) In IR3, l’intersezione tra una sfera centrata nell’origine di raggio 1 e l’ortante positivo `e un politopo.
(b) In IR2, l’insieme dei punti a coordinate intere del primo quadrante `e un insieme convesso.
(c) Dati y ∈ IRn e z ∈ IRn, l’insieme {x ∈ IRn | x = λy + (1 − λ)z, 0 ≤ λ ≤ 1/2} `e un insieme convesso.
(d) L’insieme {x ∈ IRn | Ax ≥ b, l ≤ x ≤ u}, con A matrice m × n, x ∈ IRn, b ∈ IRm, l ∈ IRn e u ∈ IRn `e un politopo.
2. Dato un problema di Programmazione Lineare nella forma min cTx
Ax ≥ b,
si denoti con P il poliedro dell’insieme ammissibile del problema. Dire quali delle seguenti affermazioni sono corrette.
(a) Se P `e non vuoto, allora il problema o risulta illimitato oppure ammette ottimo finito.
(b) Se P `e non vuoto e limitato, allora il problema ammette soluzione ottima su un vertice di P .
(c) Se ¯x `e un punto ammissibile che non `e un vertice di P , allora `e sempre possibile deter- minare un punto ˜x ∈ P nel quale il numero dei vincoli attivi linearmente indipendenti supera di almeno 1 il numero dei vincoli attivi linearmente indipendenti in ¯x.
(d) Per porre il problema in forma standard `e richiesto che il rango di A sia massimo.
3. Sia dato un problema di Programmazione Lineare Intera.
(a) Se P `e una sua formulazione lineare allora l’insieme ammissibile del problema di PLI si pu`o scrivere nella forma P ∩ Zn.
(b) Se P1 e P2 sono due formulazioni del problema di PLI, e se risulta che P2 ⊆ P1 allora P1`e una formulazione migliore di P2.
(c) Se un poliedro P ha tutti i vertici interi, allora esso rappresenta la formulazione ottima di ogni problema di PLI con insieme ammissibile P ∩ Zn.
(d) Il valore dell’ottimo del rilassamento lineare di un problema di PLI in forma di minimiz- zazione costituisce un lower bound del valore ottimo del problema di PLI.
4. Sia dato il problema di Programmazione Lineare
min 3x1− x2+ 5x3+ x5+ x6
1 0 1 1 2 −1
1 1 3 −1 1 2
x =0
2
x = (x1, x2, x3, x4, x5, x6)T ≥ 0 Dire quali delle seguenti affermazioni sono corrette.
(a) Il problema `e in forma canonica.
(b) La base composta dalla 3a e dalla 2a colonna `e una base ammissibile.
(c) Il criterio di illimitatezza `e soddisfatto in corrispondenza della base formata dalla 3a e dalla 2a colonna.
(d) La SBA associata alla base formata dalla 3ae dalla 2acolonna `e data da (0, 2, 0, 0, 0, 0)T. 5. Al termine della Fase I del metodo del simplesso applicato alla soluzione di un problema di
Programmazione Lineare risulta xB = (x3, α2, x2, α4)T, xN = (α3, x4, α1, x1)T,
B−1N =
3 4 2 3
−2 3 1 −1
2 6 7 5
0 0 0 2
, B−1b =
2 0 3 0
.
Dire quali delle seguenti affermazioni sono corrette.
(a) Il problema originario `e inammissibile perch´e sono presenti due variabili artificiali in base.
(b) Una possibile base ammissibile per il problema originario dalla quale far partire la Fase II corrisponde ad avere variabili di base xB= (x3, x1, x2)T.
(c) Una possibile base ammissibile per il problema originario dalla quale far partire la Fase II corrisponde ad avere variabili di base xB= (x3, x4, x2, x1)T.
(d) La matrice dei vincoli di uguaglianza del problema originario ha rango massimo.
6. Si consideri il poliedro descritto dal seguente sistema x1+ 2x2+ x3 = 4 x1+ 4x2+ 2x3 = 7 2x1+ 10x2+ 5x3+ x4 = 17
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 (1, 1, 1, 1)T appartiene al poliedro.
(c) L’origine degli assi `e vertice del poliedro.
(d) Il poliedro non ammette vertici perch´e il numero delle variabili presenti (n) `e maggiore del numero dei vincoli di uguaglianza (m).
7. Sia dato un problema di Programmazione Lineare in forma standard. Dire quali delle seguenti affermazioni sono corrette.
(a) 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.
(b) Se ad una iterazione della Fase I del metodo del simplesso tutte le variabili artificiali sono fuori base, allora `e sicuramente verificato il criterio di ottimalit`a.
(c) Se il rango della matrice dei vincoli di uguaglianza non `e massimo, allora il problema artificiale che si risolve nella Fase I del metodo del simplesso `e illimitato inferiormente.
(d) Il problema artificiale che si risolve nella Fase I del metodo del simplesso ammette sempre soluzione ottima.
8. Dire quali delle seguenti affermazioni sono corrette.
(a) Dato un problema di Programmazione Lineare, si pu`o sempre costruire il problema duale associato.
(b) Data una coppia primale–duale, la funzione obiettivo del problema primale calcolata in un punto ammissibile `e sempre minore del valore che la funzione obiettivo del duale assume in qualsiasi punto ammissibile per il problema duale.
(c) Se un problema di Programmazione Lineare ammette soluzione ottima, il suo duale potrebbe anche essere inammissibile.
(d) C’`e una corrispondenza biunivoca tra i vincoli del problema primale e le variabili del problema duale.
9. Si consideri il poliedro definito da
x1+ 2x2+ x4 ≥ θ 2x1+ ηx2+ x3 ≥ −2
x1+ 2x4 ≥ 1 x2 ≥ 0 x3 ≥ 0 x4 ≥ 0
con θ ∈ IR e η ∈ IR. Dire quali delle seguenti affermazioni sono corrette.
(a) Il punto (−1, 1, 1, 1)T appartiene al poliedro per θ ≤ 2, η ≥ −1.
(b) Per θ = 3, il punto (0, 1, 1, 1)T `e vertice del poliedro se η = −3.
(c) Per θ = 2, il punto (1, 0, 0, 1)T `e vertice del poliedro per ogni valore η ∈ IR.
(d) L’origine `e vertice del poliedro se e solo se θ = 0 e per ogni valore di η ∈ IR.
10. In un’iterazione della Fase II del metodo del simplesso applicato ad un problema di Program- mazione Lineare in forma di minimizzazione si ha xB= (x6, x3, x8, x7)T e xN = (x1, x5, x2, x4)T, ed inoltre risulta γ = (1, 0, − 2, − 10)T.
B−1N =
−1 −1 0 1
2 −2 1 −1
1 −1 2 2
2 −4 1 0
, B−1b =
1 0 2 1/2
.
Dire quali delle seguenti affermazioni sono corrette.
(a) Supponiamo che x4 sia la variabile entrante. Allora la successiva Soluzione di Base Ammissibile sar`a degenere.
(b) Supponiamo che x4sia la variabile entrante. Allora si ha ¯ρ = 0.
(c) Supponiamo che x2 sia la variabile entrante. Allora l’unica variabile uscente pu`o essere x3.
(d) Supponiamo che x4sia la variabile entrante. Allora la variabile uscente pu`o essere x7.
Prova scritta di Ricerca Operativa Corso di Laurea in
Ingegneria Informatica e Automatica
21 giugno 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. Al termine della Fase I del metodo del simplesso applicato alla soluzione di un problema di Programmazione Lineare risulta xB = (x3, α2, x2, α4)T, xN = (α3, x4, α1, x1)T,
B−1N =
3 4 2 3
−2 3 1 −1
2 6 7 5
0 0 0 2
, B−1b =
2 0 3 0
.
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, x4, x2, x1)T.
(b) La matrice dei vincoli di uguaglianza del problema originario ha rango massimo.
(c) Il problema originario `e inammissibile perch´e sono presenti due variabili artificiali in base.
(d) Una possibile base ammissibile per il problema originario dalla quale far partire la Fase II corrisponde ad avere variabili di base xB= (x3, x1, x2)T.
2. Dire quali delle seguenti affermazioni sono corrette.
(a) Dato un problema di Programmazione Lineare, si pu`o sempre costruire il problema duale associato.
(b) Se un problema di Programmazione Lineare ammette soluzione ottima, il suo duale potrebbe anche essere inammissibile.
(c) C’`e una corrispondenza biunivoca tra i vincoli del problema primale e le variabili del problema duale.
(d) Data una coppia primale–duale, la funzione obiettivo del problema primale calcolata in un punto ammissibile `e sempre minore del valore che la funzione obiettivo del duale assume in qualsiasi punto ammissibile per il problema duale.
3. Si consideri il poliedro descritto dal seguente sistema x1+ 2x2+ x3 = 4 x1+ 4x2+ 2x3 = 7 2x1+ 10x2+ 5x3+ x4 = 17
xi≥ 0, i = 1, . . . , 4 Dire quali delle seguenti affermazioni sono corrette.
(a) Il punto (1, 1, 1, 1)T appartiene al poliedro.
(b) L’origine degli assi `e vertice del poliedro.
(c) Il poliedro non ammette vertici perch´e il numero delle variabili presenti (n) `e maggiore del numero dei vincoli di uguaglianza (m).
(d) Il punto (1, 1, 1, 0)T `e vertice del poliedro.
4. In un’iterazione della Fase II del metodo del simplesso applicato ad un problema di Program- mazione Lineare in forma di minimizzazione si ha xB= (x6, x3, x8, x7)T e xN = (x1, x5, x2, x4)T, ed inoltre risulta γ = (1, 0, − 2, − 10)T.
B−1N =
−1 −1 0 1
2 −2 1 −1
1 −1 2 2
2 −4 1 0
, B−1b =
1 0 2 1/2
.
Dire quali delle seguenti affermazioni sono corrette.
(a) Supponiamo che x2 sia la variabile entrante. Allora l’unica variabile uscente pu`o essere x3.
(b) Supponiamo che x4 sia la variabile entrante. Allora la successiva Soluzione di Base Ammissibile sar`a degenere.
(c) Supponiamo che x4sia la variabile entrante. Allora si ha ¯ρ = 0.
(d) Supponiamo che x4sia la variabile entrante. Allora la variabile uscente pu`o essere x7. 5. Sia dato il problema di Programmazione Lineare
min 3x1− x2+ 5x3+ x5+ x6
1 0 1 1 2 −1
1 1 3 −1 1 2
x =0
2
x = (x1, x2, x3, x4, x5, x6)T ≥ 0 Dire quali delle seguenti affermazioni sono corrette.
(a) Il problema `e in forma canonica.
(b) La SBA associata alla base formata dalla 3ae dalla 2acolonna `e data da (0, 2, 0, 0, 0, 0)T. (c) La base composta dalla 3a e dalla 2a colonna `e una base ammissibile.
(d) Il criterio di illimitatezza `e soddisfatto in corrispondenza della base formata dalla 3a e dalla 2a colonna.
6. Dire quali delle seguenti affermazioni sono corrette.
(a) In IR2, l’insieme dei punti a coordinate intere del primo quadrante `e un insieme convesso.
(b) In IR3, l’intersezione tra una sfera centrata nell’origine di raggio 1 e l’ortante positivo `e un politopo.
(c) Dati y ∈ IRn e z ∈ IRn, l’insieme {x ∈ IRn | x = λy + (1 − λ)z, 0 ≤ λ ≤ 1/2} `e un insieme convesso.
(d) L’insieme {x ∈ IRn | Ax ≥ b, l ≤ x ≤ u}, con A matrice m × n, x ∈ IRn, b ∈ IRm, l ∈ IRn e u ∈ IRn `e un politopo.
7. Sia dato un problema di Programmazione Lineare in forma standard. Dire quali delle seguenti affermazioni sono corrette.
(a) Se il rango della matrice dei vincoli di uguaglianza non `e massimo, allora il problema artificiale che si risolve nella Fase I del metodo del simplesso `e illimitato inferiormente.
(b) Il problema artificiale che si risolve nella Fase I del metodo del simplesso ammette sempre soluzione ottima.
(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 iterazione della Fase I del metodo del simplesso tutte le variabili artificiali sono fuori base, allora `e sicuramente verificato il criterio di ottimalit`a.
8. Dato un problema di Programmazione Lineare nella forma min cTx
Ax ≥ b,
si denoti con P il poliedro dell’insieme ammissibile del problema. Dire quali delle seguenti affermazioni sono corrette.
(a) Se P `e non vuoto e limitato, allora il problema ammette soluzione ottima su un vertice di P .
(b) Se ¯x `e un punto ammissibile che non `e un vertice di P , allora `e sempre possibile deter- minare un punto ˜x ∈ P nel quale il numero dei vincoli attivi linearmente indipendenti supera di almeno 1 il numero dei vincoli attivi linearmente indipendenti in ¯x.
(c) Se P `e non vuoto, allora il problema o risulta illimitato oppure ammette ottimo finito.
(d) Per porre il problema in forma standard `e richiesto che il rango di A sia massimo.
9. Si consideri il poliedro definito da
x1+ 2x2+ x4 ≥ θ 2x1+ ηx2+ x3 ≥ −2
x1+ 2x4 ≥ 1 x2 ≥ 0 x3 ≥ 0 x4 ≥ 0
con θ ∈ IR e η ∈ IR. Dire quali delle seguenti affermazioni sono corrette.
(a) Per θ = 3, il punto (0, 1, 1, 1)T `e vertice del poliedro se η = −3.
(b) Il punto (−1, 1, 1, 1)T appartiene al poliedro per θ ≤ 2, η ≥ −1.
(c) L’origine `e vertice del poliedro se e solo se θ = 0 e per ogni valore di η ∈ IR.
(d) Per θ = 2, il punto (1, 0, 0, 1)T `e vertice del poliedro per ogni valore η ∈ IR.
10. Sia dato un problema di Programmazione Lineare Intera.
(a) Se un poliedro P ha tutti i vertici interi, allora esso rappresenta la formulazione ottima di ogni problema di PLI con insieme ammissibile P ∩ Zn.
(b) Il valore dell’ottimo del rilassamento lineare di un problema di PLI in forma di minimiz- zazione costituisce un lower bound del valore ottimo del problema di PLI.
(c) Se P `e una sua formulazione lineare allora l’insieme ammissibile del problema di PLI si pu`o scrivere nella forma P ∩ Zn.
(d) Se P1 e P2 sono due formulazioni del problema di PLI, e se risulta che P2 ⊆ P1 allora P1`e una formulazione migliore di P2.
Prova scritta di Ricerca Operativa Corso di Laurea in
Ingegneria Informatica e Automatica
21 giugno 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. Si consideri il poliedro descritto dal seguente sistema x1+ 2x2+ x3 = 4 x1+ 4x2+ 2x3 = 7 2x1+ 10x2+ 5x3+ x4 = 17
xi≥ 0, i = 1, . . . , 4 Dire quali delle seguenti affermazioni sono corrette.
(a) L’origine degli assi `e vertice del poliedro.
(b) Il poliedro non ammette vertici perch´e il numero delle variabili presenti (n) `e maggiore del numero dei vincoli di uguaglianza (m).
(c) Il punto (1, 1, 1, 0)T `e vertice del poliedro.
(d) Il punto (1, 1, 1, 1)T appartiene al poliedro.
2. In un’iterazione della Fase II del metodo del simplesso applicato ad un problema di Program- mazione Lineare in forma di minimizzazione si ha xB= (x6, x3, x8, x7)T e xN = (x1, x5, x2, x4)T, ed inoltre risulta γ = (1, 0, − 2, − 10)T.
B−1N =
−1 −1 0 1
2 −2 1 −1
1 −1 2 2
2 −4 1 0
, B−1b =
1 0 2 1/2
.
Dire quali delle seguenti affermazioni sono corrette.
(a) Supponiamo che x2 sia la variabile entrante. Allora l’unica variabile uscente pu`o essere x3.
(b) Supponiamo che x4 sia la variabile entrante. Allora la successiva Soluzione di Base Ammissibile sar`a degenere.
(c) Supponiamo che x4sia la variabile entrante. Allora si ha ¯ρ = 0.
(d) Supponiamo che x4sia la variabile entrante. Allora la variabile uscente pu`o essere x7. 3. Sia dato un problema di Programmazione Lineare in forma standard. Dire quali delle seguenti
affermazioni sono corrette.
(a) Se il rango della matrice dei vincoli di uguaglianza non `e massimo, allora il problema artificiale che si risolve nella Fase I del metodo del simplesso `e illimitato inferiormente.
(b) Il problema artificiale che si risolve nella Fase I del metodo del simplesso ammette sempre soluzione ottima.
(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 iterazione della Fase I del metodo del simplesso tutte le variabili artificiali sono fuori base, allora `e sicuramente verificato il criterio di ottimalit`a.
4. Dato un problema di Programmazione Lineare nella forma min cTx
Ax ≥ b,
si denoti con P il poliedro dell’insieme ammissibile del problema. Dire quali delle seguenti affermazioni sono corrette.
(a) Se P `e non vuoto, allora il problema o risulta illimitato oppure ammette ottimo finito.
(b) Se ¯x `e un punto ammissibile che non `e un vertice di P , allora `e sempre possibile deter- minare un punto ˜x ∈ P nel quale il numero dei vincoli attivi linearmente indipendenti supera di almeno 1 il numero dei vincoli attivi linearmente indipendenti in ¯x.
(c) Se P `e non vuoto e limitato, allora il problema ammette soluzione ottima su un vertice di P .
(d) Per porre il problema in forma standard `e richiesto che il rango di A sia massimo.
5. Sia dato il problema di Programmazione Lineare
min 3x1− x2+ 5x3+ x5+ x6
1 0 1 1 2 −1
1 1 3 −1 1 2
x =0
2
x = (x1, x2, x3, x4, x5, x6)T ≥ 0 Dire quali delle seguenti affermazioni sono corrette.
(a) Il criterio di illimitatezza `e soddisfatto in corrispondenza della base formata dalla 3a e dalla 2a colonna.
(b) La SBA associata alla base formata dalla 3ae dalla 2acolonna `e data da (0, 2, 0, 0, 0, 0)T. (c) Il problema `e in forma canonica.
(d) La base composta dalla 3a e dalla 2a colonna `e una base ammissibile.
6. Dire quali delle seguenti affermazioni sono corrette.
(a) In IR2, l’insieme dei punti a coordinate intere del primo quadrante `e un insieme convesso.
(b) In IR3, l’intersezione tra una sfera centrata nell’origine di raggio 1 e l’ortante positivo `e un politopo.
(c) Dati y ∈ IRn e z ∈ IRn, l’insieme {x ∈ IRn | x = λy + (1 − λ)z, 0 ≤ λ ≤ 1/2} `e un insieme convesso.
(d) L’insieme {x ∈ IRn | Ax ≥ b, l ≤ x ≤ u}, con A matrice m × n, x ∈ IRn, b ∈ IRm, l ∈ IRn e u ∈ IRn `e un politopo.
7. Si consideri il poliedro definito da
x1+ 2x2+ x4 ≥ θ 2x1+ ηx2+ x3 ≥ −2
x1+ 2x4 ≥ 1 x2 ≥ 0 x3 ≥ 0 x4 ≥ 0
con θ ∈ IR e η ∈ IR. Dire quali delle seguenti affermazioni sono corrette.
(a) Per θ = 2, il punto (1, 0, 0, 1)T `e vertice del poliedro per ogni valore η ∈ IR.
(b) L’origine `e vertice del poliedro se e solo se θ = 0 e per ogni valore di η ∈ IR.
(c) Il punto (−1, 1, 1, 1)T appartiene al poliedro per θ ≤ 2, η ≥ −1.
(d) Per θ = 3, il punto (0, 1, 1, 1)T `e vertice del poliedro se η = −3.
8. Sia dato un problema di Programmazione Lineare Intera.
(a) Se P `e una sua formulazione lineare allora l’insieme ammissibile del problema di PLI si pu`o scrivere nella forma P ∩ Zn.
(b) Se un poliedro P ha tutti i vertici interi, allora esso rappresenta la formulazione ottima di ogni problema di PLI con insieme ammissibile P ∩ Zn.
(c) Se P1 e P2 sono due formulazioni del problema di PLI, e se risulta che P2 ⊆ P1 allora P1`e una formulazione migliore di P2.
(d) Il valore dell’ottimo del rilassamento lineare di un problema di PLI in forma di minimiz- zazione costituisce un lower bound del valore ottimo del problema di PLI.
9. Al termine della Fase I del metodo del simplesso applicato alla soluzione di un problema di Programmazione Lineare risulta xB = (x3, α2, x2, α4)T, xN = (α3, x4, α1, x1)T,
B−1N =
3 4 2 3
−2 3 1 −1
2 6 7 5
0 0 0 2
, B−1b =
2 0 3 0
.
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, x1, x2)T.
(b) Il problema originario `e inammissibile perch´e sono presenti due variabili artificiali in base.
(c) Una possibile base ammissibile per il problema originario dalla quale far partire la Fase II corrisponde ad avere variabili di base xB= (x3, x4, x2, x1)T.
(d) La matrice dei vincoli di uguaglianza del problema originario ha rango massimo.
10. Dire quali delle seguenti affermazioni sono corrette.
(a) Dato un problema di Programmazione Lineare, si pu`o sempre costruire il problema duale associato.
(b) Se un problema di Programmazione Lineare ammette soluzione ottima, il suo duale potrebbe anche essere inammissibile.
(c) C’`e una corrispondenza biunivoca tra i vincoli del problema primale e le variabili del problema duale.
(d) Data una coppia primale–duale, la funzione obiettivo del problema primale calcolata in un punto ammissibile `e sempre minore del valore che la funzione obiettivo del duale assume in qualsiasi punto ammissibile per il problema duale.
Prova scritta di Ricerca Operativa Corso di Laurea in
Ingegneria Informatica e Automatica
21 giugno 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 Intera.
(a) Se un poliedro P ha tutti i vertici interi, allora esso rappresenta la formulazione ottima di ogni problema di PLI con insieme ammissibile P ∩ Zn.
(b) Se P `e una sua formulazione lineare allora l’insieme ammissibile del problema di PLI si pu`o scrivere nella forma P ∩ Zn.
(c) Se P1 e P2 sono due formulazioni del problema di PLI, e se risulta che P2 ⊆ P1 allora P1`e una formulazione migliore di P2.
(d) Il valore dell’ottimo del rilassamento lineare di un problema di PLI in forma di minimiz- zazione costituisce un lower bound del valore ottimo del problema di PLI.
2. Dire quali delle seguenti affermazioni sono corrette.
(a) In IR2, l’insieme dei punti a coordinate intere del primo quadrante `e un insieme convesso.
(b) Dati y ∈ IRn e z ∈ IRn, l’insieme {x ∈ IRn | x = λy + (1 − λ)z, 0 ≤ λ ≤ 1/2} `e un insieme convesso.
(c) In IR3, l’intersezione tra una sfera centrata nell’origine di raggio 1 e l’ortante positivo `e un politopo.
(d) L’insieme {x ∈ IRn | Ax ≥ b, l ≤ x ≤ u}, con A matrice m × n, x ∈ IRn, b ∈ IRm, l ∈ IRn e u ∈ IRn `e un politopo.
3. Si consideri il poliedro definito da
x1+ 2x2+ x4 ≥ θ 2x1+ ηx2+ x3 ≥ −2
x1+ 2x4 ≥ 1 x2 ≥ 0 x3 ≥ 0 x4 ≥ 0
con θ ∈ IR e η ∈ IR. Dire quali delle seguenti affermazioni sono corrette.
(a) Per θ = 2, il punto (1, 0, 0, 1)T `e vertice del poliedro per ogni valore η ∈ IR.
(b) L’origine `e vertice del poliedro se e solo se θ = 0 e per ogni valore di η ∈ IR.
(c) Il punto (−1, 1, 1, 1)T appartiene al poliedro per θ ≤ 2, η ≥ −1.
(d) Per θ = 3, il punto (0, 1, 1, 1)T `e vertice del poliedro se η = −3.
4. Dato un problema di Programmazione Lineare nella forma min cTx
Ax ≥ b,
si denoti con P il poliedro dell’insieme ammissibile del problema. Dire quali delle seguenti affermazioni sono corrette.
(a) Se ¯x `e un punto ammissibile che non `e un vertice di P , allora `e sempre possibile deter- minare un punto ˜x ∈ P nel quale il numero dei vincoli attivi linearmente indipendenti supera di almeno 1 il numero dei vincoli attivi linearmente indipendenti in ¯x.
(b) Per porre il problema in forma standard `e richiesto che il rango di A sia massimo.
(c) Se P `e non vuoto, allora il problema o risulta illimitato oppure ammette ottimo finito.
(d) Se P `e non vuoto e limitato, allora il problema ammette soluzione ottima su un vertice di P .
5. Sia dato il problema di Programmazione Lineare
min 3x1− x2+ 5x3+ x5+ x6
1 0 1 1 2 −1
1 1 3 −1 1 2
x =0
2
x = (x1, x2, x3, x4, x5, x6)T ≥ 0
Dire quali delle seguenti affermazioni sono corrette.
(a) La SBA associata alla base formata dalla 3ae dalla 2acolonna `e data da (0, 2, 0, 0, 0, 0)T. (b) Il problema `e in forma canonica.
(c) La base composta dalla 3a e dalla 2a colonna `e una base ammissibile.
(d) Il criterio di illimitatezza `e soddisfatto in corrispondenza della base formata dalla 3a e dalla 2a colonna.
6. 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 ammette sempre soluzione ottima.
(b) 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.
(c) Se ad una iterazione della Fase I del metodo del simplesso tutte le variabili artificiali sono fuori base, allora `e sicuramente verificato il criterio di ottimalit`a.
(d) Se il rango della matrice dei vincoli di uguaglianza non `e massimo, allora il problema artificiale che si risolve nella Fase I del metodo del simplesso `e illimitato inferiormente.
7. Si consideri il poliedro descritto dal seguente sistema x1+ 2x2+ x3 = 4 x1+ 4x2+ 2x3 = 7 2x1+ 10x2+ 5x3+ x4 = 17
xi≥ 0, i = 1, . . . , 4 Dire quali delle seguenti affermazioni sono corrette.
(a) L’origine degli assi `e vertice del poliedro.
(b) Il punto (1, 1, 1, 0)T `e vertice del poliedro.
(c) Il punto (1, 1, 1, 1)T appartiene al poliedro.
(d) Il poliedro non ammette vertici perch´e il numero delle variabili presenti (n) `e maggiore del numero dei vincoli di uguaglianza (m).
8. Dire quali delle seguenti affermazioni sono corrette.
(a) Dato un problema di Programmazione Lineare, si pu`o sempre costruire il problema duale associato.
(b) Se un problema di Programmazione Lineare ammette soluzione ottima, il suo duale potrebbe anche essere inammissibile.
(c) C’`e una corrispondenza biunivoca tra i vincoli del problema primale e le variabili del problema duale.
(d) Data una coppia primale–duale, la funzione obiettivo del problema primale calcolata in un punto ammissibile `e sempre minore del valore che la funzione obiettivo del duale assume in qualsiasi punto ammissibile per il problema duale.
9. In un’iterazione della Fase II del metodo del simplesso applicato ad un problema di Program- mazione Lineare in forma di minimizzazione si ha xB= (x6, x3, x8, x7)T e xN = (x1, x5, x2, x4)T, ed inoltre risulta γ = (1, 0, − 2, − 10)T.
B−1N =
−1 −1 0 1
2 −2 1 −1
1 −1 2 2
2 −4 1 0
, B−1b =
1 0 2 1/2
.
Dire quali delle seguenti affermazioni sono corrette.
(a) Supponiamo che x4 sia la variabile entrante. Allora la successiva Soluzione di Base Ammissibile sar`a degenere.
(b) Supponiamo che x2 sia la variabile entrante. Allora l’unica variabile uscente pu`o essere x3.
(c) Supponiamo che x4sia la variabile entrante. Allora la variabile uscente pu`o essere x7. (d) Supponiamo che x4sia la variabile entrante. Allora si ha ¯ρ = 0.
10. Al termine della Fase I del metodo del simplesso applicato alla soluzione di un problema di Programmazione Lineare risulta xB = (x3, α2, x2, α4)T, xN = (α3, x4, α1, x1)T,
B−1N =
3 4 2 3
−2 3 1 −1
2 6 7 5
0 0 0 2
, B−1b =
2 0 3 0
.
Dire quali delle seguenti affermazioni sono corrette.
(a) Il problema originario `e inammissibile perch´e sono presenti due variabili artificiali in base.
(b) Una possibile base ammissibile per il problema originario dalla quale far partire la Fase II corrisponde ad avere variabili di base xB= (x3, x4, x2, x1)T.
(c) Una possibile base ammissibile per il problema originario dalla quale far partire la Fase II corrisponde ad avere variabili di base xB= (x3, x1, x2)T.
(d) La matrice dei vincoli di uguaglianza del problema originario ha rango massimo.
