15 07 19testo e sol

Page 1

Metodi di ottimizzazione della ricerca operativa Prova d’esame - 15.07.19 Cognome Nome Matricola 1 Metodi di ottimizzazione della ricerca operativa Prova d’esame - 15.07.19 Domanda 1.In un certo territorio una azienda deve rifornire ndestinazioni, ad ogni destinazione`ea s s o c i a t au n a domandadj. La azienda decide di creare due nuove unit`a produttive nel territorio che possono essere assegnate inm potenziali siti candidati. Ogni potenziale unit`a produttiva ha un costo fisso di attivazione pari afie una disponibilit`a massima diai. Il costo unitario di trasporto dall’origine ialla destinazionej`ep a r iacij. Si formuli il problema che permette di decidere quali unit `a devono essere attivate in modo di soddisfare la domanda delle destinazioni minimizzando il costo totale. Variabili di decisione: xij:q u a n t i t`a di prodotto inviato dal origine ialla destinazionej. yi= I 1se il candidatoiviene creato 0altrimenti Formulazione: min mÿ i=1 nÿ j=1 cijxij+ mÿ i=1 fiyi s.a. mÿ i=1 yi=2 nÿ j=1 xijÆaiyi ’i=1,...,m mÿ i=1 xijØdj ’j=1,...,n xijØ0 ’i=1, . . . , m, j=1,...,n yiœ{0,1}’i=1,...,m Domanda 2.SianoPeDuna coppia di problemi primale e duale. Per ogni a ermazione si indichi se `ev e r aof a l s a e si motivi la risposta. Risposte senza motivazione non saranno considerate. a)SeP`ei n a m m i s s i b i l e ,Dnon pu`o essere illimitato. ⇤V⌅F ⇤non si pu`od i r e Perch´e?:Dpu`oe s s e r ei n a m m i s s i b i l eoi l l i m i t a t o b)SeDammette soluzione ottimale,Pnon pu`o essere illimitato. ⌅V⇤F ⇤non si pu`od i r e Perch´e?:Per il teorema di dualit`af o r t ePha una soluzione ottimale (con lo steso valore del problema D) c)Se D`e illimitato, P pu`o ammettere soluzioni ammissibili. ⇤V⌅F ⇤non si pu`od i r e Perch´e?:Questo`e in contraddizione con il teorema di dualit`a…