• Non ci sono risultati.

Prova scritta di Ricerca Operativa Corso di Laurea in Ingegneria Informatica e Automatica

N/A
N/A
Protected

Academic year: 2021

Condividi "Prova scritta di Ricerca Operativa Corso di Laurea in Ingegneria Informatica e Automatica"

Copied!
4
0
0

Testo completo

(1)

Prova scritta di Ricerca Operativa Corso di Laurea in

Ingegneria Informatica e Automatica

12 aprile 2012

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

(2)

1. (a) L’insieme {(x, y) ∈ <2 | y ≥ x2, y ≤ 4} `e un poliedro;

(b) i punti (−2, 4), (2, 4), (0, 0) sono tutti e soli i vertici dell’insieme {(x, y) ∈ <2 | y ≥ x2, y ≤ 4};

(c) l’intersezione di un poliedro e di un insieme convesso `e un insieme convesso, ma non necessariamente un poliedro;

(d) l’intersezione di due iperpiani `e un insieme convesso.

2. Sia dato il poliedro P = {x ∈ <n | Ax ≥ b} con A matrice m × n e b ∈ <m; siano aTi le righe di A e I(¯x) l’insieme dei vincoli attivi in ¯x.

(a) Un punto ¯x ∈ P `e vertice di P se il rango della matrice {aTi, i ∈ I(¯x)} `e pari a n;

(b) se m < n, allora P non ammette vertici;

(c) se il numero dei vincoli attivi in un punto ¯x `e minore di n, allora deve esistere d ∈ <n, d 6= 0 tale che aTi d = 0 per ogni i ∈ I(¯x);

(d) se ¯x `e vertice di P allora la matrice A non pu`o avere rango minore di n.

3. Sia dato un problema di PL

min cTx Ax ≥ b.

Allora

(a) Se l’insieme ammissibile `e non vuoto, allora comunque si sceglie M ∈ <, M > 0, allora

`e possibile trovare un punto x ammissibile tale che cTx ≤ −M ;

(b) il problema pu`o essere illimitato (inferiormente) se e solo se l’insieme ammissibile `e illimitato;

(c) se il problema non ammette soluzione ottima, allora l’insieme ammissibile pu`o essere vuoto oppure non vuoto;

(d) se la funzione obiettivo cTx viene sostituita da una funzione non lineare, il Teorema Fon- damentale continua a valere, ma la soluzione ottima pu`o non essere un vertice dell’insieme ammissibile.

4. Dato il poliedro definito dal sistema

x1− 2x2 ≤ 1 x1+ x3 ≤ 2 x2+ 2x3− x4 ≤ 3

x ≥ 0

(a) Il punto (1, 0, 1, 0)T `e un vertice del poliedro;

(b) Il punto (3, 1, 1, 0)T non appartiene al poliedro;

(c) Il punto (0, 0, 2, 1)T `e un vertice del poliedro;

(d) L’origine `e un vertice del poliedro.

5. Sia dato un problema di Programmazione Lineare e si consideri la Fase I nella quale si risolve il problema artificiale.

2

(3)

(a) L’applicazione della Fase II al problema articificiale porta sempre ad indentificare un punto di ottimo del problema artificiale;

(b) se non si pu`o applicare la Fase II al problema artificiale allora il problema originario non

`e ammissibile;

(c) se la matrice dei vincoli del problema originario ha rango massimo, allora non `e necessario effettuare la Fase I;

(d) se il problema artificiale ammette soluzione ottima allora il valore all’ottimo della fun- zione obiettivo `e zero.

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 qualche componente di B−1b `e negativa allora non `e soddisfatto il criterio di otti- malit`a;

(b) se risulta γi= 0 e (B−1N )i≤ 0, allora `e soddisfatto il criterio di illimitatezza;

(c) il vettore xB = B−1b `e univocamente determinato;

(d) si possono sempre scrivere i vincoli di uguaglianza del problema nella forma BxB+N xn= b.

7. Arrivati all’ottimo del problema artificiale che si risolve nella fase I del metodo del simplesso abbiamo che risulta xB= (x4, α2, α3, x2), xN = (x1, α1, x3, α4),

B−1b =

 0 0 0 0

, B−1N =

5 13 1 1

0 5 −1 6

1 −4 2 4

0 5 0 9

Allora

(a) Poich´e il vettore B−1b `e tutto a componenti nulle, la matrice dei vincoli del problema originario ha un vincolo ridondante;

(b) una possibile base ammissibile per il problema originario dalla quale far partire la Fase II corrisponde ad avere variabili di base xB= (x4, x3, x1, x2);

(c) una possibile base ammissibile per il problema originario dalla quale far partire la Fase II corrisponde ad avere variabili di base xB= (x4, x1, x3, x2);

(d) se non si fosse a conoscenza di quali variabili sono in base (ovvero non fosse noto xB), sapendo che il vettore B−1b `e tutto a componenti nulle, si pu`o comunque dedurre che il problema originario `e ammissibile.

8. Ad una iterazione della fase II del metodo del simplesso si ha: xB= (x3, x5, x1)T, xN = (x2, x6, x4)T,

B−1N =

σ −1 0

3 0 −1

5 0 0

, B−1b =

 σ 1 1

Se la funzione obiettivo (da minimizzare) `e f (x1, x2, x3, x4, x5, x6) = x3+ x6 allora

3

(4)

(a) se σ < 0, la SBA corrente soddisfa il criterio di ottimalit`a;

(b) per σ > 0 la variabile x6`e una variabile candidata ad entrare in base;

(c) non esistono valori di σ per il quali il criterio di illimitatezza `e soddisfatto;

(d) per σ > 0 allora x1`e una variabile candidata a uscire dalla base.

9. Sia dato il seguente poliedro

x1− x2 = 0 2x1+ τ x3 = 2 x1+ x3+ x4 = 1

x ≥ 0

(a) il punto (1, 1, 0, 0)T `e un vertice del poliedro per ogni valore di τ ; (b) esistono valori di τ per i quali il punto (1, 1, 1, − 1)T `e una SBA;

(c) per τ = 2 il punto (0, 0, 1, 0)T `e una SBA;

(d) per τ = 0 l’origine `e un vertice del poliedro.

10. Sia dato il seguente problema di Programmazione Lineare:

min cTx Ax = 0 x ≥ 0 (a) Il suo duale `e

 max cTu ATu ≤ c

(b) un problema di PL e il suo duale possono essere entrambi inammissibili;

(c) il numero delle variabili di un problema duale `e pari al numero dei vincoli del problema primale;

(d) dati due punti ¯x ammissibile per il primale e ¯u ammissibile per il duale. Se il valore della funzione obiettivo del problema primale calcolata in ¯x coincide con il valore della funzione obiettivo del problema duale calcolata in ¯u, allora i due punti sono soluzioni ottime per i rispettivi problemi.

4

Riferimenti

Documenti correlati

• Per ogni affermazione VERO/FALSO NON correttamente individuata viene assegnato un punteggio negativo pari a -0.25 punti7. Supera la prova chi totalizza un punteggio pari ad almeno

• Per ogni affermazione VERO/FALSO NON correttamente individuata viene assegnato un punteggio negativo pari a -0.25 punti7. Supera la prova chi totalizza un punteggio pari ad almeno

(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

(b) Nella sequenza delle basi generate durante la Fase II del metodo del simplesso una ripetizione non pu` o verificarsi se supponiamo che ogni soluzione di base ammissibile sia

(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..

• 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

• 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

(b) Se il problema ammette soluzione ottima, esiste sempre almeno un punto tale che le colonne della matrice della matrice A corrispondenti alle componenti positive di questo punto