Использование конечного двойственного метода для корректировки решений близких задач линейно-квадратичного программирования. Разработка программы на языке С для решения и корректировки решений. Двойственная задача. Основные понятия и утверждения.
Аннотация к работе
Эти задачи в теории управления решались разными методами. Они не позволяли учитывать ограничения на управления, которые характерны для современных постановок задач. Было построено много различных способов решения задач оптимального управления: и линейных, и линейно-негладких, и линейно-квадратичных, и других. При этом будут автоматически учитываться ограничения на управление и траекторию, т.к. они являются составными элементами задач оптимального управления.Задачу (1.1) - (1.3) можно трактовать как поиск такого решения уравнения (1.2) на ограниченном множестве (1.3), которое минимально в среднеквадратичном уклоняется от нулевого вектора.Теорема 1.1 (достаточное условие оптимальности) Если для плана выполняются соотношения при ; Основное ограничение (1.2) задачи (1.1) - (1.3) называется управляемым, если для любых m-вектора b и n-вектора х найдется такой n-вектор , что на векторе будет выполняться основное ограничение: Из последнего равенства имеем , откуда Поскольку на каждой итерации прямых методов осуществляется переход от плана х задачи к некоторому другому плану , то при разработке прямых методов возникает частный случай управления основным ограничением, а именно, поскольку х - план задачи, то , и из (1.6) получаем Таким образом, каким бы ни взять (n - m) - вектор , подсчитав по формуле (1.10) m-вектор получим n-вектор , добавление которого к любому плану х дает n-вектор , являющийся псевдопланом, т.е. вектором, на котором выполняется основное ограничение. Из формулы приращения (1.17) следует следующая теорема: Теорема 1.4 (критерий оптимальности) Для оптимальности плана . в задаче (1.1) - (1.9) достаточно существования такой опоры ; что для опорного плана выполняются соотношения при ;Основной вопрос при решении задачи (1.1) - (1.3) состоит в построении оптимального плана . Тут же возникает вопрос: как изменится оптимальный план и оптимальное значение функции при изменении параметров задачи?Согласно правилу составления двойственных задач, двойственная задача для задачи (1.1) - (1.3) имеет вид: (2.1) Задача (1.1) - (1.3) называется прямой, а (2.1) - двойственная к ней. Решения задач (1.1) - (1.3) и (2.1) удовлетворяют следующим соотношениям двойственности, выражающим тесную связь между прямой и двойственной задачей: 1) для существования решения прямой задачи необходимо существования решения двойственной задачи;Исходя из соотношений (1.19) критерия оптимальности, а также с учетом формул (1.14) - (1.16), которые определяют векторы потенциалов и оценок, следует структура оптимального плана задачи (1.1) - (1.3): 1) опорные компоненты , "отвечают" только за соблюдение основного ограничения (1.2) и могут принимать любые значения из отрезков: , (предпочтительнее, конечно, вариант, когда все последние неравенства строгие, т.е. случай невырожденности опорного плана , что делает справедливой необходимую часть критерия оптимальности); 2) неопорные компоненты , , делятся на две группы: одни из них принимают критические значения (или ) в сочетании с определенным знаком оценок (см. При этом очевидно, что поскольку оценки зависят от плана, то любой малый сдвиг от точки сразу нарушит равенство нулю оценок компонент второй группы (некритических компонент), т.е. сразу будет нарушена третья группа соотношений из (1.19). Если при этом у компонент, принимающих критические значения, оценки ненулевые, то малый сдвиг от точки не изменит знаки этих оценок, т.е. при малом сдвиге две первые группы соотношений из (1.19) будут выполняться. Если для начального опорного плана оценки всех неопорных компонент не равны нулю, то, как и в линейной задаче, все неопорные компоненты плана можно направить к соответствующим границам (или ) прямых ограничений (в соответствии со знаком ) в надежде, что знаки оценок не изменятся, и при шаге вдоль выбранного направления, равном единице, будут выполнены условия (1.19) критерия оптимальности с критическими значениями для "(устойчивые (3.1) и неустойчивые (3.2) признаки для критических значений ).Программа DMQP - программа конечного двойственного метода линейно-квадратичного программирования. , и - нижнее и верхнее ограничениям на переменные, - вектор-столбец размерности , соответствующий начальному плану задачи, - количество основных ограничений задачи, - количество переменных. Программа корректировки решений близких задач линейно-квадратичного программирования написана на языке С. Программа конечного двойственного метода линейно-квадратичного программирования написана на языке фортран и скомпилирована в файл dmqp. exe. Входной файл имеет следующую структуру: В файле: - транспонированный двумерный массив , и соответственно равны и , - размер опоры ограничений начального согласованного опорного плана, - обратная матрица к опорной матрице, - размер опоры целевой функции начального согласованного опорного плана, - вектор-столбец, содержащий элементы верхнего треугольника матрицы, обратной к опорной матрице целевой функции, записанные по строчкам; - вектор-столбец размерности , который сод
План
Содержание
Реферат
Содержание
Введение
1. Постановка задачи
1.1 Прямая задача квадратичного программирования. Основные понятия
1.2 Основные утверждения
1.3 Проблема построения решений близких задач квадратичного программирования
2. Двойственная задача. основные понятия и утверждения
3. Классификация методов решения линейно-квадратичных задач
4. Два подхода к проблеме решения близких линейно-квадратичных задач
5. Использование программы DMQP
Заключение
Список использованных источников
Приложения
Введение
В теории управления до сих пор являются актуальными многие задачи. Например, задачи регулирования, демпфирования и стабилизации динамических систем с ограниченными управлениями.
Эти задачи в теории управления решались разными методами. Они не позволяли учитывать ограничения на управления, которые характерны для современных постановок задач.
В середине прошлого века от общей теории управлений отделилась теория оптимального управления, которая с тех пор прошла огромный путь развития. Было построено много различных способов решения задач оптимального управления: и линейных, и линейно-негладких, и линейно-квадратичных, и других. Поэтому уместно применять методы оптимального управления к классическим задачам управления. При этом будут автоматически учитываться ограничения на управление и траекторию, т.к. они являются составными элементами задач оптимального управления. При этом переходным процессам будут приданы дополнительные полезные свойства: минимизация энергии, расхода топлива, интенсивности управления и другие. Но в применении к классическим задачам управления задачи оптимального управления являются не основными, а вспомогательными. При этом приходится строить решения целой серии близких задач оптимального управления выбранного вида, т.е. актуальной является проблема корректировки решений близких задач оптимального управления. Эти задачи можно решать в различных классах допустимого управления. Тогда соответственно задачи оптимального управления будут эквивалентны конечномерным задачам математического программирования.
В данной работе в качестве таких задач рассматривается линейно-квадратичная задача. линейное квадратичное программирование язык