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)

где ,  удовлетворяют неравенствам

 .

Как видим, Т-задачу с тремя пунктами производства и  пунктами потребления можно свести к последовательности -шаговых задач с единственным параметром состояния .