Содержание к диссертации
Введение
ГЛАВА 1. Анализ методов моделироваііия и оценки систем физической защиты 12
1.1. Автоматизация процессов проектирования систем физической защиты 12
1.2. Показатели эффективности систем физической защиты 19
1.3. Методы и средства оптимизации систем физической защиты 31
1.4. Постановка задачи исследования и выбор метода оптимизации 39
Основные результаты и выводы 44
ГЛАВА 2. Математическая модель системы физической защиты и оценка ее эффективности 46
2.1. Обобщенная модель систем физической защиты 46
2.2. Математическая модель систем физической защиты объекта со сложной топологией 53
2.3. Общий подход к оценке эффективности систем физической защиты 57
2.4. Эффективность систем физической защиты в условиях неопределенности 62
2.5. Пространственная модель систем физической защиты 69
2.6. Оценка эффективности рубежа защиты 72
Основные результаты и выводы 79
ГЛАВА 3. Оптимизация систем физической защиты 82
3.1. Постановка задачи оптимизации систем физической защиты, как задачи оптимального управления 82
3.2. Оптимизация систем последовательных и параллельных рубежей защиты 87
3.3. Экнивалснтные преобразования модели систем физической защиты объектов со сложной топологией 91
3.4. Оптимизация систем физической защиты объектов со сложной топологией 97
Основные результаты и выводы 103
ГЛАВА 4. Алгоритмы решения задачи оптимизации и анализ результатов 105
4.1. Алгоритм поиска последовательности операций агрегирования 105
4.2. Алгоритм решения задачи оптимизации 108
4.3. Оценка временной и емкостной сложности алгоритма 114
4.4. Анализ результатов решения задачи оптимизации для системы двух рубежей 118
4.5. Анализ результатов решения задачи оптимизации для СФЗ
со сложной топологией 123
Основные результаты и выводы 130
Заключение 132
Перечень принятых сокращений 134
Список использованных источников 135
- Автоматизация процессов проектирования систем физической защиты
- Математическая модель систем физической защиты объекта со сложной топологией
- Постановка задачи оптимизации систем физической защиты, как задачи оптимального управления
- Алгоритм решения задачи оптимизации
Введение к работе
Актуальность работы. Изменения в общественно-экономической формации, произошедшие в последние годы в России, вызвали резкое увеличение масштабов угроз безопасности военных и крупных промышленных объектов России, в первую очередь, объектов ядерно-оружейного комплекса и предприятий ядерной энергетики, объектов топливно-энергетического комплекса, химической отрасли и т.п. Это связано с образованием на территории бывшего СССР новых государств и возникшей «прозрачностью» государственных границ, с резким ростом масштабов внутреннего и международного терроризма, появлением в стране организованной преступности, а также с высоким уровнем внутригосударственной экономической и социальной напряженности. В этих условиях резко возросла потребность в развитии и совершенствовании методов и средств управления уровнем безопасностью важных государственных объектов, промышленно-хозяйственных предприятий малого и среднего бизнеса, объектов социального значения.
Рост степени организации и квалификации преступных групп, доступ преступных элементов к современным средствам вооружения, взрывным устройствам, оснащение средствами радиосвязи и спецтехникой требует расширения функциональных возможностей системы безопасности и, как следствие, ведет к усложнению ее структуры. Оперативный сбор, обработка и отображение информации от сотен и тысяч охранных и пожарных датчиков, контроль и управление доступом на территорию тысяч людей с различными правами доступа невозможны без построения централизованной информационно-управляющей системы. Поэтому важнейшая роль в современных интегрированных системах безопасности (ИСБ) объектов принадлежит системам физической защиты (СФЗ) на основе комплексов инженерно-технических средств физической защиты (ИТСФЗ), обеспечивающих решение задач обнаружения и пресечения несанкционированных действий персонала и посторонних лиц.
В условиях возрастающих возможностей современной технологии задача совершенствования средств анализа, оценки и оптимизации систем физической защиты, особенно на ранних этапах проектирования, становится все более актуальной. Это связано в первую очередь с возрастающей сложностью систем физической защиты и увеличением числа альтернативных вариантов построения системы. В то же время, важность решения задачи обеспечения безопасности объектов жизнедеятельности человека предъявляет жесткие требования к эффективности систем физической защиты и рентабельности проектных решений, что диктуется условиями рыночной экономики. При этом высокая стоимость систем физической защиты не позволяет провести практическую проверку, принимаемых проектных решений. Сложный и дорогостоящий процесс проектирования систем физической защиты предъявляет жесткие требования к проектным решениям, принятым на ранних стадиях разработки проекта.
Однако средства анализа и оптимизации СФЗ в настоящее время развивается крайне медленно. Это обусловлено наличием ряда проблем. Основная проблема состоит в том, что СФЗ представляет собой конфликтную систему с антагонистическими интересами, вследствие чего в процесс ее анализа и оптимизации вносится элемент неопределенности. Отсутствие единого понятийного аппарата и показателей эффективности приводит к увеличению влияния субъективных факторов при выборе проектных решений. Кроме того, для решения задач анализа и оптимизации СФЗ в первую очередь необходима разработка формализованного описания, показателей эффективности системы и методик их получения, способов структурного и параметрического синтеза систем защиты.
В настоящее время наметились основные тенденции решения указанных проблем: ведутся работы по созданию единого понятийного аппарата и выработке единых критериев оценки, разрабатываются методики параметрического синтеза систем физической защиты.
Вопросы создания систем физической защиты объектов нашли свое отражение в работах российских ученых Ю. А. Оленина, Л. В. Измайлова, Г. Е. Шепитько, Э. И. Абалмазова, А. М. Омельянчука и других.
В частности в работах Э. И. Абалмазова нашли свое отражение вопросы интегральной оценки систем физической защиты, вопросы получения показателей эффективности на основе вероятностных моделей рассматриваются в работах Ю. А. Оленина, А. В. Измайлова. В работах IO. А. Оленина рассматриваются вопросы применения методов системного анализа к решению задачи физической защиты объектов. Предложены методы оптимизации систем физической защиты, в частности метод матрицы угроз, предложенный А. М. Омельянчуком и другие.
Однако многие вопросы анализа и оптимизации систем физической защиты остаются нерешенными. В частности, большинство предлагаемых показателей эффективности систем физической защиты не применимы для анализа систем физической защиты объектов со сложной топологией, не позволяют в полной мере учесть взаимное влияние элементов системы. Кроме того, методики получения показателей качества системы защиты не позволяют получить интегральную оценку качества системы при наличии множества предметов физической защиты.
Предлагаемая в работе модель систем физической защиты позволяет получить интегральные показатели эффективности системы при наличии множества целей защиты, Возможность получения интегрального показателя позволила применить существующие методы оптимизации, в частности метод динамического программирования, для получения системы оптимальной по критерию «эффективность - стоимость»,
обладающей максимальной эффективностью при заданных ограничениях на используемые ресурсы на основе заданного множества вариантов реализации ее подсистем.
Результаты исследования позволили разработать алгоритм оптимизации систем физической защиты объектов со сложной топологией при наличии множества целей и его программную реализацию.
Необходимо отметить, что результаты работы могут применяться к решению задач оценки и оптимизации систем информационной безопасности, в системах контроля доступа и других технических систем.
Объект исследования - системы физической защиты важных и особо важных объектов.
Предмет исследования - процессы анализа и оптимального синтеза систем физической защиты объектов со сложной топологией.
Целью диссертационной работы является совершенствование средств анализа и оптимального синтеза систем физической защиты особо важных объектов со сложной топологией.
Для достижения поставленной цели решаются следующие задачи:
- разработка математической модели систем физической защиты объектов со сложной топологией, адекватно отображающей связи внутри системы для решения задачи оценки и оптимизации по критерию «эффективность - стоимость»;
- исследование и теоретическое обоснование функционально-стоимостных показателей эффективности СФЗ особо важных объектов;
- определение функциональных зависимостей интегральных показателей эффективности СФЗ от параметров ее подсистем;
разработка способа и алгоритмов оптимального синтеза СФЗ особо важных объектов со сложной топологией на основе заданного набора опций реализации рубежей защиты;
— теоретическое и экспериментальное исследование алгоритмов оптимального синтеза СФЗ объектов со сложной топологией.
Методологической основой работы являются методы системного анализа, методы динамического программирования, математический аппарат теории графов, теории вероятностей, теории алгоритмов.
Научная новизна работы заключается в следующем:
1. Предложена математическая модель систем физической защиты особо важных объектов на основе сети с кратными дугами. В отличие от известных модель позволяет описать СФЗ объектов со сложной топологией на заданном уровне декомпозиции и получить интегральную оценку эффективности СФЗ при наличии множества предметов защиты без применения операции редукции вектора эффективности к интегральному показателю.
2. Разработаны и обоснованы интегральные функционально-стоимостные показатели эффективности СФЗ особо важных объектов. В отличие от известных предложенные показатели позволяют выполнять оптимизацию СФЗ с учетом принципов равнопрочное™ и адекватности для предметов защиты различной категории.
3. Получены функциональные зависимости интегральных показателей эффективности СФЗ от параметров ее подсистем, позволяющие, в отличие от известных, обобщить способ количественной оценки эффективности для субъектов защиты со сложной структурой подсистем.
4. Предложены эквивалентные преобразования на взвешенных графах, которые позволяют формализовать процесс агрегирования на модели СФЗ при решении задачи оптимизации.
5. Разработан алгоритм поиска последовательности эквивалентных преобразований, приводящих исходную модель к трехэлементной модели, что позволяет представить непоследовательный процесс выбора оптимального управления последовательным.
6. Предложен способ оптимизации СФЗ особо важных объектов со сложной топологией. В отличие от известных предложенный способ позволяет выполнять оптимизацию на всем множестве возможных вариантов реализации при заданных ограничениях на используемые ресурсы с учетом топологии и взаимного влияния подсистем СФЗ, что дает возможность значительно снизить влияние субъективного фактора на результаты оптимизации.
Практическая значимость работы состоит в создании новых, более эффективных средств оптимального синтеза систем физической защиты объектов, что позволяет сократить затраты на разработку и повысить качество концептуального проекта. В работе получены следующие практические результаты:
1. Алгоритм оптимального синтеза систем физической защиты особо важных объектов на заданном наборе опций реализаций рубежей защиты. В отличие от известного алгоритма прямого перебора, имеющего экспоненциальную зависимость времени работы от количества опций реализации рубежей защиты, сложность предложенного алгоритма имеет линейную зависимость.
2. Программная реализация предложенного алгоритма «Analyzer», позволяющая автоматизировать процесс оптимизации СФЗ на этапе разработки концептуального проекта, существенно снизить время проектирования и влияние субъективных факторов.
Реализации и внедрение результатов. Основные результаты и положения диссертационной работы использованы ДГУП Научно-исследовательский и конструкторский институт радиоэлектронной техники (НИКИРЭТ) ФГУП «СНПО «Элерон» (г. Заречный Пензенской обл.).
Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на следующих конференциях:
- III Всероссийской научно-практической конференции «Технические средства охраны. Комплексы охранной сигнализации и системы управления доступом» (г. Заречный, Пензенская область, 2000 г.);
- IV Международной научно-технической конференции «Новые информационные технологии и системы» (г. Пенза, 2000 г.);
- XII Международной школе-семинаре «Синтез и сложность управляющих систем» (г. Пенза, 2001 г.);
- IV Всероссийской научно-практической конференции «Современные охранные технологии и средства обеспечения комплексной безопасности объектов» (г. Заречный, Пензенская область, 2002 г.);
- VI Всероссийской научно-технической конференции «Новые информационные технологии» (г. Москва, 2003 г.);
- XIV научно-технической конференции профессорско-преподавательского состава и студентов (г. Пенза, 2003 г.);
- Всероссийской научно-технической конференции «Вооружение, безопасность, конверсия» (г. Пенза, 2003 г.).
Публикации. По теме диссертации опубликованы 10 печатных работ, в том числе 5 статей, 5 тезисов докладов.
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, приложений и списка литературы из 72 наименований. Работа содержит 144 страницы основного текста, 25 рисунков и 5 таблиц.
Основные положения, выносимые на защиту:
1. Математическая модель систем физической защиты особо важных объектов со сложной топологией на основе сети с кратными дугами.
2. Интегральные функционально-стоимостные показатели эффективности систем физической зашиты и их функциональные зависимости от параметров, входящих в нее подсистем.
3. Операции параллельного и последовательного агрегирования на модели систем физической защиты с использованием преобразований на взвешенных графах.
4- Алгоритм поиска на графе последовательности эквивалентных преобразований, приводящих исходную модель к трехэлементной модели,
5- Способ решения задачи оптимизации систем физической защиты особо важных объектов со сложной топологией на заданном наборе опций реализации рубежей защиты методом динамического программирования.
б. Алгоритм оптимизации систем физической защиты особо важных объектов со сложной топологией и его программная реализация.
Автоматизация процессов проектирования систем физической защиты
В настоящее время в области создания систем обеспечения безопасности не сложилось единого понятийного аппарата. Эта проблема поднимается многими авторами [1, 2, 3,4, 5], рассматриваются причины появления и подходы к ее разрешению. В частности в [1] отмечается, что ориентация нормативной терминологии в основном под ограниченные задачи и функции вневедомственной охраны систем МВД, характерная для России, привела к тому, что для вновь развивающихся технологий безопасности в системах связи и информации, охране ядерных, нефтехимических, энергетических, крупных промышленных объектов несовершенная терминологическая система понятий вызывает логическую неоднозначность.
При решении задач обеспечения безопасности особо важных объектов (ОВО) [6] наибольшее применение находит терминология, относящаяся к обеспечению безопасности ядерно-опасных объектов [4], узаконенная международными и российскими нормативными документами [7]. В соответствии с данными документами система физической защиты представляет собой совокупность организационных и инженерно-технических мероприятий, направленных на пресечение угроз объекту со стороны вероятных внешних и внутренних нарушителей [7].
В некоторых случаях при необходимости подчеркнуть структурную или функциональную интеграцию подсистем СФЗ применяются термины интегрированная или комплексная система безопасности [5].
Жизненный цикл СФЗ включает несколько этапов [6], представленных на рис. 1.1. Этап концептуального проектирования является одним из наиболее важных этапов создания СФЗ. В первую очередь это обусловлено тем, что СФЗ представляет собой сложную «человеко-машинную» систему, что, в отличие от чисто технических систем, приводит к необходимости учета человеческого фактора [8, 9].
Другой проблемой возникающей на этапе проектирования СФЗ является тот факт, что в разрабатываемую систему входят подсистемы, преследующие антагонистические цели» т.е. наличие в системе элемента конфликта. Наличие элемента конфликта приводит к неопределенности стратегии поведения части подсистем. Как отмечается в [7], особенности проектирования конфликтных «человеко-машинных» систем, как правило, не учитываются нормативной документацией по проектированию технических систем.
Кроме того, к СФЗ ОБО предъявляются жесткие требования по надежности и эффективности решения поставленных задач. В то же время СФЗ представляет собой сложную и дорогостоящую систему, что не позволяет выполнить практическую проверку эффективности проектных решений, выбираемых из множества альтернативных вариантов се реализации. Из теории обеспечения качества известно, что на каждом этапе создания системы стоимость устранения ошибок, допущенных на предыдущем этапе, возрастает примерно в 10 раз. Как следствие существенно возрастает роль ранних этапов проектирования СФЗ -концептуального проектирования [10].
Разработка концептуального проекта (КП) включает следующие этапы [6, 10, 11]; - предпроектное обследование объекта; - разработка концепции обеспечения безопасности объекта; - разработка и оформление концептуального проекта. На первом этапе выполняется обследование предложенных заказчиком или определенных совместно стиповых» объектов. По результатам работы создается протокол предпроектного обследования, содержащего характеристики объекта и существующей СФЗ, в котором определяются: - цели и задачи физической защиты; - конкретные объекты защиты и жизненно важные центры -предметы физической защиты (ПФЗ), их категорировапис по важности; - анализ возможных угроз, разработка моделей вероятных нарушителей для всех ПФЗ объекта. На втором этапе разрабатывается концепция обеспечения безопасности объекта [6], которая определяет ПФЗ (люди, имущество, информация), угрозы (чрезвычайная ситуация, утрата, утечка и другие), адекватные меры защиты (система охранной безопасности, система информационной безопасности и другие), В ходе разработки концепции безопасности выполняется обработка результатов обследования объекта, формулируются основные принципы физической защиты (ФЗ), необходимый уровень защищенности, производится оценка уязвимости существующей системы ФЗ (для действующих объектов), разрабатывается стратегия и тактика адекватных мер защиты. Выбор стратегии построения СФЗ определяет показатели эффективности. Выделяют различные стратегии обеспечения безопасности объектов, представленные на рис. 1.2 [12]. Для объектов особой важности основной является стратегия, направленная на обеспечение максимальной эффективности защиты. Дополнительно могут применяться показатели, определяемые стратегией направленной на обеспечение максимальной средней эффективности на единицу затрат (рентабельности).
Математическая модель систем физической защиты объекта со сложной топологией
В рассмотренную выше модель СФЗ все подсистемы включены как элементарные объекты. Однако в соответствии с заданными целями построения модели необходима модель, учитывающая особенности структуры объекта защиты, субъекта угрозы и субъекта защиты.
Основой для построения модели является структура объекта защиты вследствие того, что именно структура объекта защиты является наиболее устойчивой в рамках поставленных целей моделирования по сравнению с другими элементами модели - субъектом угрозы и субъектом защиты. Это связано с тем, что структура объекта защиты в силу свойств системы 2 и 4 определяет его системные качества, и, как следствие, изменение структуры ведет к существенному изменению системных свойств объекта зашиты. В то же время в процессе разработки СФЗ структура субъекта угрозы может изменяться, а изменение системных качеств (в том числе структуры) субъекта защиты является целью всего процесса анализа.
Объект защиты, как и любая система, представляет собой структурированную совокупность элементов, взаимодействующих для образования системного качества. При построении модели эти элементы включаются в качестве элементарных объектов. При этом глубина декомпозиции определяется необходимым уровнем детализации,
В рамках поставленных целей исследования целесообразно рассматривать только те элементы объекта защиты и внешней среды, взаимодействие которых ведет к образованию целевого качества системы. Кроме того, необходимо также учитывать воздействия тех элементов объекта защиты и внешней среды, которые оказывают влияние на формирование целевого системного качества, но непосредственно не участвуют в его формировании.
Таким образом, в модель СФЗ включаются: - элементы системы «объект защиты», отражающие целевое качество системы; - элементы внешней среды и системы «объект защиты», взаимодействующие для формирования целевого системного качества системы; - элементы внешней среды и системы «объект защиты», взаимодействие которых оказывает влияние, в первую очередь опасное, на объект защиты; - связи между элементами, отражающими все взаимодействия» оказывающие влияние на целевое качество объекта защиты. Применение математического аппарата теории графов, позволяет задать математическое описание модели СФЗ объекта защиты со сложной топологией ориентированным мультиграфом S следующим образом [58]: S=S{Xfr9DfH), (2.1) где X - конечное множество вершин графа S; Г - отображение Г : X — X х z+, заданное конечным подмножеством дуг U с X х X х z+, z+ - множество неотрицательных целых чисел; DaX - множество элементов «объект защиты»; И с X - множество элементов «субъект угрозы». Более подробно свойства отображений, заданных на одном множестве, рассмотрены в [47]. Каждая вершина графа хг- є X определяет входящий в модель элемент /, а каждая дуга uij,n = xiJXjin er\xitXj є X,nez+J определяет воздействие п элемента д-;- на элемент х . В дальнейшем там, где это не приводит к разночтениям, вместо ttijn = xhxjtn будет использоваться и.-} = х х} . Необходимо отметить, что воздействие элемента х( на элемент х.- в общем случае отличается от воздействия элемента Х: на элемент х,, что определяется направлением дуг графа. Кроме того, кратность дуг графа, позволяет учесть тот факт, что воздействие элемента хі на элемент х?, в общем случае может носить различный характер. Множество D е X задает множество элементов, оказывающих опасное воздействие на объект зашиты, а Н с X задает множество элементов, определяющих проявление целевого качества объекта защиты. Для того чтобы связать полученную модель объекта защиты с моделью СФЗ, представленной на рис. 2.2, следует рассмотреть взаимодействие двух элементов модели (2.1) xt-, х.- є X, для которых существует дуга uitj = X;,Xj є Г, Элементы Xj и Xj образуют систему, в Каждый элемент, включенный в модель, представляет собой элементарный объект и обладает определенными свойствами, оказывающими влияние на целевое качество включающей его метасистемы (объекта защиты). Проявление целевого качества системы определяется свойствами элементов множества И . Таким образом, изменение свойств элемента системы ведет к изменению целевого качества объекта защиты. Как следствие каждый элемент представляет собой объект защиты относительно включающей метасистемы (объекта защиты), которая выступает в этом случае в качестве субъекта безопасности. Однако изменение системных свойств элементарного объекта в рамках системы возможно только под воздействием внешних по отношению к нему систем. Следовательно, если изменение системных качеств элемента Xj под воздействием элемента xt может носить при условиях, определяемых воздействиями элементов множества D опасный относительно метасистемы характер, то в этой системе элемент х,-является субъектом угрозы относительно элемента Xj - объекта защиты В соответствии с моделью, представленной на рис. 2.2, воздействие субъекта угрозы на объект защиты осуществляется через субъект защиты, т.е. дуга Uj : = xhXj є Г описывает субъект защиты относительно элемента -V.-. Таким образом, модель СФЗ объекта защиты со сложной топологией может быть адекватно описана ориентированным мультиграфом (2,1), При этом система произвольных взаимодействующих элементов xi9Xj є X9uitj = Xj9Xj єГ, является подсистемой ФЗ, представленной на рис. 2,2, где элемент х,- представляет собой субъект угрозы, элемент х объект защиты, а дуга и,-,- субъект защиты.
Постановка задачи оптимизации систем физической защиты, как задачи оптимального управления
Система физической защиты представляет собой сложную человеко-машинную систему с элементом конфликта свойства которой определяются множеством факторов, что значительно усложняет построение математической модели. Проведенный анализ позволил построить модель, принципиально отличающуюся от моделей СФЗ, рассмотренных в предыдущей главе.
Построение модели СФЗ осуществляется на основе структуры объекта защиты. В модель включаются все системы и связи, оказывающие влияние па целевое системное качество объекта защиты. Это позволяет максимально полно выявить все факторы, влияющие на безопасность объекта. При этом, каждый элемент модели СФЗ также рассматривается как система, что обеспечивает возможность построения модели СФЗ множества предметов защиты объекта со сложной топологией на произвольном уровне декомпозиции- Применение математического аппарата теории графов позволило получить компактное и наглядное математическое описание СФЗ,
2. Основной проблемой оценки эффективности СФЗ является неопределенность стратегии реализации угрозы субъектом угрозы. Указанная неопределенность снимается применением принципа гарантированного результата. Принцип гарантированного результата является крайне осторожным, очень пессимистическим критерием, однако, применительно к задачам оценки эффективности СФЗ особо важных объектов является вполне оправданным. При необходимости могут быть применены менее пессимистические критерии, что также допускается рассмотренной моделью.
3. Выбранное представление модели в виде сети позволяет получить интегральные показатели эффективности без применения операции редуцирования, что дает возможность решить задачу оптимизации СФЗ по критерию «эффективность - стоимость», используя показатели предотвращенного риска Э или удельного предотвращенного риска Q на единицу затрат В.
Предложенный показатель эффективности Э учитывает относительную значимость предметов защиты и вероятность возникновения угрозы, что позволяет применять его для интегральной оценки эффективности СФЗ объекта с множеством предметов защиты и угроз. Кроме того, предложенный показатель эффективности характеризует такие свойства СФЗ как равпопрочность и адекватность защиты для предметов защиты различных категории важности. 4. Представление субъекта защиты в виде системы последовательно и параллельно взаимодействующих подсистем позволило получить функциональные зависимости показателя эффективности субъекта защиты W от частных показателей. Такой подход дает возможность оценить эффективность субъекта зашиты произвольной сложности при известных параметрах его элементов, которые являются общими для большинства разрабатываемых СФЗ.
В работе используются частные показатели эффективности решения задач обнаружения Жобн, готовности lVr0T и реагирования Жрсаг сил охраны, эффективность боевого столкновения Жбс, предотвращения угрозы Гпрсд. Рассмотрены функциональные зависимости данных показателей от тактико-технических характеристик ИТСФЗ.
Алгоритм решения задачи оптимизации
Выше было показано, что алгоритм, представленный на рис. 4.1, выполняет последовательность операций агрегирования, преобразующую исходный граф в граф (3.15). Однако для решения задачи оптимизации методом динамического программирования требуется также сохранение результатов условной оптимизации и информации о структуре исходного графа. Таким образом, требуется разработка специфических структур данных и некоторая модификация алгоритма обхода графа.
В алгоритме, представленном на рис. 4Л, операции агрегирования выполняются удалением агрегируемой дуги и, для последовательного агрегирования, ее конечной вершины» при этом меняется начальная вершина агрегирующей дуги. При такой реализации алгоритма теряется информация о структуре графа. Решением проблемы может служить изменение алгоритма выполнения операции агрегирования, что требует введения дополнительных изменений структур данных. Основные структуры данных необходимые для реализации рассмотренного алгоритма приводятся в табл. 4.1. В структуру дуги графа (рубежа защиты) вводится дополнительный параметр, определяющий текущую вершину-источник дуги. Таким образом, операция последовательного агрегирования сводится к замене вершины-источника агрегирующей дуги на вершину-источник агрегируемой дуги. Однако при этом полустепень исхода и захода для вершин, участвующих в операции агрегирования, не изменяется. Для отслеживания условий агрегирования и выбора вершины на обработку необходимо введение дополнительных счетчиков обработанных входящих и исходящих дуг и изменение в соответствии с выполняемой операцией.
При выполнении операций агрегирования (шага оптимизации) для решения задачи ДП необходимо выполнить условную оптимизацию и сохранить результат. Решение задачи условной оптимизации выполняется путем вычисления для каждого значения вектора фазовых переменных как результата применения каждого значения вектора управления из допустимого множества управления и выбора вектора управления, минимизирующего целевую функцию на данном шаге. Допустимое множество управления, как было отмечено выше, задастся ограничениями, наложенными на фазовые переменные и переменные управления.
Эффективность рубежа защиты (дуги) для каждого вектора управления определяется опцией имеющей наибольшую эффективность среди всех опций реализации рубежа, допускаемых данным вектором управления. Эффективность опции определяется соответствии с выражением (2,24) методом преодоления рубежа защиты, обеспечивающего наименьшую эффективность при текущем значении вектора фазовых переменных.
Для вычисления значения целевой функции на шаге к текущему значению вектора фазовых переменных и вектора управления применяются уравнения процесса, результат которых определяет значение целевой функции на предыдущем шаге (для агрегируемой дуги), и для полученного результата вычисляется целевая функция.
Выбранное наилучшее значение вектора управления и значение целевой функции при применении данного управления для каждого значения вектора фазовых переменных сохраняются в массиве результата. Размерность массива равна мощности вектора фазовых переменных.
Массив результата и информация об агрегируемой на данном шаге дуге помещаются в начало списка агрегирования агрегирующей дуги, при этом дуги входящие в этот список имеют собственные (возможно пустые) списки агрегирования- В результате работы данного алгоритма формируется дерево агрегирования, что позволяет выполнить абсолютную оптимизацию, начиная с последней агрегирующей дуги, и получить решение задачи оптимизации. В целом рассмотренный алгоритм аналогичен алгоритму, представленному на рис, 4.1. На рис. 4.2 приводится описание алгоритма функций агрегирования.
