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

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

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

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

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

Рассмотрим множество достижимости системы (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], и принимаются соответственно за и .