Основы теории принятия решений

Министерство науки и высшего образования Российской Федерации 
Казанский национальный исследовательский 
технологический университет 
Н. Н. Зиятдинов, Т. В. Лаптева, И. В. Логинова 
ОСНОВЫ ТЕОРИИ  
ПРИНЯТИЯ РЕШЕНИЙ
Учебно-методическое пособие 
Казань 
Издательство КНИТУ 
2023 

УДК 519.816(075) 
ББК  22.18я7   
З-66 
Печатается по решению редакционно-издательского совета  
Казанского национального исследовательского технологического университета 
Рецензенты: 
д-р техн. наук, проф. Р. И. Ибятов 
д-р техн. наук, доц. С. В. Новикова 
З-66 
Зиятдинов Н. Н. 
Основы теории принятия решений : учебно-методическое пособие / 
Н. Н. Зиятдинов, Т. В. Лаптева, И. В. Логинова; Минобрнауки России, 
Казан. нац. исслед. технол. ун-т. – Казань : Изд-во КНИТУ, 2023. – 104 с. 
ISBN 978-5-7882-3352-9 
Рассмотрены используемые в системном анализе методы количественно обоснованного принятия решений, которые применяются в транспортной задаче линейного программирования, математической теории игр и динамическом программировании. Пособие содержит теоретический материал, задачи с приведенным решением, задачи для самостоятельной работы студентов, вопросы для контроля знаний. 
Предназначено для бакалавров, обучающихся по направлениям: 27.03.01 
«Стандартизация и метрология», 27.03.02 «Управление качеством», 27.03.03 «Системный анализ и управление», 27.03.05 «Инноватика», а также может быть использовано студентами других направлений, изучающими дисциплину «Системный анализ и принятие решений», для подготовки к контрольным работам, экзамену, в том числе к интернет-тестированию. 
Подготовлено на кафедре системотехники. 
УДК 519.816(075) 
ББК  22.18я7   
ISBN 978-5-7882-3352-9 
© Зиятдинов Н. Н., Лаптева Т. В., 
Логинова И. В., 2023 
© Казанский национальный исследовательский 
технологический университет, 2023 
2

СОД Е РЖА Н И Е 
Введение ............................................................................................................................................... 
4 
1. ТРАНСПОРТНАЯ ЗАДАЧА 
........................................................................................................... 
5 
1.1. Постановка транспортной задачи 
............................................................................................ 
5 
1.1.1. Формулировка и формализация транспортной задачи 
................................................... 
5 
1.1.2. Соблюдение баланса в задаче 
........................................................................................... 
7 
1.2. Методы получения допустимого базисного решения 
......................................................... 
12 
1.2.1. Метод северо-западного угла ......................................................................................... 
14 
1.2.2. Метод наименьших стоимостей ..................................................................................... 
18 
1.2.3. Метод аппроксимации Фогеля ....................................................................................... 
23 
Вопросы для контроля знаний 
...................................................................................................... 
28 
2. РЕШЕНИЕ ТРАНСПОРТНОЙ ЗАДАЧИ МЕТОДОМ ПОТЕНЦИАЛОВ ............................... 
29 
2.1. Метод потенциалов 
................................................................................................................. 
29 
2.2. Проверка оптимальности плана и перераспределение поставок с помощью метода 
потенциалов 
.................................................................................................................................... 
31 
Вопросы для контроля знаний 
...................................................................................................... 
36 
3. МАТЕМАТИЧЕСКИЕ МЕТОДЫ ПРИНЯТИЯ РЕШЕНИЙ В УСЛОВИЯХ
НЕОПРЕДЕЛЕННОСТИ 
................................................................................................................... 
37 
3.1. Математическая теория игр ................................................................................................... 
37 
3.2. Модель игры 
............................................................................................................................ 
37 
3.3. Игры в чистых стратегиях 
...................................................................................................... 
40 
3.4. Решение игр в смешанных стратегиях 
.................................................................................. 
41 
3.4.1. Игра 2х2 ............................................................................................................................ 
42 
3.4.2. Уменьшение порядка платежной матрицы ................................................................... 
44 
3.4.3. Сведение к задаче линейного программирования ........................................................ 
47 
3.5. Геометрическая интерпретация  игровых задач .................................................................. 
49 
3.6. Общая схема решения игровых задач 
................................................................................... 
54 
3.7. Игры с природой ..................................................................................................................... 
54 
3.7.1. Критерии максимизации результата .............................................................................. 
55 
3.7.2. Критерии минимизации результата ............................................................................... 
59 
Вопросы для контроля знаний 
...................................................................................................... 
61 
4. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ 
........................................................................... 
62 
4.1. Общие сведения ...................................................................................................................... 
62 
4.2. Решение задач, представленных графами ............................................................................ 
63 
4.2.1. Элементы теории графов 
................................................................................................. 
63 
4.2.2. Задача выбора транспортных маршрутов 
...................................................................... 
65 
4.2.3. Задача о кратчайшем пути .............................................................................................. 
69 
Вопросы для контроля знаний 
...................................................................................................... 
70 
5. ЛАБОРАТОРНЫЕ РАБОТЫ ........................................................................................................ 
71 
Лабораторная работа 1. ТРАНСПОРТНАЯ ЗАДАЧА ............................................................... 
71 
Задания для самостоятельной работы 
.......................................................................................... 
76 
Лабораторная работа 2. ТЕОРИЯ ИГР ........................................................................................ 
93 
Задания для самостоятельной работы 
.......................................................................................... 
94 
Лабораторная работа 3. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ 
................................ 
100 
Задания для самостоятельной работы 
........................................................................................ 
100 
Заключение ....................................................................................................................................... 
102 
Библиографический список ............................................................................................................ 
103 
3 

В В Е Д Е Н И Е 
В процессе любой сферы деятельности, будь то проектирование, 
управление техническими, экономическими или социальными системами, человек сталкивается с проблемами принятия наилучших решений при наличии нескольких альтернативных, которые сводятся 
к поиску компромисса. Цель пособия – помочь студентам овладеть 
базовыми понятиями и методами теории системного анализа и принятия решений.   
В учебно-методическом пособии рассматриваются вопросы формализации оптимизационных задач, которые сводятся к транспортной задаче линейного программирования, и основные методы ее решения. Изложены методы принятия компромиссных решений задач 
в условиях неопределенности на основе математической теории игр. 
Рассмотрены различные стратегии решения в зависимости от исходных постановок задач. Дано описание и предложены примеры применения метода динамического программирования для решения многомерных задач оптимизации путем их декомпозиции на этапы и представления в виде графов.
В первой главе рассматриваются транспортная задача, методы получения допустимого базисного решения (северо-западного угла, 
наименьших стоимостей и аппроксимации Фогеля). 
Во второй главе описан алгоритм метода потенциалов. Приведен 
пример с проверкой оптимальности плана и перераспределением поставок с помощью метода потенциалов. 
В третьей главе изложены основные понятия математической теории игр, рассмотрено решения игр в чистых и смешанных стратегиях, 
геометрическая интерпретация игр, общая схема решения игровых задач, а также вопросы принятия решения в условиях неопределенности 
на основании критериев Лапласа, Вальда, максимального оптимизма, 
Сэвиджа, Гурвица. 
В четвертой главе рассмотрен принцип оптимальности Р. Беллмана, лежащий в основе метода динамического программирования, для 
решения задач, представленных графами. 
В конце каждой главы предложены вопросы для контроля знаний. 
Теоретический материал подкреплен разбором примеров задач и заданиями для самостоятельного работы в лабораторных работах. 
4 

. Т РА Н С П О Р Т Н А Я  З АД АЧ А 
1 . 1 .  П о с т а н о в к а  т р а н с п о р т н о й  з а д а ч и 
Транспортная задача – это задача о выборе оптимального плана перевозок однородного продукта из m пунктов отправления  в n пунктов 
назначения. При этом в качестве критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки. 
Модели этого типа весьма разнообразны и предназначены для решения не только задач, связанных с транспортом (рис. 1.1). Многие задачи 
можно переформулировать как транспортные и применить методы решения к ним. 
Рис. 1.1. Задачи, относящиеся к транспортным 
1 . 1 . 1 . Ф о р м у л и р о в к а  и  ф о р м а л и з а ц и я
т р а н с п о р т н о й  з а д а ч и  
Рассмотрим транспортную задачу, в качестве критерия оптимальности которой взята минимальная стоимость перевозок всего груза. Пусть 
имеются m пунктов отправления (производства) и n пунктов назначения – 
потребители (рис. 1.2). 
5 

Рис. 1.2. Иллюстрация к транспортной задаче 
Введем обозначения: 
– запасы грузов в пунктах отправления ai , i = 1,…,m;
– потребность в грузах  в пункте назначения bj, j = 1,…,n;
– расходы на перевозку единицы продукта из i-го пункта отправления в j-й пункт назначения cij. 
Требуется найти такое количество продукта xij, доставляемого из 
i-го пункта отправления в  j-й пункт потребления, для которого стоимость 
доставки будет минимальной. 
Исходные данные транспортной задачи обычно записывают в виде 
таблицы (табл. 1.1). 
Таблица 1.1 
Исходные данные транспортной задачи 
Пункты  
Пункты назначения 
Запасы 
отправления 
 груза 
В1 
В2 
… 
Вn 
А1 
с11 
с12 
… 
с1n 
а1 
А2 
с21 
с21 
… 
с2n 
а2 
… 
… 
… 
… 
… 
… 
Аm 
сm1 
сm2 
… 
сmn 
аm 
Потребности 
b1
b2
… 
bn
В транспортной задаче с m пунктами отправления и n пунктами 
назначения количество искомых переменных  xij равно mхn, а количество 
ограничений будет m + n. 
6 

. 1 . 2 . С о б л ю д е н и е  б а л а н с а  в  з а д а ч е  
Транспортные задачи делятся на две группы: 
– закрытая модель транспортной задачи (сбалансированная); 
– открытая модель транспортной задачи. 
Закрытая модель транспортной задачи. К этому виду относятся задачи, удовлетворяющие условию баланса, означающему, что суммарные 
запасы (предложение) поставщиков точно соответствуют суммарным потребностям (спросу), т.е. ∑
𝒂𝒊= ∑
𝒃𝒋
𝒎
𝒊=𝟏
. Это условие является необхо𝒏
𝒋=𝟏
димым и достаточным  условием разрешимости транспортной задачи. 
Математическая модель сбалансированной задачи: 
1) В модели m x n поисковых переменных xij. 
2) Целевая функция – суммарные затраты на перевозку грузов: 
m
n

→
=
=
=
j
ij
ij x
c
L
i
1
1
min
 
3) Ограничения по поставщикам: 
n
ij
a
x =

i
j
=1
, 
m
i
,
1
=
 – полный вывоз груза. 
4) Ограничения по потребителям: 
m
n
j
b
x
j
ij
,
1
,
=
 – полное удовлетворение спроса, 
i
1
=
=

,
0

ij
x
   
m
i
,
1
=
, 
n
j
,
1
=
 – условие неотрицательности. 
Открытая модель транспортной задачи. В задачах с нарушением баланса возможен один из двух случаев: 
1. Есть дефицит продукта, т. е. ∑𝑎𝑖< ∑𝑏
𝑗. Условие означает, 
что груз из пунктов отправления будет вывезен полностью, но спрос потребителей на продукцию удовлетворяется не полностью.  
Ограничения по поставщикам задаем в виде равенств, а ограничения 
по потребителям – в виде неравенств. 
Математическая модель задачи: 
m
n

=
=
i
j
ij
ijx
c
1
1
→ min. 
7 

Ограничения: 
n
ij
a
x =

– по поставщикам:
i
j
=1
 
,
,
1 m
i =
; 
m
ij
,
1
,
– по потребителям:     
n
j
b
x
j
=
 
i
1
=


,
0

ij
x
   
m
i
,
1
=
  , 
n
j
,
1
=
. 
2. Есть избыток продукта, т. е.  



j
i
b
a
. Условие означает, что  
груз из пунктов отправления будет вывезен не полностью, но спрос потребителей на продукцию удовлетворяется полностью.  
Ограничения по поставщикам задаем в виде неравенств, а ограничения по потребителям –  в виде равенств. 
Математическая модель задачи: 
∑
∑
𝑐𝑖𝑗𝑥𝑖𝑗
𝑚
𝑖=1
→ min 
𝑛
𝑗=1
Ограничения: 
n
ij
a
x 

– по поставщикам:
i
j
=1
 
,
,
1 m
i =
    
m
=
=

ij
,
1
,
– по потребителям: 
n
j
b
x
j
=
 
 
     
i
1
,
0

ij
x
   
m
i
,
1
=
  , 
n
j
,
1
=
. 
Примечание. Если не нужно доставлять груз  в  j-й пункт назначения, 
то в целевой функции удельные стоимости перевозок в этот пункт назначения задаются большим числом, на 2–3 порядка больше самой большой 
стоимости в таблице. После получения решения в формуле целевой функции надо восстановить настоящие значения удельных стоимостей перевозок для этого пункта назначения. 
Если безразлично, какой поставщик и в каком количестве полностью не реализовал продукцию (случай 1) либо безразлично, спрос какого потребителя и в каком количестве не удовлетворен (случай 2), то 
такие задачи легко приводятся к закрытой модели. 
Пример транспортной задачи. Три цементных завода ежедневно отправляют на три стройплощадки декоративный цемент. 
  
8 

     Заводы 
Стройплощадки 
Запасы 
В1
В2
В3 
А1
6 
5 
4 
55
А2 
1 
2 
4 
35
А3
3 
2 
3 
60
Потребности 
35 
25
90
     150
150 
Найти такой план доставки груза, чтобы суммарная стоимость перевозок была минимальной при условии, что пропускная способность  
от 2-го завода до 1-й стройплощадки составляет  не более 15 т груза, 
а маршрут от 1-го завода до 3-й стройплощадки временно закрыт. 
Математическая модель: 
так как 
i
a =
i
b = 150, то имеем закрытую модель. 
Целевая функция: 
6x11 +5x12 +1000 x13 +x21 +2x22 +4x23 +3x31 +2x32 +3x33 →  min 
Ограничения по поставщикам: 
x11 + x12 + x13 = 55, 
x21 + x22 + x23 = 35, 
x31 + x32 + x33 = 60. 
Ограничения по потребителям: 
x11 + x21 + x31 = 35, 
x12 + x22 + x32 = 25, 
x13 + x23 + x33 = 90. 
Ограничение по пропускной способности: 
х21 ≤ 15. 
Условие неотрицательности: 
,
0

ij
x
m
i
,
1
=
, 
n
j
,
1
=
.
9 

Пример задачи о назначениях (сводится к транспортной задаче). 
Известно большое число задач, сводящихся к транспортной задаче с дополнительным условием целочисленности решения. В качестве примера 
рассмотрим так называемую задачу о назначениях. 
Пусть требуется выполнить n различных работ и имеется n механизмов (машин) для их выполнения, причем каждый механизм может использоваться при любом типе работ. Производительность каждого механизма на различных работах может быть различной.   
Обозначим через 𝑐𝑖𝑗 производительность i-го механизма на
j-й работе. Пусть каждый механизм может выполнять только одну какую-либо работу.
Задача заключается в таком распределении механизмов по работам, при котором суммарная производительность максимальна. 
Построим математическую модель этой задачи. Сопоставим каждый из возможных вариантов распределения машин по работам с набором значений неизвестных 
ij
x , относительно которых условимся, что  
𝑥𝑖𝑗= { 1,если 𝑖-й механизм назначается на 𝑗-ю работу 
0, если 𝑖-й механизм назначается не на 𝑗-ю работу 
Для любого варианта среди чисел 
ij
x
должно быть точно n единиц, 
причем должны выполняться следующие условия: 
∑
𝑥𝑖𝑗
𝑛
𝑗=1
= 1  (𝑖= 1, . . . , 𝑛) – каждый механизм назначается на одну работу, 
∑
𝑥𝑖𝑗
𝑛
𝑖=1
= 1  (𝑗 = 1, . . . , 𝑛) – на каждую работу назначается один механизм. 
Суммарная производительность при данном варианте назначения 
машин на работы выразится суммой 
∑
∑
𝑐𝑖𝑗𝑥𝑖𝑗
𝑛
𝑖=1
. 
𝑛
𝑗=1
Таким образом, математическая модель задачи о назначениях будет иметь такой вид: 
𝑛
𝑛
→𝑚𝑎𝑥
𝐹= ∑∑𝑐𝑖𝑗𝑥𝑖𝑗
𝑖=1
𝑗=1
10