Quali tra i seguenti è un passo previsto dall'approccio modellistico ai problemi decisionali Confronto del modello matematico con altre tipologie di modelli Sintesi del modello Soluzione numerica o matematica Soluzione grafica o visiva.
Un modello matematico è Dipendente dalla soluzione specifica del problema Dipendente dai dati specifici del problema Indipendente dalle relazioni specifiche del problema Indipendente dai dati specifici del problema.
Quale tra le seguenti non è una proprietà del modello valutata in fase di analisi del modello secondo l'approccio modellistico Condizioni di ottimalità Esistenza e unicità della soluzione ottima Stabilità delle soluzioni Determinazione della soluzione ottima.
Quale tra le seguenti non è una fase prevista dall'approccio modellistico Soluzione qualitativa del problema Soluzione numerica del problema Analisi del problema Analisi del modello.
Nei modelli matematici previsti dall'approccio modellistico la regione ammissibile è L'insieme dei valori delle variabili che massimizzazione la funzione obiettivo Nessuna delle opzioni L'insieme dei valori delle variabili che minimizzano la funzione obiettivo L'insieme dei valori delle variabili che soddisfano tutti i vincoli.
Nei modelli matematici previsti dall'approccio modellistico la funzione obiettivo È una funzione delle variabili decisionali del problema Non può essere vuota Non può essere una costante È una funzione dei vincoli logici del problema.
L'identificazione di un modello di Programmazione Matematica non prevede La definizione delle variabili di decisione del problema La definizione dei vincoli del problema La definizione della soluzione del problema La definizione della funzione obiettivo del problema.
Un modello matematico può essere O statico o dinamico, ma non entrambi O stocastico o dinamico, ma non entrambi O statico o deterministico ma non entrambi Nessuna delle opzioni.
Un modello matematico può essere Nessuna delle opzioni O stocastico o deterministico, ma non entrambi Sia stocastico che deterministico O stocastico o statico, ma non entrambi.
La definizione di modelli matematici previsti dall'approccio modellistico Non prevede la definizione di grandezze bensì di relazioni funzionali Nessuna delle opzioni Prevede la definizione di variabili matematiche e di opportune grandezze per rendere esplicite le principali relazioni funzionali che legano le variabili del problema tra loro Prevede la definizione di opportune grandezze per rendere esplicite le principali relazioni funzionali che legano le variabili del problema tra loro.
Nei modelli matematici previsti dall'approccio modellistico la funzione obiettivo È sempre una funzione lineare delle variabili del problema È sempre una funzione da massimizzare o da minimizzare È sempre una funzione da massimizzare È sempre una funzione da minimizzare.
L'approccio modellistico ai problemi decisionali Prevede una serie aciclica di passi Prevede una serie di passi che vanno dall'analisi del problema alla validazione del modello adottato Prevede una serie di passi che vanno dall'analisi del problema alla sua soluzione numerica Nessuna delle opzioni.
Quali tra i seguenti è un passo previsto dall'approccio modellistico ai problemi decisionali Soluzione per ispezione Confronto interno ed esterno del modello canonico Traduzione del modello Identificazione del modello.
Il problema min{e^-x: x ≥ 0} è Ammette soluzione ottima Illimitato superiormente Vuoto Nessuna delle opzioni.
Massimizzare una funzione f a valori reali su un insieme C è equivalente a Minimizzare la funzione -f sull'insieme C Massimizzare la funzione f sull'insieme Minimizzare la funzione f su un insieme D con intersezione nulla con C Minimizzare la funzione f sull'insieme complemento di C.
Un problema di ottimizzazione di minimizzazione è inferiormente illimitato se Preso un valore M esiste sempre una soluzione ammissibile di valore maggiore o uguale di M Preso un valore M esiste sempre una soluzione ammissibile di valore minore o uguale di M Preso un valore M esiste sempre una soluzione ammissibile di valore minore di M Preso un valore M esiste sempre una soluzione ammissibile di valore maggiore di M.
Un problema di ottimizzazione è illimitato Se lo è sia inferiormente che superiormente Se è vuoto e non ammette soluzione ottima Se è non vuoto e ammette soluzione ottima O superiormente o inferiormente.
Il problema min{e^-x: x ≥ 0} è Nessuna delle opzioni Illimitato inferiormente Ammette soluzione ottima Vuoto.
Un problema di ottimizzazione di massimizzazione è superiormente illimitato se Preso un valore M esiste sempre una soluzione ammissibile di valore minore di M Preso un valore M esiste sempre una soluzione ammissibile di valore maggiore o uguale di M Preso un valore M esiste sempre una soluzione ammissibile di valore maggiore di M Preso un valore M esiste sempre una soluzione ammissibile di valore minore o uguale di M.
Un problema di ottimizzazione può O ammettere soluzione ottima o essere inammissibile O ammettere soluzione ottima o essere illimitato (inferiormente o superiormente) O ammettere soluzione ottima o essere inammissibile e
essere illimitato (inferiormente o superiormente) O ammettere soluzione ottima o essere inammissibile o
essere illimitato (inferiormente o superiormente).
Il valore che la funzione obiettivo assume in una soluzione ottima è detto Valore ottimo Nessuna delle opzioni Valore ammissibile Valore di decisione.
Minimizzare una funzione f a valori reali su un insieme C è equivalente a Massimizzare la funzione -f sull'insieme C Massimizzare la funzione f su un insieme D con intersezione nulla con C Massimizzare la funzione f sull'insieme vuoto Nessuna delle opzioni.
Un problema di ottimizzazione è inammissibile se L'insieme delle soluzioni ottime è vuoto L'insieme delle variabili è vuoto L'insieme delle soluzioni ammissibili è vuoto Nessuna delle opzioni.
Dato un insieme non vuoto C e una funzione f definita in C a valori reali (f:C->R), il problema di massimizzazione associato alla coppia (C,f) consiste in Determinare, se esiste, un elemento x* in C tale che f(x*) <= f(x) per ogni x in C Determinare, se esiste, un elemento x* in C tale che f(x*) >= f(x) per ogni x in C Determinare, se esiste, un elemento x* in C tale che f(x*) <f(x) per ogni x in C Determinare, se esiste, un elemento x* in C tale che f(x*) > f(x) per ogni x in C.
Il problema min{5: x =1, x ≥ 0} Risulta vuoto Risulta illimitato inferiormente Ammette soluzione ottima Nessuna delle opzioni.
Dato un insieme non vuoto C e una funzione f definita in C a valori reali (f:C->R), il problema di minimizzazione associato alla coppia (C,f) consiste in Determinare, se esiste, un elemento x* in C tale che f(x*) <f(x) per ogni x in C Determinare, se esiste, un elemento x* in C tale che f(x*) > f(x) per ogni x in C Determinare, se esiste, un elemento x* in C tale che f(x*) <= f(x) per ogni x in C Determinare, se esiste, un elemento x* in C tale che f(x*) >= f(x) per ogni x in .
Il problema max{3: x =2, x ≤ 0} Ammette soluzione ottima pari a 3 Nessuna delle opzioni Ammette soluzione ottima pari a 2 Non ammette soluzione.
Il problema max{x: x ≥ 0} è Illimitato inferiormente Nessuna delle opzioni Ammette soluzione ottima Vuoto.
Il problema max{x: x ≥ 0} è Ammette soluzione ottima Nessuna delle opzioni Vuoto Illimitato superiormente.
Il problema min{2x: x + y =1, x + y ≤ 0} è Ammette soluzione ottima Illimitato superiormente Nessuna delle opzioni Vuoto.
Il problema di massimizzazione MAX(X,f) associato alla coppia (X,f) È equivalente al problema di minimizzazione associato alla coppia (X,f) È equivalente al problema di massimizzazione associato alla coppia (X,-f) È equivalente al problema di minimizzazione associato alla coppia (X,-f) È equivalente al problema di massimizzazione associato alla coppia (-X,-f).
13. Il problema max{7: x =0, y=1} Ammette soluzione ottima di valore 0 Ammette soluzione ottima di valore 1 Ammette soluzione ottima di valore 7 Non ammette soluzione.
Dati i vettori x=( 1 2 )^T e y=( 15 30 )^T x e y sono illimitati Non si può dire nulla sull'indipendenza/dipendenza lineare x e y sono linearmente indipendenti x e y sono linearmente dipendenti.
L'insieme A={1,a,5,bn} è Rappresentato in forma estensiva Inammissibile Nessuna delle opzioni Vuoto.
Dati due insiemi, A e B, l'espressione A \subseteq B indica che Se A è vuoto, allora anche B è vuoto Se un elemento appartiene a B, allora appartiene anche ad A Se un elemento appartiene a A \cup B, allora appartiene anche ad A \cap B Se un elemento appartiene ad A, allora appartiene anche a B.
Un insieme può essere rappresentato Solo se ha almeno due elementi In forma implicita o in forma estensiva Solo se non è vuoto Sempre in forma implicita.
L'insieme dei numeri naturali è Rappresentato in forma implicita Vuoto Finito Nessuna delle opzioni.
L'insieme A={x ∈ Rn: x ≥ 0} è Nessuna delle opzioni Finito Vuoto Rappresentato in forma implicita.
L'insieme A = {3} è Linearmente dipendente Linearmente indipendente Nessuna delle opzioni Inammissibile.
02. L'insieme A = {0n} è Linearmente dipendente Vuoto Nessuna delle opzioni Linearmente indipendente.
02. Dati i vettori x=(2 0 3)^T, y=(0 1 2)^T e z=(0 2 1)^T x, y e z sono linearmente dipendente Non si può dire nulla sull'indipendenza/dipendenza lineare x, y e z sono linearmente indipendente Nessuna delle opzioni.
Dati i vettori x=(2 1 3)T, y=(1 2 0)T e z=(3 3 3)T Nessuna delle opzioni x, y e z sono linearmente dipendente x, y e z sono linearmente indipendente Non si può dire nulla sull'indipendenza/dipendenza lineare.
Dati i vettori x=(2 1)T e y=(0 4)T x e y sono linearmente indipendente Nessuna delle opzioni x e y sono linearmente dipendente Non si può dire nulla sull'indipendenza/dipendenza lineare.
Dati i vettori x=(1 2)^T, y=(0 2)^T e z=(1 1)^T Nessuna delle opzioni z è la somma dei vettori x e y z è il prodotto dei vettori x e y z è combinazione lineare di x e y.
L'insieme {0,1}^n indica L'insieme dei vettori di n componenti comprese tra 0 e 1, estremi esclusi L'insieme dei vettori di n componenti appartenenti all'insieme finito composto dai valori reali 0 e 1 L'insieme dei vettori di n componenti comprese tra 0 e 1 L'insieme dei vettori di n componenti appartenenti al primo ortante.
L'insieme dei vettori di 3 componenti a valori reali maggiori o uguali a 0 e strettamente minori di 1 può essere indicato come (0,1] [0,1]^3 [0,1)^3 (0,1).
Si consideri la matrice 2x2 I2. La sottomatrice ottenuta eliminando la seconda riga è (1 0)T (1 0) (0 1)T (0 1).
Risolvendo il seguente sistema di equazioni lineari si può concludere che Una soluzione del sistema è (0,8,0,-6,4) Il sistema è incompatibile Il sistema è compatibile Due righe del sistema sono ridondanti.
Due sistemi di equazioni compatibili con insiemi delle soluzioni X e Y si dicono equivalenti se X \cap Y =X X \cup Y = \emptyset X=Y X \cap Y =Y.
Risolvendo il seguente sistema di equazioni lineari si può concludere che Una riga del sistema è ridondante Una soluzione del sistema è (0,2,0,4,8) Il sistema non ammette soluzioni Nessuna delle opzioni.
Risolvendo il seguente sistema di equazioni lineari si può concludere che Una soluzione del sistema è (0,0,1) Due righe del sistema sono ridondanti Il sistema è incompatibile Il sistema è compatibile.
Risolvendo il seguente sistema di equazioni lineari si può concludere che Il sistema ammette la soluzione (4,2,0,8,0) Una soluzione del sistema è (4,2) Il sistema non ammette soluzioni Il sistema ammette la soluzione (8,0,0,0,4).
Risolvendo il seguente sistema di equazioni lineari si può concludere che Una soluzione del sistema è (3,4) Due righe del sistema sono ridondanti Il sistema non ammette soluzioni Il sistema è compatibile.
Risolvendo il seguente sistema di equazioni lineari si può concludere che Nessuna delle opzioni Una riga del sistema è ridondante Una soluzione del sistema è (3,4,1) Il sistema è incompatibile.
Risolvendo il seguente sistema di equazioni lineari si può concludere che Nessuna delle opzioni Nessuna riga del sistema è ridondante Il sistema è incompatibile Una riga del sistema è ridondante.
Dato un sistema Ax=b con A matrice m x n e b vettore a m componenti, la matrice dei coefficienti estesa Ha m righe e n colonne Ha m righe e m colonne Ha n righe e m+1 colonne Ha m righe e n+1 colonne.
Un sistema Ax=b è compatibile se e solo se Il rango dell'insieme B dei vettori colonna della matrice A è pari al rango della matrice dei coefficienti estesa del sistema Ax=b Il rango dell'insieme B dei vettori colonna della matrice A è minore del rango della matrice dei coefficienti estesa del sistema Ax=b Nessuna delle opzioni La matrice A ha un numero di righe inferiore al numero di colonne.
Un sistema Ax=b è compatibile se e solo se Il vettore dei termini noti b è esprimibile come combinazione lineare di ogni base dell'insieme B dei vettori colonna della matrice A Nessuna delle opzioni Il vettore delle variabili x è esprimibile come combinazione lineare di una base dell'insieme B dei vettori colonna della matrice A Il vettore delle variabili x è esprimibile come combinazione lineare di ogni base dell'insieme B dei vettori riga della matrice A.
Un sistema Ax=b si definisce incompatibile se L'insieme delle soluzioni del sistema Ax=b è vuoto L'insieme delle soluzioni del sistema Ax=b è illimitato La matrice A ha rango pari al numero di colonne La matrice A ha rango pari al numero di righe.
Una sequenza di operazioni elementari effettuate a partire da una matrice A produce La matrice identità Una matrice A' equivalente ad A Una matrice A' uguale ad A La matrice A^T.
Quale tra le seguenti non è un'operazione elementare sulle righe di una matrice moltiplicare una riga della matrice per una costante non nulla moltiplicare una riga della matrice per una costante nulla sommare a una riga una combinazione lineare di altre righe permutare le righe.
Due sistemi di equazioni si dicono equivalenti se Hanno intersezione nulla degli insiemi di soluzioni ammissibili Hanno due insiemi di soluzioni ammissibili ortogonali Hanno una soluzione ammissibile in comune Hanno lo stesso insieme di soluzioni ammissibili.
Un sistema Ax=b è compatibile se e solo se Il rango dell'insieme B dei vettori colonna della matrice A è minore del rango della matrice dei coefficienti estesa del sistema Ax=b Nessuna delle opzioni Il vettore dei termini noti b è esprimibile come combinazione lineare di ogni base dell'insieme B dei vettori riga della matrice A Una base dell'insieme B dei vettori colonna della matrice A è anche una base dell'insieme dei vettori colonna della matrice (A,b).
Un problema di PL di massimizzazione si definisce illimitato superiormente se Comunque scelto un valore M esiste una soluzione ammissibile di valore non minore di M Comunque scelto un valore M esiste una soluzione ammissibile di valore minore di M Comunque scelto un valore M esiste una soluzione ammissibile di valore non maggiore di M Comunque scelto un valore M esiste una soluzione ammissibile di valore maggiore di M.
Si considerino i due problemi di PL I due problemi non sono equivalenti Nulla di può dire riguardo l'equivalenza dei due problemi Nessuna delle opzioni I due problemi sono equivalenti.
Si considerino i due problemi di PL I due problemi non sono equivalenti Nulla di può dire riguardo l'equivalenza dei due problemi I due problemi sono equivalenti Nessuna delle opzioni.
Un problema di PL di minimizzazione può essere Illimitato sia superiormente che inferiormente Illimitato inferiormente Illimitato superiormente O illimitato inferiormente o illimitato superiormente.
Un problema di PL di massimizzazione può essere Illimitato sia superiormente che inferiormente Illimitato inferiormente Illimitato superiormente O illimitato inferiormente o illimitato superiormente.
Un problema di ottimizzazione può essere sempre scritto nella sua forma generale Vero ma solo per problemi di Programmazione Lineare Falso Vero ma solo per problemi di minimizzazione Vero.
Si considerino i due problemi di PL Nulla di può dire riguardo l'equivalenza dei due problemi I due problemi non sono equivalenti Nessuna delle opzioni I due problemi sono equivalenti.
Un problema di PL di minimizzazione si definisce illimitato inferiormente se Comunque scelto un valore M esiste una soluzione ammissibile di valore non maggiore di M Comunque scelto un valore M esiste una soluzione ammissibile di valore non minore di M Comunque scelto un valore M esiste una soluzione ammissibile di valore minore di M Comunque scelto un valore M esiste una soluzione ammissibile di valore maggiore di M.
Si considerino i due problemi di PL Nulla di può dire riguardo l'equivalenza dei due problemi Nessuna delle opzioni I due problemi non sono equivalenti I due problemi sono equivalenti.
In un problema di Programmazione Lineare in forma standard le variabili Sono soggette a vincoli di capacità Sono dette vincolate in segno Nessuna delle opzioni Sono dette libere.
Un problema di Programmazione Lineare in forma standard è Un problema di Programmazione Lineare con vincoli di uguaglianza e con variabili non negative Un problema di Programmazione Lineare con vincoli di disuguaglianza e con variabili positive e negative Un problema di Programmazione Lineare con vincoli di disuguaglianza e con variabili non negative Un problema di Programmazione Lineare con vincoli di uguaglianza.
In un problema di Programmazione Lineare in forma generale le variabili Sono sempre positive Sono vincolate in segno Non sono soggette a vincoli Sono libere.
Un problema di Programmazione Lineare in forma generale è Un problema di Programmazione Lineare di massimizzazione con vincoli di maggiore o uguale e variabili non negative Un problema di Programmazione Lineare di minimizzazione con vincoli di maggiore o uguale e variabili non negative Un problema di Programmazione Lineare di massimizzazione con vincoli di disuguaglianza Un problema di Programmazione Lineare di massimizzazione con vincoli di minore o uguale e variabili libere in segno.
10. Un problema di PL inammissibile Ammette soluzioni ammissibili ma non ottime Non ammette soluzioni ammissibili Ammette solo soluzioni ottime Può essere illimitato superiormente o inferiormente.
Si consideri l'insieme convesso [1,2] di valori compresi tra 1 e 2 2 non è punto estremo Ci sono infiniti punti estremi 1 è punto estremo Non ci sono punti estremi.
In un problema della dieta I vincoli sono di disuguaglianza e pari al numero di alimenti considerati I vincoli sono lineari e pari al numero di fattori nutritivi considerati I vincoli sono di uguaglianza e pari al numero di alimenti considerati I vincoli sono non lineari e pari al numero di fattori nutritivi considerati.
Si consideri l'insieme convesso [-1,1] di valori compresi tra -1 e 1 Uno tra -1 e 1 è un punto estremo Non ci sono punti estremi Né 1 né -1 sono punti estremi -1 e 1 sono entrambi punti estremi.
Nel piano i punti estremi di un poliedro Sono i punti appartenenti al poliedro Sono i vertici del poliedro Non sono definibili Sono i vertici del poliedro che sono intersezione di almeno tre rette.
Un vettore z si dice direzione di un poliedro se Ogni retta passante per un punto del poliedro e avente direzione z appartiene al poliedro Ogni retta parallela a z appartiene al poliedro Ogni semiretta con origine in un punto del poliedro e direzione z appartiene al poliedro Ogni semiretta con direzione z appartiene al poliedro.
Si definisce cono di recessione di un poliedro La più piccola direzione del poliedro Nessuna delle opzioni L'insieme di tutte le direzioni del poliedro L'intersezione di tutte le direzioni del poliedro.
Se nel problema della dieta consideriamo 3 alimenti e 2 fattori nutritivi La formulazione matematica ha 2 variabili libere in segno La formulazione matematica ha 5 variabili in funzione obiettivo La formulazione matematica ha 3 variabili non negative La formulazione matematica ha 3 variabili e 3 vincoli.
Se nel problema della dieta consideriamo 4 alimenti e 3 fattori nutritivi La formulazione matematica ha 4 variabili libere in segno La formulazione matematica ha 3 variabili in funzione obiettivo La formulazione matematica ha 4 variabili e 3 vincoli La formulazione matematica ha 3 variabili non negative.
Un poliedro è Unione di un numero finito di semispazi chiusi Unione di un numero finito di semispazi aperti Intersezione di un numero finito di semispazi chiusi Intersezione di un numero finito di semispazi aperti.
La rappresentazione interna del poliedro P relativo al seguente problema di PL ha rec(P) e conv(Ext(P)) vuoti Ext(P) vuoto Nessuna delle opzioni rec(P) vuoto.
Dato un problema di PL in forma standard con 3 vincoli e 4 variabili il massimo numero di soluzioni di base è 24 4 16 35.
In un problema del trasporto occorre determinare la distribuzione di merce a costo minimo da tutti i magazzini a tutti i depositi la distribuzione di merce a ricavo massimo che garantisca l'esaurimento di disponibilità di ciascun deposito se attivare o meno un servizio di trasporto tra magazzini e depositi la distribuzione di merce a costo minimo che garantisca il soddisfacimento della domanda di ciascun magazzino.
Una soluzione di base x di un problema di PL in forma standard è ammissibile se e solo se le righe della matrice A con indice nell'insieme di supporto S(x) sono linearmente dipendenti le colonne della matrice A con indice nell'insieme di supporto S(x) sono linearmente indipendenti le righe della matrice A con indice nell'insieme di supporto S(x) sono linearmente indipendenti le colonne della matrice A con indice nell'insieme di supporto S(x) sono linearmente dipendenti.
Una soluzione di base x di un problema di PL in forma standard con m vincoli e n variabili si definisce degenere se la cardinalità dell'insieme delle componenti positive di x è maggiore di m la cardinalità dell'insieme delle componenti positive di x è maggiore di n la cardinalità dell'insieme delle componenti positive di x è minore di m la cardinalità dell'insieme delle componenti positive di x è minore di n.
Se una soluzione di base ammissibile x=(xB, xN) è degenere al più una componente di xB è non nulla almeno una componente di xN è non nulla al più una componente di xN è non nulla almeno una componente di xB è nulla.
Una base di un problema di PL in forma standard è invertibile solo se ha tutte le colonne non negative esiste sempre è sempre invertibile è invertibile solo se è una base ammissibile.
Dato un problema di PL in forma standard con 3 vincoli e 4 variabili il massimo numero di soluzioni di base ammissibili è 35 24 Nessuna delle opzioni 32.
Si consideri il problema di PL caratterizzato dal seguente poliedro Il massimo numero di soluzioni di base è 6 8 4 Nessuna delle opzioni.
Una soluzione di base di un problema di PL è ammissibile se l'insieme delle colonne è linearmente indipendente è ammissibile se rispetta i vincoli di non negatività esiste sempre è sempre ammissibile.
Dato un problema di PL in forma standard con matrice dei coefficienti A ∈ R^(m x n) si definisce base una sottomatrice di A con rango pari a n una sottomatrice di A con rango minore o uguale a m una sottomatrice di A con rango pari a m una sottomatrice di A con rango minore o uguale a n.
In un problema del trasporto con n depositi e m magazzini la formulazione matematica ha n vincoli m vincoli n + m vincoli n x m vincoli.
In un problema del trasporto con n depositi e m magazzini la formulazione matematica ha n variabili m variabili n + m variabili n x m variabili.
Una soluzione di base ammissibile di un problema di PL è una soluzione di base ottima è una soluzione di base a componenti non negative è una soluzione ammissibile con insieme delle colonne linearmente indipendente esiste sempre.
Il metodo grafico si può utilizzare per risolvere problemi di PL che ammettano almeno una soluzione problemi di PL in 2 dimensioni qualsiasi tipo di problema di PL problemi di PL che ammettano almeno una soluzione ottima.
Il metodo grafico si può utilizzare prevede la verifica preliminare che il problema non sia illimitato, se lo è non si individua graficamente il poliedro l'esplorazione dei soli vertici ottimi del poliedro Nessuna delle opzioni la determinazione per ispezione visiva di tutti i vertici del poliedro.
Dato un problema di PL, il problema è inammissibile oppure è Illimitato, altrimenti ammette una soluzione ottima Vuoto Illimitato, altrimenti e ammette una soluzione ammissibile Illimitato.
01. Dato un problema di PL non vuoto se esiste un vettore y del cono di recessione tale che cTy<0 allora il problema è illimitato se esiste un vettore y del cono di recessione tale che cTy>0 allora il problema è illimitato se esiste un vettore y del cono di recessione tale che cTy>=0 allora il problema è illimitato se esiste un vettore y del cono di recessione tale che cTy<=0 allora il problema è illimitato.
Dato un problema di PL non vuoto se per ogni vettore y del cono di recessione cTy >=0 allora il problema ammette una soluzione ottima se per ogni vettore y del cono di recessione cTy <=0 allora il problema ammette una soluzione ammissibile se per ogni vettore y del cono di recessione cTy >=0 allora il problema ammette una soluzione ammissibile se per ogni vettore y del cono di recessione cTy <=0 allora il problema ammette una soluzione ottima.
Dato un problema di PL non vuoto la regione ammissibile può o meno essere convessa la regione ammissibile è sempre convessa e limitata la regione ammissibile è sempre convessa la regione ammissibile è sempre convessa e illimitata.
Il teorema fondamentale della PL implica che se esiste una soluzione ottima allora esiste un vertice ottimo della regione ammissibile tutte le soluzioni ottime si trovano su un vertice della regione ammissibile tutte le soluzioni ottime si trovano nella regione ammissibile se esiste una soluzione ottima allora esiste più di un vertice ottimo della regione ammissibile.
Il teorema fondamentale della PL implica che il problema ammette sempre soluzione se il problema è vuoto o illitato non può ammettere soluzione ottima il problema è vuoto o illimitato se il problema è illimitato è anche vuoto.
Il metodo grafico è un metodo algebrico di soluzione di problemi di PL in 2 dimensioni un metodo algebrico di soluzione di problemi di PL in 3 dimensioni un metodo di soluzione per ispezione visiva di problemi di PL in 3 dimensioni un metodo di soluzione per ispezione visiva di problemi di PL in 2 dimensioni.
Il metodo grafico è è essenziale nella soluzione di problemi di PL01 è utile a dimostare il teorema fondamentale della PL Nessuna delle opzioni ha applicazione limitata per i problemi di PL.
Il metodo grafico prevede di rappresentare la regione ammissibile nel piano tracciando le rette relativi ai vincoli di uguaglianza e individuando il semispazio chiuso relativo ai vincoli rappresentare la regione ammissibile nel piano tracciando le rette relativi ai vincoli di disuguaglianza con segno di minore uguale e individuando il semispazio chiuso relativo ai vincoli rappresentare la regione ammissibile nel piano tracciando le rette relativi ai vincoli di disuguaglianza con segno di maggiore uguale e individuando il semispazio chiuso relativo ai vincoli rappresentare la regione ammissibile nel piano tracciando le rette relativi ai vincoli di disuguaglianza e individuando il semispazio chiuso relativo ai vincoli.
Si consideri un problema di PL in 5 variabili e sia data una soluzione di base ammissibile con costi ridotti (0,-2/3,-2,0,1/3) possiamo concludere che la soluzione di base corrente sia non ottima possiamo concludere che il problema sia inammissibile possiamo concludere che la soluzione di base corrente sia ottima non possiamo concludere che la soluzione di base corrente sia ottima.
Dato il seguente problema di PL il numero di soluzioni di base ammissibili è 4 5 2 6.
Dato il seguente problema di PL il numero di soluzioni di base è 6 3 4 5.
Dato il seguente problema di PL il numero di soluzioni di base massimo è 5 6 4 2.
Si consideri un problema di PL in 5 variabili con costi ridotti (-1,0,1,0,1) possiamo concludere che il problema sia illimitato possiamo concludere che la soluzione di base corrente sia non ottima non possiamo concludere che la soluzione di base corrente sia ottima possiamo concludere che la soluzione di base corrente sia ottima.
Si consideri un problema di PL in 4 variabili con costi ridotti (0,0,1,1) possiamo concludere che la soluzione di base corrente sia non ottima possiamo concludere che il problema sia illimitato possiamo concludere che la soluzione di base corrente sia ottima non possiamo concludere che la soluzione di base corrente sia ottima.
Si consideri un problema di PL in 3 variabili con costi ridotti (0,0,0) nessuna delle opzioni possiamo concludere che la soluzione di base corrente sia ottima possiamo concludere che il problema sia illimitato non possiamo concludere nulla in base ai costi ridotti.
Si consideri un problema di PL in 4 variabili e sia data una soluzione di base corrente con costi ridotti (-1,0,1,-1) non possiamo concludere che la soluzione di base corrente sia ottima possiamo concludere che il problema sia illimitato inferiormente possiamo concludere che la soluzione di base corrente sia non ottima possiamo concludere che la soluzione di base corrente sia ottima.
Dato il seguente problema di PL il numero di soluzioni di base non ammissibili è 2 5 4 3.
Applicando il criterio di ottimalità alla soluzione di base relativa alle colonne B=(1,5) del problema di seguito caratterizzato possiamo concludere che nessuna delle opzioni il problema è vuoto o illimitato occorre determinare un'altra soluzione di base la soluzione di base corrente sia ottima.
Si consideri il seguente problema di PL in forma standard il problema è vuoto o illimitato occorre determinare un'altra soluzione di base nessuna delle opzioni la soluzione di base corrente sia ottima.
Si consideri il seguente problema di PL Se consideriamo la soluzione di base ammissibile relativa alle colonne dei coefficienti delle variabili di slack introdotte per ridurre il problema in forma standard, applicando un'operazione di pivot
La nuova soluzione di base è non ammissibile il problema risulta vuoto La nuova soluzione di base ammissibile è ottima La nuova soluzione di base ammissibile ha valore 2.
Si consideri il seguente problema di PL il problema è illimitato nessuna delle opzioni il problema non è illimitato il problema è vuoto o illimitato.
Si consideri il seguente problema di PL in forma standard nessuna delle opzioni la soluzione di base corrente sia ottima occorre determinare un'altra soluzione di base il problema è vuoto o illimitato.
Si consideri il seguente problema di PL Se consideriamo la soluzione di base ammissibile relativa alle colonne dei coefficieni delle variabili di slack introdotte per ridurre il problema in forma standard, applicando un'operazione di pivot Esce di base la colonna relativa alla variabile x3 Entra in base la colonna relativa alla variabile x1 Entra in base la colonna relativa alla variabile x2 il problema risulta illimitato.
Si consideri il seguente problema di PL Se consideriamo la soluzione di base ammissibile relativa alle colonne dei coefficieni delle variabili di slack introdotte per ridurre il problema in forma standard, applicando un'operazione di pivot Entra in base la colonna relativa alla variabile x1 il problema risulta vuoto Esce di base la colonna relativa alla variabile x3 Entra in base la colonna relativa alla variabile x2.
Si consideri il seguente problema di PL Se consideriamo la soluzione di base ammissibile relativa alle colonne dei coefficieni delle variabili di slack introdotte per ridurre il problema in forma standard, applicando un'operazione di pivot La nuova soluzione di base ammissibile è ottima il problema risulta illimitato La nuova soluzione di base ammissibile fallisce il criterio di ottimalità La nuova soluzione di base ammissibile soddisfa il criterio di illimitatezza.
Si consideri il seguente problema di PL Se consideriamo la soluzione di base ammissibile relativa alle colonne dei coefficieni delle variabili di slack introdotte per ridurre il problema in forma standard, applicando un'operazione di pivot non è possibile determinare il valore della soluzione di base ammissibile considerata 1 -1 0.
Applicando la Fase 2 del metodo del simplesso al seguente problema di PL si può concludere che alla prima iterazione entra in base la variabile x1 ed esce la variabile x4 alla prima iterazione entra in base la variabile x2 ed esce la variabile x4 alla prima iterazione entra in base la variabile x2 ed esce la variabile x1 alla prima iterazione entra in base la variabile x1 ed esce la variabile x3.
Il metodo del Simplesso prevede una Fase 2 che determini una soluzione di base ammissibile per il problema oppure concluda che il problema sia vuoto partendo da una soluzione di base ammissibile determini una soluzione di base ammissibile ottima per il problema oppure concluda che il problema sia vuoto partendo da una soluzione di base ammissibile determini una soluzione di base ammissibile ottima per il problema oppure concluda che il problema sia illimitato determini se il problema sia non vuoto o illimitato.
Applicando la Fase 2 del metodo del simplesso al seguente problema di PL si può concludere che l'algoritmo termina dopo la seconda iterazione determinando una soluzione ottima di valore 1/2 l'algoritmo termina dopo la prima iterazione determinando una soluzione ottima di valore 1/2 l'algoritmo termina dopo la seconda iterazione concludendo che il problema è illimitato l'algoritmo termina dopo la prima iterazione determinando una soluzione ottima di valore 1/4.
Applicando la Fase 2 del metodo del simplesso al seguente problema di PL si può concludere che alla prima iterazione entra in base la variabile x2 ed esce la variabile x3 alla prima iterazione entra in base la variabile x1 ed esce la variabile x4 alla prima iterazione entra in base la variabile x2 ed esce la variabile x4 alla prima iterazione entra in base la variabile x1 ed esce la variabile x3.
Applicando la Fase 2 del metodo del simplesso al seguente problema di PL si può concludere che l'algoritmo termina dopo la seconda iterazione concludendo che il problema è illimitato l'algoritmo termina dopo la seconda iterazione determinando una soluzione ottima di valore 5/4 nessuna delle opzioni l'algoritmo termina dopo la prima iterazione determinando una soluzione ottima di valore 3/4.
Applicando la Fase 2 del metodo del simplesso al seguente problema di PL si può concludere che alla seconda iterazione entra in base la variabile x2 ed esce la variabile x3 l'algoritmo termina dopo la prima iterazione determinando una soluzione ottima di valore 3/4 l'algoritmo termina dopo la seconda iterazione concludendo che il problema è illimitato alla seconda iterazione entra in base la variabile x2 ed esce la variabile x1.
Si consideri un problema di PL in cinque variabili e la soluzione di base ammissibile determinata dalle ultime tre variabili. Sia la forma tabellare rispetto a tale soluzione di base la seguente: Il valore della soluzione di base ammissibile è -1 Il valore della soluzione di base ammissibile è -5 Non è possibile determinare il valore della soluzione di base ammissibile considerata Il valore della soluzione di base ammissibile è 0.
Si consideri un problema di PL in cinque variabili e la soluzione di base ammissibile determinata dalle ultime tre variabili. Sia la forma tabellare rispetto a tale soluzione di La soluzione di base ammissibile è x=(8,0,4,0,0) Non è possibile determinare la soluzione di base ammissibile considerata La soluzione di base ammissibile è x=(-5,-1,0,0,0) La soluzione di base ammissibile è x=(0,0,8,0,4).
Il metodo del Simplesso prevede una Fase 1 che nessuna delle opzioni partendo da una soluzione di base ammissibile determini una soluzione di base ammissibile ottima per il problema oppure concluda che il problema sia illimitato determini una soluzione di base ammissibile per il problema oppure concluda che il problema sia vuoto determini se il problema sia non vuoto o illimitato.
Nella coppia prima/duale simmetrica Sia il primale che il duale hanno vincoli di disuguaglianza e variabili libere in segno Il primale ha variabili non negative, mentre il duale ha variabili libere in segno Sia il primale che il duale hanno vincoli di disuguaglianza e variabili non negative Primale e duale hanno lo stesso numero di vincoli di disguguaglianza e di variabili non negative.
Nella coppia prima/duale in cui il primale è in forma standard Sia il primale che il duale hanno vincoli di uguaglianza e variabili non negative Nessuna delle opzioni Il duale ha solo vincoli di disuguaglianza e variabili vincolate in segno Il duale ha solo vincoli di disuguaglianza.
Si consideri il seguente problema di Programmazione Lineare Il suo problema duale ha solo variabili libere in segno Il suo problema duale ha solo variabili vincolate in segno Nulla si può dire riguardo le variabili del suo problema duale Il suo problema duale ha sia variabili vincolate in segno che variabili libere in segno.
Si consideri il seguente problema di Programmazione Lineare Nessuna delle opzioni Il suo problema duale ha sia variabili vincolate in segno che variabili libere in segno Il suo problema duale ha tutte le variabili vincolate in segno Il suo problema duale ha tutte le variabili libere in segno.
Si consideri il seguente problema di Programmazione Lineare Il suo problema duale ha tutte le variabili vincolate in segno Nessuna delle opzioni Il suo problema duale ha sia variabili vincolate in segno che variabili libere in segno Il suo problema duale ha tutte le variabili libere in segno.
Si consideri il seguente problema di PL in due variabili Nessuna delle opzioni Il suo problema duale ha tre variabili vincolate in segno Il suo problema duale ha tre variabili di cui due vincolate in segno Il suo problema duale ha due variabili vincolate in segno.
Si consideri il seguente problema di Programmazione Lineare Il suo problema duale ha tre variabili di cui due libere in segno e una vincolata Il suo problema duale ha quattro variabili Il suo problema duale ha tre variabili di cui due vincolate in segno e una libera Nessuna delle opzioni.
In una coppia primale/duale, se il primale è un problema di massimizzazione con m vincoli di uguaglianza e n variabili Il duale è un problema di minimizzazione con solo variabili libere in segno Il duale è un problema di massimizzazione con solo vincoli di disuguaglianza Nessuna delle opzioni Il duale è un problema di minimizzazione con m variabili vincolate in segno.
Si consideri il seguente problema di Programmazione Lineare Nessuna delle opzioni Il suo problema duale ha tre vincoli di uguaglianza Il suo problema duale ha quattro vincoli e tre variabili Il suo problema duale ha quattro vincoli di uguaglianza.
In una coppia primale/duale, se il primale è un problema di minimizzazione con m vincoli di disuguaglianza e n variabili Il duale è un problema di massimizzazione con solo variabili vincolate in segno Il duale è un problema di minimizzazione con n vincoli e m variabili libere in segno Nessuna delle opzioni Il duale è un problema di massimizzazione con solo vincoli di disuguaglianza.
In una coppia primale/duale, se il primale è un problema di massimizzazione con m vincoli e n variabili vincolate in segno Il duale è un problema di massimizzazione con solo vincoli di disuguaglianza Il duale è un problema di minimizzazione con solo vincoli di disuguaglianza Il duale è un problema di minimizzazione con n vincoli e m variabili vincolate in segno Nessuna delle opzioni.
In una coppia primale/duale, se il primale è un problema di minimizzazione con m vincoli e n variabili Il duale è un problema di massimizzazione con m vincoli e m variabili Il duale è un problema di minimizzazione con n vincoli e m variabili Il duale è un problema di massimizzazione con n vincoli e m variabili Il duale è un problema di minimizzazione con n vincoli e n variabili.
In una coppia primale/duale, se il primale ha m vincoli e n variabili Il duale è un problema di massimizzazione Il duale ha m+n vincoli e m variabili Il duale ha n vincoli e m variabili Il duale ha n vincoli e m+n variabili.
In una coppia primale/duale, se il primale è un problema di massimizzazione con m vincoli di uguaglianza e n variabili libere in segno Il duale è un problema di minimizzazione con m vincoli di uguaglianza e n variabili vincolate in segno Il duale è un problema di massimizzazione con m vincoli di uguaglianza e n variabili vincolate in segno Il duale è un problema di minimizzazione con n vincoli di disuguaglianza e m variabili libere in segno Il duale è un problema di minimizzazione con n vincoli di uguaglianza e m variabili libere in segno.
In una coppia primale/duale, il duale del problema duale è Il problema primale Il problema duale Il problema duale in caso di problema in forma generale Il problema primale in caso di problema in forma standard.
Siano x e y soluzioni ammissibili per un problema di PL di minimizzazione e per il suo problema duale Il valore della soluzione x è non maggiore del valore della soluzione y Il valore della soluzione x è maggiore del valore della soluzione y Il valore della soluzione x è minore del valore della soluzione y Il valore della soluzione x è non minore del valore della soluzione y.
Siano x e y soluzioni ammissibili per un problema di PL di massimizzazione e per il suo problema duale Il valore della soluzione x è maggiore del valore della soluzione y Il valore della soluzione x è minore del valore della soluzione y Il valore della soluzione x è non maggiore del valore della soluzione y Il valore della soluzione x è non minore del valore della soluzione y.
Dire quale delle seguenti affermazioni è falsa Il problema duale del duale è il problema primale Ogni soluzione ammissibile di un problema primale di massimizzazione ha valore non superiore a quello di ogni soluzione ammissibile del relativo problema duale Se il primale è illimitato (inferiormente o superiormente) allora il problema duale ammette soluzione ottima Se il primale ammette soluzione ottima allora il duale ammette soluzione ottima e le due soluzioni hanno valore uguale.
Dire quale delle seguenti affermazioni è vera Se il primale ammette soluzione ottima allora il duale è illimitato Se il problema primale è inammissibile allora il problema duale è illimitato o inammissibile Se il problema primale è inammissibile allora il problema duale è inammissibile Se il problema primale è inammissibile allora il problema duale è illimitato.
Dire quale delle seguenti affermazioni è vera Nessuna è vera Se il primale ammette soluzione ottima allora il duale ammette soluzione ottima e le due soluzioni hanno componenti uguali Se il primale ammette soluzione ottima allora il duale ammette soluzione ottima e le due soluzioni hanno valore diverso Se il primale ammette soluzione ottima allora il duale ammette soluzione ottima e le due soluzioni hanno valore uguale.
Dire quale delle seguenti affermazioni è falsa Ogni soluzione ammissibile di un problema primale di minimizzazione ha valore non inferiore a quello di ogni soluzione ammissibile del relativo problema duale Se il primale è illimitato (inferiormente o superiormente) allora il problema duale non ammette soluzioni ammissibili Se il primale ammette soluzione ottima allora il duale ammette soluzione ottima e le due soluzioni hanno valore uguale Se il primale è inammissibile allora il duale ammette soluzione ottima.
Siano x e y soluzioni ammissibili per un problema di PL di massimizzazione e per il suo problema duale Se il loro valore è uguale allora x e y sono soluzioni ottime per i rispettivi problemi Se il valore della soluzione x è minore del valore della soluzione y allora sono soluzioni ottime Se il valore della soluzione x è maggiore del valore della soluzione y allora non sono soluzioni ottime Se il valore della soluzione x è minore del valore della soluzione y allora non sono soluzioni ottime.
Siano x e y soluzioni ammissibili per un problema di PL di minimizzazione e per il suo problema duale Se il valore della soluzione x è maggiore del valore della soluzione y allora non sono soluzioni ottime Se il valore della soluzione x è minore del valore della soluzione y allora non sono soluzioni ottime Se il valore della soluzione x è maggiore del valore della soluzione y allora sono soluzioni ottime Se il loro valore è uguale allora x e y sono soluzioni ottime per i rispettivi problemi.
Dire quale delle seguenti affermazioni è falsa Se il primale è inammissibile allora il duale è illimitato oppure inammissibile Nessuna è falsa Se il primale ammette soluzione ottima allora il duale è illimitato Il problema duale del duale è il problema primale.
Definite due variabili di decisione x e y relative alla selezione di due progetti distinti, il vincolo x + y ≥ 3 esprime il fatto che Almeno tre progetti devono essere attivati Nessuna delle opzioni Il problema è inammissibile Nessuno dei due progetti può essere selezionato.
Definite due variabili di decisione x e y relative alla selezione di due progetti distinti, il vincolo x + y = 2 esprime il fatto che Uno solo dei due progetti deve essere selezionato Al più uno solo dei due progetti deve essere selezionato Entrambi i progetti devono essere selezionati Nessuno dei due progetti può essere selezionato.
Definite due variabili di decisione x e y relative alla selezione di due progetti distinti, il vincolo x + y = 0 esprime il fatto che Al più uno solo dei due progetti deve essere selezionato Uno solo dei due progetti deve essere selezionato Almeno uno dei due progetti deve essere selezionato Nessuno dei due progetti può essere selezionato.
Definite due variabili di decisione x e y relative alla selezione di due progetti distinti, il vincolo x + y ≥ 1 esprime il fatto che Uno solo dei due progetti deve essere selezionato Almeno uno dei due progetti deve essere selezionato Nessuno dei due progetti può essere selezionato Al più uno solo dei due progetti deve essere selezionato.
Definite due variabili di decisione x e y relative alla selezione di due progetti distinti, il vincolo x + y ≤ 1 esprime il fatto che Uno solo dei due progetti deve essere selezionato Al più uno solo dei due progetti deve essere selezionato Nessuno dei due progetti può essere selezionato Almeno uno dei due progetti deve essere selezionato.
Definite due variabili di decisione x e y relative alla selezione di due progetti distinti, il vincolo x + y = 1 esprime il fatto che Uno solo dei due progetti deve essere selezionato Almeno uno dei due progetti deve essere selezionato Al più uno solo dei due progetti deve essere selezionato Nessuno dei due progetti può essere selezionato.
Data una formulazione lineare P di un problema di PL01 con insieme delle soluzioni ammissibili S e vettore dei costi elementari c Il valore ottimo del rilassamento lineare fornisce una limitazione superiore del problema di PL01 solo nel caso in cui di minimizzazione Il valore ottimo del rilassamento lineare fornisce una limitazione inferiore del problema di PL01 solo nel caso in cui di massimizzazione Il valore ottimo del rilassamento lineare fornisce una limitazione inferiore del problema di PL01 solo nel caso in cui di minimizzazione Il valore ottimo del rilassamento lineare fornisce una limitazione superiore del problema di PL01 solo nel caso in cui di massimizzazione.
Dato un problema di PL01 di minimizzazione con insieme delle soluzioni S a n componenti e vettore dei costi c L'insieme delle soluzioni ammissibili dipende dal vettore dei costi L'insieme delle soluzioni ammissibili è incluso in {0,1}n L'insieme delle soluzioni ammissibili è incluso in Rn L'insieme delle soluzioni ammissibili non è incluso in {0,1}n.
Data una formulazione lineare P di un problema di PL01 con insieme delle soluzioni ammissibili S e vettore dei costi elementari c, si definisce rilassamento lineare del problema Il problema di PL ottenuto rimuovendo i vincoli di non negatività sulle componenti intere del vettore delle variabili di decisione Il problema di PL01 ottenuto invertendo la funzione obiettivo del problema originale Il problema di PL ottenuto rimuovendo i vincoli di interezza sulle componenti intere del vettore delle variabili di decisione Il problema di PL01 ottenuto rafforzando i vincoli di interezza sulle componenti intere del vettore delle variabili di decisione.
Data una formulazione lineare P di un problema di PL01 con insieme delle soluzioni ammissibili S e vettore dei costi elementari c Se la soluzione ottima del rilassamento lineare ha tutte componenti intere allora è una soluzione ottima del problema di PL01 Se la soluzione ottima del rilassamento lineare ha un numero di componenti intere pari almeno al numero di vincoli del problema allora è una soluzione ottima del problema di PL01 La soluzione ottima del rilassamento lineare non può mai essere soluzione ottima del problema di PL01 La soluzione ottima del rilassamento lineare può essere a componenti intere solo nel caso in cui P=S.
Data una formulazione lineare P di un problema di PL01 con insieme delle soluzioni ammissibili S e vettore dei costi elementari c Se P=conv(S) allora la soluzione ottima del rilassamento lineare ha tutte componenti frazionarie Se P=conv(S) allora la soluzione ottima del rilassamento lineare è una soluzione ottima del problema di PL01 Se l'intersezione di P e di conv(S) è pari all'ipercubo unitario allora il problema non ammette soluzione Se l'unione di P e di conv(S) è pari all'ipercubo unitario allora il problema non ammette soluzione.
Data una formulazione lineare P di un problema di PL01 con insieme delle soluzioni ammissibili S e vettore dei costi elementari c Se esiste una soluzione ammissibile x' in S che valore maggiore della soluzione ottima del rilassamento lineare allora possiamo concludere che x' è soluzione ottima del problema di PL01 Se esiste una soluzione ammissibile x' in S che valore minore della soluzione ottima del rilassamento lineare allora possiamo concludere che il problema di PL01 è vuoto Se esiste una soluzione ammissibile x' in S che valore minore della soluzione ottima del rilassamento lineare allora possiamo concludere che il problema di PL01 è illimitato Se esiste una soluzione ammissibile x' in S che ha lo stesso valore della soluzione ottima del rilassamento lineare allora possiamo concludere che x' è soluzione ottima del problema di PL01.
01. Data un problema di PL01 con insieme delle soluzioni ammissibili S e vettore dei costi elementari c A ogni formulazione lineare corrisponde un lo stesso rilassamento lineare e lo stesso lower bound per il problema A ogni formulazione lineare corrisponde un diverso rilassamento lineare e un diverso lower bound per il problema A ogni formulazione lineare corrisponde lo stesso rilassamento lineare ma un diverso lower bound per il problema A ogni formulazione lineare corrisponde un diverso rilassamento lineare e ma stesso lower bound per il problema.
Data un problema di PL01 con insieme delle soluzioni ammissibili S e vettore dei costi elementari c Una formulazione è tanto migliore quanto più alto è il valore del lower bound Una formulazione è tanto migliore quanto più intero è il valore del lower bound Una formulazione è tanto migliore quanto più basso è il valore del lower bound Una formulazione è tanto migliore quanto più positivo è il valore del lower bound.
Data un problema di PL01 con insieme delle soluzioni ammissibili S e vettore dei costi elementari c Non è possibile determinare un criterio di preferenza che sia independente dalla funzione obiettivo per stabile se una formulazione è migliore di un'altra È possibile determinare un criterio di preferenza (dependente dalla funzione obiettivo) per stabile se una formulazione è migliore di un'altra È possibile determinare un criterio di preferenza (independente dalla funzione obiettivo) per stabile se una formulazione è migliore di un'altra Tutte le formulazioni del problema sono ugualmente utili.
Date due formulazioni lineari P_1 e P_2 di un problema di PL01 P_1 è migliore di P_2 se e solo se l'intersezione di P_1 e P_2 è l'ipercubo unitario P_1 è migliore di P_2 se e solo se l'intersezione di P_1 e P_2 è vuota P_1 è migliore di P_2 se e solo se l'intersezione di P_1 e P_2 è l'insieme S P_1 è migliore di P_2 se e solo se P_1⊂P_2.
Date due formulazioni lineari P_1 e P_2 di un problema di PL01 Non si può stabilire quale sia la formulazione migliore P_1 è migliore di P_2 se e solo se P_1⊂P_2 Se ogni soluzione di P_2 è contenuta in P_1 Se ogni soluzione di P_1 è contenuta in P_2.
Data un problema di PL01 con insieme delle soluzioni ammissibili S e vettore dei costi elementari c Il problema ammette soluzione ottima solo se esistono almeno due formulazioni del problema Il problema ammette formulazione ottima solo se di minimizzazione Il problema ammette sempre formulazione ottima Il problema può non ammettere soluzione ottima.
Risolvere un problema di PL01 significa determinare una soluzione ammissibile x* in S⊂{0,1}n tale che cTx*< cTx per ogni x in {0,1}n cTx*< cTx per ogni x in S cTx* ≤ cTx per ogni x in S cTx* ≤ cTx per ogni x in {0,1}n.
In generale il processo di formulazione di un problema di PL01 Produce sempre una formulazione a componenti non negative Determina sempre la formulazione ottima del problema Produce sempre una formulazione con un numero finito di soluzioni ammissibili Non è univoco.
Dato un problema di PL01 con insieme delle soluzioni ammissibili S, una formulazione lineare del problema È tale che l'intersezione di P con l'insieme dei numeri naturali è uguale a S È tale che l'intersezione di P con S è l'ipercubo unitario Può contenere un numero infinito di soluzioni a componenti intere È tale che l'intersezione di P con l'ipercubo unitario è uguale a S.
Dato un problema di PL01 con insieme delle soluzioni ammissibili S, una formulazione lineare del problema È tale che l'intersezione di P con l'ipercubo unitario è uguale a S È tale che l'unione di P con l'ipercubo unitario è uguale a S È tale che l'unione di S con l'ipercubo unitario è uguale a P È tale che l'intersezione di S con l'ipercubo unitario è uguale a P.
Dato un problema di PL01 con insieme delle soluzioni ammissibili S, una formulazione lineare del problema Può non esistere Esiste solo se il problema ammette un numero finito di soluzioni ammissibili Esiste sempre Esiste solo se il problema è di minimizzazione.
Dato un problema di PL01 con insieme delle soluzioni ammissibili S, una formulazione lineare del problema Consente sempre di separare i vettori a componenti {0,1} corrispondenti a soluzioni ammissibili in S dai vettori a componenti {0,1} che non appartengono a S Consente sempre di separare i vettori a componenti {0,1} corrispondenti a soluzioni ammissibili in S dai vettori a componenti {0,1} che non appartengono a S solo nel caso di problemi di minimizzazione Consente sempre di separare i vettori a componenti {0,1} corrispondenti a soluzioni ammissibili in S dai vettori a componenti frazionarie Consente di separare i vettori a componenti {0,1} corrispondenti a soluzioni ammissibili in S dai vettori a componenti {0,1} che non appartengono a S solo nel caso di funzioni obiettivo lineari.
Dato un limite inferiore LB per un problema di PL01 di minimizzazione La somma del valore di una soluzione ammissibile e del limite inferiore (LB) ci permette di capire quanto la soluzione ammissibile sia lontana dalla soluzione ottima del problema PL01 La differenza (gap) tra valore di una soluzione ammissibile e limite superiore (UB) ci permette di capire quanto la soluzione ammissibile sia lontana dalla soluzione ottima del problema PL01 La differenza (gap) tra valore di una soluzione ammissibile e limite inferiore (LB) ci permette di capire quanto la soluzione ammissibile sia lontana dalla soluzione ottima del problema PL01 La differenza (gap) tra valore di una soluzione ammissibile e limite superiore (UB) ci permette di capire quanto la soluzione ammissibile sia vicina alla soluzione ottima del problema PL01.
Dato un limite inferiore LB per un problema di PL01 di minimizzazione Tanto più LB è alto meglio è Tanto più il valore di una soluzione ammissibile è vicino a LB, tanto migliore è la soluzione Tanto più LB è intero meglio è Tanto più il valore di una soluzione ammissibile è lontano da LB, tanto migliore è la soluzione.
Anche nel caso in cui non si conosca il valore ottimo di un problema (PL01), la conoscenza del limite inferiore per il problema ci permette di stabilire Se una soluzione sia a componenti intere oppure no Quanto sia "buona" una qualsiasi soluzione ammissibile Quanto sia intera una qualsiasi soluzione ammissibile Se una soluzione sia ammissibile o meno per il problema.
In generale il processo di formulazione di un problema di PL01 Fornisce automaticamente un potente strumento esatto di soluzione Non fornisce automaticamente uno strumento di soluzione del problema Produce sempre una formulazione con sole soluzioni ammissibili con componenti intere Produce sempre una formulazione con un numero finito di soluzioni ammissibili.
In generale il processo di formulazione di un problema di PL01 Produce sempre una formulazione con sole soluzioni ammissibili con componenti intere Può ammettere più formulazioni per lo stesso problema Fornisce automaticamente un potente strumento esatto di soluzione Determina sempre la formulazione ottima del problema.
Data una formulazione lineare P di un problema di PL01 con insieme delle soluzioni ammissibili S e vettore dei costi elementari c Se la soluzione ottima del rilassamento lineare ha tutte componenti intere allora è una soluzione ottima del problema di PL01 Se la soluzione ottima del rilassamento lineare ha tutte componenti frazionarie tranne una allora è una soluzione ottima del problema di PL01 La soluzione ottima del rilassamento lineare non può mai essere a componenti intere Se la soluzione ottima del rilassamento lineare ha tutte componenti non negative allora è una soluzione ottima del problema di PL01.
Determinare un lower bound per un problema di PL01 significa determinare un valore LB tale che LB ≥ cTx per ogni x in S LB ≥ cTx* per x* ottima in S LB ≤ cTx* per x* ottima in S LB ≤ cTx per ogni x in S.
Nel metodo branch and bound Quando la soluzione approssimata del sottoproblema corrente è a componenti intere, l'upper bound viene sempre aggiornato Quando la soluzione approssimata del sottoproblema corrente è a componenti intere, l'upper bound viene aggiornato se il valore della soluzione è minore del precedente Quando la soluzione approssimata del sottoproblema corrente è a componenti intere, il problema viene decomposto Quando la soluzione approssimata del sottoproblema corrente è a componenti intere, l'upper bound viene aggiornato se il valore della soluzione è non superiore del precedente.
Nel metodo branch and bound Quando il valore della soluzione approssimata del sottoproblema corrente è superiore all'upper bound il problema viene eliminato dalla lista dei sottoproblemi aperti Quando il valore della soluzione approssimata del sottoproblema corrente è superiore all'upper bound il problema viene eliminato dalla lista dei sottoproblemi aperti ma non chiuso (potrebbe ancora contenere una soluzione ottima) Quando il valore della soluzione approssimata del sottoproblema corrente è inferiore all'upper bound il problema viene eliminato dalla lista dei sottoproblemi aperti Quando il valore della soluzione approssimata del sottoproblema corrente è inferiore all'upper bound allora il problema viene chiuso.
Le possibili strategie di soluzione del metodo branch and bound Risolvono in maniera approssimata solo il primo sottoproblema Risolvono in maniera esatta il sottoproblema corrente Risolvono in maniera approssimata il sottoproblema corrente Risolvono in maniera approssimata due sottoproblemi alla volta.
Nel metodo branch and bound Si arresta quando l'upper bound viene aggiornato Si arresta quando determina una soluzione ammissibile intera Procede finché la lista dei sottoproblemi aperti è non vuota Procede finché la lista dei sottoproblemi aperti è vuota.
Nel metodo branch and bound Il sottoproblema corrente viene decomposto quando il valore della soluzione approssimata del sottoproblema è minore dell'upper bound Il sottoproblema corrente viene decomposto quando il valore della soluzione approssimata del sottoproblema è minore dell'upper bound e la soluzione non è a componenti intere Il sottoproblema corrente viene decompostoin base alla strategia di soluzione dei sottoproblemi Il sottoproblema corrente viene decomposto quando la soluzione approssimata del sottoproblema corrente non è a componenti intere.
Nel metodo branch and bound L'algoritmo si arresta quando viene trovato un sottoproblema vuoto L'algoritmo si arresta quando viene determinata una soluzione ammissibile L'algoritmo si arresta quando la lista dei sottoproblemi chiusi è vuota L'algoritmo si arresta quando la lista dei sottoproblemi aperti è vuota.
Le possibili strategie di selezione del metodo branch and bound Determinano come gestire la lista dei sottoproblemi generati dall'inizio del metodo all'iterazione corrente Selezionano quali sono le soluzioni migliori dei sottoproblemi chiusi Determinano come gestire la lista dei sottoproblemi aperti Determinano come gestire le soluzioni ottime dei sottoproblemi ancora aperti.
Le possibili strategie di selezione del metodo branch and bound Determina come chiudere tutti i sottoproblemi aperti Determina come partizionare l'insieme delle soluzioni ammissibili in due o più sottoinsiemi Determina quali dei sottoproblemi aperti sono vuoti Determina come partizionare l'insieme delle soluzioni ammissibili in due sottoinsiemi.
Gli elementi principali del metodo branch and bound sono Impiego di tecniche di euristiche di soluzione Soluzione esatta dei sottoproblemi generati ricorsivamente Decomposizione ricorsiva del problema corrente e soluzione approssimata dei sottoproblemi Decomposizione una tantum del problema originale.
Il metodo branch and bound Esplora in maniera implicita (parziale) l'insieme delle soluzioni ammissibili di un problema di PL01 Esplora in maniera implicita (parziale) l'insieme delle soluzioni ammissibili di un problema di PL01 e valuta la funzione obiettivo su sottoinsiemi limitati di soluzioni ammissibili Esplora in maniera esplicita (completa) l'insieme delle soluzioni ammissibili di un problema di PL01 ma lo fa in maniera rapida Esplora parte delle soluzioni ammissibili di un problema di PL01 quindi non può certificare l'ottimalità della soluzione ammissibile restituita.
Il metodo branch and bound È un metodo esatto di soluzione per problemi di PL01 Si applica solo a problemi di minimizzazione È un metodo euristico di soluzione per problemi di PL È un metodo euristico di soluzione per problemi di PL01.
Applicando il metodo branch and bound al seguente problema di PL01 All'ultima iterazione il lower bound è minore dell'upper bound All'ultima iterazione non è disponibile un upper bound All'ultima iterazione il lower bound è maggiore dell'upper bound All'ultima iterazione il lower bound e l'upper bound hanno valore uguale a 3.
Si consideri il seguente problema di knapsack binario Qual è il minimo valore non nullo del parametro k tale che il metodo branch and bound converga alla soluzione ottima alla prima iterazione? 2 1 Nessuna delle opzioni 3.
Applicando il metodo branch and bound al seguente problema di knapsack binario Al termine della seconda iterazione il numero di problemi aperti nella lista è 2 Nessuna delle opzioni Al termine della seconda iterazione il numero di problemi aperti nella lista è 4 Al termine della prima iterazione il numero di problemi aperti nella lista è 3.
Un problema di knapsack binario con 4 variabili di decisione Ammette al più 32 soluzioni ammissibili Nessuna delle opzioni Ammette al più 16 soluzioni ammissibili Si può risolvere solamente con il metodo del branch and bound.
Un problema di knapsack binario con 5 variabili di decisione Ammette al più 32 soluzioni ammissibili Nessuna delle opzioni Ammette al più 16 soluzioni ammissibili Si può risolvere solamente con il metodo del branch and bound.
Si consideri il seguente problema di knapsack binario Qual è il minimo valore non nullo del parametro k tale che il metodo branch and bound converga alla soluzione ottima alla prima iterazione? 2 1 Nessuna delle opzioni 8.
Applicando il metodo branch and bound al seguente problema di PL01 Alla prima iterazione il lower bound e l'upper bound hanno valore uguale Alla prima iterazione non è disponibile un upper bound Alla prima iterazione il lower bound è maggiore dell'upper bound Alla prima iterazione il lower bound è minore dell'upper bound.
Applicando il metodo branch and bound al seguente problema di PL01 L'algoritmo si arresta alla terza iterazione restituendo una soluzione ottima di valore 3 L'algoritmo si arresta alla prima iterazione restituendo una soluzione ottima di valore 8 L'algoritmo si arresta alla seconda iterazione restituendo una soluzione ottima di valore 3 L'algoritmo si arresta alla prima iterazione restituendo una soluzione ottima di valore 3.
Si consideri il seguente problema di PL01 in cinque variabili decisionali e un vincolo di diseguaglianza l'ordinamento degli indici delle variabili in ordine crescente di rapporto costo/ingombro è {5,2,3,2,2} {5,4,3,2,1} {5,1,2,3,4} {5,1,2,4,3}.
AMPL è Un server di calcolo per la risoluzione di problemi di programmazione matematica Un linguaggio di programmazione che permette di definire un qualsiasi problema di programmazione matematica Un linguaggio di programmazione che permette di definire solo alcune classi specifiche di problemi di programmazione matematica Un problema di programmazione matematica.
AMPL è Un pacchetto software per la soluzione di problemi di Programmazione Lineare Un server di calcolo per la risoluzione di problemi di programmazione matematica Un linguaggio di programmazione che permette di definire un qualsiasi problema di programmazione matematica Un pacchetto software per la soluzione di problemi di Programmazione Lineare {0,1}.
AMPL è Un linguaggio di programmazione che permette la modellazione di problemi di programmazione matematica lineari e non lineari, caratterizzati da variabili continue Un linguaggio di programmazione che permette la modellazione di problemi di programmazione matematica non lineari, caratterizzati da variabili intere Un linguaggio di programmazione che permette la modellazione di problemi di programmazione matematica lineari, caratterizzati da variabili intere e continue Un linguaggio di programmazione che permette la modellazione di problemi di programmazione matematica lineari e non lineari, caratterizzati da variabili intere e continue.
Definiti in AMPL due insiemi A e B, quale tra le seguenti espressioni non identifica tutti gli elementi dell'insieme intersezione di A e di B A inter B {i in A: i in B} {i in B: i in A} {A,B}.
Definiti in AMPL due insiemi A e B, quale tra le seguenti espressioni identifica tutti gli elementi dell'insieme differenza A/B {j in A} {i in A, j in B} {i in A: i not in B} A - B.
Definiti in AMPL due insiemi A e B, quale tra le seguenti espressioni identifica tutti gli elementi dell'insieme B Nessuna delle opzioni {i in A, j in B} {i in B: i not in A} {i in B}.
In AMPL un insieme Contiene almeno un elemento Contiene zero o più elementi Può contenere solo valori interi Si può dichiarare ma non definire.
Definiti in AMPL due insiemi A e B, quale tra le seguenti espressioni identifica tutti gli elementi dell'insieme differenza B/A {i in B, j not in A} B/A {i in B: i not in A} Nessuna delle opzioni.
In AMPL la dimensione di un insieme Dipende dal numero degli elementi dell'insieme Non si può dichiarare ma solo definire È la lunghezza delle liste che rappresentano un numero di elementi dell'insieme pari alla dimensione È la lunghezza della lista che rappresenta ogni elemento dell'insieme.
Definiti in AMPL due insiemi A e B, quale tra le seguenti espressioni identifica tutti gli elementi dell'insieme unione di A e di B {i in A: i in B} Nessuna delle opzioni A union B A diff B.
Definiti in AMPL due insiemi A e B, quale tra le seguenti espressioni identifica tutti gli elementi dell'insieme intersezione di A e di B {i in A, j in B} {A,B} {i in A: i in B} {i in A: i not in B}.
Definiti in AMPL due insiemi A e B, quale tra le seguenti espressioni identifica tutti gli elementi dell'insieme A {i in A: i in B} {B} {i in A: i not in B} {A}.
Un insieme in AMPL Non può assumere un valore di default Può assumere un valore di default Può assumere un valore di default purchè diverso dall'insieme vuoto Non può mai essere vuoto.
In AMPL è bene Separare la struttura del modello e i dati del problema in due file distinti Indicare simultaneamente struttura e dati del problema ma non nello stesso file Separare la struttura del modello e la struttura del problema in due file distinti Rendere disponibili solo le dichiarazioni ma non le definizioni.
In AMPL un insieme Può avere una o più dimensioni Non si può né dichiarare né definire a meno di casi specifici Non può avere dimensione uno Può contenere solo valori interi.
In AMPL gli elementi di un insieme Possono ripetersi nell'insieme Possono ripetersi nell'insieme solo se l'insieme ha dimensione superiore a due Devono essere tutti distinti solo se l'insieme ha dimensione pari a uno Devono essere tutti distinti.
In AMPL l'istruzione solve Restituisce sempre il numero di iterazioni del metodo del simplesso duale Determina sempre la soluzione ottima del problema Restituisce il valore ottimo del problema, se disponibile, e il vettore soluzione solo se unica soluzione ottima del problema Restituisce il valore ottimo del problema, se disponibile, senza restituire il vettore soluzione.
In AMPL l'istruzione display È seguita dal nome dell'entità di cui visualizza il valore Restituisce il valore ottimo del problema, se disponibile, e il vettore soluzione solo se unica soluzione ottima del problema È seguita dal nome del file contenente le dichiarazioni del modello che si vuole risolvere Restituisce errore se seguita dal nome identificativo di un parametro o di un insieme.
In AMPL L'istruzione option è usata solo per risolvere un modello se sono precedentemente stati caricati i parametri del problema L'istruzione option può essere usata per selezionare un solutore specifico L'istruzione option è usata solo per selezionare un solutore specifico se sono precedentemente stati caricati i parametri del problema L'istruzione option può essere usata per selezionare il solutore di default.
In AMPL Le istruzioni model e data possono essere eseguite in qualsiasi ordine Non c'è alcuna dipendenza tra le istruzioni model e data: possono far riferimento anche a problemi diversi Nessuna delle opzioni Le istruzioni model e data vanno eseguite esattamente in questo ordine.
La matrice di incidenza nodi archi di un generico grafo G(N,A) ha Componenti definite in [0,1] Componenti definite in [-1,1] Componenti definite in {-1,0,1} Componenti definite in {0,1}.
In AMPL È possibile selezionare un solutore e richiamarlo per risolvere un modello se sono stati precedentemente caricati un file .mod e un file .dat È possibile invocare un unico solutore per risolvere un modello È possibile selezionare un solutore ma non richiamarlo per risolvere un modello È possibile selezionare un solutore e richiamarlo per risolvere un modello se è stato precedentemente caricato un file .mod o un file .dat.
Il problema di flusso di costo minimo Ammette un'unica soluzione ammissibile Ammette solo soluzioni con flusso non nullo Ammette solo soluzioni con flusso non negativo Ammette un'unica soluzione ottima.
Nel problema di flusso di costo minimo La regione ammissibile è un insieme di dimensione pari al numero di sottoinsiemi dell'insieme dei nodi La regione ammissibile è un insieme di dimensione pari al numero degli archi della rete di flusso La regione ammissibile è un insieme di dimensione pari al numero dei nodi della rete di flusso La regione ammissibile non si può definire.
Nel problema di flusso di costo minimo Nessuna delle opzioni La regione ammissibile è composta di tutte le clique ammissibili per la rete di flusso La funzione obiettivo è lineare nelle componenti del flusso a coefficienti pari alle capacità La regione ammissibile è composta di tutti i flussi ammissibili per la rete di flusso.
Nel problema di flusso di costo minimo La funzione obiettivo è lineare nelle componenti del flusso e va minimizzata I vincoli sono lineari tranne nel caso di costi nulli La funzione obiettivo è lineare nelle componenti del flusso e va massimizzata I vincoli sono lineari tranne nel caso di somma delle domande non nulla.
Il problema di flusso di costo minimo è Il problema di determinare un flusso ammissibile a costo minimo Il problema di determinare un flusso ammissibile a capacità minima Il problema di determinare un taglio di costo minimo sulla rete di flusso Il problema di determinare un flusso ammissibile cui corrisponda la minima somma delle domande.
In una rete di flusso tutti i vincoli Sono lineari Sono vincoli di capacità Sono vincoli di costo Sono vincoli di non negatività.
In una rete di flusso La somma delle domande associate ai nodi è non nulla La somma delle domande associate agli archi è positiva La somma delle domande associate ai nodi è nulla La somma delle domande associate agli archi è nulla.
In una rete di flusso I costi associati agli archi compaiono nei vincoli di capacità I costi sono non negativi I costi sono associati agli archi I costi sono associati ai nodi.
In una rete di flusso Devono essere rispettati i vincoli di conservazione del flusso ma solo in presenza di domande nulle Devono essere rispettati sia i vincoli di capacità che quelli di conservazione del flusso se il flusso è discreto Devono essere rispettati i vincoli di capacità ma solo in presenza di capacità non nulle Devono essere rispettati sia i vincoli di capacità che quelli di conservazione del flusso.
In una rete di flusso Le domande definite sugli archi compaiono nei vincoli di capacità Le domande definite per ogni coppia (nodo, arco) compaiono nei vincoli di conservazione del flusso e nei vincoli di capacità Le capacità definite sui nodi sono non negative Le domande definite sui nodi compaiono nei vincoli di conservazione del flusso.
In una rete di flusso Le capacità definite sugli archi sono non negative Le capacità definite sui nodi sono positive Le capacità definite sugli archi sono positive Le capacità definite sui nodi sono non negative.
Si consideri il grafo G(N,A) in figura e si consideri le componenti della colonna della matrice di incidenza nodi archi M di G(N,A) relativa all'arco cf Nella colonna ci sarà il valore 1 in corrispondenza della riga relativa al nodo f e il valore -1 in corrispondenza della riga relativa al nodo c Nella colonna ci sarà il valore 1 in corrispondenza della riga relativa al nodo f e il valore 1 in corrispondenza della riga relativa al nodo c Non si può dire nulla delle componenti della colonna considerata Nella colonna ci saranno tutte componenti nulle.
Si consideri il grafo G(N,A) in figura e si consideri le componenti della riga della matrice di incidenza nodi archi M di G(N,A) relativa al nodo e Nella riga compariranno solo i valori 0 e -1 Nella riga compariranno solo i valori 0 e 1 Non si può dire nulla delle componenti della riga considerata Nella riga ci saranno tutte componenti nulle.
Si consideri il grafo G(N,A) in figura e si consideri le componenti della riga della matrice di incidenza nodi archi M di G(N,A) relativa al nodo c Nella riga ci saranno 6 componenti in tutto Non si può dire nulla delle componenti della riga considerata Nella riga ci saranno 3 componenti di valore -1 e 2 di valore 1 Nella riga ci saranno tutte componenti nulle.
Si consideri il grafo G(N,A) in figura e si determini il valore della componente M(e,ce) della matrice di incidenza nodi archi di G(N,A) 0 Non si può calcolare 1 -1.
Si consideri il grafo G(N,A) in figura e si determini il valore della componente M(c,ce) della matrice di incidenza nodi archi di G(N,A) 1 0 -1 Non si può calcolare.
Si consideri il grafo G(N,A) in figura e si determini il valore della componente M(a,ce) della matrice di incidenza nodi archi di G(N,A) Non si può calcolare -1 0 2.
In AMPL l'istruzione solve Richiama il solutore per risolvere il modello correntemente caricato È seguita dal nome del file contenente le dichiarazioni del modello che si vuole risolvere Non è seguita dal nome identificativo di alcun solutore solo se diverso da quello di default È preceduta dal nome del solutore che si vuole usare per risolvere il modello.
La componente (i,j) della matrice di incidenza nodi archi di un generico grafo G(N,A) è 0 se i è il nodo sorgente dell'arco j Non definita 0 se il nodo i non è né sorgente né destinazione dell'arco j 0 se i è il nodo destinazione dell'arco j.
La componente (i,j) della matrice di incidenza nodi archi di un generico grafo G(N,A) è -1 se i è il nodo destinazione dell'arco j 1 se i è il nodo sorgente dell'arco j -1 se i è il nodo sorgente dell'arco j 1 se j è il nodo sorgente dell'arco (i,j).
La componente (i,j) della matrice di incidenza nodi archi di un generico grafo G(N,A) è 1 se i è il nodo destinazione dell'arco j 1 se j è il nodo sorgente dell'arco (i,j) 1 se i è il nodo destinazione dell'arco (i,j) 1 se i è il nodo sorgente dell'arco j.
26. La matrice di incidenza nodi archi di un generico grafo G(N,A) ha Tante righe e colonne quanti sono i nodi in N Tante righe e colonne quanti sono gli archi in A Tante righe quanti sono gli archi in A e tante colonne quanti sono i nodi in N Tante righe quanti sono i nodi in N e tante colonne quanti sono gli archi in A.
Si consideri il grafo G(N,A) in figura e si determini il valore della componente M(a,ce) della matrice di incidenza nodi archi di G(N,A) 1 0 -1 Non si può calcolare.
Il problema del cammino di costo minimo da s a t Può essere dichiarato in AMPL con lo stesso file .mod contenente le dichiarazioni del problema di flusso di costo minimo Può essere dichiarato in AMPL con lo stesso file .mod e definito con lo stesso file .dat del problema di flusso di costo minimo Può essere dichiarato in AMPLsenza file .mod Può essere definito in AMPLsenza file .dat.
Nel problema del cammino di costo minimo da s a t La regione ammissibile è un insieme di dimensione pari al numero degli archi della rete di flusso La regione ammissibile non si può definire La regione ammissibile è un insieme di dimensione pari al numero di sottoinsiemi dell'insieme dei nodi La regione ammissibile è un insieme di dimensione pari al numero dei nodi della rete di flusso.
Il problema del cammino di costo minimo da s a t È un problema di flusso in cui la somma delle capacità è sempre finita È un caso particolare di problema di flusso di costo minimo È un problema di flusso senza vincoli di conservazione È un problema di flusso in cui la somma delle domande è sempre positiva.
Nel problema del cammino di costo minimo da s a t Le domande sono pari a -1 per il nodo s, 1 per il nodo t e 0 per tutti gli altri nodi Le domande sono pari a -1 per il nodo s, 1 per il nodo t e 0 per i nodi connessi a s e a t Le domande sono nulle per tutti i nodi Le domande sono pari a -1 per il nodo s e a 1 per tutti gli altri nodi.
Nel problema del cammino di costo minimo da s a t Possiamo trascurare i vincoli di capacità perché le capacità degli archi sono infinite Possiamo trascurare i vincoli di capacità perché le capacità dei nodi sono nulle Possiamo trascurare i vincoli di capacità perché le capacità degli archi sono molto grandi Possiamo trascurare i vincoli di capacità perché le capacità dei nodi sono infinite.
Nel problema del cammino di costo minimo da s a t La funzione obiettivo è una combinazione lineare a coefficienti pari al costo degli archi La funzione obiettivo è una combinazione lineare a coefficienti pari alla capacità degli archi La funzione obiettivo è una combinazione lineare a coefficienti pari alle domande dei nodi La funzione obiettivo è una combinazione lineare a coefficienti pari alle domande degli archi.
Il problema del cammino di costo minimo da s a t Il problema di determinare un cammino da s a t di capacità minima Il problema di determinare un cammino da s a t che soddisfa tutte le domande agli archi Il problema di determinare un cammino da s a t che soddisfa tutte le domande ai nodi Il problema di determinare un cammino da s a t di costo minimo.
Nel problema del cammino di costo minimo da s a t Possiamo trascurare i vincoli di capacità perché le capacità dei nodi sono infinite Possiamo trascurare i vincoli di conservazione del flusso perché le domande ai nodi sono nulle Possiamo trascurare i vincoli di capacità perché le capacità degli archi sono infinite La somma delle domande è diversa da 0.
Il problema del cammino di costo minimo da s a t Ammette solo soluzioni con flusso non negativo su tutti i nodi Ammette solo soluzioni con flusso non negativo su tutti gli archi Ammette solo soluzioni corrispondenti a cammini di costo negativo Ammette un'unica soluzione ammissibile.
In AMPL se è stato precedentemente caricato un modello e un primo file .dat, caricando un secondo file .dat (relativo sempre allo stesso modello) l'interprete AMPL Restituisce un errore Considera solo le definizioni contenute nel secondo file .dat Restituisce la soluzione ottima della prima istanza di problema definita Restituisce la soluzione ottima della seconda istanza di problema definita.
Nel problema del cammino di costo minimo da s a t Il numero di archi considerato nella rete di flusso è pari al numero di archi del grafo Il numero di archi considerato nella rete di flusso è maggiore del numero di archi del grafo Il numero di archi considerato nella rete di flusso è pari al numero di archi del grafo più uno Nessuna delle opzioni.
Nel problema del massimo flusso da s a t Il numero di archi considerato nella rete di flusso è pari al numero di archi del grafo Nessuna delle opzioni Il numero di archi considerato nella rete di flusso è minore del numero di archi del grafo Il numero di archi considerato nella rete di flusso è pari al numero di archi del grafo più uno.
Nel problema del massimo flusso da s a t La somma delle domande associate agli archi è non nulla Le domande associate ai nodi sono tutte nulle La somma delle domande associate agli archi è nulla La somma delle domande associate ai nodi è non nulla.
Nel problema del massimo flusso da s a t Dobbiamo considerare sia i vincoli di conservazione del flusso che i vincoli di capacità Possiamo trascurare i vincoli di capacità perché la capacità sull'arco fittizio è infinita Possiamo trascurare i vincoli di capacità perché sono le domande dei nodi sono nulle Possiamo trascurare i vincoli di capacità perché sono le capacità degli archi sono infinite.
Nel problema del massimo flusso da s a t La regione ammissibile è un insieme di dimensione pari al numero degli archi della rete di flusso La regione ammissibile è un insieme di dimensione superiore al numero degli archi della rete di flusso La regione ammissibile è un insieme di dimensione pari al numero dei nodi della rete di flusso La regione ammissibile non si può definire.
Il problema del massimo flusso da s a t Ammette solo soluzioni con flusso non negativo Ammette un'unica soluzione ammissibile Ammette solo soluzioni con flusso non nullo Ammette un'unica soluzione ottima.
Il problema del massimo flusso da s a t Il problema di determinare la massima quantità di flusso uscente da s ed entrante in t Il problema di determinare un flusso ammissibile a capacità massima Il problema di determinare un taglio di costo minimo sulla rete di flusso Il problema di determinare un flusso ammissibile cui corrisponda la minima somma delle domande.
Nel problema del massimo flusso da s a t I vincoli sono lineari tranne nel caso di somma delle domande non nulla La funzione obiettivo è lineare nelle componenti del flusso e va massimizzata I vincoli sono lineari tranne nel caso di capacità nulle La funzione obiettivo è lineare nelle componenti del flusso e va minimizzata.
Nel problema del massimo flusso da s a t La regione ammissibile è composta di tutte le clique ammissibili per la rete di flusso Nessuna delle opzioni La regione ammissibile è composta di tutti i flussi ammissibili per la rete di flusso che ha domande tutte nulle associate ai nodi La funzione obiettivo è lineare nelle componenti del flusso a coefficienti pari alle capacità.
In AMPL è possibile Definire istanze di problemi non ancora dichiarati nel file .mod Nessuna delle opzioni Dichiarare modelli con più gruppi di vincoli purché si assegnino identificativi diversi a ogni gruppo e ogni elemento del gruppo sia indicizzato Dichiarare modelli con un solo gruppo di vincoli.
Data una rete di flusso, il taglio s-t di capacità minima Ha capacità data dalla somma delle capacità meno il valore del flusso a ogni arco Ha capacità pari al valore del massimo flusso da s a t Ha capacità non inferiore al massimo flusso da s a t Ha capacità data dalla somma delle capacità dei nodi.
Data una rete di flusso, ogni taglio s-t Ha capacità pari al minimo flusso da s a t Ha capacità inferiore al minimo flusso da s a t Ha capacità superiore al massimo flusso da s a t Ha capacità non inferiore al massimo flusso da s a t.
Il problema del minimo taglio s-t è Il problema di determinare il taglio s-t di costo minimo Il problema di determina il minimo flusso da s a t Il problema di determinare il taglio s-t di capacità minima Il problema di determinare il taglio di capacità minima nel grafo.
Si consideri un problema di PL in quattro variabili e la soluzione di base ammissibile indicata nella seguente forma tabellare Indicare quale tra le seguenti è la soluzione di base ammissibile Non è possibile determinare la soluzione di base ammissibile (X1,X2,X3,X4)=(0,0,6,0) (X1,X2,X3,X4)=(1,0,1,1) (X1,X2,X3,X4)=(-2/3,1,0,1/3).
Si consideri il seguente problema di Programmazione Lineare Nessuna delle opzioni Il problema è in forma standard Il problema è in forma generale Il problema è sia in forma standard che in forma generale.
Si consideri il seguente problema di Programmazione Lineare Il problema è sia in forma standard che in forma generale Il problema è in forma standard Il problema è in forma generale Nessuna delle opzioni.
Si considerino un problema di PL in cinque variabili e le soluzioni di base ammissibile determinata dalle ultime variabili. Sia la forma tabellare rispetto a tale soluzione di base la seguente: Non è possibile determinare la soluzione di base ammissibile considerata La soluzione di base ammissibile è x={-5, -1,0,0,0}. La soluzione di base ammissibile è x={0,0,1,1,2}. La soluzione di base ammissibile è x={1,1,2,0,0}.
Si consideri il seguente problema di Programmazione Lineare Nessuna delle opzioni Il problema è in forma standard Il problema è in forma generale Il problema è sia in forma standard che in forma generale.
Il problema min{5: x =1, x ≤ 0} è Vuoto Ammette soluzione ottima Nessuna delle opzioni Illimitato inferiormente.
Si consideri il seguente problema di Programmazione Lineare Il suo problema duale è un problema di minimizzazione in tre variabili Il suo problema duale è un problema di minimizzazione in due variabili Il suo problema duale è un problema di massimizzazione in due variabili Nessuna delle opzioni.
Si consideri il seguente problema di Programmazione Lineare Il problema è sia in forma standard che in forma generale Il problema è in forma generale Il problema è in forma standard nessuna delle opzioni.
Dati i seguenti vettori: Non si può dire nulla sull'indipendenza/dipendenza lineare dei due vettori x e y sono linearmente dipendenti x e y sono linearmente indipendenti x e y sono illimitati.
Si consideri il seguente problema di programmazione lineare Nessuna delle opzioni Il problema è in forma standard Il problema è sia in forma standard che in forma generale Il problema è in forma generale.
La coppia V={1,2,3,4} e E={12,13,14,23,24} definisce un grafo: SENZA LOOP SENZA LOO.
Si definisce taglio d(A) in un grafo G(V,E): UN SOTTOINSIEME DI ARCHI CHE CONNETTONO NODI IN A CON NODI IN V-A UN SOTTOINSIEME DI ARCHI CHE CONNETTONO NODI IN A CON NODI IN V-.
Sia G il grafo con V={1,2,3,4} e E={12,13,14,23,24}: LA SOMMA DEI GRADI DEI NODI IN V E' 10 LA SOMMA DEI GRADI DEI NODI IN V E' 1.
In una coppia primale/duale, le condizioni di complementarietà: SONO SODDISFATTE DA UNA SOLUZIONE OTTIMA PRIMALE E DA UNA SOLUZIONE OTTIMA DUALE SONO SODDISFATTE DA UNA SOLUZIONE OTTIMA PRIMALE E DA UNA SOLUZIONE OTTIMA DUAL.
In una coppia primale/duale, se la soluzione ottima primale è (3,0,-1) allora: LA SOLUZIONE OTTIMA DUALE SODDISFERA' ALL'UGUAGLIANZA IL PRIMO E IL TERZO VINCOLO DUALE LA SOLUZIONE OTTIMA DUALE SODDISFERA' ALL'UGUAGLIANZA IL PRIMO E IL TERZO VINCOLO DUAL.
In una coppia primale/duale, se il primale ha m vincoli e n variabili: LE CONDIZIONI DI COMPLEMENTARIETÀ SARANNO m+n LE CONDIZIONI DI COMPLEMENTARIETÀ SARANNO mn.
L'algoritmo di Ford and Fulkerson: CONVERGE IN UN NUMERO FINITO DI PASSI CONVERGE IN UN NUMERO FINITO DI PASS.
Un flusso st ammissibile è massimo se e solo se: IL VALORE DEL MASSIMO FLUSSO è PARI ALLA CAPACITà DEL TAGLIO MINIMO ST IL VALORE DEL MASSIMO FLUSSO è PARI ALLA CAPACITà DEL TAGLIO MINIMO .
Il problema del massimo flusso st consiste nel determinare: UNA DISTRIBUZIONE DEL FLUSSO CHE RISPETTI I VINCOLI DI CAPACITA' E DI CONSERVAZIONE DEL FLUSSO E MASSIMIZZI LA QUANTITA' DI FLUSSO DA S A T UNA DISTRIBUZIONE DEL FLUSSO CHE RISPETTI I VINCOLI DI CAPACITA' E DI CONSERVAZIONE DEL FLUSSO E MASSIMIZZI LA QUANTITA' DI FLUSSO .
Nella formulazione matematica del problema di flusso di costo minimo: IL NUMERO DI VARIABILI è PARI AL NUMERO DEGLI ARCHI DEL GRAFO IL NUMERO DI VARIABILI è PARI AL NUMERO DEGLI ARCHI DEL GRAF.
L'algoritmo di Dijkstra termina: IN UN NUMERO DI PASSI PARI AL PIU' AL NUMERO DEI NODI DEL GRAFO IN UN NUMERO DI PASSI PARI AL PIU' AL NUMERO DEI NODI DEL GRAF.
L'algoritmo di Dijkstra determina: UN CAMMINO DI COSTO MINIMO DA UNA SORGENTE A UNA DESTINAZIONE UN CAMMINO DI COSTO MINIMO DA UNA SORGENTE A UNA DESTINAZION.
Dato un grafo connesso G(V,E), un albero ricoprente di peso minimo è: UN ALBERO T(V,F) CON |F| = |V|-1 UN ALBERO T(V,F) CON |F| = |V|.
L'algoritmo di Prim: RESTITUISCE UN ALBERO RICOPRENTE DI PESO MINIMO RESTITUISCE UN ALBERO RICOPRENTE DI PESO MINIM.
L'algorimo di Kruskal: AGGIUNGE ITERATIVAMENTE UN ARCO ALL'ALBERO RICOPRENTE PARZIALE AGGIUNGE ITERATIVAMENTE UN ARCO ALL'ALBERO RICOPRENTE PARZIAL.
Si consideri il seguente problema di PL Se consideriamo la soluzione (x1;x2)=(0,1) il valore della soluzione è 1 0 -1 Non è possibile determinare il valore della soluzione considerata perché è ammissibile.
Si consideri il seguente problema di Programmazione Lineare Nessuna delle opzioni Il problema è in forma standard Il problema è sia in forma standard che in forma generale Il problema è in forma generale.
Si consideri il seguente problema di Programmazione Lineare Nessuna delle opzioni IL problema è in forma standard Il problema è sia in forma standard che in forma generale Il problema è in forma generale.
Si consideri il seguente problema di Programmazione Lineare e il punto x=(x1,x2) di componenti (x1,x2)=(1,0) Il valore della soluzione ammissibile x è -3 X è una soluzione ottima del problema X è una soluzione ammissibile del problema Nessuna delle opzioni.
Si consideri il seguente problema di Programmazione Lineare Nessuna delle opzioni IL problema è in forma standard Il problema è sia in forma standard che in forma generale Il problema è in forma generale.
Si consideri il seguente problema di Programmazione Lineare e il punto x=(x1,x2) di componenti (x1,x2)=(3,0) X è una soluzione ammissibile del problema e il suo valore è -3 X non è una soluzione ammissibile del problema X è una soluzione ammissibile del problema e il suo valore è -9 Nessuna delle opzioni.
Si consideri il seguente problema di PL in quattro variabili e la soluzione di base ammissibile indicata nella seguente formula Non è possibile determinare una soluzione di base ammissibile La soluzione di base indicata è degenere Non è possibile determinare il valore della soluzione di base ammissibile La soluzione di base indicata è non ammissibile.
Si consideri il seguente problema di PL01 in tre variabili decisionali e un vincolo di disuguaglianza, l’ordinamento degli indici delle variabili in ordine crescente di rapporto costo/ingombro è: {3,2,1} {3,1,2} Non si può calcolare alcun ordinemanto {1,2,3}.
Si consideri il seguente problema di PL01 in tre variabili decisionali e un vincolo di disuguaglianza, l’ordinamento degli indici delle variabili in ordine decrescente di rapporto costo/ingombro è: {3,2,1} {1,3,2} Nessuna delle opzioni {1,2,3}.
Si consideri il seguente problema di Programmazione Lineare Il suo problema duale ha due vincoli di uguaglianza e tre variabili Nessuna delle opzioni Il suo problema duale ha tre vincoli e due variabili Il suo problema duale ha coefficienti tutti nulli in funzione obiettivo.
Si consideri un problema di PL in quattro variabili e la soluzione di base ammissibile indicata nella seguente formula: Il valore della soluzione di base ammissibile è (2, 0, 0, 1) Il valore della soluzione di base ammissibile è 0 Il valore della soluzione di base ammissibile è 6 Non è possibile determinare il valore della soluzione di base ammissibile considerata.
Si consideri il seguente problema di Programmazione Lineare Nessuna delle opzioni Il suo problema duale è un problema di minimizzazione in tre variabili Il suo problema duale è un problema di massimizzazione in due variabili Il suo problema duale è un problema di massimizzazione in un’unica variabile.
Si consideri il seguente problema di PL. Il massimo numero di soluzioni di base è Nessuna delle opzioni 6 4 8.
Si consideri il seguente problema di Programmazione Lineare Il suo problema duale ha tutti vincoli di disuguaglianza Il suo problema duale è un problema di massimizzazione con un unico vincolo Nessuna delle opzioni Il suo problema duale ha tutti vincoli di uguaglianza.
Si consideri il seguente problema di Programmazione Lineare Il problema è sia in forma standard che in forma generale Il problema è in forma standard Nessuna delle opzioni Il problema è in forma generale.
Si consideri il seguente problema di Programmazione Lineare e il punto x=(x1,x2) di componenti (x1,x2)=(1,0) X è una soluzione ammissibile del problema e il suo valore è -3 Nessuna delle opzioni X è una soluzione ammissibile del problema e il suo valore è 3 X non è una soluzione ammissibile del problema.
Si consideri il seguente problema di Programmazione Lineare Nessuna delle opzioni Il suo problema duale ha una variabile vincolata in segno ed una libera Il suo problema duale ha tutte le variabili vincolate in segno Il suo problema duale ha tutte le variabili libere in segno.
Si consideri il seguente problema di Programmazione Lineare Il problema è in forma standard Nessuna delle opzioni Il problema è in forma generale Il problema è sia in forma standard che in forma generale.
Si considerino un problema di PL in cinque variabili e le soluzioni di base ammissibile determinata dalle ultime tre variabili. Sia la forma tabellare rispetto a tale soluzione di base la seguente: Non è possibile determinare la soluzione di base ammissibile considerata La soluzione di base ammissibile è x={-5, -1,0,0,0}. La soluzione di base ammissibile è x={0,0,1,1,2}. La soluzione di base ammissibile è x={1,1,2,0,0}.
Si consideri un problema di PL in cinque variabili e la soluzione di base ammissibile indicata nella seguente forma tabellare Le variabili in base sono (x1, x2, x3) Le variabili in base sono (x3, x4, x5) Le variabili in base sono (x1, x4, x5) Non è possibile determinare le variabili in base nella soluzione di base considerata.
Si consideri il seguente problema di Programmazione Lineare il problema è in forma generale i problema è sia in forma standard che in forma generale il problema è in forma standard.
Si consideri un problema di PL in cinque variabili e la soluzione di base ammissibile indicata nella seguente forma tabellare possiamo concludere che il problema sia illimitato possiamo concludere che occorre effettuare un cambio di base non è possibile concludere nulla possiamo concludere che la soluzione di base corrente sia ottima.
Si consideri il problema di PL01 in tre variabili decisionali e un vincolo di diseguaglianza ha valore pari a 4 ha valore pari a 7 ammissibile non ammissibile.
Se consideriamo la soluzione (x1, x2)= (1/2,0) la soluzione non è ammissibile non è possible dire nulla della soluzione data la soluzione è ottima per il problema di PL la soluzione è ammissibile.
|
