Esame di Ricerca Operativa Corso di Laurea in Ingegneria Informatica e Automatica

(1)

Esame di Ricerca Operativa Corso di Laurea in

Ingegneria Informatica e Automatica

18 settembre 2014

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à altra possibilità di consegna e dovrà 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

(2)

1. Sia P = {x ∈ IRⁿ : 0 ≤ xⁱ ≤ 1, i = 1, . . . , n}. Dire quali delle seguenti affermazioni sono corrette.

(a) Il punto (1/2, 1/2, . . . , 1/2)^⊤`e un vertice di P . (b) Il punto (0, 0, . . . , 0, 1)^⊤`e un vertice di P . (V)

(c) Nel punto (0, 0, . . . , 0)^⊤sono attivi n vincoli. (V) (d) Nell punto (0, 1/2, 0, . . . , 0)^⊤sono attivi n vincoli.

2. Sia P = {x ∈ IRⁿ: Ax ≥ b} un poliedro, con A ∈ IR^m×ne b ∈ IR^m, e sia v ∈ P un suo vertice.

(a) `E possibile trovare un vettore d 6= 0ntale che risulti x = v + λd ∈ P per ogni λ ∈ IR.

(b) In v sono attivi almeno n vincoli. (V) (c) In v sono attivi al pi`u n vincoli.

(d) P pu`o contenere delle semirette. (V)

3. Sia P = {x ∈ IRⁿ: Ax ≥ b, x ≥ 0n}, con A ∈ IR^m×n, b ∈ IR^m. (a) P non contiene rette. (V)

(b) P `e in forma standard.

(c) P ammette sempre vertici.

(d) P ammette sempre punti ammissibili.

4. Sia (P A) il problema che si risolve nella Fase I del metodo del Simplesso.

(a) (P A) ammette soluzioni il cui valore della funzione obiettivo `e negativo.

(b) Il valore ottimo di (P A) `e necessariamente zero.

(c) Se il problema originario `e inammissibile allora (P A) `e illimitato inferiormente.

(d) (P A) potrebbe non ammettere soluzioni di base ammissibili.

5. Siano (P ) : min{c^⊤x : Ax ≥ b, x ≥ 0n} e (D) : max{b^⊤u : A^⊤u ≤ c, u ≥ 0m} con c ∈ IRⁿ, b ∈ IR^me A ∈ IR^m×n. Sia ¯x un punto ammissibile di (P ).

(a) (D) potrebbe essere inammissibile. (V) (b) (D) potrebbe essere illimitato superiormente.

(c) (D) potrebbe ammettere soluzione ottima. (V)

(d) Esistono soluzioni ammissibili u di (D) tali che b^⊤u > c^⊤x.¯ 6. Si consideri il seguente poliedro

x1+ x2− x3 ≤ τ x1+ x3 ≥ 2 x3 ≤ 0 x1 ≥ 0 (a) Il punto (2, 1, 0)^⊤`e un vertice per ogni τ ∈ IR.

(b) Il punto (2, −1, 0)^⊤`e un vertice per ogni τ ∈ IR.

(c) Per τ = 2, il punto (2, −1, 0)^⊤`e un vertice.

(d) Per τ = 1, il punto (0, 1, 0)^⊤`e un vertice.

2

(3)

7. Al termine della Fase I del metodo del Simplesso risulta x^B = (x1, α1, x3)^⊤, x^N = (x2, α2, x4)^⊤,

B⁻¹N =





5 −1 −1

0 3 0

2 4 4



, B⁻¹b =



 0 β 1



.

(a) Per ogni β ∈ IR, il problema originario `e inammissibile.

(b) Per β > 0, nel problema originario `e presente un vincolo ridondante.

(c) Per β = 0, una base ammissibile da cui far partire la Fase II del metodo del Simplesso

`e {x1, x4, x3}.

(d) Per β = 0, il problema originario `e inammissibile.

8. Sia A una matrice m × n di rango m.

(a) A si dice totalmente unimodulare se ogni sua sottomatrice quadrata ha determinante pari a 0, 1, o −1. (V)

(b) Se A `e non singolare e ha elementi pari a 0, 1 o −1 allora `e totalmente unimodulare.

(c) Se A `e totalmente unimodulare allora i suoi elementi devono essere pari a 0, 1 o −1. (V)

(d) La matrice A =





1 0 1 0

0 1 0 −1

0 0 1 1



`e totalmente unimodulare. (V)

9. Sia P = {x ∈ IRⁿ: Ax = b, x ≥ 0n}, A ∈ IR^m×n, b ∈ IR^m. Inoltre risulti rg(A) = m

(a) Una sottomatrice B di A, quadrata e di rango m `e una base ammissibile se e solo se B⁻¹b > 0.

(b) Una sottomatrice B di A, quadrata e di rango m `e una base ammissibile se e solo se B⁻¹b ≥ 0. (V)

(c) Esistono matrici di base di dimensione strettamente minore di m.

(d) Un punto x ammissibile soddisfa i vincoli B⁻¹b − B⁻¹N xN ≥ 0m e xN ≥ 0n−m. (V) 10. Sia dato un problema di PL in forma standard di minimizzazione.

(a) Il metodo del simplesso con regole anticiclaggio si arresta, in un numero finito di passi, in una SBA ottima.

(b) La Fase I del metodo del Simplesso con regole anticiclaggio determina, in un numero finito di passi una prima SBA.

(c) La Fase I del metodo del Simplesso con regole anticiclaggio determina, in un numero finito di passi se il problema `e illimitato inferiormente.

(d) La Fase I del metodo del Simplesso con regole anticiclaggio determina, in un numero finito di passi se il problema `e ammissibile. (V)

3

(4)