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

5

4

2

Решить задачу, приведя ее к рекуррентным соотношениям.

Сначала рассмотрим задачу в общей постановке. Если обозначить количество вопросов типа і через k_i , то задача принимает следующий вид:

при ограничениях

k_i -неотрицательные числа.

Если отбросить требования целочисленности k_i , то решение задачи нетрудно найти с помощью симплекс-метода (см. Приложение В). В самом деле, так как остается лишь одно ограничение, базисной будет только одна переменная, и задача сводится к выбору типа і, для которого величина v_i W/w_i принимает максимальное значение. Исходная задача не является задачей линейного программирования, и для ее решения необходимо использовать метод динамического программирования. Следует отметить, что рассматриваемая задача может быть также решена с помощью методов целочисленного программирования.

Каждый из трех основных элементов модели ДП определяется следующим образом.

1. Этап j ставится в соответствии типу j, j=1,2,…,N.

2. Состояние y_j на этапе j выражает суммарный вес вопросов, количество ответов на которые приняты на этапах j,j+1,…,N; при этом y₁ =W и y_j =0,1,…,W при j=2,3,…,N.

3. Варианты решения k_j на этапе j описываются количеством вопросов типа j. Значение k_j заключено в пределах от нуля до [W/w_j ], где [W/w_j ]-целая часть числа (W/w_j ).

Пусть f_i (y_i )-максимальный суммарный вес вопросов, ответы на которые приняты на этапах j,j+1,…,N при заданном состоянии y_j .

Рекуррентное соотношение (для процедуры обратной прогонки) имеет следующий вид:

Заметим, что максимальное допустимое значение k_j ограничено величиной [y_j /w_j ]. Это позволяет автоматически исключать все не являющиеся допустимыми варианты при заданном значении переменной состояния y_j .

Решение исходной задачи (см. приложении А):

Этап 8.

Этап 7.

Этап 6.

Этап 5.

Этап 4.

Этап 3.

Этап 2.

Этап 1.

Оптимальное решение определяется теперь следующим образом. Из условия W=30 следует, что первый этап решения задачи при y₁ =30 дает оптимальное решение k₁ =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 Анализ чувствительности решения

В таблице для первого этапа нам, по существу, необходимо получить оптимальное решение лишь для y₁ =30, так как это последний этап, подлежащий рассмотрению (см. Приложение А). Однако в таблицу включены вычисления для y₁ =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