- •Математические методы системного анализа и теория принятия решений Методическое пособие
- •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-го рода.
П р и м е р. Независимая компания «Иванов & сын» собрала некоторые статистические данные о том, какой тип женщин наиболее тщательно следит за своей фигурой. Выявилось два основных типа женщин: женщины, которым приходится часто общаться с людьми (журналистки, манекенщицы, учительницы, врачи и т. п.) и поэтому стараются делать все возможное, чтобы быть в форме, и женщины, которые большую часть времени проводят дома или занимаются тяжелым трудом (домохозяйки, дворники, доярки и т. п.) и поэтому не особенно заботится о своей фигуре. Также оказалось, что некоторые женщины не знали к какому типу себя отнести. Перед компанией «Иванов & сын» встала задача к какому типу их отнести, если у каждого типа известны два параметра: обхват талии(см) и обхват бедер (см).
Р е ш е н и е. Задана ТОС (табл. 7), в которой имеется часть представителей каждого образа и на каждом объекте МО и МЭ измерены косвенные свойства: — обхват талии (см) и — обхват бедер (см). Объекты МО расклассифицированы по образам. Необходимо отнести объекты МЭ к одному из представленных образов.
табл. 7
|
Материал обучения |
|
|
|
Материал экзамена |
|
||
N |
Образ |
|
N |
Образ |
||||
1 |
63 |
100 |
1 |
|
11 |
58 |
86 |
0 |
2 |
62 |
98 |
1 |
|
12 |
56 |
88 |
0 |
3 |
64 |
92 |
1 |
|
13 |
63 |
103 |
0 |
4 |
70 |
102 |
1 |
|
14 |
57 |
90 |
0 |
5 |
66 |
91 |
1 |
|
15 |
65 |
91 |
0 |
6 |
55 |
80 |
2 |
|
|
|
|
|
7 |
59 |
85 |
2 |
|
|
|
|
|
8 |
60 |
90 |
2 |
|
|
|
|
|
9 |
58 |
88 |
2 |
|
|
|
|
|
10 |
57 |
84 |
2 |
|
|
|
|
|
1. Находим экстремальные разницы:
Для свойства : 15;
Для свойства : 22.
2. Находим общую матрицу мер сходства (табл. 8):
табл. 8
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
1 |
1 |
0.92 |
0.78 |
0.72 |
0.70 |
0.28 |
0.53 |
0.67 |
0.56 |
0.44 |
2 |
0.92 |
1 |
0.80 |
0.64 |
0.71 |
0.36 |
0.60 |
0.75 |
0.64 |
0.52 |
3 |
0.78 |
0.80 |
1 |
0.57 |
0.91 |
0.43 |
0.67 |
0.82 |
0.71 |
0.58 |
4 |
0.72 |
0.64 |
0.57 |
1 |
0.62 |
0.00 |
0.25 |
0.39 |
0.28 |
0.16 |
5 |
0.70 |
0.71 |
0.91 |
0.62 |
1 |
0.38 |
0.63 |
0.78 |
0.67 |
0.54 |
6 |
0.28 |
0.36 |
0.43 |
0.00 |
0.38 |
1 |
0.75 |
0.61 |
0.72 |
0.84 |
7 |
0.53 |
0.60 |
0.67 |
0.25 |
0.63 |
0.75 |
1 |
0.85 |
0.90 |
0.91 |
8 |
0.67 |
0.75 |
0.82 |
0.39 |
0.78 |
0.61 |
0.85 |
1 |
0.89 |
0.76 |
9 |
0.56 |
0.64 |
0.71 |
0.28 |
0.67 |
0.72 |
0.90 |
0.89 |
1 |
0.88 |
10 |
0.44 |
0.52 |
0.58 |
0.16 |
0.54 |
0.84 |
0.91 |
0.76 |
0.88 |
1 |
3. Вычисляем порог:
|
0.85 |
4. Объекты МО разбиваем на однородные группы. Для облегчения работы строим просеянную общую матрицу мер сходства (табл. 9).
табл. 9
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
1 |
1 |
0.92 |
|
|
|
|
|
|
|
|
2 |
0.92 |
1 |
|
|
|
|
|
|
|
|
3 |
|
|
1 |
|
0.91 |
|
|
|
|
|
4 |
|
|
|
1 |
|
|
|
|
|
|
5 |
|
|
0.91 |
|
1 |
|
|
|
|
|
6 |
|
|
|
|
|
1 |
|
|
|
|
7 |
|
|
|
|
|
|
1 |
0.85 |
0.90 |
0.91 |
8 |
|
|
|
|
|
|
0.85 |
1 |
0.89 |
|
9 |
|
|
|
|
|
|
0.90 |
0.89 |
1 |
0.88 |
10 |
|
|
|
|
|
|
0.91 |
|
0.88 |
1 |
В результате разбиения было получено пять однородных групп, для которых были вычислены голотипы (Г) и радиусы (R) (табл. 10).
табл. 10
Образ |
Группа |
Объекты |
Г |
R |
1 |
1 |
, |
0.92 |
|
|
2 |
, |
0.91 |
|
|
3 |
1 |
||
2 |
4 |
1 |
||
|
5 |
, , , |
0.88 |
5. Прежде, чем приступить к распознаванию, составим таблицу мер сходства объектов МЭ со всеми голотипами (табл. 11).
табл. 11
|
|||||
11 |
0.52 |
0.66 |
0.24 |
0.76 |
0.95 |
12 |
0.49 |
0.64 |
0.22 |
0.78 |
0.93 |
13 |
0.93 |
0.72 |
0.74 |
0.21 |
0.49 |
14 |
0.57 |
0.72 |
0.29 |
0.71 |
0.92 |
15 |
0.73 |
0.94 |
0.58 |
0.42 |
0.7 |
6. Проверяем МО на наличие ошибок 1-го и 2-го рода и распознаем МЭ (табл. 12).
табл. 12
|
Образ |
Гр. 1 |
Гр. 2 |
Гр. 3 |
Гр. 4 |
Гр. 5 |
||
1 |
63 |
100 |
1 |
* |
|
|
|
|
2 |
62 |
98 |
1 |
* |
|
|
|
|
3 |
64 |
92 |
1 |
|
* |
|
|
|
4 |
70 |
102 |
1 |
|
|
* |
|
|
5 |
66 |
91 |
1 |
|
* |
|
|
|
6 |
55 |
80 |
2 |
|
|
|
* |
|
7 |
59 |
85 |
2 |
|
|
|
|
* |
8 |
60 |
90 |
2 |
|
|
|
|
* |
9 |
58 |
88 |
2 |
|
|
|
|
* |
10 |
57 |
84 |
2 |
|
|
|
|
* |
11 |
58 |
86 |
2 |
|
|
|
|
* |
12 |
56 |
88 |
2 |
|
|
|
|
* |
13 |
63 |
103 |
1 |
* |
|
|
|
|
14 |
57 |
90 |
2 |
|
|
|
|
* |
15 |
65 |
91 |
1 |
|
* |
|
|
|
При решении данной задачи алгоритмом Голотип-N МЭ был расклассифицирован по образам. К 1-му образу было отнесено два объекта МЭ: и , а ко 2-му образу — три объекта МЭ: , и .
Другими словами, тех женщин, которые не знали к какому типу себя отнести, мы по двум критериям распределили по группам, с которыми они наиболее схожи (в смысле схожести параметров). И это не противоречит ожидаемым результатам, т. к. в наше трудное время не многие женщины (особенно работающие) могут уделить время для занятия физкультурой или еще чем-нибудь, чтобы быть в форме.