22/5/2014 - IASI-CNR

1) Un rilassamento di un problema di programmazione matematica (P) `e
(a) Un problema ottenuto da (P) trascurando alcune variabili. FALSA
(b) Un problema ottenuto da (P) trascurando alcuni vincoli. VERA
(c) Un problema ottenuto da (P) trascurando la funzione obiettivo. FALSA
(d) Un problema equivalente a (P), cio`e che certamente fornisce la medesima soluzione ottima. FALSA
2) Sia P = min{f (x) : x ∈ F } un problema di programmazione matematica
e (Pr) un suo rilassamento. Indichiamo con x∗ l’ottimo globale di (P) e
con x∗r quello del rilassamento. Risulta
(a) f (x∗r ) ≤ f (x∗ ). VERA
(b) f (x∗r ) > f (x∗ ). FALSA
(c) sempre f (x∗r ) = f (x∗ ). FALSA
(d) sempre f (x∗r ) < f (x∗ ). FALSA
3) Dato un problema di PL, min{c⊤ x : x ∈ P }, un oracolo di separazione
per P `e una procedura che dato un punto x¯
(a) Dice se x
¯ appartiene al poliedro P . FALSA
(b) Dice se x
¯ `e soluzione ottima del problema (PL). FALSA
(c) Fornisce una disequazione a⊤ x ≥ a0 violata da x
¯, se x
¯ 6∈ P . FALSA
(d) Fornisce una disequazione a⊤ x ≥ a0 violata da x
¯, se x
¯ 6∈ P , oppure
conclude che tale disequazione non esiste. VERA
4) Se risolviamo un problema di PL, min{c⊤ x : x ∈ P }, con un algoritmo
dinamico primale (generazione di righe),
(a) Questo algoritmo termina quando sono stati generati tutti i vincoli
che forniscono una rappresentazione esterna di P . FALSA
(b) Non tutte le disequazioni di una rappresentazione esterna di P saranno
necessariamente generate dall’algoritmo. VERA
` necessario disporre di un oracolo di separazione. VERA
(c) E
(d) Non `e necessario disporre di un oracolo di separazione. FALSA
5) Dato un problema, di PLI (c, S) = min{c⊤ x : x ∈ S}, con S ⊂ Zn
(a) Una formulazione di (c, S) `e un poliedro. VERA
(b) Se P `e una formulazione di (c, S), allora P ∩ Zn = S. VERA
(c) Una formulazione di (c, S) `e un rilassamento. FALSA
(d) Un rilassamento di (c, S) `e un poliedro. FALSA
1
6) Dato un problema di PLI, (c, S) = min{c⊤ x : x ∈ S}, con S ⊂ Zn , sia P
una formulazione.
(a) Il rilassamento lineare di (c, S) `e un problema che si ottiene trascurando gli eventuali vincoli nonlineari. FALSA
(b) Il rilassamento lineare di (c, S) `e il problema continuo min{c⊤ x : x ∈
P }. VERA
(c) Il rilassamento lineare coincide con la formulazione P . FALSA
(d) La soluzione ottima del rilassamento lineare, se a componenti intere
`e anche soluzione di (c, S) . VERA
7) Dato un problema di PLI, (c, S) = min{c⊤ x : x ∈ S}, e due sue formulazioni P1 e P2 , diciamo che P1 `e migliore di P2
(b) Quando P2 ⊂ P1 . FALSA
(c) Quando c⊤ x1 < c⊤ x2 , con xi soluzione ottima di min{c⊤ x : x ∈ Pi },
i = 1, 2. FALSA
(a) Quando P1 ⊂ P2 . VERA
(c) Quando c⊤ x1 > c⊤ x2 , con xi soluzione ottima di min{c⊤ x : x ∈ Pi },
i = 1, 2. FALSA
8) Il metodo del Piano di Taglio di Gomory
(a) Termina in un numero finito di passi. VERA
(b) Determina la soluzione ottima di un problema di PLI risolvendo problemi lineari (continui). VERA
(c) Definisce una sequenza finita di formulazioni P1 , P2 , . . . , Pr . VERA
(d) Potrebbe terminare con una soluzione ottima non intera. FALSA
9) L’i-esima chiusura di Chv´atal di una formulazione di un problema di PLI
(c, S)
` un poliedro. VERA
(a) E
` una formulazione. VERA
(b) E
` un problema. FALSA
(c) E
(d) Coincide con l’insieme delle soluzioni ammissibili intere S. FALSA
10) Nell’algoritmo di Branch & Bound per la soluzione di un problema di PLI
di minimo, un sottoproblema pu`
o essere chiuso
(a) Quando il lower bound calcolato al nodo `e maggiore o uguale all’upper
bound. VERA
(b) Solo quando il lower bound calcolato al nodo `e maggiore stretto
dell’upper bound. FALSA
2
(c) Quando la soluzione del rilassamento del sottoproblema fornisce una
soluzione intera. VERA
(d) Solo quando la soluzione del rilassamento del sottoproblema fornisce
una soluzione intera. FALSA
3
Foglio Risposte
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
4

Download Report