21-3. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

Современная наука и техника все чаще сталкиваются с задачами отыскания оптимальных процессов

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

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

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

где некоторая функция x и ее производных, и заданы граничные условия в виде значений

при (начало процесса) и (конец процесса). Заменой переменных

задача приводится к отысканию функции, соответствующей максимуму (экстремаль) функционала:

при заданных граничных значениях

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

Рис. 21-7. Пример функции одной переменной, иллюстрирующий недостаточность классических методов для решения проблем оптимальности.

Аналогично решается задача определения экстремума функционала

при более общих условиях типа системы дифференциальных уравнений

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

Применение классических методов вариационного исчисления наталкивается на большие трудности при ограничениях переменных в виде неравенств. Число элементарных арифметических операций, необходимых для достаточно точного численного решения уравнения Эйлера с заданными условиями частично в начале и частично в конце (граничные условия), во многих практических задачах чрезмерно велико. Классический методы позволяют определить лишь те значения (рис. 21-7) функционала или функции, которым соответствует двусторонний

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

Кроме того, могут встретиться двусторонние экстремумы неаналитического типа 3 (рис. 21-7), отыскание которых требует в лучшем случае видоизменения классических приемов.

Все это вызвало в последнее время, с одной стороны, развитие вариационного исчисления в направлении решения неклассических задач, а с другой — разработку приближенного общего метода, называемого динамическим программированием. Понтрягиным и его учениками создан важный метод решения задач оптимального управления, получивший название принципа максимума [Л. 21-6]. Метод динамического программирования развит Беллманом [Л. 21-5]. Что касается определения экстремума функции многих переменных три ограничении типа неравенств, то для решения частного вида этой задачи широко попользуется способ линейного программирования. Хотя оба последних метода разработаны как чисто вычислительные, мы изложим основные идеи этих методов для выяснения целесообразного вида алгоритмов игровых систем автоматического управления.

Рис. 21-8. К пояснению основной идеи метода динамического программирования.

а) Динамическое программирование

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

Для пояснения основной идеи динамического программирования рассмотрим одну простую иллюстрацию. Пусть состояние некоторой системы характеризуется координатами х, у, принимающими дискретных значений Требуется перевести систему из состояния в состояние На плоскости существует множество процессов или траекторий перевода системы из (рис. 21-8,а). Все множество траекторий образуется путем перехода изображающей точки из какого-либо квадрата в квадрат, лежащий справа, или в квадрат, лежащий сверху. Всего изображающая точка при любой траектории пройдет через этапов или сделает переходов. Пусть далее для каждой траектории перехода из состояния в состояние определена функция выгоды Функция выгоды образуется как сумма приращений

функций выгоды во всех квадратах, через которые пройдет изображающая точка.

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

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

В основе метода динамического программирования лежит интуитивный принцип оптимальности, который позволяет решать задачи оптимизации многоэтапных процессов последовательно путем построения рекуррентных соотношений. Для применения принципа оптимальности в рассматриваемом примере разделим траекторию изображающей точки на два участка: от начала до некоторого промежуточного этапа и от этого промежуточного этапа до конца (рис. 21-8,6).

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

где

Вместе с определением определяется и траектория, от т. е. движение вверх—направо или направо—вверх. После определения можно» найти:

и

где

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

В табл. рис. 21-9 приведен числовой пример для В табл. а приведены числовые значения а в табл. числовые значения и оптимальная траектория от

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

Перейдем к более общей математической формулировке метода, динамического программирования.

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

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

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

При оптимальной программе Функция выгоды примет максимальное значение и будет зависеть только от начального состояния системы. Обозначив максимумы функций выгоды как будем иметь:

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

оптимальной программы обеспечивающей эту максимальную функцию выгоды.

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

Для одного этапа, как уже указывалось, имеем:

Согласно (21-9) состояние системы на втором этапе двухэтапного процесса равно:

По условию каковы бы ни были второй этап должен быть оптимальным, т. е.

Суммарная функция выгоды двухэтапного процесса

Соответственно максимальное значение функции, выгоды для двухэтапного процесса

Рассуждая аналогичным образом, для трехэтапного процесса будем иметь:

и, наконец, для этапов

Рис. 21-9. Иллюстрация задачи, решаемой методом динамического программирования.

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

Поскольку после определения определяется окончательно и для определения следует откинуть начальный этап и обратиться к -этапному процессу с начальный состоянием т. е. определить как функцию

Таким же образом определяются остальные члены оптимальной программы:

Метод динамического программирования разработан не только для дискретных, но и для непрерывных процессов или задач [Л. 21-5]. С другой стороны, непрерывные задачи оптимизации путем разбиения на этапы могут быть приблйженно решены методом динамического программирования в дискретной форме.

Пусть, например, требуется найти функцию соответствующую максимуму функционала

при условии

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

В рассматриваемой задаче характеризует состояние системы, функцию выгоды, выражение

играет роль функции преобразования является параметром преобразования. На основании общего уравнения динамического программирования (21-13) записываем:

Отыскивая последовательно максимумы функций

находим приближенное значение максимума функционала и начальную ординату функции Вторую ординату находим из рассмотрения всех этапов без первого:

и соответственно далее:

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

Максимум функции в каждом этапе при небольшом числе аргументов — компонент вектора параметра — можно находить по способу «слепого» поиска.

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

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

Например, если известно, что функция выгоды в каждом этапе имеет лишь один максимум «двустороннего» типа, расположенный внутри области допустимых изменений параметра то поиск может осуществляться на основе метода наискорейшего спуска или метода Гаусса-Зайделя, или метода градиента Для случая, когда функция выгоды линейна и ограничения изменения аргументов представляют собой линейные неравенства, применяются специальные методы поиска наибольшего значения, получившие название методов линейного программирования. Линейное программирование может использоваться как способ отыскания максимума функции выгоды в каждом этапе динамического программирования и как самостоятельный способ решения линейных задач на оптимум, часто возникающих в различных областях планирования.

Рис. 21-10. Геометрическая интерпретация задач линейного программирования.

б) Линейное программирование

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

при ограничениях в виде неравенств

Здесь заданные постоянные коэффициенты.

Легко указать геометрическую интерпретацию сформулированной задачи. Ограничения (21-16) определяют область на плоскости переменных Границами этой области возможных значений являются, с одной стороны, оси с другой — прямые

Таким образом, область возможных значений в данном случае представляет собой четырехугольник на плоскости Эта область на рис. 21-10,а имеет внутреннюю штриховку. В особых случаях, когда одно из неравенств (21-16) есть следствие других, четырехугольная область возможных решений уступает место треугольной области.

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

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

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

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

того или иного способа линейного программирования.

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

при ограничениях в виде системы линейных неравенств

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

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

Можно дать формальную интерпретацию многомерной задачи линейного программирования, подобную рассмотренной геометрической интерпретации двухмерной задачи. А именно: задача линейного программирования заключается в отыскании наибольшего значения линейной функции переменных область возможных изменений которых задана в виде многогранника (21-18) в -мерном пространстве. Однако подобная геометрическая интерпретация, как и любая интерпретация в -мерном пространстве при не дает непосредственно способа числового решения задачи.

Для решения задач линейного программирования разработано несколько методов. Давно применяется метод транспортирования, получивший свое название в задачах оптимального планирования перевозок. Более общим является симплексный метод. Мы не будем здесь останавливаться на этих вычислительных методах, довольно громоздкое описание которых можно найти. в специальной литературе [Л. 21-3 и 21-4].

Кратко остановимся на специальной форме метода градиента, применимой для решения задач линейного программирования. Достоинство этого способа — его прозрачное геометрическое содержание.

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

Первое перемещение точки начинается от начала координат в направлении вектора градиента функции выгоды

т. е. по прямой

Увеличивая т. е. двигаясь вдоль указанного первого вектора градиента, следим одновременно за условиями (21-18) нахождения в многограннике ограничений

которые в данном случае принимают вид:

Пусть при достижении некоторого значения одно из неравенств (21-19) первым обратилось в равенство

Следует заметить, что одновременное обращение в равенства двух или большего числа неравенств (21-19) является особым случаем, благоприятным, кстати сказать, для решения задачи линейного программирования. Излагаемая методика легко обобщается на этот особый случай, но для краткости мы не будем на нем останавливаться.

Выполнение равенства (21-20) при некотором означает, что мы, двигаясь вдоль первого вектора градиента, достигли грани многогранника ограничений в точке

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

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

можно исключить один из аргументов, напимер Тогда

В соответствии с этим компоненты второго вектора градиента равны:

Движение вдоль второго вектор» градиента начинается от точки где

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

Здесь — положительная переменная. Движению вдоль второго вектора градиента соответствует увеличение начиная с

При некотором значении нарушается еще одно из неравенств (21-18). Особый случай одновременного нарушения нескольких неравенств не рассматривается. Тогда

Отсюда определяется значение и по формулам (21-22) координаты конца второго участка поиска. Далее находится третий вектор градиента функции выгоды

при условии

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

Процесс поиска заканчивается тогда, когда движение по вектору градиента в следующем этапе приводит в начальной точке к нарушению ограничений (21-18). Для двухмерной задачи линейного программирования (рис. 21-10) изложенная методика сводится к движению по первому вектору градиента (рис. 21-10,б) и далее по второму участку поиска до точки А.

Пример. Требуется решить задачу линейного программирования функции

для условий

Координаты первого участка поиска равны:

Подставляя эти выражения в неравенства ограничений

убеждаемся, что при возрастании первым нарушается верхнее неравенство при Координаты конца первого участка поиска здесь равны:

Для второго участка поиска исключаем переменную из выражений

Тогда

Таким образом, на втором участке поиска

Подставляя эти выражения во второе неравенство, находим . Таким образом, и координаты конца второго участка поиска равны:

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

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

получаем:

Таким образом, координаты третьего участка будут равны:

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

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