Системный анализ – Теория матричных игр
Федеральное агентство по образованию РФ
Пермского Государственного технического университета
Лысьвенский филиал
Кафедра ИЭ и ЕН
Пояснительная записка к курсовой работе
по дисциплине «Системный анализ – Теория матричных игр»
Выполнила: Студентка гр. БИВТ- 04-1
Руководитель:
Лысьва-2007
СОДЕРЖАНИЕ
РЕФЕРАТ
ВВЕДЕНИЕ
Глава 1: ТЕОРИЯ ИГР
1.1 Понятие игры
1.2 Основные определения
1.3 Конечная парная антагонистическая игра
1.4 Теорема фон Неймана
1.5 Игра размерностью m×n
Глава 2: РАЗРАБОТКА
2.1 О среде разработки – Turbo Pascal
2.2 Руководство пользователя
2.3 Используемые процедуры и функции
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ
РЕФЕРАТ
Введение содержит главную цель разработки и её значимость на сегодняшний день.
Теоретические данные раскрывают суть теории матричных игр, виды, основные определения, методы нахождения оптимального решения и цены игры.
Руководство пользователя написано доступным языком, а предоставленные рисунки делают описание работы программы еще более понятным.
Описан алгоритм решения задачи, используемые процедуры и переменные.
Пояснительная записка содержит так же приложение: результат работы программы над решением задачи, описанной в руководстве пользователя.
Сделан вывод о проделанной работе. Отчет содержит 24 листа.
ВВЕДЕНИЕ
Целью данного проекта является разработка программы, которая посредствам вычислений определяла оптимальные стратегии для каждого игрока и цену матричной игры в целом. Кроме того, предусматривается возможность не только получить конечный ответ, но и просмотреть промежуточные вычисления решения задачи.
Программа реализуется на языке программирования Turbo Pascal, предусматривает ввод квадратных и неквадратных платежных матриц, имеющих количество строк и столбцов не более десяти.
Глава 1: ТЕОРИЯ ИГР
1.1 Понятие игры
Теория игр представляет собой математическую теорию конфликтных ситуаций. Ее цель – выработка рекомендаций по разумному поведению участников конфликта. Впервые описана в1944 – в монографии фон Неймана и Моргенштерна.
Игра – эта ситуация, в которой эффективность решений одного игрока зависит от действий другого игрока.
Игра развивается по определенным правилам, которые определяют последовательность ходов игроков.
Конец игры наступает в том случае, когда все возможные ходы игроками сделаны.
Игра характеризуется:
1. Множество заинтересованных сторон – лиц, участников, игроков
2. Множеством возможных действий (ходов) для каждого игрока – стратегий
3. Интересами игроков, задаваемых с помощью функции выигрыша – функции платежа.
Игры бывают:
1. Игры парные (2 игрока) и множественные.
2. По количеству возможных стратегий:
• конечные (конечное у каждого игрока)
• бесконечные (хотя бы у одного игрока бесконечное число стратегий)
3. По свойствам функции платежа:
• антагонистическая (с нулевой суммой) – выигрыш одного = проигрышу другого,
• игра с постоянной разностью (участники выигрывают и проигрывают одновременно, следовательно выгодно действовать сообща).
4. По наличию предварительной договоренности о совместных действиях: кооперативные (есть договоренность) и некооперативные (договоренности нет).
1.2 Основные определения
Стратегия – совокупность правил, определяющих выбор варианта действия игроком в зависимости от ситуации в игре.
Целью является отыскание оптимальной стратегии для каждого игрока.
Оптимальная стратегия – стратегия, которая при многократном повторении игры обеспечивает игроку максимально возможный выигрыш или минимально возможный проигрыш независимо от поведения противника.
Выбор одной из возможных стратегий и ее реализация называется ходом.
Ход – может быть личным (выбор стратегии сознателен) и случайным.
Игру можно описать разными способами
1. Позиционный – задается в виде дерева шагов.
2. Нормальный – задаются допустимые стратегии для каждого игрока и функция выигрыша, которая определяет выигрыш или проигрыш для каждой стратегии. Чаще всего задается в виде платежной матрицы.
1.3 Конечная парная антагонистическая игра
Два игрока (I и II) обладают конечным набором стратегий:
I стратегии А1…..Am
II стратегии B1….Bn
Эта игра размерностью n×m.
Предположим, что на некотором ходе игрок I выбрал стратегию Ai , а игрок II отвечает стратегией Bj. Тогда W1 (Ai , Bj) – выигрыш, который получит игрок I при этой паре стратегий. W2 (Ai , Bj) – выигрыш, который получит игрок II при этой паре стратегий
Так как игра антагонистическая, то
W1 (Ai , Bj) + W2 (Ai , Bj) =0 или W1 (Ai , Bj) =- W2 (Ai , Bj) = W (Ai , Bj)
Обозначим W (Ai , Bj)=aij тогда получим платежную матрицу
Каждый положительный элемент это выигрыш I игрока, каждый отрицательный – проигрыш II.
1.4 Теорема фон Неймана
Любая антагонистическая парная конечная игра имеет по крайней мере одно решение, возможное в смешанных стратегиях.
Следовательно игра имеет цену γ, α≤ γ ≤ β
Игрок I стремится добиться выигрыша = γ, а игрок II стремится минимизировать проигрыш до γ.
Смешанные стратегии также обладают свойством равновесия, обоим игрокам выгодно их применять.
Теорема:
Применение оптимальных смешанных стратегий гарантирует игроку максимально возможный средний выигрыш (минимально возможный средний проигрыш) равный цене игры γ, независимо от поведения противника, если игрок не выходит за пределы своих активных стратегий.
1.5 Игра размерностью m×n
В ТИ доказано, что в играх размерностью m×n число активных стратегий = min{m,n}. Таким образом, решение игр m×2 и 2×n сводится к решению игр 2×2.
Способы понижения размерности платежной матрицы
1. Размерность матрицы можно понизить путем удаления дублирующих и заведомо не выгодных стратегий .
2. Если в матрице все элементы некоторой строки (столбца) равны, то соответствующие стратегии называются дублирующими.
3. Если в матрице все элементы некоторой строки , соответствующие стратегии Ai I игрока не больше соответствующих элементов другой строки, то стратегии Ai называется заведомо невыгодной для I игрока.
4. Если в матрице все элементы некоторого столбца, соответствующие стратегии Bj II игрока не меньше соответствующих элементов другого столбца, то стратегию Bj называется заведомо невыгодной для II игрока
Рассмотрим игру, которая будет описана следующей платежной матрицей.
Находим решение в смешанных стратегиях:
I игрок чистые стратегии А1…..Am; II игрок чистые стратегии B1….Bn;
Оптимальные смешанные стратегии p*A ,p*B
Предположим, что все элементы платежной матрицы ≥0, иначе добавляем к каждому элементу положительное число, при этом оптимальные стратегии не меняются, а цена игры увеличивается на это число.
Согласно теореме ТИ если I игрок будет придерживаться оптимальной смешанной стратегии, то он получит выигрыш ≥γ (цены игры). При этом II игрок применяет свои чистые стратегии
Введем обозначения xi=pi/γ i=1..m
Разделим неравенства на γ
Цель I игрока увеличить выигрыш γ
Так как p1+…+pm=1, то x1+…xm=1/γ
F=x1+…..+xm→min
Получаем задачу линейного программирования.
Составим аналогичную задачу для II игрока.
Если II игрок придерживается оптимальной смешанной стратегии, то он получит проигрыш ≤γ. При этом I игрок применяет свои чистые стратегии.
Введем обозначения yi=qj/γ j=1..n
Разделим неравенства на γ
II игрок стремится уменьшить γ и следовательно F1 надо максимизировать. Таким образом, решение матричных игр m×n сводится к решению пары двойственных симметричных задач.
Решая эти задачи найдем оптимальное решение x*=(x1*.....xm*) y*=(y*1…y*n)
Отсюда найдем цену игры:
Глава 2: РАЗРАБОТКА
2.1 О среде разработки – Turbo Pascal
2.1.1 Системные требования
В официальной документации написано, что для минимальной работоспособности потребуется процессор не ниже Intel 80386 и 4МБ памяти – это действительно минимальная конфигурация для запуска компилятора, для нормальной работы лучше иметь железо не хуже, чем Pentium-75/16МБ. Требуемое место на диске зависит от того, что вы будете устанавливать – можно работать с 8МБ, можно поставить и на 90МБ – и пользоваться всеми возможностями этого замечательного продукта.
2.1.2 Ожидаемые технико-экономические показатели
Данная программа довольно проста и легко компилируется.
Благодаря реализованному алгоритму она будет исправно работать на любом ПК в любой операционной системе Windows NT.
2.2 Руководство пользователя
Поскольку программа реализована в среде Turbo Pascal, то пользователю достаточно выполнять инструкции, следующие друг за другом. Переход от одного действия к другому выполняется клавишей Enter.
Чтобы показать, как работает программа, решим ее средствами следующую задачу теории матричных игр:
Найти решение игры, определяемой матрицей:
А=
Решение:
1. На первом этапе пользователю необходимо ввести размерность платежной матрицы: количество строк и количество столбцов (Рис.1)
Рис.1 – Ввод размерности матрицы
2. Затем, нужно ответить какое решение нужно:
целочисленное, то есть во время вычисления программа будет округлять все промежуточные и конечное решения до целого;
дробное, то есть программа будет округлять все промежуточные и конечное решения до Epsilon = 0.00001 (Рис.2).
Рис.2 – Выбор целочисленного решения или нет
3. Далее вводятся непосредственно элементы платежной матрицы (Рис.2)
Рис.3 – Ввод элементов матрицы
4. Затем, программа выводит на печать исходную матрицу, проверяет ее на наличие Седловой точки. Если Седлова точка есть, то на этом этапе работа программы прекращается, ответ выводится на экран (Например, в матрице Седлова точка равна 1(Рис.4)).
Рис.4 – Вывод решения при наличии Седловой точки
5. Если Седловой точки нет, то задача решается симплекс методом, решение сохраняется в файл RESHENIE.DAT (Результат вычислений для приведенного примера находится в приложении1).
Рис.5 – Вид окна программы в случае отсутствия Седловой точки
2.3 Используемые процедуры и функции
Для легкого чтения, компилирования и модернизации программного кода я использовала прием дробления программы на подпрограммы.
1. В качестве первой подпрограммы описана функция создания индексов. Она формирует индексы основных и дополнительных переменных на этапе решения задачи Симплекс – методом:
FUNCTION SIMVB(V:INTEGER;S:CHAR):
VAR M,Z:STRING;
BEGIN
STR(V,M);
Z:=S+M;
SIMVB:=Z;
END;
2. Следующая подпрограмма – это процедура, выполняющая запись данных в файл:
PROCEDURE SAVE(X1:REAL;K:STRING;Mstr:
VAR V:STRING;
BEGIN
ASSIGN(F,'Reshenie.DAT');
APPEND(F);
CASE Mstr OF
0:WRITELN(F,'');
1:BEGIN
IF K=' ' THEN STR(X1:1:0,V) ELSE STR(X1:10:4,V);
WRITE(F,V);
WRITE(F,' ');
END;
2:WRITE(F,K);
3:WRITELN(F,K);
END;
CLOSE(F);
END;
3. Далее следует процедура определения дополнительных переменных для решения Симплекс – методом.
PROCEDURE DOP_PER;
BEGIN
IF ZNAC[I1]='=' THEN
BEGIN
Kell:=Kell+1;Bvsp[Kell]:=
DPy:=DPy+1;
Xnew[I1,Kell]:=1;
IF Fm=1 THEN FX[Kell]:=-1 ELSE FX[Kell]:=1;
FunctPr[Kell]:=1;
FOR I:=1 TO Kstr DO
IF I<>I1 THEN Xnew[I,Kell]:=0;
END;
IF ZNAC[I1]='>=' THEN
BEGIN
Kell:=Kell+1;Bvsp[Kell]:=
DPx:=DPx+1;Dop_X:=Dop_X+1;
Xnew[I1,Kell]:=-1;FX[Kell]:=0;
FOR I:=1 TO Kstr DO
IF I<>I1 THEN Xnew[I,Kell]:=0;
Kell:=Kell+1;Bvsp[Kell]:=
DPy:=DPy+1;
Xnew[I1,Kell]:=1;
IF Fm=1 THEN FX[Kell]:=-1 ELSE FX[Kell]:=1;
FunctPr[Kell]:=1;
FOR I:=1 TO Kstr DO
IF I<>I1 THEN Xnew[I,Kell]:=0;
END;
IF ZNAC[I1]='<=' THEN
BEGIN
Kell:=Kell+1;Bvsp[Kell]:=
DPx:=DPx+1;Dop_X:=Dop_X+1;
Xnew[I1,Kell]:=1;FX[Kell]:=0;
FOR I:=1 TO Kstr DO
IF I<>I1 THEN Xnew[I,Kell]:=0;
END;
END;
4. Следующая процедура сокращения Y:
PROCEDURE SOKR;
VAR P:INTEGER;
BEGIN
Kell:=Kell-1;
FOR P:=NachKell+DOP_X TO Kell DO
IF Bvsp[P]=BS[KLstr] THEN BEGIN
FOR J:=P TO Kell DO
Bvsp[J]:=Bvsp[J+1];
FunctPr[J]:=FunctPr[J+1];
Fx[J]:=Fx[J+1];
FOR I:=1 TO Kstr DO
Xnew[I,J]:=Xnew[I,J+1]
END;
END;
5. Следующая процедура, выполняющая Метод Гомори, необходима в процедуре, выполняющей Симплекс – метод:
PROCEDURE GOMORY;
VAR MAX,Z:REAL;
BEGIN
KLstr:=1;
MAX:=H[1]-INT(H[1]);
FOR I1:=2 TO Kstr DO
IF (H[I1]-INT(H[I1]))>=MAX THEN BEGIN MAX:=H[I1]; KLstr:=I1;END;
Kstr:=Kstr+1;
Hnew[Kstr]:=H[KLstr]-INT(H[
FOR I1:=1 TO Kell DO
BEGIN
Z:=INT(X[KLstr,I1]);
IF X[KLstr,I1]<0 THEN Z:=Z-1;
Xnew[Kstr,I1]:=X[KLstr,I1]-Z;
END;
ZNAC[Kstr]:='>=';
END;
6. Далее следуют несколько подпрограмм, необходимые для проверки наличия или отсутствия Седловой точки:
Процедура нахождения максимума по столбцам:
PROCEDURE MAXIM(k:integer);
BEGIN
MAXi:=1;
MAXJ:=K;
FOR I:=1 TO Kstr do BEGIN
IF Xnew[I,MAXJ]>Xnew[MAXi,MAXJ]
THEN BEGIN
MAXi:=I;
END; END;
end;
Процедура нахождения минимума по строкам:
PROCEDURE MINIM(v:INTEGER);
BEGIN
MINj:=1;
MINi:=v;
FOR J:=1 TO Kell do
IF Xnew[mini,J]<Xnew[mini,MINj]
THEN BEGIN
MINj:=J;
END;
END;
Процедура нахождения Седловой точки:
PROCEDURE SEDLOVAYA_T;
VAR STB,STR:MAS;
BEGIN
FOR J:=1 TO Kell DO
begin
MAXIM(J);
stb[J]:=Xnew[MAXi,MAXJ];
END;
FOR I:=1 TO Kstr DO
begin
Minim(I);
STR[I]:=Xnew[mini,MINj];
END;
M:=1;
FOR J:=2 TO Kell DO
IF STB[J]<STB[M] THEN
M:=J;
BETA:=STB[J];
M:=1;
FOR I:=2 TO Kstr DO
IF STR[I]>STR[M] THEN
M:=I;
ALFA:=STR[I];
IF ALFA=BETA THEN
WRITELN('Найдена Седлова точка, значит цена игры равна: ',ALFA)
ELSE
writeln('');
WRITELN('Седловой точки нет, значит решение Симплекс метолом');
writeln('');
writeln('---------------------
WRITELN(' Результат работы программы смотрите в файле Reshenie.dat |');
writeln('---------------------
END;
ЗАКЛЮЧЕНИЕ
В разработанной курсовой работе я исследовала один из разделов теории принятия решений и исследования операций – Теория матричных игр.
В теоретических данных раскрыта идея теории, основные определения, формулы, алгоритмы решения задач и теоремы.
Данный проект заостряет внимание именно на играх размерностью m×n.
В результате была разработана программа, которая автоматизирует нахождение оптимального для каждого игрока решения и цены игры в целом. В руководстве пользователя я разобрала пример решения задачи матричной игры средствами написанной программы, результаты решения находятся в Приложении №1.
СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ
Цифровая литература:
Эксклюзивный дистрибьютор «В помощь студенту: Основы программирования».
Литература:
1. Фаронов В.В. Ф24 Delphi. Программирование на языке высокого уровня: Учебник для вузов – СПб.: Питер, 2005. 640 с.: ил.
2. Культин Н.Б. Основы программирования в Delphi/ - СПб.:ДХВ – Петербург,2003.
3. Курс лекций «Системный анализ».
2
Reshaem dlya 2-go igroka
C B H X1 X2 X3 X4 X5 X6 X7
0.0000 X5 1.0000 7.0000 8.0000 7.0000 5.0000 1.0000 0.0000 0.0000
0.0000 X6 1.0000 6.0000 7.0000 9.0000 8.0000 0.0000 1.0000 0.0000
0.0000 X7 1.0000 5.0000 8.0000 4.0000 6.0000 0.0000 0.0000 1.0000
0.0000 -1.0000 -1.0000 -1.0000 -1.0000 0.0000 0.0000 0.0000
Klyuchevoi stolbec 4 Kluchevaya stroka 2
C B H X1 X2 X3 X4 X5 X6 X7
0.0000 X5 0.3750 3.2500 3.6250 1.3750 0.0000 1.0000 -0.6250 0.0000
1.0000 X4 0.1250 0.7500 0.8750 1.1250 1.0000 0.0000 0.1250 0.0000
0.0000 X7 0.2500 0.5000 2.7500 -2.7500 0.0000 0.0000 -0.7500 1.0000
0.1250 -0.2500 -0.1250 0.1250 0.0000 0.0000 0.1250 0.0000
Klyuchevoi stolbec 2 Kluchevaya stroka 3
C B H X1 X2 X3 X4 X5 X6 X7
0.0000 X5 0.0455 2.5909 0.0000 5.0000 0.0000 1.0000 0.3636 -1.3182
1.0000 X4 0.0455 0.5909 0.0000 2.0000 1.0000 0.0000 0.3636 -0.3182
1.0000 X2 0.0909 0.1818 1.0000 -1.0000 0.0000 0.0000 -0.2727 0.3636
0.1364 -0.2273 0.0000 0.0000 0.0000 0.0000 0.0909 0.0455
Klyuchevoi stolbec 1 Kluchevaya stroka 1
C B H X1 X2 X3 X4 X5 X6 X7
1.0000 X1 0.0175 1.0000 0.0000 1.9298 0.0000 0.3860 0.1404 -0.5088
1.0000 X4 0.0351 0.0000 0.0000 0.8596 1.0000 -0.2281 0.2807 -0.0175
1.0000 X2 0.0877 0.0000 1.0000 -1.3509 0.0000 -0.0702 -0.2982 0.4561
0.1404 0.0000 0.0000 0.4386 0.0000 0.0877 0.1228 -0.0702
Klyuchevoi stolbec 7 Kluchevaya stroka 3
C B H X1 X2 X3 X4 X5 X6 X7
1.0000 X1 0.1154 1.0000 1.1154 0.4231 0.0000 0.3077 -0.1923 0.0000
1.0000 X4 0.0385 0.0000 0.0385 0.8077 1.0000 -0.2308 0.2692 0.0000
0.0000 X7 0.1923 0.0000 2.1923 -2.9615 0.0000 -0.1538 -0.6538 1.0000
0.1538 0.0000 0.1538 0.2308 0.0000 0.0769 0.0769 0.0000
V 5 -i iteracii bylo polucheno optimalnoe reshenie
t.k pri issledovanii na MAKSIMUM indecsnaya stroka ne soderjet otricatelnyh elementov
pri etom:
summa X = 0.1538
CENA IGRY = 6.5000
X1= 0.1154
X4= 0.0385
X7= 0.1923
Veroyatnosti:
VerX1= 0.7500
VerX4= 0.2500
Rezultat dlya 1-go igroka:
Veroyatnosty:
Ver= 0.5000
Ver= 0.5000
Ver= 0.0000
2