Динамическое программирование (задача о загрузке) - Математика - Скачать бесплатно
следует из
определения состояния.
Обозначим количества оставленных и проданных в 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 |k7=0 |
|Y8=y7-3*k7=5 |k8=5 |
соответственно максимально количество баллов, которое студент может набрать
за отведенное время равно 10.
Что произойдет, если типов вопросов будет 4, вместо 8 (см. Приложение
Б)?
Этап 4.
[pic]
Этап 3.
[pic]
Этап 2.
[pic]
Этап 1.
[pic]
|y1=30 |k1=5 |
|y2=y1-2*k1=20 |k2=3 |
|y3=y2-4*k2=8 |k3=4 |
|y4=y3-k3=4 |k4=3 |
соответственно максимально количество баллов, которое студент может набрать
за отведенное время равно 39.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
1. Таха Х. Введение в исследование операций.–М.: Мир,1985.
2. Кузнецов Ю. Н. Математическое программирование. –М.: Наука,1976.
3. Вентцель Е. С. Исследование операций. –М.: Наука,1976.
4. Вентцель Е. С. Элементы динамического программирования. –М.: Наука,1987.
5. Акоф Р., Сасиени М. Основы исследования операций. –М.: Мир,1971.
6. Вентцель Е. С. Исследование операций: задачи, принципы, методология.
–М.: Наука,1988.
7. Карманов В. Т. Математическое программирование. –М.:Наука,1986.
8. Зайченко Ю. П. Исследование операций. –К.: Высшая школа,1985.
9. Аоки М. Введение в методы оптимизации. –М.: Наука,1977.
10. Беллман Р., Дрейфус С. Прикладные задачи динамического
программирования. –М.: Наука,1965.
11. Муну М. Математическое программирование. Теория алгоритмов. –М.:
Наука,1990.
ПРИЛОЖЕНИЕ А
Решение задачи методом динамического программирования
ПРИЛОЖЕНИЕ Б
Анализ чувствительности решения
ПРИЛОЖЕНИЕ В
Решение задачи симплекс-методом
|
