- •Математические методы системного анализа и теория принятия решений Методическое пособие
- •1. Теория принятия решений 4
- •2. Линейное программирование 9
- •3. Нелинейное программирование 42
- •4. Игровые методы обоснования решений 51
- •5. Задачи распознавания образов 62
- •Предисловие
- •1. Теория принятия решений
- •1.1. Задачи, связанные с принятием решений Проблема оптимальности.
- •Основные понятия и принципы исследования операций.
- •Примеры задач исследования операций.
- •1.2. Математические модели операций Искусство моделирования.
- •1.3. Разновидности задач исследования операций и подходов к их решению Прямые и обратные задачи исследования операций.
- •Пример выбора решения при определенности: линейное программирование.
- •Проблема выбора решений в условиях неопределенности.
- •Выбор решения по многим критериям.
- •«Системный подход».
- •2. Линейное программирование
- •2.1. Краткое представление о математическом программировании Предмет математического программирования.
- •Краткая классификация методов математического программирования.
- •2.2. Примеры экономических задач линейного программирования Понятие линейного программирования.
- •Задача о наилучшем использовании ресурсов.
- •Задача о выборе оптимальных технологий.
- •Задача о смесях.
- •Задача о раскрое материалов.
- •Транспортная задача.
- •2.3. Линейные векторные пространства Основные понятия линейного векторного пространства.
- •Решение систем линейных уравнений методом Гаусса.
- •Реализация метода исключения неизвестных в среде Excel.
- •Различные схемы реализации метода Гаусса.
- •Опорные решения системы линейных уравнений.
- •2.4. Формы записи задачи линейного программирования Основные виды записи злп.
- •Каноническая форма представления задачи линейного программирования.
- •Переход к канонической форме.
- •2.5. Геометрическая интерпретация задачи линейного программирования Определение выпуклой области.
- •Геометрическая интерпретация.
- •2.6. Свойства решений задачи линейного программирования Свойства основной задачи линейного программирования.
- •Графический метод решения задачи линейного программирования.
- •2.7. Симплексный метод Идея симплекс-метода.
- •Теоретические обоснования симплекс-метода.
- •Переход к нехудшему опорному плану.
- •Зацикливание.
- •Алгоритм симплекс-метода.
- •2.8. Двойственность в линейном программировании Прямая и двойственная задача.
- •Связь между решениями прямой и двойственной задач.
- •Геометрическая интерпретация двойственных задач.
- •2.9. Метод искусственного базиса Идея и реализация метода искусственного базиса.
- •3. Нелинейное программирование
- •3.1. Общая задача нелинейного программирования Постановка задачи.
- •Примеры задач нелинейного программирования (экономические).
- •Геометрическая интерпретация задачи нелинейного программирования.
- •3.2. Выпуклое программирование Постановка задачи выпуклого программирования.
- •3.3. Классические методы оптимизации Метод прямого перебора.
- •Классический метод дифференциальных исчислений.
- •3.4. Метод множителей лагранжа
- •3.5. Градиентные методы решения задач нелинейного программирования Общая идея методов.
- •Метод Франка-Вулфа.
- •Метод штрафных функций.
- •4. Игровые методы обоснования решений
- •4.1. Предмет и задачи теории игр Основные понятия.
- •Классификация выборов решений.
- •Антагонистические матричные игры.
- •Чистые и смешанные стратегии и их свойства.
- •4.2. Методы решения конечных игр Упрощение матричной игры.
- •Решение матричной игры размерностью 22.
- •Графическое решение матричной игры.
- •Сведение задач теории игр к задачам линейного программирования.
- •4.3. Задачи теории статистических решений Игры с природой.
- •Критерии принятия решений.
- •5. Задачи распознавания образов
- •5.1. Общая постановка задачи распознавания образов и их классификация Проблема распознавания.
- •Обсуждение задачи опознавания.
- •Язык распознавания образов.
- •Априорные предположения — это записанные специальным образом, накопленные знания специалистов.
- •Общая постановка задачи.
- •Геометрическая интерпретация задачи распознавания.
- •Классификация задач распознавания.
- •5.2. Подготовка и анализ исходных данных Общая схема решения задачи.
- •Общая схема постановки и решения задачи Анализ данных с целью выбора постановки и метода решения
- •5.3. Методы опознавания образов Основные этапы процесса опознавания образов.
- •Методы создания системы признаков.
- •Признаковое пространство.
- •Сокращение размерности исходного описания.
- •Методы построения решающего правила.
- •5.4. Меры и метрики Понятие о сходстве.
- •Меры сходства и метрики.
- •Примеры функций мер сходства.
- •5.5. Детерминированно-статистический подход к познаванию образов Основные этапы детерминированно-статистического подхода.
- •Получение исходного описания.
- •Создание системы признаков.
- •Сокращение размерности исходного описания.
- •Нахождение решающего правила (метод эталонов).
- •Коррекция решающего правила.
- •5.6. Детерминированный метод построения решающего правила (метод эталонов) Идея метода эталонов.
- •Минимизация числа эталонов.
- •Габаритные эталоны.
- •Применение метода эталонов к частично пересекающимся образам.
- •Дополнительная минимизация числа признаков.
- •Квадратичный дискриминантный анализ.
- •Распознавание с отказами.
- •5.8. Алгоритм голотип-1 Назначение
- •Постановка задачи
- •Метод решения задачи.
- •Условия применимости.
- •Условия применимости.
- •5.10. Алгоритм направление опробования Назначение
- •Постановка задачи.
- •Метод решения задачи.
- •Условия применимости.
- •Транспортная задача Математическая постановка.
- •Постановка задачи.
- •Теоретическое введение.
- •Методы нахождения опорного плана транспортной задачи.
- •Определение оптимального плана транспортной задачи.
- •Заключение.
- •Целочисленное программирование Постановки задач, приводящие к требованию целочисленности.
- •Постановка задачи.
- •Методы отсечения.
- •Алгоритм Гомори.
- •Первый алгоритм р. Гомори решения полностью целочисленных задач.
- •Приближенные методы.
- •Заключение.
- •Параметрическое программирование Введение.
- •Формулировка задачи.
- •Теоретическая часть.
- •Общая постановка задачи.
- •Решение задачи.
- •Геометрическая интерпретация задачи.
- •Общая постановка задачи.
- •Решение задачи.
- •Геометрическая интерпретация задачи
- •Постановка задачи.
- •Решение.
- •Геометрическое решение.
- •Решение задачи симплекс-методом.
- •Результат.
- •Некооперативные игры n лиц с ненулевой суммой Введение.
- •Теоретическая часть.
- •Постановка и решение задачи.
- •Заключение.
- •Cписок литературы
Метод решения задачи.
Рассмотрим некоторую совокупность объектов , каждый объект описан набором свойств . Аналогично алгоритму Голотип-1 вычисляется матрица мер сходства по всему набору свойств и разобьем все объекты на компоненты связности, выбрав за порог () средн.., либо среднюю максимальную меру сходства. Эти компоненты связности по числу входящих в них объектов разобьем на две группы: малочисленные и многочисленные (малочисленными называются такие компоненты связности. число объектов в которых не превосходит некоторую величину ; в частности ). Голотипом является объект, который в среднем больше всего похож на остальные объекты данной компоненты. В каждой из малочисленных компонент определим голотип и для каждого голотипа вычислим коэффициент типичности
,
где ; — число компонент компонент связности.
Упорядочим все голотипы , по возрастанию величины и разобьем на три типа: краевые, центральные и срединные. При этом краевыми называются такие компоненты связности, голотипы которых занимают первые мест () в упорядоченной последовательности. Иначе говоря, краевыми компонентами связности являются самые удаленные компоненты, центральными компонентами связности являются компоненты, голотипы которых занимают последние мест в упорядоченной последовательности, а срединными компонентами связности являются такие компоненты, голотипы которых занимают остальные мест в упорядоченной последовательности. Идея данного алгоритма заключается в построении некоторой стратегии, позволяющей последовательно выбирать участки для опробования. При этом строятся три чистых стратегии и одна смешанная.
Первая чистая стратегия заключается в рассмотрении самых нетипичных голотипов (голотипов, отвечающих краевым компонентам связности). В первую очередь выбирается для опробования голотип с минимальным коэффициентом типичности, затем голотип, стоящий рядом с ним и т. д.
Вторая чистая стратегия заключается в рассмотрении самых типичных голотипов. В этом случае в первую очередь выбирается для опробования голотип с максимальным коэффициентом типичности, затем голотип, стоящий рядом с ним в упорядоченной последовательности и т. д.
Третья чистая стратегия заключается в рассмотрении голотипов, отвечающих срединным компонентам связности. В этом случае в первую очередь опробовается голотип, типичность которого наиболее близка к средней типичности между между голотипами. Затем голотип, стоящий по типичности рядом с ним и т. д.
Смешанная стратегия заключается в выборе голотипов для опробования следующим образом. В первую очередь выбирается самый нетипичный голотип, затем самый типичный, затем первый из срединных голотипов, затем снова нетипипичный и т. д.
Условия применимости.
ТОС должна быть без пропусков; свойства — арифметические, логические 1-го и 2-го рода.
П р и м е р. В некотором районе поиска выделены 30 участков, в которых, по предположениям геологов, может быть найдена нефть. Но количество участков, относящихся к месторождениям, значительно меньше пустых участков. Необходимо опробовать участки с целью отыскания одного или нескольких, содержащих нефть.
Р е ш е н и е. В некотором множестве выделена совокупность перспективных объектов, которые предстоит опробовать с целью отыскания объекта нужного значения. Для данной задачи априорные предположения будут иметь следующий вид:
1) , т. е. количество полезных объектов намного меньше, чем пустых;
2) , т. е. полезные объекты значительно отличаются от пустых;
3) , т. е. полезные участки схожи между собой.
Задана ТОС (табл. 14), в которой на каждом из тридцати объектов измерено по два косвенных свойства. Необходимо выделить несколько объектов таким образом, чтобы количество опробований сводилось к минимуму.
табл. 14
N |
|
N |
||||
1 |
2 |
67.78 |
|
16 |
3.95 |
49.79 |
2 |
3.07 |
7.14 |
|
17 |
2.03 |
40.27 |
3 |
3.37 |
85.75 |
|
18 |
2.88 |
87.31 |
4 |
3.35 |
35.56 |
|
19 |
2.98 |
62.43 |
5 |
4.58 |
51.95 |
|
20 |
2.49 |
23.48 |
6 |
2 |
20 |
|
21 |
3.73 |
25.74 |
7 |
2.16 |
34.81 |
|
22 |
4.61 |
78.64 |
8 |
3.24 |
67.04 |
|
23 |
5 |
99 |
9 |
3.42 |
89.72 |
|
24 |
3.06 |
24.28 |
10 |
3.29 |
72.52 |
|
25 |
3.17 |
76.12 |
11 |
4.99 |
99 |
|
26 |
3.62 |
27.19 |
12 |
5 |
100 |
|
27 |
4.68 |
24.33 |
13 |
2.18 |
7 |
|
28 |
2.54 |
3 |
14 |
2.62 |
5.77 |
|
29 |
3.49 |
22.10 |
15 |
4.15 |
23.55 |
|
30 |
4.61 |
42.27 |
Вычисляются матрицы мер сходства по каждому свойству, общая матрица мер сходства, выбирается порог и строится просеянная общая матрица мер сходства. Все эти вычисления производятся по тем же формулам, что и в алгоритме Голотип-1. В нашем примере порог = 0.85.
Разбиваем объекты на однородные группы (табл.15).
табл.15
Группа 1 |
|
Группа 2 |
|
Группа 3 |
|
Группа 4 |
|
Группа 5 |
|
Группа 6 |
При наших априорных предположениях нам необходимо оставить малочисленные группы и во всех полученных группах найти голотипы. Малочисленными считаются группы, в которых содержится не более трех объектов. Голотипы находятся также как в алгоритме Голотип-1. У нас четыре малочисленные группы — Группа 2, Группа 4, Группа 5, Группа 6 и голотипами в этих группах соответственно являются объекты — , , , .
Находим меры сходства наших голотипов между собой (табл. 16).
табл. 16
|
||||
1 |
0.34 |
0.58 |
0.51 |
|
0.34 |
1 |
0.57 |
0.83 |
|
0.58 |
0.57 |
1 |
0.74 |
|
0.51 |
0.83 |
0.74 |
1 |
Находим среднюю меру сходства для каждого данного объекта с другими (табл. 17) и упорядочиваем (табл. 18).
табл. 17 табл. 18
0.6076 |
|
0.77 |
||
0.686 |
|
0.7239 |
||
0.7239 |
|
0.686 |
||
0.77 |
|
0.6076 |
При решении данной задачи с помощью алгоритма Направление опробования мы получили, что наиболее перспективным является участок .
Геологам мы посоветуем разрабатывать четыре участка, причем в таком порядке: , , , .
5.11. АЛГОРИТМ ЭНТРОПИЯ
Назначение
— решение задач распознавания на образов, где , причем для каждого объекта формируется свое решающее правило.
Постановка задачи.
В исходных данных, представленных в виде ТОС, присутствуют представители всех образов. Для каждого объекта указана его принадлежность к образу. В процессе распознавания определяется принадлежность объектов экзамена к одному из образов.
Метод решения задачи.
Этот метод основан на том, что для каждого объекта формируется свое решающее правило, для чего вокруг каждого объекта экзамена описывается система концентрических сфер. Далее рассматриваются только те из них, в которые попадает достаточно много объектов обучения. Для каждой из этих сфер определяется функция энтропии, характеризующая преобладание точек одного образа из образов в этой сфере. Результат определяется по той сфере, где значение функции оптимально. Точка экзамена относится к тому классу, который в этой сфере преобладает.
Рассмотрим данный алгоритм более подробно. На первом этапе необходимо вычислить матрицы мер сходства по каждому свойству, а затем и общую матрицу мер сходства . Из общей матрицы мер сходства выбирается максимальная и минимальная меры сходства. На следующем этапе введем некоторый шаг
,
где — заданное нами постоянное число сфер.
Вычисляется мера сходства для каждого объекта экзамена с каждым объектом МО . Затем выбираем все объекты, для которых мера сходства с объектами МО удовлетворяют условию
, 0,1...
В результате получаем набор вложенных сфер (концентрических). Для каждой из этих сфер мы вычисляем энтропию
,
где — число объектов -го образа, попавших в -ую сферу;
— число объектов, попавших в -ую сферу.
Из всех полученных энтропий выбираем минимальную . Затем находим номер сферы с минимальной энтропией . Эта сфера, в которой объектов одного образа намного больше объектов другого образа, т. е. .
Последним этапом решения является распознавание. Распознавание производится при помощи правила Байеса. Объект будет отнесен к -му образу, если
,
где — число объектов -го образа в -ой сфере,
— общее число объектов -го образа,
— число объектов -го образа в -ой сфере,
— общее число объектов -го образа.
Иначе, если
,
то объект будет отнесен к -му образу.
П р и м е р. Задана ТОС (табл. 19), в которой имеются объекты, на которых измерены прямые и косвенные свойства (МО) и объекты, на которых измерены только косвенные свойства (МЭ). Часть объектов МО относятся к 1-му образу, часть ко 1-му образу. Необходимо объекты МЭ расклассифицировать по образам.
Р е ш е н и е
табл. 19
|
Материал обучения |
|
|
|
Материал экзамена |
|
||
N |
Образ |
|
N |
Образ |
||||
1 |
285 |
68.8 |
1 |
|
11 |
150 |
87.2 |
0 |
2 |
243 |
58.5 |
1 |
|
12 |
290 |
87 |
0 |
3 |
202 |
51.2 |
1 |
|
13 |
110 |
44 |
0 |
4 |
132 |
80 |
1 |
|
|
|
|
|
5 |
146 |
69.3 |
1 |
|
|
|
|
|
6 |
245 |
62 |
2 |
|
|
|
|
|
7 |
235 |
87.2 |
2 |
|
|
|
|
|
8 |
164 |
68 |
2 |
|
|
|
|
|
9 |
136 |
64.3 |
2 |
|
|
|
|
|
10 |
225 |
44 |
2 |
|
|
|
|
|
1. Находим экстремальные разности
Для свойства : 153.1; Для свойства : 43.2.
|
|
2. Находим матрицы мер сходства по каждому свойству, а затем вычисляем общую матрицу мер сходства (табл. 20).
табл. 20
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
1 |
1 |
0.74 |
0.53 |
0.37 |
0.54 |
0.79 |
0.62 |
0.6 |
0.46 |
0.52 |
2 |
0.74 |
1 |
0.78 |
0.39 |
0.56 |
0.95 |
0.64 |
0.63 |
0.58 |
0.77 |
3 |
0.53 |
0.78 |
1 |
0.44 |
0.61 |
0.73 |
0.48 |
0.68 |
0.63 |
0.84 |
4 |
0.37 |
0.39 |
0.44 |
1 |
0.83 |
0.42 |
0.58 |
0.76 |
0.8 |
0.28 |
5 |
0.54 |
0.56 |
0.61 |
0.83 |
1 |
0.59 |
0.50 |
0.92 |
0.91 |
0.45 |
6 |
0.79 |
0.95 |
0.73 |
0.42 |
0.59 |
1 |
0.68 |
0.67 |
0.62 |
0.73 |
7 |
0.62 |
0.64 |
0.48 |
0.58 |
0.50 |
0.68 |
1 |
0.55 |
0.41 |
0.47 |
8 |
0.6 |
0.63 |
0.68 |
0.76 |
0.92 |
0.67 |
0.55 |
1 |
0.86 |
0.52 |
9 |
0.46 |
0.58 |
0.63 |
0.80 |
0.91 |
0.62 |
0.41 |
0.86 |
1 |
0.47 |
10 |
0.52 |
0.77 |
0.84 |
0.28 |
0.45 |
0.73 |
0.47 |
0.52 |
0.47 |
1 |
3. Выбираем максимальную и минимальную меры сходства:
Максимальная 0.95,
Минимальная 0.28.
Постоянную задаем равную 3 и вычисляем шаг: =0.24.
4. Вычисляем для каждого объекта экзамена энтропию, отыскиваем минимальную энтропию и производим распознавание:
Для 1-го объекта МЭ:
|
1 |
|||
1 |
0.35 |
|
|
1 |
2 |
0.37 |
|
|
1 |
3 |
0.41 |
|
1 |
1 |
4 |
0.86 |
1 |
1 |
1 |
5 |
0.78 |
1 |
1 |
1 |
6 |
0.4 |
|
1 |
1 |
7 |
0.72 |
1 |
1 |
1 |
8 |
0.73 |
1 |
1 |
1 |
9 |
0.69 |
1 |
1 |
1 |
10 |
0.26 |
|
|
1 |
|
Энтропия |
0.292 |
0.297 |
0.301 |
, , значит, объект 1 принадлежит ко второму образу.
Для 2-го объекта МЭ:
|
2 |
|||
1 |
0.7707 |
1 |
1 |
1 |
2 |
0.513 |
|
1 |
1 |
3 |
0.2959 |
|
|
1 |
4 |
0.4003 |
|
1 |
1 |
5 |
0.3216 |
|
|
1 |
6 |
0.5614 |
|
1 |
1 |
7 |
0.8204 |
1 |
1 |
1 |
8 |
0.3673 |
|
|
1 |
9 |
0.232 |
|
|
1 |
10 |
0.2877 |
|
|
1 |
|
Энтропия |
0.301 |
0.292 |
0.301 |
, , значит, объект 2 принадлежит к первому образу.
Для 1-го объекта МЭ:
|
3 |
|||
1 |
0.1414 |
|
|
1 |
2 |
0.3991 |
|
1 |
1 |
3 |
0.6162 |
|
1 |
1 |
4 |
0.5118 |
|
1 |
1 |
5 |
0.5906 |
|
1 |
1 |
6 |
0.3508 |
|
|
1 |
7 |
0.0918 |
|
|
|
8 |
0.5449 |
|
1 |
1 |
9 |
0.6801 |
1 |
1 |
1 |
10 |
0.6244 |
|
1 |
1 |
|
Энтропия |
0 |
0.297 |
0.298 |
, , значит, объект 3 относится ко второму образу.
В результате решения данной задачи при помощи алгоритма Энтропия получили следующие результаты:
|
N |
Образ |
||
|
11 |
150 |
87.2 |
2 |
|
12 |
290 |
87 |
1 |
|
13 |
110 |
44 |
2 |
П р и л о ж е н и е 1
( Из курсового проекта студенток 216 группы Прохоровой Ю.В. и Охотниковой Л.Н.)