Метод криволинейного поиска глобального экстремума в задаче оптимального управления

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ В ЗАДАЧАХ ДИНАМИКИ И УПРАВЛЕНИЯ

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

Работа выполнена при частичной финансовой поддержке РФФИ грант № 08-07-00163-а и президентской программы «Ведущие научные школы РФ» грант № НШ-1676.2008.1.

БИБЛИОГРАФИЯ

1. Томилин, В.В. Использование ГИС в муниципальном управлении / В.В. Томилин, Г.М. Нориевская // Практика муниципального управления. - 2007. - № 7.

2. Иванникова, А.Д. Геоинформатика / А. Д. Иванникова, В.П. Калугина, АН. Тихонова, В .Я. Цветкова. - М.: МАКС Пресс, 2001. - 349 с.

3. Берлянт, А.В. Геоинформатика. Толковый словарь основных терминов / А.В. Берлянт, С.К. Кошкарева. - М.: ГИС-Ассоциация, 1999. - 203 с.

4. Постановление мэра г. Иркутска от 14.01.2002 № 031-06-26/2 «Об упорядочении адресов объектов недвижимости на территории г. Иркутска»._

5. Бычков, И.В. Применение ГИС- и ВЕБ-технологий для создания интегрированных информационно-аналитических систем / И.В. Бычков, Е.С. Фереферов, А.Е. Хмельнов // Вычислительные технологии. - 2007. - Т. 12, спец. вып. № 3. - С. 5-20.

6. Гаченко, А.С. Муниципальная информационная система обеспечения градостроительной деятельности / А.С. Гаченко, Г.М. Ружников, Е.С. Фереферов, А.Е. Хмельнов // Вычислительные технологии. - 2008. - Т. 13, спец. вып. № 1. - С. 11-16.

7. Бычков, И.В. Применение ГИС- и Веб- технологий для создания интегрированных информационно-аналитических систем / И.В. Бычков, А.С. Гаченко, А.К. Попова, Г.М. Ружников, Е.С. Фереферов, А.Е. Хмельнов // Вычислительные технологии. - 2007. - Т. 12, спец. вып. № 3. - С. 5-20.

8. Бычков, И.В. Современные информационные технологии в 1Т-проектах органов государственной власти и местного самоуправления / И.В. Бычков, Г.М. Ружников, А.Е. Хмельнов // Открытое образование. - 2008. - Т. 4 (69). -С.39-47.

Горнов А.Ю., Зароднюк Т.С.

УДК 517.977.58

МЕТОД «КРИВОЛИНЕИНОГО» ПОИСКА ГЛОБАЛЬНОГО ЭКСТРЕМУМА В ЗАДАЧЕ

л

ОПТИМАЛЬНОГО УПРАВЛЕНИЯ

Введение. Для задач конечномерной оптимизации известно множество подходов к поиску глобального экстремума, построены достаточно эффективные алгоритмы, имеется большое количество публикаций, в которых представлены прецеденты успешно решенных задач (см., напр., [12, 11]). После дискретизации непрерывной задачи

Работа выполнена при частичной финансовой поддержке РФФИ, проект № 09-07-00267; РГНФ, проект № 09-02-00650; интеграционного проекта СО РАН -УрО РАН № 85; междисциплинарного интеграционного проекта СО РАН № 4.

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

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

В большом обзоре зарубежных публикаций по глобальной оптимизации (см. [3]), несмотря на присутствие раздела по динамическим моделям («4. differential-algebraic models»), не удалось найти ссылок на серьезные работы по исследованию невыпуклых задач оптимального управления, в основном отражены работы по параметрической идентификации систем («parameter estimation»); возможно, исключением являются статьи [4-6], опубликованные в труднодоступных источниках. Известно довольно много публикаций, посвященных построению алгоритмов поиска глобального экстремума функционалов, основанных на генетических методах, привлекаемых, очевидно, как «последнее средство» (см. работы H. Seywald, R.R. Kumar, Y.Yamashita, M. Shima, M.H. Lee, Ch. Han, K.S. Chang, Z. Michalewicz, C.Z. Janikov, J.B. Krawczyk, S. Smith, R. Stonier, N.V. Dakev,

A.J. Chipperfield, J.F. Whidborne, P.J. Fleming,

H. Muhlenbein, D. Schlierkamp-Voosen, B. de Andres-Toro, J.M. Giron-Sierra, J.A. Lopez-Orozco, J. Bobbin, X. Yao, Y.C. Sim, S B. Leng, V. Subramaniam, H. Pohlheim, A. Heibner, Q.T. Pham, M.M.A. Hashem, K. Watanabe, K. Izumi, F.S. Wang, J.P. Chiou). Самой последовательной в этом направлении представляется диссертация

I.L. Lopez Cruz [10], в которой даже приведены решения трех нелинейных тестовых задач. Однако сам факт наличия у вышеперечисленных авторов не более одной-двух публикаций по рассматриваемой тематике красноречиво говорит о малой эффективности данного подхода.

Среди немногочисленных российских работ, посвященных невыпуклым ЗОУ, следует отметить, прежде всего, фундаментальную монографию

B.Ф. Кротова [7]. Большой объем новых результатов получен в группе А.С. Стрекаловского, разработавшего методики исследования задач оптимального управления некоторых частных классов, основанные на DC-разложениях [8-9]. Однако для общей ЗОУ в нелинейной постановке, столь важной в практических приложениях, пока результатов регулярных вычислительных экспериментов не публиковалось. Можно утверждать, что работа по исследованию невыпуклых нелинейных задач оптимального управления пока только начинается.

Вычислительные затраты, необходимые исследования невыпуклых задач оптимизации мож-

но (довольно условно) разделить на две составляющие, соответствующие двум этапам решения: собственно поиск глобального экстремума и доказательство того факта, что полученное решение является глобальным. Практика решения конечномерных задач показывает [1-2, 11], что экстремальное решение можно найти относительно быстро и основное время работы алгоритмов, за редким исключением, тратится на втором этапе. Кроме того, при детальном рассмотрении оказывается, что в любой программной реализации алгоритмов неявно закладываются гипотезы, не позволяющие гарантировать получение глобального экстремума, речь может идти только о повышении вероятности его нахождения. Представляется, что в настоящее время гарантировать получение глобальных решений в ЗОУ не удастся даже при наличии надежного теоретического фундамента, поэтому целесообразно применение других методических подходов к исследованию невыпуклых задач. Авторы предлагают использование «логики предъявления»: задача (временно) считается успешно решенной, если алгоритм способен найти локальный экстремум с достаточно «хорошим» значением целевого функционала. Далее полученный результат публикуется и считается правдоподобным решением задачи до «момента опровержения» - предъявления кем-либо лучшего решения. Отметим, что подобный подход давно используется в конечномерной оптимизации при создании коллекций тестовых задач - принцип «наилучшего из известных» («best of known», см., напр., [12]). Доказательство факта достижения локального экстремума может базироваться, как и в выпуклой оптимизации, на необходимых условиях оптимальности, для задач оптимального управления традиционно это выполнение одного из вариантов принципа максимума Понтрягина.

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

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ В ЗАДАЧАХ ДИНАМИКИ И УПРАВЛЕНИЯ

множества достижимости (см., напр., [15-17]) могут быть использованы для построения специализированных алгоритмов оптимизации в ЗОУ. В частности, свойство связности позволяет построить механизмы непрерывного варьирования управления, приводящие к непрерывной фазовой траектории на множестве достижимости. Отметим, что идея использования свойства связности при конструировании численных алгоритмов оптимизации принадлежит А.Г. Ченцову [18].

В большинстве известных подходов к построению методов невыпуклой оптимизации решение задачи разделяется на две стадии: «глобальную», на которой выполняется широкое сканирование вариабельного пространства, и «локальную», направленную на локальное уточнение полученного решения (см., напр., [2]). Сочетание различных методов на каждой стадии, а также порядок чередования стадий и определяет конкретный вычислительный алгоритм. Представляется интересной идея совмещения обеих стадий в одной алгоритмической конструкции и построения метода, позволяющего на каждой итерации как выполнять процедуру «глобального сканирования», так и получать локальное улучшение известного решения в случае, когда сканирование не принесло успеха.

В теории глобальной оптимизации принято условно разделять методы на «эвристические» и «математические, рациональные» (см., напр., [11, с. 18]). Под рациональными методами обычно понимаются методы, основанные на конкретной модели целевой функции и, следовательно, сопровождаемые какой-либо математической теорией, под эвристическими - все остальные. Характерным является кардинальное изменение отношения специалистов к эвристическим методам, произошедшее в течение последних десятилетий, отраженное в авторитетнейших источниках [11] и [2], вышедших в свет в 1991 и 2008 гг., соответственно. Если в монографии [11] эвристические методы подвергались серьезной критике и почти приравнивались к «научному шаманству», то в последней книге тех же авторов уже высказывается совершенно другое отношение к эвристическим методам: «некогда презренные, а ныне весьма респектабельные» («heuristic methods: once scorned, now highly respectable») [2, с. 21]. Представляется, что это изменение «общественного мнения» связано как с накоплением опыта практического применения методов глобальной оптимизации, так и с появлением строгих математических доказательств невозможности существования гарантированных методов поиска глобального экстремума любых

непрерывных функций за разумное число операций (см., напр., [2, 19]). «Окончательным судьей» в данной многолетней дискуссии, очевидно, является практика применения методов, а не наличие красивых математических теорий.

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

Постановка задачи. Предлагаемый подход позволяет решать задачи оптимального управления в следующей эталонной постановке: х = /(х,и,¿), х(^0) = х0, где ?еТ = [?0,. Вектор-функция / (х, и, ^) предполагается непрерывно дифференцируемой по всем аргументам. ЗОУ состоит в поиске допустимого кусочно-

непрерывного управления и * (^) из множества и = (и(^) е Яг : и1 < и(^) < ия} , доставляющего минимум терминальному функционалу I(и) = ((х(^)) , где ((х) также предполагается непрерывно дифференцируемой.

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

аппроксимации множеств достижимости получены авторами в предыдущих работах (см. [20-25]). В заключительном разделе работы полученные в тестовых задачах решения предъявляются заинтересованным специалистам для опровержения.

Алгоритм 1.

1. Выбирается ие и , ? е Т = [?0,.

2. Задаются алгоритмические параметры:

Ыс - число итераций метода «криволинейного» поиска; Ыр - стартовое число проб одномерного поиска.

3. Вычисляется стартовое рекордное значение функционала 1гес = I(и0), задается игес(£) = и ).

На к -й итерации (к > 0):

4. Генерируется псевдослучайное вспомогательное управление и ) е и , ? е Т = [?0, ?1].

5. Если I (и1) < 1гес, то 1гес = I (и1) и игес (^) = и1 (I). Переход на шаг 12.

6. Генерируется псевдослучайное вспомогательное управление и2 (¿) е и , £еТ = [£0,].

7. Если I(и2) < 1гес, то 1гес = I(и2) игес^) = и2 ^). Переход на шаг 12.

8. Формируется управление

f—1

к t \ ' u (a, t) = а

u (t) + u (t) "2

- Urec

+

u 2(t)-u \t) /ч

+ a 2 + urec (t).

9. uk (a, t) проецируется на допустимую область при t eT = [t0,tj :

если uk (a, t) < ul, полагается uk (a, t) = ul, если uk (a, t) > ug , полагается uk (a, t) = ug.

10. Решается задача min I(uk(a)).

ae[-1,1]

11. Если I(uk (a*)) < Irec, то Irec = I(uk(a*)) и urec (t) = uk (a* , t).

12. Запоминаем Irec и urec(t). Итерация завершена.

Тестирование предлагаемого алгоритма.

Для проведения вычислительных экспериментов использовались следующие значения алгоритмических параметров: NC = 1000, NP = 100, что позволило найти более точные решения, но привело

к увеличению процессорного времени, затрачиваемого на его получение (так, например, в ЗОУ динамикой развития вируса иммунодефицита решение, совпадающее с рекордным с точностью до 3-х знаков, удалось получить уже при NC = 50, NP = 30 за 2307 задач Коши). Современные мощности персональных компьютеров позволяют решать тысячи задач Коши за 1 секунду. В данной работе не ставилась задача получения решения за как можно меньшее процессорное время. Поэтому значения алгоритмических параметров выбраны одинаковыми для всех представленных вычислительных экспериментов. Расчеты проводились на персональном компьютере с процессором Intel Core2 Quad 2.33 ГГц и объемом оперативной памяти 8 Гб.

Задача управления осциллятором Даф-финга [26]. Управляемый осциллятор Даффинга описывается нелинейным дифференциальным

••2 3

уравнением х + с х + sx = u , которое эквива-

лентно

следующей

системе:

и

х2 =-2х1 — 6x1 + и . Данный динамический процесс рассматривается на интервале Т = [?0, = [0,1], управление удовлетворяет следующим ограничениям: и е [—10,10]. Необходимо минимизировать функционал

1 f 2

I (и) = — u dt

2 о

^ min

с учетом ограничений на траекторию в начальный и конечный моменты времени: хх(?0) = 1.5, х2 (?0 ) = —1.5 и х1(^1) = х2(^) = 0. Учет краевых условий выполняется стандартным методом штрафов путем добавления к терминальному функционалу взвешенных квадратов отклонений траектории от требуемых значений в конечный момент времени. Оптимальное управление и соответствующие ему траектории приведены на рис. 1.

Для получения рекордного значения функционала, равного 2.648442, потребовалось решение 109219 задач Коши за общее процессорное время 27 сек. При этом улучшение функционала выполнялось на каждой итерации метода.

Процесс «покрытия» кривыми множества достижимости при решении задачи отражен на рис. 2. Иллюстрация на рис. 2, а получена при следующих значениях алгоритмически параметров: Ыс = 300, Ыр = 30, на рис. 2, б - при Ыс = 1000, Ыр =100.

x1 = Х2

Рис. 1. Оптимальные траектории и управление в задаче 1 Рис. 3. Оптимальные траектории и управление в задаче 2

Рис. 2. Иллюстрация работы метода «криволинейного» Рис- 4 Иллюстрация раб°ты мет°да «криволинейного» поиска на примере множества достижимости задачи 1 поиска на примере множества достижимости задачи 2

Тестовая задача 2. Рассмотрим тестовую задачу, динамический процесс в которой описывается системой нелинейных дифференциальных уравнений

2

x1 = x2, x2 = -2xj - 3x2--arctan(5x2) + u - sin(15xj),

n

определенной на интервале T = [t0, t1] = [0,2], необходимо найти минимум функционала

I(u) = 2Xj2 - 1.05x1 + xf / 6 - Xjx2 + x2 +1 ^ min при следующих ограничениях на управляющее воздействие: u е[-10,10] и фиксированным значением траектории в начальный момент времени

x^) = x2(*0) = -1.

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

Оптимальное значение функционала 1.000000 достигнуто за 64 сек в результате решения 110175 задач Коши, при этом улучшение критерия качества выполнялось на 55 итерациях из 1000, это связано с тем, что глобальное значение функционала находится достаточно быстро. Изображение на рис. 4, а получено при NC =100, NP = 50, на рис. 4, б - при NC = 1000, NP = 100 (рис. 4).

Тестовая задача 3 [21].

Xj = sin x2, x2 = u - eXl,

x(t0) = (1,1), luí < 1, t e T = [0, 5].

I(u) = x1(t1) + x2(tj) ^ min.

Рис. 5. Оптимальные траектории и управление (а); множество достижимости и экстремальные точки (б) в задаче 3

С помощью предлагаемого подхода найдено оптимальное значение функционала -16.43078 за 60 сек и 119269 задач Коши. На рис.5 изображены оптимальное управление и соответствующие ему траектории, а также множество достижимости с выделенными точками, в которых достигаются минимальные значения целевого функционала (глобальный экстремум дополнительно выделен белой областью в центре).

Тестовая задача 4 [27].

jq = (x1 + x2 )u, x2 = sin(xj + x2 + u), x(t0) = (-9.0,1), -1 <u(t) < 1,t eT = [0,1], I (u) = -x1(t1) ^ min .

Глобальный минимум равен 0.055868 и достигается в точке (-0.055868, 1.848724), локальный - 0.6282969 при x = -0.628297, x2 = 0.062108 (рис. 6). Оптимальное значение функционала получено рассматриваемым методом за 23 сек, при этом на 607 итерациях из 1000 произошло последовательное улучшение значения функционала. Общее число решенных задач Коши равно 96708.

б

Рис. 6. Оптимальные траектории и управление (а); множество достижимости и экстремальные значения целевого функционала (б) в задаче 4

ЗОУ ядерным ректором (Stirred Tank Reactor, [28, 29]). Эта задача включена в коллекцию тестовых задач, опубликованную в Справочнике тестовых задач локальной и глобальной оптимизации (Handbook of The Test Problems in Local and Global Optimization).

Процесс протекания необратимой химической реакции в ядерном реакторе описывается системой нелинейных дифференциальных уравнений

xi =-(2 + u)(x1 + 0.25) + (x2 + 0.5) exp

25x1 Л

V X + 2 /

X2 = 0.5 - x2 - (x2 + 0.5)exp|

25x1 xi + 2 j

рекордное значение равно 0.14433), общее число задач Коши, решенное в процессе численного поиска оптимального значения критерия качества, равно 111901. При этом в 998 итерациях из 1000 получено последовательное улучшение функционала. Оптимальное управление и соответствующие ему траектории сопоставимы с известными из первоисточника (рис. 7).

ñ

Рис. 7. Оптимальные траектории (а), управление (б) и множество достижимости (в) в ЗОУ ядерным реактором

ЗОУ динамикой развития вируса иммунодефицита (Control of theHIV-1 dynamics, [30]).

Данная модель описывает динамику развития вируса иммунодефицита человека при использовании лекарственного лечения. Входящие в нее дифференциальные уравнения отражают изменение численности неинфицированных клеток C , инфицированных клеток I и развитие вируса V за промежуток времени T = [t0, tj = [0,1]:

C=s+pC

1 -

C Л

j

Cm

- dCC - (1 - u)kVC,

ЗОУ заключается в определении управляющего воздействия u * (t), которое минимизирует интегральный целевой функционал

0.78

I(u) = | (xj2 + x^ + 0.1u 2)dt ^ min . Начальные ус-

0

ловия заданы: xx(0) = x2(0) = 0.09. Управляющая функция может принимать значения из интервала 0 < u(t) < 5.0.

Оптимальное значение функционала 0.137102 получено за 99 сек (в первоисточнике

I = (1 — и)кУС — dII, V = Ш¡I — dVУ.

Управляющее воздействие и является мерой эффективности воздействия лекарственных препаратов: если и = 1 - осуществляется максимальное препятствие росту численности инфицированных клеток, тогда как при и = 0 - сдерживающего воздействия не осуществляется (таким образом, 0 < и < 1). Значения фазовых координат в начальный момент времени t0 равны 9, 0.8 и 0.2, соот-

и

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ В ЗАДАЧАХ ДИНАМИКИ И УПРАВЛЕНИЯ

ветственно. Минимизируемый функционал зависит от изменения численности I и V, при этом учитывается факт того, что введение большого числа лекарственных препаратов может оказывать негативное воздействие на пациентов: t1

J M (12 + V2) + udt ^ min.

На рис. 8 и 9 отражено оптимальное управление и соответствующее ему развитие C, I и V для следующих значений параметров модели: 5 = 0.2, p = 0.05, Cmax = 25, к = 0.08, dC = 0.01, dj = 0.3, dV = 0.009, N = 0.005, M = 8.

Рис. 8. Оптимальное управление в ЗОУ динамикой развития вируса иммунодефицита

менты в максимально допустимых дозах в первый период и затем совсем прекратить лекарственные инъекции. Во втором периоде рост числа инфицированных клеток и вирусов естественно снижается посредством неконтролируемой динамики. Множество достижимости в рассматриваемой задаче представлено на рис. 10. Решение задачи получено за 37 сек, рекордное значение функционала равно 4.787449, число задач Коши - 115336.

е.,-

'--VA

—1—'—I—'—I—'—I « »3 »l J * i *

ftlffi-

Ii

\

а а 04 Об 0 Е

Рис. 9. Динамика изменения численности неинфициро-ванных клеток С

Из рис. 9 видно, что численность вирусов монотонно убывает благодаря эффективному использованию лекарственного лечения. В результате расчетов рекомендуется использовать медика-

Рис. 10. Множество достижимости в ЗОУ динамикой развития вируса иммунодефицита

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

Сравнение результатов расчетов с известными множествами достижимости системы, полученными с применением других вычислительных методов (обсуждение которых выходит за рамки настоящей статьи, см., напр., [31-32]), позволяет сделать вывод о достаточно плотном покрытии множества достижимости фазовыми траекториями, т.е. об адекватности сканирующих возможностей метода в рассматриваемых тестовых задачах. Основным ресурсом дальнейшего повышения качества предложенной алгоритмической схемы авторы считают использование более широкого спектра методов генерации вспомогательных управлений (квазислучайные «сплайн-

управления», случайные управления, полученные на основе принципа максимума и т.д., см. [20, 23]).

б

БИБЛИОГРАФИЯ

1. Евтушенко, Ю.Г. Параллельные методы решения задач глобальной оптимизации / Ю.Г. Евтушенко, М.А. Половинкин // Тр. IV Междунар. конф. «Параллельные вычисления и задачи управления». - М., 2008. - С. 18-39.

2. Zhigliavsky, A. Stochastic global optimization / A. Zhigliavsky, A. Zilinskas. - Springer Science-Business Media, 2008. - 262 p.

3. Floudas, C.A. A review of recent advanced in global optimization / C.A. Floudas, C.E. Gounaris // J. Global Optimization. -2008. - (In appear).

4. Chachuat, B. Global methods for dynamic optimization and mixed-integer dynamic optimization / B. Chachuat, A.B. Singer, P.I. Barton // Ind. Eng. Chem. Res. - 2006. - № 45 (25). -P. 8373-8392.

5. Barton, P.I. Optimization of hybrid systems / P.I. Barton, C.K. Lee, M. Yunt // Comput. Chem. Eng. - 2006. - № 30 (10-12). - P. 1576-1589.

6. Lin, Y.D. Deterministic global optimization of nonlinear dynamic systems / Y.D. Lin, M.A. Stadtherr // AIChE J. - 2006. - № 53 (4). -P.866-875.

7. Krotov, V.F. Global methods in optimal control theory / V.F. Krotov. - N.Y.: Marcel Dekker Inc., 1996. - 384 р.

8. Стрекаловский, А.С. О невыпуклой задаче оптимального управления / А.С. Стрекаловский, Е.В. Шаранхаева // Журнал вычислительной математики и математической физики. - 2005. - Т. 45, № 10. -С.1785-1800.

9. Стрекаловский, А.С. Задачи оптимального управления с терминальными функционалами, представимыми в виде разности двух выпуклых функций / А.С. Стрекаловский // Журнал вычислительной математики и математической физики. - 2007. - Т. 47, № 11. -С. 1865-1879.

10. Lopez Cruz, I.L. Efficient Evolutionary Algorithms for Optimal Control: PhD Thesis. - Wageningen (The Netherlands): Wageningen University, 2002. - 122 р.

11. Жиглявский, А.А. Методы поиска глобального экстремума / А.А. Жиглявский, А.Г. Жилинскас. - М.: Наука, 1991. - 248 с.

12. Floudas, C.A. A Collection of Test Problems for Constrained Global Optimization Algorithms / C.A. Floudas, P.M. Pardalos. - Springer-Verlag, 1990. - 180 p.

13. Хрусталев, М.М. Необходимые и достаточные условия оптимальности в форме уравнения Беллмана / М.М. Хрусталев // Докл. АН СССР. - 1978. - Т. 242, № 5. - С. 1023-1026.

14. Хрусталев, М.М. Точное описание множеств достижимости и условия глобальной оптимальности динамических систем / М.М. Хрусталев // АиТ. - 1988. - № 5. -С.62-70.

15. Толстоногов, А.А. Дифференциальные включения в банаховом пространстве / А.А. Толстоногов. - Новосибирск: Наука, 1986. - 295 с.

16. Толстоногов, А.А. Об уравнении интегральной воронки дифференциального включения / А.А. Толстоногов // Мат. заметки. - 1982. -Т. 32, № 6. - С. 841-852.

17. Толстоногов, А.А. О структуре множества решений дифференциального включения с невыпуклой правой частью / А.А. Толстоногов // УМН. - 1981. - № 4. -С. 226-227.

18. Субботин, А.И. Оптимизация гарантии в задачах управления / А.И. Субботин, А.Г. Ченцов. - М., 1981.

19. Torn, A. Global Optimization / A. Torn, A. Zilinskas. - Springer, 1989.

20. Горнов, А.Ю. Реализация метода случайного мультистарта для задачи оптимального управления / А.Ю. Горнов // Ляпуновские чтения: Тез. докл. - Иркутск, 2003. - C. 31.

21. Горнов, А.Ю. Подход к исследованию невыпуклых задач оптимального управления с па-раллелепипедными ограничениями / А.Ю. Горнов, А.В. Данеева // Вестник Бурятского ун-та. Сер. Математика и информатика. - Улан-Удэ, 2005. - Вып. 2. - С. 122-130.

22. Данеева, А.В. О некотором опыте численного решения невыпуклых задач оптимального управления / А.В. Данеева, А.Ю. Горнов // Материалы Всерос. конф. с междунар. участием «Математика, ее приложения и математическое образование». - Улан-Удэ: Изд-во ВСГТУ, 2005. - C. 75-78.

23. Ливанцова, Т.С. Подход к поиску глобального экстремума в задаче оптимального управления / Т.С. Ливанцова, А.Ю. Горнов // Тр. X Байкальской всерос. конф. «Информационные и математические технологии в науке, технике и образовании». Ч. I. - Иркутск: ИСЭМ СО РАН, 2005. - C. 154-160.

24. Горнов, А.Ю. Методики конструирования тестовых задач оптимального управления / А.Ю. Горнов, А.В. Данеева // Вестник Бурят-

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ В ЗАДАЧАХ ДИНАМИКИ И УПРАВЛЕНИЯ

ского ун-та. Сер. Математика и информатика. - Улан-Удэ: Изд-во Бурятского ун-та, 2006. -Вып. 3. - C. 136-143.

25. Gornov, A.Yu. Optimal Control Problem: Heuristic Algorithm for Global Minimum / A.Yu. Gornov, T.S. Zarodnuk // Proc. of the Second Intern. Conf. on Optimization and Control. - Ulanbaatar (Mongolia), 2007. - P. 27-28.

26. El-Gindy, T.M. A Chebyshev Approximation for Solving Optimal Control Problems / T.M. El-Gindy, H.M. El-Hawary, M.S. Salim, M. El-Kady // Computers Math. Applic. - 1995. -Vol. 29, № 6. - Р. 35-45.

27. Зароднюк, Т.С. Технология поиска глобального экстремума в задаче оптимального управления / Т.С. Зароднюк, А.Ю. Горнов // Современные технологии. Системный анализ. Моделирование. - Иркутск: ИрГУПС, 2008. -№ 3 (19). - С. 70-76.

28. Dadebo, S. Optimal control of time-delay systems by dynamics programming / S. Dadebo, R. Luus // Optimal Control Application & Methods. - 1992. - № 13. - P. 29-41.

29. Meyer, C.A. A Global Optimization with non-analytical constraints / C.A. Meyer, C.A. Floudas, A. Neumaier. -http://en.scientificcommons.org/clifford a meye L_- 2002. - 40 p.

30. Carlini, E. An efficient algorithm for Hamilton-Jacobi equations in high dimension / E. Carlini, M. Falcone, R. Ferretti // Comput. Vis. Sci. -2003. - № 7. - P. 15-29.

31. Gornov, A.Yu. On a Class of Algorithms for Constructing Internal Estimates of Reachable Set / A.Yu. Gornov // Proc. of the Intern. Workshop DIC-98. Sept. 7-11, 1998. - Pereslavl-Zalessky, 1998. - P. 10-12.

32. Горнов, А.Ю. Метод максимизации объема для аппроксимации интегральной воронки нелинейной управляемой динамической системы на плоскости / А.Ю. Горнов // Тез. докл. Междунар. симп. «Обобщенные решения в задачах управления». 27-31 августа 2002 г. -Переславль-Залесский, 2002. - С. 200-204.

Казаков А. Л., Маслов А.М.

УДК 656.212+519.876.2:872.6

ПОСТРОЕНИЕ МОДЕЛИ НЕРАВНОМЕРНОГО ТРАНСПОРТНОГО ПОТОКА НА ПРИМЕРЕ ЖЕЛЕЗНОДОРОЖНОЙ ГРУЗОВОЙ СТАНЦИИ

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

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

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