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

Обозначим через 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,. Рассмотренный пример иллюстрирует трудности вычислительного характера, которые обычно возникают при использовании алгоритма прямой прогонки.

Дата добавления: 2014-01-15