§ 5. Вычислительный метод динамического программирования для задачи распределения с двумя ограничениями и задачи с двумя переменными

Задача распределения с двумя ограничениями формулируется следующим образом: определить

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

(3.24)

x_j>0; j = 1, 2, ..., n; x_j - все целочисленные.

Из тех же соображений, что и в задаче с одним ограничением, будем предполагать, что все a_1j, a_2j и b₁, b₂ целые и положительные числа.

Задача с двумя ограничениями, естественно, возникает тогда, когда в процессе распределения участвуют два источника ограниченных ресурсов. На j-м шаге выбирается величина x_j, одновременно определяющая соответственно количества a_1jx_j и a_2jx_j ресурсов первого и второго типов, Предназначенных для использования на этом шаге.

Поскольку задача (3.24) решается аналогично задаче (3.1) с той лишь разницей, что теперь используются два параметра состояния, то не будем приводить всех рассуждений, необходимых для вывода реккурентных соотношений, а запишем сразу окончательные результаты. Имеем функцию состояния на первом шаге:

(3.25)

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

(3.26)

Искомая величина Z^* = max Z есть

Одновременно с F_n (b₁, b₂) на последнем n-м шаге находится оптимальное управление на этом шаге x^*_n. Оптимальные значения остальных управлений выбираются среди уже вычисленных совместно с величинами F_n (b₁, b₂) условных оптимальных управлений _k (ξ₁, ξ₂). Этот выбор производится с помощью соотношений вида

(3.27)

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

найти

(3.28)

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

все x_j и y_j - целочисленные. Все a_1ja_2j и b₁, b₂ также считаются целочисленными и положительными.

Решение этой задачи опять проводится аналогично решению задач (3.1) и (3.24), но теперь на j-м шаге необходимо выбирать значения двух переменных x_j и y_j. Как и в задаче (3.24), на каждом шаге используются два параметра состояния, определяющих количества используемых ресурсов каждого вида.

Функция состояния на первом шаге записывается в виде

(3.29)

Реккурентные соотношения для вычисления функций состояния на любом шаге k = 2, ..., n имеют вид:

(3.30)

где x_k также может принимать значения 0, 1, ..., [ξ₁/a_1k] и y_k - значения 0, 1, ..., [ξ₂/a_2k]. В общем случае максимум по x_k и y_k находится прямым перебором возможных комбинаций этих переменных и вычисления для каждой из комбинаций величин

Таким образом, решение задач распределения с двумя ограничениями и двумя переменными (управлениями) в общем случае требует значительного увеличения объема вычислений. Поэтому задачи с двумя переменными обычно удается решать только с помощью больших электронных цифровых вычислительных машин (ЭВМ). Задачи с тремя переменными или (и) тремя параметрами состояния в ряде случаев также могут быть решены на больших ЭВМ. Во всяком случае задачи с четырьмя переменными,по-видимому, представляют тот предел, который в настоящее время в некоторых случаях еще может быть преодолен с помощью самых больших и быстродействующих ЭВМ.

Для того чтобы продемонстрировать эту слабую сторону вычислительного метода динамического программирования, сравним эффективность последнего с описанным в гл. I, §5 симплексным методом на примере решения задачи линейного программирования

найти:

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

(3.31)

Предположим сначала, что все a_ij≥0.

Эта задача может рассматриваться как n-шаговый процесс, в котором на каждом j-м шаге выбирается значение величины x_j, т. е. задача в такой постановке может решаться методами динамического программирования с одним переменным и m параметрами состояния.

Функция состояния соответственно будет иметь вид:

где максимум берется по всем x₁, ..., x_k, удовлетворяющим условиям

Реккурентные соотношения для вычисления функций состояния записываются в виде

(3.32)

где x_k меняется в интервале от 0 до min {[ξ_i/a_ik]}, k = 2, ..., n.

Если число параметров состояния ξ₁ велико, то объем вычислений методом динамического программирования становится чрезмерно большим. Например, при наличии 100 ограничений (m = 100) и соответственно 100 параметров состояния и при условии, если каждый из них принимает 100 значений, общее количество значений функции F_k (ξ₁, ..., ξ_m) достигает 10²⁰⁰. Это столь большое количество, что для его вычисления на ЭВМ со скоростью 10⁶ значений F_k (ξ₁, ..., ξ_m) в секунду потребуется более 10¹⁸⁶ лет. Ясно, что задачу (3.31) с таким числом параметров состояния невозможно решить методом динамического программирования, тогда как решение этой задачи на ЭВМ симплексным методом часто не представляет большого труда. Симплексный метод зачастую оказывается эффективнее даже при наличии только одного или двух ограничений.

В том случае, если в задаче (3.31) некоторые a_ij<0, решение методом динамического программирования еще iee усложняется, так как наибольшее значение ξ_i, для которого должна быть вычислена функция F_k-1 в (3.32), может быть уже не равно b_i. Во всяком случае оказывается трудно указать точно область определения каждого ξ_i.

Итак, мы рассмотрели вычислительный метод динамического программирования на примере задачи распределения. Однако, как уже указывалось выше, метод динамикою программирования может с успехом использоваться решении самых различных задач многошагового принятия решений. Забегая вперед, укажем, что вид реккурентных соотношений, используемых для вычисления функций состояния F_k(ξ), в различных задачах оказывается существо различным, т. е. вид этих соотношений зависит от структуры решаемой задачи. Для того чтобы облегчить в дальнейшем понимание проса решения различных конкретных задач, в следующем параграфе будет дана более общая постановка задачи динамического программирования.