Paniere Ricerca Operativa 2 risposte multiple

Formulazioni lineari e lower bound nel problema di PL01

PL0120. Data un problema di PL01 con insieme delle soluzioni ammissibili S e vettore dei costi elementari c. Ogni formulazione lineare corrisponde a un diverso rilassamento lineare e a un diverso lower bound per il problema.

21. Data un problema di PL01 con insieme delle soluzioni ammissibili S e vettore dei costi elementari c. Una formulazione è tanto migliore quanto più alto è il valore del lower bound.

22. Data un problema di PL01 con insieme delle soluzioni ammissibili S e vettore dei costi elementari c. È possibile determinare un criterio di preferenza (indipendente dalla funzione obiettivo) per stabilire se una formulazione è migliore di un'altra.

23. Date due formulazioni lineari P1 e P2 di un problema di PL01. P1 è migliore di P2 se e solo se P1⊂P2.

24. Date due formulazioni lineari P1 e P2 di un problema di PL01⊂P2. P1 è migliore di P2 se e solo se P1⊂P2.

25. Data un problema di PL01 con insieme delle soluzioni ammissibili S e vettore dei costi elementari c.

1. costi elementari
2. Il problema ammette sempre formulazione ottima
3. Lezione 0130
4. Le possibili strategie di soluzione del metodo branch and bound
5. Risolvono in maniera approssimata il sottoproblema corrente
6. Le possibili strategie di selezione del metodo branch and bound
7. Determinano come gestire la lista dei sottoproblemi aperti
8. Nel metodo branch and bound
9. Procede finché la lista dei sottoproblemi aperti è vuota
10. Il metodo branch and bound
11. È un metodo euristico di soluzione per problemi di PL01
12. Il metodo branch and bound
13. 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
14. Gli elementi principali del metodo branch and bound sono
15. Decomposizione ricorsiva del problema corrente e soluzione approssimata dei sottoproblemi
16. Le possibili strategie di separazione del metodo branch and bound
17. Determina come partizionare l'insieme

delle soluzioni ammissibili in due o più sottoinsiemi. Nel metodo branch and bound, l'algoritmo si arresta quando la lista dei sottoproblemi aperti è vuota. Nel metodo branch and bound, quando il valore della soluzione approssimata del sottoproblema corrente è superiore all'upper bound, il problema viene eliminato dalla lista dei sottoproblemi aperti. Nel metodo branch and bound, quando la soluzione approssimata del sottoproblema corrente è a componenti intere, l'upper bound viene aggiornato se il valore della soluzione è minore del precedente. Nel metodo branch and 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. Lezione 014 01. Applicando il metodo branch and bound al seguente problema di PL, l'algoritmo si arresta alla prima iterazione restituendo una soluzione ottima di valore 30.

Consideri il seguente problema di PL01 in cinque variabili decisionali e un vincolo di disuguaglianza, l'ordinamento degli indici delle variabili in ordine crescente di rapporto costo/ingombro è {5,1,2,4,3}.

Un problema di knapsack binario con 5 variabili di decisione ammette al più 32 soluzioni ammissibili.

Applicando il metodo branch and bound al seguente problema di PL01, alla prima iterazione non è disponibile un upper bound.

Applicando il metodo branch and bound al seguente problema di PL01, all'ultima iterazione il lower bound e l'upper bound hanno valore uguale a 307.

Un problema di knapsack binario con 4 variabili di decisione ammette al più 16 soluzioni ammissibili.

Applicando il metodo branch and bound al seguente problema di PL01...

problema di knapsack binario

Al termine della seconda iterazione il numero di problemi aperti nella lista è 209. 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?

210. 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?

Lezione 01601. Nel clustering le regole sono

1. I criteri algoritmicamente indotti analizzando i dati che permettono di classificare le osservazioni in gruppi omogenei
2. Dire quali tra le seguenti applicazioni non si risolve tramite tecniche di clustering Pattern recognition
3. Un cluster è un gruppo di oggetti simili in base a un qualche criterio di omogeneità
4. L'apprendimento automatico è un qualsiasi processo induttivo umano
5. Una distanza d

È una relazione a valori non negativi che gode della proprietà di simmetria e che assume valore nullo in corrispondenza di due punti uguali.

Una semimetrica è una distanza che gode della proprietà di soddisfare le diseguaglianze triangolari.

Una metrica è una semimetrica che assume valore nullo solo in corrispondenza di due punti uguali.

Una metrica norma è una metrica.

La metrica norma l2 è la distanza Euclidea.

La metrica norma l1 è la distanza di Manhattan.

La metrica norma l0 è la distanza di Hamming.

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 è minore della distanza tra un qualsiasi punto del cluster e un punto esterno al cluster.

Lezione 01701. Un algoritmo di clustering partizionale raggruppa le osservazioni del training set in cluster sulla base di una misura di similarità.

definitasull'insieme delle coppie di osservazioni02. Nella metodologia generale di clustering l'astrazione sui dati èLa definizione di opportuni rappresentanti dei cluster determinati dall'algoritmo di soluzione03. Nella metodologia generale di clusteringPrima si definisce la misura di similarità e poi l'algoritmo di soluzioneLezione 01801. Si definisce partizione P dell'insieme X una famiglia finita di k insiemiNon vuoti e tali che la loro unione sia pari a X e a due a due disgiunti02. Si definisce partizione P dell'insieme X una famiglia finita di k insiemiNon vuoti e tali che la loro unione sia pari a X e a due a due disgiunti03. Il vettore di incidenza di un insieme paritizione èUn vettore a m componenti {0,1} con m numero degli archi del grafo delle istanze04. 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}

Il vettore di incidenza di un insieme multi-taglio è un vettore a m componenti {0,1} con m numero degli archi del grafo delle istanze

L'insieme partizione E(V) di un sottoinsieme V di nodi non vuoto è l'insieme degli archi che connettono nodi di V

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 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 partizione del grafo nei sottoinsiemi V1,...,Vk non vuoti e disgiunti è l'insieme degli nodi appartenenti a due sottoinsiemi distinti in {V1,...,Vk}

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=δ(P(G)) e W_2=E(P(G))

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 e nodi di W

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=δ(P(G)) e W_2=E(P(G))

In un problema di clustering partizionale con vincoli di dimensione, il numero dei vincoli di dimensione è pari al numero dei nodi del grafo delle istanze

In un problema di clustering partizionale un vincolo di dimensione è un vincolo logico che rende ammissibili solo soluzioni in cui ogni cluster abbia almeno un certo numero s di elementi

Un problema di clustering partizionale di n istanze con parametro di dimensione s minore o uguale di 1 è un problema di partizione in clique dei nodi di

un grafo16. 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

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 in k sottoinsiemi con k = n / s

18. 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 e nodi di W

19. L'insieme di taglio di un sottoinsieme V di nodi non vuoto è l'insieme degli archi che connettono nodi di V con nodi non appartenenti a V

20. Un problema di clustering partizionale di n istanze con parametro di dimensione s con n multiplo di s è un problema di equipartizione in k sottoinsiemi con k = n / s

21. La stella di un nodo è un caso particolare di insieme di taglio

22. Si definisce partizione P

dell'insieme X una famiglia finita di k insiemi non vuoti e tali che la loro unione sia pari a X e a due a due disgiunti

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}
• V2={2,3}
• V3={7}
• V4={5,4}

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={b,e}
• V2={f,c,d}
• V3={a}

25. In un problema di clustering partizionale il grafo delle istanze ha il massimo numero di archi orientati

26. In un problema di clustering partizionale il grafo delle istanze ha il massimo numero di archi orientati

27. Sia N={1,2,3,4,5,6}. Il grafo delle istanze G(N,A) ha un numero di archi pari a 15

28. Sia N={a,b,c,d,e,f}. Il grafo delle istanze G(N,A) ha un numero di archi pari a 15