Corso di Laurea in
Ingegneria Informatica e Automatica
15 giugno 2015
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 o tablet.
– 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
1 Sia dato un problema di Programmazione Lineare la cui regione ammissibile `e non vuota e non contiene rette.
(a) Se il problema non `e illimitato, allora ammette soluzione ottima. (V) (b) Se il problema ha soluzione ottima allora la regione ammissibile `e limitata.
(c) Se il problema non ha soluzione ottima allora la regione ammissibile `e illimitata. (V) (d) Se la regione ammissibile `e illimitata, allora il problema non ammette soluzione ottima.
2. Dato il seguente problema
(max cTx x ∈ P
con P = {x ∈ IRn | Ax ≤ b}, A matrice m × n, e b ∈ IRm. Si supponga che P sia non vuoto.
(a) Il problema non `e un problema di Programmazione Lineare.
(b) L’insieme P non `e un poliedro.
(c) L’insieme P pu`o avere infiniti vertici.
(d) L’insieme P non pu`o avere vertici.
3. Si consideri un problema di Programmazione Lineare nella forma
min cTx Ax = b x ≥ 0 dove A una matrice m × n e rango(A) = m.
(a) La Fase II del metodo del simplesso applicata al problema dato con l’uso di regole anticiclaggio termina in un numero finito di iterazioni. (V)
(b) Se nell’applicazione della Fase II del metodo del simplesso al problema dato ogni soluzione di base ammissibile `e non degenere, allora in un numero finito di passi si trova soddisfatto il criterio di ottimalit`a o il criterio di illimitatezza. (V)
(c) Si pu`o sempre applicare direttamente la Fase II al problema dato in quanto si `e supposto che rango(A) = m.
(d) L’insieme ammissibile del problema dato, se non `e vuoto, ammette sempre vertici. (V)
2
4 Si consideri la Fase II del metodo del simplesso applicata ad un problema di Programmazione Lineare in forma standard con
A =1 0 −1 2 1 1
0 1 −2 1 −1 1
, b =2 1
, c =
0 1 2 1 0 0
.
Ad una certa iterazione del metodo del simplesso si ha B =1 0 0 1
.
(a) La Soluzione di Base Ammissibile associata a B soddisfa il criterio di ottimalit`a.
(b) `E verificato il criterio di illimitatezza.
(c) La quarta variabile fuori base `e l’unica variabile candidata ad entrare in base. (V) (d) Le variabili x1e x2sono entrambi variabili candidate ad uscire dalla base.
5. Al termine della fase I del metodo del simplesso applicato alla soluzione di un problema di PL risulta xB= (α1, x1, α3, x4)T, xN = (α4, x2, α2, x3)T,
B−1N =
5 0 7 0
0 −1 3 2 1 −2 4 0
1 1 0 0
, B−1b =
0 2 0 1
.
(a) Non esiste una base ammissibile per il problema originario.
(b) Il valore ottimo del problema artificiale `e 0. (V)
(c) Il problema di PL considerato presenta un vincolo ridondante. (V)
(d) Una possibile base ammissibile per il problema originario dalla quale far partire la fase II corrisponde ad avere variabili di base xB= (x1, x3, x4)T
6. Si consideri il poliedro descritto dal seguente sistema x1+ 2x2− x3+ x4 = 1
3x1− x2+ x3 = 4 5x2− x3+ x4 = τ xi≥ 0, i = 1, . . . , 4 con τ ∈ IR.
(a) Il punto (1, 1, 1, 1)T `e vertice del poliedro per ogni valore di τ . (b) Se τ = 0 allora il punto (1, 0, 1, 1)T `e vertice del poliedro. (V) (c) Il poliedro non ammette vertici comunque si scelga τ .
(d) Per τ = 0 il poliedro ammette al pi`u 4 vertici. (V)
3
7 Dire quali delle seguenti affermazioni sono vere e quali sono false.
(a) Se un problema di PL `e inammissibile allora il suo duale `e sicuramente illimitato.
(b) Se i vincoli di un problema di Programmazione Lineare sono espressi nella forma Ax ≥ 0, x ≥ 0, con A matrice m × n, allora il suo duale sar`a un problema con m variabili. (V) (c) Ad ogni variabile primale vincolata in segno corrisponde un vincolo di uguaglianza del
problema duale.
(d) Ad ogni vincolo di disuguaglianza del problema primale corrisponde una variabile duale vincolata in segno. (V)
8. Sia dato il seguente poliedro
2x1+ 2x2+ x3 ≤ 3 2x1− x2+ x3 ≥ 3 x2 ≥ 0 x3 ≥ 0 (a) Il punto (3/2, 0, 0) `e un vertice del poliedro. (V) (b) Il punto (−2, 0, 7) appartiene al poliedro. (V) (c) Il punto (−2, 0, 7) `e un vertice del poliedro.
(d) Il punto (1, 1, 1) `e un vertice del poliedro.
9. Si consideri un problema di Programmazione Lineare Intera (PLI) nella forma
min cTx Ax ≥ b
x ≥ 0, intero
(a) Se P `e un poliedro di IRntale che P ∩ Zn= {x ∈ IRn | Ax ≥ b, x ≥ 0, intero}, allora P `e una formulazione lineare del problema di PLI. (V)
(b) Se P e P′ sono due diverse formulazioni lineari del problema di PLI, e P′⊆ P allora P
`e una formulazione migliore di P′.
(c) Sia ¯x soluzione ottima del problema di PLI. Sia P `e una formulazione lineare del problema di PLI, e sia x⋆la soluzione ottima del problema
(min cTx x ∈ P Allora risulta cTx⋆≤ cTx. (V)¯
(d) La formulazione ottima di un problema di PLI `e necessariamente un politopo.
10. Dire quali affermazioni sono vere e quali sono false.
(a) La matrice di incidenza di un grafo (non orientato) bipartito `e unimodulare. (V) (b) La matrice di incidenza di un grafo orientato `e totalmente unimodulare (V)
(c) Sia dato un grafo orientato pesato. Il problema della determinazione del cammino ori- entato di peso minimo tra due nodi del grafo ammette sempre soluzione.
(d) L’algoritmo di Dijkstra si pu`o sempre applicare ad un qualsiasi grafo orientato pesato determinando, in un numero finito di iterazioni, l’albero dei cammini minimi.
4
