Методы оптимизации и исследование операций в области информационной безопасности

Московский государственный технический университет  
имени Н. Э. Баумана 
 
 
М. А. Басараб, С. В. Вельц  
 
 
 
Методы оптимизации и исследование операций 
в области информационной безопасности 
 
 
Методические указания к выполнению лабораторных работ  
по дисциплине «Методы оптимизации и исследование операций»  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Б27 
УДК 519.8(075.8) 
ББК 22.18 
Б27 
 
Издание доступно в электронном виде на портале ebooks.bmstu.ru  
по адресу: http://ebooks.bmstu.ru/catalog//117/book967.html 
 
Факультет «Информатика и системы управления» 
Кафедра «Информационная безопасность» 
 
Рекомендовано Редакционно-издательским советом  
МГТУ им. Н. Э. Баумана в качестве методических указаний 
 
Рецензент  
канд. техн. наук, доцент Ю. Т. Каганов 
 
 
Басараб, М. А. 
 
Методы оптимизации и исследование операций в области информационной безопасности : методические указания к выполнению лабораторных работ по дисциплине «Методы оптимизации и 
исследование операций» / М. А. Басараб, С. В. Вельц. — Москва : 
Издательство МГТУ им. Н. Э. Баумана, 2015. — 61, [3] с. : ил. 
ISBN 978-5-7038-4123-5  
Методические указания являются руководством к выполнению лабораторных работ по дисциплине «Методы оптимизации и исследование операций» и включают разделы «Линейное программирование», «Целочисленное 
программирование», «Булево программирование», «Элементы теории игр и 
теории принятия решений в условиях неопределенности». Для каждой работы предусмотрено 30 вариантов заданий.  
Для студентов МГТУ им. Н.Э. Баумана, обучающихся по направлению «Компьютерная безопасность». Могут быть также полезны студентам 
и аспирантам других специальностей, интересующимся современными 
методами решения задач теории оптимизации и исследования операций. 
 
 
УДК 519.8(075.8) 
ББК 22.18 
 
 
 
© МГТУ им. Н. Э. Баумана, 2015 
© Оформление. Издательство 
ISBN 978-5-7038-4123-5 
 
 
         МГТУ им. Н. Э. Баумана, 2015 
2 

 
Предисловие 
При решении производственных, управленческих, организационно-технических и других задач в области информационной безопасности часто приходится иметь дело с проблемой выбора одного варианта (оптимального или квазиоптимального) среди 
множества других решений.  
В зависимости от целевой функции и характера ограничений 
такого рода задачи можно условно разбить на два типа: 
1) задачи оптимизации. Предполагается, что ограничения известны, и необходимо найти экстремальное решение, доставляющее минимум либо максимум функционалу того или иного вида. 
Задачи конечномерной оптимизации с одной целевой функцией 
называют также задачами математического программирования; 
2) задачи теории игр (принятие решений в условиях неопределенности). Поиск оптимального решения (стратегии) осуществляется при априори неизвестных действиях другого игрока (игроков), имеющего собственные интересы, либо состояниях внешней 
среды («игра с природой»). 
Лабораторный практикум включает в себя работы по решению 
задач линейного программирования, принятия решений в условиях 
неопределенности, теории матричных игр. Значительный объем 
занимает изложение симплекс-метода решения задач линейного 
программирования, поскольку к этим задачам сводятся решения 
ряда других проблем (целочисленное программирование, матричные игры в смешанных стратегиях). 
Ряд работ имеет содержательную интерпретацию в области 
информационной безопасности, например: выбор оптимального 
набора средств безопасности (задача о покрытии), моделирование 
действии инсайдера (матричная игра).  
При выполнении лабораторных работ целесообразно воспользоваться либо готовыми программными пакетами математического моделирования (Matlab, MathCAD), электронными табли3 

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

Лабораторная работа № 1.  
Линейное программирование. Симплекс-метод 
Цель работы — изучить постановку задачи линейного программирования (ЛП); овладеть навыками решения задач ЛП с помощью симплекс-метода. 
Постановка задачи и методические указания 
Постановка задачи ЛП. Требуется найти решение следующей 
задачи: 
 
F = cx → min, 
 
Ax ≤ b, 
 (1.1) 
 
x ≥ 0. 
Здесь 
т
1
2
[
,
,...,
]
n
x x
x
=
x
 — искомый вектор решения; 
 
1
2
[
,
,...,
]
n
c c
c
=
c
 — вектор коэффициентов целевой функции (ЦФ) F; 
a
a
n
11
1
 
A
 — матрица системы ограничений; 
a
a
...
...
...
...
...
m
mn
⎡
⎤
⎢
⎥
= ⎢
⎥
⎢
⎥
⎣
⎦
1
 
т
1
2
[ ,
, ...,
]
m
b b
b
=
b
 — вектор правой части системы ограничений. 
В развернутой форме задача (1.1) имеет вид  
min;
n
 
=
=
→
∑
 
 (1.2)  
i i
i
F
c x
1
a x
a x
a x
b
...
;
n
n
11 1
12 2
1
1
a x
a
x
a
x
b
...
;
n
n
21 1
22 2
2
2
 
 
(1.3) 
...................................................
a
x
a
x
a
x
b
...
;
m
m
mn
n
m
+
+
+
≤
⎧
⎪
+
+
+
≤
⎪
⎨
⎪
⎪
+
+
+
≤
⎩
1 1
2 2
 
0,
i
x ≥
 
1,..., .
i
n
=
 
(1.4) 
Каноническая форма задачи ЛП. Систему неравенств (1.3) 
можно преобразовать в систему линейных алгебраических уравне5 

ний (СЛАУ) посредством прибавления к левой части каждого неравенства неотрицательных дополнительных переменных 
0,
n i
x + ≥
 
1, ...,
:
i
m
=
 
 
j
j
j
F
c x
+
1
min;
n m
=
=
→
∑
 
(1.5) 
 
ij
j
i
j
a x
b
+
1
,
n m
=
=
∑
    
1,2, ...,
;
i
m
=
 
(1.6) 
 
0,
j
x ≥
    
1, ...,
.
j
n
m
=
+
 
(1.7) 
При записи задачи ЛП в канонической форме (1.5)–(1.7) возможны следующие случаи: 
1) число линейно независимых уравнений больше числа переменных. Такая СЛАУ несовместна; 
2) число независимых уравнений равно числу переменных. 
СЛАУ имеет единственное решение (это решение будет либо недопустимым, если хотя бы одна из его компонент отрицательна, 
либо искомым оптимальным); 
3) число линейно независимых уравнений равно m, а число переменных равно 
.
n
m
+
 При совместности системы у нее существует бесконечное множество решений. В этих решениях n переменных могут принимать произвольные значения (свободные 
переменные), а остальные m переменных (базисные переменные) 
выражаются через свободные. 
Коэффициенты линейной ЦФ определяют семейство параллельных гиперплоскостей в гиперпространстве и направление, в 
котором уменьшается значение ЦФ. Для задачи минимизации гиперплоскость ЦФ следует перемещать параллельно самой себе в 
сторону уменьшения ее значений до тех пор, пока она еще будет 
содержать точки выпуклого многогранника ограничений. 
Симплекс-метод решения задачи ЛП. Решение — любой 
набор переменных 
1
2
,
, ...,
,
n m
x x
x +
 удовлетворяющий СЛАУ (1.6). 
Допустимое решение — решение с неотрицательными переменными (1.7). Базис — набор таких переменных, для которых матрица, составленная из коэффициентов этих переменных в уравнени6 

ях, будет невырожденной, т. е. ее определитель отличен от нуля. 
Базисное решение — решение, которое получится, если положить 
все небазисные (свободные) переменные равными нулю и решить 
уравнения относительно базисных переменных. 
Пусть ЦФ (1.5) и уравнения (1.6) разрешены относительно базисных переменных 
,
1, ...,
i
x i
m
=
 (выражены через свободные 
переменные 
,
1, ...,
j
y
j
n
=
): 
=
−
+
+
+
+
+
(
...
...
);
x
s
s y
s y
s y
s
y
k
k
n
n
1
10
11
1
12
2
1
1,
=
−
+
+
+
+
+
...............................................................................
(
...
...
);
x
s
s y
s y
s y
s
y
r
r
r
r
rk
k
r n
n
0
1
1
2
2
,
 
(1.8) 
.....................................
..........................................
(
...
...
);
x
s
s
y
s
y
s
y
s
y
m
m
m
m
mk
k
m n
n
0
1
1
2
2
,
(
...
...
).
m
m
m
m
k
k
m
n
n
1,0
1,1
1
1,2
2
1,
1,
⎧
⎪
⎪
⎪
⎪
⎨
⎪
⎪
=
−
+
+
+
+
+
⎪
=
−
+
+
+
+
+
⎪
⎩
F
s
s
y
s
y
s
y
s
y
+
+
+
+
+
Значения коэффициентов 
ij
s  можно записать в симплекстаблицу, содержащую 
1
m +  строку и 
1
n +  столбец: 
s
s
s
s
s
k
n
10
11
12
1
1,
...
...
...
...
...
...
...
...
...
s
s
s
s
s
r
r
r
rk
r n
0
1
2
,
 (1.9) 
...
...
.
...
...
...
...
...
...
...
s
s
s
s
s
...
...
m
m
m
mk
m n
0
1
2
,
...
...
m
m
m
m
k
m
n
1,0
1,1
1,2
1,
1,
s
s
s
s
s
+
+
+
+
+
−
−
−
−
⎡
⎤
⎢
⎥
⎢
⎥
⎢
⎥
−
−
−
−
⎢
⎥
⎢
⎥
⎢
⎥
−
−
−
−
⎢
⎥
−
−
−
−
⎢
⎥
⎣
⎦
Алгоритм преобразования симплекс-таблицы (жордановы 
исключения). Принцип нахождения оптимального решения в симплекс-методе состоит в следующем. Задачу линейного программирования записывают в канонической форме. Определяют допустимое базисное решение и проверяют его оптимальность. Если 
решение не оптимальное, то из базиса вычеркивают определенную 
7