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

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

СЫСОЕВ Антон Сергеевич

МОДЕЛИРОВАНИЕ И ОПТИМИЗАЦИЯ СИСТЕМ

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

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

численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

. 2 3 ЯНВ 2СМ

Воронеж — 2013

005544643

005544643

Работа выполнена в ФГБОУ ВПО «Липецкий государственный технический университет»

Научный руководитель: Блюмин Семён Львович, доктор физико-

математических наук, профессор, ФГБОУ ВПО «Липецкий государственный технический университет», профессор кафедры прикладной математики

Официальные оппоненты: Матвеев Михаил Григорьевич, доктор технических наук, профессор, ФГБОУ ВПО «Воронежский государственный университет», заведующий кафедрой информационных технологий управления;

Преображенский Андрей Петрович, кандидат физико-математических наук, доцент, АНОО ВПО «Воронежский институт высоких технологий», доцент кафедры инновационных систем информатизации и безопасности

Ведущая организация: ФГБОУ ВПО «Рязанский государственный радиотехнический университет»

Защита диссертации состоится 17 февраля 2014 г. в 11:00 на заседании диссертационного совета Д 212.037.01 при ФГБОУ ВПО «Воронежский государственный технический университет» по адресу: 394026, г. Воронеж, Московский просп., 14.

С диссертацией можно ознакомиться в научно-технической библиотеке ФГБОУ ВПО «Воронежский государственный технический университет».

Автореферат разослан 27 декабря 2013 г.

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

диссертационного совета Барабанов Владимир Федорович

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

Тематика работы соответствует научному направлению Липецкого государственного технического университета «Алгебраические методы прикладной математики и информатики в моделировании и управлении сложными распределенными системами».

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

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

Для достижения поставленной цели решались следующие задачи:

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

— формирование моделей многоканальных систем массового обслуживания с неременной структурой с применением методов идемпотентной алгебры;

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

— разработка метода анализа конечных изменений функций многих переменных, основанного на применении теоремы Лаграпжа о промежуточной точке, проведение численных экспериментов;

— разработка и тестирование комплекса программ, реализующего предложенные алгоритмы моделирования и оптимизации для СМО с переменной структурой на примере регулируемого перекрестка.

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

Тематика работы. Содержание диссертации соответствует следующим пунктам паспорта специальности 05.13.18— Математическое моделирование, численные методы и комплексы программ: п. 2 «Развитие качественных и приближенных аналитических методов исследования математических моделей»; п. 4 «Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента»; п. 8 «Разработка систем компьютерного и имитационного моделирования».

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

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

— численный мультистартовый параллельный алгоритм многомерной оптимизации, отличающийся использованием кластеризации для функциона-

ла качества специальной нелинейной структуры, позволяющий осуществлять поиск оптимальных параметров функционирования СМО с переменной структурой;

— численный метод анализа конечных изменений функции многих переменных, отличающийся использованием теоремы Лагранжа и позволяющий осуществить оценку организационной структуры СМО с переменной структурой с целью дальнейшего принятия управленческих решений;

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

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

Компоненты математическохчз и программного обеспечения прошли государственную регистрацию в Отраслевом фонде алгоритмов и программ и в ФГБУ «Федеральный институт промышленной собственности».

Реализация и внедрение результатов работы. Полученные практические результаты и разработанный комплекс программ используются для планирования строящихся и оптимизаций уже существующих регулируемых пересечений городских магистралей Управлением дорог и транспорта Липецкой области, а также для анализа регулируемых перекрестков Липецка и Липецкой области УГИБДД УМВД России по Липецкой области. Теоретические результаты диссертации используются в учебном процессе в ФГБОУ ВПО «Липецкий государственный технический университет» при чтении спецкурсов, выполнении дипломных и курсовых проектов.

Апробация. Основные результаты, полученные в диссертационной работе, докладывались и обсуждались на международных и всероссийских конференциях и форумах: Международной научной конференции студентов, аспирантов и молодых ученых «Ломоносов» (Москва, 2009), Летней школе молодых ученых в рамках 22-ой Международной научной конференции «Математические методы в технике и технологиях» ММТТ-22 (Иваново, 2009), Международном форуме студенческой и учащейся молодежи «Первый шаг в

науку» (Минск, 2009-2011), IV Международной научно-практической конференции «Инновации и информационные технологии в образовании» (Липецк, 2011), 26 Европейской конференции по операционному исчислению (Рим, 2013), VI, VII, IX, X Всероссийских школах-конференциях молодых ученых «Управление большими системами» (Ижевск, 2009; Пермь, 2010; Липецк, 2012; Уфа, 2013); на профильных семинарах в Рурском университете (ФРГ, Бохум, 2012, 2013); а также на научных семинарах кафедры прикладной математики Липецкого государственного технического университета и научно-образовательных семинарах «Математическое моделирование, информационные технологии и проблемы управления» Липецкого научно-образовательного центра по проблемам управления (Липецк, 2010-2013).

Научные работы по теме диссертационного исследования были отмечены дипломами победителя на конкурсах: научно-технического творчества молодежи «Моделирование и оптимизация функционирования объекта управле-

trim nn»\i\\iftn 111 ТЦ>1Г1ЖГП1|Т1Г11| IППТОТЧЧП1ТП11ЛТ1П ПЛПгагтЛПОПП^Л^ О ^V

i . . . / . ^wp^TvnbliVt Дп1 ti-ii\;3i ! iifci.l ^pci jjll-i^j -OiVi^-i V^ ¡.ii j ^ iViLv,:.!,^, Ю j )

учньтх работ молодых ученых по теории управления и ее приложениям «Моделирование и оптимизация системы управления транспортным потоком на регулируемом перекрестке» (Москва, 2013).

Работа выполнялась при финансовой поддержке гранта РФФИ «Разработка математического и программного обеспечения для моделирования, прогнозирования, оптимизации и управления сложными системами на основе методов идемпотентной математики и интервального анализа» (проект №11-07-00580_а), Фонда развития малых форм предприятий «Участник молодежного научно-инновационного конкурса» «У.М.Н.И.К» (тема № 576ГУ1/2013, 2013-2014 гг.), Европейского союза в рамках программы Erasmus Mundus Action 2 (стажировка в Рурском университете, Бохум, 2012 г.), Благотворительного фонда Михаила Прохорова в рамках программы «Академическая мобильность» (исследования в Рурском университете, Бохум, 2013 г.).

Публикации. Основные результаты диссертационного исследования опубликованы в 13 научных работах, в том числе 2 — в изданиях, рекомендованных ВАК РФ, 1 свидетельство на программу для электронных вычислительных машин. В работах, опубликованных в соавторстве, лично соискателю принадлежат следующие результаты: [l] — пример применения идемпотент-ного подхода к моделированию для описания транспортных систем, [3,13] — разработка математических и программных методов моделирования, оптимизации и анализа регулируемого перекрестка, а также проведение вычислительных экспериментов.

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

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

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

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

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

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

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

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

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

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

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

ррт»ріги

- и і ■.

іСііио которого функционирует

ров обслуживающих устройств.

Ассоциируем с описываемой системой гипеграф (V, Е), такой, что множество его вершин V = {г»1, ...,уп}, мощность которого совпадает с числом обслуживающих устройств п. Множество гиперребер Е показывает структуру фаз функционирования системы.

На рис. 1 представлен пример гиперграфа системы с переменной структурой с 7 обслуживающими устройствами, функционирующими следующим образом: в фазе 1 — устройства 1, 3 и 7; в фазе 2 — устройства 2, 3, 4 и 5; в фазе 3 — устройства 5, 6 и 7. Матрица инцидентности С гиперграфа (V, Е), построенная над идемпо-тентным полукольцом Д, имеет следующую структуру:

1, если обслуживающее устройство ] функционирует в фазе г, I е, иначе.

Обозначим: А(к) = (а^к), ...,ап(к))Т - вектор моментов прибытия заявок в систему, 0(к) = ((¡-¡(к),..., (1п(к))т - вектор моментов выхода обслуженных заявок, ЦТ (к) — (ю\(к),..., гип(к))т - вектор неслучайных моментов ожидания заявками обслуживания, Е(/с) = (^(/с),...,£п(/с))т - вектор случайных моментов ожидания заявками обслуживания.

Рисунок 1 - Пример гиперграфа, ассоциированного с системой

II с ||у =

Тогда рассматриваемую систему можно аналитически представить с помощью следующего выражения:

D{k) = А{к) © W(k) © (DT{k - 1) ® S{k))T, (1)

СцфЕ

где uii(k) = (£) Щ, Cij—инверсный к Cjj элемент, сиг— переменная-счетчик,

i=CUT

хранящая информацию о числе фаз, прошедших с начала функционирования цикла системы, l,j = 1, ...,п.

Выражение (1) показывает динамику цикла функционирования многоканальной системы массового обслуживания с переменной структурой и может быть использовано для имитации работы регулируемого перекрестка.

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

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

В строгой постановке: найти точку (T,gi,...,gm) такую, что

/ (T,gi,-,gm) =

г=1

Е vi

г=1

при системе ограничений

( m

i=l

т ■ <т < т

шш _ _ J-majo

Здесь fi(T,9i) = k)

Ыmin <9i< Ытах , г = 1,..., m,

„ 91, -,9m > 0.

T

o-f)2

2(1-шт{1,Х4}|)

TT h

/

+ 15t e

№ -1)

х{ =

vJT_ Si9i'

\

(2)

(3)

(Хг- 1)2 + 240^ t,

T /

Т— время цикла светофорного регулирования (с), д^г = 1,...,т— длительность фаз светофорного регулирования (с), / (Т,д\, ...,дт) — значение функции агрегированной задержки (с), к^, г = 1,...,т— коэффициент, определяющий тип прибытия транспортных средств, г>г, г = 1 ,...,т— интенсивность прибытия транспортных средств на направлении г (прив.авт./час), л,, г = 1, ...,т— поток насыщения направления^ (прив.авт./час), Тш[п(шах)— ограничения на длительность времени цикла светофорного регулирования (с), (^г)тт(тах) > * = —,тп— ограничения на длительности фаз светофорного регулирования (с), 1е— время для прогноза вычисления задержки (мин).

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

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

Получаем задачу многомерной безусловной минимизации

№дъ...,дт,Р) = 1{Т,д1,...,дт)+(р{Т,д1,...,дт,/3) -> тт. (4)

Решение полученной задачи (4) проведено численно на основе предложенного мультистартового параллельного алгоритма безусловной многомерной минимизации с кластеризацией.

Шаг 0. Настройка параметров алгоритма. На этом шаге необходимо задать:

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

Д/3— приращение параметра штрафной функции (Д/3 = к)),

£1 > 0— точность шага алгоритма оптимизации,

£2 > 0— точность алгоритма,

5 > 0— параметр кластеризации.

Шаг 1. В качестве начального значения для множителя штрафной функции положить /3 = 0. Тем самым будет найден глобальный оптимум исходной функции без учета ограничения-равенства.

Шаг 2. Для заданной функции без ограничений необходимо смоделировать на множестве X п равномерно распределенных в Ят+1 точек х\, ...,хп.

Шаг 3. Минимизация функции со штрафом для конкретного параметра/3.

Шаг 3.1. Используя полученные точки в качестве начальных, провести одну или несколько итераций алгоритма статистического градиента с целью улучшения рабочих точек. В результате получены точки г\,..., гп (для первой итерации используются точки шага 2, для последующих - точки шага 3.4).

Рисунок 2 - Схема алгоритма оптимизации

Шаг 3.2. Применить кластеризацию к полученным точкам z\,..., zn.

Шаг 3.2.1. Положить, что все точки принадлежат различным кластерам.

Шаг 3.2.2. Найти ближайшую пару Zj, такую, что

. .. pij = arg min pkj-

kji=l.....N

Шаг 3.2.3. Если расстояние между ближайшими соседями не превосходит некоторое достаточно малое число 5 > 0, то Zi, Zj объединяются в один кластер, и, тем самым, число кластеров сокращается на единицу.

Пусть получено т кластеров. Если m — 1, переход к шагу 3.4, иначе - к

шагу 3.3.

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

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

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

<£1- " (5)

Если условие (5) выполнено, переход к шагу 4.

Шаг 4. Проверка, условия окончания алгоритма

\п*к+1,/зк)-№,рк-1)\ <е2. (6)

Если условие (6) выполнено - положить ж* = гк+1, в противном случае -переход к шагу 5.

Шаг 5. Пересчет (увеличение) параметра /3 штрафной функции по заданному правилу: /Зк+г = /Зк + А0. Переход на шаг 2.

В приведенном алгоритме в качестве метода локальной оптимизации использован алгоритм статистического градиента. Общая схема метода приведена на рис. 2.

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

п О Г П ог

А/(хи...,хп) = + аДх;) • Дх; = V (£). Д^, (7)

г—1 °Х4 4=1

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

В математическом анализе принято рассматривать оценку изменения величин в форме разностей (приращений) финального ж и начального х0 значений. Однако возможны и другие оценки изменения величин, например, по аналогии с конечными разностями (приращениями) Ах = Хо — х, конечные

частные (индексы) гх = — (при х0 ф 0). Такой подход приводит к появ-

зс о

лению мегадики более общего анализа, нежели экономический факторный анализ, — анализа конечных изменений.

Теорема Лагранжа представляет собой основную модель аддитивного раз-

личительного исчисления (7). Путем логарифмирования (экспоненцирования) аргумента (функции) возможно получение основной модели мультипликативного различительного исчисления (8) и смешанных моделей аддитивного-мультипликативного (9) и мультипликативно-аддитивного (10) различительных исчислений

п

гу = П ' (8)

¿=1

где 7,- = -^у • д~(0 ' частные эластичности в промежуточной точке;

Axt

п (ехр(/Ш'Й

^ = 11 ехР ■ > (9)

{ п т \

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

п п

а-0 + Е а'хг + Е /(*!,...,*„) =-ЕЦ-•=!-, (11)

!=1

где X; > 0, а0,йг,Ь1 > 0.

Выражения для параметра промежуточной точки модели (11) имеет вид

¿=1 V ¿=1 ¿=1

а =--. (12)

Е ^г

г=1

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

В третьей главе содержится подробное описание программного комплекса «Моделирование и оптимизация процессов на регулируемом перекрестке», который состоит из следующих модулей:

— основной модуль «SMO», реализующий имитационную идсмпотентную модель многоканальной системы массового обслуживания переменной структуры, описанную выше;

— основной модуль «Optimization», реализующий численный мультистар-товый параллельный алгоритм безусловной многомерной минимизации;

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

Рисунок 3 - Структура комплекса для моделирования, оптимизации и анализа регулируемых перекрестков

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

Структура программного комплекса представлена на рис. 3. На рис. 4 показано окно мастера вспомогательного модуля построения конфигурации регулируемого перекрестка.

Данный программный комплекс предназначен для: а) формирования структуры исследуемого регулируемого перекрестка и имитационного моделирова-

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

Рисунок 4 Окно конфигуратора перекрестка

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

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

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

Таблица 1. Сравнительные результаты оптимизации

Фаза 1 Фаза 2 Фаза 3 Фаза 4

Интенсивность движения в критической группе, прив.авт./'ч 1533 242 242 1086

Поток насыщения, прив.авт./ч 1800 1800 1800 1800

Длительность гКяч с до 38 16 8 23

после 31,5 9,8 9,9 21,5

Webster 12,6 7 7 8,9

v/c-отношение до 1,905 0,714 1,428 2,229

после ! ,966 0,997 0,987 2,040

Webster 2,399 0,682 0,682 2,407

Задержка, с до 212,2 54,75 14,97 647,52

после 207,09 48,87 11,63 367,28

Webster 213,7 40,26 11,25 412,83

По данным табл. 1 можно сделать вывод, что использование предлагаемого метода оптимизации, во-первых, также как и классический подход Вебстера, стремится к балансировке у/с-отношений в фазах, и, во-вторых, в результате экономия времени агрегированной задержки составляет 30,1%. Алгоритм получения средней задержки для регулируемого перекрестка

п

Е /Ы • ч

приводит к модели вида / = п-. Анализ этой функции, где в каче-

Х>а

¿=1

стве каждого f(vi) выступают выражения из системы (2), является вычислительно сложной задачей. Для упрощения анализа применим к функции/ разложение в ряд Маклорена (до трех членов). В результате такого приема получаем модель, структурно схожую с формулой (9). Параметр средней точки для данной модели вычисляется согласно выражению (12).

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

критических групп в фазах - и процентное влияние факторов.

Вклад факторов в изменение средней задержки, % Рисунок 5 Результаты анализа двухфазного перекрестка

Результаты анализа полученной функции структуры (11) при помощи моделей (7-10) могут служить основанием для принятия управленческих решений по реорганизации существующего режима функционирования регулируемого перекрестка и при устройстве планирующихся на этапе их моделирования.

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

4. Полученные теоретические результаты применены для описания функционирования, моделирования, оптимизации и анализа регулируемого перекрестка.

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

6. Компоненты программного обеспечения прошли государственную регистрацию в ФГБУ «Федеральный институт промышленной собственности» и в Фонде алгоритмов и программ Всероссийского научно-технического информационного центра.

7. Комплекс внедрен Управлением дорог и транспорта Липецкой области для планирования строящихся и оптимизации уже существующих регулируемых пересечений городских магистралей, а также УГИБДД УМВД России по Липецкой области для анализа работы регулируемых перекрестков Липецка и Липецкой области.

Основные результаты диссертационного исследования опубликованы в следующих работах:

Публикации в изданиях, рекомендованных ВАК РФ

1. Сысоев, A.C. Идемпотентный подход к моделированию: транспортные системы и оптимизация подвижных процессов [Текст] / A.C. Сысоев, С.Л. Блю-мин, 0.0. Черных // Вести высших учебных заведений Черноземья.— 2012. — № 2. — С. 43-46.

2. Сысоев, A.C. Численный алгоритм оптимизации функции транспортной задержки на регулируемом перекрестке [Тскст] / A.C. Сысоев // Научно-технический вестник Поволжья. — 2012. — № 5. — С. 324-330.

Свидетельства на программу для электронных Вычислительных машин

3. Сысоев, A.C. Моделирование и оптимизация процессов на регулируемом перекрестке / A.C. Сысоев, Д.И. Попова, С.Л. Блюмин. — М.: ФГБУ ФИПС. — 2013. Госрегистрация № 2013616785 от 19.07.2013.

Статьи и материалы конференций

4. Сысоев, A.C. Об одной теореме классического математического анализа [Текст] / A.C. Сысоев // Управление большими системами: сборник трудов

VI Всероссийской школы-семинара молодых ученых. — Том 1. — Ижевск: ООО Информационно-издательский центр «Бон Анц». — 2009. — С. 320-324.

5. Сысоев, A.C. Квантовая h-эластичность производственной функции Ал-лена [Текст] / A.C. Сысоев // Управление большими системами: материалы

VII Всероссийской школы-конференции молодых ученых .— Том 1. — Пермь: ПГТУ. — 2010. — С. 370-373.

6. Сысоев, A.C. Моделирование объекта системы управления дорожным движением [Текст] / A.C. Сысоев // Первый шаг в науку — 2011: сборник материалов Международного форума студенческой и учащейся молодежи. — Минск: «Четыре четверти». — 2011. — С. 576-578.

7. Сысоев, A.C. Математическая модель объекта регулирования дорожного движения [Электроннный ресурс] / A.C. Сысоев // Инновации и информационные технологии в образовании: сборник материалов IV Международной научно-практической конференции. — Липецк: ЛГПУ. — 2011.

8. Сысоев, A.C. Имитационное идемпотентное моделирование транспортных систем [Текст] / A.C. Сысоев // Управление большими системами: материалы IX Всероссийской школы-конференции молодых учёных. — Том 1. — Тамбов—Липецк: изд-во Першина Р.В. — 2012. — С. 97-100.

9. Сысоев, A.C. Анализ подходов к расчету оптимального времени цикла светофорного регулирования [Текст] / A.C. Сысоев // Информационные технологии моделирования и управления. — 2012. — Т. 76. — № 4. — С. 300-307.

10. Сысоев, A.C. Синтез мультистартового параллельного алгоритма безусловной многомерной оптимизации для минимизации функции транспортной задержки [Текст] / .A.C. Сысоев // Управление большими системами: материалы X Всероссийской школы-конференции молодых ученых. — Том 3. -.."Уфа: УГАТУ. — 2013. -'- С. 273-276. \>,

11. Сысоев, А.С. Экономический факторный анализ: возможность применения в транспортных системах [Текст] / А.С. Сысоев // Актуальные вопросы современной информатики: материалы III Международной научно-практической конференции. — Коломна: Московский государственный областной социально-гуманитарный институт. — 2013, — С. 140-143.

12. Sysoev, A.S. Synthesis of parallel algorithm for multidimensional optimization for traffic delay function [Text] / A.S. Sysoev // Computer Science and Information Technologies (CSIT2013): Proceedings of the Workshop. — Volume 2. — Vienna-Budapest-Bratislava: Ufa State Aviation Technical University. — 2013. — P. 88-91.

13. Сысоев, А.С. Моделирование и анализ объекта управления и транспортной задержки в дорожном движении / А.С. Сысоев, С.Л. Блюмин. — М.: ОФАП. — 2011. Госрегистрация № 50201150560 от 27.04.2011.

Подписано в печать 27.12.2013. Формат бумаги 60x84 1/16. Бумага офсетная. Усл. печ. л. 1,0. Тираж 100 экз. Заказ № ■// . Издательство Липецкого государственного технического университета. Полиграфическое подразделение Издательства ЛГТУ. 398600 Липецк, ул. Московская, 30.

ЛИПЕЦКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

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

04201456036

СЫСОЕВ Антон Сергеевич

МОДЕЛИРОВАНИЕ И ОПТИМИЗАЦИЯ СИСТЕМ

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

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

численные методы и комплексы программ

ДИССЕРТАЦИЯ

на соискание ученой степени кандидата технических наук

Научный руководитель: доктор физико-математических наук, профессор БЛЮМИН С.Л.

Липецк - 2013

Оглавление

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

Глава 1. Методы моделирования, оптимизации и анализа систем с переменной структурой.......................... 13

1.1 Введение.............................. 13

1.2 Понятие системы с переменной структурой........... 13

1.3 Возможность применения систем массового обслуживания для моделирования процессов..................... 14

1.4 Идемпотентная математика как инструмент реализации быстрых и эффективных алгоритмов в теории массового обслуживания ................................ 17

1.5 Общая классификация методов глобальной оптимизации ... 20

1.6 Возможность факторного анализа функций, описывающих некоторые экономические, технические и технологические процессы с применением теоремы Лагранжа о промежуточной точке .................................. 23

1.7 Подходы к постановке задачи оптимизации функционирования пересечения городских магистралей............... 27

1.7.1 Структура и модели транспортного потока....... 27

1.7.2 Регулируемое пересечение городских магистралей ... 30

1.7.3 Критерии оценки функционирования регулируемого перекрестка .......................... 32

1.8 Обзор систем для автоматизированной оптимизации дорожного движения: отечественный и зарубежный опыт......... 39

1.9 Выводы по главе и постановка задач исследования...... 41

Глава 2. Графоструктурное моделирование, численная оптимизация и

анализ конечных приращений систем с переменной структурой . . 42

2.1 Введение.............................. 42

2.2 Идемпотентное графоструктурное моделирование систем массового обслуживания с переменной структурой........ 42

2.2.1 Идемпотентное моделирование одноканальных систем массового обслуживания................. 42

2.2.2 Идемпотентное графоструктурное моделирование многоканальных систем массового обслуживания с переменной структурой....................... 45

2.3 Оптимизация процесса функционирования систем массового обслуживания с переменной структурой............ 47

2.3.1 Постановка задачи оптимизации............. 47

2.3.2 Мультистартовый параллельный алгоритм многомерной оптимизации с кластеризацией.............. 49

2.4 Анализ конечных изменений функций многих переменных . . 55

2.4.1 Основные определения.................. 55

2.4.2 Построение зависимостей для анализа конечных изменений функций........................ 56

2.4.3 Анализ дробно-рациональных функций специального вида............................. 61

2.4.4 Применение анализа конечных изменений для исследования функционирования систем с переменной структурой ............................. 65

2.5 Выводы по главе.......................... 66

Глава 3. Разработка проблеммно-ориентированного программного

обеспечения для моделирования и оптимизации функционирования регулируемого перекрестка.................... 67

3.1 Введение.............................. 67

3.2 Структура комплекса программных средств для моделирования, оптимизации и анализа функционирования регулируемого перекрестка ............................ 67

3.3 Описание программы....................... 68

3.4 Руководство оператора...................... 80

3.5 Выводы по главе.......................... 88

Глава 4. Моделирование, оптимизация и анализ процессов на пересечениях городских магистралей методами идемпотентной математики и анализа конечных изменений................. 89

4.1 Введение.............................. 89

4.2 Моделирование регулируемых перекрестков методами идемпотентной математики........................ 89

4.3 Оптимизация процесса функционирования регулируемого перекрестка .............................. 96

4.4 Анализ параметров функционирования регулируемого перекрестка методами анализа конечных изменений........100

4.5 Выводы по главе..........................106

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

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

Приложения.................................121

Введение

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

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

Примером СМО с переменной структурой с ожиданием является регулируемый перекресток. Критерий качества такой системы - величина сред-

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

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

Тематика работы соответствует научному направлению Липецкого государственного технического университета «Алгебраические методы прикладной математики и информатики в моделировании и управлении сложными распределенными системами».

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

Для достижения поставленной цели решались следующие задачи:

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

— формирование моделей многоканальных систем массового обслуживания с переменной структурой с применением методов идемпотентной алгебры;

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

— разработка метода анализа конечных изменений функций многих переменных, основанного на применении теоремы Лагранжа о промежуточной точке, проведение численных экспериментов;

— разработка и тестирование комплекса программ, реализующего предложенные алгоритмы моделирования и оптимизации для СМО с переменной структурой на примере регулируемого перекрестка.

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

Тематика работы. Содержание диссертации соответствует следующим пунктам паспорта специальности 05.13.18 — Математическое моделирование, численные методы и комплексы программ: п. 2 «Развитие качественных и приближенных аналитических методов исследования математических моделей»; п. 4 «Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента»; п. 8 «Разработка систем компьютерного и имитационного моделирования».

Научная новизна. В диссертации получены следующие результаты, характеризующиеся научной новизной:

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

л

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

— численный метод анализа конечных изменений функции многих переменных, отличающийся использованием теоремы Лагранжа и позволяющий осуществить оценку организационной структуры СМО с переменной структурой с целью дальнейшего принятия управленческих решений;

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

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

Компоненты математического и программного обеспечения прошли государственную регистрацию в Фонде алгоритмов и программ Всероссийского научно-технического информационного центра, а также в ФГБУ «Федеральный институт промышленной собственности» (приложение Г).

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

для планирования строящихся и оптимизации уже существующих регулируемых пересечений городских магистралей Управлением дорог и транспорта Липецкой области (приложение А), а также для анализа регулируемых перекрестков Липецка и Липецкой области УГИБДД УМВД России по Липецкой области (приложение Б). Теоретические результаты диссертации используются в учебном процессе в ФГБОУ ВПО «Липецкий государственный технический университе» при чтении спецкурсов, выполнении дипломных и курсовых проектов (приложение В).

Апробация. Основные результаты, полученные в диссертационных работе, докладывались и обсуждались на международных и всероссийских конференциях и форумах: Международной научной конференции студентов, аспирантов и молодых ученых «Ломоносов» (Москва, 2009), Летней Школе молодых ученых в рамках 22-ой Международной научной конференции «Математические методы в технике и технологиях» ММТТ-22 (Иваново 2009), Международном форуме студенческой и учащейся молодежи «Первый шаг в науку» (Минск, 2009-2011), IV Международной научно-практической конференции «Инновации и информационные технологии в образовании» (Липецк, 2011), 26 Европейской конференции по операционному исчислению (Рим, 2013), VI, VII, IX, X Всероссийских школах-конференциях молодых ученых «Управление большими системами» (Ижевск, 2009; Пермь, 2010; Липецк, 2012; Уфа, 2013); на профильных семинарах в Рурском университете (ФРГ, Бохум, 2012, 2013); а также на научных семинарах кафедры прикладной математики Липецкого государственного технического университета и научно-образовательных семинарах «Математическое моделирование, информационные технологии и проблемы управления» Липецкого научно-образовательного центра по проблемам управления (Липецк, 2010-2013).

Научные работы по теме диссертационного исследования были отмечены дипломами победителя на конкурсах: научно-технического творче-

ства молодежи «Моделирование и оптимизация функционирования объекта управления дорожным движением (регулируемого перекрестка)» (Москва, 2013), научных работ молодых ученых по теории управления и ее приложениям «Моделирование и оптимизация системы управления транспортным потоком на регулируемом перекрестке» (Москва, 2013).

Работа выполнялась при финансовой поддержке гранта РФФИ «Разработка математического и программного обеспечения для моделирования, прогнозирования, оптимизации и управления сложными системами на основе методов идемпотентной математики и интервального анализа» (проект №11-07-00580_а), Фонда развития малых форм предприятий «Участник молодежного научно-инновационного конкурса» «У.М.Н.И.К» (тема № 576ГУ1/2013, 2013-2014 гг.), Европейского союза в рамках программы Erasmus Mundus Action 2 (стажировка в Рурском университете, Бохум, 2012 г.), Благотворительного фонда Михаила Прохорова в рамках программы «Академическая мобильность» (исследования в Рурском университете, Бохум, 2013 г.).

Публикации. Основные результаты диссертационного исследования опубликованы в 13 научных работах [15,16,66,79-83,85-89], в том числе 2 [16,86] — в изданиях, рекомендованных ВАК РФ, 1 [66] — свидетельство на программу для электронных вычислительных машин. В работах, опубликованных в соавторстве, лично соискателю принадлежат следующие результаты: [16] — пример применения идемпотентного подхода к моделированию для описания транспортных систем, [15,66] — разработка математических и программных методов моделирования, оптимизации и анализа регулируемого перекрестка, а также проведение вычислительных экспериментов.

Объем и структура работы. Диссертация состоит из введения, четырех глав, заключения и пяти приложений. Список использованной литературы содержит 118 наименований. Основная часть работы изложена на 120 страницах машинописного текста, включая 30 рисунков и 15 таблиц.

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

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

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

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

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

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

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

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