Содержание к диссертации
Введение
1. Анализ современного состояния и перспектив развития телекоммуникационных систем 10
1.1. Структура, условия функционирования, принципы построения и перспективы развития телекоммуникационных систем, краткий обзор основных направлений обеспечения защищенности информации в современных телекоммуникационных системах 10
1.2. Анализ угроз информации, средств и методов их нейтрализации в современных телекоммуникационных системах 39
1.2.1. Анализ угроз информации в современных телекоммуникационных системах 39
1.2.2. Анализ современных средств и методов защиты информации в современных телекоммуникационных системах ... 61
1.3. Обоснование общего подхода к решению задачи анализа телекоммуникационных систем с целью обеспечения защищенности информации в них. Постановка задачи исследований 79
Выводы 82
2. Математические модели и алгоритмы для анализа современных телекоммуникационных систем и оценки качества функционирования систем защиты информации в них 85
2.1. Математическая модель действий нарушителя безопасности по реализации им своих целей 85
2.2. Математические модели оптимизации состава комплекса средств защиты информации в современных телекоммуникационных системах 90
2.3. Применение метода встречного решения функциональных уравнений динамического программирования для решения задач оптимизации состава комплекса средств защиты информации в телекоммуникационных системах 93
2.3.1. Особенность применения метода встречного решения функциональных уравнений динамического программирования для решения задач оптимизации состава комплекса средств защиты информации в телекоммуникационных системах 93
2.3.2. Применение теории двойственности для повышения эффективности метода встречного решения функциональных уравнений динамического программирования 105
Выводы 111
3. Экспериментальная проверка и исследование разработанных математических моделей и алгоритмов оптимизации состава комплексов средств защиты информации в современных телекоммуникационных системах 112
3.1. Экспериментальная проверка эффективности разработанных матеметичесих моделей оптимизации состава комплекса средствзащиты информации в телекоммуникационных системах 112
3.2. Экспериментальная оценка эффективности метода встречного решения функциональных уравнений динамического программирования 117
3.3. Практические рекомендации по использованию разработанного математического аппарата анализа телекоммуникационных систем с целью обеспечения защищенности информации 121
Выводы 124
Заключение 125
Список используемой литературы
- Анализ угроз информации, средств и методов их нейтрализации в современных телекоммуникационных системах
- Анализ современных средств и методов защиты информации в современных телекоммуникационных системах
- Применение метода встречного решения функциональных уравнений динамического программирования для решения задач оптимизации состава комплекса средств защиты информации в телекоммуникационных системах
- Экспериментальная оценка эффективности метода встречного решения функциональных уравнений динамического программирования
Введение к работе
Наиболее эффективными средствами телекоммуникации и обработки данных в настоящее время считаются телекоммуникационные вычислительные сети с распределенными обработкой и хранением информации, на базе которых строятся современные телекоммуникационные системы (ТС) [1]. Главной целю ТС является организация оперативного и надежного обмена информацией между адресатами, а также сокращение затрат на передачу данных [2].
Создание ТС - сложная комплексная задача, требующая согласованного решения ряда вопросов [2,3]:
- выбора рациональной структуры ТС (определяется состав элементов и звеньев системы, их расположение, способы соединения);
- выбора типа линий и каналов связи между звеньями ТС и оценки их пропускной способности; обеспечения способности доступа пользователей к общесетевым ресурсам;
- распределения аппаратных, информационных и программных ресурсов по звеньям ТС; защиты информации, циркулирующей в ТС и др.
Совершенствование современных ТС должно производиться не только в области повышения степени автоматизации процессов управления и передачи информации, но и в сфере информационных потенциалов за превосходство над конкурентом в количестве, качестве и скорости получения, передачи, анализа и применения информации. Потери от нарушения целостности или конфиденциальности информации в ТС могут носить поистине катастрофический характер [1,4].
Широкомасштабная стандартизация и унификация средств вычислительной техники, программного обеспечения, протоколов информационного взаимодействия в значительной степени расширяют возможности несанкционированного воздействия на информацию в современных ТС. Подобное положение дел резко обостряет проблему защиты информации в современных ТС. Поэтому при проведении исследований и
разработке предложений по совершенствованию ТС должны быть рассмотрены принципы превосходства в сборе, обработке и передаче информации, эффективности и устойчивости управления, системного подхода [1,2].
Существует большое число работ из данной области на базе которых строятся современные и будут строиться перспективные ТС и системы защиты информации в них.
В работах В.М. Глушкова [5], Д. Флинта [6], Э.А. Якубайтиса [7,8] излагаются основные принципы построения вычислительных сетей, организация сетей передачи данных и связи, их анализ и синтез. В работе Г.Т.Артамонова и В.Д. Тюрина [9] исследуются влияние топологических характеристик сетей на их надежность, пропускную способность, стоимость и ряд других системных характеристик. В работе Г.Ф. Янбых и Б.А. Столярова [10] рассматривается проблема оптимизации физической структуры информационно-вычислительных сетей. Математические постановки задач формулируются в терминах нелинейного дискретного программирования. Методы и алгоритмы синтеза и оптимизации структуры централизованных и распределенных сетей ЭВМ с единых методологических позиций рассмотрены Ю.П. Зайченко и Ю.В. Гонта [11].
В работах В.А. Балыбердина [12,13,14] предложены единый метод исследования системы вычислительных средств сетей ЭВМ, основанный на выделении и рассмотрении совокупностей взаимодействующих информационных процессов, протекающих в системах вычислительных средств, комплекс аналитических моделей совокупностей информационных процессов для решения задач анализа сетей ЭВМ и методы многоуровневой оптимизации для решения задач синтеза.
Работы В.В. Хорошевского [15], Е.Н. Турута [16,17], O.K. Кондратьева [18] посвящены отражению прогресса, достигнутого при решении задач повышения устойчивости информационно вычислительных процессов. Работы А.Г. Мамиконова, В.В. Кульбы, С.К. Сомова, А.Б. Шелкова [19,20,21] посвящены решению вопросов повышения достоверности и сохранности программных модулей и информационных массивов в вычислительных сетях за счет организации оперативного и восстановительного резервирования.
Основой для организации мероприятий по защите информации являются законодательные акты, нормативные и руководящие документы [22-52]. Работы А.А. Молдавяна [53,54], Е.В. Касперского [55], Н.Н. Безрукова [56], Ю.В. Романец [57] посвящены изложению принципов построения, функционирования и практического использования современных средств и методов защиты информации. В работах В.А. Герасименко [58], В.В. Мельникова [59], П.Д. Зегжды [60] Л. Хоффмана [61], К. Шеннона [62] выработаны требования к современным системам защиты информации в ТС, изложены и теоретически обоснованы основные подходы к их построению, обоснована необходимость комплексного использования имеющихся средств и методов для обеспечения эффективного функционирования системы защиты.
Практическое решение вопросов синтеза сетей ЭВМ и организации их функционирования связано с развитием теории и практики оптимизации, которым посвящены работы О.Г. Алексеева [63], B.C. Михалевича [64,65], И.В. Сергиенко [66], В.Д. Киселева [67].
Приведенный перечень работ с одной стороны свидетельствует о большом опыте, накопленном в нашей стране и за рубежом в области решения задач обеспечения защиты информации, синтеза и оптимизации структуры, анализа сетей ЭВМ, особенно сетей передачи данных, и неугасающий интерес к их развитию, а с другой стороны - указывает на отсутствие единого подхода к решению всего комплекса вышеперечисленных задач.
Существующие в настоящее время работы обладают рядом существенных недостатков, к которым относятся следующие:
1. Не разработана единая методология обеспечения защищенности информации в современных ТС на этапах проектирования, эксплуатации и реконструкции;
2. Недостаточно полно формализованы модели и методы определения состава комплексов средств защиты информации в ТС;
3. Существующие постановки указанных задач предполагают их решение в процессе проектирования ТС. Исходя из этого, к разрабатываемым методам и алгоритмам их решения не предъявляется достаточно жестких требований по времени решения.
Как показывает анализ существующих математических моделей задач оптимизации состава комплексов средств защиты информации, их реализация связана с решением дискретных, иногда нелинейных задач большой размерности в короткие сроки. Это, в свою очередь порождает задачу разработки эффективных методов поиска оптимального решения.
Таким образом актуальность работы связана с необходимостью:
повышения эффективности и устойчивости функционирования современных ТС в условиях жесткого информационного противодействия;
разработки и совершенствования математического аппарата анализа ТС с целью обеспечения защищенности информации, циркулирующей и обрабатываемой в них;
исследования задачи сокращения вычислительной сложности и повышения эффективности методов решения задач дискретной оптимизации.
Научной задачей, решаемой в диссертационной работе, является разработка математического аппарата анализа современных ТС с целью оптимизации состава комплексов средств систем защиты информации включающего:
общий подход к построению информационно-вычислительного процесса и комплексных систем защиты информации в современных ТС;
модели, методы и алгоритмы оптимизации систем защиты информации в современных ТС;
способы и методы повышения эффективности методов решения задач дискретной оптимизации.
В связи с этим целью работы является обеспечение защищенности информации в современных ТС за счет рациональной организации системы защиты информации. Поставленная цель достигается решением ряда задач, позволяющим устранить перечисленные выше недостатки, существующие к настоящему времени в области их создания.
Научная новизна работы заключается в том, что:
1. Предложен общий подход к решению задачи обеспечения защищенности информации в ТС;
2. Разработана математическая модель действий нарушителя по реализации им своих целей в системе вычислительных средств защищаемой ТС, позволяющая оценивать качество функционирования системы защиты информации;
3. Формализован комплекс математических моделей оптимизации состава комплексов средств защиты информации по критериям максимума вероятности успешного противодействия системы защиты действиям нарушителя, минимума вероятности достижения нарушителем всех своих целей, минимума среднего значения потерь от действий нарушителя при реализации им всех своих целей, минимума интегрального показателя «стоимость-риск»;
4. Предложен и экспериментально проверен способ упорядочения ограничений по жесткости в методе встречного решения функциональных уравнений динамического программирования, обеспечивающий значительное сокращение числа членов условно оптимальных последовательностей и времени решения задач оптимизации состава комплексов средств защиты информации в современных ТС.
Практическая ценность работы заключается в том, что разработанные и предложенные методы, модели и алгоритмы могут быть использованы при разработке, эксплуатации и реконструкции современных ТС; методы и алгоритмы доведены до рабочих программ и позволяют решать достаточно широкий круг научно-технических задач.
Материалы диссертации докладывались, обсуждались и одобрены на XI, XII НТК Тульского АИИ 1999, 2001 гг., XVI-й научной сессии, посвященная дню радио, Тула, 1999 г.; НТК "Технические аспекты в борьбе с терроризмом в пограничном пространстве". М.: 2001 г.; XVII-й научной сессии, посвященной дню радио. Тула. 2001 г; LVII научной сессии, посвященной дню радио. М.: 2002 г; региональной научно-практической конференции "Проблемы информационной безопасности и защиты информации". Тула, 2002 г.
По теме диссертации опубликовано 16 печатных работ в различных научно-технических изданиях, в том числе журналах «Радиотехника», «Электродинамика и техника СВЧ и КВЧ».
Результаты исследований внедрены в учебный процесс Тульского АИИ, НИР «Алмаз-Развязка 2» ОАО НПО «Алмаз», «Защита», «Связь» НИИ ТЦ ФПС РФ, что подтверждено соответствующими актами реализации.
Работа содержит 138 страницы машинописного текста, 14 таблиц и 29 рисунков, 24 страниц приложений, состоит из введения, 3 глав, заключения, списка литературы из 122 наименований.
Анализ угроз информации, средств и методов их нейтрализации в современных телекоммуникационных системах
Надежная защита информации в ТС может быть эффективной лишь в том случае, если она является надежной на всех объектах и во всех компонентах системы, которые могут быть подвергнуты угрозам со стороны дестабилизирующих факторов. При этом принципиальное значение имеет однозначное определение и формирование полных перечней тех объектов и элементов, которые, с одной стороны, могут быть подвергнуты угрозам с целью нарушения защищенности информации, а с другой - могут быть достаточно четко определены (обособленны) с целью организации защиты информации [57,90].
Защита ТС и обрабатываемой в ней информации основывается на осознании и выявлении потенциальных угроз, на этапах создания, эксплуатации и реконструкции ТС [88].
Все существующие на сегодняшний день угрозы информации в ТС можно разделить на несколько больших групп по ниже приведенным критериям [93,96,97].
1) Характер источника возникновения: Случайные угрозы (вызываемые физическими воздействиями стихийных природных явлений, не зависящих от человека, ошибками или сбоями программ или оборудования, недостаточной надежностью используемых линий связи, неправильной установкой и конфигурированием сетевых операционных систем и средств защиты, а также ошибками конечных пользователей.); Преднамеренные угрозы (вызываемые деятельностью в результате сознательно предпринятых действий со стороны нарушителя);
2) Местоположение источника угроз: В пределах ТС; Вне ТС;
3) Отношение угроз к процессу обработки информации: Не зависят от процесса обработки; Проявляются в процессе обработки информации;
4) Отношение угроз к элементам ТС; Без изменения элементов ТС; С изменением элементов ТС; С физическим доступом к элементам ТС; Без физического доступа к элементам ТС.
5) Продолжительность реализации угроз: Кратковременная (свидетельствует о случайности или нежелании нарушителя привлечь к себе внимание); Долговременная (связано с устойчивой заинтересованностью в чужом информационном пространстве с целью изучения его структуры и содержания).
6) Воздействие угрозы на информационную среду: Неразрушающие (сеть продолжает функционировать нормально); Разрушающие (внесены какие-либо изменения в программы и/или данные, что сказывается на работе сети).
7) Частота попыток реализации угрозы: Разовая; Многократная. 8) Обнаружение попытки реализации угрозы: зарегистрированными (при проведении периодического анализа регистрационных данных администратором сети); незарегистрированными.
Наибольшую опасность для ТС представляют преднамеренные угрозы. Классификация преднамеренных угроз приведена на рис. 1.5. [52].
Действие преднамеренных угроз направлено практически против всех без исключения элементов ТС и отличается высокой целенаправленностью, опасностью и регулярностью.
В качестве возможных объектов воздействия могут быть [59,93,98]: операционная система, обслуживающая сеть; служебные, регистрационные таблицы и файлы обслуживания сети - это файлы паролей, прав доступа пользователей к ресурсам, ограничения по времени, функциям и т.д.; программы и таблицы шифровки информации, циркулирующей в сети. Любое воздействие на эти компоненты вызовет отказ в работе или серьезные сбои; операционные системы компьютеров конечных пользователей; специальные таблицы и файлы доступа к данным на компьютерах конечных пользователей - это пароли файлов или архивов, индивидуальные таблицы шифровки/дешифровки данных, таблицы ключей и т.д. Степень опасности воздействия на них зависит от принятой системы защиты и от ценности защищаемой информации. Наиболее опасным воздействием является копирование этой информации; прикладные программы на компьютерах сети и их настроечные таблицы (здесь для разработчиков новых прикладных программ серьезную угрозу представляет копирование, так как в ходе разработки большинство программ существуют в незащищенном виде);
Анализ современных средств и методов защиты информации в современных телекоммуникационных системах
Воздействие угроз в общем случае сводится к нарушению целостности (искажению, разрушению) или конфиденциальности (утечке), блокированию информации в ТС, то действие систем защиты должно сводиться к следующему [19,90]:
1) Предотвращение - предотвращение причин и условий ведущих к утечке, искажению или разрушению информации, используемой в ТС.
2) Обнаружение - обеспечение раннего обнаружения, даже если механизмы защиты были обойдены, факта утечки, искажения или разрушения информации.
3) Ограничение - уменьшение размера потерь от утечки, искажения или разрушения информации, если таковые имели место, несмотря на принятые меры по их предотвращению и обнаружению.
4) Восстановление - обеспечение эффективного восстановления информации при ее разрушении, искажении.
Существующие в настоящее время средства и методы защиты информации, составляющие основу современных систем защиты информации представлены на рис.1.9., они подразделяются на [57,59,60]: Организационные; Физические; Программные, аппаратные и программно-аппаратные; Криптографические средства защиты.
Каждая из разновидностей средств и методов защиты информации обладает своими достоинствами и недостатками, областью применимости, поэтому конкретный их выбор при построении системы защиты зависит от ряда факторов, таких как: структура, принципы и условия функционирования информационной системы, с учетом результатов анализа возможных целей нарушителя и угроз информации; стоимостные, эффективностные и эксплутационные характеристики средств защиты и др. [61,106].
К физическим средствам защиты относятся физические объекты, механические, электрические и электронные устройства, элементы конструкций зданий, средства пожаротушения и целый ряд других средств.
В общем случае физические средства защиты решают следующие задачи [68,90]: 1) Охрана территории; 2) Охрана внутренних помещений и наблюдение за ними; 3) Охрана оборудования и перемещаемых носителей информации; 4) Осуществление контролируемого доступа в защищаемые зоны; 5) Нейтрализация излучений и наводок, в том числе противодействие перехвату электромагнитных излучений и выявление радиозакладных устройств; 6) Препятствие визуальному наблюдению; 7) Противопожарная защита; 8) Блокирование действий нарушителя.
Физические средства защиты являются наиболее традиционными средствами охраны ТС. Данные средства защиты обычно составляют первый рубеж защиты жизненно важных элементов вычислительной системы.
Поэтому к ним предъявляют следующие требования [58,59,106]. 1) Максимальная полнота охвата контролируемой зоны; 2) Минимальная вероятность не обнаруживаемого обхода преграды нарушителем; 3) Достаточная избирательность и чувствительность к присутствию, перемещению и другим действиям нарушителя; 4) Возможность исключения "мертвых " зон и простота размещения датчиков обнаружения; 5) Высокая надежность работы в заданных климатических условиях; 6) Устойчивость к естественным случайным помехам; 7) Удовлетворительное время обнаружения нарушителя; 8) Достаточно быстрая и точная диагностика места нарушения; 9) Простота и надежность конструкции; 10) Возможность централизованного контроля событий; 11) Приемлемая стоимость.
Разработка средства удовлетворяющего всем указанным требованиям является чрезвычайно сложной задачей. Поэтому в зависимости от конкретных условий часто применяют не одно, а несколько средств физической защиты, объединяя их в один охранный комплекс. Обычно систему охраны ТС строят по многоуровневому (многорубежевому) принципу. В качестве первого (внешнего) уровня (рубежа) охраны используют системы охраны зданий или периметров территорий.
Для реализации систем физической защиты могут быть использованы самые разнообразные средства и методы, классификация которых приведена на рис.1.10. [90,94,107]. 1) СВЧ- и ультразвуковые системы предназначены для обнаружения движущихся объектов, определение их размеров, скорости и направления перемещения. Принцип их действия основан на изменении частоты отраженного от движущегося объекта сигнала (эффект Доплера).
Применение метода встречного решения функциональных уравнений динамического программирования для решения задач оптимизации состава комплекса средств защиты информации в телекоммуникационных системах
В последние годы важное место среди математических методов оптимизации занимает метод динамического программирования. Основная идея этого метода заключается в замене одновременного выбора большого числа параметров управления поочередным их выбором. В результате такой замены многомерная задача оптимизации искусственно сводится к многошаговой (многоэтапной) задаче меньшей размерности. Поэтому динамическое программирование можно определить как метод многошаговых принятий решений, позволяющий указать пути решения целого класса экстремальных задач [63-66].
Для уяснения общих принципов динамического программирования обычно рассматривается система, которая из начального состояния So за m шагов может быть переведена в конечное состояние Sw. На каждом шаге переход системы из состояния Sj в состояние Si+] осуществляется под действием управления /,-. На этом шаге будет получен выигрыш W]=w(S,Ui). Оптимизация заключается в таком выборе управления U, при котором общий выигрыш т W(U) = Y_l Wj .min.
В результате решения задачи оптимизации методом динамического программирования должно быть найдено оптимальное управление U=(Ui,U2,...,Ui,...,UJ многошагового процесса, где Ut - оптимальное управление на і-м шаге, т.е. должно быть найдено оптимальное управление на каждом шаге [117].
Аддитивность показателя эффективности W и возможность деления оптимизируемого процесса на этапы приводит к мысли пошаговой оптимизации. Эта идея и лежит в основе методов динамического программирования. Однако принцип динамического программирования не предполагает выбор оптимального управления на каждом шаге изолированного от других шагов, т.к. в этом случае получение оптимального управления в целом не гарантировано. В динамическом программировании управление на каждом шаге выбирается с учетом его последствий в будущем, т.е. на еще предстоящих шагах [118].
Среди всех шагов есть один, который не имеет последствий (будущего) - это последний шаг. Поэтому динамическое программирование предполагает анализ управляемого процесса от конца к началу. Раньше всех планируется последний шаг. Но планировать последний шаг можно лишь тогда, когда известно, чем кончится предпоследний (т-1)-и. Поэтому необходимо сделать все возможные предположения относительно окончания (т-І)-то шага и для каждого из них найти такое управление, при котором приращение показателя эффективности минимально. Решение этой задачи позволяет найти условное оптимальное управление на т-ом шаге, т.е. то управление, которое необходимо применить, если (т-1)-й шаг закончился определенным образом.
Если известно условное оптимальное управление на m - м шаге и соответствующий ему условный оптимальный выигрыш, то можно оптимизировать управление на предпоследнем (т-І)-ош шаге. Для этого все возможные предположения о том, чем кончился (т-2)-й шаг и для каждого из этих предположений находится такое управление на (т-І)-ом шаге при котором выигрыш за последние два шага (из них последний уже оптимизирован) был минимален. Далее оптимизируется управление на (т-2)-ом шаге и т.д. Одним словом, на каждом шаге ищется такое управление, которое обеспечивает оптимальное продолжение процесса от достигнутого в данный момент состояния. Этот принцип выбора носит название принципа оптимальности. Само управление, обеспечивающее оптимальное продолжение процесса относительно заданного состояния, называется условным управлением на данном шаге.
Если предположить, что известно на каждом шаге условное оптимальное управление, то можно найти и оптимальное управление на каждом шаге. Действительно, если известно начальное состояние процесса So, то для оптимального перехода в следующее состояние необходимо применить условное оптимальное управление, выбранное для первого шага, относящееся к состоянию So. Для следующего шага также известно условное оптимальное управление и т.д. [117-121].
Процесс оптимизации методом динамического программирования анализируется дважды [63-66]: - от конца к началу для нахождения условных оптимальных управлений на каждом шаге; - от начала к концу, при котором находятся оптимальное управление для каждого шага и всего процесса в целом.
Таким образом, условием применимости метода динамического программирования является возможность разбиения процесса принятия решений не ряд однотипных шагов, каждый из которых планируется отдельно, но с учетом результатов, полученных на других шагах, с целью достижения экстремума принятого критерия эффективности всего процесса [63-66].
Экспериментальная оценка эффективности метода встречного решения функциональных уравнений динамического программирования
Оценка эффективности метода встречного решения функциональных уравнений динамического программирования, использующего принцип двойственности для упорядочения ограничений по жесткости, проводилась по времени решения задач и числу итераций [122].
При экспериментальной проверке эффективности применения метода встречного решения функциональных уравнений динамического программирования для решении задач дискретной оптимизации ставились следующие задачи [122]: 1. Оценить эффективность метода при решении задач различной размерности. 2. Оценить влияние применения теории двойственности для упорядочения ограничений по жесткости на общую эффективности метода встречного решения функциональных уравнений динамического программирования. Для этого, в качестве характеристик метода встречного решения функциональных уравнений динамического программирования использовались следующие величины. Время решения задачи (tmin минимальное, tmax максимальное, tcp среднее). Количество членов условно-оптимальных последовательностей (Lmin минимальное, Lmax максимальное, Lcp среднее). Число итераций за которое производилось решение задач.
Эффективность метода встречного решения функциональных уравнений динамического программирования оценивалась при решении задач выбора состава комплекса технических средств.
Исходные данные для тестирования формировались следующим образом. Коэффициенты при переменных в целевой функции и ограничениях генерировались как независимые друг от друга целые случайные числа, по следующей схеме. си =ci-ij+virdijk=dl-1,jk +д,]к Си = dijk =0, i = 2,...,N,j = l,2,...,A,,k = l,2,...,M. Коэффициенты Vy и dijlc определялись как случайные числа равномерно распределенные на интервале 100/А(. Правые части ограничений вычислялись по следующей зависимости. N Dk = Z maxdijk, к = 1,2,..., Af, у = 1,2,..., Д.. /=i J Коэффициент Z определял жесткость ограничений и выбирался из интервала [0.3, 0.9] с шагом 0.2 .
Эксперимент проводился на вычислительном комплексе с процессором Intel Pentium III 750 MHz, с оперативной памятью объемом 256 MB, под управлением операционной системы MS Windows 98 ME. Решалось по 10 задач каждой размерности.
Результаты экспериментального исследования эффективности метода встречного решения функциональных уравнений динамического программирования при решении задачи представлены в приложении 2 и на рис.3.4,-3.7. [122].
На рис.3.4. изображена зависимость времени решения от размерности задач. Из рисунка видно, что с увеличением количества переменных время решения резко возрастает по закону, близкому к экспоненциальному. Кроме того, увеличение количества ограничений в задаче приводит к значительному возрастанию числа анализируемых вариантов, и как результат, к увеличению времени решения.
На рис.3.5. приведена зависимость среднего времени решения задач от жесткости ограничений. Из данного рисунка видно, что с увеличением жесткости ограничений (уменьшением значения коэффициента Z) время решения задач возрастает. Так при увеличении жесткости ограничений с 90 до 50% увеличивается время решения на два порядка. Однако, при увеличении жесткости ограничений более 50%) наблюдается некоторое снижение времени решения. Это объясняется тем, что в данном случае происходит значительный отсев бесперспективных вариантов и, как следствие, уменьшение числа анализируемых методом вариантов решения, что в конечном итоге приводит к снижению времени решения.
На рис.3.6.-3.7. приведены результаты оценки влияния применения теории двойственности для упорядочения ограничений по жесткости на эффективность метода встречного решения функциональных уравнений динамического программирования. Из данных рисунков видно, что предварительное упорядочение ограничений по жесткости позволяет снизить время решения от 10 до 60 раз. Этот выигрыш получается за счет того, что большинство (до 80%) решаемых задач решается за первые 2-3 итерации по наиболее жестким ограничениям.
