Paniere Ricerca operativa

T T

c x*< c x per ogni x in S

T T

c x* ≤ c x per ogni x in S

T T n

c x* ≤ c x per ogni x in {0,1}

14. In generale il processo di formulazione di un problema di PL01

Produce sempre una formulazione a componenti non negative

Determina sempre la formulazione ottima del problema

Produce sempre una formulazione con un numero finito di soluzioni ammissibili

Non è univoco

15. Dato un problema di PL01 con insieme delle soluzioni ammissibili S, una formulazione lineare del problema

È tale che l'intersezione di P con l'insieme dei numeri naturali è uguale a S

È tale che l'intersezione di P con S è l'ipercubo unitario

Può contenere un numero infinito di soluzioni a componenti intere

È tale che l'intersezione di P con l'ipercubo unitario è uguale a S

16. Dato un problema di PL01 con insieme delle soluzioni ammissibili S, una formulazione lineare del problema

È tale che l'intersezione di P con l'ipercubo unitario è uguale a S

È tale che l'unione di P con l'ipercubo unitario è uguale a S

È tale che l'unione di S con l'ipercubo unitario è uguale a P

È tale che l'intersezione di S con l'ipercubo unitario è uguale a P

17. Dato un problema di PL01 con insieme delle soluzioni ammissibili S, una formulazione lineare del problema

Può non esistere

Esiste solo se il problema ammette un numero finito di soluzioni ammissibili

Esiste sempre

Esiste solo se il problema è di minimizzazione

18. 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

19. Dato un limite inferiore LB per un problema di PL01 di minimizzazione

La somma del valore di una soluzione ammissibile e del limite inferiore (LB) ci permette di capire quanto la soluzione ammissibile sia lontana dalla soluzione ottima del

problema PL01

La differenza (gap) tra valore di una soluzione ammissibile e limite superiore (UB) ci permette di capire quanto la soluzione ammissibile sia lontana dalla soluzione ottima

del problema PL01

La differenza (gap) tra valore di una soluzione ammissibile e limite inferiore (LB) ci permette di capire quanto la soluzione ammissibile sia lontana dalla soluzione ottima

del problema PL01

La differenza (gap) tra valore di una soluzione ammissibile e limite superiore (UB) ci permette di capire quanto la soluzione ammissibile sia vicina alla soluzione ottima del

problema PL01

20. Dato un limite inferiore LB per un problema di PL01 di minimizzazione

Tanto più LB è alto meglio è

Tanto più il valore di una soluzione ammissibile è vicino a LB, tanto migliore è la soluzione

Tanto più LB è intero meglio è

Tanto più il valore di una soluzione ammissibile è lontano da LB, tanto migliore è la soluzione

21. Anche nel caso in cui non si conosca il valore ottimo di un problema (PL01), la conoscenza del limite inferiore per il problema ci permette di stabilire

Se una soluzione sia a componenti intere oppure no

Quanto sia "buona" una qualsiasi soluzione ammissibile

Quanto sia intera una qualsiasi soluzione ammissibile

Se una soluzione sia ammissibile o meno per il problema

22. In generale il processo di formulazione di un problema di PL01

Produce sempre una formulazione con sole soluzioni ammissibili con componenti intere

Produce sempre una formulazione con un numero finito di soluzioni ammissibili

23. In generale il processo di formulazione di un problema di PL01

Produce sempre una formulazione con sole soluzioni ammissibili con componenti intere

Può ammettere più formulazioni per lo stesso problema

Fornisce automaticamente un potente strumento esatto di soluzione

Determina sempre la formulazione ottima del problema

24. 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 frazionarie tranne una allora è una soluzione ottima del problema di PL01

La soluzione ottima del rilassamento lineare non può mai essere a componenti intere

Se la soluzione ottima del rilassamento lineare ha tutte componenti non negative allora è una soluzione ottima del problema di PL01

25. ≤Determinare un lower bound per un problema di PL01 significa determinare un valore LB tale che

T

LB ≥ c x per ogni x in S

T

LB ≥ c x* per x* ottima in S

T

LB ≤ c x* per x* ottima in S

T

LB ≤ c x per ogni x in S

26. Dare la definizione di lower bound di un problema di PL01

27. Definire un criterio di ordinamento delle formulazioni di un problema di PL01

28. Dare la definizione di formulazione ottima di un problema di PL01

29. Dare la definizione di formulazione lineare di un problema di PL01

Lezione 023

01. Nel metodo branch and bound

Quando la soluzione approssimata del sottoproblema corrente è a componenti intere, il problema viene decomposto

Quando la soluzione approssimata del sottoproblema corrente è a componenti intere, l'upper bound viene aggiornato se il valore della soluzione è non superiore del

precedente

02. 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 ma

non chiuso (potrebbe ancora contenere una soluzione ottima)

Quando il valore della soluzione approssimata del sottoproblema corrente è inferiore all'upper bound il problema viene eliminato dalla lista dei sottoproblemi aperti

Quando il valore della soluzione approssimata del sottoproblema corrente è inferiore all'upper bound allora il problema viene chiuso

03. Le possibili strategie di soluzione del metodo branch and bound

Risolvono in maniera esatta il sottoproblema corrente

Risolvono in maniera approssimata due sottoproblemi alla volta

04. Il metodo branch and bound

Procede finché la lista dei sottoproblemi aperti è vuota

05. Nel metodo branch and bound

Il sottoproblema corrente viene decomposto quando il valore della soluzione approssimata del sottoproblema è minore dell'upper bound

Il sottoproblema corrente viene decomposto quando il valore della soluzione approssimata del sottoproblema è minore dell'upper bound e la soluzione non è a componenti

intere

Il sottoproblema corrente viene decompostoin base alla strategia di soluzione dei sottoproblemi

Il sottoproblema corrente viene decomposto quando la soluzione approssimata del sottoproblema corrente non è a componenti intere

06. Nel metodo branch and bound

L'algoritmo si arresta quando viene trovato un sottoproblema vuoto

L'algoritmo si arresta quando la lista dei sottoproblemi chiusi è vuota

07. Le possibili strategie di selezione del metodo branch and bound

Determinano come gestire la lista dei sottoproblemi generati dall'inizio del metodo all'iterazione corrente

Selezionano quali sono le soluzioni migliori dei sottoproblemi chiusi

Determinano come gestire la lista dei sottoproblemi aperti

Determinano come gestire le soluzioni ottime dei sottoproblemi ancora aperti

08. Le possibili strategie di separazione del metodo branch and bound

Determina quali dei sottoproblemi aperti sono vuoti

Determina come partizionare l'insieme delle soluzioni ammissibili in due sottoinsiemi

09. Gli elementi principali del metodo branch and bound sono

Impiego di tecniche di euristiche di soluzione

Decomposizione una tantum del problema originale

10. Il metodo branch and bound

ammissibili

Esplora in maniera esplicita (completa) l'insieme delle soluzioni ammissibili di un problema di PL01 ma lo fa in maniera rapida

Esplora parte delle soluzioni ammissibili di un problema di PL01 quindi non può certificare l'ottimalità della soluzione ammissibile restituita

11. Il metodo branch and bound

Si applica solo a problemi di minimizzazione

È un metodo euristico di soluzione per problemi di PL

È un metodo euristico di soluzione per problemi di PL01

12. Descrivere la metodologia branch and bound per la soluzione di un problema di PL01

13. Descrivere le possibili strategie di soluzione per il metodo branch and bound per la soluzione di un problema di PL01

14. Descrivere le possibili strategie di separazione per il metodo branch and bound per la soluzione di un problema di PL01

Lezione 024

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

All'ultima iterazione il lower bound è minore dell'upper bound

All'ultima iterazione non è disponibile un upper bound

02. Si consideri il seguente problema di knapsack binario

Qual è il minimo valore non nullo del parametro k tale che il metodo branch and bound converga alla soluzione ottima alla prima iterazione?

2

1

Nessuna delle opzioni

3

03. Applicando il metodo branch and bound al seguente problema di knapsack binario

Nessuna delle opzioni

Al termine della seconda iterazione il numero di problemi aperti nella lista è 4

Al termine della prima iterazione il numero di problemi aperti nella lista è 3

04. Un problema di knapsack binario con 4 variabili di decisione 2^4, perché ammette solo due possibili soluzioni (0,1).

Ammette al più 32 soluzioni ammissibili

Nessuna delle opzioni

Ammette al più 16 soluzioni ammissibili

Si può risolvere solamente con il metodo del branch and bound

05. Un problema di knapsack binario con 5 variabili di decisione

Ammette al più 32 soluzioni ammissibili

Ammette al più 16 soluzioni ammissibili

Si può risolvere solamente con il metodo del branch and bound

Nessuna delle opzioni

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

8

3

Nessuna delle opzioni

2

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

Alla prima iterazione non è disponibile un upper bound

Alla prima iterazione il lower bound è maggiore dell'upper bound

Alla prima iterazione il lower