Задачи многокритериального выбора на графах в условиях недетерминированности исходных данных


НАУЧНАЯ МЫСЛЬ

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

ЗАДАЧИ МНОГОКРИТЕРИАЛЬНОГО ВЫБОРА НА ГРАФАХ В УСЛОВИЯХ НЕДЕТЕРМИНИРОВАННОСТИ ИСХОДНЫХ ДАННЫХ

Монография



Москва РИОР

УДК ББК

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

519.17:518.2
22.18
К65
        Авторы:
        Копытов В.В. — д-р техн. наук, профессор, профессор кафедры организации и технологии защиты информации, Северо-Кавказский федеральный университет (Ставрополь). Автор более 200 печатных работ, в том числе 2 монографий, 7 учебных пособий, 9 патентов по проблемам построения защищенных информационных систем и информационному противоборству.
        Петренко В.И. — канд. техн. наук, доцент, заведующий кафедрой организации и технологии защиты информации, Северо-Кавказский федеральный университет (Ставрополь). Автор более 200 печатных работ, в том числе 21 учебного пособия, 7 из которых имеют гриф УМО, 80 изобретений по проблемам защиты информации, защиты персональных данных, арифметических операций в конечных полях, синтеза дискретных последовательностей, систем связи.
        Тебуева Ф.Б. — д-р физ.-мат. наук, доцент, заведующий кафедрой прикладной математики и компьютерной безопасности, Северо-Кавказский федеральный университет (Ставрополь). Автор 185 печатных трудов, в том числе 4 монографий, 2 изобретений по проблемам математического моделирования процессов в информационно-телекоммуникационных системах.
        Рецензенты:
        Макаров А.М. — д-р техн. наук, профессор, профессор кафедры информационно-коммуникационных технологий, математики и информационной безопасности Пятигорского государственного университета (Пятигорск).
        Осипян В.О. — д-р техн. наук, доцент, профессор кафедры информационных технологий Федерального государственного бюджетного образовательного учреждения высшего образования «Кубанский государственный университет» (Краснодар).
        Никитина А.В. — д-р техн. наук, доцент, доцент кафедры интеллектуальных и многопроцессорных систем Южного федерального университета (Таганрог).
        Копытов В.В., Петренко В.И., Тебуева Ф.Б.
  К65     Задачи многокритериального выбора на графах в условиях недетер-
        минированности исходных данных / В.В. Копытов, В.И. Петренко, Ф.Б. Тебуева. — М. : РИОР, 2018. — 234 с. — (Научная мысль). — DOI: https://doi.org/10.29039/0883-6
           ISBN 978-5-369-00883-6
           В монографии исследуются вопросы моделирования сложных систем, которые математически формализуются как задачи многокритериального выбора на графах в условиях недетерминированности исходных данных. Недетерминированность исходных данных возникает в ситуациях, когда не представляется возможным проведение вычислительного эксперимента и получения точных значений характеристик функционирования системы. Рассматриваются задачи, имеющие исходные данные в виде нечетких множеств, интервалов значений и временных рядов.
           Для преподавателей, студентов, аспирантов физико-математических и технических специальностей, интересующихся вопросами моделирования слабоформализуемых процессов.
                                                      УДК 519.17:518.2
                                                      ББК 22.18


ISBN 978-5-369-00883-6

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

ВВЕДЕНИЕ


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

3

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

4

Глава 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] приведено описание теории приближенных множеств Павлака, которая представляет собой построение процедур логического вывода на базе экспертных оценок о состоянии рассматриваемой сложной

5

системы. Такие оценки часто имеют как объективный, так и субъективный характер. Синонимами теории нечетких множеств являются: теория приближенных множеств [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].
   О недетерминированности исходных данных рассматриваемой системы говорят при неполноте и неточности информации о протекающих процессах, недостаточности и недостоверности знаний, наличии субъективно

6

сти экспертных оценок. Математически недетерминированность [47, 74, 125, 131, 138, 285] может быть описана статистическими данными, составляющими временной ряд, с позиций теории нечетких множеств, а также интервалом значений. Отмеченные формы описания перечислены по возрастанию степени неопределенности. Для иллюстрации рассмотрим три прикладные задачи, которые можно формализовать как дискретные многокритериальные задачи на графах в условиях недетерминированности исходных данных.
    Транспортная задача с промежуточными пунктами [57, 58, 286]. Транспортная задача с промежуточными пунктами представляет собой общий случай известной транспортной задачи и связана с возможностью доставки продукции от некоторого источника i к заданному стоку j.
    Примером промежуточных пунктов является логистическая система крупной компании, имеющей сеть магазинов в различных городах. В такой системе всегда имеются зональные и региональные пункты, через которые продукция поступает от источника в стоки. Причем всегда имеются ограничения: продукция не всегда может быть доставлена из любого источника и по любому маршруту и не обязательно может проходить через промежуточные пункты.
    Промежуточные пункты могут иметь свои особенности. Например, при доставке продукции от источника к стоку через склад часть продукции может оставаться неприкасаемой на складе.
    Введем обозначения:
    I - пункты отправки;
    J - промежуточные пункты;
    K - пункты назначения;
    Aᵢ - максимальный объем потребления продукта пунктом i;
    Bₖ - объем необходимого для доставки k -му пункту потребления продукта;
    Dⱼₖ - максимально возможный объем продукта для перевозки из промежуточного пункта j к потребителю k;
    Ej - максимально возможный объем продукта при доставке из пункта производства i в промежуточный пункт j;
    cᵢⱼₖ - стоимость доставки единицы продукции из пункта производства i через промежуточный пункт j к потребителю k, i е I, j е J, k е K.
    Если величинам Ai, Bₖ, Dⱼₖ, Eij, cᵢⱼₖ невозможно задать точные значения, а можно представить в виде нечетких множеств, интервалов или временных рядов значений за предыдущий период, то эту задачу следует отнести к классу задач многокритериального выбора на графах в условиях недетерминированности исходных данных.
    Рассматриваемая задача заключается в определении таких величин объемов продукции xᵢⱼₖ, которые могут быть доставлены из пункта произ

7

водства i через промежуточный пункт j к потребителю k, для которых выполняются условия:
     XX Xijk * Ai, i e I; XX Xijk > Bk, k e K ;
     j e Jk e K       ie I j e J
     XX x.jk > Bk, k e K; X Xijk > Djk, j e J, k e K;           (1.1)
     i e I j e J      i e I
     Xijk > 0, i e I, j e J, k e K.
    Целевая функция характеризует суммарные затраты на перевозку продукции и имеет вид
     XXX cijk ■ xijk ^ mⁱn.                                     ⁽1.²⁾
     ieI je JkeK
    Задача распределения мощностей каналов передачи данных провайдерами сети Интернет. Данная задача относится к задачам распределения ограниченных ресурсов в иерархических системах [210, 286]. Формулировка задачи распределения ресурсов в иерархических системах состоит в следующем. Имеется иерархическая система, состоящая из элементов, которые могут производить, передавать или потреблять некий однородный ресурс. Для такой системы характерно наличие ограничений на объемы передаваемого ресурса. Такие объемы в большинстве случаев бывает невозможно задать точными числами, поэтому их описывают интервалами значений и нечеткими множествами. Целью распределения ресурсов в иерархических системах является нахождение таких допустимых объемов ресурсов, при которых принимают экстремальные значения критерии оптимальности, определяющие эффективность функционирования системы. Наличие нескольких критериев оптимальности в таких задачах делает их многокритериальными.
    Рассмотрим математическую постановку задачи распределения информационных ресурсов в сети городского провайдера Интернет. Пусть заданы необходимые для абонентов сети Интернет потребности в той или иной информации. Являются известными провайдеры и их возможности по предоставлению каналов для передачи данных различной мощности между принадлежащими им узлами связи. Для каждого абонента или узла определены пожелания по передаче требуемого количества информации.
    При этом для каждого конкретного распределения каналов и их пропускной способности можно признать или не признать их эффективность. Является различной структура каналов передачи и самой информации в ней. В рассматриваемой задаче могут быть следующие ограничения:
    -     информация передается от провайдера центра к абонентам через коммутационные узлы по каналам связи;
    -     каждый абонент может обслуживаться одним или несколькими коммутационными узлами;
    - имеются ограничения на объем распределения информации (возможности каждого провайдера и минимальные потребности абонентов в получаемой информации).

8

    Целью в такой задаче является эффективное распределение пропускной способности каналов, при котором будут удовлетворены потребности абонентов сети с учетом возможностей провайдеров.
    Введем обозначения для множеств:
    P - провайдеры сети Интернет;
    R - коммуникационные узлы;
    U - абоненты сети Интернет.
    Пусть А_- и Ai являются верхним и нижним ограничениями пропускной способности каналов передачи данных, которые может предоставить провайдер i;
    Bi- и Bi являются верхним и нижним ограничениями коммуникационного узла j по обработке общей мощности канала передачи данных;
    Ск и с; являются верхним и нижним ограничениями предоставления абоненту к общей мощности канала передачи данных;
    D_ и Dyₖ являются верхним и нижним ограничениями пропускной способности канала передачи данных от провайдеров к абонентам через коммуникационные узлы;
    hi - затраты на предоставление провайдером i связи удельной мощно

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

мощности;
    qₖ - доход от получения абонентом к связи удельной мощности; i е P,

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

i е P, j е R , к е U, для которых выполняются условия:
     А < ЕЕ Хук < a; , i е P; В_ < ЕЕ Хук < Bj, j е R ;
         jеR кeU               iеP кeU
     С_ < ЕЕ Xj < с; , к е U; D^ < x* < D^, i е P, j e R , к e U. iе P je R

(1.3)

    Целевая функция характеризует суммарный доход и принимает вид
     Е Е Е ш - hi - gj ^Xjk ^ max.                              ⁽1.⁴⁾
     ie P je РкeU
    Задача выбора оптимального набора средств программно-аппаратной защиты информации [274]. Можно сформулировать задачу определения мер и средств программно-аппаратной защиты информации в двух постановках [69]. Целью первой постановки является минимизация стоимости мер и средств программно-аппаратной защиты при требуемой эффективности мер защиты, целью второй постановки является, соответственно, максимизация эффективности мер защиты при ограничении на стоимость

средств.

9

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