4736387705

3. Firma wysłała kierowcę, który powinien przewieźć towar do magazynu oddalonego o 5 723 km. od siedziby firmy. Ze względów bezpieczeństwa kierowca nie może przejechać więcej niż 750 km. dziennie. Firma chce zarezerwować noclegi dla kierowcy w zaprzyjaźnionych motelach znajdujących się na jego trasie. Moteli tych jest 20: Mi,..., M20■ Znane są oczywiście odległości między motelami:

M0,i	M2,3	M4,5	Me,7	Mgtg	Mio,n	Mi2,l3	Mi4,15	M 16,17	Mis,19
282	341	205	403	298	179	296	369	224	198
Mi,2	M3,4	M5,6	M7,s	Mg, 10	Mn,12	Mi3,i4	Mi5,i6	Mi7,18	Mi9,20
382	243	405	213	258	187	392	267	124	298

gdzie Mij oznacza odległość między motelami Mi oraz Mj oraz Mq oznacza firmę, z której startuje kierowca. Firma chce zarezerwować jak najmniejszą liczbę noclegów. W których motelach powinien nocować kierowca?

(a)    Opracować metodę zachłanną, która rozwiąże ten problem.

(b)    Czy ta metoda w naszej sytuacji daje optymalne rozwiązanie problemu? Odpowiedź uzasadnić.

(c)    Czy ta metoda daje optymalne rozwiązanie dla dowolnego innego zestawu danych? (Zakładamy, że kierowca ma do przejechania n km., nie może dziennie pokonać dłuższej drogi niż m km., są podane odległości < m pomiędzy miejscami, w których możliwy jest nocleg.)

4. Kierowca musi przejechać 6 835 km. Nie może jednak przejechać więcej niż 650 km. na jednym baku. Na trasie kierowca ma 20 ulubionych stacji benzynowych: Si,..., S20■ Zna on odległości między stacjami:

50,i	52,3	S4,5	56,7	58,9	5io.n	5l2.13	5i4,15	5i6.17	5i8,19
332	391	255	454	347	225	343	419	274	245
01,2	53,4	55,6	*7,8	59,10	5n,l2	5i3.14	5l5,16	5i7.18	5l9,20
431	292	451	263	300	237	500	317	177	350

gdzie Sij oznacza odległość między stacjami Si oraz Sj, ponadto So oznacza punkt, z którego startuje kierowca. Kierowca chce tankować jak najmniejszą liczbę razy. Na których stacjach powinien on tankować.

(a)    Opracować metodę zachłanną, która rozwiąże ten problem.

(b)    Czy ta metoda w naszej sytuacji daje optymalne rozwiązanie problemu? Odpowiedź uzasadnić.

(c)    Czy ta metoda daje optymalne rozwiązanie dla dowolnego innego zestawu danych?