Введение……………………………………………………………………………………………..4

1.Постановка  задачи………………………………………………………………………………...5

1.1 Назначение и функции программы……………………………………………………………5

1.2 Математическая  формулировка задачи………………………………………….……….……5

1.3 Информационная база задачи…………………………………………………………………10

1.3.1 Входная информация…………………………………………………………………...……10

1.3.2 Выходная информация………………………………………………………………………10

1.4 Система меню……………………………………………………………………….…….……11

1.5 Контрольные примеры…………………………………………………………………….…..14

2 Описание программы……………………………………………………………………………14

3 Описание применения………………………………………………………………...…………16

Заключение…………………………………………………………………….................................17

Список используемых источников……………………………………………………….……….18

Приложение А (алгоритм программы и подпрограммы)………………………………..………19

Приложение Б (блок – схема)…………………………………………………………....….……..20

Приложение В (листинг программы)……………………………………………………...………21

     В последнее время резко возрос интерес к программированию. Это  связано с развитием и внедрением в повседневную жизнь информационно-коммуникационных технологий. Если человек имеет дело с компьютером, то рано или поздно у него возникает желание, а иногда и необходимость, программировать. Среди пользователей персональных компьютеров в настоящее время наиболее популярно семейство операционных систем Windows и, естественно, что тот, кто собирается программировать, стремится писать программы, которые будут работать в этих системах. Несколько лет назад рядовому программисту оставалось только мечтать о создании собственных программ, работающих в среде Windows, т. к. единственным средством разработки был Borland C++ for Windows, явно ориентированный на профессионалов, обладающих серьезными знаниями и опытом.

     Бурное  развитие вычислительной техники, потребность  в эффективных средствах разработки программного обеспечения привели к появлению систем программирования, ориентированных на так называемую "быструю разработку", среди которых можно выделить Borland Delphi и Microsoft Visual Basic. В основе систем быстрой разработки (RAD-систем, Rapid Application Development — среда быстрой разработки приложений) лежит технология визуального проектирования и событийного программирования, суть которой заключается в том, что среда разработки берет на себя большую часть рутинной работы, оставляя программисту работу по конструированию диалоговых окон и функций обработки событий. Производительность программиста при использовании RAD-систем -фантастическая!

       Delphi — это среда быстрой разработки, в которой в качестве языка программирования используется язык Delphi. Язык Delphi — строго типизированный объектно-ориентированный язык, в основе которого лежит хорошо знакомый программистам Object Pascal. В настоящее время программистам стала доступна очередная версия пакета Delphi - Borland Delphi 7 Studio. Как и предыдущие версии, Borland Delphi 7 Studio позволяет создавать самые различные программы: от простейших однооконных приложений до программ управления распределенными базами. В состав пакета включены разнообразные утилиты, обеспечивающие работу с базами данных, XML-документами, создание справочной системы, решение других задач. Отличительной особенностью седьмой версии является поддержка технологии .NETBorland Delphi 7 Studio может работать в среде операционных систем от Windows 98 до Windows XP. Особых требований, по современным меркам, к ресурсам компьютера пакет не предъявляет: процессор должен быть типа Pentium или Celeron с тактовой частотой не ниже 166 МГц (рекомендуется Pentium II 400 МГц), оперативной памяти - 128 Мбайт (рекомендуется 256 Мбайт), достаточное количество свободного дискового пространства  (для полной установки версии Enterprise необходимо приблизительно 475 Мбайт).

1.Постановка  задачи

     1.1 Назначение и функции программы

     Эта программа предназначена для  нахождения максимального и минимального элемента матрицы, а также седловой точки. Основное применение – экономика.

1.2 Математическая формулировка  задачи

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

       Матричная игра двух игроков  с нулевой суммой может рассматриваться как следующая абстрактная игра двух игроков.

       Первый  игрок имеет m стратегий i = 1,2,...,m, второй имеет n стратегий j = 1,2,...,n. Каждой паре стратегий (i,j) поставлено в соответствие число аij, выражающее выигрыш игрока 1 за счёт игрока 2, если первый игрок примет свою i-ю стратегию,

а второй – свою j-ю стратегию.

       Каждый  из игроков делает один ход: игрок 1 выбирает свою i-ю стратегию 

(i=), 2 – свою j-ю стратегию (j=), после чего игрок 1 получает выигрыш аij за счёт игрока 2 (если аij< 0, то это значит, что игрок 1 платит второму сумму | аij | ). На этом игра заканчивается.

       Каждая  стратегия игрока i=;  j=  часто называется чистой стратегией.

       Если  рассмотреть матрицу

А =

то проведение каждой партии матричной игры с матрицей А сводится к выбору игроком 1 i-й строки, а игроком 2 j-го столбца и получения игроком 1 (за счёт игрока 2) выигрыша аij.

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

аij     (i =)

т.е. определяется минимальный выигрыш для игрока 1 при условии, что он примет свою i-ю чистую статегию, затем из этих минимальных выигрышей отыскивается такая стратегия i = iо, при которой этот минимальный выигрыш будет максимальным, т.е. находится 

  аij  =              (1). 

     Определение.  Число , определённое по формуле (1) называется нижней чистой ценой игры и показывает, какой минимальный выигрыш может гарантировать себе игрок 1, применяя свои чистые стратегии при всевозможных действиях игрока 2.

   аij

т.е. определяется max выигрыш игрока 1, при условии, что игрок 2 применит свою j-ю чистую стратегию, затем игрок 2 отыскивает такую свою j = j1 стратегию, при которой игрок 1 получит min выигрыш, т.е. находит

aij = =                   (2).

     Определение. Число , определяемое по формуле (2), называется чистой верхней ценой игры и показывает, какой максимальный выигрыш за счёт своих стратегий может себе гарантировать игрок 1.

     Другими словами, применяя свои чистые стратегии, игрок 1 может обеспечить себе выигрыш не меньше , а игрок 2 за счёт применения своих чистых стратегий может не допустить выигрыш игрока 1 больше, чем .

     Определение. Если в игре с матрицей А  = , то говорят, что эта игра имеет седловую точку в чистых стратегиях и чистую цену игры u = , =.

     Седловая точка – это пара чистых стратегий (iо,jо) соответственно игроков 1 и 2, при которых достигается равенство  = . В это понятие вложен следующий смысл: если один из игроков придерживается стратегии, соответствующей седловой точке, то другой игрок не сможет поступить лучше, чем придерживаться стратегии, соответствующей седловой точке. Математически это можно записать и иначе:               (3)    

где i, j – любые чистые стратегии соответственно игроков 1 и 2; (iо,jо) – стратегии, образующие седловую точку.

     Таким образом, исходя из (3), седловой элемент  является минимальным в iо-й строке и максимальным в jо-м столбце в матрице А. Отыскание седловой точки матрицы А происходит следующим образом: в матрице А последовательно в каждой строке находят минимальный элемент и проверяют, является ли этот элемент максимальным в своём столбце. Если да, то он и есть седловой элемент, а пара стратегий, ему соответствующая, образует седловую точку. Пара чистых стратегий (iо,jо) игроков 1 и 2, образующая седловую точку и седловой элемент , называется решением игры. При этом iо и jо называются оптимальными чистыми стратегиями соответственно игроков 1 и 2.

     Седловой  точкой является пара (iо = 3; jо = 1), при которой u = = = 2.

     Заметим, что хотя выигрыш в ситуации (3;3) также равен 2 = = , она не является седловой точкой, т.к. этот выигрыш не является максимальным среди выигрышей третьего столбца.

       Из  анализа матрицы выигрышей видно, что  < , т.е. данная матрица не имеет седловой точки. Если игрок 1 выбирает свою чистую максиминную стратегию i = 2, то игрок 2, выбрав свою минимаксную j = 2, проиграет только 20. В этом случае игроку 1 выгодно выбрать стратегию i = 1, т.е. отклониться от своей чистой максиминной стратегии и выиграть 30. Тогда игроку 2 будет выгодно выбрать стратегию j = 1, т.е. отклониться от своей чистой минимаксной стратегии и проиграть 10. В свою очередь игрок 1 должен выбрать свою 2-ю стратегию, чтобы выиграть 40, а игрок 2 ответит выбором 2-й стратегии и т.д.

       Смешанное расширение матричной  игры.

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

       Определение. Смешанной стратегией игрока называется полный набор вероятностей применения его чистых стратегий.

       Таким образом, если игрок 1 имеет m чистых стратегий 1,2,...,m, то его смешанная стратегия x – это набор чисел x = (x1, ..., xm) удовлетворяющих соотношениям

xi ³ 0   (i = 1,m),    = 1.

       Аналогично  для игрока 2, который имеет n чистых стратегий, смешанная стратегия y –  это набор чисел

y = (y1, ..., yn),   yj ³ 0,  (j = 1,n),   = 1.

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

       Чистая  стратегия есть частный случай смешанной  стратегии. Действительно, если в смешанной  стратегии какая-либо i-я чистая стратегия  применяется с вероятностью 1, то все остальные чистые стратегии  не применяются. И эта i-я чистая стратегия является частным случаем смешанной стратегии. Для соблюдения секретности каждый игрок применяет свои стратегии независимо от выбора другого игрока.

E (A, x, y) =  = x A yT

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

       Е (А, х, y).

       Аналогичной должна быть ситуация и для игрока 2, т.е. нижняя цена игры должна быть   

       Е (А, х, y).

       Подобно играм, имеющим седловые точки в чистых стратегиях, вводится следующее определение: оптимальными смешанными стратегиями игроков 1 и 2 называются такие наборы хо, уо соответственно, которые удовлетворяют равенству 

       Е (А, х, y) = Е (А, х, y) = Е (А, хо, уо).

       Величина  Е (А, хо ,уо) называется при этом ценой игры и обозначается через u.

       Имеется и другое определение оптимальных  смешанных стратегий: хо, уо называются оптимальными смешанными стратегиями соответственно игроков 1 и 2, если они образуют седловую точку: Е (А, х, уо) £ Е (А, хо, уо) £ Е (А, хо, у)

       Оптимальные смешанные стратегии и цена игры называются решением матричной игры.

       Основная  теорема матричных игр имеет  вид :

       Теорема (о минимаксе). Для матричной игры с любой матрицей А величины 

       Е (А, х, y) и  Е (А, х, y)

существуют  и равны между собой

       Свойства  решений матричных  игр.

       Обозначим через G (Х,Y,А) игру двух лиц с нулевой  суммой, в которой игрок 1 выбирает стратегию х Î Х, игрок 2 – y Î U, после чего игрок 1 получает выигрыш А = А (х, y) за счёт игрока 2.

       Определение. Стратегия х1 игрока 1 доминирует (строго доминирует) над стратегией х2, если

       А (х1, y) ³ А (х2, y)   (А (х1, y) > А (х2, y)), y Î U.

       Стратегия y1 игрока 2 доминирует (строго доминирует) над стратегией y2, если

       А (х, y1) £ А (х, y2)  (А (х, y1) < А (х, y2)), х Î Х.

       При этом стратегии х2 и y2 называются доминируемыми (строго доминируемыми).

       Спектром  смешанной стратегии игрока в  конечной антагонистической игре называется множество всех его чистых стратегий, вероятность которых согласно этой стратегии положительна.

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

     Игра G¢ = (Х¢,Y¢,А¢) называется подыгрой игры G (Х,Y,А), если Х¢Ì Х, U¢Ì U, а матрица А¢ является подматрицей матрицы А. Матрица А¢ при этом строится следующим образом. В матрице А остаются строки и столбцы, соответствующие стратегиям Х¢ и U¢, а остальные “вычеркиваются”. Всё то что “останется” после этого в матрице А и будет матрицей А¢.

     Свойство 3. Пусть G = (Х,Y,А) – конечная антагонистическая  игра, G¢ = (Х х¢,Y,А) – подыгра игры G, а х¢ – чистая стратегия игрока 1 в игре G, доминируемая некоторой стратегией  , спектр которой не содержит х¢. Тогда всякое решение (хо, yо, u) игры G¢ является решением игры G.

     Свойство 4. Пусть G = (Х,Y,А) – конечная антагонистическая  игра, G¢ = (Х,Y y¢,А) – подыгра игры G, а y¢ – чистая стратегия игрока 2 в игре G, доминируемая некоторой стратегией , спектр которой не содержит y¢.Тогда всякое решение игры G¢ является решением G.

     Свойство 5. Если для чистой стратегии х¢ игрока 1 выполнены условия свойства 3, а  для чистой стратегии y¢ игрока 2 выполнены условия свойства 4, то всякое решение игры G¢ = (Х х¢,Y y¢,А) является решением игры G = (Х,Y,А).

     Свойство 6. Тройка (хо, yо, u) является решением игры G = (Х,Y,А) тогда и только тогда, когда (хо, yо, кu +а) является решением игры G(Х,Y,кА+а), где а – любое вещественное число, к > 0.

     Свойство 7. Для того, чтобы хо = была оптимальной смешанной стратегией матричной игры с матрицей А и ценой игры u, необходимо и достаточно выполнение следующих неравенств

        (j =)

     Аналогично  для игрока 2 : чтобы yо = (, ...,, ...,) была оптимальной смешанной стратегией игрока 2 необходимо и достаточно выполнение следующих неравенств:

              ((j =)           

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

     ,              

получим решение матричной игры.

     Таким образом, решение матричной игры сводится к нахождению неотрицательных  параметров решений линейных неравенств (*) (**) и линейных уравнений (***). Однако это требует большого объёма вычислений, которое растёт с увеличением числа чистых стратегий игроков. (Например для матрицы 3 3 имеем систему из 6 неравенств и 2 уравнений). Поэтому в первую очередь следует, по возможности используя свойства 2 и 3, уменьшить число чистых стратегий игроков. Затем следует во всех случаях проверить выполнение неравенства

        = .

Замечание. Отметим, что исключение доминируемых (не строго) стратегий может привести к потере некоторых решений. Если же исключаются только строго доминируемые стратегии, то множество решений игры не изменится.

       1.3 Информационная база  задачи

  1. Для матричной игры, заданной платёжной матрицей A, найти:

1. Максиминную стратегию игрока 1;
2. Минимаксную стратегию игрока 2;
3. Седловую точку;

1.3.1 Входная информация

     Создаем матрицу размерностью 4/5.

   Нахадим:

1. Максиминную стратегию игрока 1;
2. Минимаксную стратегию игрока 2;
3. Седловую точку;
4. Цену игры.

1.3.2 Выходная информация

Максиминные стратегии игрока 1 определяются по формуле:

Для строк  таблицы получаем следующие значения :(0, 3, 7, 4, 7).

Максимумов  два: для 3-й строки и для 5-й. Они  равны 7. Таким образом, игрок 1 имеет  две максиминные стратегии: 3 и 5.

Минимаксные стратегии игрока 2 ищутся по формуле:

Для столбцов таблицы получаем такие значения :(13, 7, 17, 7).

Седловых  точек четыре: (3,2); (5,2); (3,4); (5,4).

Первая  цифра в скобках – номер  выбранной стратегии для игрока 1, вторая – для игрока 2.

Цена  игры равна 7.

1.4 Система меню

Рабочее поле состоит из:

Button 1 (Создать таблицу!);

Button 2 (Выполнить!);

Label 1 (Количество строк);

Label 2 (Количество столбцов);

Label 3 (Седловая точка);

Edit 1

Edit 2

Edit 3

StringGrid1 (Таблица).

Рис.1

1.5 Контрольные примеры

     Пример  №1

Задаём  матрицу размерностью 4/4, как показано на Рис.2

Программа выводит седловую точку: mas[4,4]=5.

Рис.2 

       Пример 2

Задаём  матрицу размерностью 3/3, как показано на Рис.3

Программа выводит седловую точку mas[3,3]=4

   Рис.3 

     Пример 3

Задаём  матрицу размерностью 2/2, как показано на Рис.4

Программа выводит седловую точку mas[2,2]=3

   Рис.4

       Запускаем программу, Рис 5

       Рис 5

       Вводим  количество строк-5, количество столбцов-5, затем нажимаем кнопку «Создать таблицу» как показано на Рис.6

       Рис.6

       Заносим значения в таблицу, затем нажимаем кнопку «Выполнить», как показано на Рис.7

       Программа выводит ответ: mas[5,5]=6

Программа применяется в сфере экономики. Больше всего седловая точка применятся в играх: позиционные игры, матричные игры, антагонистические игры, игры порядка 2 х 2…

В курсовой работе были рассмотрены следующие  вопросы: рассмотрена характеристика «Теории игр» и следующие методы её решения: метод Седловой точки, метод максимина, метод минимакса.

1. http://www.bestreferat.ru
2. http://www.referat.ru
3. Петросян, Зенкевич, Семина «Теория игр»
4. http://www.INTUIT.ru
5. http://pascal.sources.ru