Аналитические и процедурные модели организации распределенных информационных систем в условиях неопределенности тема диссертации и автореферата по ВАК РФ 05.25.05, кандидат наук Копылов Сергей Александрович

• Копылов Сергей Александрович
• кандидат наук
• 2021

Оглавление диссертации кандидат наук Копылов Сергей Александрович

ВВЕДЕНИЕ

1 АНАЛИЗ СОВРЕМЕННОГО СОСТОЯНИЯ И ВОПРОСОВ ОРГАНИЗАЦИИ РАСПРЕДЕЛЕННОЙ ИНФОРМАЦИОННОЙ СИСТЕМЫ ПРИ ЕЕ СИНТЕЗЕ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ

1.1 Современное состояние вопроса организации сложных систем

1.2 Современное состояние вопроса выбора организации РИС

1.3 Применение информационных систем для решения задач выбора организации РИС

1.4 Выводы по главе

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

2.1 Построение аналитической модели нечеткой оптимизационной выбора организации РИС с типом «звезда-дерево»

2.1.1 Построение аналитической модели нечеткой оптимизационной задачи выбора организации РИС с типом «звезда-дерево» при ограничении узлов ветвления

2.1.2 Построение аналитической модели нечеткой оптимизационной задачи выбора организации РИС с типом «звезда-дерево» (общий случай)

2.2 Построение аналитической модели нечеткой оптимизационной задачи выбора организации РИС с типом «дерево-дерево»

2.2.1Построение аналитической модели нечеткой оптимизационной задачи выбора организации РИС с типом «дерево»

2.2.2Построение аналитической модели нечеткой оптимизационной задачи выбора организации РИС с типом «дерево-дерево»

2.3 Выводы по главе

3 ПРОЦЕДУРНЫЕ МОДЕЛИ ВЫБОРА ОРГАНИЗАЦИИ РИС РАЗЛИЧНЫХ ТИПОВ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ

3.1 Разработка процедурных моделей решения задач выбора организации РИС с типом «звезда-дерево»

3.1.1 Разработка процедурной модели решения задачи выбора организации РИС с типом «звезда-дерево» при условии идентичности параметров узлов ветвления информационных потоков

3.1.2 Разработка процедурной модели решения задачи выбора организации РИС с типом «звезда-дерево» (общий случай)

3.2 Разработка процедурной модели решения задачи выбора организации РИС с типом «дерево-дерево»

3.2.1 Разработка процедурной модели решения задачи выбора организации РИС с типом «дерево»

3.2.2 Разработка процедурной модели решения задачи выбора организации РИС с типом «дерево-дерево»

Выводы по главе

4. ВЫЧИСЛИТЕЛЬНЫЙ ЭКСПЕРИМЕНТ С ИСПОЛЬЗОВАНИЕМ РАЗРАБОТАННЫХ МОДЕЛЕЙ

4.1 Описание моделей и схем информационной системы организации РИС с различным типом

4.2 Вычислительный эксперимент выбора организации РИС с типом «звезда-дерево»

4.2.1 Вычислительный эксперимент выбора организации РИС с типом «звезда-дерево» при условии идентичности параметров узлов ветвления информационных потоков

4.2.2 Вычислительный эксперимент выбора организации РИС с типом «звезда-дерево» (общий случай)

4.3 Вычислительный эксперимент выбора организации РИС с типом «дерево-дерево»

4.3.1 Вычислительный эксперимент выбора организации РИС с типом «дерево»

4.2.2 Вычислительный эксперимент выбора организации РИС с типом

«дерево-дерево»

Выводы по главе

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

ПРИЛОЖЕНИЕ А

АКТЫ ВНЕДРЕНИЯ

Введение диссертации (часть автореферата) на тему «Аналитические и процедурные модели организации распределенных информационных систем в условиях неопределенности»

ВВЕДЕНИЕ

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

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

Однако, как и прежде, основным требованием, предъявляемым к РИС, остается эффективность. Именно она определяет, насколько РИС

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

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

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

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

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

сложных систем, такие, как работы Ю.Ю. Громова, В.М. Белова,А.Г. Додонова, А.В. Душкина, И.О.Ивановой, Б.С. Рябинина, В.Ф. Крапивина, Ю.М. Парфенова, И.А. Флейшмана, Д.В. Ландэ, И.Ю. Стекольникова, D.-Z. Du, M.X. Cheng, Y. Li.

Результаты анализа публикаций, в которых представлены результаты работ, полученные отечественными и зарубежными авторами, в оптимизации, проектировании и моделировании РИС позволили выделить основные направления: оптимизация количества и распределения узлов ветвления в РИС; определение структуры и характеристик связей между как конечными, так и узлами ветвления.

Многие авторы, как отечественные, так и зарубежные, посвятили свои работы разработке методов синтеза структуры РИС, а также их анализу. Эти вопросы были рассмотрены в таких работах, как работы М. В. Губко, В.В. Кульба, А. Дойча, Р. Бесслера, В.Д. Тюрина, Г.Т. Артамонова. В работах Г.Г. Савина, В.Г. Лазарева, Б.А. Столярова, Г.Ф. Янбых, B.C. Лукьянова, A.W. Neebe и M.R. Rao, L.R. Bahl и D.T. Tang, H.G. Dysart и N.D. Georganas были представлены эвристические методы синтеза структуры РИС, основанные на положении узлов ветвления.

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

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

Научная задача исследования заключается в построении математического обеспечения, позволяющего обеспечить снижение стоимости организации РИС заданного типа при обеспечении уровня качества функционирования не ниже заданного при неопределённости ряда параметров.

Объект исследования: типы распределённых информационных систем.

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

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

1. Предложить аналитические модели выбора организации РИС типа «звезда-дерево».

2. Предложить аналитические модели выбора организации РИС типа «дерево-дерево».

3. Разработать процедурную модель решения задачи выбора организации РИС типа «звезда-дерево».

4. Разработать процедурную модель решения задачи выбора организации РИС типа «дерево-дерево».

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

Научная новизна:

1. Аналитическая модель выбора организации РИС типа «звезда-дерево» при неопределённых параметрах (мощности информационного потока, объёме передаваемого сообщения, скорости передачи информационного потока), отличающаяся введением в рассмотрение соответствующих нечётких переменных и применением релаксации Лагранжа с последующей декомпозицией.

2. Процедурная модель выбора организации РИС типа «звезда-дерево», отличающаяся применением декомпозиционного подхода с использованием нечётких переменных Ь-Я типа, характеризующих мощность информационного потока, объём передаваемого сообщения, скорость передачи информационного потока, и разработанного эвристического подхода для заданных значений функций принадлежности.

3. Аналитическая модель выбора организации РИС типа «дерево-дерево» при неопределённых параметрах (мощности информационного потока, объёме передаваемого сообщения, скорости передачи информационного потока), отличающаяся введением в рассмотрение соответствующих нечётких переменных и применением релаксации Лагранжа с последующей декомпозицией.

4. Процедурная модель выбора организации РИС типа «дерево -дерево», отличающаяся применением декомпозиционного подхода с использованием нечётких переменных Ь-Я типа, характеризующих мощность информационного потока, объём передаваемого сообщения, скорость передачи информационного потока, и разработанного подхода для заданных значений функций принадлежности.

Теоретическая и практическая значимость работы.

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

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

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

Положения, выносимые на защиту:

1. Аналитическая модель выбора организации РИС типа «звезда-дерево» при неопределённых параметрах (мощности информационного потока, объёма передаваемого сообщения, скорости передачи информационного потока).

2. Процедурная модель выбора организации РИС типа «звезда-дерево» с использованием нечетких переменных L-R типа.

3. Аналитическая модель выбора организации РИС типа «дерево-дерево» при неопределённых параметрах (мощности информационного потока, объёма передаваемого сообщения, скорости передачи информационного потока).

4. Процедурная модель выбора организации РИС типа «дерево-дерево» с использованием нечетких переменных L-R типа.

Степень достоверности и апробация результатов.

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

Материалы диссертационного исследования и полученные результаты были представлены научному сообществу и одобрены им на следующих конференциях: «Техника и безопасность объектов уголовно-исполнительной системы» (Воронеж 2018); XVI Всероссийская школа-конференция молодых ученых «Управление большими системами» (Тамбов 2019); Международная научно-техническая конференция "Актуальные проблемы прикладной математики, информатики и механики" (Воронеж 2019); Международная научно-практическая конференция «Системы управления, математическое моделирование, автоматизация и энергоэффективность SUMMA 2019» (Липецк 2019); «Актуальные проблемы прикладной математики, информатики и механики» (Воронеж, 2020) и др., а также на семинарах кафедры «Информационные системы и защита информации» ФГБОУ ВО «ТГТУ» и Межвидового центра подготовки и боевого применения войск радиоэлектронной борьбы Российской Федерации (учебный и испытательный).

Всего по теме диссертации опубликовано восемнадцать работ, среди которых 2 публикации в журналах, индексируемых в международных базах цитирования Web of Science и Scopus, 3 публикации в журналах, рекомендуемых ВАК при Министерстве науки и высшего образования РФ для публикации основных результатов диссертации, 5 публикаций в прочих изданиях, входящих в ВАК при Министерстве науки и высшего образования РФ и 8 публикаций в сборниках трудов международных и всероссийских конференций.

Внедрение результатов исследования. Результаты работы использованы при подготовке бакалавров на кафедре «Мехатроника и технологические измерения» Института автоматики и информационных технологий (ИАИТ) ФГБОУ ВО «ТГТУ», Тамбовском областном государственном бюджетном учреждении «ЦОКСОН», ООО «ТН-ГРУ1111», Межвидовом центре подготовки и боевого применения войск РЭБ (учебный и испытательный), Управлении информационных технологий, связи и

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

Объём и структура работы.

Диссертация, общий объем которой составляет 148 страниц, состоит из введения, четырех глав, заключения, списка использованной научной литературы, включающего 127 наименований научных трудов на русском и иностранных языках, и приложения. Диссертация содержит 48 иллюстраций и 36 таблиц.

Работа соответствует пункту 6: «Сетевые информационные ресурсы и технологии...» (паспорт специальности 05.25.05 «Информационные системы и процессы»).

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

1 АНАЛИЗ СОВРЕМЕННОГО СОСТОЯНИЯ И ВОПРОСОВ ОРГАНИЗАЦИИ РАСПРЕДЕЛЕННОЙ ИНФОРМАЦИОННОЙ СИСТЕМЫ ПРИ НЕОПРЕДЕЛЕННОСТИ ПАРАМЕТРОВ ФУНКЦИОНИРОВАНИЯ

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

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

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

1.1 Современное состояние вопроса организации сложных систем.

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

немало авторов, которые разрабатывают собственные математические приемы для описания формы этого компонента в системном контексте [38].

Чаще всего встречаются два вида действий, которые производят над элементами: выборка и распределение элементов [39]. Специалисты отмечают, что в большинстве своем задачи, которые соответствуют данным видам действий над элементами, формируются в полной независимости друг от друга [25]. В формате общей картины данные задачи имеют полную совместимость, поскольку по логике одна вытекает из другой, то есть их решение требуется выполнять в рамках общей модели [37].

На данный момент существует несколько способов для произведения выборки элементов. Наиболее простые из них - на "глазок" [42] и с применением априорной информации [28]. К подобным методам по классификации можно также отнести таксономические методы [27, 28]. Данные методы берут за основу разбиение совокупности данных на непустые и непересекающиеся множества.

Когда используется нечеткая информация, применяют иные методы. Данные методы берут за основу построение функций принадлежности [29] с последующим их использованием при решении задач, связанных с разделением и сравнением с эталоном [40], а также при построении нечетких классификаций [6-13].

В различных литературных источниках можно найти много информации о методах, применяемых для выявления признаков объектов [9, 11]. Данные методы можно разделить на две группы [11]. Подобное разделение основывается на редукции признаков, способных дать характеристику изучаемому объекту. Методы, которые дают неполную редукцию, специалисты относят к первой группе, а ко второй соответственно методы, дающие полную редукцию [14]. Также стоит отметить, что для того, чтобы получить полную либо не полную редукцию можно использовать факторный анализ [15]. Иными методами считаются: метод потенциалов [9] и центра тяжести [10].

Методы, подходящие для решения задач по организации систем, условно делят на простые, основанные на организации перебора, и математического программирования [6]. Ввиду того, что первая группа методов обладает низкой эффективностью, а задачи, связанные с организацией систем, являются МР-полными задачами [16], то для решения подобных задач принято использовать методы, относящиеся ко второй группе [1, 3, 5, 7, 17].

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

В 1947 году была создана методика, предназначенная для решения задач линейного программирования с одним главным критерием. Именно она получила широкое распространение и большое количество публикаций, посвященных ей от разных авторов [6, 17, 18]. Однако метод линейного программирования имеет ограниченную область применения и далеко не все задачи организации систем можно решить с его помощью.

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

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

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

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

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

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

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

1.2 Современное состояние и вопросы выбора организации РИС.

Синтезирование РИС возможно только после нахождения ответа на некоторые основообразующие вопросы:

1. Какое количество узлов ветвления в РИС и где место их расположения?

2. Какой вид имеет тип конечных узлов и узлов ветвления в РИС?

3. Какой тип взаимосвязи применен между узлами ветвления потоков информации и центральным узлом в РИС [19-27]?

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

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

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

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

2. Нахождение оптимальных решений для объединения конечных узловых элементов с ближайшим ветвителем по минимальному пути.

Если вышеуказанные задачи решать многократно, то можно добиться получения приемлемого решения для текущей задачи. Кроме того, были разработаны, помогающие решить эти задачи рекурсивно, жадные эвристические алгоритмы. Данные алгоритмы отличаются своей простотой, однако, полученное через них решение не является оптимальным для общей задачи [18, 29].

Ранее классические задачи о местоположении узла ветвления изучались такими учеными, как: H. G. Dysart и N. D. Georganas,E.A. Березин, Л.С. Турин, И.П. Норенков, P. McGregor и D. Shen,H.n. Бусленко, Л.А. Растригин, В.В. Братищенко, L. R. Bahl и D. T. Tang, A. W. Neebe и М. R. Rao, а также G. M. Schneider и M. N. Zastrow, которые представили различные алгоритмы для решения этой задачи [30-32]. Однако исследования, которые производились ранее, не рассматривали способов, предназначенных для оценки качественных характеристик решения, например, величину отклонения от нижней границы [33, 34].

Благодаря алгоритму, который смог разработать Э. Мирзаян, получилось получить нижнюю границу, в случае, когда у конечного узла одинаковая коммуникационная нагрузка на РИС, то этот алгоритм был основан на применении релаксаций Лагранжа [35]. Алгоритм похожего

действия так же был представлен Клиенцевицем и Луссвом, и Ло и Кершенбаумом [36, 37]. Другой исследователь Х. Пиркуль занимался разработкой другой модели, которая отличалась более высокой эффективностью и включала в себя существенную оптимизацию в сравнении с моделями, которые другие исследователи рассматривали ранее [38]. В последующем настоящий алгоритм был модифицирован Пиркулем. Здесь был добавлен функционал для увеличения площади покрытия. Одновременно возникла необходимость решать задачи по усовершенствованию надежности и отказоустойчивости системы.

В основном большинство алгоритмов основано на соединении конечных узловых элементов с узлами ветвления или централизации РИС.

Когда вышеперечисленные методы предполагают связь конечных узлов с центральным узлом РИС или одним или несколькими узлами ветвления, снижение стоимости синтеза достигается путем создания множественных конечных узлов. Целью данных действий является использование низкоскоростных или среднескоростных линий связи, а также метода "опроса". Как правило, решение данной задачи решается рекурсивно и не зависит от расположения узла ветвления [40]. Большая часть эвристик, которые были разработаны для произведения синтеза подобных систем, берут за основу фундаментальное решение Кляйнрока, доказавшего в свое время, что сумма средних загрузок подсистем системы является большим количеством запросов полной загрузки системы [41]. Есть еще один путь к золотой середине, который не загружает РИС большим количеством запросов. Он заключается в произведении корректировки мощности в процессе формулировки задачи. Мощность снижают, что гарантирует стабильную работы в моменты ее пика, однако, при этом загруженность РИС не достигает своего максимума. То есть, если известен средний уровень загруженности, то это может принести пользу в процессе создания большой локальной РИС. Это послужило основанием для создания новой задачи по

обходу дерева с минимальными показателями мощности (CMST), при идентичности параметров конечных узлов (рис. 1.1).

Х. Пападимитриу нашел доказательства того, что настоящая задача принадлежит к разряду МР-полных [58].

- Центральный узел РИС 2 ■ - Узел ветвления информационных потоков в РИС ф - Конечный узел РИС

Рисунок 1.1 - РИС с типом «звезда-дерево»

Решения задачи CMST стало главной целью для всех научно-исследовательских работ. Учитывая принадлежность задачи к так называемым №-полным, Грэвиш в ходе наблюдений не исключил того, что в использованной модели, основанной на методе ветвлении и определения границ, нет достаточного потенциала для решения задачи в оптимальном режиме, поскольку вычислительные процессы потребляют очень большое количество времени.

Список литературы диссертационного исследования кандидат наук Копылов Сергей Александрович, 2021 год

я - я

Я = {я, др (Я)}, где др(Я) = ^ я0 — я , Я =< Яо, я,, Яр >

Яр(Я) = "

яр - яо ^ /¿у /¿уь

А = {/;,Д£(/;)}, гДе^(А0 = < А' о, ь, р >

Я ..(/• ■) = Ар А ^ ^ А'р - А'о

/¿ р - /¿

С/Ш = {сУШ, Дс7т(СУш)}, где (С/Ш) = ^

¿С(С;Ш) = С;Ш ^

ЯС(С/Ш) =

СУшо СУШ! л-- _ Со - С,™ , С/Ш =

Р С/Ш

7 т) = 7

С/шР °/то

< С- С- С- >

Ш Ш Ш

где Мс^(Суш),Мс(Одр?(Я), Д/^СА) - функции принадлежности;^^,

Яо, /¿у - моды;СуШ1, С;ШР, , , Яь, Яр, /¿у1,/¿уР - левый и правый интервал

нечеткости параметров С/Ш, Я?, соответственно. Функция,

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

В соответствии с имеющимся ограничением (2.73) каждому узловому элементу выделяется только один экземпляр дуги. Следующий

V

ограничительный комплекс (2.74) служит для подтверждения существования межузлового потока. В качестве подтверждения возникает реальная связь.

Другие действующие ограничители (2.75 - 2.77) затрагивают мощностные характеристики. Соединительные функции регулирует ограничитель (2.78) (потокосохранение).

Ограничение (2.79) устанавливает истинность соединения при наличии сгенерированной дуги. Ограничение (2.80) позволяет установить один ветвитель с неустановленной мощностью (т) на всех отрезках РИС.

Ограничительный комплекс (2.81 - 2.83) обеспечивает удержание и положительное значение переменных.

Рассматриваемую проблему (2.72 - 2.83) можно отнести к задачам с труднонаходимым решением.

Доказательство: возьмем в рассмотрение случай, при котором стоимости всех дуг будут идентичны, и при этом показатель мощности каждой дуги (Я) будет равен «?». Исходя из этого, показатель мощности каждого узла ветвления будет равен общему трафику - число конечных узлов). Таким образом, задача сводится к задаче о размещении объекта. Исходя из того, что по своей сути эта задача относится к классу ЫР-полных задач, то и задача, которая была представлена в аналитической модели (2.72)-(2.83), по аналогии является ЫР-полной.

Для получения значений, более близких к нижней границе добавлены следующие ограничения:

Ограничение на непрерывание (2.84)

Ги* < ^кЕШиЫХ]кт VI Е Р, V]■ Е Ш. (2.85)

Чтобы решить настоящую проблему возьмем в качестве основного инструмента традиционный Лагранжев метод множителей [6]. Здесь надо учитывать появление нечетких чисел в целом ряде параметров. Данный тип данных соответствует ЬЯ - модели.

Вывод: задача расходится на две параллельные, в которых необходимо отыскать решение для Ьи Я представлений нечеткого числа.

Пусть 7={ЬД}. Введем неотрицательные множители Лагранжа а1, а2, а3, а4, а5, а6.Тогда задача (2.1)-(2.8) представляется в виде двух задач.

С учетом того, что ряд значений являются нечеткими числами ЬЯ-типа, из чего следует, что поставленная задача преобразуется в две задачи для Ь представления нечетких чисел и Я представления. Пусть 7={ЬД}. Умножив ограничения (2.74)-(2.77), (2.79) и (2.85) на неотрицательные множители а1,а2,а3,а4,а5,а6, которые также добавлены в функцию (2.72), получен Лагранжиан

XX«

+ХХ

¿Е}} ¡ЕШиИ

кт

+ ХХХ ъЛГц^Ы

1Е! ¡ЕШкЕШиЫ

Е кЕ

Е

+ ХХ "Чк^Гцк-*'*

]ЕI кЕРиМ

1]к ^ Х]к

Е

+

(2.86)

X X Гт - X-ЖтЪкт) + ХХ ЪуХ -

] ЕР кЕРиМ ЬЕ1 ЬЕ1 ЬЕ1 ]ЕР

- Х Х¥1кт} + ХХ Х а6^\}к-ХЧт.^ кЕРиМ тЕЯ ЬЕ1 ]ЕР кЕРиМ тЕЯ

при ограничениях (2.67), (2.72), (2.74)-(2.78)

а2^>0,У1ЕР,) Е I, (2.87)

а4]к > 0, V],г Е Р,а4)к >0, У],кЕ1 (2.88)

а1}к >0,У]ЕР,гЕШи ^а1]к > 0, V] Е 1,к Е Р и С (2.89)

а5] >0, У]ЕР,У] ЕШ ,г ЕШ и N (2.90)

аЧ] >0,У1Е Р, ) Е Ш,ащ > 0, VI Е I, ] Е Р (2.91)

> 0, VI е Р, у е ж,г eЖuN, а6.. > 0, vi е I, j е Р

(2.92)

Лагранжиан (2.86), (2.73), (2.78), (2.80)-(2.84), (2.87)-(2.92) декомпозирована на три подзадачи. Подзадача 1:

Х Х ^ (293) ;'еР&еРиМтеР ¿е/ ¿е/

с ограничениями (2.80),(2.82), (2.87), (2.90)-(2.92). Подзадача 2:

ZZ«

iew yewuw

(2.94)

-ZZ Z ^k^k-ZZ^^-'^-

¿6/ yewfcewuw _/e/ fce/

-Z Z ai;kÄZ^'k + ZZ ^ min

;'6Z k6PUN ¿6/ ;'6P

с ограничениями (2.73), (2.81), (2.87)-(2.89), (2.91). Подзадача 3:

Эта подзадача состоит из |I| подзадач следующего типа: Для каждого i 6 /:

Z Z «2W/V+ZZ<V/V+Z Z %кЛ,к +

fc6WUW ;'6/ k6/ ;'6/ fc6PUW

+ Z Z %-k/zi;k + Z Z ;'6P k6PUW ;'6P k6PUW

с ограничениями (2.78), (2.83), (2.87)-(2.91).

Обобщая решения трех подзадач: (2.93), (2.80), (2.82), (2.87), (2.90)-(2.92); (2.94), (2.73), (2.81), (2.87)-(2.89), (2.91); (2.95), (2.78), (2.83), (2.87)-(2.91); получим решение Лагранжиана (2.86), (2.73), (2.78), (2.80)-(2.84), (2.87)-(2.92).

(2.95)

2.3 Выводы по главе 2.

Были разработаны следующие аналитические модели:

1. Аналитическая модель выбора организации РИС с ТЗД, минимизирующая стоимость синтеза РИС.

2. Аналитическая модель выбора организации РИС с ТЗД, минимизирующая стоимость синтеза РИС, при условии идентичности информационных потоков;

3. Аналитическая модель выбора организации РИС с ТД, минимизирующая стоимость синтеза РИС;

4. Аналитическая модель выбора организации РИС с ТДД, минимизирующая стоимость синтеза РИС.

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

3 ПРОЦЕДУРНЫЕ МОДЕЛИ ВЫБОРА ОРГАНИЗАЦИИ РИС РАЗЛИЧНЫХ ТИПОВ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ

3.1. Разработка процедурных моделей решения задач выбора организации РИС с типом «звезда-дерево».

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

На первом этапе модель типовой аналитики создает условия для выявления общих элементов между узлами ветвления РИС и центральным узлом РИС, в том случае, если параметры и связи между узлами ветвления и центральным узлом РИС идентичны.

Во второй модели, представляющей собой аналитическую модель нечеткой оптимизационной задачи выбора организации РИС с ТЗД, работают обобщенные системы, поскольку требований к идентичности связей и узлов ветвления нет.

3.1.1 Разработка процедурной модели решения задачи выбора организации РИС с типом «звезда-дерево» при условии идентичности параметров узлов ветвления информационных потоков.

Рисунок 3.1 передает графическую форму модели процедурного типа нечеткой оптимизационной задачи. Рассматривается РИС с ТЗД [21, 22] и сохранение общих параметров ветвителей потоков информации.

Поэтапная структура модели:

1. Инициирование счетчика цикла = 1.

2. Назначаются необходимые значения нижнего предела и лучшего варианта выполнения задачи для данной модели (2.7)-(2.20).

Рисунок 3.1 - Процедурная модель решения задачи выбора организации РИС с ТЗД при условии идентичности параметров узлов ветвления информационных потоков

3. Создаются значения Лагранжиана (2.23), (2.8), (2.13) -(2.16), (2.18) -(2.21), (2.24) -(2.29).

4. Решение входящих подзадач (2.30), (2.19), (2.27) -(2.29); (2.31), (2.8), (2.18), (2.24) -(2.28); (2.32), (2.14) -(2.17), (2.25) -(2.29).

5. Вычисление Лагранжиана (2.23), (2.8), (2.13) -(2.16), (2.18) -(2.21),(2.24)-(2.29).

6. В случае превышения результата по Лагранжиану нижнего предела, итератор цикла возвращается к пункту 2.

7. В том случае если результат можно оптимизировать, происходит переход к следующему пункту (2.7)-(2.20).

8. Оптимизация результата.

9. Если полученное значение, представляющее собой разницу между нижним пределом и допустимым вариантом <1%, а также при превышении циклов итерации 800 процесс поиска останавливается. В противном случае следует переход к следующему пункту.

10. Счетчик итерации увеличивается на одно значение и переходит к новому циклу (см. пункт 2).

В Лагранжиане (2.23), (2.8), (2.13)-(2.16), (2.18)-(2.21), (2.24)-(2.29)

участвует три входящих подзадачи. Решение данных подзадач (2.30), (2.19), (2.27)-(2.29) получается при помощи определенной процедуры. Схематично данная процедура изображена на рисунке 3.2.

В нее входят следующие последовательные действия: Решение первой подзадачи: 7 е Р

1. Вычисление относительно каждого ветвителя потоков данных в

РИС по формуле:

Результат сохраняется в векторном значении - V.

2. Произвести сортировку вектора V в порядке неубывания.

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

ЬЕР

Е Р

Решение второй подзадачи:

В ходе решения второй подзадачи создается дерево, настроенное на малый сектор охвата с централизацией в корне N.

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

Начало

Для каждого узла ветвления ВЫЧ11 слить и сохранить в вгктор V.

I

Сортировать Уъ неубывающем порядке

Сделать (¡.т) ицд ешсамн первого элемента V

НЕТ

= 1

Удалить все элементы ] из V

Рисунок 3.2 - Процедурная модель решения подзадачи (2.30), (2.19),

(2.27)-(2.29)

Допустим, что (а1*, а2*, а3*, а4*, а5*, а6*) представляет собой оптимальное соотношение значений Лагранжиана (2.23), (2.8), (2.13)-(2.16), (2.18)-(2.21), (2.24)-(2.29). В этом случае, чтобы получить значения, приближенные к оптимальным, для нахождения множителей применяется

алгоритмическая основа оптимизации по субградиенту. Это дает возможность получить нижний предел положительного значения в решении данной задачи [53].

Полученные в результате решения подзадач (2.30), (2.19), (2.27)-(2.29) и (2.31), (2.8), (2.18), (2.24)-(2.28) переменные ( у* и Х*у) функционируют по следующему принципу:

1. Присвоить Ху = 1 если соблюдено условие = 1.

2. Предварительно создать условие, при котором У^у = 1, только в случае Ху* = 1.

В соответствии с пунктами применения модели 1 и 2 можно с большой долей вероятности предсказать, что ожидаемый результат достичь не удастся при некоторых условиях:

• Произошло присоединение ветвителя к недоступному узлу. В этом случае получаем У^ у' = 1, но Ху = 0.

• Если качество связи достаточно мощное, то возможно превышение данного значения. В этом случае получаем в результате выполнения выражения |5 ¿)|>Р- 1, соответственно в содержится ветвление узлов из поддерева данного корня I.

• Возможно превышение мощности на некоторых точках ветвления за пределы ограничения, тогда |5 ¿(у)| > С, где] £ Ж.

Исходя из анализа полученной информации и данных процедуры нахождения результатов для каждой итерации цикла Лагранжиана (2.23), (2.8), (2.13)-(2.16), (2.18)-(2.21), (2.24)-(2.29), можно отметить эффективность данной модели с точки зрения эвристического принципа выполнения условий.

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

• р(0- является завершающей точкой связи вектора исходящей из ¡. Соответственно Уф( ¿) = 1;

• - является определением выражения стоимости в качестве

дополнительной функции для ликвидации связи ( ¿, р(0), а также

прибавление связующего звена ( I , &).

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

Процедурная поисковая модель для нахождения положительного результата по Лагранжиану, в составе аналитической модели нечеткой оптимизационной задачи выбора организации РИС с ТЗД, может быть использована в случае соответствия аналогичных параметров на точках аккумулирующих потоки данных.

Модель выполняется поэтапно последовательно. Всего существует три этапа (Рисунок 3.3).

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

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

На отработке второго этапа происходит смена ветвителей для узловых элементов с текущих на минимизированные по показателю стоимости.

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

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

Действия будут постоянно повторяться, до тех пор проявляются неосуществимости.

Первый этап:

1.0 = (у е ш\х]- = 1},и = ш -С у = (у еЩб 1е р. уч = 1).

2. Справедливо для всех ] Е V:

До тех пор, пока правдиво выражение Б^) > 0(Т^* = тт(Тг}, V Р Е Б^у гЕРи0и( назначить

Хiw(i) = ° У1к* = 1

ЗД) = ЗД) - (0 }

Второй этап:

1. V = (у Е 0^0') > с)

2. V ] Е V:

До тех пор, пока правдиво выражение 0)| > ^Б^) > С) (Т^* = тт(Т^}, V Р Е Б^'), V г ЕРи0и( ,г € БЩ). Назначить У^) = 0, У^* = 1 БгЦ) = БгЦ) - (1} }Х,т= = 1 Третий этап:

1. До тех пор, пока правдиво выражение (3 1 Е 1^. (0| > К)(3 I Е Р№Ц)\> Й) {и* = тт(|Б^и)|:и Е Р,Б(и)1 > Й,ю(и) Е Ш}

Тк*с* = пап(Ткс1с Е Р \J0vQ, с € Б1(и*), к Е 51(и*)}у^0с)* = 0, Ук*с* = 1 БЬ(и*) = Б^и*) - (к} }

Рисунок 3.3 - Процедурная модель поиска допустимого решения Лагранжиана в аналитической модели выбора организации РИС с ТЗД при условии идентичности параметров узлов ветвления информационных

потоков

3.1.2 Разработка процедурной модели решения задачи выбора организации РИС с типом «звезда-дерево» (общий случай).

Следующее графическое изображение 3.4 наглядно показывает процесс вычисления результата для процедурной модели нечеткой оптимизационной задачи выбора организации РИС с ТЗД [24], не имеющего пороговых значений по идентичности узлов ветвления информационных потоков.

Рисунок 3.4 - Процедурная модель решения задачи выбора организации РИС с ТЗД (общий случай)

Решение состоит из последовательного выполнения настоящих этапов:

1. Инициирование счетчика цикла = 1.

2. Назначаются необходимые значения нижнего предела и лучшего варианта выполнения задачи для данной модели (2.33)-(2.44).

3. Указываются значения Лагранжиана (2.47), (2.34), (2.39), (2.41)-(2.45), (2.48)-(2.53).

4. Решение входящих подзадач (2.54), (2.41), (2.43), (2.48), (2.51)-(2.53); (2.55), (2.34), (2.43), (2.48)-(2.50), (2.52); (2.56), (2.39), (2.44), (2.48)-(2.53).

5. Вычисление Лагранжиана (2.47), (2.34), (2.39), (2.41)-(2.45), (2.48)-(2.53).

6. В случае превышения результата по Лагранжиану нижнего предела итератор цикла возвращается к пункту 2.

7. В том случае, если результат можно оптимизировать, то происходит переход к следующему пункту (2.33)-(2.44).

8. Оптимизация результата.

9. Если полученное значение, представляющее собой разницу между нижним пределом и допустимым вариантом <1%, а также при превышении циклов итерации 800, процесс поиска останавливается. В противном случае следует переход к следующему пункту.

10. Счетчик итерации увеличивается на одно значение и переходит к новому циклу (см. пункт 2).

Разбираем происходящие процессы выполнения аналитической

Несколько подзадач входят в данный Лагранжиан (2.47), (2.34), (2.39), (2.41)-(2.45), (2.48)-(2.53), в нашем случае их три. Эволюционирование данной системы происходит поэтапно-последовательно.

Для подзадачи № 1 решение выглядит следующим образом: 1. Если существует мощность узла, обеспечивающего ветвление информационных потоков, выражаемая формулой(/, т):у £ Р, т£ Я] £ Р, т £ R , необходимо получить значение

С последующим сохранением в векторное значение V. Данное решение аналогично уже имеющемуся варианту из вышеизложенного описания

2. Производится сортировка векторных величин в порядке неубывания.

3. Параметры (¡*,т*) служат для индексации начального значения V.

4. В случае достижения условия > 0 процесс останавливается.

модели:

5. Задается Х^*т* = 1.

6. Элементы, идущие под индексом у* , удаляются из массива V.

7. Производится переход к пункту 3.

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

Графическое представление процедуры изображено на блок-схеме (рисунок 3.5)

Рисунок 3.5 - Блок-схема процедуры решения подзадачи (2.54), (2.41),

(2.43), (2.48), (2.51)-(2.53)

Для подзадачи №2 решение примет следующую форму:

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

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

Для подзадачи № 3 решение находится путем вычисления оптимального маршрута от некоторого узла i определенного условием задачи к централизующему узлу Q. В процессе решения применяется Дейкстеровксий алгоритм вычисления требуемого значения в данной графе.

Аналогично уже рассмотренной схеме, допустим, что (аI, а*, а*, а**, а*, а*,) представляет собой оптимальное соотношение значений Лагранжиана. В этом случае, чтобы получить значения, приближенные к оптимальным, для нахождения множителей применяется алгоритмическая основа оптимизации по субградиенту.

Это дает возможность получить нижний предел положительного значения в решении данной задачи.

Переменные, полученные в ходе решения подпроцессов (2.54), (2.41), (2.43), (2.48), (2.51)-(2.53); (2.55), (2.34), (2.42), (2.48)-(2.50), (2.52); (2.56), (2.39), (2.44), (2.48)-(2.53) Y* и X* можно использовать согласно следующему примеру:

1. Задается значение равное Xjm = 1, в том случае если Х*т = 1.

2. Предварительно назначается Ytj = 1,при условии, что полученное Y * = 1.

В соответствии с п.п 1 и 2, есть повышенная вероятность наступления негативного исхода тестирования при наступлении одного и более условий:

1. Ветвитель j, к которому делается подключение вне зоны доступности [HiEPJ' EW,Yij, = 1,Xj,m = 0}*y.

2. Повышение значений мощности межузловых связей^(0| > R — 1, где i Е Р, St(i)= является массивом узлов поддерева с корневым ветвителем i.

3. Превышение пограничных значений по мощности для некоторых узловых элементов, выраженное в следующей записи: ISt(j)| > Cjm, где j EW,mE K,Xjm Е К Е R.

Исходя из анализа полученных результатов, положительное решение может быть найдено с помощью разбиения на три этапа разработанной процедурной модели нечеткой оптимизационной задачи поиска, удовлетворяющего решения Лагранжиана, в аналитической модели нечеткой оптимизационной задачи выбора организации РИС с ТЗД (рисунок 3.6): Этап I:

1.0 = еш,тек, х]т = 1}, и = ш -о, V = {/ е и\з1 ер, те К: У1] = 1}

2. Для каждого ] еУ Для каждого ] е V пока > 0| делать

(г* = а^ттгериощ{Т1Г1 VI е Б^)},к* = а^ттк е юоис^к1, Vi е

^ 0)}

Задать

У1г(1) = 0, у1г* = 1, ^ОО = БЩ) - {0 Обновить множество V }. Этап II: 1.

О = [(],т)\] е О, те К, Х]т = 1, БЩ) > С]т},Т = [(], т) IУ е О, м. е Я, У]т = 1, (]) > Qjm} 2У(],т) е Б:

пока фУ) > С]т),(№(1')1 > Qjm), делать {

г* = агдтт {Т^, VI е St(j)}

гериоид, г^Бга)

Задать

У1Р(1) = 0, у1г* = 1, Б^) = БЩ) - {1} Обновить множество О }. Этап III:

1. Пока 0 | i е 1,^ (0 i > К},[^ е Р, ^(01 > &} делать

и* = агдтт\\Б1(и)1 : |5г:(и)| > Ё, р(и) Е Ш}(к*,с*) = агдтт {Ткс}

иер '

кЕБг(и*), сериои(2

с£Б1(и*)

У^(к*) = 0» Ук*с* = 1

Бг(и*) = Бг(и*) - {к*}хг*р(г1 = 0,хг*ч* = Ш (и*) = Бг(и*) - {г*}}.

начало

О = { .1 ) е Р. т е К. \"|Ш = 1>

<

>

к = ai g.mil! { Г»,ь|, V \ е Л7(/> }

к е /иОиС

I

Обновить множество V

I

Т= (0, т) j е О. т е Л, У„„ = I, Ь«]) > д,,,,)

■

<

1

>

к* = аг£Ш1И1 { V 1 е }

к е £>1_|<Г, к е 5г(у)

I

1Р(0 °|Х,Ь

I

Обновить множество Т

т

{11 1 е I. \Ыр)\ • К}

Ят(ч ) - ЯНи ) - {г

х

конец

Рисунок 3.6 - Процедурная модель поиска допустимого решения Лагранжиана в аналитической модели выбора организации РИС с ТЗД без ограничения на идентичность параметров узлов ветвления информационных

потоков (общий случай)

3.2 Разработка процедурной модели решения задачи выбора организации РИС с типом «дерево-дерево».

3.2.1 Разработка процедурной модели решения задачи выбора организации РИС с типом «дерево».

Рисунок 3.7 представляет графическую схему рассматриваемой процедурной модели нечеткой оптимизационной задачи выбора организации РИС с ТД [23, 27].

Модель включает в себя такие этапы как:

1. Инициирование счетчика цикла = 1.

2. Назначаются необходимые значения нижнего предела и лучшего варианта выполнения задачи для данной модели (2.57)-(2.64).

3. Указываются значения Лагранжиана (2.66), (2.58), (2.62), (2.63), (2.65), (2.67)-(2.69).

4. Решение входящих подзадач (2.70), (2.58), (2.65), (2.67)-(2.69); (2.71), (2.62), (2.67)-(2.69).

5. Вычисление Лагранжиана (2.66), (2.58), (2.62), (2.63), (2.65), (2.67)-(2.69).

6. В случае превышения результата по Лагранжиану нижнего предела, итератор цикла возвращается к пункту 2.

7. В том случае, если результат можно оптимизировать, происходит переход к следующему пункту.

8. Оптимизация результата.

9. Если полученное значение, представляющее собой разницу между нижним пределом и допустимым вариантом <1%, а также при превышении циклов итерации 800, процесс поиска останавливается. В противном случае, следует переход к следующему пункту.

10. Счетчик итерации увеличивается на одно значение и переходит к новому циклу (см. пункт 2).

11. В отличие от предыдущих моделей, в данном случае Лагранжиан (2.66), (2.58), (2.62), (2.63), (2.65), (2.67)-(2.69) разделен на две входящих подзадачи.

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

Рисунок 3.7 -Процедурная модель решения задачи выбора организации

РИС с ТД

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

Итак, по определению (а2, а*2,а.Х) может считаться оптимальным вариантом для решения Лагранжиана.

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

Точка завершения w(i), идущая из векторной связи узловой величины Р. Возможны изменения условий функционирования. Данная функция может служить как для удаления, так и добавления связей. Если дополнительные параметры создают риск зацикливания или падению мощности, можно считать, что итоговая величина будет стремиться к бесконечности.

Переменные, полученные в ходе решения подпроцессов У2 и X2 , можно использовать согласно следующему примеру:

1. Задается значение равное Х^т = 1, в том случае если Х2т = 1.

2. Задается значение равное Уц = 1,в том случае если = 1.

3. В соответствии с п.1, есть повышенная вероятность наступления негативного исхода тестирования при наступлении одного и более условий:

- Рост графика мощности межузловых связей^(0| > Й — 1, где1 Е Р,

Б1(1)= является массивом узлов подствола с корневым ветвителем ¡.

Исходя из анализа полученных результатов, положительное решение процедурной модели нечеткой задачи поиска, удовлетворяющего решения Лагранжиана, в аналитической модели нечеткой оптимизационной задачи выбора организации РИС с ТД (рисунок 3.8) проводится поэтапно -последовательно, тремя этапами.

н* = тт {\51(и)\} и Ю

(>•*.{}+} =аг£»11п{Г»ц} г <1 / С

¡7 &(и*)

Хгц- = О. ЛГ, = 1 $'<"') = ж(и*) - {Г*}

1-

Рисунок 3.8 - Процедурная модель поиска допустимого решения Лагранжиана в аналитической модели выбора организации РИС с ТД

I:

Пока О = ¡1 \ ¡еР, №(0\>Ё} то

и* = агдтт{1Б1(и)\}

и ЕРПО

^*,с*) = аг^т (Ткс}

Ук*ы(к*) = 0, Ук*с* = 1,Бг(и*) = 5г(и*) - {к*} }

II:

Оптимизировать локально можно при помощи агрессивного алгоритма, заменяющего текущие ответвления.

Этап III:

1. Найти Г = ащттК = QwШ + QJ■W(J■) — + Qji}, I Е Р

2. При К > 0,

= ° ЦшО) = 0

У^(])] = 1, уп = 1 Возврат к 1.

3. Завершение.

3.2.2 Разработка процедурной модели решения задачи выбора организации РИС с типом «дерево-дерево».

Графическая схема данной процедурной модели РИС с ТДД [25] изображена на рис 3.9 и осуществляется последовательно следующим образом:

1. Инициирование счетчика цикла = 1.

2. Назначаются необходимые значения нижнего предела и лучшего варианта выполнения задачи для данной модели (2.72)-(2.83).

3. Указываются значения Лагранжиана (2.86), (2.73), (2.78), (2.80)-(2.84), (2.87)-(2.92).

Рисунок 3.9 -Процедурная модель решения задачи выбора организации

РИС с ТДД

4. Решение входящих подзадач (2.93), (2.80), (2.82), (2.87), (2.90)-(2.92); (2.94), (2.73), (2.81), (2.87)-(2.89), (2.91); (2.95), (2.78), (2.83), (2.87)-

(2.91).

5. Вычисление Лагранжиана (2.86), (2.73), (2.78), (2.80)-(2.84), (2.87)-

(2.92).

6. В случае превышения результата по Лагранжиану нижнего предела, итератор цикла возвращается к пункту 2.

7. В том случае, если результат можно оптимизировать, то происходит переход к следующему пункту (2.72)-(2.83).

8. Оптимизация результата.

9. Если полученное значение, представляющее собой разницу между нижним пределом и допустимым вариантом <1%, а также при превышении циклов итерации 800, процесс поиска останавливается. В противном случае, следует переход к следующему пункту.

10.Счетчик итерации увеличивается на одно значение и переходит к новому циклу (см. пункт 2).

Есть две входящих подзадачи формирующих Лагранжиан. Процедура решения подзадачи №1 показана на изображении 3.10 и выполняется последовательно по шагам:

1.Любой УВ с известной мощностью можно получить по выполнению выражений:

С последующим сохранением в векторную величину V.

2.Производится сортировка векторных величин в порядке неубывания.

3. Параметры(]*, г*, т*) служат для индексации начального значения V.

4. В случае достижения условия У]*г*т* > 0 процесс останавливается.

5. Ввод Х]-*г*т* = 1^)*к*т* = 1.0

6. Элементы, идущие под индексом/* удаляются из массива V.

7.Производится переход к пункту 3.

По завершении текущей процедуры полученный оптимальный результат сохраняется в вектор X*.

ЬеР

ЬеР

Рисунок 3.10 - Блок-схема процедуры решения подзадачи (2.93), (2.80),

(2.82), (2.87), (2.90)-(2.92)

Подзадача два выполняется по пути вычисления оптимального маршрута от некоторого узла ¡, определенного условием задачи, к центральному узлу N. В процессе решения применяется Дейкстеровксий алгоритм вычисления требуемого значения [47].

Аналогично уже рассмотренной схеме, допускается, что (а1, а2, а*3, а.\, аЗ, а*6) представляет собой оптимальное соотношение значений Лагранжиана. В этом случае, чтобы получить значения, приближенные к

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

Переменные X* и Y*, которые были получены в ходе решения подзадач (2.93), (2.80), (2.82), (2.87), (2.90)-(2.92); (2.94), (2.73), (2.81), (2.87)-(2.89), (2.91); (2.95), (2.79), (2.83), (2.87)-(2.91) будут использованы следующим образом:

1. Задать Xjrm = 1, при условии, что Xjrm = 1, где г G W U N.

2. Предварительно задать Yi j = 1, если Yij = 1.

В соответствии с п-п 1 и 2, есть повышенная вероятность наступления негативного исхода тестирования при наступлении одного и более условий:

1. Попытка присоединения части узлов к недостижимому ветвителю

U = [г G W|Xjrm = 1, Xjim = 0, V/ G W U N, Vm' G K}

2. Соединения узлов принимают цикличность.

3.Попытка присоединения части узлов к недостижимому ветвителю /: [ i|i G Р, j' G W, m G K, Yij' = 1, Xj'm = 0} Ф <p.

4. Возможность превышения мощности связи между конечными узлами. |S t(i)| > R - 1, |St(i)| > K - 1, где i G I, St(i) =, где i G Р, = множеству узлов в поддереве с корнем i.

Некоторые узлы ветвления, в частности, могут нарушать ограничение по мощности, то есть S t(j) > Qjm, где у G W, m G K, Qjm = 1.

Были введены дополнительные обозначения: w(i) - определена как конечная точка направленной связи из узла P, то есть Yiw(i ) = 1 ; Tir - функция стоимости, определенная как дополнительная стоимость удаления связи ( i ,w(i))) и добавления связи(/, г). 7jr = œ в том случае, когда дополнение к связи ( i, г) приводит к циклу или нарушению мощности; PredQ (j) - набор узлов ветвления - предшественников узла ветвления j в базовой РИС.

Аналогично предыдущим решениям в данной модели вводятся дополнительные параметры, относящиеся к стоимости межузловых связей. Данная поисковая модель схематично представлена на рисунке 3.11.

Структурная модель поэтапной спецификации: Этап I:

1. Любому у, так, что

згеи = {ге ш\х]гт = 1, хг1т> = 0, ч1ешиы, чт' е к} зкеи = [к е Р1У]кт = 1,У]кт' = 0,ч 1еРи с,чт' е Я}

Найти й* = argmindeWuQQjdm,t* = агдтт1еРисС]ш, где

и

Х]гт = 0,Х]а,*т = 1

2. Если 3 узел (¡,г) таким образом, что ] е PredN(r), г е PredN(j), тогда найти I* = агдтт1ем^]1т, I* = агдт1п1еР^с С]Ът.

Присвоить Х]гт = 0, Qjlm = 1. Присвоить У]Г = 0, Уц = 1. Бг(]) = Б1(]) - Ш.

Обновить массив V } Этап II:

1. о = [)\] еш, гешиы, тек, х]гт = 1}, и = ш-о, V = {/ е и\з1 е Р. Уц = 1}.о =

{)\) еР,кеРиС,теЯ,У]кт = 1},и = Р-о,У = [) еи1з 1е

I. хч = 1}

2. Для каждого/ е V:

пока |5^(/)| >0 { к* = агдтт{Т1к1У1 е St(j)}

^(1) = 0 у1к* = 1 Этап III:

1. й ={(], г, т) \], те О, теК, Х]гт = 1, БЩ) > С]гт}, Т = {(', к, т) \], к е О,те Я,У]кт,5^) > Qjkm}

2. Ч(/, г, т) е й,Ч (¡, к,т) еч Т.

пока |5^(/)| >0 { к* = агдтт{Т1к1У1 е St(j)}

УшО) = 0, У** = 1, ЗД) = БЩ) - [¿}

Обновить массив Б} Этап IV:

Ш} (к*, с*) = агдтт {Ткс}

ке|5С(и*)|, сеРиои<э с£|5С(и*)|

^к*ж(к*) = 0 Ук*с* = 1 ,хг*р(г*) = 0,Xr*q* = 1>

Б1(и*) = 5t(u*) - {к*}^(и*)| = |^(и*)| - {г*}}

Рисунок 3.11 - Процедурная модель поиска допустимого решения Лагранжиана в аналитической модели выбора организации РИС с ТДД

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

Второй этап оптимизирует узловые значения к минимальной стоимости. На третьем этапе прерывается возможность роста показателей мощности межузловых связей.

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

3.3 Выводы по главе 3.

Для достижения цели исследования разработаны следующие модели:

- процедурная модель решения задачи выбора организации РИС с ТЗД, при которых стоимость ее синтеза будет минимальна;

- процедурная модель поиска допустимого решения Лагранжиана в аналитической модели выбора организации РИС с ТЗД, отличающаяся применением эвристического подхода.

- процедурная модель решения задачи выбора организации РИС с ТД, при которых стоимость ее синтеза будет минимальна.

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

- процедурная модель решения задачи выбора организации РИС с ТДД, при которых стоимость ее синтеза будет минимальна.

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

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

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

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

4.1 Описание моделей и схем информационной системы выбора организации РИС с различной структурой.

Тестирование рассматриваемых моделей производится на алгоритмах, подготовленных в первых двух разделах.

Общее взаимодействие отражено на рис. 4.1