Математическая модель принятия решений системного интегрирования в условиях множественного выбора альтернатив

Размещено на http://allbest.ru

Институт компьютерных систем и информационной безопасности Кубанского государственного технологического университета

УДК 681.322 05.00.00 Технические науки

Математическая модель принятия решений системного интегрирования в условиях множественного выбора альтернатив Научный журнал КубГАУ, №112(08), 2015 года, http://ej.kubagro.ru/2015/08/pdf/83.pdf

Хализев Вячеслав Николаевич, к.т.н., профессор;

Угрюмов Дмитрий Викторович, аспирант

системный анализ, управление и

обработка информации (по отраслям),

третий год обучения. SPIN-код 8849-5628.

Краснодар, Россия

Введение

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

В связи с этим, системный интегратор, получивший право участия в проекте информатизации, должен располагать полноценной и достоверной информацией о составе, структуре и состоянии ИТ-инфраструктуры объекта информатизации, должен в краткие и жестко лимитированные сроки разработать технико-коммерческое предложение для заключения конкурса, вынужден в кратчайшие сроки провести полноценное обследование ИТ-инфраструктуры заказчика и решить задачу обоснования оптимального состава средств информатизации, предлагаемых к внедрению.

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

Разработка научного аппарата для решения этой задачи предполагает решение следующих подзадач:

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

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

Задача выбора системным интегратором одного альтернативного решения из нескольких предложенных вариантов при многих критериях-параметрах выбора - это задача МДО. Наиболее известным эвристическим методом построения решения МДО является метод скаляризации с применением линейной либо мультипликативной свертки критериев.

При любых произвольных данных параметров системно интегрированных компонентов - условия вогнутости и выпуклости вектора решений и критериев могут не выполняться - линейная скаляризация принятая в методе анализа иерархий (МАИ) Саати не всегда дает верные решения. интегрированный информационный мультипликативный

Для принятия решения оптимизации технических характеристик интегрированных систем, когда о вероятности появления состояний внешней среды ничего не известно, но с появлением этих состояний необходимо считаться, а также если реализуется лишь малое количество принятия решений, то наиболее применимы минимаксный критерий или критерий Вальда, критерий Севиджа и критерий Гурвица, для которого коэффициент оптимизма r принимает значения 0,25; 0,5; 0,75; 1,0 поочереди.

Задача множественного выбора

Задача множественного выбора, то есть выбора множества или совокупности решений из набора альтернатив (задача МВ), возникает как задача оптимального выбора некоторого количества подсистем интегрированной системы, в следующем виде. При системном интегрировании перед ЛПР стоит задача выбора между несколькими всеобъемлющими многофункциональными системами (имеющими много технических параметров и возможно качественных экспертных характеристик для сравнения) и возможно несколькими узкоспециализированными подсистемами, как правило с лучшими некоторыми параметрами, чем у первых, а также их возможными сочетаниями.

Чистая модель МДО не может реализовать такую системную интеграцию. Она дает возможность выбора ПО решений в виде ранжирования альтернатив по предпочтениям ЛПР с учетом различных критериев отбора. Но каждая альтернатива оценивается независимо друг от друга, то есть не в системном взаимодействии с другими решениями.

Наиболее близким по смыслу к задаче системного интегрирования является модель выбора набора альтернатив (различных видов оборудования в [2]) путем решения задачи о наименьшем покрытии множества - ЗНП. Сформулируем ее в терминах системной интеграции.

Пусть определено множество технических параметров оборудования ИС и требований к ним , и множество объектов (элементов оборудования), таких, что каждый ассоциирован с подмножеством . При этом удовлетворяет всем требованиям из , либо выполняет функции из с определенным качеством. Совокупность называется покрытием множества , если .

Определим матрицу:

Задача выбора оптимальной по стоимости совокупности элементов оборудования системы из составляющих ее объектов , для реализации полного набора заданных функций (требований) как задача ЦЛП имеет вид:

при условиях:

В этом случае задача структурного синтеза сводится к определению экстремального значения целевой функции (1).

Если интерпретировать как эффективность элементов оборудования, то значения целевой функции (4) определят максимальную эффективность набора оборудования, для построения системы, удовлетворяющей всем заданным требованиям, при тех же ограничениях (2) и (3):

Использовать модель ЗНП из [2] для системной интеграции напрямую не представляется возможным по следующим соображениям.

1. Неизвестно откуда брать значения В_j . Если это сумма параметров альтернативы из модели МДО, то получим, что вектор параметров заменен его линейной сверткой и все многообразие параметров альтернативы S_j не будет учтено при системной интеграции объектов S. Модель ограничена только одним критерием -- АЛС.

2. При объединении параметров качества в покрытии суммирование не всегда корректно для всех типов параметров.

Для устранения этих недостатков модели из [2] необходимо объединение ЗНП и МДО в одну модель с возможностью учета системного взаимодействия элементов, входящих в множественный выбор, что и является конечной целью исследования для формирования процедур поддержки принятия решений системным интегратором.

Модели МДО и ЗНП должны быть объединены не просто механически, а встроены одна в другую, передавать друг другу свои результаты и настройки критериев поиска. При этом модель ЗНП генерирует покрытия с использованием метода ветвей и границ (МВГ), затем получает из него промежуточные альтернативы множественного выбора и далее модель МДО обрабатывает их по критериям, отобранным для оптимизации технических приложений.

Итак, для построения объединенной модели ЗНП+МДО введем в математическую модель (1) данные о технических параметрах решаемых задач R путем добавления матрицы натуральных чисел В. Определим матрицу :

Если объекты имеют конкретные числовые характеристики, отражающие их количественные или качественные параметры по реализации функции (требования) r_i, то их можно взять в качестве величин , проведя стандартную процедуру согласования и нормализации (приведения к единому диапазону [0..1], (1 - лучший показатель, 0 - худший), чтобы их правомерно было сравнивать как показатели качества. Фактически этим мы соединили модель ЗНП и МДО, так как вектор и есть вектор критериев задачи МДО, но с возможно «пустыми» значениями тех параметров, которые не реализованы в : . Заметим, что модель МДО работает с полным вектором Вj уже после его генерации в модели ЗНП.

Эта обобщенная модель несколько похожа по постановке задачи на обобщенную ЗНП (минимизации системы булевых функций, распределения ресурсов по нескольким потребителям), приведенную в [7], но только в том смысле, что она в одном частном случае даст тот же результат, что и ОЗНП - если все веса в будут по 1 и используется только один критерий МДО - АЛС. То есть модель (7) - более общий случай, с большими возможностями параметрической системной интеграции и получением множественного решения.

В общем случае технические параметры имеют разный физический смысл, поэтому для одних включение в решение объектов и требует суммирования показателей и , а для других значения max(, ), поэтому сумму в критерии (6) необходимо заменить на нелинейный функционал Ш:

где D=(d_l,...,d_m) - вектор, учета типа задачи r_i..

Чтобы учесть разный вес задач r_i. в критерии (4) из-за чувствительности результата к изменениям соотношения параметров , для разных столбцов необходимо ввести весовой коэффициент важности - вектор, , и целевая функция (4) приобретает вид:

С практической точки зрения интересной задачей является задача определения выбранного состава оборудования минимальной стоимости при заданной степени качества решения задачи (качества решения всех задач R). Эта задача решается как задача ЦЛП вида:

при условиях:

Где

Обратная задача - при заданной максимальной стоимости С_max выбранного состава оборудования обеспечить максимальную степень качества решения всех задач из R - решается как задача нелинейного программирования вида:

при ограничениях:

Этим мы соединили модель ЗНП и МДО в одну модель системной интеграции с множественным выбором альтернатив.

Если все функции заменить на суммы, то результат совпадет с моделью в [2], только суммирования сначала по столбцам выбранных альтернатив, а потом по строкам, и значит с тем же результатом, что и по АЛС как и в МАИ. Модель (12) скорректирована относительно (4) с АЛС на шаге получения нелинейным функционалом вектора параметров МВ, но этого недостаточно. Линейная скаляризация в ней присутствует, и изменить это в рамках этой модели не представляется возможным.

В [7] показано, что решение ЗНП методом ЦЛП в общем случае не является выпуклой в пространстве , поэтому неправомерно решать задачу выбора оптимальной структуры системы из множества составляющих ее объектов (1) методом линейной свертки.

При этом фактически, введением матрицы , мы изменили задачу (7) на задачу многокритериальной дискретной оптимизации (МДО) с критериями вида (10-11) для каждой функции из R.

Другим известным подходом к определению множества решений многокритериальной задачи является метод уступок, используя который можно поставить задачу нахождения некоторого подмножества парето-оптимальных решений [2]. В методе уступок по алгоритму А1, при котором от двухкритериальной задачи (1)-(4) переходят к однокритериальной задаче вида (4) и ограничению

где - решение задачи (1) F₁(x^*),

- величина уступки.

Таким образом, задачу МДО удается свести к итерационному алгоритму А1 следующего вида:

Шаг 1: Решить m раз задачу ЦНП вида (17) при условиях (10), а также дополнительном ограничении (18):

Шаг 2: Определить вектор X*, при котором

Шаг 3: Вычислить и присвоить значение точки [, ] по формуле (19),

; Если , то стоп, иначе перейти на шаг 1.

Этот алгоритм решает задачу МДО методом свертки (анализа иерархий) Саати, скорректированный нелинейной сверткой. В [6,7] доказано, что так получается парето-оптимальное решение «разумного» многокритериального выбора.

Для точного решения ЗНП используем новый элемент в модели ЗНП - алгоритм генерации векторов полного множества альтернатив (ПМА), получаемый методом ветвей и границ (МВГ).

Генерация каждой новой альтернативы идет по пути поиска ближайшего тупикового покрытия, а граница заключается в отсечении не тупиковых покрытий. Ищутся все тупиковые покрытия или все простые импликанты булевой функции ( СкДНФ функция матрицы |А| ) .

Для практического решения реальных задач ЗНП используются, как правило, приближенные алгоритмы, среди которых ведущее место принадлежит, так называемым "жадным" алгоритмам. Для поставленных задач наиболее подходит метод модификации "жадного" алгоритма, на каждом шаге которого вычисляется оценка

При этом в покрытие включается элемент с оценкой

Для точного решения ЗНП используем новый элемент в модели ЗНП - алгоритм генерации векторов полного множества альтернатив (ПМА), получаемый методом ветвей и границ (МВГ).

Генерация каждой новой альтернативы идет по пути поиска ближайшего тупикового покрытия (методом Закревского), а граница заключается в отсечении не тупиковых покрытий. Ищутся все тупиковые покрытия или все простые импликанты булевой функции ( СкДНФ функции матрицы |А| ) .

В данной постановке задачи для процесса МДО нужны все тупиковые покрытия, полученные по Т-критерию. Поэтому перебор всех тупиковых решений может быть получен в любом порядке путем генерации методом ветвей и границ, в котором нахождение минимального тупикового покрытия и является условием отсечения дальнейшего поиска решения. Поэтому в алгоритме реализации выбирается метод покрытия Закревского с полным перебором дерева покрытий по Т-критерию.

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

Есть ли таких генерируемых альтернатив решений достаточно много и они сами могут составить полное покрытие множественного выбора, то этот случай покрывается Т-критерием и он входит пространство поиска выбора в любом случае.

Т-критерий уточняется следующим алгоритмом для обеспечения ввода доминируемых альтернатив в решение.

Алгоритм Ту-критерия

Цикл по j в группе:

1. Ищется альтернатива S1 с максимальным весом

2. Ищется альтернатива S2 с минимальным весом

3. Проверяем, что S1 доминирует над S2. Искусственно, обнуляем значение

Конец цикла по j.

Уточнение Т-критерия проводится для более глубокой связи МДО и ЗНП и получения более полного множество решений.

В качестве иллюстрации применения уточняющего критерия на рисунках 1-3 приведены примеры получения полного множества решений , его Парето-оптимальный фронт, и уточненный вариант по нескольким параметрам с использованием Ту-критерия для примера из 33 альтернатив и 25 параметров сформированных в 5 групп.

Рисунок 1 -- Результат Ту-критерия (первичная оценка система № 9026)

Рисунок 2 -- Результат Ту-критерия (первичная оценка система № 1)

Рисунок 3-- Результат Ту-критерия (уточнение 2 система № 70)

Практическая реализация алгоритма А1 показала практическую возможность решения задач размерностью 300х300 с приемлемой точностью.

Иллюстрация системных свойств модели на примере выборки небольшого размера со специально подобранными данными межсетевых экранов, систем обнаружения вторжений и антивирусных средств представлена на рисунке 4.

Модель системной интеграции размером 200 на 300 это вполне реальная область принятия решения системным интегратором по современным требованиям стандартов ИТ-технологий.

Таким образом, решается задача разработки моделей и методов, позволяющих на основе анализа требований, предъявляемых к обеспечению ИС, выбирать оптимальный набор оборудования для синтеза интегрированной системы из различных подсистем и элементов, предложенных на рынке.

Рисунок 4- Иллюстративный пример системного интегрирования

Список литературы

1. В.Д. Ногин. Принятие решений при многих критериях. Учебно-методическое

пособие.- СПб. Издательство «ЮТАС», 2007. - 104 с.

2. Заозерская Л.А., Колоколов А.А. Исследование и решение двухкритериальной задачи о покрытии множества. //Проблемы информатики №2, 2009, URL: http://problem-info.ru›2009-2/2.pdf, (дата обращения: 25.06.2012).

3. Я. Е. Львович, Г. Д. Чернышева, И. Л. Каширина, Воронежский государственный технический университет, Воронежский государственный университет- Оптимизация проектных решений в САПР на основе эквивалентных преобразований задачи о минимальном покрытии. Электронное научно-техническое издание № ФС 77 - 30569. Государственная регистрация №0421100025 URL: http://technomag.edu.ru/index.html, (дата обращения: 25.06.2012).

4. Ногин В.Д., Басков О.В. Сужение множества Парето на основе учёта произвольного конечного набора числовой информации об отношении предпочтения // Доклады АН, 2011, т. 438, № 4, С. 1-4.

5. Ногин В.Д. Границы применимости распространенных методов скаляризации при решении задач многокритериального выбора// Методы возмущений в гомологической алгебре и динамика систем: Межвуз. сб. науч. тр. Саранск: Изд-во Мордов. ун-та, 2004, С. 59-68.

6. Ногин В.Д. Логическое обоснование принципа Эджворта-Парето // Журнал вычисл. математики и мат. Физики.-2002.-Т.42, № 7.- с.951-957.

7. Есипов Б.А., Муравьев В.В. Исследование алгоритмов решения обобщенной задачи о минимальном покрытии. Известия Самарского научного центра Российской академии наук, т. 16, №4(2), 2014.

References

1.V.D. Nogin. Prinjatie reshenij pri mnogih kriterijah. Uchebno-metodicheskoe

posobie.- SPb. Izdatel'stvo «JuTAS», 2007. - 104 s.

2.Zaozerskaja L.A., Kolokolov A.A. Issledovanie i reshenie dvuhkriterial'noj zadachi o pokrytii mnozhestva. //Problemy informatiki №2, 2009, URL: http://problem-info.ru›2009-2/2.pdf, (data obrashhenija: 25.06.2012).

3.Ja. E. L'vovich, G. D. Chernysheva, I. L. Kashirina, Voronezhskij gosudarstvennyj tehnicheskij universitet, Voronezhskij gosudarstvennyj universitet- Optimizacija proektnyh reshenij v SAPR na osnove jekvivalentnyh preobrazovanij zadachi o minimal'nom pokrytii. Jelektronnoe nauchno-tehnicheskoe izdanie № FS 77 - 30569. Gosudarstvennaja registracija №0421100025 URL: http://technomag.edu.ru/index.html, (data obrashhenija: 25.06.2012).

4.Nogin V.D., Baskov O.V. Suzhenie mnozhestva Pareto na osnove uchjota proizvol'nogo konechnogo nabora chislovoj informacii ob otnoshenii predpochtenija // Doklady AN, 2011, t. 438, № 4, S. 1-4.

5.Nogin V.D. Granicy primenimosti rasprostranennyh metodov skaljarizacii pri reshenii zadach mnogokriterial'nogo vybora// Metody vozmushhenij v gomologicheskoj algebre i dinamika sistem: Mezhvuz. sb. nauch. tr. Saransk: Izd-vo Mordov. un-ta, 2004, S. 59-68.

6. Nogin V.D. Logicheskoe obosnovanie principa Jedzhvorta-Pareto // Zhurnal vychisl. matematiki i mat. Fiziki.-2002.-T.42, № 7.- s.951-957.

7. Esipov B.A., Murav'ev V.V. Issledovanie algoritmov reshenija obobshhennoj zadachi o minimal'nom pokrytii. Izvestija Samarskogo nauchnogo centra Rossijskoj akademii nauk, t. 16, №4(2), 2014.

Аннотация

УДК 681.322

05.00.00 Технические науки

Математическая модель принятия решений системного интегрирования в условиях множественного выбора альтернатив. Хализев Вячеслав Николаевич, к.т.н., профессор; Угрюмов Дмитрий Викторович, аспирант 05.13.01 системный анализ, управление и обработка информации (по отраслям), третий год обучения.

SPIN-код 8849-5628.

Институт компьютерных систем и информационной безопасности Кубанского государственного технологического университета, Краснодар, Россия

В статье рассмотрены модели и методы, позволяющие из предложенных подсистем и компонентов, на основе анализа требований, предъявляемых к обеспечению параметров, выбрать оптимальное решение для синтеза интегрированной системы

Ключевые слова: математическая модель синтеза, анализ требований, системная интеграция

Annotation

UDC 681.322 Technical sciences

Mathematical model of decision-making system integration in the multiple choice alternatives. Halizev Vyacheslav Nikolaevich, Cand.Tech.Sci., professor; Ugriumov Dmitry Victorovich, postgraduate student of System analysis, management and information processing, third year of study.

RSCI SPIN-code: 8849-5628.

Institute of Computer Systems and Information Security Kuban State Technological University, Krasnodar, Russia

The article deals with the models and the methods of the market of the proposed sub-systems and equipment, based on the analysis of the requirements for security to choose the best solution for the synthesis of the integrated security system

Keywords: mathematical model for synthesis, analysis of requirements, system integration

Размещено на Allbest.ru