Векторные задачи на графах с недетерминированными входными параметрами

ВЕКТОРНЫЕ ЗАДАЧИ 

НА ГРАФАХ

С НЕДЕТЕРМИНИРОВАННЫМИ 

ВХОДНЫМИ ПАРАМЕТРАМИ

Москва 
РИОР

ИНФРА-М

МОНОГРАФИЯ

В.И. Петренко, Ф.Б. Тебуева

УДК 519.17:518.2
ББК 22.18
          П30

А в т о р ы :
Петренко В.И. — канд. техн. наук, доцент, заведующий кафедрой организации и технологии 
защиты информации, Северо-Кавказский федеральный университет (Ставрополь). 
Автор более 200 печатных работ, в том числе 22 учебных  пособий, 7 из которых имеют гриф 
УМО, 85 изобретений по проблемам защиты информации, защиты персональных данных, 
арифметических операций в конечных полях, синтеза дискретных последовательностей, 
систем связи;
Тебуева Ф.Б. — д-р физ.-мат. наук, доцент, заведующий кафедрой прикладной математики 
и компьютерной безопасности, Северо-Кавказский федеральный университет 
(Ставрополь). Автор более 200 печатных трудов, в том числе 5 монографий, 5 изобретений 
по проблемам математического моделирования процессов в информационно-телекоммуникационных 
системах.
Р е ц е н з е н т ы :
Макаров А.М. — д-р техн. наук, профессор, профессор кафедры информационно-коммуникационных 
технологий, математики и информационной безопасности Пятигор-
ского государственного университета (Пятигорск);
Осипян В.О. — д-р техн. наук, доцент, профессор кафедры информационных технологий 
Федерального государственного бюджетного образовательного учреждения высшего 
образования «Кубанский государственный университет» (Краснодар);
Никитина А.В. — д-р техн. наук, доцент, доцент кафедры интеллектуальных и многопро-
цессорных систем Южного федерального университета (Таганрог).

ФЗ 
№ 436-ФЗ
Издание не подлежит маркировке 
в соответствии с п. 1 ч. 2 ст. 1

Петренко В.И., Тебуева Ф.Б.

П30 
 
Векторные задачи на графах с недетерминированными входными 

параметрами : монография / В.И. Петренко, Ф.Б. Тебуева. — Москва : 
РИОР, ИНФРА-М, 2020. — 234 с. — (Научная мысль). — DOI: https://doi.
org/10.29039/1809-5

ISBN 978-5-369-01809-5 (РИОР)
ISBN 978-5-16-014436-8 (ИНФРА-М)

В монографии исследуются вопросы моделирования сложных систем, кото-

рые математически формализуются как векторные задачи на графах с недетер-
минированными входными параметрами. Недетерминированность параметров 
возникает в ситуациях, когда не представляется возможным проведение вычис-
лительного эксперимента и получения точных значений характеристик функци-
онирования системы. Рассматриваются задачи, имеющие входные параметры в 
виде нечетких множеств, интервалов значений и временных рядов.

Для преподавателей, студентов, аспирантов физико-математических и тех-

нических специальностей, интересующихся вопросами моделирования слабо-
формализуемых процессов.

УДК 519.17:518.2 
ББК 22.18

©  В.И. Петренко,  

Ф.Б. Тебуева

ISBN 978-5-369-01809-5 (РИОР)
ISBN 978-5-16-014436-8 (ИНФРА-М)

ВВЕДЕНИЕ 

В практике жизнедеятельности человека почти всегда возникают зада-
чи выбора оптимальной альтернативы и последующее принятие решений. 
В самых простых случаях, когда рассматриваемые альтернативы оценива-
ются одним показателем, осуществить выбор возможно интуитивно, без 
использования математического аппарата. Если же рассматриваемые аль-
тернативы оцениваются несколькими показателями качества, то задача 
значительно усложняется – возникает ситуация многокритериальности. 
Для нахождения многокритериального оптимума можно воспользоваться 
математическим арсеналом теории многокритериальной оптимизации. Бо-
лее сложные задачи многокритериального выбора возникают в условиях 
недетерминированности исходных данных. Под недетерминированностью 
исходных данных в контексте настоящей работы следует понимать описа-
ние весов ребер графа тремя видами неопределенности: интервал значе-
ний, нечеткое множество, временной ряд. При осуществлении выбора и 
принятии решения в таких многокритериальных задачах возникает ряд 
сложностей: сравнение величин с неточными и размытыми границами 
числовых значений параметров, обобщение понятия оптимальной альтер-
нативы, разработка методов отыскания оптимальной альтернативы. 
В первой главе монографии проведен анализ возможных неопределен-
ностей исходных данных в задачах многокритериального выбора на графах 
и исследована проблема отыскания предпочтительной альтернативы. От-
мечено, что в процессе решения задач многокритериального выбора на 
графах в условиях недетерминированности исходных данных возникает 
ряд методологических и практических трудностей и неразрешимостей:  
1) при суммировании весов в виде нечетких множеств, с одной стороны, 
при совпадающих носителях оперирование происходит только функцией 
принадлежности, с другой стороны, при несовпадающих носителях резко 
возрастает количество компонентов, что приводит в случае многоразового 
их использования к быстрому переполнению оперативной памяти и потере 
информативности результата; 2) при сравнении весов в виде нечетких 
множеств в случае с несовпадающими носителями необходимо вначале 
представить нечеткие множества в α -уровневом виде, что для дискретных 
нечетких множеств представляет собой неразрешимую задачу; 3) при использовании 
минимаксного MinMax или максиминного MaxMin показателя 
предпочтительности для исходных данных в виде интервалов с вложенными 
границами возникает случай несравнимости; 4) невозможность суммирования 
или сравнения весов в виде динамических временных рядов.  
Во второй главе разработаны методы структурирования исходных данных 
в виде нечетких множеств и интервалов. Отмечено, что для обработки 
исходных данных в виде нечетких множеств существует ряд методов, каждый 
из которых имеет свои характерные ограничения относительно применимости 
для различных классов нечетких множеств. Рассматриваются 

дискретные нечеткие числа с признаком для классификации «Близость к 
наиболее вероятной величине».  
В третьей главе проводится анализ и прогнозирование исходных данных 
в виде временных рядов. Отмечено, что при прогнозировании временных 
рядов корреляционно-регрессионными методами возникают две трудности: 
1) получение усредненных прогнозных значений временных рядов 
при использовании регрессионных моделей в то время, как имеется необходимость 
в получении мгновенных прогнозных значений; 2) не приемлемая 
ошибка прогнозирования временных рядов, обладающих свойствами 
зависимости значений, часто меняющимся трендом, являющихся нестационарными, 
закон распределения которых не является нормальным.  
В главе обоснован выбор классификации временных рядов по признаку 
«Персистентность». Согласно этой классификации все временные ряды 
делятся на персистентные, хаотические и антиперсистентные. Для вычисления 
глубины долговременных корреляций предложен метод последовательного 

S
R / -анализа на базе метода нормированного размаха Херста. 
Глубина памяти временного ряда представляет собой нечеткую величину. 
Для персистентных временных рядов разработана прогнозная модель, ба-
зирующаяся на математическом аппарате линейных клеточных автоматов 
и реализующая вероятностно-статистический подход.  
В четвертой главе описана разработанная методика решения дискрет-
ных многокритериальных задач на графах в условиях недетерминирован-
ности исходных данных. Вычислительная схема предлагаемой методики 
состоит из пяти этапов: ввод исходных данных, формирование множества 
допустимых решений и постановка цели, структурирование неопределен-
ностей исходных данных, вычисление количественных оценок допустимых 
решений, нахождение предпочтительной альтернативы. 

В пятой главе разработаны численные методы предложенных матема-
тических моделей и методов для задач многокритериального выбора на 
графах в условиях недетерминированности исходных данных. Кроме того, 
оценена эффективность решения этого класса задач. Отмечено, что эффек-
тивность моделирования и алгоритма, обеспечивающего получение ре-
зультатов, можно оценить по следующим трем показателям качества: диа-
пазон исходных данных, точность, вычислительная сложность. Показатель 
качества «диапазон исходных данных» определяет объем памяти ЭВМ, не-
обходимой для ввода исходной информации. Исходной информацией в 
рассматриваемом классе задач являются: количество вершин графа, список 
ребер графа, веса ребер графа, структура допустимого решения, векторная 
целевая функция с критериями предпочтительности альтернатив.  
В шестой главе описан разработанный комплекс проблемно-
ориентированных программ – приводятся алгоритмы в виде блок-схемы и 
описываются характеристики программного обеспечения.  
 
 

Глава 1. АНАЛИЗ ВОЗМОЖНЫХ НЕОПРЕДЕЛЕННОСТЕЙ 
ИСХОДНЫХ ДАННЫХ В ЗАДАЧАХ МНОГОКРИТЕРИАЛЬНОГО 
ВЫБОРА НА ГРАФАХ И ИССЛЕДОВАНИЕ ПРОБЛЕМЫ 
ОТЫСКАНИЯ ПРЕДПОЧТИТЕЛЬНОЙ АЛЬТЕРНАТИВЫ 

Проблема 
отыскания 
множества 
недоминируемых 
альтернатив 
наименьшей мощности является весьма актуальной в настоящее время. 
При этом теория поиска недоминируемых альтернатив считается доста-
точно развитой. Огромное количество публикаций разного уровня посвя-
щено многокритериальным задачам и их свойствам [5, 11, 15, 25, 60, 73, 
85, 87, 129, 151, 152, 207, 216, 221, 223, 228, 283]. 
В математической постановке задачи многокритериального выбора со-
держатся следующие элементы:  
1) множество всех возможных допустимых (альтернативных) решений; 
2) векторная целевая функция для оценки допустимых (альтернатив-
ных) решений; 
3) отношение предпочтения (доминирования) допустимых (альтерна-
тивных) решений между собой. 
Решить задачу многокритериального выбора означает найти множе-
ство недоминируемых альтернатив на основе векторной целевой функции 
и имеющихся сведений об отношении предпочтения лица, принимающего 
решение. При этом достаточно широким является получающееся множе-
ство альтернатив, называемое множеством Парето [14, 97, 126, 151], или 
областью компромиссов. В процессе многокритериального выбора и при-
нятия решения основной проблемой является сужение полученного мно-
жества Парето.  
В реальных системах исходные данные получаются путем экспертного 
оценивания. Эксперты на базе своих рассуждений задают весовые показа-
тели рассматриваемой системы. Эти показатели чаще всего приобретают 
одну из неопределенностей: нечеткое множество, интервал, временной 
ряд. Про такие исходные данные говорят, что они имеют нечеткие или 
размытые границы значений. Моделирование подобных систем с экспертно 
заданными исходными данными, с одной стороны, имеет недетерминированный 
характер, с другой – является более адекватным реальной ситуации. 

В последние десятилетия интенсивно развивается ряд новых дисциплин, 
в основе которых заложен аппарат работы с неопределенностями и 
недетерминированностями: интервальная математика, нечеткая логика, 
теория возможностей [10, 36]. В работе [40] показано, что теория вероятностей 
и теории возможностей являются довольно близкими между собой, 
но имеют ряд важных различий. Математической основой теории возможностей 
является теория нечетких множеств [3, 21, 22, 33, 42, 99, 118]. 
В работе [26] приведено описание теории приближенных множеств 
Павлака, которая представляет собой построение процедур логического 
вывода на базе экспертных оценок о состоянии рассматриваемой сложной 

системы. Такие оценки часто имеют как объективный, так и субъективный 
характер. Синонимами теории нечетких множеств являются: теория приближенных 
множеств [2, 4, 32, 38, 90, 115] и теория недоопределенных 
множеств [149]. Теорию недоопределенных множеств можно назвать 
обобщением существующих подходов к анализу и формализации неопределенностей. 

В настоящее время многие авторы стали классифицировать все имеющиеся 
подходы к моделированию неопределенностей и указывать условия 
их применимости. Общей тенденцией всех имеющихся теорий моделирования 
неопределенностей является их объединение в одну общую. Процесс 
объединения очень интенсивно развивается, и к настоящему времени можно 
говорить о двух укрупненных теориях – нечеткого моделирования [66] 
и прикладного интервального анализа [7, 8, 20, 21, 23, 30, 31, 43, 106, 108]. 

1.1. Формализация прикладных задач в виде задач  
многокритериального выбора на графах в условиях 
недетерминированности исходных данных 

Для неопределенной информации попытки определения строгих границ «
волевым» образом или задание определенности часто приводят к неверному 
результату, так как происходит огрубление данных и потеря информативности. 
Целью математического моделирования является определение 
адекватности всех исходных данных и связей, описывающих исследуемые 
процессы, а также оценка однозначности или неоднозначности 
всех параметров. 

Известные процессы и явления объективного мира можно разделить на 

детерминированные (заданные однозначно) и недетерминированные (за-
данные неоднозначно) [45, 74, 90, 91, 125, 285]. Процессы и явления, в ко-
торых можно определить однозначно реакцию исследуемой системы на 
заданные воздействия, являются детерминированными. Недетерминиро-
ванными являются процессы и явления, в которых при заданном множе-
стве условий реакция системы является различной при выполнении одних 
и тех же условий. 

Основными причинами появления недетерминированности могут быть: 
– огромное количество факторов, которые не всегда бывают известны 

аналитику и от которых зависит рассматриваемая система; 

– огрубление модели, являющее следствием исключения несуществен-

ных, по мнению исследователя, параметров; 

– различные погрешности, ошибки при расчетах, погрешности измере-

ний и др.; 

– использование экспертных оценок, базирующихся на рассуждения 

человека [45]. 

О недетерминированности исходных данных рассматриваемой систе-

мы говорят при неполноте и неточности информации о протекающих про-
цессах, недостаточности и недостоверности знаний, наличии субъективно-

сти экспертных оценок. Математически недетерминированность [47, 74, 
125, 131, 138, 285] может быть описана статистическими данными, состав-
ляющими временной ряд, с позиций теории нечетких множеств, а также 
интервалом значений. Отмеченные формы описания перечислены по воз-
растанию степени неопределенности. Для иллюстрации рассмотрим три 
прикладные задачи, которые можно формализовать как дискретные много-
критериальные задачи на графах в условиях недетерминированности ис-
ходных данных. 
Транспортная задача с промежуточными пунктами [57, 58, 286]. 
Транспортная задача с промежуточными пунктами представляет собой 
общий случай известной транспортной задачи и связана с возможностью 
доставки продукции от некоторого источника i к заданному стоку j . 
Примером промежуточных пунктов является логистическая система 
крупной компании, имеющей сеть магазинов в различных городах. В такой 
системе всегда имеются зональные и региональные пункты, через которые 
продукция поступает от источника в стоки. Причем всегда имеются огра-
ничения: продукция не всегда может быть доставлена из любого источника 
и по любому маршруту и не обязательно может проходить через промежу-
точные пункты.  
Промежуточные пункты могут иметь свои особенности. Например, при 
доставке продукции от источника к стоку через склад часть продукции 
может оставаться неприкасаемой на складе. 
Введем обозначения:  

I  – пункты отправки; 
J  – промежуточные пункты; 
K  – пункты назначения; 

iA  – максимальный объем потребления продукта пунктом i;  

k
B  – объем необходимого для доставки k -му пункту потребления про-
дукта;  

jk
D  – максимально возможный объем продукта для перевозки из про-
межуточного пункта j  к потребителюk ; 

ij
E  – максимально возможный объем продукта при доставке из пункта 
производства i в промежуточный пункт j; 

ijk
с  – стоимость доставки единицы продукции из пункта производства i 
через промежуточный пункт j к потребителю k , 
I
i∈ , 
J
j ∈ , 
K
k ∈ .  
Если величинам 
iA , 
k
B , 
jk
D , 
ij
E , 
ijk
с  невозможно задать точные значения, 
а можно представить в виде нечетких множеств, интервалов или времен-
ных рядов значений за предыдущий период, то эту задачу следует отнести 
к классу задач многокритериального выбора на графах в условиях неде-
терминированности исходных данных. 
Рассматриваемая задача заключается в определении таких величин 
объемов продукции 
ijk
x , которые могут быть доставлены из пункта произ-

водства i через промежуточный пункт j к потребителю k , для которых 
выполняются условия:  

i
J
j
K
k
ijk
A
x
≤
∑ ∑
∈
∈

, 
I
i ∈ ; 
k
I
i
J
j
ijk
B
x
≥
∑∑
∈
∈

, 
K
k ∈
; 

k
I
i
J
j
ijk
B
x
≥
∑∑
∈
∈

, 
K
k ∈
; 
jk
I
i
ijk
D
x
≥
∑
∈

, 
J
j ∈ , 
K
k ∈
; 

0
≥
ijk
x
, 
I
i ∈ , 
J
j ∈ , 
K
k ∈
. 

 
(1.1) 

Целевая функция характеризует суммарные затраты на перевозку продукции 
и имеет вид 

min
→
⋅
∑∑∑
∈
∈
∈
I
i
J
j
K
k
ijk
ijk x
c
.
(1.2)

Задача распределения мощностей каналов передачи данных провайдерами 
сети Интернет. Данная задача относится к задачам распределения 
ограниченных ресурсов в иерархических системах [210, 286]. Формулировка 
задачи распределения ресурсов в иерархических системах состоит в 
следующем. Имеется иерархическая система, состоящая из элементов, которые 
могут производить, передавать или потреблять некий однородный 
ресурс. Для такой системы характерно наличие ограничений на объемы 
передаваемого ресурса. Такие объемы в большинстве случаев бывает невозможно 
задать точными числами, поэтому их описывают интервалами 
значений и нечеткими множествами. Целью распределения ресурсов в 
иерархических системах является нахождение таких допустимых объемов 
ресурсов, при которых принимают экстремальные значения критерии оптимальности, 
определяющие эффективность функционирования системы. 
Наличие нескольких критериев оптимальности в таких задачах делает их 
многокритериальными.  
Рассмотрим математическую постановку задачи распределения информационных 
ресурсов в сети городского провайдера Интернет. Пусть 
заданы необходимые для абонентов сети Интернет потребности в той или 
иной информации. Являются известными провайдеры и их возможности 
по предоставлению каналов для передачи данных различной мощности 
между принадлежащими им узлами связи. Для каждого абонента или узла 
определены пожелания по передаче требуемого количества информации.  
При этом для каждого конкретного распределения каналов и их пропускной 
способности можно признать или не признать их эффективность. 
Является различной структура каналов передачи и самой информации в 
ней. В рассматриваемой задаче могут быть следующие ограничения: 
− информация передается от провайдера центра к абонентам через 
коммутационные узлы по каналам связи; 
− каждый абонент может обслуживаться одним или несколькими коммутационными 
узлами; 
– имеются ограничения на объем распределения информации (возможности 
каждого провайдера и минимальные потребности абонентов в получаемой 
информации). 

Целью в такой задаче является эффективное распределение пропускной 
способности каналов, при котором будут удовлетворены потребности 
абонентов сети с учетом возможностей провайдеров. 
Введем обозначения для множеств:  
P  – провайдеры сети Интернет; 
R  – коммуникационные узлы; 
U  – абоненты сети Интернет.  
Пусть 
_
iA  и 
+
iA  являются верхним и нижним ограничениями пропускной 
способности каналов передачи данных, которые может предоставить 
провайдер i;  

_
iB  и 
+
iB  являются верхним и нижним ограничениями коммуникационного 
узла j  по обработке общей мощности канала передачи данных;  

_
k
С  и 
+
k
C  являются верхним и нижним ограничениями предоставления 
абоненту k  общей мощности канала передачи данных;  

_
ijk
D  и 
+
ijk
D  являются верхним и нижним ограничениями пропускной 
способности канала передачи данных от провайдеров к абонентам через 
коммуникационные узлы;  

ih  – затраты на предоставление провайдером i связи удельной мощности; 


j
g  – затраты на обработку передающей станцией j  связи удельной 
мощности;  

kq  – доход от получения абонентом k  связи удельной мощности; 
P
i ∈
, 

R
j ∈
, 
U
k ∈
.  
Целью сформулированной задачи является максимизация суммарного 
дохода и отыскание таких значений мощности канала связи 
ijk
x для предоставления 
абонентам k  через коммуникационные узлы j  провайдерами i, 

P
i ∈
, 
R
j ∈
, 
U
k ∈
, для которых выполняются условия: 

+

∈
∈
≤
≤ ∑∑
i
R
j
U
k
ijk
i
A
x
A_
, 
P
i ∈
; 
+

∈
∈
≤
≤∑∑
j
P
i
U
k
ijk
j
B
x
B _
, 
R
j ∈
;

+

∈
∈
≤
≤ ∑∑
k
P
i
R
j
ijk
k
C
x
C _
, 
U
k ∈
; 
+
≤
≤
ijk
ijk
ijk
D
x
D _
, 
P
i ∈
, 
R
j ∈
, 
U
k ∈
. 

(1.3) 

Целевая функция характеризует суммарный доход и принимает вид 

(
)
max
→
−
−
∑ ∑ ∑
∈
∈
∈
P
i
R
j
U
k
ijk
j
i
k
x
g
h
q
.
(1.4)

Задача выбора оптимального набора средств программно-аппаратной 
защиты информации [274]. Можно сформулировать задачу определения 
мер и средств программно-аппаратной защиты информации в двух поста-
новках [69]. Целью первой постановки является минимизация стоимости 
мер и средств программно-аппаратной защиты при требуемой эффектив-
ности мер защиты, целью второй постановки является, соответственно, 
максимизация эффективности мер защиты при ограничении на стоимость 
средств.  

При этом имеется определенная нормативными документами ФСТЭК 
последовательность этапов построения защиты информации: 
1) выявление и оценка актуальности потенциально возможных угроз 
информационной безопасности;  
2) оценка вероятности возникновения актуальных угроз;  
3) определение класса защищенности информационной системы; 
4) установление набора мер по защите информации для определенного 
класса защищенности. 
В работе [69] сформулирована задача определения мер и средств про-
граммно-аппаратной защиты информации, состоящая в покрытии графа 
множества требований по защите информации множеством мер и способов 
защиты. Данная постановка использует профиль функциональных требо-
ваний защиты согласно ГОСТ Р ИСО/МЭК 15408.  
В третьей постановке цель экономической целесообразности выбран-
ных мер и средств защиты информации не ставится. Для решения задачи в 
ней необходимо иметь строгие методики для осуществления обоснованно-
го выбора конкретных мер, способов и средств защиты информации. От-
сутствие таких строгих методик приводит к несостоятельности и неадек-
ватности выбранного набора мер и средств защиты информации. 
Процесс поиска, изучения, анализа и выбора средств является очень 
сложным и продолжительным, во многом зависит от уровня знаний экс-
перта. Поэтому при выборе следует учитывать некоторые ограничения и 
факторы. В силу этого обстоятельства возникают различные ошибки, ко-
торые в свою очередь приводят к выбору далеко не оптимального набора 
средств защиты. Такие ошибки могут нанести серьезный материальный 
ущерб предприятию. Поэтому актуальным становится решение задач мно-
гокритериального выбора состава набора средств защиты информации.  
Для решения такой задачи следует использовать математические моде-
ли теории многокритериальной оптимизации и теории принятия решения. 
В работе [212] предлагается подход к осуществлению выбора опти-
мального набора средств защиты, используя целевую функцию «предпо-
чтительность средства защиты информации». Для вычисления показателя 
предпочтительности средства защиты информации необходимо найти 
сумму обязательных показателей экспертных оценок (требования РД 
ФСТЭК и ФСБ по функциональности) и дополнительных требований с 
учетом их важности для каждого средства защиты информации в отдель-
ности. 
Сформулированная модель является неприменимой, если: 
– средства защиты информации покрывают функциональные требова-
ния из различных подсистем; 
– средства защиты информации внутри одной подсистемы покрывают 
все требования по функциональности только частично. 
Для решения сформулированной задачи в работе [212] предложена 
частная оптимизационная модель, которая является уточнением моделей 
многокритериальной оптимизации. При этом предложенная модель соче-