Диссертация (1150701), страница 2
Текст из файла (страница 2)
В современных мегаполисах есть большое количество новых районов, дорожная сетькоторых представляет собой систему параллельных и перпендикулярных между собой улиц. В этих условиях для описания задачи размещения точечногообъекта подходит прямоугольная метрика (1 -метрика). При оптимальном размещении пунктов экстренной помощи населению необходимо минимизироватьмаксимальное расстояние от объекта экстренной службы до самого дальнегоклиента (жилого дома или группы домов) с тем, чтобы сократить время реагирования на экстренный вызов и соблюсти установленные нормативы.
В силувозможных обстоятельств социального, градостроительного, технического и др.характера могут возникать разного рода ограничения на допустимую областьразмещения. Таким образом, в рассматриваемой ситуации необходимо решатьзадачу 1-центра с ограничениями на этапах проектирования, осуществлениязастройки или реорганизации городских территорий.Важно отметить, что некоторые простейшие (по исходным данным и ограничениям) из описанных выше задач имеют аналитические решения, более сложные задачи можно решить алгоритмически, например при помощи методов линейного и смешанного целочисленного линейного программирования.
Алгорит-8мический подход обычно обеспечивает численное нахождение одного из решений и требует применения специальных программных средств. Такой подходне позволяет получить все решения аналитически в виде явных формульныхзависимостей, удобном для дальнейшего анализа и непосредственных расчетов. Поэтому есть необходимость в разработке новых методов для получения вявном виде аналитических решений задачи 1-центра. Возможностью получатьтакие решения обладает подход на основе применения методов тропической математики.Таким образом, актуальной теоретической и практической задачей является разработка методов тропической оптимизации для решения задач 1-центрас прямоугольной метрикой с разного рода ограничениями на допустимую область размещения, которые возникают при исследовании принципов создания ифункционирования аппаратных средств автоматизации различных процессов,проектировании и развитии информационных систем различного назначения.Степень разработанности темы.
Диссертационное исследование базируется на теоретических положениях, методологических подходах и концептуальных выводах, обоснованных в трудах отечественных и зарубежных ученых.Значительный вклад в развитие теории и методов тропической математикивнесли Н. Н. Воробьев [11–13], В. П. Маслов [14,15], И. В.
Романовский [16–18],А. А. Корбут [19], Р. А. Кунингхайм-Грин [20], У. Циммерманн [21], Г. Л. Литвинов [22, 23], Г. Б. Михалкин [24, 25], А. Э. Гутерман [26, 27], Д. С. Голан [28],П. Буткович [29], М. Гондран [30], Д. Ю. Григорьев [31, 32], Д. Гунаварден [33],И. Итенберг [34], Г. Кохен [35], Д. Д. Лоусон [36], У. Макэнини [37], Я. Н.
Шитов [38, 39] и др.При этом учеными разрабатывались не только теоретические положения, нотакже рассматривались прикладные задачи, которые формулируются и эффективно решаются в терминах идемпотентной алгебры, составляющей важныйраздел тропической математики. Такие задачи изучались в работах Ф. Бачелли [40], Я.
Г. Олcдера [41], Б. Хейдерготта [42, 43], В. Д. Матвеенко [44–46],Н. К. Кривулина [1, 47–49], С. Л. Блюмина [50], Д. А. Николаева [51–53] и др.Описание подходов к решению задачи 1-центра с использованием евклидовой метрики приведено в работах М. Колебрука [54], Н. Мегиддо [55], А. Фоула [56], О. Худека [57] и др. Ее геометрическое решение предложено в [58], а9итерационное решение в виде алгоритма – в [59]. Оптимизационная задача Ролса с прямоугольной метрикой решена в [60, 61]. Также известно геометрическоерешение этой задачи, описанное в [62,63].
Итерационные алгоритмы ее решенияразработаны в [64–66]. Возможно также использование для ее решения методовлинейного программирования, в частности, симплекс-метода [67–70] и др. Однако, известные подходы и методы решения этих задач не позволяют получитьполного решения задач в явном виде с прямоугольной метрикой, в том числе при наличии ограничений на допустимую область размещения. Применениеитерационных методов позволяет найти частное решение задачи 1-центра в виде одной точки, одного из возможных решений задачи. Это исключает возможность аналитического исследования множества всех решений, включая корректировку этого множества при добавлении ограничений, что значительно снижает теоретическую и практическую значимость получаемых таким способомрешений.
Кроме того, вычислительная сложность решения в явном виде, можетбыть определена точно, в то время как для алгоритмических решений обычноизвестны только оценки порядка сложности вычислений. Это становится особенно важным преимуществом аналитических решений, когда полученные расчетные формулы обеспечивают низкую (например, линейную) вычислительнуюсложность.Решения некоторого класса задач размещения с чебышевской метрикой втерминах тропической математики представлены в работах [71–73] и др.Таким образом, несмотря на наличие значительного количества разработокв области тропической математики, они в незначительной степени рассматривают подходы к аналитическому решению минимаксных задач размещения точечных объектов на плоскости с прямоугольной метрикой.
Требуется обоснование новых математических методов, позволяющих эффективно решать указанные задачи, применение которых позволит рационализировать проектированиекомплексов аппаратных средств автоматизации информационных процессов, атакже решать иные прикладные задачи, связанные с развитием современныхинформационных технологий и ускорением на этой основе научно-техническогопрогресса.Цель работы – разработка новых математических методов решения минимаксных задач размещения точечных объектов на плоскости и в трехмерном10пространстве с прямоугольной метрикой на основе применения методов идемпотентной алгебры и программно-алгоритмического обеспечения для их реализации при проектировании комплексов аппаратных средств автоматизацииинформационных процессов.В соответствии с указанной целью, были поставлены следующие задачиисследования:– разработка методов решения задач оптимизации функций, заданных наидемпотентных полуполях, с несколькими переменными на основе решения расширенной задачи в векторной форме с использованием экстремальных свойств идемпотентного спектрального радиуса матрицы;– разработка методов решения задач оптимизации функций на идемпотентных полуполях с несколькими переменными с помощью сведения задачиоптимизации к системе параметризованных неравенств и последующегонахождения всех ее решений;– исследование минимаксных задач размещения с прямоугольной метрикойна плоскости и в трехмерном пространстве с ограничениями и без ограничений, включая представление этих задач в виде задач оптимизации втерминах тропической алгебры, построение прямых решений таких задачв явном виде и оценку вычислительной сложности решений;– разработка рекомендаций по оптимальному размещению центральногосервера управления в сети локальных коммуникаций и оптимальному размещению центра управления системой видеонаблюдения на основе реализации разработанных методов;– разработка на основе полученных результатов программных средств длярешения задач размещения и их практическое применение для решениятестовых задач.Соответствие диссертации паспорту научной специальности.Содержание диссертационного исследования соответствует паспорту научной специальности 05.13.17 – Теоретические основы информатики (пп.
2. Исследование информационных структур, разработка и анализ моделей информаци-11онных процессов и структур; 11.Разработка методов обеспечения высоконадежной обработки информации и обеспечения помехоустойчивости информационных коммуникаций для целей передачи, хранения и защиты информации; 16.Общие принципы организации телекоммуникационных систем и оценки их эффективности.
Разработка научных принципов организации информационныхслужб по отраслям народного хозяйства. Изучение социально-экономическихаспектов информатизации и компьютеризации общества), а также 01.01.09 –Дискретная математика и математическая кибернетика (п. 3. Математическоепрограммирование (методы минимизации функций)).Научная новизна результатов исследования заключается в разработкекомплекса математических методов оптимального размещения точечных объектов на плоскости и в пространстве с прямоугольной метрикой с использованием инструментария идемпотентной алгебры, отличающегося возможностьюполучения явных результатов в аналитическом виде, без использования итерационных алгоритмов в целях повышения эффективности организации и функционирования информационных систем и применения современных информационных технологий. Итерационные решения минимаксных задач размещенияс прямоугольной метрикой позволяют находить только частные, одноточечныерешения.
Использование инструментария идемпотентной алгебры, напротив,позволяет получать полные решения в виде явных формул, удобных для применения при решении практических задач, анализе и интерпретации получаемыхрезультатов. К тому же процедуры, построенные на основе разработанных вдиссертационной работе методах имеют меньшую алгоритмическую сложностьв сравнении с известными итерационными алгоритмами.Наиболее существенными результатами, полученными лично автором, содержащими элементы научной новизны и выносимыми дляпубличной защиты, являются следующие:– разработаны математические методы для решения класса минимаксныхзадач, заданных на идемпотентных полуполях с несколькими переменными, базирующиеся на решении расширенной задачи в векторной формес использованием экстремальных свойств идемпотентного спектральногорадиуса матрицы и на процедуре сведения задачи оптимизации к систе-12ме параметризованных неравенств с последующим нахождением всех еерешений;– получены прямые решения в явном виде минимаксных задач размещенияс прямоугольной метрикой на плоскости и в трехмерном пространстве сограничениями и без ограничений для оптимизации выбора мест локализации объектов обработки и хранения информации в информационныхсистемах, а также результаты оценки вычислительной сложности соответствующих алгоритмов;– предложены рекомендации по применению разработанных аналитическихметодов для решения задач оптимального размещения центрального сервера управления в сети локальных коммуникаций и оптимального размещения центра управления системой видеонаблюдения для обеспечениявысоконадежной обработки информации и помехоустойчивости информационных коммуникаций;– предложена программная реализация алгоритмов численного определения областей оптимального (по минимаксному критерию) размещенияточечных объектов на плоскости с прямоугольной метрикой в условияхдействия ограничений, на основе применения методов идемпотентной алгебры.Все результаты, выносимые на защиту, являются новыми и получены автором лично или при его непосредственном участии.Теоретическая и практическая значимость работы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
