О методах математического программирования при разработке программ автоматизированных систем управления
Математическое программирование охватывает область математики, разрабатывающую теорию и прикладные методы решения многомерных экстремальных задач ограничениями на изменения переменных при разработке программного обеспечения систем автоматического управления.
Линейное программирование при разработке программного обеспечения систем автоматического управления. Этот раздел математического программирования разрабатывает теорию и числовые методы решения задач определения экстремума линейной функций многих переменных при наличии линейных ограничений на эти переменные.
Основная задача линейного программирования при разработке программного обеспечения систем автоматического управления. Необходимо определить значения переменных х1 -хт, для которых целевая функция достигает экстремального значения. Эта задача может быть решена следующими методами: симплекс-методом, модифицированным симплекс-методом, методом последовательного уточнения оценок и методом последовательного сокращения невязок. Варианты постановки задачи, ее полная теория и методы решения даны в работах.
Задачи линейного программирования большой размерности при разработке программного обеспечения систем автоматического управления (число переменных превышает 100) и сверхбольшой размерности (число переменных превышает 1000). Методы этой группы включают специальные приемы разделения задач на задачи меньшей размерности — декомпозиции задач.
«Транспортная» задача линейного программирования при разработке программного обеспечения систем автоматического управления. Необходимо определить значения переменных, при которых функция достигает экстремального значения. Методы решения этой задачи имеют особенности, связанные со спецификой постановки задачи. Теория и методы решения «транспортных» задач даны в работах.
«Распределительная» задача линейного программирования при разработке программного обеспечения систем автоматического управления. Эта задача представляет собой некоторое обобщение предыдущей и также имеет свои особенности, которые позволяют строить более эффективные методы решения по сравнению с основной задачей линейного программирования.
Обобщенная задача в сетевой постановке. Сетевая постановка задач линейного программирования при разработке программного обеспечения систем автоматического управления дает возможность учесть ряд особенностей, возникающих при практическом использовании, и построить достаточно эффективные методы их решения.
Необходимо определить значения х„ при которых целевая функция достигает экстремального значения. Решение такой задачи при разработке программного обеспечения систем автоматического управления осуществляется с помощью метода Гомори или метода секущих. Обзор методов решения этого класса задач дан в книге, сами методы изложены в работах.
Целочисленные задачи с булевыми переменными при разработке программного обеспечения систем автоматического управления. Задачи этого класса в значительной степени аналогичны задачам предыдущего класса, но в то же время имеют свои особенности, которые позволяют их выделить.
Необходимо определить набор (хг,...,хм), при котором целевая функция достигает экстремального значения.
Основным методом решения этой задачи является метод «ветвей и границ».
Комбинаторное программирование при разработке программного обеспечения систем автоматического управления. Этот раздел математического программирования включает дискретные задачи, и специальные методы их решения, как правило, нелинейны. Термин «комбинаторное программирование» обусловлен тем, что чисто дискретные задачи можно интерпретировать как задачи оптимизации функций, определенных на заданном множестве выборок (комбинаций) из конечного числа элементов.
Задачи календарного планирования при разработке программного обеспечения систем автоматического управления. Примером задачи названного класса является задача определения очередности выполнения заданий.
Вторымпримером задач названного класса является задачаопределения порядка обработки деталей.
Нелинейное программирование при разработке программного обеспечения систем автоматического управления
Этот раздел математического программирования разрабатывает теорию и методы решения задач определения экстремума нелинейной функции многих переменных при наличии нелинейных ограничений на эти переменные.
Общая формулировка задачи нелинейного программирования заключается в следующем: задана нелинейная целевая функция F(х), где х — n-мерный вектор, определяющий некоторую точку в и-мерном евклидовом пространстве Еп й т функций ограничений.
Необходимо определить значение составляющих вектора х таких, чтобы функция F(x) достигала экстремального значения при выполнении всех ограничений при разработке программного обеспечения систем автоматического управления.
По характеру функции F(x) и функций ограничений д((х) можно классифицировать задачи нелинейного программирования.
Необходимо определить значение вектора х такое, чтобы функция F(x) достигала экстремального значения при выполнении заданных ограничений.
Второй разновидностью задач рассматриваемого класса является задача квадратичного программирования, в которой необходимо определить экстремум квадратичной функции.
Динамическое программирование при разработке программного обеспечения систем автоматического управления. Динамическое программирование — это метод решения задач нелинейного математического программирования. Метод основан на следующем принципе оптимальности: оптимальная стратегия обладает тем свойством, что каковы бы ни были начальное состояние и принятое начальное решение, последующие решения должны составлять Оптимальную стратегию относительно состояния, возникшего в результате первоначального решения.
Математическая формулировка этого принципа заключается в следующем. Рассмотрим некоторый управляемый объект, состояние которого в любой момент времени задано вектором х. Составляющие вектора являются фазовыми координатами изображающей точки в фазовом пространстве объекта. Время выделяется, как отдельная координата. На каждой стадии n-этапного процесса изменения состояния объекта можно изменять управляющее воздействие, описываемое вектором и. Под воздействием вектора и объект переходит в новое состояние х'. Если состояние объекта отображается в дискретном пространстве», то используется дискретное динамическое программирование.
Метод Множителей Лагранжа при разработке программного обеспечения систем автоматического управления. Этот метод решения служит для определения экстремума функций многих переменных. Он является одним из основных методов решения задач нелинейного математического программирования. Сущность метода заключается в следующем: пусть задана нелинейная целевая функция F(x), где х — n-мерный вектор. Необходима определить экстремум F(x) при ограничениях д (х) ~ Ь, где д и Ь — векторы.
Решение определяется поэтапно. На первом этапе вводится вектор у = (у; у2,...,ут) составляющие которого носят название множителей Лагранжа. На втором этапе определяется функция Лагранжа как сумма целевой функции и скалярного произведения вектора множителей Лагранжа и лектора разности между постоянными ограничениями и функциями ограничений.
Градиентные методы оптимизации. К градиентным методам оптимизации относят методы, в которых процесс вычисления оптимального значения целевой функции основан на использовании градиента (или антиградиента) этой функции.
Метод формулируется следующим образом. Пусть задана целевая функция F(x), значения которой зависят от составляющих вектора x = (Х1,…..хп), определяющего положение точки х в n-мерном евклидовом пространстве Еп. Процесс оптимизации представляет собой вычисление значений F(x) для такой последовательности точек х1, х2, хт, которая приводит к оптимальному значению F(x). Для определенности дальнейших формулировок примем, что оптимальной точкой является точка минимума функции.
В процессе оптимизации в окрестности точки хк определяется одно или несколько значений F (х)1 так называемые пробные шаги. Затем на основании полученных значений вычисляется новая точка — рабочий шаг, после чего процесс вычислений повторяется.
Градиентный метод дает глобальный минимум только для строго вогнутых функций. Может оказаться, что найденный минимум и глобальный минимум совпадают для некоторой многоэкстремальной функции. Это совпадение может быть либо случайным, либо целенаправленным, но в последнем случае необходима дополнительная информация о характере изменения функции F(x). Градиентные и примыкающие к ним методы возможных направлений достаточно полно исследованы в работах. Оценка числа арифметических операций при использовании метода градиента дается в работе.
Метод покоординатной оптимизации при разработке программного обеспечения систем автоматического управления
Сущность метода заключается в том, что определение минимума функции F(x), где х— n-мерный вектор евклидового пространства, связано с преобразованием координат на каждом шаге таким образом, чтобы координатные оси совпадали с направлением поиска. Направление поиска выбирается из условия определения локального минимума функции F(x). Производится аналогичное построение и для определения максимума функций.
Этот метод оказывается эффективным в тех случаях, когда специфические особенности задач позволяют осуществить определение абсолютного минимума по выбранному направлению координатной оси.
Изложенный метод является эффективным для решения сетевых задач, в том числе задач оптимального распределения ресурсов. Детальное изложение метода и ряд возможных приложений дано в работах.
Принцип максимума Понтрягина при разработке программного обеспечения систем автоматического управления. Принцип максимума представляет собой основу для решения вариационных задач, возникающих в теории управления физическими объектами.