ФОРМАЛИЗАЦИЯ И РЕШЕНИЕ ОПТИМИЗАЦИОННЫХ ЗАДАЧ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ В СИСТЕМЕ "ВЕКТОР"

Седых В.И., Богданов В.И., Болотов В.П.
В настоящей работе предпринята попытка познакомить читателя с оптимизационным методом динамического программирования Р. Белмана и показать, что решение задач этим методом значительно упрощается при использовании компьютерно-графических систем. Метод поясняется на ряде примеров,  используемых для этой же цели профессором Военно-воздушной академии им. Жуковского Еленой Сергеевной Вентцель, учеником которой посчастливилось быть одному из авторов статьи.

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

Суть метода динамического программирования изложена Р. Белманом в двух формулировках его основной теоремы.

Первая формулировка: оптимальная стратегия (поведение) системы не зависит от ее предыстории, а зависит лишь от состояния системы в данный рассматриваемый момент времени.

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

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

Пример. Некоторый летательный объект (ЛО) стартует в точке А и имеет высоту 0 условных единиц и скорость 0 условных единиц. ЛО объект должен попасть в точку В и иметь при этом скорость V=5 условных единиц и высоту H=5 условных единиц.
Построим сетку (рис.1) на вертикалях, горизонталях и диагоналях которой отложим цифры, характеризующие расход  топлива в условных единицах при движении ЛО по соответствующему маршруту. Эти данные получены, например, в предыдущих экспериментах.

Согласно теоремам Р. Белмана и приведенным выше пояснениям оптимальную стратегию будем искать не с начала траектории, а с ее конца.

При этом оптимальный (наименьший) расход топлива необходимый для того, чтобы пройти оставшую часть пути, будем откладывать в узловых точках. Рассматривая с конца пути все точки сетки, нетрудно оцифровать их так, чтобы путь от каждой из них до т. В был оптимальным. На этом принципе и базируется метод динамического программирования: процесс разворачивается от конца к началу; прежде всего планируется последний m-й шаг.

   Рис. 1.

 Оптимальное управление на m-м шаге называется условным, т.к. оно выбирается на основании гипотезы: предпоследний шаг оптимален и соответствует оптимальной стратегии в целом. Этот предпоследний шаг отметим стрелкой, что поможет в дальнейшем решении задачи - поиску безусловной оптимизации. Теперь мы можем оптимизировать управление на предпоследнем  (m-1) - шаге. Снова, сделав предположения о том, чем кончился предыдущий (m-2) - шаг, найдем такое управление на (m-1)-м шаге, при котором выигрыш за последние два шага (один из которых, с номером m, уже оптимизирован) минимален.

В результате мы найдем для каждого исхода (m-2)-го шага условно оптимальную стратегию на (m-1)-м шаге и условный оптимальный выигрыш на двух последних шагах. Далее продолжая процедуру, оптимизируем управление на (m-2)-м шаге и т.д., пока не дойдем до первого.

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

Теперь мы можем определить уже не условно оптимальный, а оптимальный выигрыш. Для этого надо осмыслить полученные результаты и найти безусловное оптимальное управление системы, что достигается движением по стрелкам от начала к концу.
Рассмотрим решаемый пример в компьютерно-графической системе "Вектор", где имеются развитые графические возможности, язык программирования, возможности работы с циклами, векторами и случайными числами.
Рис. 3
Допустим, что мы не знаем метода динамического программирования и пользуемся простым перебором всех возможных вариантов движения объекта от начала к концу, выбирая из них оптимальный в зависимости от расхода топлива. Здесь проблема заключается в том, как перебрать все возможные варианты движения. Наиболее простой подход - организовать движения от каждой точки по методу случайных чисел. Данный подход был апробирован сначала для нахождения наикратчайшего пути от точки А до точки В, где результат решения очевиден. За примерно 150 итераций был найден наикратчайший путь - прямая. В расмотренном выше примере также было выполнено 150 итераций и был найден путь, но результат решения по оптимальности неочевиден. Можно увеличить число итераций, что увеличит вероятность нахождения оптимального маршрута, но и здесь не будет уверенности, что оптимальность достигнута. Для более строгого решения воспользуемся методикой, которая была предложена Р. Белманом и примнена Е. С. Вентцель для рассмотренного примера.

Решение задачи в системе "Вектор" заключается в формализации тех действий, которые были реализованы при решении примера 1.

Исходными данными для задачи являются расход топлива, обозначенный на ребрах (горизонталях, вертикалях и диагоналях) графа (рис. 1). Вершины графа Рuv можно вычислить по формуле p=(1-v)((1-u)p50 + up55)+v((1-u)p0+up5), где параметры u и  v изменяются от 0 до 1 и могут быть подобраны соответственно требованиям задачи.
Вершины графа обозначим векторами-точками с координатами: горизонталь - координата х, вертикаль - координата y,  диагональ   - координата z. В модуле Optim системы "Вектор" имеется возможность работы с 4-мерными векторами, у которых 4-ой координатой является содержимое регистра с индексом, состоящим из буквы s и произвольно стоящей цифры. Последнее дает возможность запомнить оптимальные значения расхода топлива для каждой точки при решении первого этапа задачи.

Заполнение вершин графа оптимальными значениями при движении от конца к началу может быть любым, главное - чтобы они были последовательными. Для удобства заполнения вершин графа оптимальными значениями и возможности организации цикла можно предложить прием, показанный на рис.1, где последовательно двигаясь  от конца к началу, можно заполнить все точки (их вектора) значениями оптимальных стратегий. Не менее важно знать и направления от какой точки от конца получено оптимальное значение (на рис. 1 решенной по Белману задачи эти направления отмечены стрелкамии). Направление движения формально можно обозначить так: направление по горизонтали - 1, по вертикали - 2, по диагонали - 3 Этот код будем помещать в регистр n соответствующих номеру точки целых чисел. Ниже на языке Калькулятор приведен фрагмент первой части решения задачи в системе "Вектор".
 
 
$ начинаем движение с конца (точка p55 0-ряд)
$ помещаем в узлы (1-й ряд параллельно  диагонали от конечной точки) значения наименьших расходов топлива
$ 1 ряд
: s54=x55 s45=y55  n54=1  n45=2
 s121=z154+y54
s122=z55
s123=z145+x45
s99=1000.
s121 < s99 ? s99=s1
s122 < s99 ? s99=s2
s123 < s99 ? s99=s3
s44=s99
  Чтобы формализовать вторую часть задачи найти безусловную стратегию оптимального движения, необходимо воспользоваться признаками их оптимальной близлежащей точки и двигаться по этому направлению т.е. двигаться не методу случайных чисел а по предписанному (определенному в первой части задачи) закону. Формализация этой части задачи дана ниже, которую, в свою очередь, можно организовать через цикл и таким образом вторую часть задачи свести к этим строкам.

 
$ ВТОРАЯ ЧАСТЬ ЗАДАЧИ ОПРЕДЕЛЕНИЕ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ
 nn100  $ точка входа
n7=n100
nn100 <> 1 ?  n7=n7+1
nn100 <> 2 ?  n7=n7+10
nn100 <> 3 ?  n7=n7+10+1
p102=pn7
col2   $ : n5=13
tprin : p101=pn100 $  построение отрезка
p101=p102
 
 Общее решение задачи сводится к обращению к МК первой и второй частей задачи, передачи в нее точки входа начала движения, при этом зная, что из каждой точки графа движение будет оптимальным.

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