Интеллектуальная система. Разрешение конфликтных ситуаций по разработке и продаже программных продуктов между двумя фирмами. Матричная и

 

Зарегистрировано «___»________20___г.

________ __________________________

Подпись       (расшифровка подписи)

 

ФЕДЕРАЛЬНОЕ  ГОСУДАРСТВЕННОЕ  АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

ФАКУЛЬТЕТ КОМПЬЮТЕРНЫХ НАУК И ТЕЛЕКОММУНИКАЦИЙ

 

КАФЕДРА МАТЕМАТИЧЕСКОГО  И ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ИНФОРМАЦИОННЫХ СИСТЕМ

 

 

 

 

«Интеллектуальная система. Разрешение конфликтных ситуаций по разработке и продаже программных продуктов между двумя фирмами. Матричная игра с двумя игроками»

 

 

 

 

Курсовая работа

студента дневного отделения 5 курса группы

 

 

 

 

Научный руководитель:

д.т.н., проф. .

 

 

 

 

 

 

2012

 

ПЛАН КУРСОВОЙ РАБОТЫ

по дисциплине: «Системы искусственного интеллекта»

на тему: «Интеллектуальная система. Разрешение конфликтных ситуаций по разработке и продаже программных продуктов между двумя фирмами. Матричная игра с двумя игроками»

 

ВВЕДЕНИЕ

 

 

 

 

 

 

 

 

 

 

Исполнитель:_______________________________________/ /

Руководитель:______________________________________/ /

СОДЕРЖАНИЕ

 

ВВЕДЕНИЕ

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

Данная курсовая работа направлена на поиск оптимального выхода из конфликтной ситуации по разработке и продаже ПО. Эта задача сведена к решению матричной игры с двумя игроками, то есть, к определению оптимальных стратегий для обоих игроков, при которых они достигают наибольшего выигрыша.

Цель курсовой работы: закрепить полученные знания по дисциплине «Системы искусственного интеллекта», применить полученные знания на практике.

Задачи курсовой работы:

• исследование методов нахождения решения матричных игр;
• развитие навыков нахождения решения матричной игры методами линейного программирования;
• приобретение навыков обоснования принимаемых проектных решений и профессионального оформления проектной документации.

Курсовая работа состоит  из 28 страницы, 7 рисунков и 20 формул. Использовано 8 литературных источников.

 

1. ОСНОВНЫЕ ПОНЯТИЯ  ТЕОРИИ ИГР

1.1. Предмет и задачи  теории игр

 

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

Примерами конфликтной  ситуации являются ситуации, складывающиеся во взаимоотношениях покупателя и продавца; в условиях конкуренции различных фирм; в ходе боевых действий и др. Примерами игр являются и обычные игры: шахматы, шашки, карточные, салонные и др. (отсюда и название “теория игр” и ее терминология).

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

Теория игр - это математическая теория конфликтных ситуаций [1].

Цель теории игр - выработка рекомендаций по разумному поведению участников конфликта (определение оптимальных стратегий поведения игроков) [1].

 

1.2. Терминология и основные понятия

 
            В теории игр предполагается, что игра состоит из ходов, выполняемых игроками одновременно или последовательно.

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

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

Задача теории игр - нахождение оптимальных стратегий.

Конечная парная игра с нулевой суммой называется матричной игрой. Такая игра описывается платежной матрицей, в которой задаются выигрыши первого игрока. Номер строки матрицы соответствует номеру применяемой стратегии первого игрока, столбец - номеру применяемой стратегии второго игрока; на пересечении строки и столбца находится соответствующий выигрыш первого игрока (проигрыш второго игрока).

2. ОСНОВНЫЕ ТЕОРЕТИЧЕСКИЕ  ПОНЯТИЯ О МАТРИЧНЫХ ИГРАХ

2.1. Понятие матричной  игры. Задача теории игр.

 

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

                                            (1)

где - равно выигрышу первого (будем обозначать его А) и проигрышу второго (игрока В) при применении ими i-той и j-той чистых стратегий соответственно.

В матричной игре оптимальной  для игрока А называется стратегия, при многократном повторении игры обеспечивает максимально возможный средний  выигрыш, а для игрока В при  оптимальной понимается стратегия, обеспечивающая ему минимальный средний проигрыш. При этом предполагается, что игрок делает все для того, чтобы помешать сопернику добиться своей цели [2].

2.2. Запись матричной игры в виде платежной матрицы

 

В общем виде матричная  игра может быть записана следующей  платежной матрицей (рисунок 1):

	B1	B2	…	Bn
A1	A11	A12	...	A1n
A2	A21	A22	...	A2n
Am	Аm1	Аm2	..	Аmn

 

Рисунок 1. Общий вид платежной матрицы матричной игры

где Ai-названия стратегий  игрока A, Bj - названия стратегий игрока B, aij-значение выигрышей игрока A при  выборе им i-той стратегии, а игроком В - j-того стратегии. Поскольку данная игра является игрой с нулевой суммой, значение выигрыша для игрока В является величиной, противоположной по знаку значению выигрыша игрока А.

2.3. Решение игры в чистых стратегиях

 

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

Vн = maxi minjaij,      (2)

или найти минимальные  значения по каждому из строк платежной  матрицы, а затем определить максимальное из этих значений. Величина Vн называется Максимин матрицы или нижней ценой  игры.

Размер выигрыша игрока А равна, по определению матричной игры, величине проигрыша игрока В. Поэтому для игрока В необходимо определить значение:

Vв = minj maxi aij,                                                            (3)

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

В случае, если значение Vн и Vв не совпадают, при сохранении правил игры (коэффициентов aij) в длительной перспективе, выбор стратегий каждым из игроков оказывается неустойчивым. Стойкости он приобретает лишь при Vн = Vв = V. В этом случае говорят, что игра имеет решение в чистых стратегиях, а стратегии, в которых достигается V - оптимальными чистыми стратегиями. Величина V называется чистой ценой игры. Ситуация (a *, b *) в антагонистических играх с функцией выигрыша H (a, b), для которой выполняется двойная неравенство: H (a, b *) ≤ H (a *, b *) ≤ H (a *, b) для всех стратегий a игрока A, и для всех стратегий b для игрока B называется седловой точкой [1].

2.4. Матричные игры со смешанными стратегиями

 

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

Смешанной стратегией игрока называется определенный набор чистых стратегий, применяемых согласно установленного распределения вероятности. Матричная игра, решается с использованием смешанных стратегий, называется игрой со смешанным расширением [3].

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

Основная теорема теории игр (доказана фон Нейманом в 1928 году) утверждает: Каждая матричная игра с нулевой суммой имеет по крайней мере одно решение, возможно в области смешанных стратегий, то есть существуют стратегии и, оптимальные для обоих игроков, причем

                      (4)

Число называют ценой игры.

Из основной теоремы  следует, что каждая конечная игра имеет  цену и она лежит между нижней и верхней ценам игры: Vн £ V £ Vв .          

Кроме того, если один из игроков придерживается своей оптимальной  смешанной стратегии, то выигрыш  остается неизменным и равным цене игры V, независимо от того, каких стратегий  придерживается другой игрок, если только он не выходит за пределы своих активных стратегий. Поэтому, для достижения наибольшего гарантированного выигрыша второму игроку также необходимо придерживаться своей оптимальной смешанной стратегии [2].

 

3. МЕТОДЫ РЕШЕНИЯ МАТРИЧНЫХ ИГР

 

Сравнительно просто решаются игры, в которых хотя бы один игрок имеет всего две  чистых стратегии: игры 2 2, 2 n, m n. Когда m, n> 2 теория игр не имеет собственного точного метода. Такие игры сводятся к задачам линейного программирования и решаются методом симплекс-таблиц. Применение симплекс-метода приводит к громоздким вычислениям уже для игры 3 3. Для игр больших размеров применяются приближенные численные методы.

3.1. Решение игры 2 2

В общем случае игра 2 2 определяется матрицей

 

.    (5)

Прежде всего, необходимо проверить, есть ли у данной игры седловая точка. Если так, то игра имеет решение  в чистых стратегиях, причем оптимальными стратегиями игроков A и B соответственно будут чистая максиминная и чистая минимаксная стратегии. Если же игра с матрицей выигрышей А не имеет решения в чистых стратегиях, то оба игрока имеют только такие оптимальные стратегии, которые используют все свои чистые стратегии с положительными вероятностями.

Пусть U = (x, 1 - x) – оптимальная стратегия игрока A. Тогда

;        (6)

 

.    (7)

 

Аналогично, W = (h, 1 – h) – оптимальная стратегия игрока B, то

.    (8)

 

3.2. Решение игр  2 n и m 2

Для построения решений  игр 2×n и m×2 существует эффективный метод, основанный на простых геометрических соображениях. Этот метод называют графическим.

Рассмотрим  игру 2 n: .    (9)

Задача игрока A состоит в максимизации функции