Автореферат (1150699), страница 2

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

Текст из файла (страница 2)

Бачелли, Я. Г. Олcдера, Б. Хейдерготта,В. Д. Матвеенко, Н. К. Кривулина, С. Л. Блюмина, Д. А. Николаева и др.Описание подходов к решению задачи1-центрас использованием евклидовой мет-рики приведено в работах М. Колебрука, Н. Мегиддо, А. Фоула, О. Худека и др. Задачаразмещения Ролса с прямоугольной метрикой изучалась в работе П. Хансена. Известно геометрическое решение этой задачи, описанное в трудах Д.

Эльзинга и Р. Френсиса.Итерационные алгоритмы ее решения разработаны Л. Чалметом, С. Нобахтаном и др.Возможно также использование для ее решения методов линейного программирования, вчастности, симплекс-метода.Однако, известные подходы и методы решения этих задач, в частности при наличииограничений на допустимую область размещения, зачастую не позволяют получить полного решения задач с прямоугольной метрикой в явном виде. Применение итерационныхметодов позволяет найти частное решение задачи1-центрав виде одной точки, котораяявляется одним из возможных решений задачи. Это исключает возможность аналитического исследования множества всех решений, включая корректировку этого множествапри добавлении ограничений, что значительно снижает теоретическую и практическуюзначимость получаемых таким способом решений. Кроме того, вычислительная сложностьрешения, записанного в явном виде, может быть определена точно, а для алгоритмическихрешений обычно известны только оценки порядка сложности вычислений.

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

Требуются разработка и обоснование новых математическихметодов, позволяющих эффективно решать указанные задачи, применение которых позволит рационализировать проектирование комплексов аппаратных средств автоматизацииинформационных процессов, а также решать иные прикладные задачи, связанные с развитием современных информационных технологий и ускорением на этой основе научнотехнического прогресса.Цель работы – разработка новых математических методов решения минимаксныхзадач размещения точечных объектов на плоскости и в трехмерном пространстве с прямоугольной метрикой на основе применения методов идемпотентной алгебры и создание5программно-алгоритмического обеспечения для их реализации при проектировании комплексов аппаратных средств автоматизации информационных процессов.В соответствии с указанной целью, поставлены следующие∙задачи исследования:разработка методов решения задач оптимизации функций, заданных на идемпотентных полуполях, с несколькими переменными на основе решения расширенной задачив векторной форме с использованием экстремальных свойств идемпотентного спектрального радиуса матрицы;∙разработка методов решения задач оптимизации функций на идемпотентных полуполях с несколькими переменными с помощью сведения задачи оптимизации к системепараметризованных неравенств и последующего нахождения всех ее решений;∙исследование минимаксных задач размещения с прямоугольной метрикой на плоскости и в трехмерном пространстве с ограничениями и без ограничений, включаяпредставление этих задач в виде задач оптимизации в терминах тропической алгебры, построение прямых решений таких задач в явном виде и оценку вычислительнойсложности решений;∙разработкарекомендацийпооптимальномуразмещениюцентральногосерверауправления в сети локальных коммуникаций и оптимальному размещению центрауправления системой видеонаблюдения на основе реализации разработанных математических методов;∙разработка на основе полученных результатов программных средств для решениязадач размещения и их практическое применение для решения тестовых задач.Соответствие диссертации паспорту научной специальности.Содержание диссертационного исследования соответствует паспорту научной специальности 05.13.17 – Теоретические основы информатики (пп.

2. Исследование информационных структур, разработка и анализ моделей информационных процессов и структур;11. Разработка методов обеспечения высоконадежной обработки информации и обеспечения помехоустойчивости информационных коммуникаций для целей передачи, хранения изащиты информации; 16. Общие принципы организации телекоммуникационных систем иоценки их эффективности. Разработка научных принципов организации информационныхслужб по отраслям народного хозяйства.

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

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

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

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

В диссертации использована общая методология математической науки, общенаучные методы анализа и синтеза, приемы описанияна символьном математическом языке свойств и связей объектов реального мира, применение методов тропической математики в сочетании с результатами классической линейнойалгебры и теории оптимизации. Указанная методология использована в тесной связи снаучными методами теории информатики, в части тех ее подходов, которые связаны сисследованием и формированием структурных характеристик информационных систем.При проведении диссертационного исследования для получения новых научных результатов использованы методы математического программирования и теории исследованияопераций, в частности – методы минимизации функций.7Методика исследования базируется на использовании методического аппарата идемпотентной алгебры для решения задач размещения, обладающего рядом преимуществ перед другими известными методами∙если традиционно использование операцийmaxиminпри формулировке матема-тических постановок прикладных задач часто усложняет их решение, то на языкеидемпотентной алгебры работа с такими операциями существенно упрощается, в силу того, что в качестве идемпотентной операции сложения можно взять одну из операцияmaxилиmin.Вследствие этого, методы данного раздела математики могутоказаться удобными и эффективными при решении минимаксных задач;∙к тому же тропический подход, заключающийся в замене обычных арифметическихопераций (+,×) на пару операций (⊕,⊗) с идемпотентным сложением, позволяетрешать задачи в общем виде, не выбирая заранее полукольцо, в котором рассматривается задача.

Так, одновременно с решением в смысле (max ,+)-алгебры получаютрешение и для других постановок ((min ,+)-алгебры, (max ,×)-алгебры и т.д.). Этосущественно расширяет область применения данного подхода;∙стоит отметить также важную особенность, заключающуюся в возможности преобразовывать сложные нелинейные задачи в линейные в терминах идемпотентной алгебры. Это позволяет использовать общие методы и результаты линейной алгебры, чточасто упрощает решение и интерпретацию полученных результатов. Так, решениеминимаксной задачи размещения точечного объекта на плоскости и в пространствесводится в терминах идемпотентной алгебры к решению параметризованной системы неравенств или к минимизации некоторой функции, заданной в матричном видес использованием свойств идемпотентного спектрального радиуса матрицы. Получение явных аналитических решений позволяет анализировать результат и следить заего изменением после введения дополнительных ограничений;∙важным преимуществом идемпотентной алгебры является то, что в отличии от итерационных решений задач оптимизации, время сходимости которых можно толькооценивать, идемпотентный подход позволяет получать аналитические решения в виде точных формул, время расчета по которым можно определить напрямую.Степень достоверности результатов обеспечивается строгими математическимидоказательствами, непротиворечивостью постановок исследовательских задач, использованием апробированной методологии и методов научных исследований, подбором достоверных исходных данных, а также проведением тестовых расчетов с использованием разработанных соискателем программных средств.

Кроме того, достоверность результатовподтверждается их близостью к ранее полученным результатами, включая геометрические решения, предложенные Д. Эльзингом и Р. Френсисом, и алгебраические решенияН. К. Кривулина, полученные с использованием альтернативных методик исследования.Апробация результатов. Результаты диссертации докладывались на ряде научных конференций, в том числе на Международной научно-практической конференции«Актуальные вопросы развития современного общества» (Курск, Россия – 2014), Международной научно-практической конференции «Тренды развития современного общества:управленческие, правовые, экономические и социальные аспекты» (Курск, Россия – 2014),7-й научно-практической internet-конференции «Междисциплинарные исследования в области математического моделирования и информатики» (Тольятти, Россия – 2016), 7-йвсероссийской научной конференции по проблемам информатики СПИСОК-2017 (СанктПетербург, Россия – 2017), Всероссийской конференции «Третьи чтения памяти профессора Б.

Характеристики

Список файлов диссертации