Динамическое программирование

Пусть f_i(x_i)- оптимальная сумма инвестиций для интервала от і-го до n-го года при условии, что в начале і-го года имеется денежная сумма x_i. Далее обозначим через s_i накопленную сумму к концу n-го года при условии, что l_i и (x_i-l_i)-объемы инвестиций на протяжении і-го года в первый и второй банк соответственно. Обозначая , і=1,2, мы можем сформулировать задачу в следующем виде.

Максимизировать z=s₁+s₂+…+s_n, где

        (13)

Так как премиальные за n-й год являются частью накопленной денежной суммы от инвестиций, в выражения для s_n добавлены q_n1 и q_n2.

Итак, в данном случае рекуррентное уравнение для обратной прогонки в алгоритме динамического программирования имеет вид

 

                        (14)

где x_i+1 выражается через x_i в соответствии с приведенной выше формулой, а f_n+1(x_n+1)=0.

 

 

                  5. Задача о загрузке.

                             5.1 Общие сведения.

Задача  о загрузке – это задача о рациональной загрузке судна (самолета, автомашины и т.п.), которое имеет ограничения по объему или грузоподъемности. Каждый помещенный на судно груз приносит определенную прибыль. Задача состоит в определении загрузки судна такими грузами, которые приносят наибольшую суммарную прибыль.

Рекуррентное  уравнение процедуры обратной прогонки выводится для общей задачи загрузки судна грузоподъемностью W предметов (грузов) n наименований. Пусть m_i-количество предметов і-го наименования, подлежащих загрузке, r_i-прибыль, которую приносит один загруженный предмет і-го наименования, w_i-вес одного предмета і-го наименования. Общая задача имеет вид следующей целочисленной задачи линейного программирования.

Максимизировать z=r₁m₁+r₂m₂+…+r_nm_n.

при условии, что

w₁m₁+w₂m₂+…+w_nm_n W,

m₁,m₂,…,m_n 0 и целые.

Три элемента модели динамического программирования определяются следующим образом:

1. Этап і ставится в соответствии предмету і-го наименования, і=1,2,…n.
2. Варианты решения на этапе і описываются количеством m_i предметов і-го наименования, подлежащих загрузке. Соответствующая прибыль равна r_im_i. Значение m_i заключено в пределах от 0 до [W/w_i], где [W/w_i] – целая часть числа W/w_i.
3. Состояние x_i на этапе і выражает суммарный вес предметов, решения о погрузке которых приняты на этапах і,і+1,...n. Это определение отражает тот факт, что ограничения по весу является единственным, которое связывает n этапов вместе.

Пусть f_i(x_i)-максимальная суммарная прибыль от этапов і,і+1,...,n при заданном состоянии x_i. Проще всего рекуррентное уравнение определяется с помощью следующей двухшаговой процедуры.

Шаг 1. Выразим f_i(x_i) как функцию f_i+1(x_i+1) в виде

                      (15)

где f_n+1(x_n+1)=0.

Шаг 2. Выразим x_i+1 как функцию x_i для гарантии того, что левая часть последнего уравнения является функцией лишь x_i. По определению x_i-x_i+1 представляет собой вес, загруженный на этапе і, т.е. x_i-x_i+1=w_im_i или x_i+1=x_i-w_im_i. Следовательно, рекуррентное уравнение приобретает следующий вид:

                  (16)

 

        5.2. Рекуррентные соотношения для процедур прямой

                               и обратной прогонки.

 

Фермеру принадлежит  стадо овец, насчитывающее k голов. Один раз в год фермер принимает решение о том, сколько овец продать и сколько оставить. Прибыль от продажи одной овцы в і-м году составляет p_i. Количество оставленных в i-м году овец удваивается в (1+1)-м году. По истечении п лет фермер намеревается продать все стадо.

Этот чрезвычайно  простой пример приводится для того, чтобы наглядно продемонстрировать преимущества алгоритма обратной прогонки по сравнению с алгоритмом прямой прогонки. Вычислительные схемы процедур прямой и обратной прогонки обладают различной эффективностью в случаях, когда этапы модели нумеруются в некотором специальном порядке. Такая ситуация имеет место в приводимом примере, где этап j ставится в соответствие году j, т. е. этапы должны рассматриваться в хронологическом порядке.

Сначала построим рекуррентные соотношения для процедур прямой и обратной прогонки, а затем проведем сравнение двух вычислительных схем. Важное различие между двумя формулировками непосредственно следует из определения состояния.

Обозначим количества оставленных и проданных в j-м году овец через x_j и y_j, соответственно. Положим Zj,=x_j+y_j. Из условий задачи следует, что

z₁=2x₀=2k, 
      z_j=2x_j-1,j=l,2, ...,n.

Состояние на этапе j можно описать с помощью переменной z_j, которая выражает количество имеющихся к концу этапа j овец для распределения на этапах j+1, j+2, ..., n, или с помощью переменной x_j, которая выражает количество имеющихся к началу этапа j+1 овец, обусловленное принятыми на этапах 1,2,...,j решениями. Первое определение ориентировано на построение рекуррентного соотношения для процедуры обратной прогонки, тогда как второе определение приводит к использованию алгоритма прямой прогонки.

Алгоритм обратной прогонки.

Обозначим через f_i(z_i) максимальную прибыль, получаемую на этапах j,j+1,…,n, при заданном z_j. Рекуррентное соотношение имеет следующий вид:

                                      (17)

Заметим, что y_j и z_j - неотрицательные целые числа. Кроме того, у_j (количество овец, проданных в конце периода j) должно быть меньше или равно z_j. Верхней границей для значений z_j, является величина 2^jk (где k- исходный размер стада), которая соответствует отсутствию продажи.

Алгоритм прямой прогонки

 

Обозначим через g_j(x_j) максимальную прибыль, получаемую на этапах 1,2,...,j при заданном x_j, (где x_j— размер стада к началу этапа J+1). Рекуррентное соотношение записывается в следующем виде:

                                           (18)

- целое.

Сравнение двух формулировок показывает, что представление x_j-1 через x_j создает более существенные препятствия для вычислений, чем представление z_j+1 через z_j.

В замене x_j-1=(x_j+y_j)/2 подразумевается целочисленность правой части, тогда как на равенство z_j+1=2(z_j-y_j) такое требование не накладывается. Таким образом, в случае процедуры прямой прогонки значения y_j и x_j, связанные неравенством

Y_j <=2^jk -X_j,

должны дополнительно  удовлетворять условию целочисленности  их полусуммы, связанному с видом  зависимости х_j-1 от x_j,. Рассмотренный пример иллюстрирует трудности вычислительного характера, которые обычно возникают при использовании алгоритма прямой прогонки.

 

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

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

 

I	Wi	Vi
1 5 2 6 3 4 4 3 5 6 6 7 5 8 7	2 3 1 4 7 5 3 2	2 3 2 4 6 5 4 2

 

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

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

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

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

Если  отбросить требования целочисленности k_i, то решение задачи нетрудно найти с помощью симплекс-метода (см. Приложение В). В самом деле, так как остается лишь одно ограничение, базисной будет только одна переменная, и задача сводится к выбору типа і, для которого величина v_iW/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.

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

 

                   (19)

 

Заметим, что максимальное допустимое значение 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.

 

             5.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

соответственно  максимально количество баллов, которое  студент может набрать за отведенное время равно 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?