Динамическое программирование (задача о загрузке)

| Категория реферата: Рефераты по математике
| Теги реферата: доклад, доклад по обж
| Добавил(а) на сайт: Ignat'ev.

Шаг 2. Выразим xi+1 как функцию xi для гарантии того, что левая часть последнего уравнения является функцией лишь xi. По определению xi-xi+1 представляет собой вес, загруженный на этапе і, т.е. xi-xi+1=wimi или xi+1=xi-wimi. Следовательно, рекуррентное уравнение приобретает следующий вид:

[pic]

2.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. Рекуррентное соотношение имеет следующий вид:

[pic]

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

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

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

[pic]

[pic] - целое.

Сравнение двух формулировок показывает, что представление xj-1 через xj создает более существенные препятствия для вычислений, чем представление zj+1 через zj.

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

Yj