Курсовая работа (т): Решение и корректировка решений близких задач линейно-квадратичного программирования

Решение и корректировка решений близких задач линейно-квадратичного программирования

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ

Учреждение образования

"Гомельский государственный университет имени Франциска Скорины"

Математический факультет

Кафедра вычислительной математики и программирования

РЕШЕНИЕ И КОРРЕКТИРОВКА РЕШЕНИЙ БЛИЗКИХ ЗАДАЧ ЛИНЕЙНО-КВАДРАТИЧНОГО ПРОГРАММИРОВАНИЯ

КУРСОВАЯ РАБОТА

Исполнитель:

студент группы ПМ-32 Долгалева Анна Александровна

Научный руководитель:

к. ф. - м. н., доцент Лубочкин Александр Васильевич

Гомель 2014

Реферат

Курсовая работа 21 страница, 1 приложение, 7 источников.

Ключевые слова: план, оптимальный план, условие оптимальности, критерий управляемости основного ограничения, критерий оптимальности, двойственная задача, конечный двойственный метод.

Объект исследования: близкие задачи линейно-квадратичного программирования.

Методы исследования: использование программы двойственного метода квадратичного программирования для решения и корректировки решений близких задач линейно-квадратичного программирования.

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

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

Содержание

Реферат

Содержание

Введение

1.        Постановка задачи

1.1 Прямая задача квадратичного программирования. Основные понятия

1.2 Основные утверждения

1.3 Проблема построения решений близких задач квадратичного программирования

2. Двойственная задача. основные понятия и утверждения

3. Классификация методов решения линейно-квадратичных задач

4. Два подхода к проблеме решения близких линейно-квадратичных задач

5. Использование программы DMQP

Заключение

Список использованных источников

Приложения

Введение

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

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

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

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

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

1. 
Постановка задачи

1.1 Прямая задача квадратичного программирования. Основные понятия

Рассмотрим задачу

, (1.1)

, (1.2)

, (1.3)

где ,

,

; ;

,

; , .

Задачу (1.1) - (1.3) можно трактовать как поиск такого решения уравнения (1.2) на ограниченном множестве (1.3), которое минимально в среднеквадратичном уклоняется от нулевого вектора.

Любой n-вектор x, удовлетворяющий основному (1.2) и прямым (1.3) ограничениям называется планом задачи (1.1) - (1.3).

План , доставляющий минимум целевой функции (1.1), называется оптимальным планом.

Субоптимальный (ε-оптимальный) план  (при заданном числе ε > 0) определяется неравенством

 (1.4)

1.2 Основные утверждения

Достаточное условие оптимальности плана

Теорема 1.1 (достаточное условие оптимальности) Если для плана  выполняются соотношения

 при ;

 при ; (1.5)

 при , ,

то  оптимальный план задачи (1.1) - (1.3).

Управляемость основного ограничения. Опора ограничений. Опорный план

Задача (1.1) - (1.3) можно решать прямыми методами, на итерациях которых, преобразуются планы задачи. Следовательно, возникает проблема соблюдения на итерациях методов всех ограничений задачи. При этом главной является проблема выполнения основного ограничения (1.2), поскольку соблюдение на n-векторе прямых ограничений (1.3) не составляет никакого труда. Таким образом, первой при разработке прямых методов решения задачи (1.1) - (1.3) возникает задача управления основным ее ограничением.

Основное ограничение (1.2) задачи (1.1) - (1.3) называется управляемым, если для любых m-вектора b и n-вектора х найдется такой n-вектор , что на векторе  будет выполняться основное ограничение:

Из последнего равенства имеем , откуда

 (1.6)

Таким образом, задача управляемости основным ограничением свелась к проблеме разрешимости относительно  системы (1.6), состоящей из т линейных алгебраических уравнений с n неизвестными .

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

 (1.7)

Таким образам, доказана

Теорема 1.2 (критерий управляемости основного ограничения) Для управляемости основного ограничения (1.2) задачи (1.1) - (1.3) необходимо и достаточно выполнения условия (1.7).

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

 (1.8)

Множество индексов , называется опорой ограничений, если для опорной матрицы  выполняется условие (1.8).

Теорема 1.3 (вторая форма критерия управляемости основного ограничения) Для управляемости основного ограничения (1.2) задачu (1.1) - (1.3) необходимо и достаточно существования хотя бы одной опоры ограничений.

Из сделанных предположений следует, что в задаче (1.1) - (1.3) существует хотя бы одна опора.

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

 (1.9)

Используя опору ограничений, равенство (1.9) запишем в виде

,

где ,

,

,

откуда следует, что

, (1.10)

где .

Таким образом, каким бы ни взять (n - m) - вектор , подсчитав по формуле (1.10) m-вектор получим n-вектор , добавление которого к любому плану х дает n-вектор , являющийся псевдопланом, т.е. вектором, на котором выполняется основное ограничение.

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

Будем считать его невырожденным, если

 (1.11)

Формула приращения целевой функции

Пусть  - некоторый (начальный) опорный план задачи (1.1) - (1.3),  - некоторый ее псевдоплан. Получим формулу приращения целевой функции (1.1) при переходе от  к  при неизменной опоре ограничений

 (1.12)

Обозначив  и воспользовавшись соотношением (1.10), из (1.12) получим

 (1.13)

Обозначим через  и  (1.14)

Введём m - вектор потенциалов :

 (1.15)

и вектор оценок  со следующими компонентами

  (1.16)

Используя (1.15), (1.16), из (1.13) получим

. (1.17)

Очевидно .

Выясним физический смысл оценок .

Положим , где k - некоторый индекс из . Компоненту  найдём из (1.10): .

Согласно (1.17) имеем

, (1.18)

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

Критерий оптимальности

Из формулы приращения (1.17) следует следующая теорема:

Теорема 1.4 (критерий оптимальности) Для оптимальности плана . в задаче (1.1) - (1.9) достаточно существования такой опоры ; что для опорного плана  выполняются соотношения

 при ;

 при ; (1.19)

 при  ,

В случае невырожденности опорного плана соотношения (1.19), являются необходимыми для оптимальности плана х.

Доказательство. Достаточность. Пусть на опорном плане  соотношения (1.19) выполняются. Рассмотрим произвольный другой план . Тогда для неопорных компонент вектора  имеем:

если , то ;

если , то , . (1.20)

Сравнивая (1.19) и (1.20), получим , . Подставив эти значения в (1.17) и учитывая при этом, что , получим