- •Математические методы системного анализа и теория принятия решений Методическое пособие
- •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-го и 2-го рода.
П р и м е р. Имеется некоторая исходная ТОС. Определить для каких объектов МЭ данный МО является представительным, а для каких нет.
Р е ш е н и е. Исходными данными является ТОС (табл. 3). На каждом объекте МО и МЭ измерены два свойства: и . В МО представлены объекты только одного образа.
табл. 3
|
Материал обучения |
|
|
|
Материал экзамена |
|
||
N |
Образ |
|
N |
Образ |
||||
1 |
126 |
2.91 |
1 |
|
1 |
140 |
3.20 |
0 |
2 |
138 |
4.50 |
1 |
|
2 |
135 |
4.38 |
0 |
3 |
182 |
2.16 |
1 |
|
3 |
115 |
5.99 |
0 |
4 |
196 |
2.30 |
1 |
|
4 |
187 |
4.54 |
0 |
5 |
152 |
4.70 |
1 |
|
5 |
169 |
5.39 |
0 |
6 |
193 |
4.22 |
1 |
|
6 |
141 |
2.44 |
0 |
7 |
113 |
5.23 |
1 |
|
7 |
201 |
3.04 |
0 |
8 |
154 |
4.06 |
1 |
|
8 |
112 |
3.18 |
0 |
9 |
124 |
5.65 |
1 |
|
9 |
129 |
4.92 |
0 |
10 |
179 |
2.72 |
1 |
|
10 |
119 |
3.96 |
0 |
11 |
174 |
1.41 |
1 |
|
11 |
205 |
2.58 |
0 |
12 |
145 |
4.62 |
1 |
|
12 |
139 |
3.23 |
0 |
13 |
108 |
5.26 |
1 |
|
13 |
165 |
4.00 |
0 |
14 |
117 |
4.92 |
1 |
|
14 |
204 |
5.30 |
0 |
15 |
145 |
3.28 |
1 |
|
15 |
187 |
4.67 |
0 |
16 |
115 |
3.27 |
1 |
|
|
|
|
|
17 |
149 |
4.76 |
1 |
|
|
|
|
|
18 |
168 |
2.79 |
1 |
|
|
|
|
|
По формуле (5.2) находим экстремальную разницу для каждого свойства МО:
Для свойства : 88.3;
Для свойства : 4.25.
Вычисляем матрицы мер сходства по каждому свойству по формуле (5.3) или (5.4). Выбираем — информативный вес каждого свойства, в данном случае 0.5. Вычисляем общую матрицу мер сходства по формуле (5.5):
Вычисляем порог: по формуле (5.6), но в данном примере для порога выбираем среднюю меру сходства . И разбиваем объекты на однородные группы. Для того, чтобы облегчить процесс разбиения на однородные группы построим просеянную общую матрицу мер сходства
В группу 1 вошли объекты: .
Группу 2 составляют объекты: .
Группа 3 состоит из одного объекта: .
В каждой группе находим голотип и находим радиус эталона:
|
R |
Голотип |
Группа 1 |
0.62 |
|
Группа 2 |
0.53 |
|
Группа 3 |
0.46 |
Определяем, является ли данный МО представительным для представленного МЭ (табл. 6).
табл. 6
|
Материал обучения |
|
|
|
|
|
N |
F1 |
F2 |
Образ |
Гр. 1 |
Гр. 2 |
Гр. 3 |
1 |
126 |
2.91 |
1 |
+ |
+ |
+ |
2 |
138 |
4.50 |
1 |
+ |
+ |
+ |
3 |
182 |
2.16 |
1 |
+ |
+ |
+ |
4 |
196 |
2.30 |
1 |
+ |
+ |
+ |
5 |
152 |
4.70 |
1 |
+ |
+ |
+ |
6 |
193 |
4.22 |
1 |
+ |
+ |
+ |
7 |
113 |
5.23 |
1 |
+ |
+ |
+ |
8 |
154 |
4.06 |
1 |
+ |
+ |
+ |
9 |
124 |
5.65 |
1 |
+ |
+ |
+ |
10 |
179 |
2.72 |
1 |
+ |
+ |
+ |
11 |
174 |
1.41 |
1 |
+ |
+ |
+ |
12 |
145 |
4.62 |
1 |
+ |
+ |
+ |
13 |
108 |
5.26 |
1 |
+ |
+ |
+ |
14 |
117 |
4.92 |
1 |
+ |
+ |
+ |
15 |
145 |
3.28 |
1 |
+ |
+ |
+ |
16 |
115 |
3.27 |
1 |
+ |
+ |
+ |
17 |
149 |
4.76 |
1 |
+ |
+ |
+ |
18 |
168 |
2.79 |
1 |
+ |
+ |
+ |
|
|
|
|
|
|
|
|
Материал экзамена |
|
|
|
|
|
N |
F1 |
F2 |
Образ |
Гр. 1 |
Гр. 2 |
Гр. 3 |
1 |
140 |
3.20 |
0 |
+ |
+ |
+ |
2 |
135 |
4.38 |
0 |
+ |
+ |
+ |
3 |
115 |
5.99 |
0 |
+ |
+ |
+ |
4 |
187 |
4.54 |
0 |
+ |
+ |
+ |
5 |
169 |
5.39 |
0 |
+ |
+ |
+ |
6 |
141 |
2.44 |
0 |
+ |
+ |
+ |
7 |
201 |
3.04 |
0 |
+ |
+ |
+ |
8 |
112 |
3.18 |
0 |
+ |
+ |
+ |
9 |
129 |
4.92 |
0 |
+ |
+ |
+ |
10 |
119 |
3.96 |
0 |
+ |
+ |
+ |
11 |
205 |
2.58 |
0 |
+ |
+ |
+ |
12 |
139 |
3.23 |
0 |
+ |
+ |
+ |
13 |
165 |
4.00 |
0 |
+ |
+ |
+ |
14 |
204 |
5.30 |
0 |
+ |
+ |
+ |
15 |
187 |
4.67 |
0 |
+ |
+ |
+ |
При определении представительности МО для данного МЭ с помощью алгоритма Голотип-1 выяснилось, что в данной задаче МО является представительным для всех объектов МЭ.
5.9. АЛГОРИТМ ГОЛОТИП-N
Назначение
— решение задач распознавания в ситуациях, когда в МО представлены объекты образов ().
Постановка задачи.
В исходных данных, представленных в виде ТОС, присутствуют представители всех образов. Для каждого объекта указана его принадлежность к образу. В процессе распознавания определяется принадлежность объектов экзамена к одному из образов. Распознавание проводится в двух режимах: с отказом и без отказа.
Метод решения задачи.
Пусть совокупность экспериментально изученных объектов со свойствами представлена в виде таблицы «объекты-свойства»:
, ,
где — число свойств, — число объектов и для каждого объекта указана принадлежность к образу.
Свойства могут быть измерены в различных шкалах (арифметическая, логическая 1-го рода, логическая 2-го рода).
Данный алгоритм решается как алгоритм Голотип-1, но с некоторыми отличиями, которые состоят в следующем.
1. Постоянная для разбиения на компоненты связности выбирается так, чтобы связанными между собой оказались те объекты, для которых мера сходства не меньше средних мер сходства между объектами внутри образов и максимальных мер сходства между образами. По этой причине в одну компоненту связности всегда попадают только объекты, относящиеся к одному образу, т.е. компоненты связности однородны.
2. Радиусы компонент связности выбираются таким образом, чтобы в компонентах связности связи, описанные шарами, не попали объекты других образов.
Процедура экзамена проводится с отказом и без отказа. В режиме распознавания с отказом объект экзамена относится к той компоненте связности, в которую он попадает (, где — номер компоненты, — ее голотип, — ее радиус, и соответственно к тому образу, к которому относится голотип ). В режиме распознавания без отказа объект относится к той компоненте связности, к голотипу которой он оказывается ближе всего в смысле величины меры сходства, и соответственно к тому образу, к которому относится этот голотип.