7.2. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ ДЛЯ ЗАДАЧ С НЕСКОЛЬКИМИ ОГРАНИЧЕНИЯМИ И переМЕННЫМИ
Рассмотрим задачу оптимального распределения ресурсов, но уже при двух ограничениях [6; 18]:
при ограничениях
- целые.
Поскольку в задаче имеется два вида ресурсов 
и 
, то необходимо ввести два параметра состояния: 
, 
.
Обозначим через
(7.2.1)
при ограничениях
- целые. (7.2.2)
Запишем основное рекуррентное соотношение для этой задачи:
, (7.2.3)
где
.
Одновременно с 
находим и соответствующее оптимальное решение 
. Последовательно находим 
, ., 
, ., 
. На 
-м шаге, положив = 
, = , находим 
, и одновременно 
.
Оптимальные значения всех остальных переменных 
можно получить из таблиц предыдущих шагов при помощи соотношений
;
и т.д.
Как видим, функции , 
являются функциями двух переменных (параметров). Если каждая из переменных 
, может принимать 
значений, то функцию приходится табулировать в 
точках.
Если имеется три ограничения вида
, (7.2.4)
то для решения задачи (7.2.1), (7.2.4) методом динамического программирования надо ввести три параметра состояния , , 
и функцию 
. Если каждый из параметров , , будет приобретать значений, то функцию 
придется табулировать уже в 
точках. Как видим, объем вычислений по схеме ДП возрастает экспоненциально в зависимости от размера задачи (то есть от числа параметров состояния 
). Без специальных способов задачу, которая содержит более чем три параметра состояния, невозможно решить на современных ЭВМ из-за огромного объема вычислений, который возрастает экспоненциально в зависимости от размера задачи. Это плата за поиск глобального оптимального решения. Этот феномен Р. Беллман в свое время охарактеризовал как 'проклятие многомерности' динамического программирования [4; 18].
Задача с двумя переменными управления
Рассмотрим предыдущую задачу в несколько иной постановке, когда имеются две переменные управления 
, 
и два типа ресурсов ( , ), а доход 
есть функция количества обоих типов ресурсов, распределяемых на данном шаге.
Итак, требуется
максимизировать 
при ограничениях
.
Чтобы описать состояние системы на 
-м шаге, снова надо ввести два параметра , . Определим функцию состояния
при ограничениях
.
ОРС для данной задачи имеет вид
,
причем максимум в (7.2.3) по 
, 
находят перебором всех возможных комбинаций. Например, если , могут приобретать по значений, то для нахождения 
при фиксированных , надо перебрать значений функции
.
Итак, объем вычислений еще больше возрастает по сравнению с предыдущей задачей, и мы снова сталкиваемся с 'проклятием многомерности' Беллмана.
Применение метода множителей Лагранжа для понижения размерности задач динамического программирования
Рассмотрим один из наиболее распространенных методов понижения размерности задач ДП - метод множителей Лагранжа.
Пусть требуется решить такую задачу:
максимизировать 
(7.2.5)
при ограничениях
, (7.2.6)
, (7.2.7)
.
Заметим, что ограничения здесь заданы в форме равенств. От задачи (7.2.5) с двумя ограничениями перейдем к задаче с одним ограничениям:
максимизировать 
(7.2.8)
при ограничении
, (7.2.9)
.
Для решения задачи (7.2.8) методом динамического программирования нужен лишь один параметр состояния, и потому она намного проще исходной.
Параметр 
в (7.2.8) - это множитель Лагранжа, он играет роль цены на второй ресурс ( ). Априори величина неизвестна, и потому задачу (7.2.8) приходится решать при нескольких произвольных значениях .
Будем решать задачу (7.2.8), (7.2.9) методом динамического программирования. Ее оптимальное решение будет зависеть от как параметра.
.
Если найденное оптимальное решение 
будет удовлетворять отброшенное ограничение (7.2.7), то оно и будет искомым.
В противном случае значение надо скорректировать. Как показано в [49], функция 
монотонно убывает с увеличением . Поэтому, если 
, значение необходимо увеличить (поскольку по второму ресурсу имеется перерасход, то цену на него надо повысить). В противном случае значение необходимо уменьшить.
Для быстрого определения искомого значения можно применить метод последовательных приближений, который основан на такой интерполяционной формуле. Если уже опробованы два значения 
, 
и для них найдены соответствующие оптимальные решения 
, то на следующем шаге 
оценивают по такой формуле:
, (7.2.10)
где
.
Покажем, что если оптимальное решение задачи (7.2.8) 
удовлетворяет (7.2.7), то - оптимально и для задачи (7.2.5).
Предположим, что это утверждение неверно, и обозначим через 
решение задачи (7.2.5). Тогда
. (7.2.11)
Поскольку - оптимальное решение для (7.2.8), то
.
Вместе с тем, так как
,
то 
. (7.2.12)
Сравнивая (7.2.12) и (7.2.11), прийдем к выводу, что
.
Следовательно, это утверждение справедливо.
Основное рекуррентное соотношение для задачи (7.2.8) имеет вид
. (7.2.13)
Можно показать, что при возрастании от 0 до ∞, величина 
убывает монотонно [4; 49]. Это важное свойство значительно облегчает поиск 
при решении практических задач.
Рассмотрим общий случай ограничений:
максимизировать 
(7.2.14)
при ограничениях
(7.2.15)
Введем ( < 
) множителей Лагранжа и перейдем от (7.2.14), (7.2.15) к эквивалентной задаче максимизации функции
, (7.2.16)
при остальных 
ограничениях
.
Задачу (7.2.16) решим методом динамического программирования с использованием неопределенных множителей Лагранжа. Таким образом, задача сводится к определению функции состояния 
от переменных 
вместе с поиском по -мерному пространству переменных, удовлетворяющих первым ограничениям. Исходная многомерная задача заменяется последовательностью задач значительно меньшей размерности, что позволяет существенно снизить требования к объему памяти ЭВМ и ее быстродействию.
Решение транспортной задачи
методом динамического программирования
В качестве примера использования метода множителей Лагранжа рассмотрим транспортную задачу с двумя пунктами производства 
, 
и пунктами потребление 
, 
, ., 
.
Обозначим через 
- количество продукта, перевозимого из в 
, а 
- количество продукта, перевезимого из в , 
.
Обозначим через 
стоимость перевозки по маршруту 
. Тогда транспортная задача формулируется так:
минимизировать 
(7.2.17)
при ограничениях
; (7.2.18)
. (7.2.19)
Если 
, то задача легко решается методами ЛП. Однако мы рассмотрим случай, когда - нелинейные функции, и потому применим метод динамического программирования.
Покажем, что, несмотря на большое количество ограничений, функцию состояния процесса можно описать лишь одним параметром.
Рассмотрим случай, когда количество продуктов в пунктах и составляет и единиц. Поскольку + = 
, то = - , и потому - есть единственный параметр состояния.
Введем последовательность функций
, (7.2.20)
где минимум берут по всем 
, удовлетворяющим ограничениям
.
Основное рекуррентное соотношение тогда записывается так:
, (7.2.21)
где удовлетворяет условию 
.
При проведении вычислений функция 
должна табулироваться для всех = 0, 1, . , . На последнем шаге (при 
) найдем 
и 
. Остальные переменные 
находим последовательно из соотношений
.
Рассмотрим теперь ту же самую задачу, но с тремя пунктами производства , , 
. Функция состояния на этот раз определяется так:
(7.2.22)
при ограничениях
; (7.2.23)
. (7.2.24)
Рекуррентное соотношение динамического программирования запишется так:
(7.2.25)
причем минимум в (7.2.25) берут по 
, 
, удовлетворяющим условиям:
;
Область, в которой ищут минимум, показана на рис. 7.7. Функции 
должны табулироваться для всех целых , , таких, что 
.
Для сокращения размерности задачи применим метод множителей Лагранжа. Допустим временно, что нет ограничений на количество продукта, который вывозится из пункта , а вместо этого каждой единице продукта, вывозимой оттуда, приписана цена .
Решаем задачу вида:
минимизировать
(7.2.26)
при ограничениях
(7.2.27)
Будем искать минимум в (7.2.26) для различных значений , пока не будет найдено такое оптимальное решение, которое будет удовлетворять 
. Тогда автоматически будет выполняться и третье ограничение 
.
Для решения задачи введем функцию состояния с одним параметром 
:
, (7.2.28)
где
.
Основное рекуррентное соотношение тогда можно записать так:
(7.2.29)
где 
, 
удовлетворяют неравенствам
.
Как видим, Т-задачу с тремя пунктами производства и пунктами потребления можно свести к последовательности -шаговых задач с единственным параметром состояния .
