- •Теория принятия решений
- •1. Элементы теории игр
- •1.1 Основные понятия
- •1.2 Матричные игры
- •1.3 Принцип минимакса. Седловые точки
- •1.4 Смешанные стратегии
- •1.5 Пример полного решения матричной игры
- •1.6 Задания по теории игр
- •2. Задача о назначениях
- •2.1 Содержательная постановка
- •2.2 Математическая модель
- •2.3 Венгерский метод для задачи о назначениях
- •2.4 Алгоритм венгерского метода
- •2.5 Пример решения задачи о назначениях венгерским методом
- •2.6 Задания по задаче о назначениях
- •3. Задача о коммивояжере
- •3.1 Постановка задачи
- •3.2 Математическая модель
- •3.3 Метод ветвей и границ
- •3.4 Метод ветвей и границ для решения задачи коммивояжера
- •3.5 Пример решения задачи коммивояжера
- •3.6 Задания по задаче о коммивояжере
- •4. Динамическое программирование
- •4.1 Построение модели дп
- •4.2 Построение вычислительной схемы дп
- •4.3 Несколько замечаний к методу дп
- •4.4 Задача о распределении ресурсов
- •4.5 Пример решения задачи о распределении ресурсов
- •4.6 Задания по задаче о распределении ресурсов
- •4.7 Задача о замене оборудования
- •4.8 Пример решения задачи о замене оборудования
- •4.9 Задания по задаче о замене оборудования
- •Библиографический список
- •1. Элементы теории игр 3
- •2. Задача о назначениях 14
- •3. Задача о коммивояжере 25
- •4. Динамическое программирование 35
Федеральное агентство по образованию
Государственное образовательное учреждение высшего профессионального образования
«Омский государственный технический университет»
Теория принятия решений
Сборник заданий
для практических занятий
Омск 2006
Составители: А.В. Зыкина, О.Н. Канева
Кафедра «Автоматизированные системы обработки информации и управления»
Для студентов специальности 230102 и направления 230100
Печатается по решению редакционно-издательского совета ОмГТУ
Учебно-методическое пособие предназначено для обеспечения заданиями практических занятий по дисциплине «Теория принятия решений». Кроме того, это пособие можно использовать в качестве установочного материала студентам, использующим дистанционные технологии обучения. В сборнике кроме заданий по темам соответствующих занятий приведены краткие теоретические результаты, рекомендации к их освоению и примеры решения типовых задач.
Первый раздел – элементы теории игр. Здесь рассмотрены основные понятия теории, более подробно излагается матричная игра, кроме того, для решения матричной игры необходимо знание симплекс-метода (для повторения симплекс-метода можно обратиться к методичке [4]).
Второй раздел посвящен задаче о назначениях: приводится математическая модель, вводятся необходимые для решения задачи понятия, излагается алгоритм венгерского метода для решения задачи.
В третьем разделеизложена задача о коммивояжере: приводится математическая модель, вводятся необходимые для решения задачи понятия, приводится алгоритм метода ветвей и границ для решения задачи коммивояжера.
Четвертый разделсодержит классический подход к решению непрерывной задачи динамического программирования. Рассматриваются две содержательные задачи динамического программирования: задача о распределении ресурсов и задача о замене оборудования.
1. Элементы теории игр
1.1 Основные понятия
Теория игр – это особый раздел исследования операций, в котором изучаются математические модели принятия оптимальных решений в условиях конфликта. Под конфликтом обычно понимают любое явление, применительно к которому имеет смысл говорить, кто и как в этом явлении участвует, каковы его возможные исходы, кто в этих исходах заинтересован и в чем состоит эта заинтересованность. Важно отметить, что приведенная формулировка весьма универсальна и охватывает не только конфликты между участниками так называемых салонных игр (шахматы, шашки, карточные игры и т.д.), но и экономические столкновения интересов различных фирм в условиях конкуренции, а также военные конфликты.
В зависимости от числа сторон, участвующих в конфликте, различают игры многих лиц и игры двух лиц (парные игры). Мы будем рассматривать только парные игры. Конфликтующие стороны назовем игроками и обозначим их цифрами IиII(это могут быть и команды).
Игра состоит из последовательности ходов. Стратегией игрока называют систему правил, определяющих его выбор варианта действия при каждом ходе. В большинстве игр игрок принимает решение о своем очередном ходе перед самым этим ходом или на несколько ходов вперед. Иначе и не может быть, поскольку в таких играх, как шахматы, число возможных ходов в большинстве позиций очень велико, и это не дает возможности игрокам заранее спланировать все свои действия от начала до конца. Однако с теоретической точки зрения ничто не мешает нам предполагать, что уже до начала игры каждый игрок решил, как он будет играть в любой позиции. Таким образом, мы предполагаем, что каждый игрок выбирает стратегию еще до начала игры.
Множества стратегий игроков IиIIбудем обозначать буквамиXиYсоответственно. Пусть игрокIвыбрал стратегию, а игрокII– стратегию. Комбинация этих стратегий (x,y) называется ситуацией. Некоторые комбинации стратегий могут оказаться несовместимыми, и в этом случае говорят о невозможной ситуации.
Пример 1.1.Игра «Крестики-нолики».
Имеется поле размером 33, клетки поля пронумерованы числами 1,…,9. ИгрокIделает ход первым, ставя крестик в одну из свободных клеток. ИгрокIIиграет ноликами. Максимальное число ходов в одной партии – 9 (5 ходов игрокаIи 4 хода игрокаII). Таким образом, любую стратегиюxигрокаIможно закодировать набором, где,, – номер клетки, занятой крестиком приi-м ходе. Аналогично любая стратегияyигрокаIIесть набор.
Пусть x =53489,y=1762. Тогда ситуация (x,y) определяет ничейный исход (показано на рис. 1,a). Если жеx=53489, аy=1742, то ситуация (x,y) невозможна: игрокIIне может своим третьим ходом поставить нолик в клетку 4, так как она уже занята крестиком (рис 1,б).
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
а)
б)
Рис. 1
По количеству возможных стратегий игроков игры делятся на конечные и бесконечные.
Заинтересованность игроков в исходах игры проявляется в том, что каждый из них предпочитает одни ситуации другим. Чаще всего отношение предпочтения задается с помощью функций выигрыша, определенных на множестве ситуаций. Обозначим через (x,y) – выигрыш игрокаIв ситуации (x,y). Таким образом,(x,y) – это тот выигрыш (количество очков, сумма денег и т. д.), на который может рассчитывать игрокI, если он выберет стратегию, а его соперник – стратегию. Аналогично определяется функция выигрыша(x,y) игрокаII.
Далее мы будем рассматривать игры с нулевой суммой, когда (x,y)+(x,y)=0, то есть(x,y) =-(x,y) для любыхи. В таких играх выигрыш одного игрока одновременно является проигрышем другого, и мы можем рассматривать его как платеж проигравшего победителю.