Domande.txt

@Programmazione Matematica =============================================================================
Dato un insieme F, un intorno è
A. L'insieme di tutti i sottoinsiemi di F
B. L'insieme dei punti di F a distanza minore di epsilon da un punto x di F
C. Una funzione N: F -> 2^F
D. Una combinazione convessa di due punti x e y di F
E. Nessuna di queste
C

Si consideri un problema di ottimizzazione (F,d) ed un intorno N. La proprietà che se un punto f di F è localmente ottimo rispetto ad N allora f è l'ottimo assoluto implica
A. che N è un intorno esatto
B. che N è un intorno euclideo
C. che N è un intorno non euclideo
D. nessuna di queste caratterizzazioni
E. che N è un intorno convesso
A

Facendo variare lambda fra 0 e 1, la combinazione convessa di due punti x ed y descrive
A. tutti i punti della semiretta che origina in x e passa per y
B. tutti i punti della retta passante per x ed y
C. tutti i punti del segmento [x,y]
D. il punto centrale del segmento [x,y]
E. tutti i punti della semiretta che origina in y e passa per x
C

Data una funzione f convessa su un insieme S convesso, la corda che unisce due punti della funzione:
A. coincide con un flesso della funzione.
B. sta al di sotto della funzione ma non coincide mai con essa.
C. sta al di sopra della funzione ma non coincide mai con essa.
D. sta al di sopra della funzione o è con essa coincidente.
E. sta al di sotto della funzione o è con essa coincidente.
D

Dati una funzione convessa definita su un insieme S convesso ed una soglia t, il sottoinsieme di punti x di S in cui f(x) <= t :
A. È concavo
B. È un intorno euclideo
C. È convesso
D. È un intorno esatto
E. È il complemento di S
C

Sia dato un problema di programmazione convessa. Si ha allora che un ottimo locale rispetto alla distanza euclidea
A. Non gode di particolari proprietà
B. È spesso un ottimo globale
C. Può essere un ottimo globale se soddisfa determinate condizioni
D. È sempre un ottimo globale
E. Coincide con l'origine
D

Si considerino una funzione f convessa definita su un insieme S convesso ed un valore di soglia q. Si ha allora che il sottoinsieme di punti x di S in cui f(x) <= q
A. È un intorno esatto
B. È il complemento di S
C. Coincide con S
D. È convesso
E. È concavo
D

Si consideri una famiglia di insiemi convessi. Vale che
A. La loro unione è sempre un insieme convesso
B. La loro intersezione è un insieme convesso solo se valgono opportune condizioni
C. La loro unione è sempre un insieme concavo
D. La loro intersezione è sempre un insieme concavo
E. La loro intersezione è sempre un insieme convesso
E

@Programmazione Lineare ================================================================================
Un insieme di colonne di una matrice intera A m x n non è linearmente indipendente se:
A. la loro combinazione lineare che produce il vettore nullo ha tutti i coefficienti nulli
B. ogni colonna può essere espressa come combinazione lineare delle altre
C. la sottomatrice corrispondente non è singolare
D. il determinante della matrice corrispondente è diverso da zero
E. nessuna colonna può essere espressa come combinazione lineare delle altre
B

Un insieme di m colonne di una matrice intera A m x n è linearmente indipendente se:
A. la sottomatrice corrispondente è singolare.
B. il determinante della matrice corrispondente è nullo.
C. al massimo una colonna può essere espressa come combinazione lineare delle altre.
D. una loro combinazione lineare con coefficienti non tutti nulli può produrre il vettore nullo.
E. nessuna colonna può essere espressa come combinazione lineare delle altre.
E

Quale di queste non è un'assunzione che l'algoritmo del Simplesso deve verificare prima di poter operare?
A. Si considera sempre la forma standard con m<n.
B. La regione ammissibile F non è vuota.
C. La matrice A contiene m colonne linearmente indipendenti, ha cioè rango m.
D. La SBA iniziale non deve essere degenere.
E. Nessuna di queste.
D

Una variabile libera in segno può essere sostituita equivalentemente da:
A. la differenza fra una variabile non positiva ed una non negativa.
B. la differenza fra due variabili non negative.
C. la somma di due variabili non positive.
D. la somma di due variabili non negative.
E. la differenza fra una variabile non negativa e una non positiva.
B

Un vincolo espresso come Ax = b in forma standard equivale, in forma canonica, a
A. Ax <=b, Ax >=b
B. Ax < b
C. Ax > b
D. Ax >= b, Ax < b
E. Nessuna di queste
A

Dati un vettore di parametri a ed un vettore di incognite x, una disequazione della forma a'x <= b è equivalente a
A. a'x <= b, a'x + s = b, s >= 0.
B. a'x - s = b, s >= 0. 
C. a'x + s = b, s <= 0.
D. a'x + s = b, s >= 0.
E. Nessuna di queste.
D

Si consideri un sistema di equazioni lineari della forma Ax = b, con A matrice m x n di rango m. Il sistema ha
A. infinite soluzioni se m = n
B. infinite soluzioni se m > n
C. una sola soluzione se m = n
D. una sola soluzione se m > n
E. nessuna delle precedenti
C

Cosa è una base di una matrice A?
A. Un sottoinsieme di colonne di A.
B. Un sottoinsieme di colonne di A linearmente indipendenti.
C. Un sottoinsieme di m colonne di A (m rango di A).
D. Un sottoinsieme di m colonne di A linearmente indipendenti (m rango di A).
E. Nessuna di queste.
D

Data una matrice intera A m x n, una sua base è costituita da
A. un insieme di m colonne
B. un insieme di m colonne linearmente indipendenti
C. un insieme di m colonne la cui matrice quadrata corrispondente è singolare
D. un insieme di m colonne linearmente dipendenti
E. nessuna di queste
B

Una soluzione base corrispondente ad una sottomatrice base B di una matrice A m x n si ottiene:
A. azzerando tutte le variabili e risolvendo il sistema risultante
B. azzerando le variabili base e risolvendo il sistema risultante
C. azzerando le variabili fuori base e risolvendo il sistema risultante
D. dando un valore non nullo alle variabili fuori base e risolvendo il sistema risultante
E. nessuna di queste
C

Quale tra le seguenti è la definizione di politopo?
A. Regione in cui la combinazione convessa di ciascun punto appartiene sempre alla regione.
B. Intersezione di un numero finito di semispazi.
C. Combinazione convessa di un numero finito di vertici.
D. Regione ammissibile che ha come punti ottimi i vertici.
E. Nessuna di queste.
B

Sia P un politopo, H un generico iperpiano, HS uno dei due semispazi generati da H. Insieme dei punti f = intersezione tra P e HS è detta:
A. Politopo convesso ammissibile
B. Regione ammissibile
C. Faccia del politopo se f non vuoto e contenuto in H
D. Insieme di punti ottimi contenuti in H
E. Nessuna di queste
C

Relativamente all'affermazione 'ogni punto di un politopo è combinazione convessa dei vertici':
A. Vale solo in caso di vertici ottimi.
B. E' corretta.
C. Vale solo se la combinazione è stretta.
D. E' errata.
E. Nessuna di queste.
B

La combinazione convessa stretta di due punti distinti x ed y di un politopo convesso è:
A. un vertice del politopo.
B. un punto del politopo non coincidente con un vertice.
C. il punto centrale del politopo.
D. un punto esterno al politopo.
E. Nessuna di queste.
B

Dato un politopo P definito dai vincoli di un LP, condizione necessaria e sufficiente perché un punto sia un vertice è che:
A. La sua combinazione convessa con un qualunque altro punto del politopo appartenga ancora al politopo.
B. La relativa soluzione x abbia componenti positivi.
C. Il politopo sia limitato e non vuoto.
D. La corrispondente soluzione x sia una soluzione base ammissibile.
E. Nessuna di queste.
D

Quale tra queste affermazioni è errata?
A. Ogni punto del politopo è combinazione convessa dei vertici.
B. Ogni combinazione convessa dei vertici è un punto del politopo.
C. Un vertice è combinazione convessa stretta di due punti distinti del politopo.
D. Un vertice non è combinazione convessa stretta di due punti distinti del politopo.
E. Nessuna di queste.
C

Quale tra queste affermazioni è errata?
A. L'intersezione di un numero finito di iperpiani è un politopo (convesso).
B. La dimensione di un politopo è la minima dimensione di uno spazio che lo può contenere.
C. Una faccia di dimensione 1 viene detta spigolo.
D. Un vertice non è combinazione convessa stretta di due punti distinti del politopo.
E. Nessuna di queste.
A

Dato il politopo definito dai vincoli di un LP, una combinazione convessa di vertici ottimi è:
A. ottima solo se la combinazione convessa è stretta
B. non ottima
C. ottima sotto particolari condizioni
D. sempre ottima
E. nessuna di queste
D

Una SBA si dice degenere se:
A. Contiene più di m-n variabili con valore zero.
B. Contiene più di n-m variabili con valore zero.
C. Esistono fuori base variabili con valore zero.
D. Non c'è nessuna variabile con valore zero.
E. Nessuna di queste
B

Se due basi producono la stessa soluzione base ammissibile x, allora x contiene:
A. meno di n zeri.
B. n-m zeri.
C. meno di n-m zeri.
D. più di m zeri.
E. più di n-m zeri.
E

Quale di queste affermazioni è errata?
A. Un insieme S si dice convesso se dati due qualunque punti di S, la combinazione convessa di questi appartiene ancora ad S.
B. Una funzione c si dice convessa su un insieme convesso S se il valore della funzione nella combinazione convessa di due qualunque punti di S è maggiore o uguale alla combinazione convessa del valore della funzione nei due punti.
C. Dato un qualunque problema LP, esiste sempre un vertice ottimo.
D. Se due basi distinte producono la stessa SBA x, allora x è degenere.
E. Nessuna di queste.
B

Quale tra queste affermazioni è errata?
A. Ogni combinazione convessa di vertici ottimi è ottima.
B. Dato un LP non è detto che esista un punto ottimo; se esiste allora questo è un vertice.
C. L'insieme dei vincoli di un LP è un politopo.
D. La regione ammissibile di un LP è un politopo.
E. Nessuna di queste.
B

La definizione di politopo (convesso) è:
A. Intersezione di un numero qualunque di semispazi
B. Intersezione di un numero finito di semipiani purchè limitata
C. Intersezione di un numero qualsiasi di semipiani
D. Intersezione di un numero finito di semipiani purchè limitata e non vuota
E. Intersezione di un numero finito si semipiani purchè non vuota
D

Sia B una base di un sistema Ax=b. Qualunque colonna non appartentente a B può essere espressa come:
A. Combinazione lineare delle colonne di B, con coefficienti non negativi
B. Combinazione convessa delle colonne di B, con coefficienti positivi
C. Combinazione convessa delle colonne di B, con coefficienti non negativi
D. Combinazione lineare delle colonne di B, con coefficienti positivi
E. combinazione lineare delle colonne di B, con coefficienti di segno qualunque
E

In un politopo (convesso)  di dimensione d, uno spigolo è
A. Una faccia di dimensione d - 1
B. Una faccia di dimensione 0
C. Una faccia di dimensione 1
D. Una faccia di dimensione d
E. Una faccia di dimensione d + 1
C

@Algoritmo del Simplesso ===============================================================================
Se yij è minore o uguale a 0 per ogni i, in relazione a theta, cosa succede?
A. Viene violata assunzione 0 (forma standard con m<n).
B. Viene violata assunzione 1 (A di rango m).
C. Viene violata assunzione 2 (F non vuota).
D. Viene violata assunzione 3 (F limitata in direzione di decrescenza della funzione obiettivo).
E. Nessuna di queste.
D

Cosa significa se nel calcolo di theta max c'è un caso di parità?
A. La soluzione attuale era degenere.
B. La nuova soluzione è degenere.
C. La nuova soluzione avrà costo maggiore.
D. Niente di particolare, si prosegue scegliendo l'indice minimo.
E. Nessuna di queste.
B

In un tableau del simplesso primale, gli elementi della colonna 0 righe da 1 a m:
A. contengono i valori attuali delle sole variabili base
B. sono tutti nulli
C. contengono i valori attuali di tutte le variabili
D. contengono i costi relativi
E. contengono i valori ottimi delle sole variabili base
A

Cosa contiene il tableau a qualunque iterazione?
A. Rappresentazione compatta dei coefficienti del sistema AX = b.
B. Informazioni sui costi e valori delle soluzioni di base ammissibili.
C. Rappresentazione compatta dei vincoli di un problema di LP.
D. Rappresentazione compatta dei valori delle soluzioni.
E. Nessuna di queste.
A

Quale colonna conviene far entrare in base in un cambiamento di base?
A. Colonna con tutti elementi positivi.
B. Colonna con costo relativo positivo.
C. Colonna con costo relativo negativo.
D. Colonna con tutti elementi negativi.
E. Nessuna di queste.
C

In un tableau del simplesso primale, gli elementi della riga 0 (colonne da 1 a n):
A. sono tutti nulli.
B. possono avere segno qualunque.
C. sono tutti non negativi.
D. sono tutti positivi o nulli.
E. Nessuna di queste.
B

Cosa contiene un tableau nella posizione di riga 0 e colonna 0?
A. Costo relativo della colonna 0.
B. Il valore z0 della soluzione base attuale.
C. Il profitto della colonna 0.
D. L'opposto di z0 della soluzione base attuale.
E. Nessuna di queste.
D

Cosa dice il criterio di ottimalità?
A. Se il costo relativo j-esimo è maggiore o uguale a 0 per ogni j, allora la soluzione attuale è ottima.
B. Se il costo relativo j-esimo è positivo per ogni j, allora la soluzione attuale è ottima.
C. Se i valori delle variabili base sono tutti positivi o nulli, allora la soluzione attuale è ottima.
D. Se il valore z0 è negativo, allora la soluzione attuale è ottima.
E. Nessuna di queste.
A

Cosa afferma la regola di Dantzig?
A. Entra in base la colonna Aj con il costo Cj più negativo.
B. Entra in base la colonna Aj di indice minimo con costo Cj negativo.
C. Entra in base la prima colonna Aj con costo Cj negativo. In caso di parità, esce dalla base la colonna Aj di indice minimo.
D. Esce dalla base la colonna Aj con il costo Cj più negativo.
E. Nessuna di queste
A

Nell'operazione di pivoting del simplesso primale, in caso di parità nella scelta del pivot, la nuova soluzione base:
A. può essere peggiore della soluzione base attuale.
B. coincide sempre con la soluzione base attuale.
C. non è mai degenere.
D. può essere non ammissibile.
E. Nessuna di queste.
E

Nell'algoritmo del simplesso primale, utilizzare ad ogni iterazione la regola di Dantzig:
A. non garantisce nulla
B. garantisce la convergenza dell'algoritmo nel numero minimo di iterazioni
C. garantisce la convergenza dell'algoritmo
D. garantisce il massimo decremento locale del valore della soluzione
E. nessuna di queste
A

Sia v il vertice del politopo corrispondente alla base attuale B. Se B è degenere, un'operazione di pivoting del simplesso primale sposta la soluzione ad un vertice, che è:
A. sempre diverso da v.
B. diverso da v oppure coincidente con v, dipende dal tableau attuale.
C. coincidente con v se il determinante di B è nullo.
D. sempre coincidente con v.
E. diverso da v purché il determinante di B sia positivo.
B

Sia v il vertice del politopo corrispondente alla base attuale B. Se B non è degenere, un'operazione di pivoting del simplesso primale sposta la soluzione ad un vertice che è:
A. diverso da v oppure coincidente da v, non si può dire
B. coincidente con v se il determinante di B è nullo
C. sempre diverso da v
D. diverso da v purchè il determinante di B sia positivo
E. coincidente con v se il determinante di B è non negativo
C

In cosa consiste la Fase 1 dell'algoritmo del Simplesso?
A. Eliminare le variabili artificiali.
B. Minimizzare la funzione obiettivo originale.
C. Determinare una SBA iniziale.
D. Azzerare i costi relativi originali.
E. Nessuna di queste.
C

Nel metodo delle due fasi, se al termine della fase 1 la soluzione ha valore negativo:
A. si è ottenuta una soluzione base ammissibile per il problema originale.
B. significa che la soluzione ottima è illimitata.
C. significa che il problema originale è impossibile.
D. si è trovata la soluzione ottima del problema originale.
E. Nessuna di queste.
E

Se la soluzione del problema artificiale della fase 1 del simplesso ha valore nullo:
A. E' sempre possibile proseguire con la fase 2, a patto di eliminare le variabili artificiali, sostituire la funzione obiettivo con quella del costo originale e azzerare i costi relativi in corrispondenza delle basi o ridurre la dimensione della base.
B. Non è detto che sia sempre possibile proseguire con la fase 2.
C. Si prosegue con la fase 2 senza nessun tipo di operazione preliminare.
D. Il problema originale non ha soluzione ammissibile.
E. Nessuna di queste.
A

Cosa significa se la soluzione del problema artificiale ha valore positivo?
A. Violata assunzione 0 (forma standard con m<n).
B. Violata assunzione 1 (A di rango m).
C. Violata assunzione 2 (F non vuota).
D. Violata assunzione 3 (F limitata in direzione di decrescenza della funzione obiettivo).
E. Nessuna di queste.
C

Nel metodo delle due fasi, se al termine della fase 1 la soluzione ha valore positivo
A. significa che la soluzione ottima è illimitata
B. sotto determinate condizioni si è ottenuta una soluzione base ammissibile per il problema originale
C. si è trovata la soluzione ottima del problema originale
D. si è ottenuta una soluzione base ammissibile per il problema originale
E. significa che il problema è impossibile
E

Se un tableau del simplesso primale corrisponde alla soluzione ottima:
A. gli elementi della riga 0 sono tutti non negativi.
B. gli elementi della colonna 0 sono tutti non negativi.
C. gli elementi della riga 0, colonne da 1 a n, sono tutti positivi.
D. gli elementi della riga 0, colonne da 1 a n, sono tutti non negativi.
E. Nessuna di queste.
D

Si consideri un tableau dell'algoritmo del simplesso primale. I costi relativi si trovano:
A. In nessuna di queste posizioni
B. Nella riga 0, nelle colonne corrispondenti alla base
C. Nella riga 0, nelle colonne non corrispondenti alla base
D. Nella colonna 0, nelle righe corrispondenti alla base
E. Nella colonna 0, nelle righe non corrispondenti alla base
C

Si consideri una sottomatrice B di ordine m di una matrice A m x n. La soluzione base corrispondente a B:
A. è ammissibile per il corrispondente problema in forma standard solo se x = 0 per ogni variabile non base
B. è sempre ammissibile per il corrispondene problema in forma standard
C. Non è mai ammissibile per il corrispondente problema in forma standard
D. è ammissibile per il corrispondente problema in forma standard solo se x >= 0
E. Nessuna di queste
D

Si consideri un tableau dell'algoritmo del simplesso primale. Gli elementi della riga 0 corrispondenti alle colonne della base
A. Nessuna di queste
B. Possono avere segno qualunque
C. Sono tutti nulli
D. Contengono i costi relativi
E. Valgono tutti 1
C

Sia A_j una colonna corrispondente ad un costo relativo negativo nell'algoritmo del simplesso primale. Se tutti i coefficienti della colonna sono negativi o nulli, ciò implica che:
A. Il problema ha soluzione illimitata
B. Il sistema Ax = b è ridondante
C. Nessuna di queste
D. La soluzione attuale è ottima
E. La regione ammissibile è vuota
A

Si consideri un tableau dell'algoritmo del simplesso primale. Il costo relativo di una variabile fuori base fornisce:
A. La diminuzione unitaria del valore della soluzione se tale variabile entra in base
B. La variazione unitaria del valore della soluzione se tale variabile esce dalla base
C. La diminuzione unitaria del valore della soluzione se tale variabile esce dalla base
D. La variazione unitaria del valore della soluzione se tale variabile entra in base
E. Nessuna di queste
D

Se al termine della Fase 1 dell'algoritmo del simplesso la soluzione vale 0 ma ci sono variabili artificiali in base
A. Si è trovata la soluzione ottima del problema originale
B. Significa che il problema originale è impossibile
C. Significa che la soluzione ottima è illimitata
D. Significa che il sistema dei vincoli del problema originale è ridondante
E. Non di può dire, occorrono ulteriori iterazioni
E

Siano dati un problema di programmazione lineare ed il corrispondente tableau ottimo. L'analisi di sensistivita' dimostra che, se si cambia il coefficiente di costo di una variabile, la base attuale resta ottima se
A. i nuovi valori dei costi relativi sono non negativi
B. i nuovi valori delle variabili base soddisfano le equazioni dei vincoli
C. i nuovi valori delle variabili base sono negativi o nulli
D. i nuovi valori delle variabili base sono non negativi
E. risposta vuota
A

@Dualità ===============================================================================================
Ad una variabile primale non negativa corrisponde
A. nessuna di queste
B. un vincolo duale della forma pi'a^ <= c
C. un vincolo duale nella forma pi'a^ = c
D. una variabile duale non negativa
E. una variabile duale libera (non ristretta in segno)
B

Quale tra queste affermazioni è falsa rispetto ad una corrispondenza primale-duale?
A. Ai costi corrispondono condizioni su variabili e viceversa.
B. I vincoli sono dati dalle righe di A per il primale, dalle colonne di A per il duale.
C. Ai costi corrispondono i termini noti e viceversa.
D. Ad un vincolo corrisponde una condizione su una variabile e viceversa.
E. Nessuna di queste.
A

Se un problema di programmazione lineare (primale) ha soluzione ottima finita, allora:
A. Il suo duale non è detto che abbia soluzione ottima finita.
B. Anche il suo duale ha soluzione ottima finita e i valori delle soluzioni coincidono.
C. Anche il duale ha soluzione ottima finita, ma non è detto che i valori delle soluzioni coincidano.
D. Anche il duale ha soluzione ottima finita, ma i valori delle due soluzioni non coincidono.
E. Nessuna di queste
B

Quale può essere una possibile coppia di problemi primale-duale?
A. Primale ottimo finito / Duale illimitato.
B. Primale Illimitato / Duale Illimitato.
C. Primale impossibile / Duale impossibile.
D. Primale ottimo finito / Duale impossibile.
E. Nessuna di queste.
C

La situazione "primale illimitato" e corrispondente "duale illimitato":
A. dipende dal gradiente della funzione obiettivo del primale.
B. non può mai verificarsi.
C. può verificarsi sotto determinate condizioni.
D. dipende dai gradienti delle due funzioni obiettivo.
E. si verifica sempre.
B

Quando un primale è illimitato, la situazione "corrispondente duale impossibile":
A. dipende dai gradienti delle due funzioni obiettivo
B. non può mai verificarsi
C. può verificarsi sotto determinate condizioni
D. dipende dal gradiente della funzione obiettivo
E. si verifica sempre
E

Il lemma di Farkas:
A. Ha colto con grande anticipo l'essenza della dualità.
B. Ha colto con grande anticipo l'essenza della programmazione intera.
C. Offre una solida dimostrazione sull'efficienza dell'algoritmo del simplesso.
D. Identifica la relazione tra l'ammissibilità del primale e l'impossibilità del duale.
E. Nessuna di queste
A

Il teorema degli scarti complementari afferma:
A. Per ogni i ad 1 a m, l'i-esima variabile duale è nulla o l'i-esimo vincolo primale è soddisfatto con uguaglianza.
B. Per ogni j da 1 a n, il j-esimo vincolo primale deve essere soddisfatto con uguaglianza o la j-esima variabile duale deve essere nulla.
C. per ogni i da 1 a m, l'i-esima variabile primale è nulla o l'i-esimo vincolo duale è soddisfatto con uguaglianza.
D. Per ogni j da 1 a n, i j-esimi vincoli primali e duali devono essere soddisfatti con uguaglianza.
E. Nessuna di queste.
A

In un problema di programmazione lineare con m vincoli ed n variabili, le condizioni di ortogonalità (complementary slackness)
A. sono m-n.
B. sono m+n.
C. sono m.
D. sono m*n.
E. sono n.
B

Le condizioni di ortogonalità (complementary slackness) di una coppia primale-duale garantiscono:
A. l'ammissibilità di due soluzioni, una primale e una duale
B. l'ottimalità di due soluzioni ammissibili, una primale e una duale
C. l'ottimalità di due soluzioni, una primale e una duale, anche se non ammissibili
D. l'ottimalità di una soluzione primale e del suo complemento
E. nessuna di queste
B

In un tableau del simplesso duale, gli elementi della riga 0 (colonna da 1 a n):
A. sono tutti positivi o nulli.
B. sono tutti positivi.
C. sono tutti negativi.
D. sono tutti nulli.
E. Nessuna di queste.
A

In un tableau del simplesso duale, i costi relativi si trovano:
A. nella riga 0, colonne corrispondenti alla base
B. nella riga 0, colonne non corrispondenti alla base
C. nella colonna 0, righe non corrispondenti alla base
D. in nessuna di queste posizioni
E. nella colonna 0, nelle righe corrispondenti alla base
B

Nell'algoritmo del simplesso duale:
A. Scegliamo una riga i >= 1, corrispondente ad un yi0 frazionario
B. Il pivoting deve annullare la yi0 scelta
C. Si inizia con una base ammissibile per il primale ma non per il duale
D. La scelta del pivot garantisce il minimo aumento del valore della soluzione
E. Nessuna di queste
D

La scelta del pivot del simplesso duale viene determinata da:
A. un minimo tra rapporti di valore positivo
B. un minimo tra rapporti di valore negativo
C. un massimo tra rapporti di valore negativo
D. un massimo tra rapporti di valore positivo
E. nessuna di queste
C

Cosa succede se, dopo aver individuato la riga con elemento in colonna 0 negativo, nell'algoritmo del simplesso duale ogni elemento di quella riga è positivo o nullo?
A. Duale impossibile, Primale illimitato.
B. Duale illimitato, Primale impossibile.
C. Duale impossibile, Primale impossibile.
D. Duale illimitato, Primale illimitato.
E. Nessuna di queste.
B

Nell'algoritmo del simplesso duale, sia a'i (i>0) una riga corrispondente ad un valore negativo in colonna 0. Se tutti i coefficienti di tale riga sono positivi o nulli, ciò implica che:
A. Il sistema Ax = b è ridondante.
B. il problema è impossibile.
C. la soluzione attuale è ottima.
D. il problema ha soluzione illimitata.
E. Nessuna di queste.
B

Relativamente al prezzo ombra:
A. Il valore ottimo della variabile xi fornisce il prezzo ombra della risorsa associata al vincolo i.
B. Il prezzo ombra della risorsa i identifica il valore della soluzione ottima duale.
C. Il valore ottimo della variabile duale pi-i identifica il prezzo ombra della risorsa associata al vincolo i.
D. Il prezzo ombra della variabile duale pi-i indica il modo per capire se una base con coefficienti diversi è ancora ottima.
E. Nessuna di queste.
C

Relativamente al simplesso duale, quale tra le seguenti affermazioni è errata?
A. Vogliamo che il pivoting renda positiva yi0 .
B. Si inizia con una base ammissibile per il primale e vogliamo trovare la soluzione ottima duale.
C. Vogliamo eliminare le inammissibilità contenute nel tableau.
D. Il pivoting deve portare il valore 0 in y0s .
E. Nessuna di queste.
B

Nell'operazione di pivoting dell'algoritmo del simplesso duale:
A. Nessuna di queste.
B. La colonna del pivot viene moltiplicata per il pivot
C. La riga del pivot viene moltiplicata per il pivot
D. La colonna del pivot viene divisa per il pivot
E. La riga del pivot viene divisa per il pivot
E

Nel duale di un problema di minimizzazione in forma standard
A. Le variabili possono assumere solo valori non positivi
B. Le variabili possono assumere solo valori non negativi
C. Le variabili possono assumere solo valori positivi
D. Le variabili possono assumere qualunque valore
E. Nessuna di queste
D

La situazione in cui il primale è impossibile e il corrispondente duale è impossibile
A. Si verifica sempre
B. Può verificarsi
C. Non può mai verificarsi
D. Dipende dal gradiente della funzione obiettivo del duale
E. Dipende dai gradienti delle due funzioni obiettivo
B

Si considerino un sistema (I), definito da {Ax = b, x >= 0}, ed un sistema (II), definito da {y′A <= 0, b′y > 0}. Si ha allora che
A. il sistema (I) è impossible se e solo se il sistema (II) è possibile
B. Nessuna di queste
C. il sistema (I) è impossible se e solo se il sistema (II) è impossibile
D. il sistema (I) è possible se e solo se il sistema (II) è possibile
E. risposta vuota
A

@Programmazione Lineare Intera =========================================================================
Relativamente ad un problema ILP e il suo rilassamento continuo LP
A. z(ILP) >= z(LP)
B. z(ILP) <= z(LP)
C. z(ILP) < z(LP)
D. z(ILP) > z(LP)
E. z(ILP) = z(LP)
A

Relativamente ad un problema ILP e il suo rilassamento continuo LP
A. z(LP) >= z(ILP)
B. z(LP) <= z(ILP)
C. z(LP) > z(ILP)
D. z(LP) < z(ILP)
E. z(LP) = z(ILP)
B

Una matrice m x n è totalmente unimodulare se:
A. ogni sottomatrice quadrata ha determinante di valore +1 o -1.
B. ogni sottomatrice quadrata ha determinante di valore unitario.
C. il suo determinante ha valore unitario.
D. il suo determinante vale 0, +1 o -1.
E. Ogni sottomatrice quadrata ha determinante di valore 0, +1 o -1.
E

Se A è totalmente unimodulare, relativamente a problemi ILP:
A. Il simplesso risolve problemi in tutte le forme.
B. Il simplesso risolve solo problemi in forma standard.
C. Il simplesso risolve problemi in forma standard e canonica, ma non in forma generale.
D. Il simplesso risolve i problemi in forma standard e generale, ma non in forma canonica.
E. Nessuna di queste.
A

Scelta una riga generatrice, un taglio di Gomory impone che
A. la somma delle parti frazionarie delle variabili fuori base sia non maggiore della parte frazionaria del termine noto
B. la somma delle parti frazionarie delle variabili base sia non maggiore della parte frazionaria del termine noto
C. la somma delle parti frazionarie delle variabili base sia non minore della parte frazionaria del termine noto
D. la somma delle parti frazionarie delle variabili fuori base sia non minore della parte frazionaria del termine noto
E. nessuna delle precedenti
D

Aggiungendo un taglio di Gomory al tableau finale di un LP con yi0 non intero
A. Si elimina al più un punto intero ammissibile non ottimo
B. Il nuovo tableau contiene una base ammissibile ma non ottima per il primale
C. Il nuovo tableau contiene una base non ammissibile per il primale ma ammissibile per il duale
D. Si elimina almeno una soluzione ammissibile intera
E. Nessuna di queste
C

L'aggiunta al tableau del taglio di Gomory relativo ad una riga generatrice frazionaria produce una soluzione (un tableau) che:
A. soddisfa il vincolo di interezza ma non è ottima.
B. soddisfa il criterio di ottimalità ma non è ammissibile.
C. è ammissibile ma non è intera.
D. è ammissibile ma non soddisfa il criterio di ottimalità.
E. Nessuna di queste.
B

Sia P il problema ILP e L(P) il suo rilassamento continuo. Se L(P) è illimitato, allora:
A. P è sempre impossibile
B. non si può dire nulla su P
C. P è sempre illimitato
D. P è illimitato salvo casi molto particolari
E. nessuna di queste
D

Sia P un problema di programmazione lineare intera e L(P) il suo rilassamento continuo. Se L(P) è impossibile, allora
A. P è impossibile salvo casi molto particolari
B. non si può dire nulla su P
C. P è sempre impossibile
D. P è illimitato
E. nessuna di queste
C

In un algoritmo branch-and-bound per un problema di massimizzazione, sia U l'upper-bound del nodo corrente. Il nodo viene ucciso se:
A. U è minore o uguale al valore della soluzione ottima corrente
B. U è minore o uguale al valore della soluzione ottima finale
C. U è maggiore o uguale al valore della soluzione ottima corrente
D. U è maggiore o uguale al valore della soluzione ottima finale
E. nessuna di queste
A

Dopo aver inserito i vincoli del procedimento Branch-and-Bound nel tableau:
A. Si prosegue sempre con il simplesso primale.
B. Si prosegue sempre con il simplesso duale.
C. Si può proseguire sia con il simplesso primale che con il simplesso duale.
D. Si prosegue con la Fase 1 del simplesso primale.
E. Nessuna di queste.
B

Nel Forward Step della strategia di esplorazione Depth-First rivisitata:
A. Si generano tutti i figli di P0 e si prosegue.
B. Si calcola L0,si rimuove dai nodi attivi il nodo con più basso lower bound, si generano i suoi figli e ne si calcolano i lower bound, aggiornando quello migliore.
C. Si genera un figlio dell'ultimo nodo Pk generato finchè si ottiene una soluzione immediatamente risolubile e si aggiorna eventualmente z.
D. Si generano tutti i figli del nodo attuale, si calcolano i loro lower bound, si prosegue l'esplorazione dal figlio con minimo lower bound.
E. Nessuna di queste
D

Sia L il lower bound del nodo corrente in un algoritmo branch-and-bound per un problema di minimizzazione, il nodo viene ucciso se:
A. L è minore o uguale al valore della soluzione ottima corrente
B. L è minore o uguale al valore della soluzione ottima finale
C. L è maggiore o uguale al valore della soluzione ottima corrente
D. L è maggiore o uguale al valore della soluzione ottima finale
E. Nessuna di queste.
C

Sia x la soluzione del rilassamento continuo di un problema di programmazione lineare intera di massimizzazione. Se si arrotonda ogni x_j frazionario all'intero più prossimo,
A. Si ottiene una soluzione ammissibile ma non ottima per il problema ILP
B. Si ottiene una soluzione ottima del problema ILP
C. Si ottiene un upper bound per il problema ILP
D. Si ottiene una soluzione intera priva di particolari proprietà
E. Nessuna di queste
D

Sia P un problema di programmazione lineare intera e L(P) il suo rilassamento continuo. Allora:
A. La regione ammissibile di L(P) è contenuta nella regione ammissibile di P
B. La regione ammissibile di P e quella di L(P) non hanno nessuna relazione
C. La regione ammissibile di P è contenuta nella regione ammissibile di L(P)
D. L'intersezione fra la regione ammissibile di P e quella di L(P) è vuota
E. Nessuna di queste
C

Si consideri un problema ILP di massimizzazione. Sia z(P) il valore della sua soluzione ottima e z(L(P)) quello del suo rilassamento continuo. Si ha allora che
A. z(P) > z(L(P))
B. z(P) <= z(L(P))
C. z(P) < z(L(P))
D. z(P) = z(L(P))
E. z(P) >= z(L(P))
B

@Complessità ===========================================================================================
Cosa è un'istanza di un problema?
A. Un possibile algoritmo per risolverlo.
B. Un algoritmo attualmente in esecuzione per risolverlo.
C. L'insieme di tutti gli algoritmi che lo possono risolvere.
D. Un particolare caso numerico.
E. Nessuna di queste.
D

Cosa è la dimensione di un problema?
A. Minimo tempo di esecuzione di un algoritmo per risolverlo.
B. Lunghezza minima di un output di una sua istanza.
C. Numero di bit necessari per codificare l'input.
D. Numero di risorse utilizzate per risolverlo.
E. Nessuna di queste.
C

Se un problema appartiene alla classe NP
A. È risolubile solo mediante un albero decisionale di altezza esponenziale
B. È sempre risolubile mediante un algoritmo di programmazione dinamica
C. È sempre risolubile in tempo polinomiale
D. È sempre risolubile mediante un albero decisionale di altezza polinomiale
E. È sempre risolubile in tempo pseudo-polinomiale
B

Un algoritmo polinomiale per un problema NP-completo:
A. risolverebbe in tempo polinomiale i problemi della classe NP, ma non quelli fortemente NP-completi
B. non può esistere
C. risolverebbe in tempo polinomiale i problemi della classe NP, ma non quelli della classe P
D. risolverebbe ogni problema della classe NP in tempo polinomiale
E. nessuna di queste
D

Si dice che S' domina S'' se:
A. La somma dei pesi di S' è maggiore o uguale a quella dei pesi di S'' e la somma dei profitti di S' è minore o uguale a quella dei profitti di S''.
B. La somma dei pesi di S' e di S'' è uguale e la somma dei profitti di S'' è maggiore di quella dei profitti di S'.
C. La somma dei pesi di S' è minore o uguale alla somma dei pesi di S'' e la somma dei profitti di S' è maggiore o uguale a quella dei profitti di S''.
D. La somma dei pesi di S' è minore a quella dei pesi di S'' e la somma dei profitti di S' e di S'' coincidono.
E. Nessuna di queste.
C

L'algoritmo Knapsack DP è:
A. Polinomiale
B. Esponenziale
C. Pseudo-Esponenziale
D. Pseudo-Polinomiale
E. Nessuna di queste
D

Relativamente ad un problema fortemente NP-Completo:
A. Non può esistere nessun algoritmo pseudo-polinomiale, a meno che P=NP.
B. Non può esistere nessun algoritmo pseudo-polinomiale.
C. Può esistere un algoritmo pseudo-polinomiale, a meno che P=NP.
D. Può esistere un algoritmo pseudo-polinomiale.
E. Nessuna di queste.
A

Quale tra queste affermazioni è errata?
A. Per tutti i problemi fortemente NP-Completi esiste un algoritmo pseudo-polinomiale.
B. La versione riconoscimento e ottimizzazione hanno stessa difficoltà in relazione alla possibilità o meno di trovare la soluzione in tempo polinomiale.
C. Se A è trasformabile polinomialmente in B e si conosce un algoritmo polinomiale per B, allora si ha un algoritmo polinomiale anche per A.
D. Un problema che soddisfa la definizione di Np-Completo senza stabilire la sua appartenenza a NP viene detto NP-Difficile.
E. Nessuna di queste.
A

Relativamente alla classe di problemi NP, quale di queste affermazioni è errata?
A. Contiene i problemi risolubili con un tempo polinomiale da una Macchina di Turing Non Deterministica.
B. Se un problema non appartiene a NP, allora è possibile trovare un algoritmo polinomiale che lo risolva.
C. Identifica i problemi RV tali che, se l'istanza della risposta è "sì", ciò può essere certificato in tempo polinomiale.
D. Un problema A di NP è NP-Completo se per ogni problema B di NP, B può essere trasformato polinomialmente in A.
E. Nessuna di queste
B

La programmazione lineare:
A. È risolubile in tempo polinomiale, ma non dall'algoritmo del simplesso.
B. non è risolubile in tempo polinomiale.
C. È risolubile in tempo polinomiale dall'algoritmo del simplesso.
D. È risolubile in tempo pseudo-polinomiale dall'algoritmo del simplesso.
E. Nessuna di queste.
A

Relativamente ad un problema KP-01:
A. È risolvibile solo mediante un albero decisionale.
B. È risolvibile in tempo polinomiale.
C. È risolvibile mediante la programmazione dinamica.
D. non esiste algoritmo pseudo-polinomiale.
E. Nessuna di queste.
C

Un problema P è NP-completo se:
A. Qualunque problema della classe NP si può trasformare in P in tempo polinomiale
B. Si può trasformare in tempo polinomiale in qualunque problema della classe NP
C. è risolubile mediante un albero decisionale di altezza polinomiale
D. è risolubile mediante un algoritmo di programmazione dinamica
E. Nessuna di queste
A

Un problema Knapsack 0-1:
A. Non può essere risolto in tempo pseudo-polinomiale
B. È risolubile solo mediante un albero decisionale di altezza esponenziale
C. È risolubile in tempo polinomiale
D. È sempre risolubile mediante un albero decisionale di altezza polinomiale
E. Nessuna di queste
D