Ricerca operativa

DOMANDA 8:

Una soluzione di base di un problema PLC è chiamata degenerare quando:

1) ci sono più variabili rispetto ai vincoli;

2) il numero di variabili di base con valore zero è uguale al numero di vincoli;

3) il numero di variabili di base con valore zero è uguale alla differenza di numero di colonne e righe (n

- m);

4) il numero di variabili di base con valore diverso da zero è uguale al numero di righe nella matrice

dei vincoli;

5) la matrice di base è invertibile.

DOMANDA 9:

Dato un problema di PLC, l'analisi di sensibilità di un valore b del lato destro:

1) definisce un limite superiore sul valore della soluzione ottimale;

2) definisce il valore minimo e massimo di b che non modifica la base ottimale;

3) definisce il valore minimo e massimo di b che non cambia il valore della soluzione ottima;

4) definisce l'intervallo di valori di b che non modifica i costi ridotti;

5) definisce l'intervallo di valori di b che non lo fa modificare le doppie variabili;

DOMANDA 10:

Il metodo branch-and-bound:

1) viene utilizzato per trovare la complessità computazionale di problema;

2) può essere applicato a problemi di minimizzazione in forma standard;

3) trova l'ottimo soluzione di un problema NP-completo;

4) utilizzare sempre come procedura di delimitazione la soluzione di a Problema PLC;

5) nessuna delle risposte precedenti.

DOMANDA 11:

Dato un problema PLC P in forma di minimizzazione, con 2 vincoli con segno '≥' e 1

vincolo con segno '=' e 5 variabili, considera il problema duale D:

1) D ha 3 variabili e 5 vincoli;

2) D ha 5 variabili e 3 vincoli;

3) la prima variabile di D deve essere non negativo;

4) la terza variabile di D non ha restrizioni di segno;

5) la seconda variabile di D deve essere non positivo.

DOMANDA 12:

Il metodo del piano di taglio:

1) viene utilizzato per risolvere problemi di programmazione lineare con variabili tinue;

2) termina con un numero polinomiale di iterazioni;

3) viene utilizzato per risolvere Problemi NP-completi ("difficili");

4) ad ogni iterazione utilizza l'algoritmo simplex per risolvere il sottoproblema corrente;

5) utilizza la strategia più basso primo per esplorare i sottoproblemi.

DOMANDA 13:

Dato il modello PLI min {c T x: x P ∩ Z n } con P = {Ax = b, x ≥ 0} e l'ottimale

∈

soluzione x del suo rilassamento continuo, il taglio di Gomory è:

∗

1) una disuguaglianza per P che soddisfa il lemma di Farkas;

2) una disuguaglianza α T F x F ≥ α 0 soddisfatto da qualsiasi x P;

∈

3) una disuguaglianza α T F x F ≥ α 0 soddisfatto da qualsiasi x P ∩ Z n , ma non da x ;

∈ ∗

4) una disuguaglianza α T F x F ≥ α 0 soddisfatto da qualsiasi x P ma non da x ;

∈ ∗

5) nessuna delle risposte precedenti.

DOMANDA 14:

Considera i due problemi, P: min {c T x: Ax = b, x ≥ 0}, D: max {u T b: u T A ≤ c T },

allora

1) una soluzione ammissibile di P dà un limite inferiore al valore ottimo di D;

2) fattibile la soluzione di D dà un limite inferiore al valore ottimo di P;

3) una coppia di soluzioni x e u con x ammissibile per P eu ammissibile per D sono ottimali se c T - c T

B B −1 A ≥ 0;

4) un paio di soluzioni x eu tali che (u T A - c T ) x = 0 sono ottimi se x ≥ 0;

5) una coppia di soluzioni x e u sono ottimale se x ≥ 0 eu ≥ 0.

DOMANDA 15:

Dato un problema PLC P in forma standard con n variabili e m vincoli, si consideri il

metodo in due fasi. Il problema artificiale utilizzato per risolvere la prima fase:

1) ha m variabili e n vincoli;

2) ha al massimo n + m variabili e m vincoli;

3) ha una funzione oggettiva in forma di massimizzazione;

4) fornisce una base ammissibile per il problema P, se la sua soluzione ottima ha valore zero;

5) fornisce una soluzione ammissibile e ottimale per il problema P se la sua soluzione ottima ha un

negativo valore;

DOMANDA 16:

Considera un grafo G = (V, E), il problema dell'albero di copertura più breve e la sua soluzione ottimale

T . (Non trattato)

∗ 1) l'arco con costo minimo è sempre in T ;

∗

2) il bordo con costo minimo è in T solo se non chiude un ciclo con altri bordi;

∗

3) il bordo con il costo massimo è sempre dentro T ;

∗

4) l'arco con il secondo costo minimo è sempre in T ;

∗

5) il bordo con il secondo minimo il costo è in T solo se l'arco con costo minimo non è in T .

∗ ∗

DOMANDA 17:

Il costo ridotto di una variabile di base x j , in un tableau in forma base:

1) è sempre nullo;

2) è strettamente positivo se la soluzione attuale è ottimale e il problema è in forma di minimizzazione;

3) ha un valore non negativo se la soluzione attuale è ottimale e il problema è in minimizzazione modulo;

4) ha un valore non positivo se la soluzione corrente è ottimale e il problema è in modulo di

minimizzazione;

5) rappresentano la variazione della funzione obiettivo quando la rhs di j-esimo vincolo aumenta di una

unità;

DOMANDA 18:

Dato un problema plc primario nella minimizzazione da e il suo duplice:

1) se il primale ha una soluzione finita, allora il duale ha una soluzione finita

2) se il primale è vuoto, il duale è vuoto

3) se il primordiale è illimitato, allora il duale è illimitato

4) una soluzione duale ammissibile può avere un valore inferiore a quello della soluzione primaria ottima

5) qualsiasi soluzione ammissibile del primale ha un valore maggiore o uguale a qualsiasi soluzione

ammissibile del duale

DOMANDA 19:

Dato un problema plc con n variabili e m vincoli, una matrice di base è:

1) nessuna delle risposte precedenti

2) una matrice quadrata mxn con valore 1 sulla diagonale principale

3) una sottomatrice quadrata della matrice dei vincoli, che può essere invertita

4) una raccolta di n-m colonne della matrice dei vincoli

5) una raccolta di m vincoli

DOMANDA 20:

Il metodo branch-and-bound per problemi di zaino 0-1:

1) utilizza un albero decisionale con un numero esponenziale di nodi

2) utilizza la strategia più bassa per esplorare l'albero decisionale

3) calcola un limite superiore in ogni nodo dell'albero decisionale

4) utilizza un albero decisionale con un numero polinomiale di livelli

5) utilizza un albero decisionale con un numero esponenziale di livelli

DOMANDA 21:

Il metodo branch-and-cut:

1) utilizza sempre la strategia più bassa prima per esplorare i sottoproblemi

2) viene utilizzato per risolvere problemi NP-completi ("difficili")

3) ad ogni iterazione utilizza l'algoritmo simplex per risolvere il sottoproblema corrente

4) termina con un numero polinomiale di iterazioni

5) viene utilizzato per risolvere problemi di programmazione lineare con variabili continue

DOMANDA 22:

Dato un problema PLC primordiale in forma di minimizzazione e suo duale

1) se il primale è vuoto, il duale è vuoto

2) se il primale come soluzione finita, allora il duale come soluzione finita

3) una soluzione duale ammissibile può avere un valore inferiore a quello della soluzione primaria ottimale

4) se il primordiale è illimitato, allora il duale è illimitato

5) qualsiasi soluzione ammissibile del primale ha un valore maggiore o uguale a qualsiasi soluzione

ammissibile del duale

DOMANDA 23:

Dato il seguente tableau di un problema PLC in forma di minimizzazione:

x1 x2 x3 x4 x5 -z

0 2 0 a -3 -5

1 0 0 d -2 b

0 1 1 -1 2 8

1) se a> 0, il tableau rappresenta una soluzione ottimale

2) se a = d = 0, la colonna di x1 e x4 fornisce una doppia soluzione ammissibile

3) se b> = 0 il problema non è vuoto

4) il problema è illimitato, indipendentemente dai valori di a, be d

5) se a = 0, b> 0, le colonne di x1 e x2 danno una soluzione ammissibile primaria

DOMANDA 24:

Considera un problema di minimizzazione e l'algoritmo dual simplex:

1) ad ogni passo il valore della soluzione corrente è un limite superiore al valore ottimale

2) ad ogni passo il valore della soluzione corrente è un limite inferiore al valore ottimale

3) l'operazione di pivot viene eseguita sugli elementi aij> 0

4) l'operazione di pivot viene eseguita sugli elementi aij <0

5) i costi ridotti eT diventano non negativi nell'ultima iterazione (dando la soluzione ottimale)

DOMANDA 25:

Il metodo del piano di taglio:

1) viene utilizzato per risolvere problemi di programmazione lineare con variabili continue

2) viene utilizzato per risolvere problemi NP-completi ("difficili")

3) termina con un numero polinomiale di iterazioni

4) utilizza la strategia più bassa prima per esplorare i sottoproblemi

5) ad ogni iterazione utilizza l'algoritmo simplex per risolvere il sottoproblema corrente

DOMANDA 26:

Dato un modello PLI IP in forma di minimizzazione, considerare il suo rilassamento continuo e sia z * il

valore ottimale del rilassamento:

1) z * è un limite superiore al valore IP ottimale

2) z * è un limite inferiore al valore IP ottimale

3) (estremo superiore) di z * è un limite inferiore al valore IP ottimale se i coefficienti della funzione

obiettivo sono interi

4) (estremo superiore) di z * è un limite superiore al valore IP ottimale

5) (estremo superiore) di z * è un limite inferiore al valore IP ottimale se i coefficienti della funzione

obiettivo sono numeri razionali

DOMANDA 27:

Un problema NP-completo:

1) può essere risolto esattamente utilizzando algoritmi di tempo polinomiale con un grado elevato

2) non può essere risolto esattamente utilizzando computer all'avanguardia

3) non può essere risolto esattamente in tempo polinomiale

4) ha una complessità computazionale non superiore a O (n ^ 2)

5) nessuna delle risposte precedenti

Domanda 28:

Qualsiasi problema NP-completo:

1) può essere risolto esattamente usando l’algoritmo del simplesso con un numero di iterazioni non

polinomiale.

2) Può essere risolto esattamente utilizzando l’algoritmo del simplesso con l’aggiunta di tagli di

gomory

3) Può essere risolto esattamente utilizzando l’algoritmo di dijkstra

4) Non può essere risolto esattamente in tempo polinomiale

5) Può essere risolto esattamente usando un albero decisionale binario con n livelli, dove n è il

numero di variabili

Domanda 29:

Dato un problema di minimizzazione PLC, il costo di una variabile non in base xj, in un tableau in forma

base:

1) È strettamente positivo se la soluzione attuale è ottima

2) È la variabile della funzione obiettivo quando la rhs di j-th vincolo aumenta di una unità ( e tutte le