О методах математического программирования при разработке программ автоматизированных систем управления

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

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

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

Задачи линейного программирования боль­шой размерности при разработке программного обеспечения систем автоматического управления (число переменных превы­шает 100) и сверхбольшой размерности (чис­ло переменных превышает 1000). Методы этой группы включают специальные приемы разделения задач на задачи меньшей размер­ности — декомпозиции задач.

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

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

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

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

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

Необходимо определить набор (х_г,...,х_м), при котором целевая функция достигает экстремального значения.

Основным методом решения этой задачи является метод «ветвей и границ».

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

Задачи календарного планирования при разработке программного обеспечения систем автоматического управления. При­мером задачи названного класса является за­дача определения очередности выполнения заданий.

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

Нелинейное программирование при разработке программного обеспечения систем автоматического управления

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

Общая формулировка задачи нелинейно­го программирования заключается в следую­щем: задана нелинейная целевая функция F(х), где х — n-мерный вектор, определяющий некоторую точку в и-мерном евклидо­вом пространстве Е^п й т функций ограничений.

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

По характеру функции F(x) и функций ограничений д₍(х) можно классифицировать задачи нелинейного программирования.

Необходимо определить значение вектора х такое, чтобы функция F(x) достигала эк­стремального значения при выполнении за­данных ограничений.

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

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

Математическая формулировка этого принципа заключается в следующем. Рассмотрим некоторый управляемый объект, состояние которого в любой момент време­ни задано вектором х. Составляющие векто­ра являются фазовыми координатами изображающей точки в фазовом пространстве объекта. Время выделяется, как отдельная координата. На каждой стадии n-этапного процесса изменения состояния объекта можно изменять управляющее воздействие, описываемое вектором и. Под воздействием вектора и объект переходит в новое состоя­ние х'. Если состояние объекта отображается в дискретном пространстве», то используется дискретное динамическое программирова­ние.

Метод Множителей Лагранжа при разработке программного обеспечения систем автоматического управления. Этот метод решения служит для определения экстрему­ма функций многих переменных. Он являет­ся одним из основных методов решения за­дач нелинейного математического програм­мирования. Сущность метода заключается в следующем: пусть задана нелинейная целе­вая функция F(x), где х — n-мерный вектор. Необходима определить экстремум F(x) при ограничениях д (х) ~ Ь, где д и Ь — векторы.

Решение определяется поэтапно. На пер­вом этапе вводится вектор у = (у; у₂,...,у_т) составляющие которого носят название мно­жителей Лагранжа. На втором этапе опреде­ляется функция Лагранжа как сумма целевой функции и скалярного произведения вектора множителей Лагранжа и лектора разности между постоянными ограничениями и функциями ограничений.

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

Метод формулируется следующим обра­зом. Пусть задана целевая функция F(x), зна­чения которой зависят от составляющих век­тора x = (Х₁,…..х_п), определяющего положе­ние точки х в n-мерном евклидовом пространстве Е^п. Процесс оптимизации представляет собой вычисление значений F(x) для такой последовательности точек х¹, х², х^т, которая приводит к оптимальному значе­нию F(x). Для определенности дальнейших формулировок примем, что оптимальной точкой является точка минимума функции.

В процессе оптимизации в окрестности точки х^к определяется одно или несколько значений F (х)1 так называемые пробные ша­ги. Затем на основании полученных значений вычисляется новая точка  — рабочий шаг, после чего процесс вычислений повторяется.

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

Метод покоординатной оптимизации при разработке программного обеспечения систем автоматического управления

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

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

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

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