Математическая экономика

Эту стадию называют условной оптимизацией.

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

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

Задача об отыскании оптимального пути, соединяющего два заданных узла на прямоугольной сетке.

Рассмотрим на плоскости прямоугольник ABCD. Стороны этого прямоугольника разбиты на M частей по горизонтали и на N частей по вертикали, в результате получается сетка (рис. 6.5).

Рис. 6.5

Из точки А (начала) нужно проложить маршрут в точку С (конец), двигаясь по шагам только по сетке и перемещаясь на каждом шаге либо вправо (на восток), либо вверх (на север). Ясно, что этот маршрут будет состоять из M + N шагов и таких маршрутов можно сформировать большое количество.

Пусть каждому элементарному участку сетки приписано неотрицательное число, которое можно рассматривать как затраты, связанные с

171

преодолением этого участка. На рис. 6.5 эти числа проставлены рядом с соответствующими ячейками сетки.

Необходимо выбрать маршрут, для которого продвижение из начальной точки А в конечную точку С было бы связано с наименьшими суммарными затратами.

Решение. Будем рассматривать процесс формирования маршрута как процесс управления системой (точкой), перемещающейся по координатной сетке под влиянием управления (принимаемого решения). Состояние системы меняется дискретно, переходя с одного узла сетки в другой соседний узел. Это состояние можно характеризовать координатами (x, y) , где

x {0,1,2,3,4}, y {0,1,2,3}. Управление (команда) на каждом шаге может

принимать одно из двух значений: «вправо» или «вверх». Обозначим их условными символами: П, В. Процесс будет состоять из 7 шагов и может быть задан набором указанных символов, например (П, В, В, П, П, В, П).

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

Стадия условной оптимизации. Ее начинаем с конечной точки С. В нее в результате последнего 7-го шага можно попасть двумя способами: из точки (4; 2) с управлением (В) и затратами в 13 ед. и из точки (3; 3) с управлением (П) и затратами в 19 ед.

Запишем соответствующие величины затрат в кружки и отметим стрелками направление движения.

Рассмотрим теперь предпоследний 6-й шаг. Он может начаться в одной из трех точек с координатами (2; 3), (3; 2) и (4; 1). Для точки (2; 3) управление может быть одно (П), общие затраты 14 + 19 = 33 проставляем в кружке. Аналогично для точки (4; 1) управление возможно только (В), суммарные затраты 12 + 13 = 25. В точке (3; 2) ситуация интереснее: из нее можно идти вправо с суммарными затратами 15 + 13 = 28 ед. либо вверх с суммарными затратами 16 + 19 = 35 ед. Выбираем оптимальный вариант смещения право, отмечаем его стрелкой и проставляем величину 28 в кружок.

Аналогично рассматриваем 5-й шаг и перебираем четыре точки, с которых он может начаться, затем 4-й, 3-й, 2-й, 1-й шаги. В результате заполняем кружки во всех узлах и проставляем стрелки в соответствующих участках сетки.

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

172

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

(П, П, В, П, П, В, В).

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

1.В рассматриваемой задаче фактор времени в явном виде не присутствует. Однако псевдодинамику с дискретным временем в этой задаче удалось ввести искусственно, рассматривая управление (принятие решения

оформировании маршрута) как поэтапную, многошаговою процедуру, что вполне соответствует концепции ДП. Эта ситуация довольно типична для многих приложений ДП.

2.В ходе условной оптимизации может возникнуть ситуация, когда на некотором этапе возможно не одно, а два или более управлений (в данном примере – направление «П» или «В») с одинаковыми суммарными затратами. В таком случае можно выбирать любое из них. В результате задача будет иметь не единственное решение (оптимальный маршрут), но все решения будут иметь одну и ту же оптимальную величину критерия качества, в частности суммарную величину затрат.

3.Выполнив первую стадию решения методом ДП (условную оптимизацию), мы получили результат гораздо более содержательный, чем предполагалось поставленной задачей. Найдены оптимальные величины затрат и ориентиры (стрелки) для формирования оптимального маршрута для любого состояния системы (для каждого узла сетки), а не только заданного начального состояния (стартовой точки А).

4.В рассматриваемой задаче и многих других подобных задачах нужно выбрать решение из конечного множества возможных, легко формируемых решений. Возникает вопрос – не проще ли организовать и осуществить прямой перебор этих вариантов с оценкой каждого их них и выбором наилучшего? Решение, реализуемое с помощью ДП, также предполагает некоторый перебор вариантов, но при ДП этот перебор осуществляется целенаправленно. Это позволяет значительно сократить количество

173

рассматриваемых (обрабатываемых) вариантов по сравнению с «примитивным» перебором всех возможных вариантов. Подробнее об оценке эффективности ДП по сравнению с полным перебором вариантов см. напри-

мер [11].

5. Сравнивая методику и результаты решения задач на основе ДП с представленными в гл. 4 методами решения оптимизационных задач на графах (задача о кратчайших путях, поиск критического пути, задачи на транспортных сетях), можно увидеть много общего – решение в две стадии с движением от конца к началу и наоборот; получение меток, содержание которых аналогично информации, проставленной в кружках на рис. 6.5 и др.

§ 6.6. Основное функциональное уравнение ДП

При решении задач с помощью ДП бывает целесообразно использовать символьную (формализованную) запись изложенного выше принципа оптимальности Р. Беллмана. Для ее получения необходимо помимо обозначений, введенных в § 6.2, и формул (6.1) – (6.5) ввести дополнительные обозначения.

Будем наряду с общей оценкой эффективности всего процесса управления, выражаемой показателем

n

Y = ∑ yi , i=1

где yi – эффективность отдельного i-го шага, рассматривать величину

i=k

Она определяет эффективность участка рассматриваемого многошагового процесса от k-го шага до последнего включительно.

Условимся снабжать символом (*) переменные, соответствующие оптимальному решению, в частности:

(x* (1), x* (2),..., x* (n)) – оптимальное управление на всех шагах рассматриваемого процесса;

(s* (1),s* (2),..., s * (n)) – последовательность оптимальных состояний системы;

174

Y * – оптимальное значение критерия эффективности на всем промежутке управления;

Yk* – оптимальное значение критерия качества на участке от k-го шага до последнего.

Тогда принцип оптимальности можно записать следующим образом:

k-м шаге выбираются исходя из максимальности функции, стоящей в квадратных скобках. Оно определяется значением критерия эффективности на этом шаге в совокупности с оптимальным значением суммарного эффекта на всех последующих шагах с (k +1) -го до n -го включительно. Поскольку за последним шагом нет никаких шагов, формула (6.9) справедлива только до предпоследнего шага включительно, а на последнем шаге справедлива формула (6.10).

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

Проиллюстрируем методологию ДП на нескольких примерах (§ 6.7 –

6.11).

§ 6.7. Задача об оптимальном единовременном распределении выделенных средств между предприятиями

Рассматривается группа предприятий П1, ... , Пn , входящих в некий холдинг. Его руководство выделяет некоторый объем средств s0 для развития этих предприятий. Известны функции, определяющие получаемый доход в зависимости от величины вложенных средств fi (x(i)) для каждого

175

предприятия Пi . Требуется найти такое распределение величины s0 между предприятиями, которое даст максимальный общий доход.

Если обозначить через xi величину средств, выделенных i-му предприятию, то задача сводится к определению чисел xi = xi* , при которых целевая функция принимает наибольшее значение:

В этой задаче фактор времени отсутствует. По сути она является статической задачей и относится к задачам условной оптимизации. Такие задачи рассматривались в § 5.1 и § 5.5. Однако подобного рода задачи можно искусственно свести к динамическим, если принятие решения о распределении средств представить как пошаговую процедуру, при которой на первом этапе выделяются средства предприятию П1 , на втором – П2 и т.д. В результате получается дискретный процесс, состоящий из n этапов.

Искомые n чисел x1,..., xn в таком случае будут рассматриваться как n значений одного изменяющегося поэтапно фактора x , который можно интерпретировать как управление. Введем еще одну переменную s = si – остаток средств после их распределения на предшествующих этапах: s0 – выделенная для распределения начальная величина средств: s1 = s0 − x1 – величина средств, остающихся для распределения после первого шага, когда x1 средств выделено П1 и т.д. Эту переменную можно интерпретировать как состояние. При этом соотношение

является уравнением состояний, аналогичным (6.6). Важно, что показатель качества

n

Y= ∑ fi (xi )

i=1

соответствует условию аддитивности (6.7).

Введенная интерпретация и полученные соотношения (6.11) – (6.13) дают возможность рассматривать и решать поставленную задачу как задачу ДП.

176

Для любого k-го шага ( k =1,...,(n −1) ) этого процесса принятия решений о выделении средств можно записать уравнение Беллмана

Значение xk [0, sk −1] является допустимым управлением для k-го

шага.

Для последнего шага k = n и справедливо соотношение (6.10)

Пусть n = 4. Рассмотрим уравнение Беллмана (6.14) – (6.15) в соответствии с процедурой условной оптимизации, принятой в ДП, последовательно от последнего шага к первому. Получим следующие расчетные соотношения:

Получили последовательность расчетных соотношений, в которых результат, полученный на одном шаге, используется в расчетах на другом шаге. Такие соотношения называются рекуррентными. Поэтому условие оптимальности (6.9) – (6.10) часто называют рекуррентным уравнением Беллмана.

Далее для решения задачи нужно конкретизировать исходные условия. Будем, следуя [13], считать, что распределению подлежит величина s0 = 200 у.е., например 200 млн руб. или 200 тыс. долларов. Средства выделяются в размерах, кратных 40 у.е., а функции дохода заданы в табл. 6.1.

177

Оптимизация на каждом этапе в соответствии с приведенными выше условиями будет связана с перебором вариантов, который удобно осуществить с помощью формы, представленной в табл. 6.2.

Т а б л и ц а 6.2

178

Т а б л и ц а 6.4

Примечание. k = 2.

179

Т а б л и ц а 6.6

Примечание. k = 1.

Пояснения. Табл. 6.3, соответствующая последнему этапу, определяется упрощенным соотношением (6.10), и она могла бы быть составлена проще, но для единообразия представлена в том же виде, что и остальные табл. 6.4 – 6.6. В каждой из них колонки 1, 2, 3 заполняются очевидным способом. Колонка 4 заполняется из соответствующей колонки исходной табл. 6.1. Колонка 5 заполняется данными, полученными в последней колонке 7 предыдущей таблицы. Числа в колонке 6 получаются как сумма чисел из 4-й и 5-й колонок. В 7-й колонке выбирается наибольшее число из чисел, полученных в 6-й колонке.

Формирование этих таблиц (табл. 6.3 – 6.6) соответствует стадии условной оптимизации.

Перейдем теперь ко второй стадии – безусловной оптимизации. В последней из полученных выше таблиц (табл. 6.6.), соответствующей пер-

вому шагу, получено значение Y1* (200) = 24 . Это означает, что максималь-

ный доход, который можно получить при распределении средств в размере 200 у.е., составляет 24 ед. Здесь же получается оптимальное зна-

Из табл. 6.5 для этого состояния оптимальным значением явля-

180