Ricerca Operativa
Ricerca Operativa Quiz
Testa le tue conoscenze sulla Ricerca Operativa con questo quiz completo di 24 domande. Il quiz è progettato per stimolare i tuoi saperi su argomenti come la programmazione lineare, il branch-and-bound e l'analisi di sensitività.
Scopri se hai la preparazione necessaria per affrontare questioni complesse nella ricerca operativa.
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:
D ha 3 variabili e 5 vincoli;
D ha 5 variabili e 3 vincoli;
La prima variabile di D deve essere non negativa;
La terza variabile di D non ha restrizioni di segno;
La seconda variabile di D deve essere non positiva.
Considera I due problemi, P: min {c T x: Ax = b, x ≥ 0}, D: max {u T b: u T A ≤ c T }, allora
Una soluzione ammissibile di P dà un limite inferiore al valore ottimo di D;
Fattibile la soluzione di D dà un limite inferiore al valore ottimo di P;
Una coppia di soluzioni x e u con x ammissibile per P eu ammissibile per D sono ottimali se cT - c T B B−1 A ≥ 0;
Un paio di soluzioni x eu tali che (u T A - c T ) x = 0 sono ottimi se x ≥ 0;
Una coppia di soluzioni x e u sono ottimale se x ≥ 0 eu ≥ 0.
Dato un problema plc primario di minimizzazione e il suo duale:
Se il primale ha una soluzione finita, allora il duale ha una soluzione finita
Se il primale è vuoto, il duale è vuoto
Se il primale è illimitato, allora il duale è illimitato
Una soluzione duale ammissibile può avere un valore inferiore a quello della soluzione primaria ottima
Qualsiasi soluzione ammissibile del primale ha un valore maggiore o uguale a qualsiasi soluzione ammissibile del duale
Dato un problema PLC primale in forma di minimizzazione e il suo duale
Se il primale è vuoto, il duale è vuoto
Se il primale ha soluzione finita, allora il duale ha soluzione finita
Una soluzione duale ammissibile può avere un valore inferiore a quello della soluzione primaria ottimale
Se il primale è illimitato, allora il duale è illimitato
Qualsiasi soluzione ammissibile del primale ha un valore maggiore o uguale a qualsiasi soluzione ammissibile del duale
Nessuna delle precedenti
Considera un problema di minimizzazione e l'algoritmo dual simplex:
Ad ogni passo il valore della soluzione corrente è un limite superiore al valore ottimale
Ad ogni passo il valore della soluzione corrente è un limite inferiore al valore ottimale
L'operazione di pivot viene eseguita sugli elementi aij> 0
L'operazione di pivot viene eseguita sugli elementi aij <0
Costi ridotti eT diventano non negativi nell'ultima iterazione (dando la soluzione ottimale)
Il metodo branch-and-bound
Viene utilizzato per trovare la complessità computazionale di problema
Può essere applicato a problemi di minimizzazione in forma standard
Trova la soluzione ottima di un problema NP-completo
Utilizza sempre come procedura di delimitazione la soluzione di a problema PLC
Nessuna delle precedenti
Il metodo branch-and-bound per problemi di zaino 0-1:
utilizza un albero decisionale con un numero esponenziale di nodi
Utilizza la strategia lowest-first per esplorare l'albero decisionale
calcola un limite superiore in ogni nodo dell'albero decisionale
Utilizza un albero decisionale con un numero polinomiale di livelli
Utilizza un albero decisionale con un numero esponenziale di livelli
Il metodo branch e bound per il problema dello zaino 0-1:
Ha O(2^n) livelli degli alberi
Calcola il limite superiore in tutti I nodi generati da un vincolo del genere xj=1
Usa la prima strategia più alta per esplorare l’albero
Calcola il limite superiore solo nei nodi figlio generati aggiungendo un vincolo del genere xj=0, al nodo padre
Interrompe la ricerca non appena il livello n è raggiunto
Il metodo del piano di taglio:
Viene utilizzato per risolvere problemi di programmazione lineare con variabili continue; termina con un numero polinomiale di iterazioni;
Viene utilizzato per risolvere Problemi NP-completi ("difficili");
Ad ogni iterazione utilizza l'algoritmo del simplesso per risolvere il sottoproblema corrente;
Utilizza la strategia lowest-first strategy primo per esplorare I sottoproblemi.
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 è:
Una disuguaglianza per P che soddisfa il lemma di Farkas;
Una disuguaglianza αT F xF ≥ α0 soddisfatto da qualsiasi x ∈ P;
Una disuguaglianza αT F xF ≥ α0 soddisfatto da qualsiasi x ∈ P ∩ Z n , ma non da x ∗ ;
Una disuguaglianza αT F xF ≥ α0 soddisfatto da qualsiasi x ∈ P ma non da x ∗ ;
Nessuna delle risposte precedenti
Il metodo branch-and-cut:
Utilizza sempre la strategia più bassa prima per esplorare I sottoproblemi
Viene utilizzato per risolvere problemi NP-completi ("difficili")
Ad ogni iterazione utilizza l'algoritmo del simplesso per risolvere il sottoproblema corrente
Termina con un numero polinomiale di iterazioni
Viene utilizzato per risolvere problemi di programmazione lineare con variabili continue
Una soluzione di base di un problema di PLC è chiamata degenere quando:
Ci sono più variabili rispetto ai vincoli;
Il numero di variabili di base con valore zero è uguale al numero di vincoli;
Il numero di variabili di base con valore zero è uguale alla differenza di numero di colonne e righe (n - m);
Il numero di variabili di base con valore diverso da zero è uguale al numero di righe nella matrice dei vincoli
La matrice di base è invertibile.
Nessuna delle precedenti
Dato un problema di PLC, l'analisi di sensibilità di un valore b del lato destro:
Definisce un limite superiore sul valore della soluzione ottimale;
Definisce il valore minimo e massimo di b che non modifica la base ottimale;
Definisce il valore minimo e massimo di b che non cambia il valore della soluzione ottima;
Definisce l'intervallo di valori di b che non modifica I costi ridotti;
definisce l'intervallo di valori di b che non lo fa modificare le doppie variabili;
Dato un problema PLC P in forma standard con n variabili e m vincoli, si consideri il metodo delle due fasi. Il problema artificiale utilizzato per risolvere la prima fase:
ha m variabili e n vincoli;
Ha al massimo n + m variabili e m vincoli;
Ha una funzione oggettiva in forma di massimizzazione;
Fornisce una base ammissibile per il problema P, se la sua soluzione ottima ha valore zero;
fornisce una soluzione ammissibile e ottimale per il problema P se la sua soluzione ottima ha un valore negativo;
Il costo ridotto di una variabile di base x j, in un tableau in forma base
è sempre nullo;
è strettamente positivo se la soluzione attuale è ottimale e il problema è in forma di minimizzazione;
Ha un valore non negativo se la soluzione attuale è ottimale e il problema è in minimizzazione modulo;
Ha un valore non positivo se la soluzione corrente è ottimale e il problema è in modulo di minimizzazione;
Rappresentano la variazione della funzione obiettivo quando la rhs di j-esimo vincolo aumenta di una unità;
Dato un problema plc con n variabili e m vincoli, una matrice di base è:
Nessuna delle risposte precedenti
una matrice quadrata mxn con valore 1 sulla diagonale principale
Una sottomatrice quadrata della matrice dei vincoli, che può essere invertita
Una raccolta di n-m colonne della matrice dei vincoli
una raccolta di m vincoli
Dato un problema di minimizzazione PLC, il costo di una variabile non in base xj, in un tableau in forma base:
È strettamente positivo se la soluzione attuale è ottima
È la variabile della funzione obiettivo quando la rhs di j-th vincolo aumenta di una unità ( e tutte le variabili non di base rimangono uguale a zero)
È la variabile della funzione obiettivo quando variabile xj incrementi di una unità ( e tutte le variabili non di base rimangono uguale a zero)
È sempre nullo
Ha un valore non negativo se la soluzione corrente è ottimale
Dato un problema PLC P in forma standard con n variabili ed m vincoli, una base B e il tableau corrispondente, un’operazione di “pivot” viene utilizzata per:
Trasformare una colonna j che non appartiene a B in una colonna della matrice identità
Aggiungere una disuguaglianza valida al tableau corrente
Trasformare il tableau corrente in un nuovo tableau associato a una base con cui condivide Bn -1 colonne
Trasforma il tableau corrente in un nuovo tableau associato a qualsiasi base
Trasforma il tableau corrente in un nuovo tableau associato a una base con cui condivide Bm -1 colonne
Dato un modello PLI IP in forma di minimizzazione, considerare il suo rilassamento continuo e sia z * il valore ottimale del rilassamento:
Z * è un limite superiore al valore IP ottimale
Z * è un limite inferiore al valore IP ottimale
(estremo superiore) di z * è un limite inferiore al valore IP ottimale se I coefficienti della funzione obiettivo sono interi
(estremo superiore) di z * è un limite superiore al valore IP ottimale
(estremo superiore) di z * è un limite inferiore al valore IP ottimale se I coefficienti della funzione obiettivo sono numeri razionali
Un problema NP-completo:
Può essere risolto esattamente utilizzando algoritmi di tempo polinomiale con un grado elevato
Non può essere risolto esattamente utilizzando computer all'avanguardia
Non può essere risolto esattamente in tempo polinomiale
Ha una complessità computazionale non superiore a O (n ^ 2)
Nessuna delle risposte precedenti
Qualsiasi problema NP-completo:
Può essere risolto esattamente usando l’algoritmo del simplesso con un numero di iterazioni non polinomiale.
Può essere risolto esattamente utilizzando l’algoritmo del simplesso con l’aggiunta di tagli di gomory
Può essere risolto esattamente utilizzando l’algoritmo di dijkstra
Non può essere risolto esattamente in tempo polinomiale
Può essere risolto esattamente usando un albero decisionale binario con n livelli, dove n è il numero di variabili
Un problema NP-completo descritto da un modello di programmazione lineare intera,
Può essere risolto con il metodo del simplesso duale
Può essere risolto con una sequenza di calcoli del percorso più breve
Può essere risolto con un metodo branch-and-bound
Non può essere risolto con un algoritmo esatto
Può essere risolto con il metodo del simplesso rivisto
L’algoritmo di dikstra:
Non può essere applicato a grafi aciclici
Non può essere utilizzato in un grafico con archi di costo negativo
Può essere utilizzato per trovare l'albero di copertura del costo minimo
Può essere utilizzato per trovare il percorso più breve in un grafo diretto, da un nodo sorgente a un nodo sink
Non può essere utilizzato in un grafo con circuiti negativi
Considera un grafo G = (V, E), il problema dell'albero di copertura più breve (Shortest Spanning Tree Problem) e la sua soluzione ottimale T ∗ .
L'arco con costo minimo è sempre in T ∗ ;
Il bordo con costo minimo è in T ∗ solo se non chiude un ciclo con altri bordi
Il bordo con il costo massimo è sempre dentro T ∗
L'arco con il secondo costo minimo è sempre in T ∗
Il bordo con il secondo minimo il costo è in T ∗ solo se l'arco con costo minimo non è in T ∗
Nessuna delle precedenti
{"name":"Ricerca Operativa", "url":"https://www.quiz-maker.com/QPREVIEW","txt":"Testa le tue conoscenze sulla Ricerca Operativa con questo quiz completo di 24 domande. Il quiz è progettato per stimolare i tuoi saperi su argomenti come la programmazione lineare, il branch-and-bound e l'analisi di sensitività.Scopri se hai la preparazione necessaria per affrontare questioni complesse nella ricerca operativa.","img":"https:/images/course1.png"}
More Quizzes
PALESTRA EGI 2
532671
Quiz Time!
1268
Universal Match & Engine Quiz (APAC)
1580
Do you have any recommendations in new papers today?
100
Discover Your Inner Preferences!
15817
ENGLISH FINAL EXAM
20100
QTP Quize
1580
Ice & Rain - week 3
4020223
Quiz
1360
Consumer Studies Part 1
25120
Pop Culture
5245
What Happens in August?
320