23 01 19ts

Page 1

Metodi di ottimizzazione della ricerca operativa Prova d’esame ‐ 23.01.19 1 Domanda 1 (punti 4) Si consideri il seguente problema di ottimizzazione lineare in forma standard: P ) Quesito 1 (vedi teoria) Data la matrice di base B (nota), si ricavino per via algebrica le condizioni di ottimalità per la relativa soluzione di base ammissibile  ,BDxx x . Per ritenersi completa la risposta deve contenere tutti i passaggi algebrici a partire dal sistema di vincoli di P scritto in forma canonica. Quesito 2 (vedi teoria) Sia B la base ottimale per P. Si supponga di imporre una variazione al vettore dei coefficienti nella forma '  cc d . Si d e s c r i v a p e r v i a a l g e b r i c a c o m e p u ò e s s e r e r i c a v a t o l ’ i n t e r v a l lo di sensitività MIN MAX  affinché B continui ad essere ottimale. Domanda 2 (punti 4) Per ogni affermazione si indichi se è vera o falsa: a) Il valore ottimo di un problema intero è minore o uguale al valore ottimo del suo □ vero  falso rilasciamento continuo b) L’algoritmo di branch and bound, a differenza del metodo dei piani di taglio, è esatto □ vero  falso c) Il fenomeno del ciclaggio nel metodo dei piani di taglio si verifica quando, all’iterazione □ vero  falso successiva, l’algoritmo visita di nuovo la stessa soluzione di base d) Il metodo dei piani di taglio si arresta alla prima soluzione intera generata  vero □ falso e) Il metodo di branch and bound si arresta quando viene generata la migliore soluzione □ vero  falso ammissibile intera f) Si può generare un taglio valido per ogni variabile frazionaria nella soluzione ottimale del  vero □ falso rilasciamento continuo g) I tagli validi eliminano dalla regione ammissibile di un problema intero sotto‐regioni  vero □ falso che contengono solo soluzioni…