Диссертация (1150701), страница 3
Текст из файла (страница 3)
Полученные вдиссертации результаты направлены на развитие теоретических подходов иматематических методов решения научных и технических, фундаментальныхи прикладных оптимизационных задач теоретической информатики, основанных на применении инструментария идемпотентной алгебры и математическогопрограммирования. С практических позиций, полученные результаты позволяют находить решение большого класса прикладных задач (организация системвидеонаблюдения, проектирование топологии интегральных микросхем, формирование архитектуры телекоммуникационных сетей и др.) размещения объектов на плоскости и в пространстве с прямоугольной метрикой с разного рода13ограничениями на область размещения, такими как прямая, отрезок прямойлинии, вертикальная или горизонтальная полоса, а также прямоугольник, стороны которого параллельны координатным осям.Методология и методы исследования.
В диссертации использована общая методология математической науки, общенаучные методы анализа и синтеза, приемы описания на символьном математическом языке свойств и связейобъектов реального мира, применение методов тропической математики в сочетании с результатами классической линейной алгебры и теории оптимизации.Указанная методология использована в тесной связи с научными методами теории информатики, в части тех ее подходов, которые связаны с исследованиеми формированием структурных характеристик информационных систем.
Припроведении диссертационного исследования для получения новых научных результатов использованы методы математического программирования и теорииисследования операций, в частности – методы минимизации функций.Методика исследования базируется на использовании методического аппарата идемпотентной алгебры для решения задач размещения, обладающего рядом преимуществ перед другими известными методами– если традиционно использование операций max и min при формулировкематематических постановок прикладных задач часто усложняет их решение, то на языке идемпотентной алгебры работа с такими операциямисущественно упрощается, в силу того, что в качестве идемпотентной операции сложения можно взять одну из операция max или min. Вследствиеэтого, методы данного раздела математики могут оказаться удобными иэффективными при решении минимаксных задач, изучению методов решения которых посвящены труды [71–73];– к тому же тропический подход, заключающийся в замене обычных арифметических операций (+,×) на пару операций (⊕,⊗) с идемпотентнымсложением, позволяет решать задачи в общем виде, не выбирая заранее полукольцо, в котором рассматривается задача.
Так, одновременнос решением в смысле (max ,+)-алгебры получают решение и для другихпостановок ((min ,+)-алгебры, (max ,×)-алгебры и т.д.). Например, еслирешается минимаксная задача размещения в терминах (max ,+)-алгебры,14то одноверменно с этим может быть получено решение максиминной задачи размещения в терминах (min ,+)-алгебры. Это существенно расширяетобласть применения данного подхода;– стоит отметить также важную особенность, заключающуюся в возможности преобразовывать сложные нелинейные задачи в линейные в терминах идемпотентной алгебры.
Это позволяет использовать общие методы и результаты линейной алгебры, что часто упрощает решение и интерпретацию полученных результатов. Так, решение минимаксной задачиразмещения точечного объекта на плоскости и в пространстве сводитсяв терминах идемпотентной алгебры к решению параметризованной системы неравенств или к минимизации некоторой функции, заданной вматричном виде с использованием свойств идемпотентного спектрального радиуса матрицы. Получение явных аналитических решений позволяетанализировать результат и следить за его изменением после введения дополнительных ограничений;– важным преимуществом идемпотентной алгебры является то, что в отличии от итерационных решений задач оптимизации, время сходимостикоторых можно только оценивать, идемпотентный подход позволяет получать аналитические решения в виде точных формул, время расчета покоторым можно определить напрямую.Степень достоверности результатов обеспечивается строгим математическим доказательством указанных результатов, непротиворечивостью постановок исследовательских задач, использованием апробированной методологиии методов научных исследований, подбором достоверных исходных данных, атакже проведением тестовых расчетов с использованием разработанных соискателем программных средств.
Кроме того, достоверность результатов подтверждается их близостью к ранее полученным результатами, включая геометрические решения, предложенные Д. Эльзингом и Р. Френсисом [62,63], и алгебраические решения Н. К. Кривулина [74], которые были получены с использованиемальтернативных методик исследования.Апробация результатов. Результаты диссертации докладывались на ряде научных конференций, в том числе на Международной научно-практической15конференции «Актуальные вопросы развития современного общества» (Курск,Россия – 2014), Международной научно-практической конференции «Трендыразвития современного общества: управленческие, правовые, экономические исоциальные аспекты» (Курск, Россия – 2014), 7-й научно-практической internetконференции «Междисциплинарные исследования в области математического моделирования и информатики» (Тольятти, Россия – 2016), 7-й всероссийской научной конференции по проблемам информатики СПИСОК-2017 (СанктПетербург, Россия – 2017), Всероссийской конференции «Третьи чтения памяти профессора Б.
Л. Овсиевича. Экономико-математические исследования: математические модели и информационные технологии» (Санкт-Петербург, Россия – 2017); на семинарах кафедры статистического моделирования и кафедрысистемного программирования Санкт-Петербургского государственного университета и семинаре Санкт-Петербургского государственного университета иСанкт-Петербургского экономико-математического института РАН по тропической математике и смежным вопросам.Результаты диссертационной работы были получены при поддержке грантов №13-02-00338 – «Модели и методы тропической математики в прикладныхзадачах экономики и управления» и №16-02-00059 – «Развитие моделей и методов тропической математики в прикладных задачах экономики и управления»Российского гуманитарного научного фонда, а также №18-010-00723А – «Разработка моделей и методов тропической математики для прикладных задачэкономики и управления» Российского фонда фундаментальных исследований.Публикации.
Основные результаты работы представлены в 2 печатныхработах [75, 76], которые опубликованы в рецензируемых научных изданиях,рекомендованных ВАК при Минобрнауки России, а их переводы [77, 78] опубликованы в журналах, индексируемых в международных библиографическихбазах Scopus и Web of Science.
Всего по результатам диссертации автором опубликовано 7 работ [75, 76, 79–83].В совместных работах с Кривулиным Н. К. [75,76,81,82] соискателю принадлежит формулировка и доказательства теорем о решении задачи размещенияна плоскости точечного объекта с прямоугольной метрикой и ограничениямина область размещения, разработка алгоритмов и программных средств, а также проведение вычислительных экспериментов для верификации полученных16результатов, соавтору принадлежат постановки задач и разработка общих методов решения.Объем и структура диссертации. Диссертационная работа состоит извведения, трех глав, разбитых на параграфы, заключения и одного приложения.Полный объем диссертации составляет 122 страницы машинописного текста.Список литературы содержит 116 наименования.В первой главе систематизированы основные сведения об идемпотентнойалгебре, на которые опираются дальнейшие исследования.
Сформулированыосновные определения и введены используемые обозначения. Вводится понятие идемпотентного полуполя. Проведен обзор алгебры векторов и матриц надидемпотентными полуполями. Сформулирована задача оптимизации в терминах идемпотентной алгебры в матричной форме, на основе которой будет впоследующих материалах диссертации предложено решение частной оптимизационной задачи.Вторая глава посвящена изучению класса задач тропической оптимизациис одной, двумя и тремя переменными.
Получено решение задачи в матричнойформе на основе записи расширенной задачи в векторной форме с использованием экстремальных свойств идемпотентного спектрального радиуса матрицы.Затем проведено решение рассматриваемых задач скалярным методом с помощью сведения задачи оптимизации к системе параметризованных неравенств ипоследующего нахождения всех ее решений.В третьей главе разработаны приложения полученных во второй главетеорем для решения задач оптимального размещения центрального серверауправления в сети локальных коммуникаций и оптимального размещения центра управления системой видеонаблюдения.
Рассмотрены задачи размещенияна плоскости с прямоугольной метрикой точечного объекта без ограничений наобласть размещения, с ограничениями в виде прямой линии, отрезка прямой,полосы и прямоугольника. Завершается глава постановкой и решением задачиразмещения в трехмерном пространстве.В заключении представлены итоги выполненного исследования, рекомендации и перспективы дальнейшей разработки темы.17В приложении представлен компьютерный код алгоритмов вычислениякоординат оптимальной области размещения для задачи размещения без ограничений и с ограничениями на допустимую область размещения.18Глава 1Элементы идемпотентной алгебры1.1ВведениеИдемпотентная алгебра – это раздел прикладной математики, занимающейся изучением полуколец с идемпотентным сложением.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
