«Решение двухточечных задач линейного быстродействия» - Дипломная работа

Содержание

Введение 3

1. Задача линейного быстродействия в Rn 5

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

1.2. Многошаговый алгоритм корректировки опорной гиперплоскости 6

1.3. Пояснения к алгоритму 11

2. Реализация алгоритма 13

2.1. Описание программы 13

2.2. Результаты вычислительных экспериментов 13

2.3. Программа на языке Паскаль 14

Литература 34

Приложение 35

Введение

Тема моего исследования – решение двухточечных задач линейного быстродействия. Первые алгоритмы решения задачи линейного быстродействия были предложены Н.Н. Красовским. Далее Л. Нейштадт и Н.Е. Кирин предложили алгоритмы, на основе геометрической интерпретации условий оптимальности, сделанной Д. Лассалем. В них решение задачи быстродействия сводилось к поиску

Здесь определяется из условия

,

- решение системы

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

Рассмотренный алгоритм опирается на идею многошаговости, предложенную Н.Е. Кириным и понимаемую как использование при получении очередного приближения дополнительных точек, найденных на предыдущих итерациях. В данной работе использован новый способ выбора дополнительных точек, позволяющий более полно использовать идею многошаговости. Многошаговость отличает данный алгоритм от алгоритмов других авторов (Д.Х. Итона - Л.У. Нейштадта, Э.Д. Фаддена, - Э.Г. Гильберта Б.Н., Пшеничного, - Л.А. Соболенко), также основанных на методе корректировки опорной гиперплоскости, но являющихся одношаговыми.

Скорость сходимости рассмотренного алгоритма и алгоритма Б.Н. Пшеничного – Л.А. Соболенко выше, чем у алгоритма Э.Д. Фаддена и Э.Г. Гильберта, который в свою очередь сходится быстрее, чем алгоритм Нейштадта – Итона. Число итераций в предлагаемом алгоритме и алгоритме Пшеничного – Соболенко близко, однако трудоемкость одной итерации в алгоритме Пшеничного – Соболенко в три раза выше, чем в предлагаемом.

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

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

Выдержка из текста работы

1. Задача линейного быстродействия в Rn

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

В управляемой линейной системе

(1)

(2)

требуется найти минимальное числа о<*Т и управление u*()U, при которых

. (3)

Здесь А(), B(), d() – заданные (NxN) (Nxr) (Nx1) матрицы с кусочно-непрерывными компонентами (0,T]; U – множество управлений – вектор - функций u=u()=(и1(),u2(),…,ur()), и почти при всех [0,T]

(4)

Определение. Множеством достижимости G(t) системы (1), (2) называется множество точек xRn из которых можно попасть в точку x0 двигаясь по траекториям системы за время t

Рассмотрим множество достижимости системы (1), (2) в момент >0

G()={x(u,):uU} (5)

Тогда задачу о поиске времени быстродействия * можно сформировать следующим образом: найти наименьший момент времени *>0 при котором множество G(*) содержит точку . Из этого определения числа * следует, что при всех <*.

Пусть 1>0 – некоторый момент времени. Согласно свойству выпуклости достижимого множества линейных систем, если , то существует опорная к множеству G(1) гиперплоскость отделяющая точку от G(1). На этом свойстве и базируется метод разделяющих гиперплоскостей, в котором строится последовательность {k}), k=1,2,3,… такая, что

1<2<3<…* (6)

Опишем общую схему построения последовательности {k}. Пусть удалось установить, что k<0. Тогда приближение k+1 определяется следующим образом:

1) находится направление нормали гиперплоскости, строго разделяющей точку и множество G(k). Обозначим нормаль Гk;

2) строится опорная к G(k) гиперплоскость с нормалью Гk;

3) построенная опорная гиперплоскость непрерывно переносится в опорную плоскость множества G() при >k и определяется первый момент встречи ее с точкой . Этот момент и принимается за k+1.

В силу непрерывности семейства множеств {G()} по  можно утверждать, что построенная согласно этой схеме последовательность обладает свойством (6) и при достаточной строгости разделения будет k*. Известно, что в поставленной задаче для существования оптимального управления достаточно, чтобы существовало хотя бы одно допустимое управление, т.е. чтобы равенство (3) было бы возможно при некотором * не обязательно минимальным.

1.2. Многошаговый алгоритм корректировки опорной гиперплоскости

Конкретизируем описанную в п.1.1. схему построения последовательности {k}. Одной из важных частей этой схемы является нахождение нормали разделяющей гиперплоскости. Ясно, что если нормаль на шаге k позволяет достаточно строго отделите точку от множества достижимости G(k), то обеспечит хорошее "продвижение" по времени в п.З указанной схемы. В качестве нормали, разделяющей гиперплоскости на шаге k, k=2,3,…, берется антиградиент функции расстояния от точки до множества G(k). При этом достаточно уметь находить этот антиградиент приближенно.

Пусть известны нижняя оценка k времени оптимального быстродействия и точки х(j)G(k) .

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

(7)

Если , то задача быстродействия решена: 0=k и оптимальное управление u0() то, для которого

.

2. Пусть . Построим опорную гиперплоскость с нормалью , т.е. решим задачу определения точки такой, что

(8)

согласно принципу максимума Л.С. Понтрягина, управление , реализующее решение вариационной задачи (8), находится по формуле

, (9)

где (), [0,k] – решение задачи Коши

(10)

bi i-ый столбец матрицы В().

3. Если опорная гиперплоскость является разделяющей, то перенесем ее непрерывным образом при  >k c этой целью от =k интегрируем систему (10) и систему (1) (2) с начальным условием и управлением , определяемым согласно соотношению (9) при  >k. Интегрирование ведется пока опорная гиперплоскость разделяет точку и множество G(), т.е. пока не будет выполнено неравенство

.

Этот момент * и принимается за k+1.

4. Для того, чтобы вновь перейти к п.1, необходимо построенные точки и включить в базис {x(j)} выпуклой оболочки Vk+1, заменив в ней соответственно наиболее близкую и наиболее удаленную от точки.

Алгоритм называется многошаговым ввиду того, что в п.1 при поиске точки используется несколько дополнительных точек х(j), принадлежащих достижимому множеству, хотя теоретически для доказательства сходимости алгоритма достаточно иметь всего две точки (в этом случае алгоритм называется одношаговым). Использование дополнительных точек {х(j)}, , позволяет значительно, повысить скорость сходимости алгоритма.

Приведем подробное описание рабочего варианта многошагового алгоритма, основанного на методе разделяющих гиперплоскостей с учетом заданной  точности выполнения равенства (3).

Опишем k-ый шаг. Пусть известны

k0, ukU, xk=x(uk,k), u(j)U, x(j)=x(u(j),k),

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

1. Интегрируем на [k,0] cиcтeму

(11)

с начальным условием

и запоминаем управление

(12)

где bi – i-ый столбец матрицы В().

Интeгpиpуeм на [0,k] систему (1), (2) при .Пoлученную точку обозначим . Если , где  заданная точность попадания в , то  - решение задачи получено: . Иначе, если скалярное произведение

то положив

.

Переходим к операции 5. Если (k)<0, то обращаемся к следующей операции.

2. Проводим уточнение числа k. Интегрируем по возрастанию  от =k системы (1) и (11) с начальными условиями , (k)=-xk при управлении, определяемом по формуле (12). Интегрирование ведется до первого момента *>k, при котором выполнится неравенство

.

Этот момент принимается за k+1. Если , то положив ,  - решение задачи получено.

3. Интегрируем систему (1) на [k,k+1] с начальными условиями x(k)=xk, x(k)=x(j), , при некоторых (можно произвольных) управлениях uU. Полученные в результате точки обозначим через и , а соответствующие им управления через и .

4. Построим опорную к множеству G(k+1) гиперплоскость нормалью . С этой целью обратимся к п.1 алгоритма и решим задачу

5. На выпуклой оболочке Vk+1 векторов , найдем точку ближайшую к и соответствующее ей управление . Если , то  - решение задачи найдено: . Если , то заменив в базисе наиболее удаленную точку точкой и положив

,

переходим к п.1 алгоритма.

Для выбора точки в п.5 алгоритма нужно решить задачу квадратичного программирования (7) на выпуклой оболочке векторов . Для ее приближенного решения применим методы спуска в направлении вершин оболочки Vk+1. Положив , построим последовательность точек

так чтобы

(13)

Решив задачу (15), получим

(14)

где jn. – число из отрезка [0,1], ближайшее к :

(15)

Если

,

то полагаем jn=1. Управление, соответствующее точке zjn. в силу линейности системы. (1) вычисляется по формуле

(16)

.

В результате найдем вектор zsn и соответствующее ему управление usn()U. Взяв в качестве z0n+1 вычисленный вектор zsn и положив n=n+1, u0n()=usn-1 (), [0,k+1], цикл повторяем до тех пор, пока при некотором n=m не будет выполнено неравенство

,

где k – заданная точность выхода на шаге. Полученная точка zsm и управление usm(), [0,k+1], и принимаются соответственно за и .

Заключение

Программа состоит из 2 функций и 7 процедур.

С помощью функции dif описывается система дифференциальных уравнений.

Функция norma вычисляет расстояние от заданной точки до .

Процедура rung интегрирует сопряженную систему дифференциальных уравнений методом Рунге-Кутта четвертого порядка и вычисляет управление.

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

Процедура punkt1 строит опорную гиперплоскость к множеству G(k) с нормалью –xk(k) и находит опорную точку .

В процедуре punkt2 находится момент времени k+1 – новое приближение времени быстродействия.

Процедура punkt3 «подтягивает» точки x(j)G(k) в множество G(k+1).

Процедура punkt5 находит точку , ближайшую к и находит соответствующее управление.

Процедура zamena заменяет в базисе {x(j)} самую близкую точку точкой , и самую удаленную точку – точкой .

Список литературы

1. Кирин Н.Е. Об одном численном методе в задаче о линейных быстродействиях// Методы вычислений, Л.: 1963, с. 67-74.

2. Красовский Н.Н. Об одной задаче оптимального регулирования//Прикладная математика и механика, 1957, т. 21, вып. 5 с. 670-677.

3. Морозкин Н.Д. Оптимальное управление процессами нагрева с учетом фазовых ограничений: Учебное пособие/ Изд-е БГУ. – Уфа, 1997, с. 42-50.

4. Пшеничный Б.Н., Соболенко Л.А. Ускоренный метод решения задачи линейного быстродействия// Журнал вычислительной математики и вычислительной физики, 1968, т. 8, №6. с. 1345-1351. ч

5. Fadden E.J., Gilbert E.G. Computational Aspects of the Time-Optimal Control Problem//Computing methods in optimization problems. Balakrichnan A.(ed), 1964, p. 167-182.

6. La Salle J.R. The time optimal control problem// reprinted from: Contribution to the Theory of Nonlinear oscillations. Baltimore, 1959, v. 5.-30 p.

7. Neustadt L.W. Sunthesis of time Optimal Control Systems//Math. Anal. and Appl. 1960, v. 1, №4, p. 484-500.

Примечания

К работе прилагается все исходники. Есть приложения.