УДК 519.857
Об одном подходе к решению задачи оптимального распределения ресурса большой размерности с помощью динамического программирования
В настоящее время в современной науке разработаны математические инструменты для приведения многих реальных задач в различных аспектах жизни общества, экономике, социальных процессах, технических решениях к формализованным процедурам, которые могут быть решены на современных ЭВМ. При этом могут быть получены такие решения реальных задач, эффективность которых максимальна при заданных ограничениях. Выражаясь более просто, с помощью математических процедур, реализованных в виде программ на ЭВМ можно значительно более качественно решать различные задачи в реальной жизни. Такие задачи относятся к задачам исследования операций.
Применение исследования операций в практических оптимизационных задачах дает значительный экономический эффект по сравнению с интуитивными методами принятия решений.
Круг приложений исследования операций очень широк. Исследование операций используется для решения технических, технико-экономических, социально-экономических задач, а также задач управления в различных сферах и на различных уровнях принятия решений.
Одной из задач исследования операций является задача оптимального распределения ресурса. В реальной жизни ресурсом может быть время, деньги, природные ресурсы, детали, люди, подразделения, организации и т. д.
Такая задача обычно состоит в максимизации или минимизации нелинейной целевой функции.
Для решения такой задачи с успехом используется метод динамического программирования, основы которого разработаны Р. Беллманом.
Одной из сложностей на пути использования данного метода при решении реальных задач распределения ресурса является их большая размерность, которая не позволяет решать их на современных ЭВМ.
В данной работе предлагается подход для решения одномерной дискретной задачи распределения ресурса, который основан на многократном использовании метода Беллмана каждый раз с новым по величине или знаку шагом дискретизации распределяемого ресурса. В настоящее время существуют работы 3, 4 и др., в которых рассматривается возможность декомпозиции системы на "быструю" и "медленную" подсистемы с двукратным использованием метода Беллмана. Такой подход использует меньший объем вычислений, приводит к нахождению квазиоптимального решения. Разбиение оптимизируемой системы на множество подсистем с динамически изменяющейся дискретизацией распределяемых ресурсов и с движением процесса оптимизации «вперед» и «назад», предлагаемое в данной работе, дает больший выигрыш в объеме вычислений и позволяет получить строго оптимальное решение.
Постановка задачи. Будем искать целочисленное решение cледующей задачи:
(1)
(2)
- целые, (3)
где 
- вогнутые непрерывные скалярные функции.
Схема метода. Решением задачи (1)-(3) с шагом K будем считать такое решение, при котором xi принимает значения, кратные K , для всех i = 
, где К > 0 и целое. Способ выбора K будет рассмотрен ниже.
Идея предлагаемого подхода состоит в нахождении сначала приближенного решения задачи (1)-(3) с грубым шагом K. Исходя из него с шагом 1 находится решение x” некоторой вспомогательной задачи, для которого справедливо
(4)
где 
- компонента оптимального решения 
исходной задачи.
Затем, используя решение 
как опорное, находится оптимальное решение 
.
Решение задачи (1)-(3) разобьем на 2 этапа.
1 этап. Найдем решение 
задачи (1)-(3) с шагом K. Будем считать для простоты, что M кратно K.
2 этап. На этом этапе решаются вспомогательные задачи с шагом I.
1) 
(5)
(6)
(7)
Решение задачи (5)-(7) обозначим через 
.
Положим 
.
2) 
(8)
(9)
(10)
Все три вспомогательные задачи решаются последовательно по схеме Беллмана.
Решение задачи (8)-(10) обозначим через 
, тогда решение задачи (1)-(3) с шагом 1 имеет вид:
(11)
Ниже будет показано, что вектор x” обладает свойством (4) и, как следствие из этого, что вектор x*, вычисленный:по формуле (11), является оптимальным в задаче (1)-(3).
Заметим, что если функция f(x) вогнута, то для любых x1 < x2 и 
> 0 выполняется условие
(11’)
Причем, если здесь имеет место равенство, то функция f(x) линейна на отрезке 
с угловым коэффициентом
Доказательство данного утверждения нетрудно получить, используя свойства вогнутых функций одной переменной (см., например, 1).
Лемма 1. Если 
и 
компоненты оптимального решения исходной задачи (1)-(3), причем 
, то справедливо неравенство
(12)
где 
- целое число, удовлетворяющее условию
.
Доказательство. От противного. Пусть справедливо неравенство:
Тогда 
(13)
Добавив к правой и левой частям неравенства (13) остальные члены суммы (1) на оптимальном решении, получим противоречие с оптимальностью 
в задаче (1)-(3):
Нетрудно видеть, что если в (12) имеет место равенство, то решение задачи (1)-(3) является неединственным.
Лемма 2. Существует решение x* задачи (1)-(3) с шагом 1, для которого одновременно не выполняются два неравенства:
и 
для некоторых 
, где 
, 
- компоненты решения задачи (1)-(3) с шагом K.
Доказательство. Предположим, что в множестве оптимальных решений задачи (1)-(3) с шагом 1 существует решение 
, для которого выполняется
и (14)
(в противном случае утверждение леммы очевидно).
Из леммы 1 при 
следует, что
(15)
Используя (14), (15) и (11’), получим:
(16)
Оценивая (16), видим, что возможны два случая:
1. 
,
2. 
. (17)
Рассмотрим оба варианта подробнее.
1. Из следует
Аналогично доказательству леммы 1 прибавим к левой и правой частям неравенства остальные члены суммы (1) на оптимальном решении 
задачи (1)—(3) с шагом K и получим противоречие с оптимальностью для данной дискретизации.
Следовательно, вариант 1 невозможен.
2. Из равенства
согласно (11’), следует, что функция линейна на отрезке 
с угловым коэффициентом
.
Аналогично, из равенства
следует, что
В силу равенства (17)
.
Пусть
.
Тогда
, (18)
(19)
В сипу линейности функций 
на отрезках , 
с одним и тем же угловым коэффициентом, из (18) и (19) следует, что решение 
как и 
является оптимальным в задаче (1)-(3) и для него выполняется
или 
.
Таким образом, если существует оптимальное решение задачи (1)-(3) с шагом 1, для которого выполняется (14), то обязательно найдется другое, также оптимальное решение, для которого (14) не выполняется.
Следствие. Пусть
0, если 
,
, если 
,
тогда
.
В самом деле, если предположить обратное, то это означает, что по крайней мере для некоторого номера 
будет выполняться
и в сипу определения 
.
Тогда, так как
найдется номер 
такой, что
.
Теорема 1. В результате решения задачи (5)-(7) получим такое решение 
, для которого найдется хотя бы одно 
оптимальное решение задачи (1)-(3) с шагом I, удовлетворяющее условию
(20)
Доказательство. Предположим, что в множестве решений задачи (1)-(3) с шагом 1 найдется такое решение 
, для которого выполняется 
, где 
. Тогда обязательно найдется такое 
, для которого выполняется 
.
Из (11) и леммы 2 следует, что
.
Далее доказательство аналогично доказательству леммы 2, когда получим два варианта:
1. 
2. 
Рассматривая вариант 1, приходим к выводу, что он невозможен, так как противоречит оптимальности в задаче (5)-(7). Рассматривал вариант 2, найдем другое решение задачи (1)-(3) с шагом 1, для которого (20) выполняется.
Следствие. Пусть 
- решение задачи (8)-(10), тогда 
- решение задачи (1)-(3).
Доказательство. Пусть
;
.
Нетрудно видеть, что для любых 
, удовлетворяющих условиям (9)-(10),
.
Отсюда следует, что множество 
. Так как по теореме 1 вектор 
, то 
. Но это и означает, что если - решение задачи (8)-(10), то - решение задачи (1)-(3).
Известно2, стр.368, что количество просматриваемых вариантов при решении задачи (1)-(3) по схеме Беллмана равно
.
При достаточно больших N и M можно пользоваться приближенной оценкой
(21)
При решении задачи предлагаемым методом в два этапа количество просматриваемых вариантов можно оценить:
.
Взяв производную 
и приравняв ее к нулю, подучим значение K, при котором величина 
минимальна:
.
При данном значении K
. (22)
При 
будет выполняться условие 
. Для реальных задач, как правило, 
. Поэтому предлагаемый метод по сравнению со схемой Беллмана позволяет значительно сократить количество рассматриваемых вариантов при решении задачи (1)-(3).
Можно еще более сократить объем вычислений, если решение задачи (1)-(3) разбивать на большее количество этапов, чем в предложенном выше подходе. Процесс многоэтапного решения назовем методом челночного хода, который состоит в следующем.
Этап 1. Решается задача (1)-(3) с шагом K1 .
Получаем решение 
, оптимальное с шагом K1.
Этап 2. а) Решается задача (5)-(7) с шагом K2 при 
.
Получаем решение 
.
б) Решается задача (8)-(10) с шагом K2 при 
.
Получаем решение 
, оптимальное с шагом K2.
Этап 3. а) Решается задача (5)-(7) с шагом K3 при 
.
Получаем решение 
.
б) Решается задача (8)-(10) с шагом K3 при 
.
Получаем решение 
, оптимальное с шагом K3.
* * *
Этап n-1. а) Решается задача (5)-(7) с шагом Kn-1 при 
.
Получаем решение 
.
б).Решается задача (8)-(10) с шагом Kn-1 при 
.
Получаем решение 
, оптимальное с шагом Kn-1.
Этап n. а) Решается задача (5)-(7) с шагом 1 при 
.
Получаем решение 
.
б) Решается задача (8)-(10) с шагом 1 при 
.
Получаем решение 
, оптимальное с шагом 1.
Пользуясь (21) и определением челночного хода, получим количество рассматриваемых вариантов при решении задачи (1)-(3) методом челночного хода:
,
где 
для 
,
для 
,
для 
.
- количество вариантов, рассматриваемых на i-м этапе.
Взяв производные 
и npиpaвняв их к нулю, получим систему из 
уравнений, решение которой выглядит следующим образом:
,
.
Полученные значения шагов дискретизации являются оптимальными при решении задачи (1)-(3) методом челночного хода в n этапов.
Подставив значения 
в (23), нетрудно получить следующее соотношение
. (25)
Из (23) и (25) следует
. (26)
Формула (26) отражает количество просматриваемых вариантов оптимизируемой системы при оптимальных значениях 
, полученных из (24).
Для нахождения оптимального количества этапов при проведении метода челночного хода возьмем производную 
и приравняем ее к нулю. Получим:
.
Необходимо учесть, что к n и предъявляется требование целочисленности. Поэтому на практике оптимальное значение n* количества этапов равно значению целой части 
или 
, в зависимости от количества вычислений, которое оценивается из (26). Значения берутся как ближайшие целые к полученным из (23).
Кроме того, значение K может быть не кратно M. Поэтому в реальной двухэтапной задаче уравнение (2) примет вид:
,
где 
и кратны K.
Уравнение (9) также изменится:
.
Для метода челночного хода можно доказать теорему, аналогичную теореме 1, т. е. показать, что для любого i - го этапа 
и вектор , полученный в результате решения задачи (8)-(10), будет являться решением задачи (1)-(3) с шагом Ki, а вектор 
, полученный в результате решения задачи (8)-(10) на n - м этапе, будет решением задачи (1)-(3) с шагом 1.
Исходя из всего вышесказанного, количество просматриваемых вариантов в двухэтапной задаче будет несколько отличаться от (22), но отличие на практике является незначительным. В многоэтапной задаче уравнение (2) примет вид:
,
где и кратны K1. А уравнения (6) и (9) для i - го этапа будут иметь вид соответственно:
и 
,
где 
и кратны K.
В многоэтапной задаче количество просматриваемых вариантов также незначительно отличается от (26).
Пример. N = 100, M = Количество вычислений по схеме Беллмана
.
Используя челночный ход: n* = 13; 
.
Выигрыш предложенного метода по сравнению со схемой Беллмана составит
.
Результаты практической реализации челночного хода подтвердили теоретические расчеты. В таблице 1 приведены сводные результаты сравнения классического метода Беллмана с предложенным методом челночного хода.
Таблица 1
Способ применения динамического программирования | Время решения | ||||||
N = 3 M = 10 | N = 10 M = 102 | N = 10 M = 103 | N = 10 M = 104 | N = 102 M = 103 | N = 102 M = 104 | N = 102 M = 105 | |
Классический | 20 сек. | 1,3 мин. | 2,3 час. | 220 * час. | 22 * час. | 2,2*103 * час. | 2,2*105 * час. |
Челночный | 4 сек. | 13 сек. | 19 сек | 27 сек. | 2 час. | 4 час. | 6 час. |
Однотипные прикладные задачи решены на одной и той же ЭВМ типа IBM 390 по одной программе. Результаты, полученные классическим и челночным способом, полностью совпадают. Время решения, обозначенное * получено расчетным путем, так как решить такую задачу не представлялось возможным из-за недостатка ресурса времени ЭВМ.
Примечания.
1 / Численные методы решения экстремальных задач. - М.: Наука, 1980.
2 Хедди Дж. / Нелинейное и. динамическое программирование. - М.: Мир, 1967.
3 Dynamic programming using singular petrurbations. Krikorian K. V., Leondes N. T. “Journal of optimization Theory and Applications.”, 1982, 38, №2, 221-230.
4 Chow Joe H., Kokotovic Petar V. A two stage Lyapunov - Bellman feeddback design of a class of nonlinear systems. “Proc. 19th IEEE Conf. and Contr. incl. sump. Adapt. Process., Albuquerque, N. M., 1980. Vol. 2.“ New York, N. Y., 1980, .
