Prova scritta di Ricerca Operativa Corso di Laurea in
Ingegneria Informatica e Automatica
19 aprile 2013
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
1. Dire quali delle seguenti affermazioni sono corrette:
(a) Se un problema di Programmazione Lineare ha pi`u di una soluzione ottima, allora ne ha infinite.
(b) Sia dato un problema di Programmazione Lineare in forma di minimizzazione con regione ammissibile non vuota e che non contiene rette. Se la funzione obiettivo `e sempre maggiore di -10 nella regione ammissibile, il problema ammette soluzione ottima.
(c) Se la regione ammissibile di un problema di Programmazione Lineare `e illimitata, allora anche il problema di Programmazione Lineare `e illimitato.
(d) Un problema di Programmazione Lineare pu`o avere due sole soluzioni ottime distinte.
2. Dire quali delle seguenti affermazioni sono corrette.
(a) L’insieme S = {(x, y)T ∈ IR2 : x cosβ + y senβ ≤ 1, x ≥ 0, y ≥ 0} per un fissato β ∈ [0, π/2] `e un poliedro in IR2
(b) L’insieme di tutte le x ∈ IR che soddisfano il vincolo x2− 8x + 15 ≤ 0 `e un poliedro.
(c) Se un punto ¯x non `e un vertice del poliedro di IRn descritto dai vincoli {aTi x ≥ bi, i = 1, . . . n},
allora `e possibile trovare un vettore d ∈ IRn non nullo tale che risulti aTi d = 0 per ogni indice i appartenente all’insieme degli indici dei vincoli attivi in ¯x.
(d) Un poliedro `e un insieme limitato.
3. Dire quali delle seguenti affermazioni sono corrette.
(a) In un problema di Programmazione Lineare le variabili x sono sempre vincolate a essere non negative.
(b) In un problema di Programmazione Lineare la funzione obiettivo pu`o essere sia da min- imizzare che da massimizzare.
(c) Esistono problemi di Programmazione Lineare che non possono essere riscritti in forma standard.
(d) Un problema di Programmazione Lineare in forma standard non pu`o avere equazioni lineari come vincoli.
4. Dire quali delle seguenti affermazioni sono corrette.
(a) Il problema artificiale (ausiliario) che si risolve nella fase I del metodo del simplesso pu`o essere inammissibile.
(b) Se il problema artificiale (ausiliario) che si risolve nella fase I del metodo del simplesso ha valore ottimo positivo, allora il problema originario `e illimitato inferiormente.
(c) Se il problema artificiale (ausiliario) che si risolve nella fase I del metodo del simplesso ha valore ottimo pari a zero, allora tutte le variabili artificiali sono fuori base.
(d) Se il problema artificiale (ausiliario) che si risolve nella fase I del metodo del simplesso ha valore ottimo pari a zero, allora il problema originario ha sicuramente una soluzione ottima.
2
5. In un’iterazione del metodo del simplesso risulta xB = (x1, x3, x5)T, xN = (x2, x6, x7, x4)T,
B−1N =
3 12 10 −5
11 −2 −1 1
0 3 7 −2
, γ =
3 6 0
−1
, B−1b =
1 2 3
Dire quali delle seguenti affermazioni sono corrette.
(a) La soluzione di base corrente soddisfa il criterio di ottimalit`a.
(b) Le iterazioni della fase II del metodo del simplesso devono continuare facendo entrare in base la variabile x4.
(c) Le iterazioni della fase II del metodo del simplesso devono continuare facendo entrare in base la variabile x7.
(d) La Soluzione di Base Ammissibile corrente `e degenere.
6. Sia dato il seguente poliedro:
x1 −2x2 ≥ 4
x2 +x4 = 11
x2 +x3 = 4
x1 ≥ 0
Dire quali delle seguenti affermazioni sono corrette.
(a) il punto (12, 4, 0, 7)T non appartiene al poliedro.
(b) il punto (12, 4, 0, 7)T `e un vertice del poliedro.
(c) il punto (14, 5, − 1, 6)T non appartiene al poliedro.
(d) il punto (0, − 2, 6, 13)T `e un vertice del poliedro.
7. In un’iterazione della Fase I del metodo del simplesso risulta
xB=
α1 x4 x5 α4
, xN =
α2 x2 x3 α3
, B−1b =
0 12 25 0
,
B−1N =
0 15 21 11
7 1 0 −31
2 −5 0 9
0 −1 0 0
Dire quali delle seguenti affermazioni sono corrette.
(a) Il problema originario `e inammissibile.
(b) `E presente un vincolo ridondante.
(c) La Soluzione di Base Ammissibile corrente `e ottima per il problema artificiale.
(d) Pu`o essere effettuato uno scambio degenere tra le variabili α4e x3.
3
8. Sia dato il seguente poliedro
2x1+ x2+1
2x4+ 4x5 = 2 2x1+ x2+ x3− 2x5 = 2 x ≥ 0
Dire quali delle seguenti affermazioni sono corrette:
(a) Il punto (0, 0, 2, 4, 0) `e una Soluzione di Base Ammissibile.
(b) Il punto (1, 0, 0, 0, 0) `e un vertice.
(c) La prima e la seconda colonna della matrice dei vincoli di uguaglianza formano una base ammissibile.
(d) La Soluzione di Base associata alla base formata dalla 1ae dalla 5acolonna `e (1, 0, 0, 0, 0).
9. Sia data una soluzione di base ammissibile ¯x di un problema di PL (in forma standard).
Si supponga che le variabili x1, x2, x3 siano in base mentre le variabili x4, x5, x6, x7 sono fuori base. Il valore della funzione obiettivo in ¯x `e 7 e i coefficienti di costo ridotto sono γT = (0, 2, −1, 2). Dire quali delle seguenti affermazioni sono corrette.
(a) Il valore della funzione obiettivo nel punto ammissibile xTB = (x1, x2, x3) = (3, 7, 9), xN = (25, 1, 3, 4)T `e 14
(b) Non sono dati elementi sufficienti per calcolare il valore della funzione obiettivo nel punto ammissibile xTB = (x1, x2, x3)T = (3, 7, 9)T, xN = (25, 1, 3, 4)T `e 14
(c) Il valore della funzione obiettivo nel punto ammissibile xTB = (x1, x2, x3)T = (3, 7, 9)T, xN = (25, 1, 3, 4)T `e 19.
(d) La Soluzione di Base Ammissibile corrente soddisfa il criterio di ottimalit`a.
10. Dire quali delle seguenti affermazioni sono corrette:
(a) Il problema duale del problema di Programmazione Lineare (min cTx
Ax ≥ b
`e dato da
(min bTu ATu = c
(b) Un problema e il suo duale non possono mai avere lo stesso numero di variabili.
(c) Se un problema di Programmazione Lineare `e inammissibile, allora anche il suo duale deve anch’esso essere necessariamente inammissibile.
(d) Il valore della funzione obiettivo in un punto ammissibile di un problema di Program- mazione Lineare `e sempre uguale al valore che la funzione obiettivo del problema duale assume in corrispondenza di qualsiasi punto ammissibile.
4
