4.3 Решение задачи о загрузке.

Контрольная работа содержит вопросы по N различным темам. Каждый вопрос типа i имеет вес Vi(i=1,2,…N), а также время, отводимое на ответ Wi. Максимально время, которое может затратить студент на контрольную работу W. Требуется определить максимальное количество баллов (вес), которое может набрать студент за отведенное время W=30. Данные приведены в таблице:

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

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

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

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

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

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

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

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

Варианты решения 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.

Этап 2.

Этап 1.

Оптимальное решение определяется теперь следующим образом. Из условия 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.

Анализ чувствительности решения

В таблице для первого этапа нам, по существу, необходимо получить оптимальное решение лишь для 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.

Этап 3.

Этап 2.

Этап 1.

соответственно максимально количество баллов, которое студент может набрать за отведенное время равно 39.