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

Прежде всего условимся считать все x_j, a_j и b в задаче (3.1) целыми Требование целочисленности a_j и b фактически не является принципиальном, так как оно Может быть в большинстве случаев выполнено с необходимой степенью точности. Действительно, сделанное допущение задает лишь выбор единиц измерения величин a_j и b. Например, если b есть денежные единицы, то переход от тысяч к сотням или от сотен к десяткам и единицам рублей и т. д. всегда позволяет выразить b целым числом. То же самое относится и к a_j. Причина введения требования целочисленности x_j, a_j и b станет ясна ниже.

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

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

Итак, обозначим через Z^* абсолютный максимум Z в (3.1), т. е. величину, которую мы хотим найти:

(3.2)

Выберем некоторое значение x_n и, зафиксировав его, предположим, что мы можем определить максимум Z относительно всех остальных переменных x₁, x₂, ..., x_n-1. Конечно, при этом величины x₁, x₂, ..., x_n-1 при которых достигается max_{x1, ..., xn-1} Z, будут зависеть от выбранного нами значения x_n.

Поскольку мы условились, что x_n - целые числа, то можно представить, что эта максимизация выполнена для всех возможных значений x_n. Тогда Z^* будет наибольшим из всех полученных при этом значений Z. Таким образом, можно написать:

(3.3)

где член f_n (x_n) вынесен из-под знака максимума, поскольку величина x_n - фиксированная. Значения x₁, x₂, ..., x_n-1; кроме условий целочисленности и неотрицательности, очевидно, должны удовлетворять ограничению, которое при фиксированном x_n записывается в виде

(3.4)

Так как согласно (3.4) значения x₁, x₂, ..., x_n-1 зависят от величины ξ = b - a_nx_n, то величина

является функцией ξ, т. е. можно обозначить

(3.5)

Допустим, что нам удалось вычислить F_n-1 (ξ) для всех допустимых значений x_n. Тогда можем написать:

(3.6)

где x_n может принимать значения 0, 1, 2, ... и обозначает целую часть от величины ^b/_an. Мы можем найти Z^*, если вычислим

для всех допустимых значений x_n и затем возьмем наибольшую величину Ω_n (x_n^*), где через x_n^* обозначено значение x_n, при котором достигается этот максимум. Таким образом, если бы была известна функция F_n-1 (ξ), то задача отыскания Z^* свелась бы к задаче максимизации функции одной переменной. Условно считая, что переменная x_n уже выбрана, т. е. последний шаг спланирован для любого F_n-1 (ξ), и поступая аналогично вышеизложенному по отношению к переменной x_n-1, запишем соотношение

(3.7)

где א = ξ - a_n-1x_n-1,

(3.8)

и максимум в (3.8) берется по неотрицательным целым числам x₁, ..., x_n-2, удовлетворяющим условию

(3.9)

Величина x_n-1 в (3.7) может принимать значения 0, 1, 2, ..., [ξ/a_n-1]. Поэтому, если бы была известна функция F_n-2 (א), можно было бы вычислить F_n-1 (ξ), взяв максимум только по одной переменной x_n-1. Однако в отличие от (3.6) максимум в (3.8) должен вычисляться также для всех возможных значений ξ.

Используя последовательно этот прием для вычисления F_n-2, F_n-3 и т. д., мы, наконец, придем к вычислению

(3.10)

где x₁ в свою очередь может принимать значения 0, 1, ..., [ρ/a₁].

Итак, лишь F₁ определяется непосредственно, остальные F_k (k = 2, 3, ..., n) определяются с помощью соотношений вида

(3.11)

где x_k может принимать значения 0, 1, 2, ..., [ξ/a_k] (под ξ подразумевается любая из величин ξ, א, ..., ρ) и Z^* = F_n (b). Величина ξ называется параметром состояния; функции F_k (ξ) - функциями состояния.

Соотношения вида (3.11), обладающие тем свойством, что значение функции, вычисленное с помощью данного соотношения, подставляется как аргумент в следующее соотношение, называются реккурентными соотношениями.

Таким образом, в результате последовательного прослеживания всех шагов от конца к началу многошагового процесса мы получили выражения, с помощью которых можно найти максимальные значения Z на всех шагах, используя соответствующие условные оптимальные управления, т. е. схему вычислительного метода динамического программирования. Покажем теперь, каким образом довести вычисления до конца, т. е. найти множество значений x₁^*, x₂^*, ..., x_n^*, определяющих оптимальное управление.

Прежде всего необходимо определить

(3.12)

Для всех g=ξ = 0, 1, 2, ..., b. Здесь через x₁^{^} (ξ) обозначена величина x₁, при которой достигается максимум. Это значение F₁ может быть не единственным, т. е. соотношение (3.12) может выполняться более чем для одного значения x₁^{^} (ξ). Если необходимо найти все оптимальные решения, то для каждого ξ следует определить все x₁, для которых выполняется соотношение (3.12). Например, если a₁ = 1, то при ξ = 0 величина x₁ может принимать только одно значение x₁ = 0 и соответственно F₁ (0) = f₁(0). При ξ = 1 имеем x₁ = 0 и x₁ = 1, вычисляем f (1), сравниваем f₁ (0) и f₁ (1) и выбираем большее: F₁ (1) = max [f₁ (0), f₁ (1)] и т. д. до ξ = b. При ручном счете значения оказывается удобно записывать в виде таблиц; при счете на ЭВМ эти значения хранятся в памяти машины.

Найдя F₁ (ξ), с помощью (3.11) определяем

(3.13)

опять для всех ξ = 0, 1, ..., b. При этом для вычисления F₂ (ξ) при фиксированном ξ последовательно в (3.13) придаем x₂ целочисленные значения из интервала 0≤x₂≤[ξ/a₂] и получаем последовательность величин

Наибольшая из этих величин как раз и есть F₂ (ξ). Одновременно определяется также величина или величины ₂ (ξ), для которых F₂ (ξ) = Ω₂ (₂, ξ).

Отметим, что для определения F₂ (ξ) необходимо знать только F₁ (ξ - a₂x₂), причем число ξ - a₂x₂ есть целое неотрицательное число в силу сделанного ранее предположения о целочисленности a_j. Но величины F₁ (ξ) были вычислены ранее; поэтому нужно просто взять из них ту, которая соответствует числу ξ - a₂x₂.

Продолжая вычисления далее, определяем F₃ (ξ) и ₃ (ξ) для ξ = 0, 1, ..., b и т. д. вплоть до вычисления F_n-1 (ξ). Функцию F_n (ξ) необходимо вычислить только для ξ = b (F_n (b) = Z^*). Значение (или значения) _n (b) есть как раз то значение x^*_n, при котором получается максимум на последнем шаге, т. е. достигается F_n (b). Для нахождения x^*₁, x^*₂, ..., x^*_n-1, составляющих вместе с x^*_n оптимальное управление, следует использовать уже вычисленные значения _k (ξ). Так как величина x^*_n уже определена, остальные (n-1) переменные должны удовлетворять условию

(3.14)

где теперь b - a_nx^*_n - заданное число (числа). Поэтому должен достигаться на множестве неотрицательных целых чисел, удовлетворяющих (3.14), т. е. F_n-1 (ξ) = F_n-1 (b - a_nx^*_n) (см. соотношение (3.5)), и значение (значения) x^*_n-1 при котором этот максимум достигается, есть

(3.15)

Так как значения _n-1 (ξ) уже вычислены, то следует из этих значений взять число, соответствующее ξ = b - a_nx_n^*. Точно так же находится x^*_n-2:

или в общем виде

(3.16)

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

На этом заканчиваются вычисления, позволяющие решить задачу (3.1), т. е. найти Z^* и множество x₁^*, ..., x^*_n, образующих оптимальное управление. Отметим еще раз, что описанный вычислительный метод позволяет отыскать имеющиеся оптимальные решения. Однако зачастую очень трудно сделать.

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

при ограничении 0,4x₁ + 0,8x₂ + x₃≤2.

Прежде всего представим ограничение в таком виде, чтобы все a_j стали целыми:

Затем начнем вычислять функции F₁(ξ) (3.12). В нашем случае ξ = 0, 1, 2, ..., 10, f₁ (x₁) = 2x₁, a₁ = 2. Поэтому величина [ξ/a₁] = 0, 1, ..., 5. При ξ = 0 имеем только x₁ = 0 и

При ξ = 1 величина x₁ заключена в пределах 0≤x₁≤1/2, т. е. единственное целочисленное значение, которое может принимать x₁, есть также x₁ = 0, поэтому F₁ (1) = 0 и ₁ (1) = 0. Однако при ξ = 2 уже могут быть x₁ = 0 и x₁ = 1, т. е.

Рассуждая аналогично, получаем

Таким образом, мы определили значения функции F₁ (ξ) для всех возможных ξ и соответствующие им значения (ξ). Далее переходим к вычислению функции F₂ (ξ) по формуле (3.13), используя уже известные значения функции F₁ (ξ) для тех же значений ξ = 0, 1, ..., 10 (f₂ (x₂) = 3x₂, a₂ = 4).

Функцию F₃ (ξ) необходимо вычислить только для ξ = 10, и ее значение как раз определит max Z. Итак, для f₃ = x₃ и a₃ = 5 согласно (3.11) имеем

Значение ₃ есть как раз то значение x^*₃, при котором получается максимум относительно переменной x₃. Значение переменной x^*₂ определяем согласно (3.15):

И наконец, имеем

Таким образом, оптимальное решение (управление) есть x^*₁ = 5, x^*₂ = 0, x^*₃ = 0, и при этом функция цели достигает максимального значения Z^* = 10. Вследствие крайней простоты условий задачи в правильности такого ответа нетрудно убедиться непосредственно.

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

Если все a_j ≠ 1, то точное сравнение провести затруднительно. Поэтому рассмотрим лишь случай a_j = 1, т. е. Нижней границей числа различных комбинаций, удовлетворяющих этому ограничению, будет число различных комбинаций целых чисел, обращающих это ограничение в строгое равенство. Оно равно числу способов, которыми можно разместить b одинаковых шаров в n ящиках. Это число способов есть число сочетаний из b + n - 1 элементов по b, которое равно

Если воспользоваться вычислительным методом динамического программирования, то для вычисления всех F_k (ξ) при заданном k необходимо вычислить

значений. Для того чтобы вычислить функции F_k (ξ) для (n-1) шагов, соответственно требуется провести число вычислений в (n-1) раз большее. Однако для последней функции F_n (ξ) необходимо знать лишь значение F_n(b); поэтому потребуется провести только b + 1 вычисление. Таким образом, общее число вычислений равно:

Нетрудно убедиться для различных b и n, что при прямом переборе решений требуется выполнить во много раз дольше вычислений, причем эта разница возрастает с ростом n.