Introducing new Paper mode
Если в транспортной задаче количество положительных поставок равно n+m-1, где где n – количество поставщиков, m – количество потребителей, то такая задача является:
вырожденной
невырожденной
выраженной
Multiple Choice
Please save your changes before editing any questions.
30 seconds
Примером градиентных методов, при котором исследуемые точки не выходят за границы области допустимых решений задачи является:
метод Франка-Вульфа
метод штрафных функций
метод Ерроу-Гурвица
правильного ответа нет
Multiple Choice
Please save your changes before editing any questions.
30 seconds
Моделирование – это процесс:
использования абстракций, аналогий, гипотез, других категорий
методов познания
познания интересующего исследователя объекта-оригинала с помощью модели
построения, изучения и применения моделей
Multiple Choice
Please save your changes before editing any questions.
30 seconds
Процесс моделирования включает следующие элементы:
субъект (исследователь), объект исследования, модель
познающий субъект и познаваемый объект
гипотеза, знания, модель
объект-оригинал, система знаний об объекте-оригинале, субъект
Multiple Choice
Please save your changes before editing any questions.
30 seconds
Если результат связан с признаками сходства оригинала и модели, то это дает основания при моделировании проводить этап
построения модели
изучения модели
переноса знаний с модели на объект-оригинал
проверки и применения знаний
Multiple Choice
Please save your changes before editing any questions.
30 seconds
Процесс моделирования является
двухэтапным циклом
трехэтапным циклом
четырехэтапным циклом
нецикличным процессом
Multiple Choice
Please save your changes before editing any questions.
30 seconds
Нормативные модели выделяют в отдельный класс по следующему признаку
по уровню моделируемого объекта в хозяйственной иерархии
по характеру
по предназначению (цели создания и применения) модели
по временному признаку;
Explore all questions with a free account
.png)
Continue with Google Continue with Microsoft Continue with Facebook Continue with email Continue with phone
Тест по предмету «Методы оптимальных решений» с ответами
Нет времени или сил пройти тест онлайн? Поможем сдать тест дистанционно для любого учебного заведения: подробности.
Тест по методам оптимальных решений онлайн
Вопрос 1. Каким образом вводятся переменные двойственной задачи, соответствующие ограничениям-уравнениям прямой задачи?
- как не ограниченные по своему знаку
- как неположительные
- как неотрицательные
Вопрос 2. Каким образом можно избавиться от уравнений в системе ограничений?
- ввести дополнительные переменные
- ограничение уравнение можно заменить на два неравенства
- в каждом из них заменить знак «=» на знак неравенства
Вопрос 3. При построении двойственной задачи к задаче линейного программирования в стандартной форме вводится столько основных переменных, сколько в прямой задаче.
- другое
- основных переменных
- ограничений
Вопрос 4. Какая переменная выходит из базиса при преобразовании симплексной таблицы?
- та базисная переменная, которая соответствовала разрешающему ограничению
- другое
- та базисная переменная, которая соответствовала разрешающему столбцу
Вопрос 5. Что такое критерий эффективности операции?
- показатель управляемости операции
- оценка прибыли, полученной в результате операции
- показатель того, насколько результат операции соответствует ее целям
Вопрос 6. Если в разрешающем столбце симплексной таблицы нет положительных коэффициентов, это означает, что .
- найден оптимальный план
- целевая функция задачи не ограничена
- область допустимых планов задачи пуста
Вопрос 7. В матричной форме можно записать.
- задачу линейного программирования, предварительно приведенную к стандартной или канонической форме
- только задачу линейного программирования, предварительно приведенную к канонической форме
- задачу линейного программирования в смешанной форме
Вопрос 8. Что показывают «теневые цены» (основные переменные двойственной задачи) в линейной задаче производственного планирования?
- цены, по которым можно продать произведенную продукцию
- изменение оптимальной выручки при изменении запаса соответствующего ресурса на единицу
- затраты на производство продукции
Вопрос 9. Если в линейной задаче производственного планирования в качестве продукции выступает, например, ткань (в метрах), то переменные .
- должны быть только дробными числами
- могут быть как целыми, так и дробными числами
- должны быть только целыми числами
Вопрос 10. Если в разрешающем столбце симплексной таблицы нет положительных коэффициентов, это означает, что .
- найден оптимальный план на максимум
- задача неразрешима
- найден оптимальный план на минимум
Вопрос 11. Если в критериальной строке симплексной таблицы нет отрицательный коэффициентов, это означает, что .
- задача неразрешима
- найден оптимальный план на максимум
- найден оптимальный план на минимум
Вопрос 12. В каком случае задача математического программирования является линейной?
- если ее целевая функция линейна
- если ее ограничения линейны
- если ее целевая функция и ограничения линейны
Вопрос 13. Чему равны не базисные переменные в опорном плане задачи линейного программирования?
- нулю
- любым числам
- положительным числам
Вопрос 14. Если оптимальное значение искусственной переменной при решении задачи методом искусственного базиса равно положительному числу, то.
- найден оптимальный план исходной задачи
- область допустимых планов пуста
- целевая функция неограничена
Вопрос 15. Если оптимальное значение основной переменной задачи линейного программирования равно нулю, то оптимальное значение дополнительной переменной в соответствующем ограничении двойственной задачи .
- больше нуля
- может быть любым
- равно нулю
Вопрос 16. Если крайнее положение линии уровня пересекает область допустимых планов более чем в одной точке, то оптимальный план .
- только одна из точек пере-сечения (единственный)
- не существует
- любая точка пересечения (бесконечное множество точек)
Вопрос 17. Что такое оптимум задачи линейного программирования?
- значение целевой функции на оптимальном плане
- оптимальный план
- любое значение целевой функции
Вопрос 18. В чем заключается критерий оптимальности симплексной таблицы?
- все коэффициенты в критериальном ограничении должны быть неотрицательными (или неположительными)
- все свободные члены должны быть неотрицательными (или неположительными)
- все свободные члены должны быть неотрицательными
Вопрос 19. Все точки, удовлетворяющие уравнению системы ограничений задачи линейного программирования с двумя переменными, образуют на плоскости.
- полуплоскость
- прямую
- отрезок
Вопрос 20. Каким образом строятся ограничения двойственной задачи, соответствующие переменным прямой задачи, не ограниченным по своему знаку?
- как уравнения
- как неравенства
- другое
Вопрос 21. Если в оптимальном решении линейной задачи производственного планирования некоторый ресурс израсходован не полностью, то его теневая цена (оптимальное значение соответствующей основной переменной двойственной задачи) .
- больше нуля
- меньше нуля
- равна нулю
Вопрос 22. Если при попытке решить задачу линейного программирования симплекс- методом не обнаружено необходимого числа базисных переменных, .
- задачу можно решить только графически
- задача неразрешима
- для решения задачи симплексметодом необходимо ввести искусственный базис
Вопрос 23. Если оптимальное значение искусственной переменной при решении задачи методом искусственного базиса равно отрицательному числу,
- найден оптимальный план исходной задачи
- другое
- область допустимых планов пуста
Вопрос 24. Что такое оптимальный план задачи линейного программирования?
- любая вершина области допустимых планов
- допустимый план, при подстановке которого в целевую функцию она принимает свое максимальное или минимальное значение
- план, с рассмотрения которого следует начать решение задачи
Вопрос 25. Если оптимальное значение основной переменной задачи линейного программирования больше нуля, то оптимальное значение дополнительной переменной в соответствующем ограничении двойственной задачи .
- равно нулю
- меньше нуля
- больше нуля
Вопрос 26. Если в столбце свободных членов симплексной таблицы нет отрицательных чисел, это означает, что .
- задача неразрешима
- другое
- найден оптимальный план
Вопрос 27. В каком случае точка на отрезке между оптимальными планами задачи линейного программирования тоже будет оптимальным планом (задача не целочисленная)?
- всегда
- никогда
- если задача на максимум
Вопрос 28. Сколько допустимых планов может иметь задача линейного программирования (не целочисленная)?
- 0 или 1
- всегда 1
- 0, 1 или бесконечное множество
Вопрос 29. Что такое неограниченная область допустимых планов задачи линейного программирования?
- в которой существуют планы со сколь угодно большими по модулю значениями всех переменных
- область, включающая бесконечное множество планов
- в которой существуют планы со сколь угодно большими по модулю значениями хотя бы одной из переменных
Вопрос 30. Что такое допустимый план задачи линейного программирования?
- план, при подстановке которого в систему ограничений все они выполняются
- план, при подстановке которого в систему ограничений выполняется хотя бы одно ограничение
- план, при подстановке которого в систему ограничений ни одно из них не выполняется
Вопрос 31. Если задача линейного программирования разрешима, в каком случае будет разрешима двойственная к ней задача?
Вопрос 32. В каком направлении сдвигают линию уровня целевой функции при решении задачи линейного программирования на максимум?
- вверх
- в направлении антиградиента
- в направлении градиента
Вопрос 33. Сколько оптимальных планов может иметь задача линейного программирования (не целочисленная)?
- 0 или 1
- всегда 1
- 0, 1 или бесконечное множество
Вопрос 34. Каким образом можно избавиться от не ограниченных по знаку переменных в системе ограничений?
- исключить эти переменные из рассмотрения
- заменить неограниченную по знаку переменную на разность двух неотрицательных
- наложить на них ограничения неотрицательности
Вопрос 35. Какое из приведенных ниже утверждений о разрешимости сопряженных задач является НЕ верным?
- оптимум одной из сопряженных задач больше, чем оптимум другой
- сопряженные задачи разрешимы или неразрешимы одновременно
- если целевая функция одной из сопряженных задач линейного программирования не ограничена, то область допустимых планов другой задачи пуста
Вопрос 36. На графике оптимальный план задачи линейного программирования с двумя переменными представляет собой.
- верхнюю точку области допустимых планов
- пересечение градиента и крайнего положения линии уровня
- пересечение области допустимых планов и крайнего положения линии уровня
Вопрос 37. В чем заключается критерий допустимости симплексной таблицы?
- все коэффициенты в критериальном ограничении должны быть неотрицательными (или неположительными)
- все свободные члены должны быть неотрицательными (или неположительными)
- все свободные члены должны быть неотрицательными
Вопрос 38. При построении двойственной задачи к задаче линейного программирования в стандартной форме строится столько ограничений, сколько в прямой задаче.
- основных переменных
- другое
- ограничений
Вопрос 39. Каким образом строится целевая функция расширенной задачи при использовании двухэтапного симплекс-метода?
- суммируются дополнительные переменные
- другое
- суммируются искусственные переменные
Вопрос 40. Какая переменная входит в базис при преобразовании симплексной таблицы?
- та, при которой стоял единичный столбец
- любая из небазисных переменных
- в столбце коэффициентов при которой нарушается критерий оптимальности
Тест по моделированию с ответами
1. Своеобразный инструмент познания, который исследователь ставит между собой и объектом и с
помощью которого изучает интересующий его объект – это:
1) аналог;
+2) модель;
3) объект-заместитель;
4) абстракция;
2. Наличие некоторых данных об объекте-оригинале необходимо на этапе:
+1) построения модели;
2) изучения модели;
3) переноса знаний с модели на объект-оригинал;
4) проверки и применения знаний;
3. При моделировании использование знаний для построения обобщающей теории объекта, его преобразования или управления им происходит на этапе:
1) построения модели;
2) изучения модели;
3) переноса знаний с модели на объект-оригинал;
+4) проверки и применения знаний;
4. При моделировании знания об исследуемом объекте расширяются и уточняются, ошибки в построении модели исправляются, а построенная исходная модель постепенно совершенствуется засчет:
+1) повторения цикла моделирования;
2) построения новой теории объекта;
3) использования специфических форм абстракций, аналогий, гипотез;
4) переноса знаний с модели на объект-оригинал;
5. Динамические модели выделяют в отдельный класс по следующему признаку:
1) по уровню моделируемого объекта в хозяйственной иерархии
2) по характеру
3) по предназначению (цели создания и применения) модели
+4) по временному признаку
5) по форме отображения причинно-следственных связей
6) по способу отражения действительности
6. При решении задачи целочисленного программирования по приведенному фрагменту симплекс-таблицы определите, для какой переменной необходимо составить дополнительное ограничение
1) Х1 +2) Х2 3) Х5 4) Х3
7. Какой из перечисленных методов применяется при решении задачи целочисленного
программирования:
1) метод Эрроу-Гурвица
2) метод искусственного базиса
+3) метод Гомори
4) метод минимальной стоимости
8. В методе Гомори дополнительное ограничение имеет вид:
1) Σ f(aij*)xj = f(bi*);
+2) Σ f(aij*)xj ≥ f(bi*);
3) Σ f(aij*)xj ≤ f(bi*);
9. Если в транспортной задаче количество положительных поставок равно n+m-1, где где n – количество поставщиков, m – количество потребителей, то такая задача является:
1)вырожденной
+2)невырожденной
3)выраженной
10. Примером градиентных методов, при котором исследуемые точки не выходят за границы области допустимых решений задачи является:
+1) метод Франка-Вульфа;
2) метод штрафных функций;
3) метод Ерроу-Гурвица;
4) правильного ответа нет;
11. Моделирование – это процесс:
1) использования абстракций, аналогий, гипотез, других категорий;
2) методов познания;
3) познания интересующего исследователя объекта-оригинала с помощью модели;
+4) построения, изучения и применения моделей;
5) опосредованного познания с помощью объектов-заместителей;
12. Процесс моделирования включает следующие элементы:
+1) субъект (исследователь), объект исследования, модель;
2) познающий субъект и познаваемый объект;
3) гипотеза, знания, модель;
4) объект-оригинал, система знаний об объекте-оригинале, субъект;
13. Если результат связан с признаками сходства оригинала и модели, то это дает основания при моделировании проводить этап:
1) построения модели;
2) изучения модели;
+3) переноса знаний с модели на объект-оригинал;
4) проверки и применения знаний;
14. Процесс моделирования является:
1) двухэтапным циклом;
2) трехэтапным циклом;__
+3) четырехэтапным циклом;
4) нецикличным процессом;
15. Нормативные модели выделяют в отдельный класс по следующему признаку:
1) по уровню моделируемого объекта в хозяйственной иерархии;
2) по характеру;
+3) по предназначению (цели создания и применения) модели;
4) по временному признаку;
5) по форме отображения причинно-следственных связей;
6) по способу отражения действительности;
16. Задачи многомерной оптимизации выделяют в отдельный класс по следующему признаку классификации:
+1) количество переменных
2) отражение влияния случайных факторов
3) отображение влияния времен
4) структура функций, которые входят в состав задачи
17. Какой вид оптимизационной задачи определяет приведенная математическая модель?
1) задача определения оптимального плана производства
2) задача составления смеси
3) транспортная задача
+4) задача о назначениях
18. При решении задачи целочисленного программирования по приведенному фрагменту симплекс-таблицы определите, для какой переменной необходимо составить дополнительное ограничение
1) Х2 +2) Х1 3) Х5 4) Х3
19. В математической модели задачи целочисленного программирования целевая функция и функции в системе ограничений могут быть
1) только линейными
2) только нелинейными
+3) как линейными, так и нелинейными
20. Дробная часть числа:
1) величина положительная;
2) величина отрицательная;
+3) зависит от знака числа;
21. Может ли транспортная задача иметь несколько оптимальных решений, обеспечивающих одинаковую суммарную стоимость перевозок:
1) да
2) нет
+3) при определенных условиях
22. Если в транспортной задаче (ТЗ) суммарная мощность поставщиков превосходит суммарную потребность потребителей, то такая ТЗ называется:
+1) открытой;
2) закрытой;
3) смешанной.
23. Сколько положительных перевозок должен содержать невырожденный опорный план
транспортной задачи (n – количество поставщиков, m – количество потребителей)):
1) m+n+1;
2) m – n;
+3) m+n–1.
24. В задачах линейного программирования линейными должны быть:
1) целевая функция
2) ограничения задачи;
+3) целевая функция и ограничения задачи.
25. Целевая функция ЗЛП вида (1) графически может быть представлена
(1) F=C1X1+C2X2+C3X3
+1) прямой в трёхмерном пространстве
2) прямой в двумерном пространстве
3) плоскостью в трёхмерном пространстве
4) плоскостью в четырехмерном пространстве
26. По приведенному фрагменту симплекс-таблицы можно утверждать, что:
ЗЛП не имеет решения;
+2) направляющей будет первая строка таблицы;
3) направляющей будет вторая строка таблицы;
4) направляющей будет третья строка таблицы;
27. Градиентом называется:
1) вектор с координатами C = (c1,c2), указывающий направление убывания
целевой функции
2) прямая вида c1x1+c2x2 = h, (h – константа), отражающая частный случай
целевой функции
+3) вектор с координатами C = (c1,c2), указывающий направление возрастания
целевой функции
4)выпуклое множество, образованное пересечением полуплоскостей, графически отражающих ограничения задачи
28. Целевая функция в ЗЛП достигает своего максимума не в одной точке многоугольника
допустимых решений, но на одной из его границ, если:
+1) линия уровня (целевая функция) параллельна одному из ограничений
2) линия уровня (целевая функция) перпендикулярна одному из ограничений
3) два или более ограничения перпендикулярны друг другу
4) линия уровня (целевая функция) пересекает ось абсцисс
29. В случае, если X*- оптимальный план ЗЛП на минимум, то для любого Х справедливо
неравенство (где F(X*) — значение целевой функции при плане X*; F(X) – значение целевой функции при плане X):
1) F(X)≤F(X*) +2) F(X)≥F(X*) 3) F(X)=F(X*) 4) F(X)
30. Если у предпринимателя появились лишние средства, и он может докупить большее количество сырья, то в первую очередь следует докупать те виды сырья, двойственные оценки которых
1)положительны +2) минимальны 3) максимальны 4) равны 0
31. Коэффициентами целевой функции двойственной задачи являются:
1) коэффициенты при переменных прямой задачи
+2) свободные члены системы ограничений прямой задачи
3) коэффициентыцелевой функции прямой задачи
4) правильного ответа нет
32. После получения псевдоплана ЗЛП в рамках двойственного симплекс-метода сначала
выбирают:
1) направляющую строку
+2) направляющий столбец
3) можно начинать с любого отрицательного элемента в столбце Р0
4) правильного ответа нет
33. Для преобразования ограничения-неравенства вида «≤» исходной ЗЛП в ограничение-равенство
необходимо:
1) левую часть неравенства умножить на дополнительную неотрицательную переменную
2) левую часть неравенства разделить на дополнительную неотрицательную переменную
3) к левой части неравенства добавить дополнительную неотрицательную переменную
+4) от левой части неравенства отнять дополнительную неотрицательную переменную
34. Сколько искусственных переменных следует ввести для решения ЗЛП при следующих
ограничениях:
Об использовании методов многокритериального поиска в сфере информационной безопасности Текст научной статьи по специальности «Математика»
Аннотация научной статьи по математике, автор научной работы — Попова Екатерина Александровна
Анализируются возможности и особенности использования методов многокритериального поиска применительно к задачам обеспечения информационной безопасности . Проведена классификация задач поиска, типов используемых функций и функционалов, которые могут входить в постановку этих задач. Библиогр. 5.
i Надоели баннеры? Вы всегда можете отключить рекламу.
Похожие темы научных работ по математике , автор научной работы — Попова Екатерина Александровна
Принятие решений при многих критериях в условиях неполноты данных
Принятие управленческих решений в условиях неопределенности и нечеткости исходной информации
Об одном подходе к двухуровневой задаче формирования грузовых железнодорожных составов
Анализ современных методов построения систем поддержки принятия решений для многоуровневых предприятий
Гибридные алгоритмы векторной оптимизации в системах вычислительной диагностики
i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
i Надоели баннеры? Вы всегда можете отключить рекламу.
Possibilities and peculiarities of the application of multicriterion search methods with reference to problems in information security are analyzed in the paper. The classification of search problems, types of used functions and functionals, which can be involved in the statement of these problems, is carried out.
Текст научной работы на тему «Об использовании методов многокритериального поиска в сфере информационной безопасности»
ОБ ИСПОЛЬЗОВАНИИ МЕТОДОВ МНОГОКРИТЕРИАЛЬНОГО ПОИСКА В СФЕРЕ ИНФОРМАЦИОННОЙ БЕЗОПАСНОСТИ
При решении многих проблем обеспечения информационной безопасности возникают вопросы, связанные с многоцелевым характером процесса обеспечения безопасности. Одной из основных причин, порождающих необходимость рассмотрения многоцелевых задач в сфере информационной безопасности, является неопределенность многих характеристик систем. Один из возможных подходов к решению подобных проблем — рассмотрение этих задач как многокритериальных, в которых каждый из критериев соответствует одному объекту, одному направлению деятельности и т. д.
В большинстве случаев в задачах безопасности неопределенность связана со сложностью объекта и отсутствием информации о возможных угрозах. Для того чтобы снять эту неопределенность, необходима дополнительная информация, источником которой часто является лицо, принимающее решение (ЛПР). Участие ЛПР является принципиальным для решения и практического приложения многих задач многокритериального поиска в системах безопасности ввиду малого объема имеющейся информации. Кроме того, важным элементом процесса обеспечения безопасности является злоумышленник, поведение которого практически невозможно формализовать. Проблеме использования методов многокритериального поиска в сфере информационной безопасности и посвящена данная работа. Отметим, что близкие по содержанию проблемы рассматриваются в [1, 2].
Опишем основные критерии (характеристики) классификации многокритериальных задач в сфере безопасности. Первой характеристикой является степень формализованности рассматриваемой многокритериальной задачи. Выделим следующие три известных класса задач в зависимости от степени их формализованности [1]: формализованные, слабоструктурированные и неструктурированные задачи. Второй характеристикой многокритериальных задач безопасности являются требования, предъявляемые к виду окончательного решения. В подавляющем большинстве случаев ставится одно из следующих требований: 1) выделить один вариант;
2) разделить рассматриваемые варианты на несколько классов; 3) упорядочить варианты по заданному критерию; 4) отбросить плохие варианты. Третья характеристика связана с тем, насколько нова рассматриваемая проблема для ЛПР, поскольку при повторяющихся проблемах ЛПР может выработать типовые правила принятия решения.
Характер постановки задачи в значительной степени определяет и метод ее решения. Рассмотрим отдельные классы методов многокритериальной оптимизации. Все методы в первом приближении можно разделить на формализованные и неформализованные. Под формализованными методами решения задач многокритериальной оптимизации понимаются такие методы, которые в процессе принятия решения (или группы решений) на их основе не предполагают непосредственного участия субъекта. Выделим основные классы методов формализации:
1) методы, основанные на свертывании критериев;
2) методы, построенные на основе наложения ограничений на отдельные критерии;
3) методы целевого программирования;
4) методы, основанные на отыскании компромиссного решения;
5) методы, предполагающие построение функции полезности ЛПР без участия объективной модели;
6) методы построения множества Парето для последующего предъявления его ЛПР.
Большинство из перечисленных методов сводят многокритериальную задачу к одной
или нескольким однокритериальным задачам.
Наиболее распространенными формализованными методами решения оптимизационных задач являются методы математического программирования. Для решения многокритериальных
задач математического программирования наряду с формализованными методами применяется подход, основанный на интерактивном выявлении предпочтений ЛПР с одновременным исследованием допустимого множества действий для отыскания эффективных решений [3, 4]. Средством реализации такого подхода являются человеко-машинные процедуры, которые представляют собой циклический процесс взаимоотношения человека (ЛПР) и ЭВМ в процессе поиска. В процессе взаимодействия ЛПР проясняет характерные черты задачи, выясняет и уточняет свои предпочтения и в результате сообщает дополнительную информацию, благодаря которой ЭВМ вырабатывает все более совершенные результаты. Ответ на вопрос о том, какими методами указанного типа следует решать ту или иную задачу, зависит, прежде всего, от способности ЛПР компетентно оценивать возможные варианты решений в рассматриваемой задаче, и от того, насколько полезна информация, выдаваемая ЛПР, для нахождения решения. При значительной разнице между уровнями компетентности, имеющимися у ЛПР и требуемыми для решения задачи с помощью человеко-машинной процедуры, существенно может снизиться эффективность поиска и качество получающегося в результате поиска решения. Очень многие методы нацелены на решение различных задач критериально-экспертного выбора, поскольку именно в этих задачах ЛПР чаще всего нуждается в аналитической поддержке. С другой стороны, в связи с новизной проблемы требования к методам поиска оптимальных решений (ПОР) резко возрастают. В то же время в современном мире становится все больше проблем критериальноэкспертного выбора. Класс методов критериально-экспертного выбора включает в себя подклассы методов, основанных на построении и получении функции полезности от ЛПР, методы компенсации, методы принятия повторяющихся решений и некоторые другие подклассы [5].
Классификация методов многокритериального поиска
Выше было кратко описано содержание основных классов методов многокритериального поиска оптимального решения. При этом неоднократно отмечалось, что сфера применения различных методов ограничена. В этой связи становится актуальной задача характеризации сферы применения методов различных классов, т. е. задача исследования их полноты. Понятие полноты некоторой совокупности методов ПОР подразумевает следующее: любая ли оптимизационная задача из заданного их множества может быть достаточно удовлетворительно решена хотя бы одним методом из рассматриваемой совокупности методов? Ниже используется полнота строго формализованных методов ПОР. Для этого необходимо в начале охарактеризовать то множество оптимизационных задач, для решения которых и предназначены конечные и условно конечные методы, а затем на этой основе исследовать возможности строго формализованных методов для решения оптимизационных задач из заданной их совокупности.
Необходимым условием решения конкретной основной задачи с помощью хотя бы одного строго формализованного метода является наличие формализованной модели задачи. Анализ моделей ПОР с точки зрения возможностей использования в них строго формализованных методов проведен на основе характеризации компонентов модели. Любая модель ПОР включает в себя часть или все из следующих реквизитов:
1) функции действительного аргумента (детерминированные и стохастические);
2) функционалы над множеством действительных функций;
3) отношения, связывающие между собой функции и (или) функционалы;
4) переменные с их областями изменения.
В связи с этим для классификации моделей необходимо охарактеризовать каждый из перечисленных реквизитов. Практически во всех реальных задачах функционалы, входящие в описание задач, являются линейными одного из следующих видов:
4) экстремальный (сочетание максимума и минимума);
Отношения могут быть следующих видов:
1) равенства и неравенства;
2) включения (в том числе условия, сводящиеся к включению);
3) соотношения предпочтения (в том числе соотношения частичной упорядоченности).
Перейдем к классификации функций. Чем подробнее заданы и описаны свойства функций, тем, вообще говоря, более эффективно может быть решена основная задача, однако с тем более длинным списком классов функций (для каждого из которых необходимо иметь именно для него приспособленный набор методов ПОР) придется иметь дело. Как показывает опыт, с определенного момента приращение эффективности от использования специфических методов ПОР становится в целом малосущественным при дальнейшем уточнении свойств функций. Именно поэтому с практических позиций детализация классов функций разумна лишь до определенной степени. Заметим также, что, если область изменений значений аргументов состоит из изолированных точек, ограничения на функции вообще могут отсутствовать (например, во многих задачах целочисленного программирования).
Рассмотрим вначале детерминированные функции. Основными свойствами функций, которые могут влиять на качество конечного результата, являются «степень изменчивости» функции (свойство, определяющее возможность предсказывать особенности поведения функции исходя из ограниченной информации о ней) и ее гладкость. Первое свойство позволяет из всего множества экстремумов локализовать тот, который нас интересует, а второе свойство позволяет эффективно находить его.
Степень изменчивости функций можно измерять следующим образом:
А) относительной величиной ее отличия от фиксированного класса «неизменяющихся» или «малоизменяющихся» функций;
Б) абсолютной величиной, учитывающей все колебания значений и изменений функций. Рассмотрим каждый из этих случаев отдельно.
А. В качестве меры относительного отличия функции f (x) от произвольной функции
h(x) (x е Rn; n > 1) из фиксированного класса 3 «малоизменяющихся» функций можно
выбрать одну из следующих величин:
1) максимальное отклонение f (x) от h(x), т. е. р1(f,h) = supf (x) — h(x)|;
2) интегральное («объемное») отклонение f (x) от h(x), т. е.
P2 (f, h) = J j(| f (x) — h( x)|)dx, где ф( ■) — неотрицательно монотонно неубывающая функция (например, можно положить ф(0 = t1, l > 0). Меру отклонения f (x) от класса 3 в целом можно измерять одной из величин — pi(f, h) и р2 (f, h) для случая «удачно» выбранной функции
h(x) е 3 , т. е. одной из величин — р1(f) = inf р1( f, h) или р2( f) = inf р2( f, h).
В частности, если 3 есть множество постоянных функций, то р1( f) = inf sup f (x) — c| ,
р2 (f) = inf J j(| f (x) — c\)dx .
Характеризация изменчивости относительными величинами в процессе ПОР, по-видимому, приемлема при использовании аппроксимации методов ПОР.
Б. В качестве меры абсолютной оценки изменчивости f(x) можно выбрать одну из следующих величин:
1) число экстремумов на множестве поиска (в частности, если эта величина равна единице, то рассматриваемая функция унимодальна);
2) для функции одной переменной — число отрезков возрастания либо убывания (отметим, что величины, описанные в Б1 и Б2, в случае функции одной переменной выражаются одна через другую);
3) площадь поверхности функции f (x) на множестве Т, разделенная на площадь множества Т (обозначим ее т(Т)), если последняя величина ограничена. В случае функции
одной переменной эта величина равна Var!bf (x))/(b — a) (T = [a,b]). В многомерном случае
указанная величина равна J\df (x)| ■ (m(T))—1. В случае m(T) =+¥ в качестве абсолютной меры
«изменчивости» f (x) можно взять площадь поверхности функции у = f (x), т. е. J\df (x)|.
Степень изменчивости функции зависит также от области ее занятия. Наконец, изменчивость функции может ограничиваться путем наложения определенных ограничений на локальные изменения функции, например наложением условий непрерывности, полунепрерывности, условия Липшица и др.
Исходя из вышесказанного и содержательного анализа специальной литературы, можно выделить следующие классы функций с ограниченной изменчивостью:
1. Финитные функции (имеющие ограниченную область изменения).
2. Функции, имеющие конечное число экстремумов (в частности, унимодальные функции).
3. Функции с ограниченной вариацией
4. Пространство Ьр (р > 0) измеримых по Лебегу функций /(х) таких,
5. Функции, удовлетворяющие условию Липшица.
6. Полунепрерывные (снизу и сверху) и непрерывные функции.
Если изменчивость функции / (х) обычно позволяет разбивать множество поиска экстремума на отдельные подмножества, на каждом из которых / (х) уникальна, то для эффективности самой процедуры поиска величины экстремума и точки ее достижения на отдельном подмножестве весьма большое значение имеет степень гладкости на этом подмножестве. Степень гладкости / (х) можно измерять степенью (кратностью) ее дифференцируемости и качественными свойствами на производных (например, мерой изменчивости ее производных). Поэтому меру гладкости функции мы будем характеризовать следующими величинами:
1) кратностью дифференцируемости;
2) степенью изменчивости производной наиболее высокого порядка.
Принимая во внимание перечисленные выше характеристики изменчивости, выделим следующие классы функции с заданной степенью гладкости.
1. Бесконечно дифференцируемые функции.
2. Пространство функций Жр, т (т > 0, р> 0) таких, что для любой /(х) е Жр, т имеем
3. Множество функций, п-я производная которых удовлетворяет условию Липшица (п > 1).
4. Пространство Ст т раз непрерывно дифференцируемых функций (т > 1) (отметим, что С0 пространство непрерывных функций).
При достаточно сильных ограничениях на функцию свойства ее изменчивости или гладкости могут оказаться сильно взаимосвязанными; в частности при рассмотрении функции специального вида. Поскольку функции с подобными ограничениями довольно часто встречаются на практике, перечислим основные классы таких функций.
1. Линейные функции.
2. Квадратичные функции.
3. Полиномиальные функции.
4. Экспоненциальные функции.
5. Экспоненциально-полиномиальные функции.
6. Кусочно-элементарные функции.
7. Сильновыпуклые функции.
8. Выпуклые функции.
Теперь классифицируем стохастические функции. Степень изменчивости стохастических величин (СВ) может характеризоваться:
1) их моментными характеристиками (в частности, наибольшим порядком конечного момента);
2) свойствами функций распределения и плотности СВ (старение, симметричность, одновершинность и др.).
Степень гладкости СВ характеризуется наличием и степенью гладкости (как детерминированной функции) плотности распределения.
Исходя из сказанного, выделим следующие классы СВ.
1. Стохастические величины с конечными порядками а > 0 (прежде всего нас будут интересовать случаи а = 1 и а = 2).
2. Абсолютно непрерывные функции распределения (и СВ).
3. Стохастические величины, принимающие целочисленные значения.
4. Нормально распределенные СВ.
Как отмечалось выше, детализация свойств функций разумна только до определенного предела. Далее, поскольку поиск экстремумов обычно ограничен конечной областью и значения функций, входящих в описание задачи ПОР, на практике имеют ограниченные пределы изменения, абсолютные оценки меры изменчивости функций всегда существуют и определены.
Рассмотрим, насколько каждый из перечисленных классов функций представляет интерес при решении многокритериальных задач в сфере информационной безопасности. Для обеспечения гарантированных возможностей решения задач многокритериального поиска для каждого из перечисленных выше класса функций необходимо проведение экспертной процедуры. В качестве экспертов были выбраны 4 специалиста в сфере информационной безопасности, имеющие одновременно уровень математической подготовки, достаточный для понимания особенностей перечисленных выше классов функций. Предварительно эксперты провели совместное обсуждение по содержанию проводимой экспертной процедуры. Эксперты оценивали важность каждого класса по 100-бальной шкале на основе метода непосредственной численной оценки. По результатам экспертной процедуры в качестве основных классов функций, представляющих наибольший интерес применительно к сфере информационной безопасности, были выбраны следующие (в скобках приведены соответствующие результирующие экспертных оценок):
i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
К.3. Функции, удовлетворяющие условиям Липшица (38).
К.4. Непрерывные функции (87).
К.6. Дважды непрерывно-дифференциальные функции (44).
К.8. Квадратичные функции (73).
К.10. Выпуклые функции (63).
К.13. Абсолютно непрерывные функции (87).
К.14. Целочисленные случайные функции (48).
К.15. Нормально распределенные случайные функции (68).
Ввиду малого объема выборки для оценки степени согласованности экспертов для каждого класса функций был использован коэффициент вариации отношения среднеквадратичного отклонения, усредненного по всем экспертам, к усредненному по всем экспертам среднему значению. Затем полученные значения коэффициентов вариации были усреднены по всем классам функций. Результирующие значения оказались равными 0,28, что позволяет говорить о приемлемом уровне согласованности мнений экспертов.
На основе вышесказанного заключаем, что (относительно) полное множество конечных методов ПОР и условно конечных методов должно обеспечивать решение оптимизационных задач в произвольных детерминированных и стохастических моделях, в которых функционалы, если такие есть, функции и отношения, их связывающие, принадлежат перечисленным выше классам.
В работе проведена общая классификация методов поиска оптимальных решений. Приведенная классификация является необходимым этапом в реализации систем искусственного интеллекта, использующих технологии автоматизированного выбора наиболее приемлемых методов поиска оптимальных решений (без участия человека). Исходя из указанной цели, следует провести подобную классификацию для других классов методов описка оптимальных решений. Следующий этап реализации технологии автоматизированного поиска оптимальных решений — разработка процедуры выбора методов ПОР для решения конкретной оптимизационной задачи с учетом особенностей этой задачи. Необходимым этапом в решении этой проблемы является разработка принципов и способов оценки возможностей отдельных методов поиска оптимальных решений.
1. Герасименко В. А. Основы защиты информации автоматизированных систем защиты данных. -М.: Наука, 1996. — 328 с.
2. Герасименко В. А., Попов Г. А., Таирян В. И. Основы оптимизации в системах управления. — Деп. в ВИНИТИ, № 213-В89, 1989. — 497 с.
3. Ларичев О. И., Поляков О. А. Человеко-машинные процедуры решения многокритериальных задач математического программирования // Экономические и математические методы. — 1980. — Т. XVI, вып. 1. — С. 129-145.
4. Ларичев О. И., Никифоров А. Д. Аналитический обзор процедур решения многокритериальных задач математического программирования // Экономические и математические методы. — 1986. — Т. ХХШ, вып. 3. — С. 508-523.
5. Емельянов С. В., Ларичев О. И. Многокритериальные задачи принятия решений. — М.: Знание, 1985. — 32 с.
Статья поступила в редакцию 3.11.2009
ABOUT THE APPLICATION OF MULTICRITERION SEARCH METHODS IN THE SPHERE OF INFORMATION SECURITY
Possibilities and peculiarities of the application of multicriterion search methods with reference to problems in information security are analyzed in the paper. The classification of search problems, types of used functions and functionals, which can be involved in the statement of these problems, is carried out.
Key words: multicriterion search, information security, functions classes in search problems.