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

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

    Обозначим количества оставленных и проданных  в 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. Рекуррентное соотношение имеет следующий вид:

    

    Заметим, что 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). Рекуррентное соотношение записывается в следующем виде:

    

    

- целое.

    Сравнение двух формулировок показывает, что  представление 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,. Рассмотренный пример иллюстрирует трудности вычислительного характера, которые обычно возникают при использовании алгоритма прямой прогонки.

 

    

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

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

     

 

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

      Сначала рассмотрим задачу в общей постановке. Если обозначить количество вопросов типа і через 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.

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

      

      

 

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

      Решение исходной задачи: 

      Этап 8.

      

 

      Этап 7. 

      

 

      Этап 6.

      

 

      Этап 5.

      

 

      Этап 4.

      

 

      Этап 3.

      

 

      Этап 2.

      

 

      Этап 1.

      

 

      Оптимальное решение определяется теперь следующим  образом. Из условия W=30 следует, что первый этап решения задачи при y₁=30 дает оптимальное решение k₁=0, которое означает, что на 0 (нуль) вопросов 1-го типа будут даны ответы. Далее находим:

        

      Соответственно  оптимальным решением задачи является (0,0,4,1,0,0,5,7), соответственно максимально  количество баллов, которое студент  может набрать за отведенное время  равно 46. 

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

      В таблице для первого этапа  нам, по существу, необходимо получить оптимальное решение лишь для  y₁=30, так как это последний этап, подлежащий рассмотрению. Однако в таблицу включены вычисления для y₁=0,1,…,30, которые позволяют провести анализ чувствительности решения.

      Например, что произойдет, если время отводимое  на контрольную работу будет 20, вместо 30?  
 

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

      Что произойдет, если время отводимое  на контрольную работу будет 5, вместо 30? 
 

 

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

      Что произойдет, если типов вопросов будет 4, вместо 8?

      Этап 4.

      

 

      Этап 3.

      

 

      Этап 2.

      

 

      Этап 1.

      

 
 

 

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