26 01 21

Pagina 1

Metodi di ottimizzazione della ricerca operativa Prova d’esame - 26.01.21 Domanda 1. Falso o falso? Le seguenti affermazioni NON sono corrette. Per ciascuna di esse si fornisca il motivo della loro inesattezza. 1. Sia (P) un problema lineare scritto nella forma generale uniforme, se (P) viene scritto nella forma standard allora le colonne associate alle variabili di slack inducono una soluzione di base ammissibile. La soluzione di base associata alle variabili di slack corrisponde all’origine ( xi = 0). Questa soluzione di base non `e ammissibile se l’origine non appartiene al poliedro che definisce la regione ammissibile di (P). 2. Se B1 e B2 sono due basi adiacenti che generano due soluzioni di base ammissibili x1 e x2, allora x1 e x2 sono necessariamente diverse. Se la soluzione di base x1 `e degenere allora due base diverse (adiacenti) potrebbero generare la stesa soluzione. 3. Sia (P) un problema lineare scritto nella forma standard, se il problema ha infinite soluzioni allora l’insieme delle soluzioni contiene una retta. In un poliedro scritto nella forma standard tutte le variabili sono non negative, dunque no pu `o contenere una retta. 4. Nell’ algoritmo di Branch and Bound la soluzione del rilasciamento continuo trovata nel corso di una iterazione `e migliore rispetto a quelle generate in tutte le iterazioni precedenti. Le soluzioni dei rilasciamenti continui non possono migliorare lungo un ramo del albero. 5. Il problema ausiliario nella (FASE I) `e ammissibile se e solamente se il problema originale `e ammissibile. Il problema ausiliario `e ammissibile per costruzione. 6. Nella formulazione lineare del problema di flusso massimo la quantit `a di variabili `e pari alla quantit `a di archi nel digrafo. Le variabili corrispondono al flusso su ogni arco e il valore…