Динамическое программирование (задача о загрузке) (стр. 3 из 4)
Максимизировать z=r1m1+r2m2+…+rnmn.
при условии, что
w1m1+w2m2+…+wnmn
W,m1,m2,…,mn
0 и целые.Три элемента модели динамического программирования определяются следующим образом:
1. Этап і ставится в соответствии предмету і-го наименования, і=1,2,…n.
2. Варианты решения на этапе і описываются количеством mi предметов і-го наименования, подлежащих загрузке. Соответствующая прибыль равна rimi. Значение mi заключено в пределах от 0 до [W/wi], где [W/wi] – целая часть числа W/wi.
3. Состояние xi на этапе і выражает суммарный вес предметов, решения о погрузке которых приняты на этапах і,і+1,...n. Это определение отражает тот факт, что ограничения по весу является единственным, которое связывает n этапов вместе.
Пусть fi(xi)-максимальная суммарная прибыль от этапов і,і+1,...,n при заданном состоянии xi. Проще всего рекуррентное уравнение определяется с помощью следующей двухшаговой процедуры.
Шаг 1. Выразим fi(xi) как функцию fi+1(xi+1) в виде
где fn+1(xn+1)=0.
Шаг 2. Выразим xi+1 как функцию xi для гарантии того, что левая часть последнего уравнения является функцией лишь xi. По определению xi-xi+1 представляет собой вес, загруженный на этапе і, т.е. xi-xi+1=wimi или xi+1=xi-wimi. Следовательно, рекуррентное уравнение приобретает следующий вид:
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. Рекуррентное соотношение имеет следующий вид:
Заметим, что 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,. Рассмотренный пример иллюстрирует трудности вычислительного характера, которые обычно возникают при использовании алгоритма прямой прогонки.
2.3 Решение задачи о загрузке
Контрольная работа содержит вопросы по N различным темам. Каждый вопрос типа i имеет вес Vi(i=1,2,…N), а также время, отводимое на ответ Wi. Максимально время, которое может затратить студент на контрольную работу W. Требуется определить максимальное количество баллов (вес), которое может набрать студент за отведенное время W=30. Данные приведены в таблице:
| I | Wi | Vi |
| 1 52 63 44 356 67 58 7 | 23147532 | 23246542 |
Решить задачу, приведя ее к рекуррентным соотношениям.
Сначала рассмотрим задачу в общей постановке. Если обозначить количество вопросов типа і через ki, то задача принимает следующий вид:
при ограничениях
ki-неотрицательные числа.
Если отбросить требования целочисленности ki, то решение задачи нетрудно найти с помощью симплекс-метода (см. Приложение В). В самом деле, так как остается лишь одно ограничение, базисной будет только одна переменная, и задача сводится к выбору типа і, для которого величина viW/wi принимает максимальное значение. Исходная задача не является задачей линейного программирования, и для ее решения необходимо использовать метод динамического программирования. Следует отметить, что рассматриваемая задача может быть также решена с помощью методов целочисленного программирования.
Каждый из трех основных элементов модели ДП определяется следующим образом.
1. Этап j ставится в соответствии типу j, j=1,2,…,N.
2. Состояние yj на этапе j выражает суммарный вес вопросов, количество ответов на которые приняты на этапах j,j+1,…,N; при этом y1=W и yj=0,1,…,W при j=2,3,…,N.
3. Варианты решения kj на этапе j описываются количеством вопросов типа j. Значение kj заключено в пределах от нуля до [W/wj], где [W/wj]-целая часть числа (W/wj).
Пусть fi(yi)-максимальный суммарный вес вопросов, ответы на которые приняты на этапах j,j+1,…,N при заданном состоянии yj.
Рекуррентное соотношение (для процедуры обратной прогонки) имеет следующий вид:
Заметим, что максимальное допустимое значение kj ограничено величиной [yj/wj]. Это позволяет автоматически исключать все не являющиеся допустимыми варианты при заданном значении переменной состояния yj.
Решение исходной задачи (см. приложении А):
Этап 8.
Этап 7.
Этап 6.
Этап 5.
Этап 4.
Этап 3.
