Paniere con risposte chiuse Extra- Ricerca operativa (2022/2023)

Proprietà dei problemi di PL01

è il valore del lower bound09. Data un problema di PL01 con insieme delle soluzioni ammissibili S e vettore dei costi950 Lezione 022 09. CHIUSA elementari cÈ possibile determinare un criterio di preferenza (independente dalla funzione obiettivo) per953 Lezione 022 09. x stabile se una formulazione è migliore di un'altra955 Lezione 022 10. CHIUSA 10. Date due formulazioni lineari P_1 e P_2 di un problema di PL01959 Lezione 022 10. x P_1 è migliore di P_2 se e solo se P_1 U P_2960 Lezione 022 11. CHIUSA 11. Date due formulazioni lineari P_1 e P_2 di un problema di PL01962 Lezione 022 11. x P_1 è migliore di P_2 se e solo se P_1 U P_212. Data un problema di PL01 con insieme delle soluzioni ammissibili S e vettore dei costi965 Lezione 022 12. CHIUSA elementari c968 Lezione 022 12. x Il problema ammette sempre formulazione ottima13. Risolvere un problema di PL01 significa determinare una soluzione ammissibile x* in970 Lezione 022 13. CHIUSA S.{0,1}^n

tale che973 Lezione 022 13. x cTx* < = cTx per ogni x in S975 Lezione 022 14. CHIUSA 14. In generale il processo di formulazione di un problema di PL01979 Lezione 022 14. x Non è univoco15. Dato un problema di PL01 con insieme delle soluzioni ammissibili S, una formulazione980 Lezione 022 15. CHIUSA lineare del problema984 Lezione 022 15. x È tale che l'intersezione di P con l'ipercubo unitario è uguale a S16. Dato un problema di PL01 con insieme delle soluzioni ammissibili S, una formulazione985 Lezione 022 16. CHIUSA lineare del problema986 Lezione 022 16. x È tale che l'intersezione di P con l'ipercubo unitario è uguale a S17. Dato un problema di PL01 con insieme delle soluzioni ammissibili S, una formulazione990 Lezione 022 17. CHIUSA lineare del problema993 Lezione 022 17. x Esiste sempre18. Dato un problema di PL01 con insieme delle soluzioni ammissibili S, una formulazione995 Lezione 022 18. CHIUSA lineare del

problemaConsente sempre di separare i vettori a componenti {0,1} corrispondenti a soluzioni ammissibili

996 Lezione 022 18. x in S dai vettori a componenti {0,1} che non appartengono a S

1000 Lezione 022 19. CHIUSA 19. Dato un limite inferiore LB per un problema di PL01 di minimizzazione

La differenza (gap) tra valore di una soluzione ammissibile e limite inferiore (LB) ci permette di

1003 Lezione 022 19. x capire quanto la soluzione ammissibile sia lontana dalla soluzione ottima

del problema PL01

1005 Lezione 022 20. CHIUSA 20. Dato un limite inferiore LB per un problema di PL01 di minimizzazione

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

1007 Lezione 022 20. X 21. Anche nel caso in cui non si conosca il valore ottimo di un problema (PL01), la conoscenza

1010 Lezione 022 21. CHIUSA del limite inferiore per il problema ci permette di stabilire

1012 Lezione 022 21. x Quanto sia "buona" una qualsiasi soluzione

ammissibile1015 Lezione 022 22. CHIUSA 22. In generale il processo di formulazione di un problema di PL011017 Lezione 022 22. X Non fornisce automaticamente uno strumento di soluzione del problema1020 Lezione 022 23. CHIUSA 23. In generale il processo di formulazione di un problema di PL011022 Lezione 022 23. X Può ammettere più formulazioni per lo stesso problema24. Data una formulazione lineare P di un problema di PL01 con insieme delle soluzioni1025 Lezione 022 24. CHIUSA ammissibili S e vettore dei costi elementari cSe la soluzione ottima del rilassamento lineare ha tutte componenti intere allora è una1026 Lezione 022 24. X soluzione ottima del problema di PL0125. =Determinare un lower bound per un problema di PL01 significa determinare un valore LB1030 Lezione 022 25. CHIUSA tale che1034 Lezione 022 25. X LB <= cTx per ogni x in S1039 Lezione 023 01. CHIUSA 01. Nel metodo branch and boundQuando la soluzione approssimata del sottoproblema corrente è

a componenti intere, l'upper1041 Lezione 023 01. X bound viene aggiornato se il valore della soluzione è minore del precedente1044 Lezione 023 02. CHIUSA 02. Nel metodo branch and boundQuando il valore della soluzione approssimata del sottoproblema corrente è superiore all'upper1045 Lezione 023 02. X bound il problema viene eliminato dalla lista dei sottoproblemi aperti1049 Lezione 023 03. CHIUSA 03. Le possibili strategie di soluzione del metodo branch and bound1052 Lezione 023 03. X Risolvono in maniera approssimata il sottoproblema corrente1054 Lezione 023 04. CHIUSA 04. Il metodo branch and bound1057 Lezione 023 04. X Procede finché la lista dei sottoproblemi aperti è non vuota1059 Lezione 023 05. CHIUSA 05. Nel metodo branch and boundIl sottoproblema corrente viene decomposto quando il valore della soluzione approssimata del1061 Lezione 023 05. X sottoproblema è minore dell'upper bound e la soluzione non è a componenti

intere1064 Lezione 023 06. CHIUSA 06. Nel metodo branch and bound1068 Lezione 023 06. X L'algoritmo si arresta quando la lista dei sottoproblemi aperti è vuota1069 Lezione 023 07. CHIUSA 07. Le possibili strategie di selezione del metodo branch and bound1072 Lezione 023 07. X Determinano come gestire la lista dei sottoproblemi aperti1074 Lezione 023 08. CHIUSA 08. Le possibili strategie di separazione del metodo branch and boundDetermina come partizionare l'insieme delle soluzioni ammissibili in due o più sottoinsiemi1076 Lezione 023 08. X1079 Lezione 023 09. CHIUSA 09. Gli elementi principali del metodo branch and bound sonoDecomposizione ricorsiva del problema corrente e soluzione approssimata dei sottoproblemi1082 Lezione 023 09. X1084 Lezione 023 10. CHIUSA 10. Il metodo branch and boundEsplora in maniera implicita (parziale) l'insieme delle soluzioni ammissibili di un problema di1086 Lezione 023 10. X PL01 e valuta la funzione obiettivo su