4.2 Рекуррентные соотношения для процедур прямой и обратной прогонки.

Фермеру принадлежит стадо овец, насчитывающее k голов. Один раз в год фермер принимает решение о том, сколько овец продать и сколько оставить. Прибыль от продажи одной овцы в і-м году составляет pi. Количество оставленных в i-м году овец удваивается в (1+1)-м году. По истечении п лет фермер намеревается продать все стадо.

Этот чрезвычайно простой пример приводится для того, чтобы наглядно продемонстрировать преимущества алгоритма обратной прогонки по сравнению с алгоритмом прямой прогонки. Вычислительные схемы процедур прямой и обратной прогонки обладают различной эффективностью в случаях, когда этапы модели нумеруются в некотором специальном порядке. Такая ситуация имеет место в приводимом примере, где этап j ставится в соответствие году j, т. е. этапы должны рассматриваться в хронологическом порядке.

Сначала построим рекуррентные соотношения для процедур прямой и обратной прогонки, а затем проведем сравнение двух вычислительных схем. Важное различие между двумя формулировками непосредственно следует из определения состояния.

Обозначим количества оставленных и проданных в j-м году овец через xj и yj, соответственно. Положим Zj,=xj+yj. Из условий задачи следует, что

z1=2x0=2k, zj=2xj-1,j=l,2, ...,n. Состояние на этапе j можно описать с помощью переменной zj, которая выражает количество имеющихся к концу этапа j овец для распределения на этапах j+1, j+2, ..., n, или с помощью переменной xj, которая выражает количество имеющихся к началу этапа j+1 овец, обусловленное принятыми на этапах 1,2,...,j решениями. Первое определение ориентировано на построение рекуррентного соотношения для процедуры обратной прогонки, тогда как второе определение приводит к использованию алгоритма прямой прогонки.

Алгоритм обратной прогонки

Обозначим через fi(zi) максимальную прибыль, получаемую на этапах j,j+1,…,n, при заданном zj. Рекуррентное соотношение имеет следующий вид:

Заметим, что yj и zj - неотрицательные целые числа. Кроме того, уj (количество овец, проданных в конце периода j) должно быть меньше или равно zj. Верхней границей для значений zj, является величина 2jk (где k- исходный размер стада), которая соответствует отсутствию продажи.

Алгоритм прямой прогонки

Обозначим через gj(xj) максимальную прибыль, получаемую на этапах 1,2,...,j при заданном xj, (где xj— размер стада к началу этапа J+1). Рекуррентное соотношение записывается в следующем виде:

- целое.

Сравнение двух формулировок показывает, что представление xj-1 через xj создает более существенные препятствия для вычислений, чем представление zj+1 через zj. В замене xj-1=(xj+yj)/2 подразумевается целочисленность правой части, тогда как на равенство zj+1=2(zj-yj) такое требование не накладывается. Таким образом в случае процедуры прямой прогонки значения yj и xj, связанные неравенством

Yj <=2jk -Xj,

должны дополнительно удовлетворять условию целочисленности их полусуммы, связанному с видом зависимости хj-1 от xj,. Рассмотренный пример иллюстрирует трудности вычислительного характера, которые обычно возникают при использовании алгоритма прямой прогонки.