- •Математические методы системного анализа и теория принятия решений Методическое пособие
- •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.3. Разновидности задач исследования операций и подходов к их решению Прямые и обратные задачи исследования операций.
Задачи исследования операций делятся на две категории: а) прямые и б) обратные. Прямые задачи отвечают на вопрос: что будет, если в заданных условиях мы примем какое-то решение? Для решения такой задачи строится математическая модель, позволяющая выразить один или несколько показателей эффективности через заданные условия и элементы решения.
Обратные задачи отвечают на вопрос: как выбрать решение для того, чтобы показатель эффективности обратился в максимум или минимум (в зависимости от конкретной задачи).
Естественно, прямые задачи проще обратных. Очевидно также, что для решения обратной задачи прежде всего надо уметь решать прямую. Если число возможных вариантов решения обратной задачи невелико, то можно попросту вычислить показатель эффективности для каждого из них, сравнить между собой полученные значения и непосредственно указать один или несколько оптимальных вариантов, для которых показатель эффективности достигает максимума (минимума). Такой способ нахождения оптимального решения называется «простым перебором». Когда число возможных вариантов решения велико, применяются методы «направленного перебора».
Пусть имеется некоторая операция Q, на успех которой мы можем в какой-то мере влиять, выбирая тем или другим способом решение x. Пусть эффективность операции характеризуется одним показателем Wmax.
Возьмем самый простой, так называемый «детерминированный» случай, когда все условия операции известны заранее, т. е. не содержат неопределенности. Тогда все факторы, от которых зависит успех операции, делятся на две группы:
1) заданные, заранее известные факторы (условия выполнения операции);
2) зависящие от нас элементы решения, образующие в своей совокупности решение x.
Пример выбора решения при определенности: линейное программирование.
В типичном виде выбор решений при определенности сводится к следующему: дано множество возможных действий и нужно выбрать одно (или все) из тех, которые дают максимум (или минимум) некоторого данного показателя.
Примером выбора решений является линейное программирование (наиболее подробно оно будет рассматриваться в следующей главе).
В качестве примера задачи линейного программирования рассмотрим задачу о диете. Пусть имеется n продуктов F1, F2,..., Fn. «Диета» предписывает суточное потребление каждого продукта: x1 единиц продукта F1,, x2 единиц продукта F2 и т. д. С каждой диетой (x1, x2, ..., xn) мы можем связать (т. е. определить для нее) содержание какого-либо данного перечня питательных веществ и элементов, которые нас интересуют, скажем белков, жиров, углеводов, железа, кальция, витамина В, витамина С и т. д. Мы замечаем, что содержание в диете (x1, x2, ..., xn), скажем, белков представляется линейным выражением
а1x1+a2x2+...+anxn,
где а1 обозначает содержание белков в единице продукта F1, a2 — содержание белков в единице продукта F2 и т. д. Очевидно, некоторые ai могут быть равны нулю, но не могут быть отрицательны. То же самое относится к xi. Медицина установила, что человеку требуется некоторое минимальное количество каждого питательного вещества, скажем а единиц белков в день. Таким образом, нужно выбирать лишь между диетами, обеспечивающими эти минимальные количества. Поэтому мы требуем, чтобы диета (x1, x2, ..., xn) удовлетворяла линейным неравенствам следующего вида:
а1x1+a2x2+...+anxnа.
Это неравенство написано только для белков; для каждого из остальных питательных веществ пишется аналогичное условие. Очевидно, эти условия можно выполнить, взяв достаточно большие количества пищи без учета стоимости; однако мы часто хотим выбрать диету так, чтобы получить минимальную стоимость — например, в госпитале, — и это представляет довольно сложную задачу. Если p1, p2, ..., pn — соответственно цены единиц продуктов F1, F2, ..., Fn, то стоимость диеты (x1, x2, ..., xn) равна
p1x1+p2x2+...+pnxn.
Итак, окончательно задача сводится к такому выбору диеты, чтобы удовлетворить требованиям питательности (линейные неравенства) при минимальной стоимости (линейное выражение для стоимости).
Общая задача линейного программирования включает в основном следующие факторы:
1) операции, каждая из которых состоит в выборе n действительных чисел (например, диеты);
2) условия осуществимости (ограничения), представляющие собой линейные неравенства и равенства, которым должны подчиняться возможные выборы (например, минимальные содержания питательных веществ);
3) связанный с каждым выбором показатель, равный взвешенному среднему всех n чисел, составляющих выбор (например, функция стоимости).
Каждой задаче линейного программирования можно поставить в соответствие некоторую игру двух лиц с нулевой суммой и наоборот, поэтому, если задача линейного программирования разрешима, то решение одной задачи всегда можно истолковать так, что оно даст решение другой.
Следует упомянуть две другие известные задачи выбора решений при определенности, тесно связанные с задачей линейного программирования. В первой, называемой задачей о распределении персонала («проблемой выбора»), предполагается, что имеется n человек и n работ. «Ценность» или «производительность» человека i на работе j по предположению известна и может быть указана числом, которое мы обозначим aij. Задача состоит в том, чтобы найти распределение индивидуумов по работам, которое дает максимум общей производительности. В той задаче множество возможных действий F состоит из всех взаимно однозначных назначений людей на работе и, следовательно, всего имеется n != таких действий. Один из способов решить задачу распределения персонала — это включить ее в задачу линейного программирования.
Вторая задача — задача о коммивояжере — по идее вполне аналогична задаче о распределении персонала, но гораздо труднее ее. Коммивояжер выезжает из столицы штата и должен посетить каждую из столиц других штатов. Каким кратчайшим путем ему нужно ехать? В этой задаче имеется 47! возможных вариантов (не 48!, потому что начальная столица задана), где любой вариант есть направленный путь, проходящий через столицу каждого штата, а показателем, связанным с каждым вариантом, является длина всего маршрута.
Обе эти задачи имеют одну особенность, которая существенно отличает их от задачи линейного программирования, а именно в них множество возможных вариантов конечно.