Динамическое программирование (задача о загрузке)
(xn+1)=0.
Шаг 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 <=2jk -Xj,
должны дополнительно удовлетворять условию целочисленности их полусуммы,
связанному с видом зависимости хj-1 от xj,. Рассмотренный пример
иллюстрирует трудности вычислительного характера, которые обычно возникают
при использовании алгоритма прямой прогонки.
2.3 Решение задачи о загрузке
Контрольная работа содержит вопросы по N различным темам. Каждый вопрос
типа i имеет вес Vi(i=1,2,…N), а также время, отводимое на ответ Wi.
Максимально время, которое может затратить студент на контрольную работу W.
Требуется определить максимальное количество баллов (вес), которое может
набрать студент за отведенное время W=30. Данные приведены в таблице:
|I |Wi |Vi |
|1 [pic] 5 |2 |2 |
|2 [pic] 6 |3 |3 |
|3 [pic] 4 |1 |2 |
|4 [pic] 3 |4 |4 |
|5 |7 |6 |
|6 [pic] 6 |5 |5 |
|7 [pic] 5 |3 |4 |
|8 [pic] 7 |2 |2 |
Решить задачу, приведя ее к рекуррентным соотношениям.
Сначала рассмотрим задачу в общей постановке. Если обозначить
количество вопросов типа і через ki, то задача принимает следующий вид:
[pic]
при ограничениях
[pic]
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.
Рекуррентное соотношение (для процедуры обратной прогонки) имеет
следующий вид:
[pic]
[pic]
Заметим, что максимальное допустимое значение kj ограничено величиной
[yj/wj]. Это позволяет автоматически исключать все не являющиеся
допустимыми варианты при заданном значении переменной состояния yj.
Решение исходной задачи (см. приложении А):
Этап 8.
[pic]
Этап 7.
[pic]
Этап 6.
[pic]
Этап 5.
[pic]
Этап 4.
[pic]
Этап 3.
[pic]
Этап 2.
[pic]
Этап 1.
[pic]
Оптимальное решение определяется теперь следующим образом. Из условия
W=30 следует, что первый этап решения задачи при y1=30 дает оптимальное
решение k1=0, которое означает, что на 0 (нуль) вопросов 1-го типа будут
даны ответы. Далее находим:
|y1=30 |k1=0 |
|y2=y1-2*k1=30 |k2=0 |
|y3=y2-4*k2=30 |k3=4 |
|y4=y3-k3=26 |k4=1 |
|y5=y4-4*k4=22 |k5=0 |
|y6=y5-7*k5=22 |k6=0 |
|y7=y6-5*k6=22 |k7=5 |
|y8=y7-3*k7=7 |k8=7 |
Соответственно оптимальным решением задачи является (0,0,4,1,0,0,5,7),
соответственно максимально количество баллов, которое студент может набрать
за отведенное время равно 46.
2.4 Анализ чувствительности решения
В таблице для первого этапа нам, по существу, необходимо получить
оптимальное решение лишь для y1=30, так как это последний этап, подлежащий
рассмотрению (см. Приложение А). Однако в таблицу включены вычисления для
y1=0,1,…,30, которые позволяют провести анализ чувствительности решения.
Например, что произойдет, если время отводимое на контрольную работу
будет 20, вместо 30 (см. Приложение А)?
|Y1=20 |k1=0 |
|Y2=y1-2*k1=20 |k2=0 |
|Y3=y2-4*k2=20 |k3=4 |
|Y4=y3-k3=16 |k4=0 |
|Y5=y4-4*k4=16 |k5=0 |
|Y6=y5-7*k5=16 |k6=0 |
|Y7=y6-5*k6=16 |k7=3 |
|Y8=y7-3*k7=7 |k8=7 |
соответственно максимально количество баллов, которое студент может набрать
за отведенное время равно 34.
Что произойдет, если время отводимое на контрольную работу будет 5,
вместо 30 (см. Приложение А)?
|y1=5 |k1=0 |
|y2=y1-2*k1=5 |k2=0 |
|y3=y2-4*k2=5 |k3=0 |
|y4=y3-k3=5 |k4=0 |
|y5=y4-4*k4=5 |k5=0 |
|y6=y5-7*k5=5 |k6=0 |
|y7=y6-5*k6=5
| |  скачать работу |
Динамическое программирование (задача о загрузке) |
