Файл: М.А. Тынкевич Принятие решений в условия неопределенности (теория игр и статистических решений).pdf

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

КУЗБАССКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Кафедра вычислительной техники и информационных технологий

ПРИНЯТИЕ РЕШЕНИЙ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ

(ТЕОРИЯ ИГР И СТАТИСТИЧЕСКИХ РЕШЕНИЙ)

Методические указания и задания к практическим занятиям по курсам

“Исследование операций в экономике” и “Экономико-математические методы”

для студентов экономических специальностей

Составители М.А.Тынкевич О.А. Бияков

Утверждены на заседании кафедры вычислительной техники и информационных технологий Протокол № 5 от 16.01.2001

Рекомендованы к печати учебно-методической комиссией по специальности 351400 Протокол № 3 от 16.01.2001

Кемерово 2001

1

Работа 1. Матричные игры

1.1. Постановка задачи и описание метода решения

Теория игр занимается изучением т. н. конфликтных ситуаций, где сталкиваются интересы индивидов, партий, государств и т. п. Разумеется, не существует математической теории, которая могла бы однозначно предсказать результат реальной игры, но существуют ситуации, подобные игровым и допускающие математический анализ.

Простейшими среди игр являются матричные игры с нулевой суммой. В такой игре участвуют два игрока, первый из которых имеет m выборов и второй - n выборов. Если игрок 1 делает свой i-й выбор, а игрок

2 - свой j-й выбор, то выигрыш игрока 1 (проигрыш игрока 2) равен Rij.

Матрица R = [ Rij / i=1..m , j=1..n ] называется матрицей выигрышей

(платежной матрицей).

Система правил, однозначно определяющая выбор игрока в зависимости от сложившейся ситуации, называется стратегией.

Каждая фиксированная стратегия игрока, где конкретный выбор со-

ваются с некоторыми частотами.

При ведении игры игрок должен ориентироваться на оптимальную политику партнера и наказывать его за отступления от таковой.

С этих позиций игроку 1 гарантирован выигрыш, не меньший

V1 = max min Rij ,

i=1..m j=1..n

а игроку 2 - проигрыш, не превышающий

V2 = max min Rij .

i=1..m j=1..n

Если в матрице выигрышей существует элемент Rk l = V1 = V2, то говорят о наличии оптимальной политики "в пространстве чистых стратегий" и оптимальными выборами для игроков соответственно

Седловые точки - (4, 1) и (4, 2). Цена игры = 6; оптимальный выбор для игрока 1 - четвертый, для игрока 2 равнозначны первый и второй

(под ценой игры понимают гарантированный выигрыш-проигрыш при оптимальной политике обоих игроков).

Здесь равенство V1 = V2 не выполняется; оптимальной чистой стратегии для игроков нет.

При анализе игр часто пытаются уменьшить размеры изучаемой матрицы, выявляя доминирование между строками и столбцами. Так в примере 1 элементы четвертой строки больше соответствующих элементов других строк: использование выбора 4 выгоднее других выборов при любой политике противника. Противник видит, что в такой ситуации использовать выборы 3 и 4 неразумно.

При отсутствии седловой точки среди чистых стратегий приходится искать таковую среди смешанных.

утверждает, что любая матричная игра с нулевой суммой всегда имеет седловую точку, т.е. существуют векторы P и Q такие, что

Поиск цены игры и соответствующих вероятностей сводится к ре-

Если учесть, что при увеличении элементов матрицы R на любую константу С цена игры увеличится на С и это изменение не окажет влияния на искомые вероятности выборов, то всегда можно добиться положительности элементов матрицы и, следовательно, цены игры.

В предположении V > 0 можно провести замену переменных

Хi = Pi / V , Yj = Q j / V

3

и поставленные задачи преобразовать к задачам с меньшим числом переменных:

Решение этих задач симплексным методом дает оптимальные зна-

чения

X = { 11/37, 4/37, 5/37 }, Y = { 8/37, 7/37, 5/37 }

и экстремумы целевых функций, равные 20/37. Отсюда

V = 37/20 ,

P = {11/20, 4/20, 5/20} ,

Q = {8/20, 7/20, 5/20}.

Следует учесть, что мы здесь ограничиваемся рассмотрением игр, реализация которых может осуществляться любое число раз, не зависит от результата предыдущих действий и от длительности. Игры, где каждый последующий выбор зависит от результата предыдущих действий, относятся к т.н. многошаговым играм и не имеют столь простого решения [1].

1.2. Контрольные задания

1.2.1. Требования

1. Для матричной игры, соответствующей варианту контрольного задания, проверьте наличие оптимальной чистой стратегии.

2. Поставьте пару двойственных задач и выполните ее решение симплексным или каким-либо другим методом. Оцените полученное опти-

4

мальное решение с позиций здравого смысла.

3. С помощью лекционного материала, учебных пособий или собственных умозаключений выясните правомерность постановки задач (1) и

(2). Зачем при переходе от постановки (1) к (2) требуется уверенность в положительности цены игры ?

1.2.2. Варианты заданий

5

Работа 2. Статистические решения

2.1. Основные понятия теории статистических решений

Теория статистических решений может быть истолкована как теория поиска оптимального недетерминированного поведения в условиях неопределенности. Согласно А.Вальду, поведение считается оптимальным, если оно минимизирует риск в последовательных экспериментах, т.е. математическое ожидание убытков статистического эксперимента. В такой постановке любая задача статистических решений может рассматриваться как игра двух лиц, в которой одним из игроков является "природа".

Иногда усредненные характеристики некоторого случайного процесса испытывают тенденцию к стабилизации и появляется возможность либо замены его детерминированным, либо использования каких-то методов исследования стационарных случайных процессов ( методов теории массового обслуживания и др.).

Однако большинство процессов характеризуется "дурной неопределенностью" , для которой невозможно найти законы распределения и другие вероятностные характеристики. В таких ситуациях приходится прибегнуть к экспертным оценкам.

Возникает и проблема выбора критерия оптимальности, поскольку решение, оптимальное для каких-то условий, бывает неприемлемым в других и приходится искать некоторый компромисс.

Пусть задан некоторый вектор S = (S1,S2,..,Sn), описывающий n со-

стояний внешней среды, и вектор X = (X1,X2,..,Xm), описывающий m до-

пустимых решений. Требуется найти вектор X* =(0,0,..,0, Xi ,0,..,0), который обеспечивает оптимум некоторой функции полезности W(X,S) по некоторому критерию K.

Информация oб указанной функции представляют матрицей размер-

ности m × n c элементами Wij = F(Xi,S j), где F - решающее правило. Рассмотрим типичный пример формирования такой матрицы. Планируется выпуск новой продукции, для чего необходимо заку-

пить станки. Система оптовой торговли может поставить не более 50 станков; комплект поставки - 10 станков. Минимальный объем поставок - 20 станков. Соответственно, вектор решений об объеме поставок X = (20,30,40,50).

Ежегодный доход от продукции, снимаемой с одного станка, cоставляет 21.9 тыс.руб. Оптовая цена одного станка 4.775 тыс. руб., эксплуатационные расходы - 3.6 тыс. руб. Затраты на подготовку производства составляют 25.5 тыс.руб. и не зависят от числа станков и объема выпуска.

Пусть спрос пропорционален количеству продукции, снимаемой с S работающих станков, и для простоты ограничимся вектором состояний