ERASED TEST, YOU MAY BE INTERESTED ON RICERCA OPERATIVA 2
COMMENTS |
STATISTICS |
RECORDS
|
|---|
TAKE THE TEST
|
Title of test:
RICERCA OPERATIVA 2 Description: test ricerca operativa 2 Author:
Creation Date: 04/01/2022 Category: Entertainment Number of questions: 290 |
Share the Test:
New Comment
 Daniline ( uploaded 6 months ) Salve Paolo, alla fine ha avuto risponta? perché anch'io vorrei fare l'esame della Silvia non so se sono questi i quiz. grazie! |
 PaoloPasquale ( uploaded 7 months )Salve, sono i quiz della prof Canale Silvia di ing. Informatica Magistrale? Grazie Paolo |
Content:
|
Nel problema di percorso minimo su una rete di telecomunicazione Occorre determinare un cammino minimo da un nodo sorgente a un nodo destinazione Occorre determinare un sottoinsieme di nodi connessi Occorre verificare che il problema non sia illimitato inferiormente Occorre determinare un sottoinsieme di archi con peso minore di una determinata soglia. Un grafo di localizzazione è Un grafo in cui l'insieme dei nodi è l'intersezione dell'insieme dei nodi siti candidati e dei nodi clienti Un grafo con più archi che connettono coppie di nodi Un grafo in cui l'insieme dei nodi è l'intersezione dell'insieme dei nodi siti candidati e dei nodi clienti Un grafo con soli nodi Un grafo in cui l'insieme dei nodi è l'unione dell'insieme dei nodi siti candidati e dei nodi clienti. In un grafo di localizzazione, i costi di afferenza sono associati a ogni coppia di nodi agli archi che connettono nodi siti candidati e nodi clienti a ogni nodo a ogni arco. In un grafo di localizzazione, i costi di attivazione sono associati a ogni nodo a ogni arco a ogni nodo dell'insieme dei nodi siti candidati a ogni coppia di nodi. Dato il grafo di localizzazione in figura, il costo della soluzione ottima del problema di localizzazione degli impianti in cui sono attivati gli impianti A e B è 18 7 11 Nessuna delle opzioni. In un problema di localizzazione degli impianti con 4 siti candidati e 3 siti clienti il numero delle soluzioni ammissibili è 1 12 9 16. dato il grafo in figura, per il problema di localizzazione Il costo della soluzione ottima in cui sono attivi tutti gli impianti è 15 Il costo della soluzione ottima in cui sono attivi gli impianti A e B è 22 Non è possibile calcolare il costo di alcuna soluzione ottima Nessuna delle opzioni. La formulazione del problema di localizzazione degli impianti E' un problema di PLI E' un problema di ottimizzazione non vincolata E' un problema di programmazione dinamica E' un problema di PL. Nella formulazione del problema di PLI associato al problema di localizzazione degli impianti Occorre massimizzare il rendimento degli impianti Occorre minimizzare sia il costo di attivazione degli impianti che quello di afferenza dei siti clienti agli impianti attivati Occorre prima definire qual è la funzione obiettivo Occorre minimizzare il costo di attivazione degli impianti oppure il costo di afferenza dei siti clienti agli impianti attivati. Nella formulazione del problema di PLI associato al problema di localizzazione degli impianti Le variabili di decisione sono continue Definiamo un insieme di variabili di decisione relative all'attivazione dei siti candidati e un insieme di variabili di decisione relative all'attivazione dei siti clienti Le variabili di decisione sono uguali al numero di siti candidati Definiamo un insieme di variabili di decisione relative all'attivazione dei siti candidati e un insieme di variabili di decisione relative all'afferenza dei siti clienti ai potenziali siti candidati. Dato il grafo di localizzazione in figura, nella formulazione del problema di PLI associato al problema di localizzazione degli impianti Il numero di variabili è pari a 4 In funzione obiettivo compaiono solo 2 variabili Nessuna delle opzioni Il numero di variabili binarie è pari a 10. Determinare la soluzione ottima della formulazione del problema di localizzazione degli impianti Dipende dalla dimensione del problema E' facile perché sappiamo formulare il problema Non dipende dalla dimensione del problema Dipende dai costi di attivazione e dai costi di afferenza. Dato il grafo di localizzazione in figura, nella formulazione del problema di PLI associato al problema di localizzazione degli impianti Il numero di variabili binarie è pari a 3 Il numero di variabili è pari a 15 Il numero di variabili è pari a 12 Nessuna delle opzioni. 01-06 Il criterio di arresto dell'algoritmo greedy per il problema di localizzazione degli impianti L'algoritmo termina quando tutti i siti clienti sono serviti da almeno un sito candidato attivato L'algoritmo termina quando l'aggiunta di un qualunque altro sito non produce diminuzioni del costo L'algoritmo termina quando l'aggiunta di un qualunque altro sito produce diminuzioni del costo L'algoritmo termina dopo un numero noto a priori di iterazioni. 02-06 L'algoritmo greedy per il problema di localizzazione degli impianti Seleziona un sito cliente alla volta Seleziona un sito candidato alla volta Parte dall'attivazione di tutti i siti candidati Seleziona alternativamente un sito candidato e un sito cliente. 03-06 L'algoritmo greedy per il problema di localizzazione degli impianti Alla prima iterazione seleziona il sito candidato con la somma del costo di attivazione e dei costi di afferenza più alta Alla prima iterazione seleziona il sito candidato con la somma del costo di attivazione e dei costi di afferenza più bassa Alla prima iterazione seleziona il sito candidato con la somma dei costi di afferenza più alta Alla prima iterazione seleziona il sito candidato con il costo di attivazione più basso. 04-06 L'algoritmo greedy per il problema di localizzazione degli impianti Ammette la rimozione di un sito candidato dalla soluzione corrente Iterativamente selezione il sito candidato con costo di attivazione maggiore Si ferma quando ha garantito che tutti i siti clienti siano serviti Non ammette la rimozione di un sito candidato dalla soluzione corrente. 05-06 L'algoritmo greedy per il problema di localizzazione degli impianti Ha un numero di iterazioni pari al numero di archi che connettono i siti candidati ai siti clienti E' un algoritmo euristico per la determinazione di una soluzione ammissibile E' un algoritmo euristico che garantisce la convergenza alla soluzione ottima Non è detto che converga in un numero finito di iterazioni. 01-07 Il problema del p-centro Può essere formulato come un problema di Programmazione Dinamica Può essere formulato come un problema di PLI Può essere formulato come un problema di Programmazione Quadratica Può essere formulato come un problema di PL. Il problema del p-centro E' una variante del problema di localizzazione degli impianti dove si vuole minimizzare il massimo disagio nel servire i siti clienti E' una variante del problema di gestione delle scorte E' una variante del problema di localizzazione degli impianti dove si vuole minimizzare la media dei disagi nel servire i siti clienti E' una variante del problema di localizzazione degli impianti dove si vuole minimizzare la somma dei disagi nel servire i siti clienti. Il problema di dispiegamento di mezzo di soccorso in un impianto di produzione Un problema di ottimizzazione non vincolata Un problema di localizzazione Un problema di PL Un problema di knapsack. Il problema della localizzazione dei centri di assistenza alla produzione è Un problema di PL Un problema di knapsack Un problema di localizzazione Un problema di ottimizzazione non vincolata. Nell'applicazione dell'algoritmo greedy al problema di localizzazione degli impianti L'algoritmo si arresta quando non è più possibile aggiungere alla soluzione corrente un sito candidato facendo aumentare il costo della soluzione L'algoritmo si arresta quando non è più possibile aggiungere alla soluzione corrente un sito candidato facendo diminuire il costo della soluzione L'algoritmo si arresta quando sono stati inseriti tutti i siti candidati L'algoritmo si arresta quando trova una soluzione di costo nullo. Greedy e Ricerca locale Sono due tecniche euristiche che si possono applicare al problema di localizzazione degli impianti Sono due tecniche euristiche che forniscono sempre la soluzione ottima di un problema di localizzazione degli impianti Sono le uniche due tecniche euristiche che si possono applicare al problema di localizzazione degli impianti Non si possono applicare al problema di localizzazione degli impianti. Nell'applicazione dell'algoritmo greedy al problema di localizzazione degli impianti L'algoritmo si arresta quando una soluzione euristica è stata trovata e non è più possibile migliorarla facendo diminuire il costo della soluzione L'algoritmo si arresta quando una soluzione euristica è stata trovata L'algoritmo si arresta quando una soluzione esatta è stata trovata L'algoritmo si arresta quando una soluzione euristica a componenti intere è stata trovata. Greedy e Ricerca locale: Sono due tecniche euristiche che si possono applicare al problema di localizzazione degli impianti Sono due tecniche esatte che si possono applicare al problema di localizzazione degli impianti Sono due tecniche euristiche che forniscono sempre la stessa soluzione di un problema di localizzazione degli impianti Sono due tecniche euristiche che forniscono sempre la soluzione ottima di un problema di localizzazione degli impianti. 09-01 In generale, un problema di PLI è Più difficile di un problema di PL È facile come un problema di PL È difficile come un problema di PL Più facile di un problema di PL. 09-02 In un problema di PL le variabili Possono essere solo vincolate in segno se continue O sono tutte libere o sono tutte vincolate in segno ma non possono essere continue Possono essere solo libere Sono continue e possono essere libere o vincolate in segno. 09-04 In un problema di PL le variabili Possono essere sia continue che intere Devono ammettere componenti intere se vertici di un opportuno poliedro Possono avere dei punti di discontinuità ma solo in numero finito Sono sempre continue. 09-05 I metodi di soluzione euristici per un problema di PLI Sono più facili da usare nel caso di problemi di piccole dimensioni Sono particolarmente utili quando il problema è di grandi dimensioni e si dispone di un bound di ottimalità per misurare la qualità della soluzione trovata Sono estremamente efficienti ed efficaci Determinano la soluzione ottima del problema di PLI. 09-05 in un problema di PL la regione ammissibile Viene definita attraverso vincoli lineari nelle variabili, che possono essere di disuguaglianza o di uguaglianza Viene definita attraverso vincoli non lineari nelle variabili ma che sono sempre di uguaglianza Viene definita attraverso vincoli lineari nelle variabili, che sono di uguaglianza solo se le variabili sono non negative Può essere descritta da un poliedro solo se il problema ammette soluzioni a componenti tutte intere. 09-07 I metodi di soluzione euristici per un problema di PLI Sono particolarmente utili quando il problema è di grandi dimensioni Sono sempre utili a prescindere dalle dimensioni del problema Sono particolarmente utili quando il problema è di grandi dimensioni e si dispone di un bound di ottimalità per misurare la qualità della soluzione trovata Sono sempre utili a prescindere dalla qualità della soluzione trovata. 09-08 Si consideri il problema di pianificazione degli investimenti con i seguenti dati Nella cella C8 va inserita la formula C3+C4+C5+C6 solo se il valore risultante è minore del budget Nella cella C8 va inserita la formula C3*E3+C4*E4+C5*E5+C6*E6 Nella cella C8 va inserita la formula C3*F3+C4*F4+C5*F5+C6*F6 Nella cella C8 va inserito un valore minore del budget. 09-09 La formulazione di un problema di PLI È disponibile solo nel caso in cui l'insieme delle soluzioni sia finito È uno strumento indispensabile per risolvere il problema di PLI È sempre disponibile È uno strumento fondamentale per risolvere il problema di PLI. 09-10 I problemi di PLI Si devono sempre risolvere tramite tecniche esatte perché il numero di soluzioni ammissibili è finito Si devono sempre risolvere tramite tecniche euristiche perché il numero di soluzioni ammissibili è infinito Si possono risolvere tramite tecniche esatte o euristiche Non ammettono soluzione ottima. 09-11 Il problema di Localizzazione degli Impianti È un problema di PLI nella sola versione non capacitata È un problema di PL con variabili libere in segno È un problema di PLI con funzione obiettivo quadratica È un problema di PLI. 09-12 In un problema di decisione, l'alternativa fare/non fare viene in genere rappresentata con una Variabile continua in [0,1] Variabile {0,1} Variabile a n componenti binarie con n>1 Variabile che può assumere valori continui ma positivi. 09-13 In un problema di decisione, l'alternativa fare/non fare viene in genere rappresentata con una Variabile che può assumere solo valori interi Variabile continua Variabile che può assumere valori continui ma non negativi Variabile binaria. 09-14 I modelli di PLI vengono solitamente adottati in tutte le applicazioni caratterizzate da Divisibilità di risorse presenti in grandi quantità disponibili Divisibilità di risorse presenti in ridotte quantità disponibili Indivisibilità delle risorse e necessità di scegliere da un numero finito di alternative Necessità di scegliere la soluzione attraverso la definizione di funzioni di costo molto compless. 09-15 In un problema di PL la funzione obiettivo È una funzione lineare nelle variabili di decisione E' una funzione quadratica nelle variabili di decisione E' una funzione non lineare nelle variabili di decisione Può essere una qualsiasi funzione nelle variabili di decisione. 09-16 I modelli di PLI vengono solitamente adottati in tutte le applicazioni caratterizzate da Indivisibilità delle risorse e necessità di scegliere da un numero finito di alternative Necessità di scegliere la soluzione da un numero molto elevato di alternative Un'insieme ammissibile illimitato Indivisibilità delle risorse e necessità di scegliere da un numero infinito di alternative. 09-17 In un problema di PL la regione ammissibile Viene definita attraverso vincoli lineari nelle variabili, che sono di uguaglianza solo se le variabili sono non negative Può sempre essere descritta da un ipercubo unitario di adeguata dimensione Viene definita attraverso vincoli non lineari nelle variabili ma che sono sempre di disuguaglianza Può sempre essere descritta da un poliedro. 09-18 Il problema di Localizzazione degli Impianti È un problema di PL È un problema di PLI È un problema di PL con variabili non negative È un problema di PLI nella sola versione capacitata. 09-19 In un problema di PL le variabili Se continue non possono mai essere negative Se sono libere allora devono essere non negative Sono continue e possono essere libere o vincolate in segno O sono tutte libere o sono tutte vincolate in segno. 09-20 Il problema della pianificazione degli investimenti Ammette la stessa formulazione del problema di localizzazione degli impianti Non ammette soluzione esatta Si risolve sempre tramite tecniche euristiche È un problema di PLI. 09-21 Si consideri il problema di pianificazione degli investimenti con i seguenti dat Nella cella D7 va inserito il valore 41 Nella cella D7 va inserita la formula D3*F3+D4*F4+D5*F5+D6*F6 Nella cella D7 va inserita la formula D3+D4+D5+D6 Nella cella D7 va inserita la formula D3*E3+D4*E4+D5*E5+D6*E6. 09-22 Il problema della pianificazione degli investimenti Minimizza la somma degli indici di redditività Massimizza la somma degli indici di redditività Minimizza i costi di gestione Non ammette funzione obiettivo. 09-23 Si consideri il problema di pianificazione degli investimenti con i seguenti dati Nella cella C8 va inserito un valore minore del budget Nella cella C8 va inserita la formula C3+C4+C5+C6 solo se il valore risultante è minore del budget Nella cella C8 va inserita la formula C3*F3+C4*F4+C5*F5+C6*F6 Nella cella C8 va inserita la formula D3*xA+D4*xC+D5*xP+D6*x. 09-24 Si consideri il problema di pianificazione degli investimenti con i seguenti dati Nella cella D7 va inserito un valore minore del budget Nella cella D7 va inserita la formula D3*F3+D4*F4+D5*F5+D6*F6 Nella cella D7 va inserita la formula D3+D4+D5+D6 solo se il valore risultante è minore del budget Nella cella D7 va inserita la formula D3*xA+D4*xC+D5*xP+D6*xS. 09-25 In un problema di PL la regione ammissibile Viene definita attraverso vincoli lineari nelle variabili, che sono sempre di uguaglianza Viene definita attraverso vincoli lineari nelle variabili, che sono di disuguaglianza solo se le variabili sono non negative Viene definita attraverso vincoli lineari nelle variabili, che possono essere di disuguaglianza o di uguaglianza Viene definita attraverso vincoli lineari nelle variabili, che sono sempre di disuguaglianza. 09-26 In un problema della pianificazione degli investimenti La funzione obiettivo è difficile da calcolare La funzione obiettivo è lineare nelle variabili di decisione La funzione obiettivo è quadratica nelle variabili di decisione La funzione obiettivo è non lineare nelle variabili di decisione. 09-27 In un problema di PL la funzione obiettivo È una funzione lineare nelle variabili di decisione È sempre una funzione non nulla È sempre di massimizzazione È sempre di minimizzazione. 09-28 Il vincolo di budget in un problema di pianificazione degli investimenti È un vincolo lineare di uguaglianza nelle variabili binarie È un vincolo lineare di uguaglianza nelle variabili continue È un vincolo non lineare nelle variabili binarie È un vincolo lineare di disuguaglianza nelle variabili binarie. 09-29 In un problema della pianificazione degli investimenti Si associa una variabile continua in (0,1) a ogni progetto Si associa una variabile in {0,1} a ogni progetto Si associa una variabile continua in [0,1] a ogni progetto Si associa una variabile {0,1} a ogni progetto realizzabile con il budget disponibile. 09-30 Il problema della pianificazione degli investimenti Ammette sempre sia soluzioni intere che continue Non ammette soluzioni ammissibili Ammette sempre un numero finito di soluzioni ammissibili Ammette un numero infinito di soluzioni ammissibili, se continue. 10-01 Dato un problema di localizzazione degli impianti con i seguenti dat Le variabili del problema sono rappresentate dalle celle H5:J5 e H8:J11 Le variabili del problema sono rappresentate dalle celle D5:F5 e D8:F8 Le variabili del problema sono rappresentate dalle celle H8:J11 Le variabili del problema sono rappresentate dalle celle H5:J5. 10-02 Dato un problema di localizzazione degli impianti con i seguenti dat Nella cella J12 va inserita la formula relativa ai costi di afferenza Nella cella J12 va inserita la formula D8*H8+E8*I8+F8*J8 Nella cella J12 va inserita la formula D5*H5+E5*I5+F5*J5 Nella cella J12 va inserita una combinazione lineare delle variabili a coefficienti in {0,1}. 10-03 Dato un problema di localizzazione degli impianti con i seguenti dati Nel foglio Excel definiamo le celle C14:E18 in cui memorizzare il termine a destra dell'uguaglianza che definisce il vincolo che un cliente non può essere servito da un impianto non attivo Nel foglio Excel definiamo le celle C14:E18 in cui memorizzare il termine a sinistra dell'uguaglianza che definisce il vincolo che un cliente non può essere servito da un impianto attivo Nel foglio Excel definiamo le celle C14:E18 in cui memorizzare il termine a sinistra dell'uguaglianza che definisce il vincolo che un cliente non può essere servito da un impianto non attivo Nel foglio Excel definiamo le celle C14:E18 in cui memorizzare il termine a sinistra della disuguaglianza che definisce il vincolo che un cliente non può essere servito da un impianto non attivo. 10-04 Dato un problema di localizzazione degli impianti con i seguenti dati Il costo totale è memorizzato nella cella F13 Il costo totale è memorizzato nella cella J12 Il costo totale è memorizzato nella cella F12 Il costo totale non è memorizzato in alcuna cella. 5 10-0Dato un problema di localizzazione degli impianti Se il problema è di piccole dimensioni possiamo risolverlo con il Risolutore di Excel Se il problema è di PL possiamo risolverlo con il Risolutore di Excel Non possiamo risolverlo con il Risolutore di Excel perché non possiamo imporre i vincoli di interezza sulle variabili Se il problema ammette solo costi di attivazione possiamo risolverlo con il Risolutore di Excel. 10-06 Dato un problema di localizzazione degli impianti con i seguenti dati Nella cella F12 va inserita la formula D8*H8+E8*I8+F8*J8+D9*H9+E9*I9+F9*J9+D10*H10+E10*I10+F10*J10+D11*H11+E11*I11+F11*J11 Nella cella F12 va inserita la formula D11*H11+E11*I11+F11*J11 Nella cella F12 va inserita la formula D8*H8+E8*I8+F8*J8 Nella cella F12 va inserito un valore compreso tra 0 e la somma dei costi di afferenza. 10-07 Dato un problema di localizzazione degli impianti con i seguenti dati Nella cella F12 va inserito un valore compreso tra 0 e la somma dei costi di attivazione Nella cella F12 va inserita la formula D8*H8+E8*I8+F8*J8 Nella cella F12 va inserita una combinazione lineare delle variabili a coefficienti in {0,1} Nella cella F12 va inserita la formula D8*H8+E8*I8+F8*J8+D9*H9+E9*I9+F9*J9+D10*H10+E10*I10+F10*J10+D11*H11+E11*I11+F11*J11. 11-01 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 progetto deve essere selezionato Nessuno dei due progetti può essere selezionato Al più uno solo dei due progetti deve essere selezionato. 11-02 Definite due variabili di decisione x e y relative alla selezione di due progetti distinti, il vincolo x + y ≤ 1 esprime il fatto che Nessuno dei due progetti può essere selezionato Uno solo dei due progetti deve essere selezionato Al più uno solo dei due progetti deve essere selezionato Almeno uno dei due progetto deve essere selezionato. 11-03 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 Nessuno dei due progetti può essere selezionato Almeno uno dei due progetto deve essere selezionato Al più uno solo dei due progetti deve essere selezionato. 11-04 Definite due variabili di decisione x e y relative alla selezione di due progetti distinti, il vincolo x + y = 0 esprime il fatto che Uno solo dei due progetti deve essere selezionato Almeno uno dei due progetto deve essere selezionato Nessuno dei due progetti può essere selezionato Al più uno solo dei due progetti deve essere selezionato. 11-05 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 Entrambi i progetti devono essere selezionati Al più uno solo dei due progetti deve essere selezionato Nessuno dei due progetti può essere selezionato. 11-06 Definite due variabili di decisione x e y relative alla selezione di due progetti distinti, il vincolo x + y ≥ 3 esprime il fatto che Il problema è inammissibile Almeno tre progetti devono essere attivati Nessuno dei due progetti può essere selezionato Il problema è ammissibile. 12-01 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 ha lo stesso valore 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 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 è illimitato 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. 12-02 In generale il processo di formulazione di un problema di PL01 Non fornisce automaticamente uno strumento di soluzione del problema Produce sempre una formulazione con un numero finito di soluzioni ammissibili Fornisce automaticamente un potente strumento esatto di soluzione Produce sempre una formulazione con sole soluzioni ammissibili con componenti intere. 12-03 Dato un problema di PL01 con insieme delle soluzioni ammissibili S, una formulazione lineare del problema Può contenere un numero infinito di soluzioni a componenti intere È tale che l'intersezione di P con S è l'ipercubo unitario È tale che l'intersezione di P con l'ipercubo unitario è uguale a S È tale che l'intersezione di P con l'insieme dei numeri naturali è uguale a S. 12-04 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 non è incluso in {0,1}n L'insieme delle soluzioni ammissibili è incluso in Rn L'insieme delle soluzioni ammissibili è incluso in {0,1}n. 12-05 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 {0,1}n cTx*≤ cTx per ogni x in S. 12-06 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 ogni x in S LB ≤ cTx* per x* ottima in S LB ≥ cTx* per x* ottima in S. 12-07 In generale il processo di formulazione di un problema di PL01 Produce sempre una formulazione a componenti non negative Non è univoco Produce sempre una formulazione con un numero finito di soluzioni ammissibili Determina sempre la formulazione ottima del problema. 12-08 In generale il processo di formulazione di un problema di PL01 Produce sempre una formulazione con sole soluzioni ammissibili con componenti intere Fornisce automaticamente un potente strumento esatto di soluzione Determina sempre la formulazione ottima del problema Può ammettere più formulazioni per lo stesso problema. 12-09 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 Quanto sia intera una qualsiasi soluzione ammissibile Se una soluzione sia ammissibile o meno per il problema Se una soluzione sia a componenti intere oppure no Quanto sia "buona" una qualsiasi soluzione ammissibile. 12-09 Dato un limite inferiore LB per un problema di PL01 di minimizzazione Tanto più il valore di una soluzione ammissibile è lontano da LB, tanto migliore è la soluzione 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 è. 12-11 Dato un limite inferiore LB per un problema di PL01 di minimizzazione 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 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 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 inferiore (LB) ci permette di capire quanto la soluzione ammissibile sia lontana dalla soluzione ottima del problema PL01. 12-12 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. 12-13 Dato un problema di PL01 con insieme delle soluzioni ammissibili S, una formulazione lineare del problema Esiste solo se il problema ammette un numero finito di soluzioni ammissibili Esiste solo se il problema è di minimizzazione Esiste sempre Può non esistere. 12-14 Dato un problema di PL01 con insieme delle soluzioni ammissibili S, una formulazione lineare del problema È tale che l'intersezione di S con l'ipercubo unitario è uguale a P È tale che l'unione di S con l'ipercubo unitario è uguale a P È tale che l'unione di P con l'ipercubo unitario è uguale a S È tale che l'intersezione di P con l'ipercubo unitario è uguale a S. 12-15 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 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 Il problema di PL ottenuto rimuovendo i vincoli di non negatività sulle componenti intere del vettore delle variabili di decisione. 12-16 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. 12-17 Data una formulazione lineare P di un problema di PL01 con insieme delle soluzioni ammissibili S e vettore dei costi elementari c 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 Se la soluzione ottima del rilassamento lineare ha tutte componenti frazionarie tranne una allora è una soluzione ottima del problema di PL01 Se la soluzione ottima del rilassamento lineare ha tutte componenti intere allora è una soluzione ottima del problema di PL01 . 12-18 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 La soluzione ottima del rilassamento lineare non può mai essere 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 può essere a componenti intere solo nel caso in cui P=S. 12-19 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 è 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 P=conv(S) allora la soluzione ottima del rilassamento lineare ha tutte componenti frazionarie Se l'unione di P e di conv(S) è pari all'ipercubo unitario allora il problema non ammette soluzione. 12-20 Data un problema di PL01 con insieme delle soluzioni ammissibili S e vettore dei costi elementari c A ogni formulazione lineare corrisponde un diverso rilassamento lineare e ma 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 un lo stesso rilassamento lineare e lo stesso lower bound per il problema A ogni formulazione lineare corrisponde lo stesso rilassamento lineare ma un diverso lower bound per il problema. 12-21 Data un problema di PL01 con insieme delle soluzioni ammissibili S e vettore dei costi elementari c Una formulazione è tanto migliore quanto più intero è il valore del lower bound Una formulazione è tanto migliore quanto più alto è 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. 12-22 Data un problema di PL01 con insieme delle soluzioni ammissibili S e vettore dei costi elementari c È possibile determinare un criterio di preferenza (dependente dalla funzione obiettivo) per stabile se una formulazione è migliore di un'altra Tutte le formulazioni del problema sono ugualmente utili È possibile determinare un criterio di preferenza (independente dalla funzione obiettivo) per stabile se una formulazione è migliore di un'altra Non è possibile determinare un criterio di preferenza che sia independente dalla funzione obiettivo per stabile se una formulazione è migliore di un'altra. 12-23 Date due formulazioni lineari P1 e P2 di un problema di PL01 P1 è migliore di P2 se e solo se l'intersezione di P1 e P2 è l'ipercubo unitario P1 è migliore di P2 se e solo se P1⊂P2 P1 è migliore di P2 se e solo se l'intersezione di P1 e P2 è vuota P1 è migliore di P2 se e solo se l'intersezione di P1 e P2 è l'insieme S. 12-24 Date due formulazioni lineari P1 e P2 di un problema di PL01 Se ogni soluzione di P1 è contenuta in P2 Se ogni soluzione di P2 è contenuta in P1 P1 è migliore di P2 se e solo se P1 ⊂P2 Non si può stabilire quale sia la formulazione migliore. 12-25 Data un problema di PL01 con insieme delle soluzioni ammissibili S e vettore dei costi elementari c Il problema ammette sempre formulazione ottima Il problema ammette soluzione ottima solo se esistono almeno due formulazioni del problema Il problema ammette formulazione ottima solo se di minimizzazione Il problema può non ammettere soluzione ottima. 13-01 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. 13-02 Le possibili strategie di selezione del metodo branch and bound Determinano come gestire la lista dei sottoproblemi aperti Selezionano quali sono le soluzioni migliori dei sottoproblemi chiusi Determinano come gestire la lista dei sottoproblemi generati dall'inizio del metodo all'iterazione corrente Determinano come gestire le soluzioni ottime dei sottoproblemi ancora aperti. 13-03 Nel metodo branch and bound Procede finché la lista dei sottoproblemi aperti è vuota Si arresta quando determina una soluzione ammissibile intera Procede finché la lista dei sottoproblemi aperti è non vuota Si arresta quando l'upper bound viene aggiornato. 13-04 Il metodo branch and bound È un metodo euristico di soluzione per problemi di PL01 È un metodo euristico di soluzione per problemi di PL01 È un metodo esatto di soluzione per problemi di PL01 Si applica solo a problemi di minimizzazione. 13-05 Il metodo branch and bound Esplora parte delle soluzioni ammissibili di un problema di PL01 quindi non può certificare l'ottimalità della soluzione ammissibile restituita 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 in maniera implicita (parziale) l'insieme delle soluzioni ammissibili di un problema di PL01. 13-06 Gli elementi principali del metodo branch and bound sono Impiego di tecniche di euristiche di soluzione Decomposizione una tantum del problema originale Soluzione esatta dei sottoproblemi generati ricorsivamente Decomposizione ricorsiva del problema corrente e soluzione approssimata dei sottoproblemi. 13-07 Le possibili strategie di separazione 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 come partizionare l'insieme delle soluzioni ammissibili in due sottoinsiemi Determina quali dei sottoproblemi aperti sono vuoti. 13-08 Nel metodo branch and bound L'algoritmo si arresta quando la lista dei sottoproblemi aperti è vuota L'algoritmo si arresta quando la lista dei sottoproblemi chiusi è vuota L'algoritmo si arresta quando viene trovato un sottoproblema vuoto L'algoritmo si arresta quando viene determinata una soluzione ammissibile. 13-09 Nel metodo branch and bound Quando il valore della soluzione approssimata del sottoproblema corrente è inferiore all'upper bound allora il problema viene chiuso 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. 13-10 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 è non superiore 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 è minore del precedente. 13-11 Nel metodo branch and bound Il sottoproblema corrente viene decomposto quando la soluzione approssimata del sottoproblema corrente non è a componenti intere Il sottoproblema corrente viene decomposto in base alla strategia di soluzione dei sottoproblemi 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. 14-01 Applicando il metodo branch and bound al seguente problema di PL01 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 8 L'algoritmo si arresta alla prima iterazione restituendo una soluzione ottima di valore 3 L'algoritmo si arresta alla terza iterazione restituendo una soluzione ottima di valore 3. 14-02 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,4,3} {5,1,2,3,4}. 14-03 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,4,3,2,1} {5,1,2,4,3} {1,2,3,4,5} {5,1,3,3,3}. 14-04 Un problema di knapsack binario con 5 variabili di decisione Si può risolvere solamente con il metodo del branch and bound Nessuna delle opzioni Ammette al più 32 soluzioni ammissibili Ammette al più 16 soluzioni ammissibili. 14-05 Applicando il metodo branch and bound al seguente problema di PL01 Alla prima iterazione il lower bound è minore dell'upper bound Alla prima iterazione non è disponibile un upper bound Alla prima iterazione il lower bound e l'upper bound hanno valore uguale Alla prima iterazione il lower bound è maggiore dell'upper bound. 14-06 Applicando il metodo branch and bound al seguente problema di PL01 All'ultima iterazione non è disponibile un upper bound All'ultima iterazione il lower bound è maggiore dell'upper bound All'ultima iterazione il lower bound è minore dell'upper bound All'ultima iterazione il lower bound e l'upper bound hanno valore uguale a 3. 14-07 Un problema di knapsack binario con 4 variabili di decisione Ammette al più 16 soluzioni ammissibili Ammette al più 32 soluzioni ammissibili Si può risolvere solamente con il metodo del branch and bound Nessuna delle opzioni. 14-08 Applicando il metodo branch and bound al seguente problema di knapsack binario DA FARE Nessuna delle opzioni Al termine della prima iterazione il numero di problemi aperti nella lista è 3 Al termine della seconda iterazione il numero di problemi aperti nella lista è 2 Al termine della seconda iterazione il numero di problemi aperti nella lista è 4. 14-09 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? DA RISOLVERE --!!! 3 1 Nessuna delle opzioni - MESSA A CASO 2. 14.10 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? DA RISOLVERE --!!! 3 2 Nessuna delle opzioni 8. 16-01 Nel clustering le regole sono I criteri algoritmicamente indotti analizzando i dati che permettono di classificare le osservazioni in gruppi omogenei I criteri algoritmicamente indotti analizzando i dati che permettono di classificare le osservazioni in un solo gruppo Qualsiasi criterio di associazione definibile sulle osservazioni I criteri algoritmicamente indotti analizzando i dati che permettono di classificare le osservazioni in gruppi uguali. 16-02 Dire quali tra le seguenti applicazioni non si rivolve tramite tecniche di clustering Segmentazione delle immagini Pattern recognition Customer profiling Market segmentation. 16-03 Un cluster è Un'algoritmo di soluzione Una partizione degli oggetti Un gruppo di oggetti simili in base a un qualche criterio di omogeneità Un gruppo di oggetti uguali. 16-04 L'apprendimento automatico è Un nuovo linguaggio di programmazione Il processo di definizione automatica, distinta da quella naturale, di regole generali (pattern) a partire dalle osservazioni Una metodologia di apprendimento rapido Un qualsiasi processo induttivo umano. 16-05 Una distanza d è Una relazione a valori positivi che gode della proprietà di simmetria e che assume valore nullo in corrispondenza di due punti uguali Una relazione a valori non negativi che gode della proprietà di simmetria Una relazione a valori non negativi che gode della proprietà di simmetria e che assume valore nullo in corrispondenza di due punti uguali Una relazione a valori non negativi che gode della proprietà di simmetria e che assume sempre valore non nullo. 16-06 Una semimetrica è Una relazione n-aria che definisce l'omogeneità di un cluster Una distanza che assume valore nullo solo in corrispondenza di due punti uguali Una particolare metrica Una distanza che gode della proprietà di soddisfare le diseguaglianze triangolari. 16-07 Una metrica è Una relazione n-aria che definisce l'omogeneità di un cluster Una semimetrica che assume valore nullo solo in corrispondenza di due punti uguali Una relazione a valori non negativi che gode della proprietà di simmetria e che assume sempre valore non nullo in corrispondenza di punti diversi Una distanza che gode della proprietà di soddisfare le diseguaglianze triangolari. 16-08 Una metrica norma è Una distanza ma non una metrica Una semimetrica ma non una distanza Una metrica Una relazione binaria a valori negativi. 16-09 La metrica norma l2 è La distanza nulla La distanza di Manhattan La distanza Euclidea La distanza di Hamming. 16-10 La metrica norma l1 è La distanza nulla La distanza di Manhattan La distanza di Hamming La distanza Euclidea. 16-11 La metrica norma l0 è La distanza Euclidea La distanza nulla La distanza di Manhattan La distanza di Hamming. 16-12 Sia X uno spazio di oggetti e d una distanza definita su X. Un cluster in X è Un sottoinsieme di punti tali che la distanza tra due punti qualsiasi del cluster è uguale della distanza tra un qualsiasi punto del cluster e un punto esterno al cluster Un sottoinsieme di punti tali che la distanza tra due punti qualsiasi del cluster è maggiore della distanza tra un qualsiasi punto del cluster e un punto esterno al cluster Un sottoinsieme di punti tali che la distanza tra due punti qualsiasi del cluster è minore della distanza tra un qualsiasi punto del cluster e un punto esterno al cluster Un sottoinsieme di punti tali che la distanza tra due punti qualsiasi del cluster è nulla. 17-01 Un algoritmo di clustering partizionale Raggruppa le distanze in valori uguali sull'insieme delle coppie di osservazioni Raggruppa le osservazioni del training set in cluster sulla base di una misura di similarità definita sull'insieme delle coppie di osservazioni Determina osservazioni uguali tra loro Determina le porzioni migliori di osservazioni. 17-02 Nella metodologia generale di clustering l'astrazione sui dati è La definizione di opportuni rappresentanti delle distanze scelte per rappresentare i dati La definizione di opportuni rappresentanti dei cluster determinati dall'algoritmo di soluzione La selezione di opportuni sottoinsiemi di dati uguali tra loro Un passo opzionale. 17-03 Nella metodologia generale di clustering Prima si definisce la misura di similarità e poi l'algoritmo di soluzione Prima si definisce l'algoritmo di soluzione e poi la misura di similarità Prima si definisce la misura di similarità e poi la rappresentazione dei dati Prima si definisce l'algoritmo di soluzione e poi la rappresentazione dei dati. 18-01 Si definisce partizione P dell'insieme X una famiglia finita di k insiemi Non vuoti, a due a due disgiunti e tali che la loro intersezione sia pari a X Non vuoti, a due a due disgiunti e tali che la loro unione sia pari a X e la loro intersezione sia non vuota Non vuoti e tali che la loro unione sia pari a X e a due a due disgiunti Non vuoti e tali che la loro unione restituisca X. 18-02 Si definisce partizione P dell'insieme X una famiglia finita di k insiemi Non vuoti, a due a due disgiunti e tali che la loro unione sia pari a X e la loro intersezione sia non vuota Non vuoti e a due a due disgiunti Non vuoti e tali che la loro unione restituisca X Non vuoti e tali che la loro unione sia pari a X e a due a due disgiunti. 18-03 Il vettore di incidenza di un insieme paritizione è Un vettore a m componenti {0,1} con m numero degli nodi del grafo di localizzazione Un vettore che si può definire solo se l'insieme partizione è non vuoto Un vettore a m componenti continue in [0,1] con m numero degli nodi del grafo delle istanze Un vettore a m componenti {0,1} con m numero degli archi del grafo delle istanze. 18-04 L'insieme del multi-taglio del grafo nei sottoinsiemi V1,...,Vk non vuoti e disgiunti è L'insieme degli archi che connettono nodi appartenenti a due sottoinsiemi distinti in {V1,...,Vk} L'insieme degli nodi appartenenti all'intersezione di due sottoinsiemi distinti in {V1,...,Vk} L'insieme degli nodi appartenenti a due sottoinsiemi distinti in {V1,...,Vk} L'insieme degli archi che connettono nodi appartenenti all'intersezione di due sottoinsiemi distinti in {V1,...,Vk}. 18-05 Il vettore di incidenza di un insieme multi-taglio è Un vettore che si può definire solo se l'insieme multi-taglio è non vuoto Un vettore a m componenti continue in [0,1] con m numero degli nodi del grafo di localizzazione Un vettore a m componenti {0,1} con m numero degli archi del grafo delle istanze Un vettore a m componenti {0,1} con m numero degli nodi del grafo di localizzazione. 18-06 L'insieme partizione E(V) di un sottoinsieme V di nodi non vuoto è L'insieme dei nodi di V L'insieme degli archi che connettono nodi di V L'insieme dei nodi che non appartengono a V L'insieme degli archi che connettono nodi di V con nodi non appartenenti a V. 18-07 L'insieme partizione E(V,W) di due sottoinsiemi V e W di nodi non vuoti e disgiunti è L'insieme degli archi che connettono nodi di V e nodi di W L'insieme degli archi che connettono nodi di V e nodi di W nel caso in cui E(V) e E(W) abbiano intersezione nulla L'unione dell'insieme E(V) degli archi che connettono coppie di nodi di V e dell'insieme E(W) degli archi che connettono nodi di W L'insieme degli archi che connettono nodi di V che non appartengono a W. 18-08 L'insieme partizione E(V,W) di due sottoinsiemi V e W di nodi non vuoti e disgiunti è L'unione dell'insieme E(V) degli archi che connettono coppie di nodi di V e dell'insieme E(W) degli archi che connettono nodi di W L'insieme intersezione di E(V) e E(W) L'insieme degli archi che connettono nodi di V e nodi di W L'insieme degli archi che connettono nodi di V che non appartengono a W. 18-09 L'insieme partizione del grafo nei sottoinsiemi V1,...,Vk non vuoti e disgiunti è L'insieme degli nodi appartenenti a due sottoinsiemi distinti in {V1,...,Vk} L'intersezione degli insiemi partizione E(V1), ..., E(Vk) L'unione degli insiemi partizione E(V1), ..., E(Vk) L'insieme differenza degli insiemi partizione E(V1), ..., E(Vk). 18-10 Una partizione P(G) = {V1,...,Vk} dei nodi del grafo G(N,A) con k<|N| induce una partizione Q(G) = {W_1,W_2} degli archi del grafo con W_1 uguale a W_2 W_1=vuoto e W_2=E(P(G)) W_1=δ(P(G)) e W_2=E(P(G)) W_1=E(P(G)) e W_2=vuoto. 18-11 L'insieme di taglio di due sottoinsiemi V e W di nodi non vuoti e disgiunti è L'insieme degli archi che connettono nodi di V che non appartengono a W L'insieme degli archi che connettono nodi di V e nodi di W nel caso in cui la loro intersezione sia non vuota L'insieme degli archi che connettono nodi di V e nodi di W L'insieme unione dei nodi in V e W. 18-12 Una partizione P(G) = {V1,...,Vk} dei nodi del grafo G(N,A) con k<|N| induce una partizione Q(G) = {W_1,W_2} degli archi del grafo con W_1 uguale a W_2 W_1 e W_2 non necessariamente disgiunti W_1=δ(P(G)) e W_2=E(P(G)) W_1=N e W_2=A. 18-13 In un problema di clustering partizionale con vincoli di dimensione, il numero dei vincoli di dimensione è Pari al numero degli archi del grafo delle istanze Pari al numero dei nodi del grafo delle istanze Pari alla differenza tra il numero dei nodi e il numero degli archi del grafo delle istanze Pari alla somma del numero dei nodi e del numero degli archi del grafo delle istanze. 18-14 In un problema di clustering partizionale un vincolo di dimensione è un Vincolo logico che rende inammissibili soluzioni in cui ogni cluster abbia un certo numero s di elementi Vincolo logico che rende ammissibili solo soluzioni in cui ogni cluster abbia almeno un certo numero s di elementi Vincolo logico che rende ammissibili solo soluzioni in cui ogni cluster abbia esattamente un certo numero s di elementi Vincolo logico che rende ammissibili solo soluzioni in cui ogni cluster abbia al più un certo numero s di elementi. 18-15 Un problema di clustering partizionale di n istanze con parametro di dimensione s minore o uguale di 1 è Un problema di equipartizione Un problema di partizione in clique con vincolo di dimensione dei nodi di un grafo Un problema di partizione in clique dei nodi di un grafo Un problema di equipartizione in k sottoinsiemi con k = n / s. 18-16 Un problema di clustering partizionale di n istanze con parametro di dimensione s maggiore di 1 è Un problema di partizione in clique con vincolo di dimensione dei nodi di un grafo Un problema di partizione in clique dei nodi di un grafo Un problema di equipartizione in k sottoinsiemi con k = n / s Un problema di equipartizione. 18-17 Un problema di clustering partizionale di n istanze con parametro di dimensione s pari all'intero inferiore del rapporto n/2 è Un problema di equipartizione Un problema di equipartizione in k sottoinsiemi con k = n / s Un problema di partizione in clique dei nodi di un grafo Un problema di partizione in clique con vincolo di dimensione dei nodi di un grafo. 18-18 L'insieme di taglio di due sottoinsiemi V e W di nodi non vuoti e disgiunti è L'insieme intersezione dei nodi in V e W L'insieme degli archi che connettono nodi di V e nodi di W L'insieme degli archi che connettono nodi di V e nodi di W nel caso in cui la loro unione sia vuota L'insieme degli archi che connettono nodi di V che non appartengono a W. 18-19 L'insieme di taglio di un sottoinsieme V di nodi non vuoto è L'insieme dei nodi che non appartengono a V L'insieme degli archi che connettono nodi di V con nodi non appartenenti a V L'insieme degli archi che connettono nodi di V L'insieme dei nodi di V. 18-20 Un problema di clustering partizionale di n istanze con parametro di dimensione s con n multiplo di s è Un problema di equipartizione Un problema di partizione in clique con vincolo di dimensione dei nodi di un grafo Un problema di equipartizione in k sottoinsiemi con k = n / s Un problema di partizione in clique dei nodi di un grafo. 18-21 La stella di un nodo è Un sottoinsieme di nodi non vuoto Un caso particolare di insieme partizione Sempre vuota Un caso particolare di insieme di taglio. 18-22 Si definisce partizione P dell'insieme X una famiglia finita di k insiemi Non vuoti, a due a due disgiunti e tali che la loro unione sia pari a X e la loro intersezione sia non vuota Non vuoti, a due a due disgiunti e tali che la loro intersezione sia pari a z Non vuoti e a due a due disgiunti Non vuoti e tali che la loro unione sia pari a X e a due a due disgiunti. 18-23 Si consideri l'insieme X={1,2,3,4,5,6,7} e indicare quali tra le seguenti opzioni rappresenta una partizione P di X V1={1,6,2,3}, V2={5,4} V1={1,2}, V2={2,3}, V3={7}, V4={5,4,6} V1={1,6}, V2={7,2,3}, V3={}, V4={5,4} V1={1,6}, V2={2,3}, V3={7}, V4={5,4}. 18-24 Si consideri l'insieme X={a,b,c,d,e,f} e indicare quali tra le seguenti opzioni rappresenta una partizione P di X V1={a,b}, V2={}, V3={c}, V4={d,f,e} V1={1,c,2,b}, V2={5,a} V1={b,e}, V2={f,c,d}, V3={a} V1={a,b}, V2={d,c}, V3={s}, V4={f,e}. 18-25 In un problema di clustering partizionale il grafo delle istanze Ha il massimo numero di archi orientati Ha un numero di archi pari al numero di nodi Non ammette cicli Ha il massimo numero di archi non orientati. 18-26 In un problema di clustering partizionale il grafo delle istanze Ha un numero di archi orientati che dipende dalla metrica adottata Ha il massimo numero di archi orientati È tipicamente non completo, ma lo può diventare se adottiamo una metrica Ha un arco non orientato per ogni coppia di nodi . 18-27 Sia N={1,2,3,4,5,6}. Il grafo delle istanze G(N,A) ha un numero di archi pari a 0 10 15 6. 18-28 Sia N={a,b,c,d,e,f}. Il grafo delle istanze G(N,A) ha un numero di archi pari a 6 15 30 10. 18-29 Sia N={1,2}. Il grafo delle istanze G(N,A) ha un numero di archi pari a 4 2 0 1. 18-30 In un problema di clustering partizionale il grafo delle istanze è tale che Ogni sottoinsieme di nodi è vuoto Ogni sottoinsieme di nodi definisce una clique Ogni sottoinsieme di archi è non completo Ogni sottoinsieme di archi definisce una clique. 18-31 Il problema di clustering partizionale di tipo hard è il problema di Determinare una partizione delle istanze X sulla base di una misura unitaria Determinare un sottoinsieme delle istanze X sulla base di una misura di similarità Determinare una partizione delle istanze X sulla base di una misura di similarità Determinare tutti i sottoinsiemi vuoti delle istanze X. 18-32 Le soluzioni di un problema di clustering partizionale Possono essere rappresentate matematicamente Possono essere rappresentate matematicamente solo nel caso di grafo delle istanze completo Non possono essere definite a priori Non possono essere rappresentate matematicamente. 01-19. A ogni soluzione del problema di clustering partizionale, e quindi a ogni clustering P(G) del grafo G(N,A), è possibile associare un sottoinsieme di archi detto insieme partizione E(P(G)) 1 0 FALSO SE |N|<2 VERO SE |N|=|A. 02-19. A ogni soluzione del problema di clustering partizionale, e quindi a ogni clustering P(G) del grafo G(N,A), è possibile associare un costo dell'insieme partizione c(E(P(G))) Pari alla somma delle relazioni degli archi appartenenti a E(P(G)) Pari alla somma delle relazioni degli archi appartenenti all'insieme multi-taglio di P(G) Pari alla somma delle relazioni degli archi appartenenti a A Nullo nel caso in cui il G(N,A) sia completo. 03-19, A ogni soluzione del problema di clustering partizionale, e quindi a ogni clustering P(G) del grafo G(N,A), è possibile associare un costo dell'insieme partizione c(E(P(G))) 0 1 FALSO SE |N|<2 VERO SE |N|=|A|. 04-19. A ogni soluzione del problema di clustering partizionale, e quindi a ogni clustering P(G) del grafo G(N,A), è possibile associare un costo dell'insieme partizione c(E(P(G))) Esprimibile in funzione del vettore di incidenza di δ(P(G)) Esprimibile in funzione del vettore di incidenza di E(P(G)) Esprimibile in funzione del vettore di incidenza di A Esprimibile in funzione del vettore di incidenza di N. 05-19. Nella formulazione matematica del problema di clustering partizionale definito sul grafo G(N,A) la funzione obiettivo è Una combinazione lineare di un numero di elementi pari a |E(P(G))| Una combinazione lineare di un numero di elementi pari a |A| Una combinazione lineare di un numero di elementi pari a |N| Una combinazione lineare di un numero di elementi pari al massimo numero di clique in G(N,A). 06-19. Nella formulazione matematica del problema di clustering partizionale definito sul grafo G(N,A) la funzione obiettivo è Una combinazione lineare di un numero di variabili continue pari a |A| Una combinazione lineare di un numero di elementi pari al massimo numero di sottoinsiemi di nodi in G(N,A) Una combinazione lineare di un numero di elementi pari a |A| Una combinazione lineare di un numero di elementi pari a |N|. 01-20. Si definisce disequazione triangolo relativa ai nodi i, j e k la disequazione lineare x_ij + x_jk - x_ik > 1 x_ij + x_jk + x_ik ≤ 1 x_ij + x_jk + x_ik ≥ 1 x_ij + x_jk - x_ik ≤ 1. 02-20. Una disequazione triangolo relativa ai nodi i, j e k rende Inammissibili soluzioni in cui gli archi (i,j) e (j,k) appartengano a un cluster ma (i,k) non appartenga al cluster Ammissibili soluzioni in cui gli archi (i,j) e (j,k) appartengano a un cluster ma (i,k) non appartenga al cluster Inammissibili soluzioni in cui gli archi (j,k) e (i,k) appartengano a un cluster ma (j,k) non appartenga al cluster Inammissibili soluzioni in cui gli archi (i,j) e (i,k) appartengano a un cluster ma (j,k) non appartenga al cluster. 03-20. Una disequazione triangolo relativa ai nodi i, j e k implica che Se l'arco (i,j) e l'arco (j,k) appartengono a una clique (e quindi all'insieme partizione), allora anche l'arco (i,k) appartiene alla clique (e quindi all'insieme partizione) Solo due tra gli archi (i,j), (i,k) e (j,k) possono appartenere all'insieme partizione Solo uno tra gli archi (i,j), (i,k) e (j,k) può appartenere all'insieme partizione Gli archi (i,j), (i,k) e (j,k) non possono appartenere all'insieme partizione. 04-20. Sia G(N,A) un grafo delle istanze con N={1,2,3,4,5,6} Il numero delle disequazioni a due partizioni è 60 Il numero degli archi è 60 Il numero delle disequazioni triangolo è 60 Il numero delle formulazioni è 60. 05-20. Data una disquazione triangolo relativa ai nodi i, j e k L'ordine in cui compaiono i nodi i, j e k nella disequazione è importante solo se il grafo delle istanze è completo Il termine noto della disequazione dipende dal numero dei nodi L'ordine in cui compaiono i nodi i, j e k nella disequazione è importante L'ordine in cui compaiono i nodi i, j e k nella disequazione non è importante. 06-20. La disequazione a due partizioni (S,T) associata ai sottoinsiemi S e T è x(δ(S,T)) + x(E(S)) - x(E(T)) ≤ 1 x(δ(S,T)) - x(E(S)) - x(E(T)) ≤ min{|S|,|T|} x(δ(S,T)) + x(E(S)) - x(E(T)) ≤ min{|S|,|T|} Non definibile. 07-20. La disequazione a due partizioni (S,T) associata ai sottoinsiemi S e T è x(δ(S,T)) - x(E(S)) + x(E(T)) ≤ min{|E(S)|,|E(T)|} x(δ(S,T)) - x(E(S)) - x(E(T)) ≤ min{|E(S)|,|E(T)|} x(δ(S,T)) - x(E(S)) - x(E(T)) ≤ min{|S|,|T|} x(δ(S,T)) - x(E(S)) - x(E(T)) > min{|S|,|T|}. 08-20. Nel problema di partizione in clique dei nodi di un grafo la procedura di enumerazione completa Considera tutti i sottoinsiemi vuoti di nodi del grafo Considera tutti i cicli presenti nel grafo Considera tutte le partizioni in clique dei nodi del grafo Considera tutti i sottoinsiemi di archi del grafo. 09-20. Nel problema di partizione in clique dei nodi di un grafo La soluzione ottima esiste solo se l'insieme partizione è non vuoto La soluzione ottima esiste sempre ma non può essere individuata con una procedura di enumerazione completa La soluzione ottima esiste sempre e può essere individuata con una procedura di enumerazione completa La soluzione ottima esiste sempre e può essere individuata solo con una procedura euristica. 10-20. Una disequazione triangolo è Una disequazione lineare nelle componenti di un vettore a m componenti {0,1} con m = |A| Una disequazione lineare nelle componenti di un vettore a m componenti continue in [0,1] con m = |N| Una disequazione lineare nelle componenti di un vettore a m componenti {0,1} con m = |N| Una disequazione non lineare nelle componenti di un vettore a m componenti {0,1} con m = |A|. 01-21. Una disequazione a due partizioni (S,T) associata ai sottoinsiemi S e T definisce P*=conv(S) se |S| e |T| sono uguali |S| e |T| sono uno minore o uguale dell'altro |S| e |T| sono diversi |S| e |T| sono uno maggiore o uguale dell'altro. 02-21. Considerato il poliedro P' definito da tutte le disequazioni triangolo e il poliedro P'' definito da tutte le disequazioni a due partizioni P'' è una formulazione peggiore di P' P'' è una formulazione migliore di P' Una delle due è la formulazione ottima Non si può stabilire quale sia la formulazione migliore. 03-21. Considerato il poliedro P' definito da tutte le disequazioni triangolo e il poliedro P'' definito da tutte le disequazioni a due partizioni, il problema di separazione si può esprimere come Data una soluzione x in P', verificare che x appartenga a P'' o, se non vi appartiene, determinare due sottoinsiemi disgiunti e non vuoti S e T tali che la disequazione a due partizioni associata ai sottoinsiemi S e T sia violata da x Dipende dal grafo delle istanze e dall'algoritmo dei piani di taglio Data una soluzione x in P'', verificare che x appartenga a P' o, se non vi appartiene, determinare due sottoinsiemi disgiunti e non vuoti S e T tali che la disequazione a due partizioni associata ai sottoinsiemi S e T sia soddisfatta da x Data una soluzione x in P'', verificare che x appartenga a P' o, se non vi appartiene, determinare due sottoinsiemi disgiunti e non vuoti S e T tali che la disequazione a due partizioni associata ai sottoinsiemi S e T sia violata da x. 04-21. Considerato il poliedro P' definito da tutte le disequazioni triangolo e il poliedro P'' definito da tutte le disequazioni a due partizioni, per il problema di separazione conosciamo Una procedura esatta Una procedura esatta che diventa euristica se |S|=|T| Una procedura euristica che diventa esatta se |S|=|T| Una procedura euristica. 05-21. Nell'ambito dei problemi di clustering partizionale, la complessità della procedura euristica per il problema di separazione è Esponenziale nel numero di archi del grafo delle istanze Polinomiale nel numero di nodi del grafo delle istanze Logaritmico nel numero di archi del grafo delle istanze Esponenziale nel numero di nodi del grafo delle istanze. 06-21. Una disequazione a due partizioni (S,T) associata ai sottoinsiemi S e T Valida se S e T hanno intersezione nulla Valida se S e T sono non vuoti Non valida Valida se S e T sono non vuoti e disgiunti. 07-21. Considerato il poliedro P' definito da tutte le disequazioni triangolo e il poliedro P'' definito da tutte le disequazioni a due partizioni P'' è strettamente contenuto in P' P'' è contenuto in P' P' è contenuto in P'' P' = P''. 08-21. Nel caso in cui |S|=1 e |T|=2 la disequazione a due partizioni (S,T) associata ai sottoinsiemi S e T si riduce a Una disequazione a due partizioni con termine noto nullo Una disequazione non valida Una disequazione triangolo Una disequazione nulla. 09-21. Nel caso in cui |S|=1 e |T|=2 la disequazione a due partizioni (S,T) associata ai sottoinsiemi S e T si riduce a Una disequazione triangolo Non si può dire se non si conoscono i nodi in S e in T Una disequazione inutile per il problema Una disequazione non valida. 01-25. 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 {i in A: i in B} {i in B: i in A} A inter B {A,B}. 02-25. 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: i not in B} {i in A: i in B} {i in A, j in B} {A,B}. 03-25. 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 A union B {i in A: i in B} Nessuna delle opzioni A diff B. 04. Definiti in AMPL due insiemi A e B, quale tra le seguenti espressioni identifica tutti gli elementi dell'insieme differenza B/A Nessuna delle opzioni {i in B: i not in A} B/A {i in B, j not in A}. 05-25. AMPL è Un problema 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 server di calcolo per la risoluzione di problemi di programmazione matematica. 06-25. Definiti in AMPL due insiemi A e B, quale tra le seguenti espressioni identifica tutti gli elementi dell'insieme B {i in A, j in B} {i in B} Nessuna delle opzioni {i in B: i not in A}. 07-25. In AMPL la dimensione di un insieme Non si può dichiarare ma solo definire È la lunghezza della lista che rappresenta ogni elemento dell'insieme È la lunghezza delle liste che rappresentano un numero di elementi dell'insieme pari alla dimensione Dipende dal numero degli elementi dell'insieme. 08-25. Definiti in AMPL due insiemi A e B, quale tra le seguenti espressioni identifica tutti gli elementi dell'insieme A {B} {i in A: i not in B} {A} {i in A: i in B}. 09-25. In AMPL gli elementi di un insieme Possono ripetersi nell'insieme solo se l'insieme ha dimensione superiore a due Possono ripetersi nell'insieme Devono essere tutti distinti solo se l'insieme ha dimensione pari a uno Devono essere tutti distinti. 10-25. In AMPL un insieme Non può avere dimensione uno Può avere una o più dimensioni Può contenere solo valori interi Non si può né dichiarare né definire a meno di casi specifici. 11-25. In AMPL un insieme Si può dichiarare ma non definire Contiene zero o più elementi Contiene almeno un elemento Può contenere solo valori interi. 12-25. 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 Rendere disponibili solo le dichiarazioni ma non le definizioni Separare la struttura del modello e la struttura del problema in due file distinti. 13-25. AMPL è Un pacchetto software per la soluzione di problemi di Programmazione Lineare Un linguaggio di programmazione che permette di definire un qualsiasi problema di programmazione matematica Un server di calcolo per la risoluzione di problemi di programmazione matematica Un pacchetto software per la soluzione di problemi di Programmazione Lineare {0,1}. 14-25. AMPL è 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 non lineari, caratterizzati da variabili intere 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 lineari e non lineari, caratterizzati da variabili intere e continue. 15-25. Un insieme in AMPL Non può mai essere vuoto Può assumere un valore di default purchè diverso dall'insieme vuoto Può assumere un valore di default Non può assumere un valore di default. 16-25. Definiti in AMPL due insiemi A e B, quale tra le seguenti espressioni identifica tutti gli elementi dell'insieme differenza A/B {i in A: i not in B} {j in A} A - B {i in A, j in B}. 01-26. Il problema di flusso di costo minimo Ammette solo soluzioni con flusso non negativo Ammette un'unica soluzione ottima Ammette solo soluzioni con flusso non nullo Ammette un'unica soluzione ammissibile. 02-26. La matrice di incidenza nodi archi di un generico grafo G(N,A) ha Componenti definite in [-1,1] Componenti definite in [0,1] Componenti definite in {0,1} Componenti definite in {-1,0,1}. 03-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 quanti sono i nodi in N e tante 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 e colonne quanti sono gli archi in A. 04-26. La componente (i,j) della matrice di incidenza nodi archi di un generico grafo G(N,A) è 1 se i è il nodo sorgente dell'arco j 1 se i è il nodo destinazione dell'arco j 1 se i è il nodo destinazione dell'arco (i,j) 1 se j è il nodo sorgente dell'arco (i,j). 05-26. La componente (i,j) della matrice di incidenza nodi archi di un generico grafo G(N,A) è -1 se i è il nodo sorgente dell'arco j 1 se i è il nodo sorgente dell'arco j -1 se i è il nodo destinazione dell'arco j 1 se j è il nodo sorgente dell'arco (i,j). 06-26. La componente (i,j) della matrice di incidenza nodi archi di un generico grafo G(N,A) è 0 se il nodo i non è né sorgente né destinazione dell'arco j 0 se i è il nodo sorgente dell'arco j 0 se i è il nodo destinazione dell'arco j Non definita. 07-26. 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 1 0. 08-26. 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) 0 Non si può calcolare -1 2. 09-26. 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) 0 1 Non si può calcolare -1. 10-26. In una rete di flusso I costi sono non negativi I costi sono associati agli archi I costi sono associati ai nodi I costi associati agli archi compaiono nei vincoli di capacità. 11-26. 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 Nella riga ci saranno tutte componenti nulle Nella riga ci saranno 3 componenti di valore -1 e 2 di valore 1 e Non si può dire nulla delle componenti della riga considerata. 12-26. 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 Nella riga ci saranno tutte componenti nulle Non si può dire nulla delle componenti della riga considerata. 13-26. 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. 14-26. In una rete di flusso Le capacità definite sugli archi sono non negative Le capacità definite sui nodi sono non negative Le capacità definite sugli archi sono positive Le capacità definite sui nodi sono positive. 15-26. In una rete di flusso Le domande definite sugli archi compaiono nei vincoli di capacità Le capacità definite sui nodi sono non negative Le domande definite sui nodi compaiono nei vincoli di conservazione del flusso Le domande definite per ogni coppia (nodo, arco) compaiono nei vincoli di conservazione del flusso e nei vincoli di capacità. 16-26. In una rete di flusso Devono essere rispettati i vincoli di capacità ma solo in presenza di capacità non nulle 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 Devono essere rispettati sia i vincoli di capacità che quelli di conservazione del flusso se il flusso è discreto. 17-26. In una rete di flusso La somma delle domande associate agli archi è nulla La somma delle domande associate ai nodi è nulla La somma delle domande associate ai nodi è non nulla La somma delle domande associate agli archi è positiva. 18-26. In una rete di flusso tutti i vincoli Sono vincoli di non negatività Sono lineari Sono vincoli di capacità Sono vincoli di costo. 19-26. Il problema di flusso di costo minimo è Il problema di determinare un flusso ammissibile a costo minimo 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 Il problema di determinare un flusso ammissibile a capacità minima. 20-26. Nel problema di flusso di costo minimo La funzione obiettivo è lineare nelle componenti del flusso e va massimizzata I vincoli sono lineari tranne nel caso di somma delle domande non nulla I vincoli sono lineari tranne nel caso di costi nulli La funzione obiettivo è lineare nelle componenti del flusso e va minimizzata. 21-26. Nel problema di flusso di costo minimo La regione ammissibile è composta di tutti i flussi ammissibili per la rete di flusso 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à. 22-26. 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 non si può definire La regione ammissibile è un insieme di dimensione pari al numero dei nodi della rete di flusso. 23-26. 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) -1 1 Non si può calcolare 0. 01-27. In AMPL È possibile selezionare un solutore e richiamarlo per risolvere un modello se è stato precedentemente caricato un file .mod o un file .dat È possibile selezionare un solutore e richiamarlo per risolvere un modello se sono stati precedentemente caricati un file .mod e un file .dat È possibile selezionare un solutore ma non richiamarlo per risolvere un modello È possibile invocare un unico solutore per risolvere un modello. 02-27. In AMPL l'istruzione display È seguita dal nome del file contenente le dichiarazioni del modello che si vuole risolvere È 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 Restituisce errore se seguita dal nome identificativo di un parametro o di un insieme. 03-27. In AMPL l'istruzione solve Restituisce il valore ottimo del problema, se disponibile, e il vettore soluzione solo se unica soluzione ottima del problema Determina sempre la soluzione ottima del problema Restituisce il valore ottimo del problema, se disponibile, senza restituire il vettore soluzione Restituisce sempre il numero di iterazioni del metodo del simplesso duale. 04-27. In AMPL Nessuna delle opzioni Le istruzioni model e data vanno eseguite esattamente in questo ordine 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. 05-27. In AMPL l'istruzione solve 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 È seguita dal nome del file contenente le dichiarazioni del modello che si vuole risolvere Richiama il solutore per risolvere il modello correntemente caricato. 06-27. 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 il solutore di default 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 un solutore specifico. 01-28. Il problema del cammino di costo minimo da s a t è 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 di capacità minima Il problema di determinare un cammino da s a t di costo minimo Il problema di determinare un cammino da s a t che soddisfa tutte le domande ai nodi. 02-28. Nel problema del cammino di costo minimo da s 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 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 pari a -1 per il nodo s, 1 per il nodo t e 0 per tutti gli altri nodi. 03-28. 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 definito in AMPLsenza file .dat 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. 04-28. Nel problema del cammino di costo minimo da s a t La funzione obiettivo è una combinazione lineare a coefficienti pari alla capacità degli archi La funzione obiettivo è una combinazione lineare a coefficienti pari alle domande degli archi La funzione obiettivo è una combinazione lineare a coefficienti pari al costo degli archi La funzione obiettivo è una combinazione lineare a coefficienti pari alle domande dei nodi. 05-28. Nel problema del cammino di costo minimo da s a t Possiamo trascurare i vincoli di capacità perché sono le capacità degli archi sono infinite La somma delle domande è diversa da 0 Possiamo trascurare i vincoli di conservazione del flusso perché le domande ai nodi sono nulle Possiamo trascurare i vincoli di capacità perché sono le capacità dei nodi sono infinite. 06-28. Il problema del cammino di costo minimo da s a t è Ammette solo soluzioni con flusso non negativo su tutti gli archi Ammette solo soluzioni con flusso non negativo su tutti i nodi Ammette solo soluzioni corrispondenti a cammini di costo negativo Ammette un'unica soluzione ammissibile. 07-28. Nel problema del cammino di costo minimo da s a t La regione ammissibile è un insieme di dimensione pari al numero dei nodi della rete di flusso 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 non si può definire. 08-28. Il problema del cammino di costo minimo da s a t È un problema di flusso in cui la somma delle domande è sempre positiva È un problema di flusso senza vincoli di conservazione È un problema di flusso in cui la somma delle capacità è sempre finita È un caso particolare di problema di flusso di costo minimo. 09-28. Nel problema del cammino di costo minimo da s a t Possiamo trascurare i vincoli di capacità perché sono le capacità degli archi sono infinite Possiamo trascurare i vincoli di capacità perché sono le capacità dei nodi sono infinite Possiamo trascurare i vincoli di capacità perché sono le capacità dei nodi sono nulle Possiamo trascurare i vincoli di capacità perché sono le capacità degli archi sono molto grandi. 01-29. Nel problema del massimo flusso da s a t La funzione obiettivo è lineare nelle componenti del flusso e va minimizzata 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. 02-29. Nel problema del massimo flusso da s a t Nessuna delle opzioni La funzione obiettivo è lineare nelle componenti del flusso a coefficienti pari alle capacità La regione ammissibile è composta di tutte le clique ammissibili per la rete di flusso La regione ammissibile è composta di tutti i flussi ammissibili per la rete di flusso che ha domande tutte nulle associate ai nodi. 03-29. Nel problema del massimo flusso da s a t Possiamo trascurare i vincoli di capacità perché sono le domande dei nodi sono nulle Possiamo trascurare i vincoli di capacità perché la capacità sull'arco fittizio è infinita Dobbiamo considerare sia i vincoli di conservazione del flusso che i vincoli di capacità Possiamo trascurare i vincoli di capacità perché sono le capacità degli archi sono infinite. 04-29. Nel problema del massimo flusso da s a t La regione ammissibile è un insieme di dimensione superiore 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 dei nodi della rete di flusso La regione ammissibile è un insieme di dimensione pari al numero degli archi della rete di flusso. 05-29. Il problema del massimo flusso da s a t Ammette un'unica soluzione ammissibile Ammette solo soluzioni con flusso non negativo Ammette un'unica soluzione ottima Ammette solo soluzioni con flusso non nullo. 06-29. 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 la soluzione ottima della seconda istanza di problema definita Considera solo le definizioni contenute nel secondo file .dat Restituisce un errore Restituisce la soluzione ottima della prima istanza di problema definita. 07-29. Nel problema del massimo flusso da s a t La somma delle domande associate agli archi è nulla Le domande associate ai nodi sono tutte nulle La somma delle domande associate agli archi è non nulla La somma delle domande associate ai nodi è non nulla. 08-29. 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. 09-29. Il problema del massimo flusso da s a 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 Il problema di determinare la massima quantità di flusso uscente da s ed entrante in t. 10-29. Nel problema del cammino di costo minimo da s a t Nessuna delle opzioni Il numero di archi considerato nella rete di flusso è pari al numero di archi del grafo più uno 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. 01-30. In AMPL è possibile Definire istanze di problemi non ancora dichiarati nel file .mod Dichiarare modelli con più gruppi di vincoli purché si assegnino identificativi diversi a ogni gruppo e ogni elemento del gruppo sia indicizzato Nessuna delle opzioni Dichiarare modelli con un solo gruppo di vincoli. 01-31. Data una rete di flusso, il taglio s-t di capacità minima 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 Ha capacità data dalla somma delle capacità meno il valore del flusso a ogni arco. 02-31. Data una rete di flusso, ogni taglio s-t Ha capacità inferiore al minimo flusso da s a t Ha capacità pari al minimo flusso da s a t Ha capacità non inferiore al massimo flusso da s a t Ha capacità superiore al massimo flusso da s a t. 03-31. Il problema del minimo taglio s-t è 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 Il problema di determinare il taglio s-t di costo minimo. 01-32. In AMPL Non è possibile scrivere script se non in presenza in un file di dichiarazione e di un file di definizione di un modello È possibile gestire un insieme di istruzioni da un unico file Nessuna delle opzioni Occorre definire un file per ogni istruzione, se non data da riga di comando. 02-32. In AMPL Nessuna delle opzioni È possibile assegnare un nuovo valore a un parametro precedentemente definito solo se in precedenza assumeva il valore di default È possibile assegnare un nuovo valore a un parametro precedentemente definito Non è possibile assegnare un nuovo valore a un parametro precedentemente definito. 09-03. Dato un problema della pianificazione degli investimenti Non possiamo risolverlo con il Risolutore di Excel perché non possiamo imporre i vincoli di interezza sulle variabili Se il problema è di PL possiamo risolverlo con il Risolutore di Excel Non possiamo in alcun caso risolverlo con il Risolutore di Excel Se il problema è di piccole dimensioni possiamo risolverlo con il Risolutore di Excel. 01-22. Nell'applicazione del metodo dei piani di taglio al problema di partizione in clique dei nodi di un grafo La separazione delle disequazioni a due partizioni è euristica La separazione delle disequazioni triangolo è euristica La separazione delle disequazioni a due partizioni è esatta La separazione delle disequazioni a due partizioni non è necessaria. 02-22 Determinare la soluzione ottima del problema di PL01 è Facile se conosciamo una formulazione del problema Possibile solo se possiamo rafforzare almeno una disequazione valida per il un poliedro contenente tutte e sole le soluzioni ammissibili del problema di PL01 Possibile solo se esiste una sequenza di Gomory Sempre possibile attraverso la costruzione di una sequenza di Gomory. 03-22 Nel metodo dei piani di taglio, aggiungendo disequazioni generate e rafforzate iterativamente Si ottengono formulazioni sempre migliori Si possono ottenere poliedri che non sono necessariamente una formulazione del problema di PL01 Si ottengono sequenze di Gomory di lunghezza infinita Si ottengono formulazioni sempre più deboli. 04-22. Il metodo del piano di taglio è Un metodo generale esatto per la soluzione di problemi di PL Un metodo generale euristico per la soluzione di problemi di PLI Un metodo generale euristico per la soluzione di problemi di PL Un metodo generale esatto per la soluzione di problemi di PLI. 05-22 Nel metodo dei piani di taglio se l'oracolo di separazione non restituisce alcun iperpiano di separazione allora Il metodo termina solo se la soluzione ottima dell'i-esimo poliedro è a componenti intere Il metodo termina Il metodo non termina C'è un errore nella formulazione del problema. 06-22. Nel metodo dei piani di taglio è necessario Generare un numero finito di piani di taglio per produrre una formulazione con soluzione ottima intera Generare un numero teoricamente infinito di piani di taglio per produrre una formulazione con soluzione ottima intera Generare un numero finito di piani di taglio per produrre una soluzione frazionaria di valore ottimo e terminare Generare un numero infinito di piani di taglio. 07-22. Nell'applicazione del metodo dei piani di taglio al problema di partizione in clique dei nodi di un grafo Si applica il metodo branch and bound a un problema definito da un sottoinsieme di disequazioni triangolo Si applica il metodo branch and bound a un problema definito da un sottoinsieme di disequazioni triangolo e di disequazioni a due partizioni Si applica il metodo branch and bound a un problema definito da un sottoinsieme di disequazioni a due partizioni Non si applica il metodo branch and bound . 08-22. Nel metodo dei piani di taglio aggiungendo la disequazione determinata dall'oracolo e rafforzata al poliedro corrente Si ottiene un nuovo poliedro i+1 che non è necessariamente una formulazione del prolema di PL01 Si può ottenere un poliedro vuoto Si ottiene un nuovo poliedro i+1 contenente tutte le soluzioni a componenti frazionarie tranne quella della formulazione i-esima Si ottiene un nuovo poliedro i+1 contenente tutte le soluzioni a componenti intere in S tranne la soluzione frazionaria della formulazione i-esima. 09-22. Nel metodo dei piani di taglio Se la soluzione ottima della formulazione i-esima ha una o più componenti frazionarie allora il metodo termina Se la soluzione ottima della formulazione i-esima ha una o più componenti frazionarie allora viene invocato l'oracolo di separazione su una qualsiasi soluzione ammissibile della formulazione i-esima Se la soluzione ottima della formulazione i-esima ha una sola componente frazionaria allora il metodo termina Se la soluzione ottima della formulazione i-esima ha una o più componenti frazionarie allora viene invocato l'oracolo di separazione sulla soluzione ottima della formulazione i-esima. 10-22. Nel metodo dei piani di taglio Se la soluzione ottima della formulazione i-esima ha almeno una componente intera allora il metodo termina Se la soluzione ottima della formulazione i-esima ha tutte le componenti intere allora il metodo prosegue Se la soluzione ottima della formulazione i-esima ha tutte le componenti intere allora il metodo termina Se la lista dei sottoproblemi aperta è vuota il metodo termina. 11-22. Dato un problema di PL01 si definisce iperpiano di separazione L'iperpiano restituito da un oracolo di separazione per separare la soluzione ottima dell'i-esima formulazione di una sequenza di Gomory dalle soluzioni inammissibili per il problema di PL01 L'iperpiano restituito da un oracolo di separazione per separare la soluzione ottima dell'i-esima formulazione di una sequenza di Gomory dalle soluzioni intere ammissibili per il problema di PL01 La disequazione che partiziona l'insieme delle soluzioni intere ammissibili per il problema di PL01 La disequazione restituita da un oracolo di separazione per separare la soluzione ottima dell'i-esima formulazione di una sequenza di Gomory dalle soluzioni intere ammissibili per il problema di PL01 . 12-22. In un problema di PL01, l'ipotesi di interezza delle componenti del vettore soluzione consente Di risolvere sempre il problema in maniera euristica Di risolvere sempre il problema in maniera esatta Di rafforzare una disequazione valida per un poliedro contenente tutte e sole le soluzioni ammissibili del problema di PL01 Di eliminare alcuni elementi della sequenza di Gomory. 01-30. Per il problema di partizione in clique dei nodi di un grafo Si adotta sempre un approccio esatto Si adota sempre un approccio euristico Non si conosce un'euristica di soluzione Conosciuamo un'euristica di soluzione. 02-30. Per il problema di partizione in clique dei nodi di un grafo L'euristica di soluzione prevede la determinazione esatta di un cluster di nodi alla volta L'euristica di soluzione prevede la determinazione iterativa di sottoinsiemi di archi L'euristica di soluzione prevede la determinazione esatta di una partizione dei nodi L'euristica di soluzione prevede la determinazione iterativa di due cluster di nodi alla volta. 03-23. Nell'algoritmo euristico per il problema di partizione in clique dei nodi di un grafo All'ultima iterazione non si definiscono nuovi cluster All'ultima iterazione possono essere prodotti 0, 1 o 2 cluster All'ultima iterazione possono essere prodotti 1 o 2 cluster All'ultima iterazione possono essere prodotti 0 o 1 cluster. 04-23. Nell'algoritmo euristico per il problema di partizione in clique dei nodi di un grafo Si può modificare un cluster già formato ma solo aumentandone gli elementi Una volta formato un cluster non può più essere modificato Si può modificare un cluster già formato ma solo diminuendone gli elementi Si può modificare a piacere un cluster già formato. 05-23. L'algoritmo euristico per il problema di partizione in clique dei nodi di un grafo Converge solo alla soluzione esatta Converge in un numero finito di passi che dipende dal parametro di dimensione s Converge in un numero finito di passi che dipende dalla numero degli archi del grafo delle istanze Può non convergere. 01-33 Indicare quali tra i seguenti non è un indice di redditività considerato nel problema di capital budgeting Il grado di maturità tecnologica dell'investimento Il tasso interno di rendimento dell'investimento Il punto di break-even dell'investimento Il valore attuale netto dell'investimento. 02-33 Un problema di capital budgeting è caratterizzato da Tante variabili quanti sono i possibili investimenti nel relativo orizzonte temporale Tante variabili quanti sono i periodi del relativo orizzonte temporale Tante variabili quanti sono i diversi tipi di indici di redditività considerati Nessuna delle opzioni. In un problema di capital budgeting I flussi di cassa compaiono come coefficienti dei vincoli del problema I flussi di cassa compaiono come termini noti dei vincoli del problema I flussi di cassa compaiono come coefficienti della funzione obiettivo del problema Nessuna delle opzioni. In un problema di capital budgeting un sottoinsieme di investimenti si definisce ammissibile per il problema se Per ogni periodo dell’orizzonte temporale l’ammontare dei flussi di cassa degli investimenti nel singolo periodo rispetta il vincolo di budget per quel periodo L’ammontare dei flussi di cassa degli investimenti in tutti i periodi dell'orizzonte temporale rispetta l'ultimo vincolo di budget del problema Per ogni periodo dell’orizzonte temporale l'indice di redditività degli investimenti è maggiore della somma dei flussi di cassa in ciascun periodo dell'orizzonte temporale Nessuna delle opzioni. 05-33 In un problema di capital budgeting Occorre determinare l’insieme di investimenti ammissibile di redditività totale massima Occorre determinare l’insieme di investimenti ammissibile a minimo budget Occorre determinare l’insieme di periodi dell'orizzonte temporale in cui l'indice di redditivà di tutti gli invetimenti sia massimo Occorre determinare l’insieme dei budget che rendono ammissibili tutti gli investimenti nell'orizzonte temporale. Un problema di capital budgeting può essere formulato come problema di Programmazione Lineare {0,1} Programmazione Lineare Programmazione Quadratica Nessuna delle opzioni. In un problema di capital budgeting La formulazione naturale è intersezione delle formulazioni naturali dei singoli problemi di knapsack binario La formulazione naturale è unione delle formulazioni naturali dei singoli problemi di knapsack binario La formulazione naturale è differenza delle formulazioni naturali dei singoli problemi di knapsack binario Nessuna delle opzioni. 08-33 Si definisce cover Un sottoinsieme di indici delle variabili del vincolo di knapsack che violi il vincolo Un sottoinsieme di indici dell'orizzonte temporale per cui il vincolo di knapsack sia violato Un sottoinsieme di indici dell'orizzonte temporale per cui il vincolo di knapsack sia violato dalla soluzione intera Un grafo completo. 09-33 In un problema di knapsack binario con n variabili I l'insieme dei cover e l'insieme delle soluzioni Rappresentano l'insieme delle parti di I Hanno intersezione non nulla Hanno unione vuota Non sono confrontabili. 10-33 Un sottoinsieme T dell'insieme degli indici I delle variabili è soluzione Se e solo se non contiene un cover Se e solo se contiene un cover Se e solo se ha almeno un elemento di un cover Se e solo se intersezione di almeno due cover. 11-33 In un problema di capital budgeting La formulazione cover è intersezione delle formulazioni cover dei singoli problemi di knapsack binario La formulazione cover è intersezione delle formulazioni naturali dei singoli problemi di knapsack binario La formulazione naturale è intersezione delle formulazioni cover dei singoli problemi di knapsack binario Nessuna delle opzioni. 12-33 In un problema di knapsack binario con 5 variabili Possono esserci al più 32 soluzioni Possono esserci al più 16 cover Possono esserci al più 64 soluzioni Possono esserci al più 8 cover . 13-33 In un problema di knapsack binario l'oracolo di separazione per i cover Data una soluzione determina una disequazione cover violata dalla soluzione oppure conclude che la soluzione è ammissibile Data una soluzione determina una disequazione cover rispettata dalla soluzione oppure conclude che la soluzione non è ammissibile Data una soluzione determina una disequazione cover violata dalla soluzione oppure conclude che la soluzione non è ammissibile Non si può applicare a ogni soluzione. 14-33 In un problema di knapsack binario l'oracolo di separazione per i cover Nessuna delle opzioni Sfrutta la rappresentazione implicita della formulazione naturale Tiene conto degli indici di redditività dei possibili investimenti Sfrutta la rappresentazione esplicita della formulazione cover. 15-22 In un problema di knapsack binario, dato un vettore x l'oracolo di separazione per i cover Determina (se esiste) il vettore di incidenza u di un cover violato da una soluzione x Determina (se esiste) il vettore di incidenza u di una soluzione diversa dalla soluzione x Determina (se esiste) il vettore di incidenza u di un non cover violato da una soluzione x Non si può applicare a una qualsiasi soluzione x. 16-33 In un problema di knapsack binario l'oracolo di separazione esatta per i cover Risolve un problema di PL01 e se il valore ottimo della funzione obiettivo è maggiore di -1 allora conclude che la soluzione corrente è non ammissibile e restituisce un cover violato dalla soluzione Risolve un problema di PL01 e se il valore ottimo della funzione obiettivo è maggiore di -1 allora conclude che la soluzione corrente è ottima Risolve un problema di PL01 e se il valore ottimo della funzione obiettivo è maggiore di -1 allora conclude che la soluzione corrente è ammissibile Risolve un problema di PL01 e poi il suo rilassamento. |
Report abuse