Введение в методы и алгоритмы принятия решений

Â.Ã. Äîðîãîâ, ß.Î. Òåïëîâà

ÂÂÅÄÅÍÈÅ
 ÌÅÒÎÄÛ È ÀËÃÎÐÈÒÌÛ
ÏÐÈÍßÒÈß ÐÅØÅÍÈÉ

Ðåêîìåíäîâàíî Ó÷åáíî-ìåòîäè÷åñêèì Ñîâåòîì Ìîñêîâñêîãî
Ãîñóäàðñòâåííîãî èíñòèòóòà ýëåêòðîííîé òåõíèêè
(òåõíè÷åñêîãî óíèâåðñèòåòà) â êà÷åñòâå ó÷åáíîãî ïîñîáèÿ
äëÿ ñòóäåíòîâ âûñøèõ ó÷åáíûõ çàâåäåíèé, îáó÷àþùèõñÿ

è ïî îñíîâíîé îáðàçîâàòåëüíîé ïðîãðàììå ïîäãîòîâêè
áàêàëàâðîâ

Ïîä ðåäàêöèåé ïðîôåññîðà Ë.Ã. Ãàãàðèíîé

по направлению 09.03.01 «Информатика и вычислительная техника»

19.03.04 «Программная инженерия»

Москва 
ИД «ФОРУМ» — ИНФРА-М
2022

9.

;

09.03.01 «Информатика и вычислительная техника», аспирантов, преподава
Введение в методы и алгоритмы принятия решений : учебное пособие / В.Г. Дорогов, Я.О. Теплова ; под ред. проф. Л.Г. Гагариной. — 
Москва : ИД «ФОРУМ» : ИНФРА-М, 2022. — 240 с. — (Высшее образование).

Введение

Термин «принятие решений» встречается в различных научных
дисциплинах. Различные виды деятельности человека связаны с выбором и принятием решений. Человек стремится сделать оптимальный выбор из доступных альтернатив для достижения целей. Рассматриваемые проблемы актуальны, например, для планирования
производства, для организационного управления, для создания и внедрения информационных систем различного масштаба и назначения,
для решения иных научнотехнических задач и др.
«Принятие решений» — один из основополагающих терминов в
научном направлении, известном под названием «исследование операций». Принятие решений является одним из направлений прикладной математики. Ставятся и решаются задачи обоснования свойств
функции полезности в зависимости от тех или иных условий, накладываемых на правила выбора. Проблемы принятия оптимальных решений изучаются в теории принятия решений, которая в наиболее
общем смысле представляет собой совокупность математических и
численных методов, которые ориентированы на нахождение наилучших вариантов из множества альтернатив и позволяют избежать их
полного перебора.
Считается, что практическая потребность общества в научных основах принятия решений возникла с развитием науки и техники.
Термин «решение проблем», близкий по своему характеру к термину «принятие решений», является центральным для искусственного интеллекта. В рамках этого направления создаются различные
компьютерные системы, имитирующие поведение людей при решении тех или иных проблем.
В информатике и вычислительной технике в последнее время
уделяется большое внимание построению систем поддержки принятия решений, помогающих человеку в задачах выбора.
Рассмотрение процессов и проблем принятия решений в различных научных дисциплинах вполне оправданно. Центральным для

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

4
Введение

Глава 1
ОБЩЕЕ ОПИСАНИЕ ЗАДАЧ ПРНЯТИЯ
РЕШЕНИЙ

1.1. Базовые понятия и определения

В задаче ТПР (теории принятия решений) человек (или группа
лиц) сталкивается с необходимостью выбора одного или нескольких
альтернативных вариантов решений (действий, планов поведения).
Необходимость такого выбора вызвана какойлибо проблемной ситуацией, в которой имеются два состояния: желаемое и действительное, а
способов достижения желаемой целисостояния — не менее двух. Таким образом, у человека в такой ситуации есть некоторая свобода выбора между несколькими альтернативными вариантами. Каждый вариант выбора (выбор альтернативы) приводит к результату, который
называется исходом. У человека есть свои представления о достоинствах и недостатках отдельных исходов, свое собственное отношение к
ним, а следовательно, и к вариантам решения. Таким образом, у человека, принимающего решение, есть система предпочтений.
Под принятием решений понимается выбор наиболее предпочтительного решения из множества допустимых альтернатив [19].
Под принятием решений понимается выбор наиболее предпочтительного решения из множества допустимых альтернатив.
Теория принятия решений (ТПР) — совокупность методов и моделей, предназначенных для обоснования решений, принимаемых на
этапах анализа, разработки и эксплуатации сложных систем различной природы: информационных, технических, производственных,
социальноэконогмических и др.
Отличительная особенность используемых методов состоит в том,
что они применяются для формализации определенного вида челове

ческой деятельности, ориентированного на установление наилучшего
варианта действий.

Выбор методов зависит от класса анализируемых проблем:

• структурированные;

• слабоструктурированные.
1. Задачи первого типа характризуются тем, что все параметры
анализируемой системы и внешней среды являются детерминированными, а искомые решения — непрерывными либо дискретными.
Примеры наиболее известных задач с дискретными значениями переменных: задача коммивояжера, задача о минимальном покрытии графа, минимаксная задача о назначениях. Например, задача построения топологии локальной вычислительной сети (ЛВС) кольцевой
структуры (Token Ring) сводится к задаче коммивояжера.
Для решения этих задач используются, к примеру, методы ветвей
и границ, динамического программирования, эвристические алгоритмы и т. д. В последнее время применяются генетические алгоритмы и
нейронные сети.

Примеры
1. Одной из известных задач является задача коммивояжера, которая на концептуальном уровне формулируется следующим образом. Задано множество городов A1, ..., An и определена матрица расстояний между городами: C = || cijv ||, где cij — расстояие между iм и jм
городами, i
n
= 1,
, j
n
= 1,
. Коммивояжер находится в городе Ai, необходимо найти такой замкнутый маршрут, связывающий все города,
который имел бы минмальную длину.

6
Глава 1. Общее описание задач прнятия решений

Рис. 1.1. Основные типы задач принятия решений

2. Задача оптимизации топологии ЛВС университета состоит в
том, что задано множество ПК, расположенных в различных корпусах. Необходимо определить такую их последовательность соединения, при которой длина коммуникационных связей была бы минимальной [11].
2. Второй тип принятия решений отностися к задачам принятия
решений в условиях риска и характеризуется тем, что для ряда параметров неизвестны точные значения, а определены диапазоны их изменений и на каждом диапазоне заданы плотности распределения
случайных величин. Необходимо выбрать такое решение, которое для
заданных распределений вероятностей обеспечивает экстремум показателя эффективности. В качестве показателя эффективности выбирается либо среднее зачение, либо комбинация среднего значения и
дисперсии. Примерами таких задач могут являться задачи анализа и
синтеза систем массового обслуживания, управления запасами и т. д.
Упомянутая ранее задача оптимизациии топологии ЛВС может рассматриваться как вероятностная задача, в которой в качестве неопределенных параметров используются возможные места установки рабочих станций. Необходимо определить такую топологию ЛВС, чтобы в среднем за период развития сети обеспечивался бы минимум
затрат на организацию коммуникационных соединений.
3. Третий тип задач характеризуется тем, что для каждого из параметров заданы возможные дискретные значения показателя эффективности, соответствующие каждому из вариантов альтернативных
решений, т. е. исходная задача представляется в виде таблицы, в которой строки соответствуют альтернативным решениям, а столбцы —
дискретным значениям параметров.

Таблица 1.1. Матрица принятия решений

Альтернативные варианты решений

Дискретные значения параметра a

a1
a2
...
ai
...
am

E1
Ei
En

a11
ai1
an1

a12
ai2
an2

...
...
...

a1j
aij
anj

...
...
...

a1m
aim
anm

Пример — задача развития ЛВС университета.
Альтернативные варианты решений — различное число серверов, которые могут быть включены в состав ЛВС E = {E1, ..., En}, а
в качестве значений параметра используется количество рабочих

1.1. Базовые понятия и определения
7

станций a = {a1, ..., am}. Тогда показатель эффективности — это производительность сети для разного количества серверов при фиксированном количестве рабочих станций.
4. Четвертый тип задач характеризуется тем, что принятие решений системным аналитиком производится в условиях конкуренции
противоборствующих сторон. В качестве схемы принятия решений
используется игровая модель.
Перечисленные типы задач могут быть как однокритериальными,
так и многокритериальными. В многокритериальных задачах аналитик при выборе альтернативы стремится улучшить значения двух и
более показателей.
Основополагающий принцип ТПР сформулировали Нейман и
Моргенштерн: лицо, принимающее решение, должно всегда выбирать альтернативу с максимально ожидаемой полезностью. Этот результат строится на ряде аксиом, его называют гипотезой ожидаемой
полезности. Поэтому и задачи формулируются соответственным образом: чем полезнее, предпочтительнее альтернатива, тем выше численная оценка — «чем больше, тем лучше».
В общем случае задача ТПР строится следующим образом: устанавливаются
1) все возможные способы действия — альтернативы;
2) их последовательность и числовая оценка;
3) цели участников процесса принятия решений;
4) природа влияния на этот процесс различных случайных и детерминированных управляющих факторов.
Затем подбирается соответствующая модель и метод решения задачи. Разберем на примере.

1.2. Классификация задач принятия решений. Основные
классы концептуальных задач теории принятия решений

Методы ТПР могут использоваться в различных предметных приложениях: технических, производственных, социальных, экономических и др. Большинство из анализируемых на концептуальном уровне
проблем сводятся к нижеперечисленным классам задач:
• оптимизация на сетях;
• распределение ресурсов;

8
Глава 1. Общее описание задач прнятия решений

• календарное планирование и упорядочение работ;
• сетевое планирование и управление;
• распределение ресурсов;
• задачи теории массового обслуживания;
• задачи поиска;
• управление запасами;
• ремонт и замена оборудования и др.
Наиболее общими и существенными признаками классификации
задач принятия решений являются следующие [24].
1. По степени определенности информации:
• задачи принятия решений в условиях определенности;
• задачи принятия решений в условиях вероятностной определенности (в условиях риска);
• задачи принятия решений в условиях неопределенности.
2. Использование эксперимента для получения информации:
• задачи принятия решений по априорным данным;
• задачи принятия решений по апостериорным данным.
3. Количество целей:
• одноцелевые задачи принятия решений;
• многоцелевые задачи принятия решений;
4. Количество лиц, принимающих решение:
• индивидуальные задачи принятия решений;
• групповые задачи принятия решений.
5. Содержание решений:
• экономические задачи принятия решений;
• политические задачи принятия решений;
• военные задачи принятия решений;
• другие виды.
6. Значимость и длительность действия решений:
• долговременные задачи принятия решений;
• среднесрочные задачи принятия решений;
• краткосрочные задачи принятия решений.
Задачи принятия решений отличаются большим многообразием,
классифицировать их можно по различным признакам, характеризующим количество и качество доступной информации. В общем случае задачи принятия решений можно представить следующим набором информации [23]:

<Т, A, К, X, F, G, D>,

1.2. Классификация задач принятия решений...
9

где Т — постановка задачи (например, выбрать лучшую альтернативу
или упорядочить весь набор);
А — множество допустимых альтернативных вариантов;
К — множество критериев выбора;
Х — множество методов измерения предпочтений (например, использование различных шкал);
F — отображение множества допустимых альтернатив в множество критериальных оценок (исходы);
G — система предпочтений эксперта;
D — решающее правило, отражающее систему предпочтений.
Любой из элементов этого набора может служить классификационным признаком принятия решений.
Рассмотрим традиционные классификации.
1. По виду отображения F. Отображение множеств А и К может
иметь детерминированный характер, вероятностный или неопределенный вид, в соответствии с которым задачи принятия решений
можно разделить на задачи в условиях риска и задачи в условиях неопределенности.
2. Мощность множества К. Множество критериев выбора может
содержать один элемент или несколько. В соответствии с этим задачи
принятия решений можно разделить на задачи со скалярным критерием и задачи с векторным критерием (многокритериальное принятие решений).
3. Тип системы G. Предпочтения могут формироваться одним лицом или коллективом, в зависимости от этого задачи принятия решений можно классифицировать на задачи индивидуального принятия
решений и задачи коллективного принятия решений.
Задачи принятия решений (ЗПР) в условиях определенности.
К этому классу относятся задачи, для решения которых имеется достаточная и достоверная количественная информация. В этом случае с
успехом применяются методы математического программирования,
суть которых состоит в нахождении оптимальных решений на базе
математической модели реального объекта. Основные условия применимости методов математического программирования следующие.
1. Задача должна быть хорошо формализована, т. е. имеется адекватная математическая модель реального объекта.
2. Существует некоторая единственная целевая функция (критерий оптимизации), позволяющая судить о качестве рассматриваемых
альтернативных вариантов.

10
Глава 1. Общее описание задач прнятия решений