img377 (3)

w zależności od tego, w którym z miast w etapie 4 zatrzymano się na postój.

Krok. 2. Cofnijmy się o jeden etap. Odległość miast w etapie 3 od celu wynosi:

d_A1 + d-j g == 200 + 120 = 320, g + d₈ 9 ⁼ 250 + 130 = 380.

Tak więc z miasta 4 do 9 należy wybrać drogę d₄ 7 9 = 320.

Podobnie:

^5? + d-j^ = 200 + 120 = 320, d₅'₈ + d₈₉ = 180 + 130 = 310.

a więc z miasta 5 do 9 należy wybrać drogę <7_5>8,₉ = 310,

Następnie:

d₆17 + d_1<9 = 150 + 120 = 270, d₆, ₈ + d_s<9 = 110 + 130 = 240,

a więc z miasta 6 do 9 należy wybrać drogę d₆ 8 9 = 240.

Krok 3. Powtórzmy cale postępowanie biorąc za punkt wyjścia etap 2:

d_2A + <9 = 150 + 320 = 470, d₂, 5 + ^ds,9 = 80 + 310 = 390, di,e +    9 = 120 + 240 = 360,

a więc z miasta 2 do 9 należy wybrać drogę:

2-6-8-9

krok 2

o długości 360 km.

Podobnie

(/₃₄ + (/₄»= 150 + 320 = 470, d₃₅ + d₅ 9 = 130 + 310 = 440. d₃,6 + d_6i9 = 190 + 240 = 430,

a więc z miasta 3 do 9 należy wybrać drogę:

3 — 6 — 8 — 9

krok 2

o długości 430 km

Krok 4. Dotarliśmy do punktu startowego, w którym rozpatrujemy sposób dotarcia do celu z miasta 1 przez miasta 2 lub 3:

di,2 4" ^2,9 — 100 + 360 — 460, ^1,3 "4 ^3,9 ⁼    4 430 = 510,

a więc z miasta 1 do 9 należy wybrać drogę:

1-2-6-8-9

krok 3

o długości 460 km.

Pytania i problemy

1.    Podać sposób poszukiwania najkrótszej drogi w sieci przy zastosowaniu algorytmu znanego z rozwiązania problemu dyliżansu.

2.    Który z algorytmów z zakresu programowania dynamicznego należy zastosować w przypadku wyboru wariantu inwestycyjnego?

3.    W jaki sposób można rozwiązać problem alokacji środków przyznanych na reklamę

stosując zasady programowania dynamicznego?

4.    Podać podstawowe założenia zagadnienia znanego jako „problem dyliżansu”.

5.    Wymienić założenia przyjmowane przy rozwiązywaniu typowych zagadnień z zakresu programowania dynamicznego.

Zadania

Firma Aspolen zamierza prowadzić reklamę swego nowego wyrobu w lokalnym programie telewizyjnym Kronika TV (KTV), w „Gazecie Wyborczej” (GW) oraz w radiu RMF. Na reklamę postanowiono przeznaczyć 7 min zł. Dokonać podziału tej kwoty pomiędzy wspomniane kanały reklamowe, kierując się skutecznością reklamy, mierzoną przyrostem sprzedaży wyrobów (tabl. 184).

Tablica 184

Nakłady (w min zł)		0	1	2	3	4	5	6	7
Przyrost sprzedaży wyrobów	KTV	0	100	150	200	250	300	350	400
	GW	0	200	200	200	200	200	200	500
(w szt.) w przypadku reklamy w:	RMF	0	100	100	300	400	500	500	550

211