Автор: Пользователь скрыл имя, 20 Февраля 2012 в 11:28, курсовая работа
Целью данного проекта является разработка программы, которая посредствам вычислений определяла оптимальные стратегии для каждого игрока и цену матричной игры в целом. Кроме того, предусматривается возможность не только получить конечный ответ, но и просмотреть промежуточные вычисления решения задачи.
ВВЕДЕНИЕ 5
ГЛАВА 1: ТЕОРИЯ ИГР 6
1.1 Понятие игры 6
1.2 Основные определения 8
1.3 Конечная парная антагонистическая игра 9
1.4 Теорема фон Неймана 10
1.5 Игра размерностью m×n 11
ГЛАВА 2: РАЗРАБОТКА 14
2.1 О среде разработки – Turbo Pascal 14
2.2 Руководство пользователя 15
2.3 Используемые процедуры и функции 18
ЗАКЛЮЧЕНИЕ 22
СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ 23
дробное, то есть программа будет округлять все промежуточные и конечное решения до Epsilon = 0.00001 (Рис.2).
Рис.2 – Выбор целочисленного решения или нет
3. Далее вводятся непосредственно элементы платежной матрицы (Рис.2)
Рис.3 – Ввод элементов матрицы
4. Затем, программа выводит на печать исходную матрицу, проверяет ее на наличие Седловой точки. Если Седлова точка есть, то на этом этапе работа программы прекращается, ответ выводится на экран (Например, в матрице Седлова точка равна 1(Рис.4)).
Рис.4 – Вывод решения при наличии Седловой точки
5. Если Седловой точки нет, то задача решается симплекс методом, решение сохраняется в файл RESHENIE.DAT (Результат вычислений для приведенного примера находится в приложении1).
Рис.5 – Вид окна программы в случае отсутствия Седловой точки
Для легкого чтения, компилирования и модернизации программного кода я использовала прием дробления программы на подпрограммы.
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