в начале года Т владелец озера уже не будет беспокоиться о последствиях отлова в год Т на последующий размер популяции. Поэтому в начале года Т задача принятия решения упрощается. В качестве этапов мы принимаем годы. На каждом этапе владелец озера принимает решение относительно размера отлова в текущем году. Это количество будем обозначать . Для принятия оптимального решения на этапе / он должен
знать количество особей на начало текущего года - . Другими словами, - состояние популяции на начало этапа /.
Определим функцию /ДЬ,) как максимальную чистую прибьшь, которую можно получить за период Г, Г + 1, Г, имея в начале этапа t состояние .
Рассмотрим теперь три аспекта, упомянутые применительно к данной конкретной задаче.
1.Каково множество допустимых решений на каждом этапе! В каждый год мы не можем вьшовить больше форели, чем есть в озере. Таким образом, для любого состояния / должно выполняться соотноше-ниеО<х, <й,.
2.Какова чистая прибыль, зарабатываемая в год tl Если вылавливается Xf форелей в год, в начале которого форелей было , то чистая прибьшь выражается как v{x)-с(Х/,b),
3.Каково будет состояние к началу t 1-го года! К концу года t в озере будет bf - Х( форелей. К началу следующего года количество форелей
увеличится на 20%, а следовательно, составит 1,2( Ь -х) или
=1,2(6,-X,).
Теперь мы можем воспользоваться общим рекурсивным соотношением (7.1). Поскольку после года Т прибыли уже не рассматриваются, то
fj.(bj) = ma x{r{Xj) - с(Ху., fey,)},
где о< Xf < . Далее на основании соотношения (7.1) получаем соотношение
f,(b,) = max{r(x,)-c{x„b,) + f,,,(l,2(b,-x,))},(7.2)
где 0<х,<Ь,.
Для того чтобы начать вычисления по приведенной схеме, вычислим ff(bf) для всех возможных значений (от О до 10 ООО • (1,2)"). Далее, используя рекурсивное соотношение (7.2), проводим вычисления, пока не получим / (10 ООО), которое будет достигаться при некотором
значении х*. Тогда в начале второго года в озере будет 1,2(10 ООО - х*) форелей. Это означает, что в качестве Х2 можно выбрать любое решение, на котором соотношение (2) достигает значения /2(1,2(10 000-х*)). Продолжая эту процедуру аналогичным образом, можно получить все остальные элементы оптимального решения, а именно Хз,Х4,...,х .
Приведенная модель имеет тот недостаток, что в ней не делается различия между прибылями различных годов. С точки зрения дисконтирования, доходы ранних лет имеют большую ценность, чем последующих. Предположим, что 1 доллар, полученный в начале года / + 1, эквивалентен величине /? < 1, полученной в начале года /. Мы можем учесть эффект дисконтирования, введя коэффициент J3 в рекуррентную формулу (7.2) следующим образом
/(fe,) = max{r(x,)-c(x„ft,) + ;ff/,i(l,2(fe,-x,))},(7.3)
где 0<х,<Ь,.
Пример. Известны прогнозные значения потребления электроэнергии на ближайшие Г лет, а именно г, - прогнозируемая мощность потребления электроэнергии в год /. Каждый год необходимо принимать решение, на сколько нужно увеличить (или уменьшить) мощность выработки электроэнергии. Пусть С/(х) - стоимость увеличения мощности на X кВт ч в году /. Так как мощность может сокращаться, х может быть отрицательной величиной. В течение года 10% ранее выработанной, но не использованной электрической мощности теряется (в первый год потери не происходят). Себестоимость выработки / единиц электрической мощности в год / составляет (/). В начале первого года
уровень вырабатываемой электрической мощности составляет 100 000 кВтч Сформулируйте рекурсивное соотношение для метода динамического программирования, позволяющее компании найти решение, удовлетворяющее потребностям в электроэнергии на ближайшие Т лет с минимальными затратдми.
Решение.
Пусть как и в предыдущем примере годы будут соответствовать этапам алгоритма. В начале каждого года компания принимает решение об изменении производимой мощности на величину . Пусть - мощность, вырабатываемая в начале года, является состоянием системы. Как и в предьщущей задаче, рассмотрим три аспекта применительно к данной конкретной задаче.
1.Каково множество допустимых решений на каждом этапе! Для того, чтобы потребность в электроэнергии бьша бы удовлетворена, необходимо выполнение неравенства >а; , или х, >г, -i,. Это условие и определяет множество допустимых решений на каждом этапе.
2.Каковы затраты в год tl Если - объем наращивания (или сокращения) мощностей в год Г, а ц - мощность на начало года, то затраты выражаются соотношением c{x) + (/, + х,).
3.Каково будет состояние системы к началу t 1-го года! В начале t + 1-го года компания будет располагать 0,9 старых мощностей и х,
новыми, а следовательно, =0,9/,+х,. Теперь мы вновь можем
воспользоваться рекурсивным соотношением (7.1). Определим функцию /Д/) как минимальные затраты на удовлетворение спроса на электроэнергию за годы / + 1, Г при условии, что
мощности на начало года t, составляют fj{ij) = m i n{cJ{xJ) xт
mj{ij -Хр)}, Xj>rj-ij. ]Xnsit<TmAtQu f{d) = 0 для всех
у; (/, ) = min [с, (x,) + m, (/, + x,) + f,, (0, % + x,)},(7.4)
X, >r,
Можно предположить, что мощность не будет превышать max =\ значит, что мы можсм рассмотреть только состоя-
ния о, 1,2, г. Будем использовать соотношение (7.4) для расчетов в обратном направлении до тех пор пока не вычислим /j (100000). Далее мы найдем оптимальные изменения мощностей по годам * ♦ *
1 ,Х2,...,Х2г .