- •Математические методы системного анализа и теория принятия решений Методическое пособие
- •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писок литературы
Результат.
Если , то оптимальным планом является . То есть, при данных значениях согласно оптимальному плану следует производить 11 изделий вида B и не производить изделия A. Причем общая стоимость производимой продукции максимальна: .
Если , то оптимальным планом является , причем .
Если , то оптимальным планом является , причем .
П р и л о ж е н и е 4
(из курсового проекта студентки 211 группы Кирьяновой Ирины)
Некооперативные игры n лиц с ненулевой суммой Введение.
Игра с нестрогим соперничеством, как показывает ее название, есть игра, в которой нет строгого соперничества, потому что имеется по меньшей мере одна пара лотерей и по исходам игры, такая, что один игрок предпочитает , а не , а другой игрок не предпочитает лотерею лотерее . Для таких игр нельзя выбрать функции полезности игроков так, чтобы их сумма равнялась нулю; поэтому мы можем применять термины «игры с нестрогим соперничеством» и «игры с ненулевой суммой» один вместо другого. Большинство экономических, политических и военных столкновений интересов можно представить в форме игр лишь в том случае, если признать присущее им нестрогое соперничество.
Можно было бы простодушно предположить, что наличие некоторого согласия между игроками упростит анализ; конечно, в случае, когда имеется полное согласие, анализ тривиален. Но в общем случае он отнюдь не становится проще! Частичное согласие запутывает вопрос до такой степени, что для этих игр не было построено такой изящной и связной теории, как для игр со строгим соперничеством.
В играх со строгим соперничеством игроки не могут достигнуть обоюдной выгоды посредством какого-либо сотрудничества; напротив, в играх с нестрогим соперничеством такой обоюдный выигрыш всегда возможен. Под кооперативной игрой подразумевается игра, в которой игроки имеют полную свободу сообщения до игры для составления взаимно обязывающих соглашений. В некооперативной игре совершенно не разрешено никакое сообщение между игроками до игры.
Теоретическая часть.
Рассмотрим наиболее простую игру двух лиц с ненулевой суммой. Платежная матрица игры такова:
Возможны различные интерпретации этой игры, но наиболее известна интерпретация, которую мы можем назвать «семейный спор». Муж, игрок 1, и жена, игрок 2, могут выбрать одно их двух вечерних развлечений: матч бокса ( и ) или балет ( и ). Согласно обычному стандарту, мужчина предпочтет бокс, а женщина — балет; однако обоим гораздо важнее идти вместе, чем смотреть предпочитаемое зрелище. Если игрок 1 объявит, что он намерен выбрать и что никакой довод не заставит его изменить свой выбор, и если игрок 2 убежден в том, что игрок 1 будет упорствовать в своем намерении, то ему ничего не остается, как выбрать . Аналогичное рассуждение имеет место, если игрок 2 первым объявит свои намерения. В такой ситуации выгодно раскрыть свою стратегию первым и иметь репутацию непреклонного человека. Если при переговорах до игры муж скажет, что он обязан быть на боксе и покажет купленный им билет, то это может заставить жену подчиниться его воле. Но некоторых женщин с характером такое бесцеремонное диктаторское поведение рассердит настолько, что совершенно изменит полезности, входящие в платежную матрицу, но в некоторых случаях оно может привести к коренному изменению системы предпочтений игрока и, следовательно, платежной матрицы. В таких случаях мы, возможно, могли бы расширить множество стратегий и усложнить игру так, чтобы включить переговоры до игры.
Продолжая рассматривать ту же платежную матрицу, мы замечаем, что и суть уравновешенные пары, так как каждая стратегия в одной из пар является уравновешенной парой. Кроме того, и дают игрокам неодинаковые выигрыши.
Предположим, что игроки не сообщаются до игры, и что они должны производить свои выборы одновременно, то есть что они играют в некооперативный вариант игры. Допустим игрок 1 хочет , а его противник, очевидно, , но если игрок 1 выберет , а игрок 2 выберет , то они оба проиграют. Предположим, что игрок 1 уступит игроку 2 и выберет , тогда все же игрок 1 окажется в довольно хорошем положении, но ведь игрок 2 также может уступить сопернику выбрав , и они опять проиграют. Такой подход игроков не приведет ни к чему хорошему вследствие симметрии ситуации, поэтому, чтобы максимально увеличить свой гарантированный уровень, они выбирают смешанную стратегию , такую, чтобы максимально увеличить наименьшую из двух величин
и ,
связанных с каждым x. После некоторых вычислений игрок 1 находит, что его максиминная стратегия будет .
Игроку, участвующему в этой некооперативной игре, может быть любопытно, как поступил бы он и его противник, если бы игра была в действительности кооперативной, ибо если им ясны их роли в кооперативном варианте, то каждый мог бы поступить так, как будто он находится в сговоре с другим игроком, даже при отсутствии сообщения до игры. Хотя это предложение естественно, но его нельзя использовать в действительности гораздо плодотворнее обратный способ: анализировать кооперативную игру путем построения соответствующей вспомогательной некооперативной игры.
В кооперативной игре игроки будут пытаться прийти к или и «справедливым» решением для них будет бросание монеты, причем герб означает, что совместно выбрана пара , решетка — что совместно выбрана пара . В нашей интерпретации: герб — семейство идет на бокс, решетка — на балет. Полезность при этой совместно установленной смешанной стратегии равна для каждого игрока. Заметим, что в некооперативном варианте доход не возможен — он лежит вне затененной области на рис.1.
рис.1
Обратимся теперь к другому примеру игры с ненулевой суммой. Он приписывается Таккеру и привлек большое внимание теоретиков игр. Платежная матрица игры G такова:
Известна следующая интерпретация — так называемая «дилемма заключенного». Двух подозреваемых берут под стражу и изолируют друг от друга. Окружной прокурор убежден, что они совершили преступление, но не имеет достаточных доказательств, чтобы предъявить им обвинение на суде. Он говорит каждому из них, что у него имеется две альтернативы: признаться в преступлении, которое по убеждению полиции он совершил, или не признаться. Если оба не признаются, то окружной прокурор предъявит им обвинение в каком-либо незначительном преступлении, таком, например, как мелкая кража или незаконное владение оружием, и они оба получат небольшое наказание; если оба признаются, то будут подлежать судебной ответственности, но он не потребует самого строго преговора; если же один признается, а другой нет, то признавшемуся приговор будет смягчен за выдачу сообщника, в то время как упорствующий получит «на полную катушку».
Если обозначить и — непризнание, а и — признание, то при условии, что донос не вызывает ни у одного из них угрызений совести или страха. Перед каждым каждым заключенным стоит вопрос — признаться или нет. Игра, которую окружной прокурор предлагает заключенным, представляет собой некооперативный вариант.
Рассмотрим игру G сперва с точки зрения игрока 1. Если игрок 2 выберет или , то вторая стратегия игрока 1 предпочтительнее его первой стратегии, так как в первом случае 1 больше 0.9, а во втором случае 0.1 больше 0. Итак строго доминирует над . Точно также строго доминирует над . Поскольку каждый из игроков хочет получить максимум полезности, их «разумные» выборы будут и .
Можно попробовать доказать, что разница между 1 и 0.9 и 0.1 и 0 так мала, что даже «этика» преступника заставит выбрать его первую стратегию, чтобы оба они не попали в нелепую ловушку . Такой довод недопустим, так как по предположению числовые полезности отражают все подобные «этические» соображения. Нет, по-видемому, эту дилемму нельзя обойти. Мы не думаем, что выбор или имеет в себе что-либо неразумное или извращенное, и должны допустить, что если бы мы были в этом положении, то могли бы сделать эти выборы.