- •Воронеж 2008
- •Воронеж 2008
- •Введение
- •1 Разработка средств обеспечения инофрмационных технологий в подготовке принятия решений по документационному обеспечению защиты информации в органах государственной власти
- •1.1 Информационная сфера как объект правового регулирования
- •1.1.1 Информация как объект правового регулирования
- •1.1.2.1 Официальная правовая информация
- •1.1.2.2 Информация индивидуально - правового характера, имеющая юридическое значение
- •1.1.2.3 Неофициальная правовая информация
- •1.2 Правовое регулирование в сфере обеспечения информационной безопасности в органах государственной власти
- •1.2.1 Нормативное правовое обеспечение информационной безопасности в органах государственной власти
- •1.2.2 Система нормативных правовых документов в области защиты информации в органах государственной власти
- •1.2.3 Анализ состояния нормативной правовой базы в сфере защиты информации в органах государственной власти
- •1.2.4 Проблемы правового регулирования в сфере обеспечения информационной безопасности в органах государственной власти
- •1.2.4.1 Проблемы правового регулирования в сфере обеспечения информационной безопасности в органах государственной власти на федеральном уровне
- •1.2.4.2 Проблемы правового регулирования в сфере обеспечения информационной безопасности в органах государственной власти на региональном уровне
- •1.3 Обзор зарубежного законодательства в области защиты информации
- •Другие Указы президента посвящены следующим вопросам:
- •1.4.2 Основные направления совершенствования нормативного правового регулирования в сфере обеспечения информационной безопасности в органах государственной власти
- •1.5 Основные выводы первой главы
- •2 Исследование методов и моделей поддержки принятия решений в управленческой деятельности и разработка средства принятия решений по вопросам защиты информации в органах государственной власти
- •2.1 Выявление недостатков законодательства рф в сфере поддержки принятия решений по информационной безопасности
- •2.2 Теория принятия решения в области защиты информации в органах государственной власти
- •2.2.1 Основные понятия, термины и определения
- •2.2.2 Перечень этапов процесса принятия решения
- •2.3.2 Анализ и разработка метода принятия решения в области защиты информации в органе государственной власти.
- •2.3.3 Разработка средства поддержки принятия решения в сфере информационной безопасности на основе метода анр
- •2.3.3.1 Область применения и интерфейс программного продукта
- •2.4 Основные выводы второй главы
- •3 Разработка классификации угроз безопасности информации в органах государственной власти
- •3.1 Анализ состояния современной системы защиты в органах государственной власти рф.
- •3.2 Классификация угроз безопасности информации
- •3.3 Угрозы утечки информации по техническим каналам
- •3.3.1 Угрозы утечки информации по каналам побочных электромагнитных излучений и наводок
- •3.3.2 Угрозы утечки акустической информации по техническим каналам
- •3.3.3 Угрозы несанкционированного доступа к информации в компьютерных системах
- •3.3.3.1 Угрозы несанкционированного доступа к информации на отдельном автоматизированном рабочем месте оператора
- •3.3.3.3 Угрозы от программных закладок
- •3.3.3.4 Угрозы несанкционированного доступа к информации в компьютерной сети
- •3.4 Средства съёма
- •3.4.1 Портативные средства акустической разведки
- •3.4.1.1 Проводные системы, портативные диктофоны и электронные стетоскопы
- •3.4.1.2 Акустические закладки
- •3.4.1.3 Направленные микрофоны и лазерные акустические системы разведки
- •3.4.2 Портативные средства радио-, радиотехнической разведки
- •3.4.2.1 Сканерные приемники
- •3.4.2.2 Программно-аппаратные комплексы радио-, радиотехнической разведки
- •3.4.2.3 Средства перехвата пейджинговых сообщений и контроля телефонов сотовой связи
- •3.4.2.4 Радиопеленгаторы
- •3.4.4 Портативные средства видеонаблюдения и съемки
- •3.4.4.1 Средства видеонаблюдения с дальнего расстояния
- •3.4.4.2. Средства видеонаблюдения с близкого расстояния
- •3.4.4.3 Средства фоторазведки и фотодокументирования
- •3.4.5 Классификация вирусов и программ закладок
- •3.4.5.1 Вирусы-программы
- •3.4.5.2 Загрузочные вирусы
- •3.4.5.3 Файловые вирусы
- •3.4.5.4 Полиморфные вирусы, Стелс-вирусы
- •3.4.5.5 Макровирусы, Скрипт-вирусы
- •3.4.5.6 «Троянские программы», программные закладки и сетевые черви.
- •3.4.5.7 Программные закладки
- •3.5 Основные выводы третьей главы
- •4 Типовой объект защиты органов государственной власти
- •4.1 Сегмент органов власти информационной инфраструктуры России
- •4.1.1 Органы государственной власти как объект защиты
- •4.2 Информатизация государства в представлении безопасности информации
- •4.2.1 Особенности формирования информационных технологий на информационную безопасность
- •4.2.2 Цели и задачи государства в связи с распространением угроз безопасности информации
- •4.2.3 Государственная политика использования защищенных информационных технологий
- •4.3 Условия функционирования органов государственной власти
- •4.3.1 Системы электронного документооборота в госорганах России сегодня
- •4.4 Распространение объектно-ориентированного подхода на информационную безопасность
- •4.4.1 Основные понятия объектно-ориентированного
- •4.4.2 Применение объектно-ориентированного подхода к рассмотрению защищаемых систем
- •4.5 Функционально-условный подход к типизации объекта органов государственной власти
- •4.6 Сопоставление угроз и описания объекта
- •4.7 Основные выводы четвертой главы
- •5.1 Сеть Internet
- •5.1.1 Краткие сведения об Internet
- •5.1.2 Состав сети Internet
- •5.1.3 Доступ в Internet
- •5.1.4 Перспективы развития
- •5.2.2 Определение www
- •5.2.3 Области использования www
- •5.4 Язык программирования рнр
- •5.4.1 Основы языка программирования рнр
- •5.4.2 Терминология языка программирования рнр
- •5.4.4 Безопасность php
- •5.5 Система защиты веб-портала
- •5.5.1 Основы системы защиты веб - портала
- •5.5.2 Система разграничения доступа
- •5.5.2.1 Межсетевые экраны прикладного уровня
- •5.5.2.2 Межсетевые экраны с пакетной фильтрацией
- •5.5.2.3 Гибридные межсетевые экраны
- •5.5.4 Система контроля целостности
- •5.5.5 Криптографическая система
- •5.5.6 Система обнаружения атак
- •5.6 Основные выводы пятой главы
- •Заключение
- •394026 Воронеж, Московский просп., 14
2.2.2 Перечень этапов процесса принятия решения
Принятие решения весьма сложный и емкий процесс, поэтому для его облегчения следует разбить все действия на совокупность этапов. Решения и результаты, полученные на них могут быть обратимыми и наглядно иллюстрировать принимаемое решение.
Отсюда следует, что процесс принятия решения целесообразно разделить на следующие этапы:
поиск информации;
поиск и нахождение альтернатив;
выбор лучшей альтернативы;
выбор типа задачи принятия решения;
На первом этапе собирается вся доступная на момент принятия решения информация: фактические данные, мнение экспертов. Далее строятся математические модели; проводятся социологические опросы; определяются взгляды на проблему со стороны активных групп, влияющих на ее решение.[32]
Второй этап связан с определением того, каково состояние внешней среды, других важных факторов, т. е. с определением вариантов решений (альтернатив).
Третий этап включает в себя сравнение альтернатив и выбор наилучшего варианта (или вариантов) решения.
Четвертый этап характеризуется определением к какому типу задачи относится решаемая проблема и, соответственно, какой из множества известных методов теории принятия решения, необходимо выбрать.
Из четырех приведенных этапов процесса принятия решений наибольшее внимание традиционно уделяется третьему этапу. За признанием важности поиска информации и выделения альтернатив следует понимание того, что эти этапы в высшей степени неформализованы. Способы прохождения этапов зависят не только от содержания задачи принятия решений, но и от опыта, привычек, личного стиля ЛПР и его окружения. Хотя эти же факторы присутствуют при сравнении альтернатив, здесь их роль заметно меньше. Научный анализ проблем принятия решений начинается с момента, когда хотя бы часть альтернатив и/или критериев известна.
Детализируя этапы процесса принятия решений, получим следующее:
1. Постановка проблемы, включая построение качественной модели процесса либо системы.
Формирование проблемы предполагает подробный анализ исследуемой системы. Этот анализ связан с выделением элементов системы, установлением функциональных, информационных и управляющих связей между ними, а также включает подробное описание ее функционирования. На основе анализа выделяются проблема, которая должна быть решена, и причины, вызвавшие эту проблему.
Качественная модель, полученная в результате анализа, характеризуется:
составом локальных моделей;
уровнем детализации;
размерностью;
перечнем управляемых, неуправляемых и технологических параметров.
Целесообразность декомпозиции исходной качественной модели на локальные модели зависит от ее масштаба. Выбор уровня детализации модели определяется необходимостью учета всех существующих и постоянно действующих факторов. Размерность качественной модели включает перечень всех переменных, которые делятся на: управляемые, неуправляемые и технологические.
Управляемые параметры могут быть изменены ЛПР, неуправляемые параметры существенно влияют на моделируемую деятельность, но не могут быть изменены управляющим органом. Технологические параметры представляют совокупность констант предельных значений переменных и соотношений между ними. На этом этапе формируется перечень вариантов действий, альтернатив.
2. Конструирование концептуальной модели.
Конструирование концептуальной модели предполагает подбор одной из типовых концептуальных схем, которая соответствует качественному описанию моделируемой деятельности. В качестве типовых концептуальных схем рассматриваются системы массового обслуживания, игровые модели, модели управления запасами, модели распределения ресурсов и т.д
Одной и той же концептуальной модели могут соответствовать совершенно разные качественные модели.
3. Выбор критерия эффективности.
Критерий эффективности - количественный показатель, который устанавливает степень достижения цели для каждого из вариантов принятия решения. Цель задается вне системы, обычно системой более верхнего уровня по отношению к рассматриваемой системе. В качестве показателей могут использоваться экономические (доход, прибыль, капитализация, ликвидность, мультипликатор капитала), технические (надежность, быстродействие, помехозащищенность, безопасность), социальные (уровень дохода персонала, степень воздействия на окружающую среду).[48]
К критерию обычно предъявляются следующие требования:
1) представительность - предполагает, что критерий количественно выражает цели;
2) чувствительность - это реагирование значения критерия на изменение параметра;
3) простота вычисления;
4) наличие качественного смысла.
Выбор формы критерия зависит от типа задачи принятия решения, т.е. от степени детерминированности параметров, характеризующих моделируемую деятельность. В том случае, если все параметры детерминированы, то и значение критерия является детерминированной величиной. Если параметры носят вероятностный характер, то в качестве критерия могут выступать:
1) среднее значение W;
2) комбинация W и дисперсии D: W - К • D, где К - коэффициент, учитывающий важность дисперсии;
3) вероятность наступления определенного события;
4) одно из дискретных значений критерия, которому соответствует наибольшая вероятность.
4. Построение математической модели.
Предназначен для установления количественной зависимости между показателем эффективности, характеристиками и параметрами системы: управляемыми, неуправляемыми и технологическими.
В общем случае анализируемая система может иметь т характеристик:
(2.4)
где qi – i-ая характеристика; - вектор управляемых параметров; - вектор неуправляемых параметров; - вектор технологических параметров.
Критерий эффективности определяется аналогично:
(2.5)
Математические модели делятся на аналитические, имитационные и аналитико-имитационные.[24]
Аналитические модели содержат символьное обозначение параметров, связанных между собой различными математическими операциями. Можно выделить следующие типы соотношений для аналитических моделей:
а) аналитические выражения физических законов или общепринятых правил учета хозяйственной деятельности;
б) эмпирические соотношения, которые конструируются на основе изучения данных за прошлый период, анализа технических аспектов, экспериментальных данных, правовых предписаний или сделанных предположений;
в) нормативные соотношения, которые устанавливают связи между переменными на основе предъявляемых требований.
Имитационные модели предполагают воспроизведение алгоритма функционирования системы с постоянным измерением значений наблюдаемой величины и последующей обработкой этих значений методами математической статистики.
Аналитико-имитационные модели основаны на комбинации первых двух типов моделей.
Основной недостаток имитационных моделей - это существенные затраты машинного времени для получения точных результатов. Это предопределило широкое распространение аналитико-численных моделей, которые сочетают преимущества аналитических и имитационных моделей. Идея таких моделей состоит в том, что в промежутках между редкими событиями функционирование системы описывается с помощью аналитических соотношений, а средствами имитационных моделей воспроизводятся фрагменты функционирования системы, предшествующие и последующие за наступлением редкого события.
5. Выбор алгоритма оптимизации.
Предназначен для выбора метода оптимизации. Выбор метода зависит от вида критерия и ограничений, а также от степени дискретности параметров и наличия информации об их вероятностных законах распределения. В случае невозможности использования оптимизационных алгоритмов для первоначальной реалистичной модели необходимо выбрать один из двух вариантов:
а) выполнить упрощение модели за счет принятия определенных допущений и затем к полученной модели применить точный оптимизационный алгоритм;
б) для реалистичной модели разработать эвристический алгоритм поиска решения, близкого к оптимальному.
Практический опыт свидетельствует о предпочтительности второго варианта.[40]
6. Численная реализация алгоритма.
Этот этап связан с реализацией алгоритма оптимизации и выполняется либо с помощью стандартных пакетов прикладных программ, либо разрабатываются оригинальные программные системы.
7. Сбор данных и проверка модели.
Сбор данных производится для проверки правильности разработанной модели, а также для практического использования полученных результатов с целью поддержки процессов принятия решений. Одна из задач этого этапа состоит в правильном определении степени необходимой точности исходных данных. Проверка модели включает оценку ее непротиворечивости, чувствительности, реалистичности и работоспособности. Непротиворечивость предполагает логический анализ результатов моделирования при варьировании исходных параметров. Детальной оценке подвергаются результаты оптимизационных расчетов для предельных значений параметров. Чувствительность основана на анализе изменения характеристик системы и показателя эффективности при наибольших вариациях управляемых параметров. Одним из методов проверки реалистичности модели является установление соответствия результатов моделирования известным частным случаям. Работоспособность модели связана с оценкой ресурсов, необходимых для сбора исходных и проведения машинных экспериментов.[52]
8. Анализ полученных результатов и конструирование окончательного решения.
Предполагает проведение численных экспериментов и получение количественных зависимостей, которые представляются либо в графической, либо в табличной формах.
9. Цель этапа - качественный анализ полученных результатов решений, интерпретация графических данных и конструирование системным аналитиком окончательного решения.
Приведенные этапы характерны для обоснования решений, связанных с анализом структурированных проблем, основу которых составляют объективные модели. Другая отличительная особенность таких проблем - это больше количество вариантов решений. В случае отсутствия моделей производится экспертное сравнение конкурирующих альтернатив.
Число этапов можно варьировать в зависимости от сложности, объема проблемы. Существующие методы принятия решения также используют разное количество этапов, что будет рассмотрено далее. В данном случае был дан общий перечень действий при разработке собственного метода принятия решения.[28]
2.3 Методы принятия решения
2.3.1 Классификация основных методов принятия решения
Метод (от греч «путь сквозь») — систематизированная совокупность шагов, которые необходимо предпринять, чтобы выполнить определенную задачу или достичь определенной цели, способ постижения истины. В теории принятия решения методы неуклонно развиваются и их число растет, но на сегодняшний день основными являются следующие классы:
1) методы линейного и динамического программирования (принятия решения об оптимальном распределении ресурсов);
2) методы теории массового обслуживания (принятие решения в системе со случайным характером поступления и обслуживания заявок на ресурсы);
3) методы имитационного моделирования (принятие решения путем проигрывания различных ситуаций, анализа откликов системы на различные наборы задаваемых ресурсов);
4) методы теории игр (принятие решений с помощью определения стратегии в тех или иных состязательных задачах);
5) методы теории расписаний (принятие решений с помощью разработки календарных расписаний выполнения работ и использования ресурсов);
6) методы сетевого планирования и управления (принятие решений с помощью оценки и перераспределения ресурсов при выполнении проектов, изображаемых сетевыми графиками);
7) методы многокритериальной (векторной) оптимизации (принятие решений при условии существования многих критериев оптимальности решения).[35]
Рассмотрим методы принятия решений подробнее.
1) Методы линейного и динамического программирования (принятия решения об оптимальном распределении ресурсов);
Линейное программирование— это метод оптимизации моделей, в которых целевые функции и ограничения строго линейны. ЛП успешно применяется в военной области, индустрии, сельском хозяйстве, транспортной отрасли, экономике, системе здравоохранения и даже в социальных науках. Широкое использование этого метода также подкрепляется высокоэффективными компьютерными алгоритмами, реализующими данный метод. На алгоритмах линейного программирования (учитывая их компьютерную эффективность) базируются оптимизационные алгоритмы для других, более сложных типов моделей и задач исследования операций, включая целочисленное, нелинейное и стохастическое программирование.
Задача (модель) линейного программирования, как и любая задача исследования операций, включает три основных элемента. [55]
1. Переменные, которые следует определить.
2. Целевая функция, подлежащая оптимизации.
3. Ограничения, которым должны удовлетворять переменные (критерии).
В задачах линейного программирования пространство допустимых решений всегда имеет форму выпуклого множества. Множество называется выпуклым, если отрезок прямой, соединяющий две различные точки этого множества, полностью принадлежит данному множеству. Крайней точкой выпуклого множества является точка, принадлежащая этому множеству, но которая не лежит ни на каком отрезке прямой, соединяющей две различные точки этого множества. На рисунке 2.3 показаны два множества. Множество а, которое представляет типичное пространство решений задачи ЛП, является выпуклым множеством, тогда как множество б невыпуклое.
Рисунок 2.3 - Примеры выпуклого и невыпуклого множеств.
Оптимальное (конечное) решение двухмерной задачи ЛП соответствует крайней (угловой) точке пространства допустимых решений. Этот результат основан на том факте, что в задачах ЛП любая допустимая точка представима как функция крайних точек пространства решений.
Например, в выпуклом множестве на рисунке 2.3, а имеется шесть крайних точек X1, Х2, ..., Х6, произвольную допустимую точку X можно представить как линейную комбинацию крайних точек:
(2.6)
где все коэффициенты 0 и выполняется равенство
(2.7)
Таким образом, множество крайних точек полностью определяет пространство допустимых решений.
Задачу ЛП, записанную в стандартной форме, т. е.:
1. Все ограничения (включая ограничения неотрицательности переменных) преобразуются в равенства с неотрицательной правой частью.
2. Все переменные неотрицательные.
представим в новой форме записи с использованием матричных обозначений. Обозначим через где n – мерный вектор переменных, через А — матрицу размером mn, содержащую коэффициенты левых частей ограничений, - m-мерный вектор правых частей ограничений, - n – мерный вектор коэффициентов целевой функции. С помощью матричной формы записи стандартную задачу ЛП можно представить следующим образом.
Максимизировать или минимизировать z = CX при ограничениях:
1) AX = b,
2) X0.
На основе стандартной формы для симплекс-таблиц m крайних справа столбцов матрицы А всегда можно представить в виде единичной матрицы I, для чего, возможно, придется надлежащим образом расположить переменные и использовать при необходимости искусственные переменные.
Базисное решение системы уравнений АХ = b получается путем присвоения n - m переменным нулевых значений и последующим решением системы из m уравнений относительно оставшихся m переменных. Теория линейного программирования устанавливает следующее соответствие между геометрическим определением крайних точек и алгебраическим определением базисного решения.
Крайние точки множества {X | АХ = b} Базисные решения системы АХ = b. Это соответствие означает, что все крайние точки области решений задачи ЛП полностью определяются базисными решениями системы АХ = b и наоборот. Отсюда следует, что множество базисных решений содержит всю информацию, необходимую для оптимального решения задачи ЛП. Более того, если наложить условия неотрицательности X0, поиск оптимального решения ограничится только множеством допустимых базисных решений.
Чтобы формализовать определение базисного решения, представим систему АХ = b в векторной форме
(2.8)
где вектор Рj — j-й столбец матрицы А.
Подмножество из m векторов Рj формирует базис В тогда и только тогда, когда эти векторы линейно независимы. Для этого необходимо (и достаточно), чтобы определитель матрицы В, состоящей из данных m векторов, был отличен от нуля, т.е.
det(B) 0. (2.9)
В этом случае матрица В называется невырожденной. Обозначим через ХB вектор из m переменных, ассоциированных с векторами Рj, составляющих невырожденную матрицу В. Тогда ХB будет базисным решением, если он будет решением системы ВХB = b.
Пусть В-1 — матрица, обратная к матрице В. Тогда базисное решение находим по формуле:
ХB= В-1b, (2.10)
Если выполняется неравенство В-1b0, тогда ХB будет допустимым решением.
Количество базисных решений у системы из m уравнений с n неизвестными не превышает величины
(2.11)
Для построения симплекс – таблиц также используется матричная алгебра. Рассмотрим стандартную задачу ЛП максимизировать z = CX при ограничениях
1) AX = b,
2) X0.
Эту задачу ЛП можно также записать следующим образом.
(2.12)
Для любой симплексной итерации обозначим через ХB базисный вектор переменных, а через СB — вектор коэффициентов целевой функции, соответствующих этому базису. Поскольку все небазисные переменные равны нулю, стандартная задача ЛП будет сведена к задаче с целевой функцией
z = CB XB, (2.13)
и ограничениями ВXB = b, где текущее решение удовлетворяет следующему уравнению.
(2.14)
Симплекс-таблица получается из исходной задачи ЛП путем вычислений по следующей формуле.
(2.15)
Выполнив вычисления по этой формуле, получаем (таблица 2.3):
Таблица 2.3 – Результаты вычислений
Базис |
xj |
Решение |
z |
CBB-1Pj-cj |
CBB-1b |
XB |
B-1Pj |
B-1b |
В этой таблице необходимо вычислить только обратную матрицу В-1, так как другие элементы таблицы получаются из исходных данных задачи.
Представленная симплекс-таблица является основой всех вычислительных алгоритмов линейного программирования. В частности, на ней основаны модифицированный симплекс-метод, метод решения задач с ограниченными переменными и метод декомпозиции.
Модифицированный симплекс-метод предусматривает выполнение точно таких же этапов, как и обычный табличный симплекс-метод.
Основное отличие между ними заключается в том, что в обычном симплекс-методе при переходе от одного базиса к другому используется процедура преобразования строк симплекс-таблицы с помощью метода Гаусса-Жордана, тогда как в модифицированном симплекс-методе эти преобразования осуществляются путем вычисления обратной матрицы В-1, и основные действия связаны именно с вычислением этой матрицы.
Условия оптимальности и допустимости.
Рассмотрим стандартную задачу ЛП.
Максимизировать или минимизировать z = CX при ограничениях.
(2.16)
Для данного базисного вектора XB и соответствующих базиса В и вектора коэффициентов целевой функции СB на каждой итерации вычисления значений симплекс-таблицы выполняются по следующим формулам:
(2.17)
(2.18)
где = CB B-1Pj-cj.
Из уравнения для значений z-ой строки, следует, что увеличение значения небазисной переменной xj приводит к возрастанию (убыванию) значения целевой функции z выше текущего значения CB B-1b только в том случае, если разность строго отрицательна в задаче максимизации или строго положительна в задаче минимизации.
В противном случае переменная xj не может улучшить текущее решение и должна остаться небазисной с нулевым значением. Таким образом, любая небазисная переменная, удовлетворяющая этому условию, может быть включена в базис, что, возможно, улучшит значение целевой функции. В симплекс-методе действует эмпирическое правило, которое гласит, что в качестве вводимой в базис переменной выбирается переменная, которой соответствует наибольший (по модулю) отрицательный коэффициент в z-строке в задаче максимизации или наибольший положительный аналогичный коэффициент в задаче минимизации.
Условие допустимости симплекс-метода.
Определение исключаемого из базиса вектора основано на проверке ограничения, представленного в виде равенства, соответствующего i-й базисной переменной. Это равенство имеет следующий вид.
(2.19)
Обозначим через Рk вводимый вектор, определенный из условия оптимальности, а через xk — вводимую в базис переменную, принимающую положительное значение. Поскольку все остальные небазисные переменные сохраняют нулевые значения, равенство ограничения, соответствующее базисной переменной (XB)i, можно записать следующим образом.
(2.20)
Это уравнение показывает, что при (B-1Pk)I >0 возрастание переменной xk не приведет к отрицательному значению базисной переменной (XB)i только в том случае, если будет выполняться неравенство
для всех i. (2.21)
Таким образом, максимальное значение вводимой переменной xk можно вычислить по следующей формуле.
(2.22)
Базисная переменная, на которой достигается этот минимум, становится исключаемой.
Имея условия оптимальности и допустимости, можно описать последовательность вычислений, выполняемых в модифицированном симплекс-методе.
Шаг 0. Находится начальное базисное допустимое решение. Пусть В и Св — базис и вектор коэффициентов целевой функции, соответствующих базисным переменным.
Шаг 1. Каким-либо подходящим способом вычисляется обратная матрица В-1.
Шаг 2. Для каждой небазисной переменной хj вычисляется величина
(2.23)
Если для всех небазисных переменных хj величины ≥0 в задаче максимизации или ≤0 в задаче минимизации, то вычисления заканчиваются, так как получено оптимальное решение .
Иначе на основе условия оптимальности определяется вводимая (в базис) переменная хj как небазисная переменная, которой соответствует наибольшая (по модулю) отрицательная величина в задаче максимизации или наибольшая положительная в задаче минимизации.
Шаг 3. Вычисляется вектор В-1Рj. Если все элементы этого вектора отрицательны или равны нулю, вычисления заканчиваются, так как задача не имеет ограниченного решения. Иначе вычисляется вектор В-1b. Для всех строго положительных элементов вектора В-1Рj вычисляется отношение, определенное в условии допустимости. Базисная переменная хj, которой соответствует наименьшее отношение условия допустимости, становится исключаемой из базиса переменной.
Шаг 4. Из текущего базиса В формируется новый базис путем замены в базисе В вектора Рj на вектор Рi. Выполняется переход к этапу 1 для начала новой итерации.
Динамическое программирование определяет оптимальное решение n-мерной задачи путем ее декомпозиции на n этапов, каждый из которых представляет подзадачу относительно одной переменной. Вычислительное преимущество такого подхода состоит в том, что рассматривается одномерные оптимизационные подзадачи вместо большой n-мерной задачи. Фундаментальным принципом динамического программирования, составляющим основу декомпозиции задачи, является оптимальность.
Так как природа каждого этапа решения зависит от конкретной оптимизационной задачи, динамическое программирование не предлагает вычислительных алгоритмов непосредственно для каждого этапа. Вычислительные аспекты решения оптимизационных подзадач на каждом этапе проектируются и реализуются по отдельности.
Вычисления в ДП выполняются рекуррентно в том смысле, что оптимальное решение одной подзадачи используется в качестве исходных данных для следующей. Решив последнюю подзадачу, получается оптимальное решение исходной задачи. Способ выполнения рекуррентных вычислений зависит от того, как производится декомпозиция исходной задачи. В частности, подзадачи обычно связаны между собой некоторыми общими ограничениями. Если осуществляется переход от одной подзадачи к другой, то должны учитываться эти ограничения.[26]
2) Методы теории массового обслуживания (принятие решения в системе со случайным характером поступления и обслуживания заявок на ресурсы);
Предметом теории массового обслуживания является количественная сторона процессов, связанных с массовым обслуживанием.
Целью теории является разработка математических методов отыскания основных характеристик процессов массового обслуживания для оценки качества функционирования обслуживающей системы.
Последовательность событий условно обозначим потоком. Поток, состоящий из требований на обслуживание, будет являться потоком требований.
Поток требований, нуждающихся в обслуживании и поступающих в обслуживающую систему, называется входящим потоком. Поток требований, покидающих обслуживающую систему, называется выходящим потоком.
Задачей теории массового обслуживания является отыскание функциональных зависимостей величин, характеризующих качество функционирования обслуживающей системы, от характеристик входящего потока, параметров, характеризующих возможности одного обслуживающего аппарата, и способов организации всей обслуживающей системы в целом. Качество функционирования системы существенно зависит от того, как организовано управление процессом обслуживания, поэтому задача отыскания количественных характеристик организации управления является очень важной.[48]
Большое количество проблем, связанных с массовым обслуживанием, должно быть решено при производственном планировании. В этом случае затраты усилий на детальное изучение количественной стороны процессов планирования даст большой экономический эффект и позволит более глубоко проникнуться в природу этих процессов.
Немалую пользу может оказать теория массового обслуживания на стадии технического проектирования. При проектировании весьма важным является вопрос о загруженности оборудования. Так, еще в процессе технического проектирования необходимо определить нужное количество оборудования и его мощность исходя из объемов работ, которые должны выполняться при помощи этого оборудования. При решении этой задачи необходимо учитывать такие случайные факторы, как время обслуживания, выход из строя отдельных устройств за счет поломок и время, требуемое для их устранения, а также ряд факторов, от которых будет зависеть эксплуатация этого проектируемого оборудования.
Применение методов теории позволяет установить, какие результаты могут быть достигнуты при эксплуатации проектируемого устройства еще задолго до его создания.
3) Методы имитационного моделирования (принятие решения путем проигрывания различных ситуаций, анализа откликов системы на различные наборы задаваемых ресурсов).
Имитационное моделирование — это метод, позволяющий строить модели, описывающие процессы так, как они проходили бы в действительности. Такую модель можно «проиграть» во времени как для одного испытания, так и заданного их множества. При этом результаты будут определяться случайным характером процессов. По этим данным можно получить достаточно устойчивую статистику. [46]
Имитационное моделирование — это частный случай математического моделирования. Существует класс объектов, для которых по различным причинам не разработаны аналитические модели, либо не разработаны методы решения полученной модели. В этом случае математическая модель заменяется имитатором или имитационной моделью.
Основными методами имитационного моделирования являются:
1) аналитический метод,
2) метод статического моделирования
3)комбинированный метод (аналитико-статистический) метод.
Аналитический метод применяется для имитации процессов в основном для малых и простых систем, где отсутствует фактор случайности. Например, когда процесс их функционирования описан дифференциальными или интегродифференциальными уравнениями. Метод назван условно, так как он объединяет возможности имитации процесса, модель которого получена в виде аналитически замкнутого решения, или решения полученного методами вычислительной математики.
Метод статистического моделирования первоначально развивался как метод статистических испытаний (Монте-Карло). Это – численный метод, состоящий в получении оценок вероятностных характеристик, совпадающих с решением аналитических задач (например, с решением уравнений и вычислением определенного интеграла). Впоследствии этот метод стал применяться для имитации процессов, происходящих в системах, внутри которых есть источник случайности или которые подвержены случайным воздействиям. Он получил название метода статистического моделирования.
Комбинированный метод (аналитико-статистический) позволяет объединить достоинства аналитического и статистического методов моделирования. Он применяется в случае разработки модели, состоящей из различных модулей, представляющих набор как статистических, так и аналитических моделей, которые взаимодействуют как единое целое. Причем в набор модулей могут входить не только модули соответствующие динамическим моделям, но и модули соответствующие статическим математическим моделям.
4) Методы теории игр (принятие решений с помощью определения стратегии в тех или иных состязательных задачах).
Теория игр — математический метод изучения оптимальных стратегий в играх. В теории игр рассматриваются ситуации, связанные с принятием решений, в которых два разумных противника имеют конфликтующие цели. К числу типичных примеров относится рекламирование конкурирующих товаров и планирование военных стратегий противоборствующих армий.
В игровом конфликте участвуют два противника, именуемые игроками, каждый из которых имеет некоторое множество (конечное или бесконечное) возможных выборов, которые называются стратегиями. С каждой парой стратегий связан платеж, который один из игроков выплачивает другому. Такие игры известны как игры двух лиц с нулевой суммой, так как выигрыш одного игрока равен проигрышу другого.
В такой игре достаточно задать результаты в виде платежей для одного из игроков.
Платежом называется сумма очков, получаемая игроком по окончании партии. Величина платежа зависит от исхода случайных ходов в игре и от индивидуальных выборов каждого игрока при последующих ходах. Платеж обычно принято выражать числом очков или денежной суммой; положительный платеж означает выигрыш игрока, отрицательный – проигрыш. Предполагается, что каждый игрок стремится максимально увеличить свой выигрыш.
При обозначении игроков через А и В с числом стратегий тип соответственно игру обычно представляют в виде матрицы платежей игроку А (таблица 2.4):
Таблица 2.4 - Матрица платежей
|
B1 |
B2 |
… |
Bn |
A1 |
a11 |
a12 |
… |
a1n |
A2 |
a21 |
a22 |
… |
a2n |
… |
… |
… |
… |
… |
Am |
am1 |
am2 |
… |
amn |
Поскольку игры берут свое начало в конфликте интересов, оптимальным решением игры является одна или несколько таких стратегий для каждого из игроков, при этом любое отклонение от данных стратегий не улучшает плату тому или другому игроку. Эти решения могут быть в виде единственной чистой стратегии или нескольких стратегий, которые являются смешанными в соответствии с заданными вероятностями.
Игры представляют собой строго определённые математические объекты. Игра образуется игроками, набором стратегий для каждого игрока и указания выигрышей, или платежей, игроков для каждой комбинации стратегий. Большинство кооперативных игр описываются характеристической функцией, в то время как для остальных видов чаще используют нормальную или экстенсивную форму.
Игры в экстенсивной, или расширенной, форме представляются в виде ориентированного дерева, где каждая вершина соответствует ситуации выбора игроком своей стратегии. Каждому игроку сопоставлен целый уровень вершин. Платежи записываются внизу дерева, под каждой листовой вершиной.
Экстенсивная форма очень наглядна, с её помощью особенно удобно представлять игры с более чем двумя игроками и игры с последовательными ходами. Если же участники делают одновременные ходы, то соответствующие вершины либо соединяются пунктиром, либо обводятся сплошной линией.
В нормальной, или стратегической, форме игра описывается платёжной матрицей. Каждая сторона матрицы — это игрок, строки определяют стратегии первого игрока, а столбцы — второго. На пересечении двух стратегий можно увидеть выигрыши, которые получат игроки.
5) Методы теории расписаний (принятие решений с помощью разработки календарных расписаний выполнения работ и использования ресурсов);
Теория расписаний (ТР) является частью исследования операций. ТР исследует задачи, в которых необходимо упорядочить или, другими словами, определить последовательность выполнения совокупности работ, использования каких-либо средств и т.д.
Задачи упорядочения носят самый общий характер. Они возникают там, где существует возможность выбора той или иной очередности выполнения работ: при распределении работ на производстве, составлении расписания приземления самолетов, составлении расписания движения поездов, обслуживании клиентов в обслуживающих системах и т.д.
Результаты, к которым приводит то или иное упорядочение, существенно отличаются. В ряде практических случаев эти различия принимают стоимостной характер или определяются какой-либо другой величиной.[38]
В теории расписаний рассматриваются задачи упорядочения при условии, что решены все вопросы, относящиеся к тому, что и каким образом должно быть выполнено. При этом предполагается, что не существует зависимости между характером этих решений и устанавливаемым порядком, т.е. характер работ не зависит от их последовательности выполнения. Кроме этого, предполагается следующее:
1) Подлежащие выполнению работы определены и известны полностью. Предполагается, что все заданные работы должны быть выполнены (разбиение совокупности работ на классы выполняемых и невыполняемых не входит в задачу упорядочения).
2) Однозначно определены устройства, выделяемые для выполнения заданных работ.
3) Задана совокупность всех элементарных действий, связанных с выполнением каждой из работ, и ограничений, налагаемых на порядок их выполнения. Известно также, каким образом осуществляются эти действия и что существует, по крайней мере, по одному устройству, способному выполнить каждое из них.
Основным понятием теории расписаний является понятие операции. Операцию можно рассматривать как элементарную задачу, подлежащую выполнению. Каждая операция характеризуется
1) индексом принадлежности к определенной работе,
2) индексом принадлежности к определенной машине,
3) числом, представляющим собой длительность операции.
Составление расписания для процесса обслуживания означает, что для каждой операции на временной оси задается участок, когда эта операция должна выполняться соответствующей машиной, т.е. что для каждой операции задается один или более интервалов (a1,b1), (a2,b2)… таких, что
- (b1 - a1,) + (b2 – a2) + …- равно длительности операции;
- число - значение , относящееся к X, не меньше, чем для двух операций X и Y относящихся к одной работе и таких, что ;
- каждый из интервалов (ai,bi) расположен целиком внутри одного из отрезков времени доступности соответствующей машины.
Таким образом составление расписания может рассматриваться как задача упорядочения операций, выполняемых каждой машиной.[42]
Задача теории расписаний считается заданной, если определены
1) подлежащие выполнению работы и операции;
2) количество и типы машин, выполняющих операцию;
3) порядок прохождения машин;
4) критерии оценки расписаний.
Поиск оптимального или близкого к оптимальному расписания осуществляется с помощью одного из четырех подходов:
- математического программирования;
- комбинаторного;
- эвристического;
- статистического (вероятностного).
6) Методы сетевого планирования и управления (принятие решений с помощью оценки и перераспределения ресурсов при выполнении проектов, изображаемых сетевыми графиками);
Принципиально любая задача сетевого планирования может быть сведена к решению задачи по теории графов. Анализ пакетов символьной математики на предмет использования для решения задач сетевого планирования показал, что наиболее оптимальным является наличие модулей по теории графов. При этом достаточно только четко и грамотно провести постановку задачи, подготовить данные и обработать их с использованием стандартных процедур. Сетевое планирование – это комплекс графических и расчетных методов организационных мероприятий, обеспечивающих моделирование, анализ и динамическую перестройку плана выполнения сложных проектов и разработок. Характерной особенностью таких проектов является то, что они состоят из ряда отдельных элементарных работ. Они обусловливают друг друга так, что выполнение некоторых работ не может быть начато раньше, чем завершены некоторые другие.
Основными понятиями сетевых моделей являются понятия работы, события и пути.
Работа – это некоторый процесс, имеющий протяженность во времени, требующий затрат каких-либо ресурсов и приводящий к достижению определенного результата (обозначаются стрелками).
Событие – это момент времени, когда завершаются одни работы и начинаются другие (обозначается кружком, рисунок 2.4).
Рисунок 2.4 - Обозначение события
Путь – это любая последовательность работ в сетевом графике, в которой конечное событие одной работы совпадает с начальным событием следующей за ней работы. Различают:
- полный путь – путь от исходного до завершающего события;
- критический путь – максимальный по продолжительности полный путь;
- подкритический путь – полный путь, ближайший по длительности к критическому пути.
Рисунок 2.5 - Обозначение пути
Алгоритм расчета сетевого графика общеизвестен и включает в себя расчет ранних и поздних сроков наступления событий, резервов времени каждого события и затем определение критического пути.
Современные информационные технологии позволяют использовать некоторые другие подходы в решении приведенного выше типа задач.
7) методы многокритериальной (векторной) оптимизации (принятие решений при условии существования многих критериев оптимальности решения).
Результаты исследования задач планирования и управления показывают, что в реальной постановке данные задачи являются многокритериальными.
Оценка деятельности предприятий и планирования как системы принятия решений производится на основе более десятка критериев: выполнение плана производства по объему, по номенклатуре, плана реализации, прибыли по показателям рентабельности, производительности труда и т. д.[43]
Ранее, при исследовании проблемы многокритериальности часто все критерии, кроме одного, выбранного доминирующим, принимались в качестве ограничений, оптимизация проводилась по доминирующему критерию. Такой подход к решению практических задач значительно снижает эффективность принимаемых решений.
При применении метода многокритериальной (векторной) оптимизации строится не модель окружающей нас реальности, а модель желаний, предпочтений, политики человека, принимающего решения. Один из представителей данного метода – подход аналитической иерархии (Analytic Hierarchy Process - AHP).
В начале 1970 года американский математик Томас Саати разработал процедуру поддержки принятия решений, которую назвал "Analityc hierarchy process" (AHP). Авторы русского издания перевели это название как "Метод анализа иерархий" (Саати Т. Принятие решений. Метод анализа иерархий. - М.: Радио и Связь, 1993). Этот метод относится к классу критериальных и занимает особое место, благодаря тому, что он получил исключительно широкое распространение и активно применяется по сей день, особенно в США. Постановка задачи, решаемой с помощью метода АНР, заключается в следующем.
Дано: общая цель (или цели) решения задачи; критерии оценки альтернатив; альтернативы. Требуется: выбрать наилучшую альтернативу.
Подход АНР состоит из совокупности этапов.
Первый этап заключается в структуризации задачи в виде иерархической структуры с несколькими уровнями: цели — критерии—альтернативы.
На втором этапе ЛПР выполняет попарные сравнения элементов каждого уровня. Результаты сравнений переводятся в числа.
Вычисляются коэффициенты важности для элементов каждого уровня. При этом проверяется согласованность суждений ЛПР.
Подсчитывается количественный индикатор качества каждой из альтернатив и определяется наилучшая альтернатива.[42]