автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Алгоритмы и комплексы программ для решения класса задач об оптимальном маршруте корабля на основе теории рисков

На правах рукописи

* Н /'

Заячковский Антон Олегович

Алгоритмы и комплексы программ для решения класса задач об оптимальном маршруте корабля на основе теории рисков

05.13.18 - Математическое моделирование, численные методы и комплексы программ

5 ДЕК 2013

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 2013

005543118

Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Московский государственный университет имени М.В.Ломоносова».

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

Официальные оппоненты:

Ведущая организация:

доктор физико-математических наук, профессор, Агошков Валерий Иванович.

Зырянов Валерий Николаевич, доктор физико-математических наук, заведующий лабораторией гидродинамики Федерального государственного бюджетного учреждения науки Института водных проблем Российской академии наук,

Дмитриев Егор Владимирович, кандидат физико-математических наук, старший научный сотрудник Федерального государственного бюджетного учреждения науки Института вычислительной математики Российской академии наук.

Федеральное государственное бюджетное учреждение науки Институт вычислительного моделирования Сибирского отделения Российской академии наук.

Защита состоится 23 декабря 2013 года в 14 часов на заседании диссертационного совета Д 002.045.01 при Федеральном государственном бюджетном учреждении науки Институте вычислительной математики Российской академии наук (ИВМ РАН), расположенном по адресу: 119333, г. Москва, ул. Губкина, д. 8.

С диссертацией можно ознакомиться в библиотеке ИВМ РАН. Автореферат разослан 21 ноября 2013 года.

Ученый секретарь

диссертационного совета Д 002.045.01, доктор физико-математических наук

С У/

Бочаров Г. А.

Общая характеристика работы

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

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

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

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

Комплекс программ входит в состав Информационно-вычислительной системы (ИВС) вариационной ассимиляции данных наблюдений, разработанной в ИВМ РАН. Потребность в таких ИВС имеется во многих секторах экономики России, она обусловлена как рядом стратегических задач государства (вопросы национальной безопасности и т. д.), так и необходимостью развития национального научно-технического потенциала.

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

Научная новизна. Введен новый класс нелинейных задач - класс задач об оптимальном маршруте корабля в условиях риска: (а) стационарной угрозы при прохождении кораблем фиксированных зон, пересечение которых характеризуется определенной вероятной опасностью и возможным ущербом; (б) динамической угрозы при возможном пересечении маршрута корабля с траекторией другого объекта; (в) угрозы экологического загрязнения заданной акватории Мирового океана при движении корабля, как в природоохранной, так и в другой части бассейна.

Класс задач исследован на разрешимость (доказаны теоремы о разрешимости), найдены условия существования и единственности решения.

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

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

Практическая ценность состоит в реализации программного комплекса оперативного решения задач природоохранного направления. Программный комплекс доступен через интернет и может быть интересен различным организациям как в России, так и за рубежом (Центры морских прогнозов, структурные подразделения МЧС РФ и

Минприроды РФ, топливно-энергетических комплексов, научно-исследовательские организации и учреждения).

На защиту выносятся следующие результаты и положения:

1. Предложены новые математические модели для оптимизации маршрутов кораблей и оценки «стоимости» маршрутов в условиях различного рода рисков.

2. Исследован и численно решен класс задач об оптимальном маршруте корабля в условиях различного рода рисков.

3. Разработаны алгоритмы и комплекс программ с целью оперативного решения класса задач об оптимальном маршруте корабля в условиях различного рода рисков.

Апробация работы. Результаты диссертационной работы докладывались автором и обсуждались на научных семинарах Института вычислительной математики РАН и на конференциях и семинарах: XVII международная конференция студентов, аспирантов и молодых ученых по фундаментальным наукам «Ломоносов-2010» (Москва, 2010); Выездной семинар-школа «Состояние и перспективы мониторинга Мирового океана и морей России по данным дистанционного зондирования и результатам математического моделирования» (Таруса, 2010): Всероссийская конференция с элементами научной школы для молодежи «Проведение научных исследований в области информационно-телекоммуникаионных технологий» (Москва, 2010); Ежегодная научная конференция «Тихоновские чтения» (Москва, 2011, 2013); Международная научная конференция «Гидродинамическое моделирование Черного моря» (Севастополь, 2011); Двадцать вторая ежегодная выставка информационных технологий Softool (Москва, 2011); Научная конференция «Ломоносовские чтения» (Москва, 2011-2013); Российско-Украинская конференция «Южные моря как имитационная модель океана» (Севастополь, 2012); Международный семинар «Oil shipping safety and security: from risk assessment to smart response» (Таллин, 2012).

Публикации. Основные материалы диссертационной работы опубликованы в 11 печатных работах, среди которых 3 статьи (1 из них входит в перечень ВАК) и 8 в сборниках тезисов конференций. Также автор имеет «Свидетельство о регистрации на программу для электронных вычислительных машин (ЭВМ)», зарегистрированное в установленном порядке и приравниваемое к опубликованным работам из перечня ВАК.

Личный вклад автора. Содержание диссертации и основные положения, выносимые на защиту, отражают личный вклад автора в опубликованные работы. Подготовка к публикации полученных результатов проводилась совместно с соавторами в работах [6,7,9]. Вклад соавторов равновелик. В совместных работах [1,2,10-12] автором были предложены численные методы решения поставленных задач, написаны программные комплексы и

проведены численные эксперименты. Диссертационное исследование является самостоятельным законченным трудом автора.

Структура и объем диссертации. Работа содержит введение, пять глав, заключение, список литературы и список публикаций автора. Общий объем диссертации 108 страниц, включая 18 рисунков, 11 таблиц и список литературы из 72 наименований.

Содержание диссертационной работы.

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

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

В разделе 1.1 описан подход для измерения риска, основанный на измерении убытков от неблагоприятной ситуации. Мерой риска при таком подходе является пара: вероятность неблагоприятного события и последствия при его наступлении (ущерба):

Ущерб

Показатель риска

Ущерб = Частота События

Время Время

х Средний ущерб

События

(1)

что позволяет сравнивать ситуации с различными последствиями и вероятностями их наступления.

В разделе 1.2 введен класс задач об оптимальном маршруте корабля в условиях

риска:

• стационарной угрозы, при прохождении кораблем фиксированных зон, пересечение которых характеризуется определенной вероятной опасностью и возможным ущербом;

• динамической угрозы, при возможном пересечении маршрута корабля с траекторией другого объекта;

• экологического загрязнения заданной акватории Мирового океана, при движении корабля, как в природоохранной, так и в другой части бассейна.

В разделе 1.3 приведен анализ состояния исследуемой проблемы, показывающий, что работа является актуальной и важной, исследования соответствуют мировому уровню

В разделе 1.4 описаны методы оценки величины риска: детерминистический, вероятностный и экспертный. Изложена суть детерминистического «метода деревьев» для оценки величины риска при последовательном развитии негативных событий в ходе аварии (например, возможное столкновение танкера, перевозящего нефть, с другим объектом, характеризуемое соответствующими вероятностью и ущербом, может привести к экологическому загрязнению вследствие разлива нефти, описываемому другой парой величин вероятность-ущерб). Изложен вероятностный метод, даны оценки на объем данных, необходимых для задания параметров и характеристик распределений и методы снижения объемов входных данных путем привлечения дополнительных данных. Изложен экспертный метод и представлены матрицы качественно-количественных характеристик риска для оценки показателей риска при рассмотрении объектов с неопределенными параметрами или неизученными свойствами и при отсутствии статистических данных по объекту.

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

В разделе 2.1 введены специальные функционалы для класса задач об оптимальном маршруте корабля. Функционал стоимости отклонения корабля от предписанного маршрута имеет следующий вид:

J,(X) = j\[k,{t) I f +ko(t) I x-x^ |2jfifr,

где X(t) = (X, (t), X2 (<)) - траектория корабля в условиях возникновения риска, X""(t) -оптимальная траектория, рассчитанная заранее без учета возможного риска. Функции X,(t), X,m(t), / = 1,2 продолжены на R постоянной Л'/'ЧО) при /<0 и постоянной Х^''(Т) при t>T. Коэффициенты £„(/) и £,(/) являются гладкими функциями Vi, Аг0(0>0, £,(г)>0. Рассмотрен случай ка = 0, A-f0) = (min (t)) > 0.

Далее рассмотрен функционал, описывающий риск при прохождении кораблем фиксированных зон возможного ущерба.

Мерой риска R при подходе (1) является пара: вероятность Р неблагоприятного события и последствия О при его наступлении (ущерба). Для непрерывной случайной величины по времени возникновения критической ситуации с судном получено выражение:

R=) p(t)Q(l)dt = M[Q},

где p(t) - плотностью вероятности, а Л/[О] - математическое ожидание функции ущерба £?(<) •

Для критической ситуации, в которой вероятность возникновения аварии, например,

г , ч 1 Г U,-a,)2+U2-a2)2>|

задается по нормальному закону распределения /,,„(*) =-^ехр----1-г-*-i— с

2ка\ У 2 <т\ )

математическим ожиданием (а,,а2) и средним квадратичным отклонением (<т2,<г2), рассмотрено следующее выражение функции ущерба О от случайной величины Л':

0(.tX(/)> з J rni2(t)Q2S(j[-X(tm .

где <?(*) = , а S(-) — дельта-функция Дирака, ml2(t) - характеристический

параметр интервала, Q2 = const > 0.

Функционал риска в условиях стационарной угрозы с известными параметрами распределения при рассмотрении математического ожидания функции 0(X,X(t)) от случайного аргумента принимает вид:

J2(X) = M[Q] = J т,,2(0-а-/Л(Х(0)Л •

Образован функционал вида ./„ (Л') = Ji(X) + аЦ2(Х), где аг >. О - весовой коэффициент, задающий различные случаи задачи об оптимальном маршруте корабля.

Сформулирована задача об оптимальном маршруте корабля в условиях стационарной угрозы с известными параметрами распределения: требуется найти траекторию Л'(() е (1Г'2' (0,7"))2, такую что

- '"Г , •/„,(*(/))■ (2)

-ГеО^тгя-

.\-(1>>=.г,„„лч7>л',г)

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

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

Задан случайный процесс } Г(/) = (У|(/),У,(?)) с математическим ожиданием У(Г) = (}',(/), }'2(<)), дисперсией сг, и плотностью вероятности

г I л \ 1 { (л-.-ГДО^+О^-^СО)2"! „ .. ,

_/,(/,л-) =-- ехр--1---г—=-=- , описывающии движущиися объект, встреча

2ла, ^ 2ст, )

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

В условиях риска пересечения с траекторией другого объекта математическое ожидание ущерба вычисляется как

г о

и образован функционал вида 7„ (Л') = ./|(Л') + а,У,(Л') с весовым коэффициентом а, 0,

задающим различные случаи задачи об оптимальном маршруте корабля.

Сформулирована задача об оптимальном маршруте корабля в условиях возможного пересечения его с траекторией другого объекта: требуется найти траекторию Л'(') е ((С2'(0,7")Г, такую что

•/„(А'С)) = . , ¿ЛХ(П). (3)

Хщ1=Х,.,1,Х{Т1=Х,г

Описание задач третьего типа - в условиях риска экологического загрязнения -ведется в следующих исходных положениях. Полагаем, что судно транспортирует

пассивную примесь, которая имеет вероятность вследствие аварии распространиться по поверхности акватории. Распространение концентрации загрязняющего вещества (поллютанта) С происходит в описанной области Q из R2, г/(7,.т) = (;/,(/..г),u2(t,x)) есть заданная вектор-функция скорости течения, причем divH = 0 в Qr = Г2х[0,7"|. Функция С = С(/, х) удовлетворяет системе уравнений вида

(и,V)C-V-fjVC + Л(С) = f„p(t,x) в Пг,

cL=o, С 1^=0,

где L действует из W(Пг) в W\ÇiT), 1Г(ПГ) = L2(О,Г;IГ2(П) 1 и lV(Cïr)sL2\ 0,Г,1У2'\П)

и задача об отыскании C(t,x) рассматривается в соответствующей обобщенной постановке.

Функция f„p(t,x) описывает точечный источник мощности т = const > 0, движущийся по траектории X(t) = (Xl(t),X2(t)), которая подлежит определению, т.е. f„p(t,x) ее т ■ SU-QSix-XU)).

При таком экологическом загрязнении рассматривается функционал, задающий возможный ущерб

Q(X) = Ь- J C(l,x)z(x)dCidt,

пг

где b - размерностный коэффициент, х(') — весовая функция, задающая «охраняемую» область П.

Для решения сопряженной задачи с формально сопряженным оператором в С1Т :

|лг*

L'C' =-—— (и, V)C - V-//VC + Л(С') = z(*h t < т ct

С' U= 0, С'(х, t) = 0, при О Т справедливо равенство

Q(X) = Ь J C(t, x)x(x)dCktt = Ь J C-L'C'dCk/t =

£!, Пг

= b j" LCC'dQdt = bmC\t0,X(/0)).

"r

Поскольку t0 - вероятностная величина, то, зная ее плотность распределения p(t), можно перейти от рассмотрения Q(X) к его математическому ожиданию и в результате имеем:

x Т

R = M[Q] = | p(t ) b-mC'(I,X{t ))dt = | p[tybrm-C'(t,X(t))dl.

Сформулирована задача об оптимальном маршруте корабля в условиях риска возможного экологического загрязнения: требуется найти траекторию Л'(') £ ('(ч (О.Г))2, такую что

Л (Л'(-))= . ¡пГ , JAX(t))= . Ы . + (4)

а, >0 - весовой коэффициент.

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

Если Л'(() есть решение поставленной задачи минимизации (2) (или (3), или (4)), тогда оно необходимо удовлетворяет вариационному уравнению (уравнение Эйлера, необходимое условие оптимальности) и при наличии достаточной гладкости у X и Л""' (Л',0> е(1Г22(0,Г))2) из вариационного уравнения получаем классическую форму вариационной задачи:

Для стационарной угрозы: г] ( с!( V -

А'(0) = А'да,А'(Г) = А'(ГГ Для динамической угрозы:

Г^(А'(<) (1(Х ~л""1})'+ Х) = 'е (0'Г)'

[А'(0) = Х(0„Х(7-) = А'(7,. Для угрозы экологического загрязнения:

-—Ш~Л") | + = 0, * е(0,Г),

Л ^ Л ^

А'(0) = А'(О),А'(Г) = Х(П.

В разделе 2.3 исследованы вопросы, связанные с разрешимостью задач (2), (3) и (4). По вопросам разрешимости доказаны следующие теоремы:

Теорема 1 (о разрешимости задачи об оптимальном маршруте корабля в условиях стационарной угрозы с известными параметрами распределения):

Пусть выполнено условие аг < £,<0) [ — ] . Тогда в любой конечной окрестности

5 = {А'е (1^(0, Г))2 :||А'-А'(0) II „ ^г<оо) вектор-функции Хт существует

внутренняя точка Хб5, в которой Ju имеет абсолютный минимум и X удовлетворяет

о

уравнению У (Л'), А) = О МИ в ((Г2' (О, Г))2, т. е. X является решением задачи (2).

Теорема 2 (о разрешимости задачи об оптимальном маршруте корабля в условиях возможного пересечения его с траекторией другого объекта):

Пусть выполнено условие а> ' < А:.(0> Г — | . Тогда в любой конечной окрестности па\ \Т)

о

5" = {X е (О, Т))2: IIX - Хф) II л вектор-функции А"01 существует

(И; (О,Г))=

внутренняя точка ХеХ, в которой J,r¡ имеет абсолютный минимум и X удовлетворяет

о

уравнению У (Х),И) = О V/; е (((','(0,7'))2, т. е. X является решением задачи (3).

Теорема 3 (о разрешимости задачи об оптимальном маршруте корабля в условиях риска возможного экологического загрязнения):

Пусть выполнено условие 0 < А,10' ^^ + 2-а1-ЬпгЛ. Тогда в любой конечной

о

окрестности 5 г {X е ((К,1 (О, Г))2: || Л" - Л'(0> || „ вектор-функции Л'(0>

(Ц-,Чо.г1)=

суи/ествует внутренняя точка X е. Б, в которой Jщ имеет абсолютный минимум и X

о

удовлетворяет уравнению {Ха(Х),И) = 0 \/Ле(Щ'(0,Т))2, т.е. X является решением задачи (4).

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

В разделе 3.1 представлены итерационные методы решения и аппроксимация класса вариационных задач оптимального управления. Сначала рассматривается система (5) и задача трактуется как задача о возмущениях с малым параметром е = ■ Полагается

= и (Л = сош1 > О. Ищется х в виде х = х(0)+ ех{"+ £2хт+... Подставляя

х такого вида в систему, получаются задачи для {.г"1 }. Так в частности, заключается, что л'0' =0, и для л1" получена задача вида:

при /е (О, Г),

при / = 0, ( = Г.

Когда невозможно интерпретировать задачу как задачу возмущений с малым параметром, предлагается альтернативный итерационный метод на примере двух оставшихся типов задач.

Уравнения

)+ъ-ОуШ*+Л"0>)=0" ]+«.^«-мо^са,дг+л"0')=о

рассматриваются в виде

В итоге получаются следующие линеаризованные уравнения:

*dx | , 4 * . , 1+1 А* ч

или в частном случае:

(0 \ + g(xl') + (xм-x^■)gU) = 0, (6)

* ЧЬтрЦ'уЧС'О*,хк + Х{т) + (а1-Ь-тр(1"уАС'(1к,хк + Лг(01))(д:Л+|-л' ).

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

В разделе 3.3 исследована сходимость итерационных методов. Доказана

Теорема 4 (о сходимости итерационного метода): Пусть = {.х И х-Х\\ ,,<у} и при некоторых у,у,,у2,0< у,О ^ у,,у, <оо, щ,и2&С1у, у, 2 = у,у2 , и12 = пип{у,у^2} выполнены условия i , при х €е и i ^щ)-g(u2)-gXu1)(u^-и2У\, <у,н и2-«,112„ при

н,,и2 Тогда при еитерационный процесс (6) сходится с ог/енкой погрешности

I хк -Л11 „ «^(у, ,11 х°-М „)2'.

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

В разделе 4.1 описан программный комплекс по расчету оптимального маршрута корабля. Программный комплекс имеет модульную структуру и получает входные параметры через управляющие файлы.

В разделе 4.2 представлены результаты численных экспериментов на модельных акваториях и на формальных данных. В 12 экспериментах проведены тесты для трех типов задач, представлены численные результаты: падение нормы невязки, значения функционалов риска и минимизации, количество итераций.

В разделе 4.3 созданный программный комплекс применен для расчетов на конкретных примерах и акваториях. Проведено 9 расчетов, представлены соответствующие результаты (см. рис. 1).

В пятой главе описаны предложения по практическому использованию полученных результатов и внедрению разработок в научно-образовательный процесс и реальный сектор экономики: получено Свидетельство о государственной регистрации «Программы расчета задачи о минимизации риска загрязнения охраняемой акватории Балтийского моря»; предоставлен доступ к системе расчетов через интернет по средством удаленного веб-сервиса. Через удаленный доступ система нахождения оптимального маршрута корабля в условиях различного рода рисков планируется к внедрению в Систему принятия решений Международного проекта «Минимизация рисков транспортировки нефти на основе

требований общей безопасности и безопасности стратегий» (проект MIMIC), а также в различные заинтересованные учреждения и организации (Центры морских прогнозов, структурные подразделения МЧС РФ и Минприроды РФ, топливно-энергетических комплексов, научно-исследовательские организации и учреждения).

В разделе 5.1 приведено описание государственной регистрации комплекса программ и представлено полученное свидетельство о такой регистрации.

В разделе 5.2 в рамках инициативы по сотрудничеству с реальным сектором экономики и коммерческими предприятиями, приведено соглашение с Малым инновационным предприятием «Общество с ограниченной ответственностью „Аквалог"»,

~———-—~—м

(а)

(б)

: •' •; •

•____ i

(в) (г)

Рис. 1. Расчет оптимального маршрута при угрозе экологического загрязнения: (а) скорости поверхностного течения по модели гидротермодинамики ИВМ РАН; (б) решение сопряженной задачи, которое характеризует чувствительность охраняемой области к экологическому воздействию, т. е. показывает, как появление поллютанта в определенной точке акватории повлияет на загрязнение в интересуемой прибрежной зоне; (в) оптимальный маршрут в условиях экологического риска (красным), предварительный маршрут (синим) по данным портала http://wvvw.marinetraffic.com; (г) общий вид решения задачи по расчету оптимального маршрута корабля.

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

В разделе 5.3 рассказано про доступ к системе расчетов через интернет рамках интерфейса существующей в Институте вычислительной математики РАН Информационно-вычислительной системы.

В разделе 5.4 рассказано про вклад в международный проект «Минимизация рисков транспортировки нефти на основе требований общей безопасности и безопасности стратегий», в котором принимают участие ведущие научные организации Финляндии, Эстонии, Швеции и России, и планируемую интеграцию в систему принятия решений проекта MIMIC.

Заключение содержит основные результаты и выводы диссертации.

Основные результаты работы

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

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

• стационарной угрозы при прохождении кораблем фиксированных зон, пересечение которых характеризуется определенной вероятной опасностью и возможным ущербом;

• динамической угрозы при возможном пересечении маршрута корабля с траекторией другого объекта;

• угрозы экологического загрязнения заданной акватории Мирового океана при осуществлении проводки корабля в этой или другой частях бассейна.

Введены и описаны математические модели - функционалы риска, когда показатель риска зависит как от вероятности опасности рассматриваемого события, так и от величины ожидаемых последствий (ущерба). Задачи об оптимальном маршруте корабля сформулированы как задачи оптимального управления на минимизацию функционала-функционала риска.

2. Класс задач исследован на разрешимость, найдены условия существования и единственности решения, доказаны теоремы о разрешимости.

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

3. Решение класса задач реализовано в виде программного комплекса. Проведены тестовые испытания программного комплекса.

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

моря.

Получено Свидетельство №2013619308 от 01.10.2013 г. о государственной регистрации программы для ЭВМ «Программа расчета задачи о минимизации риска загрязнения охраняемой акватории Балтийского моря», выданное федеральной службой по интеллектуальной собственности.

Публикации по теме диссертации

1. Агошков В. И. Заячковский А. О. Исследование и алгоритмы решения задачи об оптимальном курсе корабля на основе теории рисков при дистанционном зондировании опасностей // Современные проблемы дистанционного зондирования Земли из космоса. 2012. Т.9. №3. С. 9-17.

2. Свидетельство №2013619308 от 01.10.2013 г. о государственной регистрации программы для ЭВМ «Программа расчета задачи о минимизации риска загрязнения охраняемой акватории Балтийского моря», выданное федеральной службой по интеллектуальной собственности.

3. Заячковский А. О. Моделирование экологических рисков загрязнения поверхностных вод океанов и морей на основе теории сопряженных уравнений // Сборник статей молодых ученых факультета ВМК МГУ. Выпуск 7. М.: Издательский отдел Факультета ВМиК МГУ им. М.В. Ломоносова; МАКС Пресс, 2010. С. 91-98.

4. Агошков В. И., Заячковский А. О. Исследование и алгоритм решения одной нелинейной задачи теории рисков // Экологическая безопасность прибрежной и шельфовой зон и комплексное использование ресурсов шельфа. Вып. 26. Том 2. Севастополь: МГИ НАНУ. 2012. С. 339-351.

5. Заячковский А. О. Математическое моделирование экологических рисков загрязнения вод океанов и морей // Сборник тезисов лучших дипломных работ 2010 года. М.: Издательский отдел Факультета ВМиК МГУ им. М.В. Ломоносова; МАКС Пресс, 2010. С. 22-23.

6. Агошков В. И., Гиниатуллин С. В., Гусев А. В., Залесный В. Б., Захарова Н. Б., Заячковский А. О., Лебедев С. А., Пармузин Е. И., Шутяев В. П. Теоретические основы

разработки Специализированных информационно-вычислительных систем вариационной ассимиляции данных наблюдений // Сборник тезисов Всероссийской конференции с элементами научной школы для молодежи «Проведение научных исследований в области информационно-телекоммуникаионных технологий». Москва, 2010. С. 121-122.

7. Заячковский А. О., Агошков В. И., Гиниатуллин С. В., Захарова Н. Б., Пармузин Е. И., Семененко А. Ю. Специализированная информационно-вычислительная система вариационной ассимиляции данных наблюдений в моделях гидротермодинамики океанов и море // Сборник тезисов Всероссийской конференции с элементами научной школы для молодежи «Проведение научных исследований в области информационно-телекоммуникаионных технологий». Москва, 2010. С. 123-124.

8. Заячковский А. О. Экологические риски и выбор оптимального маршрута судна // Тезисы докладов научной конференции «Тихоновские чтения-2011». М.: Издательский отдел факультета ВМиК МГУ имени М. В. Ломоносова; МАКС Пресс, 2011. С. 39-40.

9. Агошков В. И., Ассовский М. В., Гиниатулин С. В., Гусев А. В., Захарова Н. Б., Заячковский А. О., Лебедев С. А., Пармузин Е. И. Специализированная Информационно-вычислительная система вариационной ассимиляции данных наблюдений в моделях гидротермодинамики океанов и морей // Сборник тезисов Всероссийской конференции «Проведение научных исследований в области обработки, хранения, передачи и защиты информации». Москва, 2011. С. 16-17.

10. Заячковский А. О., Агошков В. И. Исследование и алгоритмы решения класса задач об оптимальном курсе корабля на основе теории рисков // Тезисы докладов научной конференции «Ломоносовские чтения-2011». М.: Издательский отдел факультета ВМиК МГУ имени М. В. Ломоносова; МАКС Пресс, 2011. С. 45-46.

11. Агошков В. И., Заячковский А. О. Расчет оптимального маршрута судна, минимизирующего риск пересечения с траекторией другого объекта // Тезисы докладов научной конференции «Ломоносовские чтения-2013». М.: Издательский отдел факультета ВМиК МГУ имени М. В. Ломоносова; МАКС Пресс, 2013. С. 42-43.

12. Агошков В. И., Заячковский А. О. Расчет оптимального маршрута судна в условиях риска экологического загрязнения // Тезисы докладов научной конференции «Тихоновские чтения-2013». М.: Издательский отдел факультета ВМиК МГУ имени М. В. Ломоносова; МАКС Пресс, 2013. С. 66-67.

Подписано в печать: 20.11.2013 Объем: 1,0 п.л. Тираж: 110 экз. Заказ № 172 Отпечатано в типографии «Реглет» 119526, г. Москва, пр-т Вернадского, д. 39 (495)363-78-90; \Y\vw.reglet.ru

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Московский государственный

университет имени М.В.Ломоносова»

На правах рукописи

04201 451 991

УДК 519.6

Заячковский Антон Олегович

Алгоритмы и комплексы программ для решения класса задач об оптимальном маршруте корабля на основе теории рисков

Специальность 05.13.18 — Математическое моделирование, численные методы

и комплексы программ

Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель: Д. ф.-м. н., профессор Агошков В. И.

Москва 2013 г.

СОДЕРЖАНИЕ

Введение...............................................................................................................................4

Глава 1. Управление рисками как инструмент теории принятия решений.......12

1.1 Элементы теории рисков......................................................................................12

1.2 Класс задач управления рисками.........................................................................16

1.3 Анализ состояния исследуемой проблемы.........................................................19

1.4 Методы оценки величины риска..........................................................................23

Глава 2. Математические модели для решения класса задач об оптимальном маршруте корабля...........................................................................................................37

2.1 Математическая постановка класса задач об оптимальном маршруте корабля в условиях риска.............................................................................................................38

2.2 Решение класса задач оптимального управления на отыскание минимума функционала....................................................................................................................48

2.3 Разрешимость исследуемого класса задач..........................................................50

Глава 3. Численные методы решения класса задач об оптимальном маршруте корабля .............................................................................................................................61

3.1 Итерационные методы решения и аппроксимация класса вариационных задач оптимального управления.............................................................................................62

3.2 Решение конечно-разностной аппроксимационной задачи..............................65

3.3 Сходимость итерационных методов....................................................................69

Глава 4. Разработка программного комплекса и проведение численных экспериментов..................................................................................................................72

4.1 Программный комплекс по расчету оптимального маршрута корабля...........72

4.2 Тестирование и оценка эффективности работы программ...............................73

4.3 Численные расчеты на океанографических данных..........................................81

Глава 5. Предложения по использованию полученных результатов...................93

5.1 Государственная регистрация программы..........................................................93

5.2 Сотрудничество с Малым инновационным предприятием «Общество с ограниченной ответственностью „Аквалог"».............................................................95

5.3 Доступ к системе расчетов через интернет.........................................................97

5.4 Интеграция в систему принятия решений проекта MIMIC..............................99

Заключение.....................................................................................................................101

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

Введение

Настоящая работа посвящена разработке алгоритмов и программ для решения класса задач об оптимальном маршруте корабля на основе теории рисков.

Такой класс задач обусловлен следующими факторами: развитие новых технологий, увеличение объемов промышленного и сельскохозяйственного производства, расширение сети транспортных систем, в том числе морских транспортных систем, и систем передачи энергии и энергоносителей — и сопровождаются ростом техногенной нагрузки на биосферу. Следствием этого являются все чаще возникающие чрезвычайные ситуации, аварии и катастрофы, характеризующиеся значительными материальными, социальными и экологическими последствиями [1, 2]. При этом, как показали события последних десятилетий, реализуются считавшиеся ранее весьма маловероятными крупные аварии и катастрофы на различных объектах высокой технологии (примерами могут служить нефте- и газопроводы, атомные электростанции, химические комбинаты и т. д. [3, 4]). Стала очевидной необходимость в разработке новых подходов к обеспечению безопасности природной среды, в т. ч. на основе теории рисков. Именно поэтому в странах с развитой экономикой актуальной стала задача исследования рисков. Основная цель таких исследований — вырабатывать для лиц, ответственных за принятие решений, рекомендации по эффективным мерам управления рисками [5, 6]. В связи с этим появляется потребность в руководстве по принятию решений, которые упрощали бы этот процесс и придавали решениям большую надежность. Система оценки экологического риска призвана в первую очередь предоставить для лица, ответственного за принятие решений, критерии, руководящие им при выборе решения.

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

на этих маршрутах стали насущной социальной потребностью. Оптимизация маршрута и условий плавания заключается в одновременном учете многих факторов, влияющих на скорость и сохранность судна, а также на обеспечение экологической безопасности окружающей среды. Прохождение заданного маршрута можно осуществить многими путями и отнюдь не самый короткий путь может оказаться оптимальным. Реализация курса движения должна предусматривать формирование пути следования, ведущего в пункт назначения за кратчайшее время и с учетом навигационных опасностей. Чтобы найти оптимальный из возможных маршрутов движения, необходимо решить задачи поиска наименьших значений специальных функционалов [7, 8, 9, 10], включающих функционалы стоимости отклонения корабля от предписанного маршрута, и составляющих, представляющих собой различного рода риски. Исследование и алгоритмы решения таких задач должны базироваться с одной стороны на методах оптимального управления, а с другой - на теории случайных функций и теории рисков [11].

На возможное изменение курса корабля влияет ряд факторов. Так в настоящее время актуальной стала проблема появления «зон возможных опасностей» для корабля, зон нападения на суда морских пиратов, появления фиксированного объекта по курсу, представляющего опасность для корабля и т. д. При следовании кораблем «предварительным оптимальным курсом» возможно также появления информации о циклоне с заданной его траекторией, информации о пересечении с курсом другого корабля и др. В связи с этим возникает проблема корректировки курса корабля, т. е. поиск нового оптимального маршрута, с целью уменьшения риска его пересечения с траекторией циклона или другого объекта, но одновременно минимизируя издержки, вызванные изменением курса корабля. Также актуальной является проблема уменьшения риска экологического загрязнения заданной акватории при следовании корабля выбранным курсом в силу возникновения опасности [3, 12].

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

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

Комплекс программ входит в состав Информационно-вычислительной системы (ИВС) вариационной ассимиляции данных наблюдений, разработанной в ИВМ РАН. Потребность в таких ИВС имеется во многих секторах экономики России, она обусловлена как рядом стратегических задач государства (вопросы национальной безопасности и т. д.), так и необходимостью развития национального научно-технического потенциала.

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

Научная новизна. Введен новый класс нелинейных задач - класс задач об оптимальном маршруте корабля в условиях риска: (а) стационарной угрозы при прохождении кораблем фиксированных зон, пересечение которых характеризуется определенной вероятной опасностью и возможным ущербом; (б) динамической угрозы при возможном пересечении маршрута корабля с траекторией другого объекта; (в) угрозы экологического загрязнения заданной акватории Мирового океана при движении корабля, как в природоохранной, так и в другой части бассейна.

Класс задач исследован на разрешимость (доказаны теоремы о разрешимости), найдены условия существования и единственности решения.

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

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

Практическая ценность состоит в реализации программного комплекса оперативного решения задач природоохранного направления. Программный комплекс доступен через интернет и может быть интересен различным организациям как в России, так и за рубежом (Центры морских прогнозов, структурные подразделения МЧС РФ и Минприроды РФ, топливно-энергетических комплексов, научно-исследовательские организации и учреждения).

На защиту выносятся следующие результаты и положения:

1. Предложены новые математические модели для оптимизации маршрутов кораблей и оценки «стоимости» маршрутов в условиях различного рода рисков.

2. Исследован и численно решен класс задач об оптимальном маршруте корабля в условиях различного рода рисков.

3. Разработаны алгоритмы и комплекс программ с целью оперативного решения класса задач об оптимальном маршруте корабля в условиях различного рода рисков.

Апробация работы. Результаты диссертационной работы докладывались автором и обсуждались на научных семинарах Института вычислительной математики РАН и на конференциях и семинарах: XVII международная конференция студентов, аспирантов и молодых ученых по фундаментальным наукам «Ломоносов-2010» (Москва, 2010); Выездной семинар-школа «Состояние и перспективы мониторинга Мирового океана и морей России по данным дистанционного зондирования и результатам математического моделирования» (Таруса, 2010); Всероссийская конференция с элементами научной школы для молодежи «Проведение научных исследований в области информационно-телекоммуникаионных технологий» (Москва,

2010); Ежегодная научная конференция «Тихоновские чтения» (Москва, 2011, 2013); Международная научная конференция «Гидродинамическое моделирование Черного моря» (Севастополь, 2011); Двадцать вторая ежегодная выставка информационных технологий Softool (Москва, 2011); Научная конференция «Ломоносовские чтения» (Москва, 2011-2013); Российско-Украинская конференция «Южные моря как имитационная модель океана» (Севастополь, 2012); Международный семинар «Oil shipping safety and security: from risk assessment to smart response» (Таллин, 2012).

Публикации. Основные материалы диссертационной работы опубликованы в 11 печатных работах, среди которых 3 статьи (1 из них входит в перечень ВАК) и 8 в сборниках тезисов конференций. Также автор имеет «Свидетельство о регистрации на программу для электронных вычислительных машин (ЭВМ)», зарегистрированное в установленном порядке и приравниваемое к опубликованным работам из перечня ВАК.

Личный вклад автора. Содержание диссертации и основные положения, выносимые на защиту, отражают личный вклад автора в опубликованные работы. Подготовка к публикации полученных результатов проводилась совместно с соавторами в работах [13, 14, 15]. Вклад соавторов равновелик. В совместных работах [16, 17, 18, 19, 20] автором были предложены численные методы решения поставленных задач, написаны программные комплексы и проведены численные эксперименты. Диссертационное исследование является самостоятельным законченным трудом автора.

Структура и объем диссертации. Работа содержит введение, пять глав, заключение, список литературы и список публикаций автора. Общий объем диссертации 108 страниц, включая 18 рисунков, 11 таблиц и список литературы из 72 наименований.

Содержание работы. В первой главе представлены элементы теории рисков, даны определения и понятия, описана ситуация риска и факторы (параметры), на нее влияющие. Особое внимание уделено статистически определенным переменным и искусственно рандомизованным нестахостическим переменным, описан подход,

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

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

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

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

В четвертой главе описан программный комплекс расчета оптимального маршрута судна, алгоритмы, используемые в программе, модульная структура и проведены результаты тестирования и оценка эффективности работы программ для различных сценариев: стационарной угрозы, динамической угрозы с заданной траекторией и риска загрязнения заданной подобласти акватории загрязняющим веществом; представлена рабочая версия программного комплекса для применения в практических реалиях, когда за стационарную угрозу принимается риск нападения на судно морских пиратов с вероятным местом нападения, за динамическую угрозу принимается риск пересечения корабля с траекторией тропического циклона, при риске загрязнения заданной подобласти акватории исследованы прибрежные зоны акватории Балтийс�