2. Теоретическая часть

 

   Теория  игр – это совокупность математических методов анализа и оценки конфликтных ситуаций.

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

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

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

   Игры  можно классифицировать по различным  признакам: стратегические и чисто  случайные, бескоалиционные и коалиционные, игры 1, 2, …, n лиц (по числу игроков), конечные и бесконечные (по числу стратегий), игры в нормальной форме и динамические, с нулевой суммой («антагонистические») и с ненулевой суммой.

   Рассмотрим  простейшую модель – игру, в которой участвуют два игрока, множество стратегий каждого игрока конечно, а выигрыш одного игрока равен проигрышу другого (бескоалиционная, конечная, антагонистическая игра двух лиц). Такую игру (Г) называют матричной. Она определяется тройкой Г=(X,Y,K), где Х – множество стратегий 1-го игрока, Y – множество стратегий 2-го игрока, K=K(x,y) – функция выигрыша (выигрыш 1-го игрока и соответственно проигрыш 2-го при условии, что 1-й игрок выбрал стратегию  , а 2-й – стратегию  ). Пару (x,y) называют ситуацией в игре Г.

   Пусть 1-й игрок имеет всего m стратегий, а 2-й – n стратегий: Х=М={1,2, …, m}, Y=N={1,2, …, n}. Тогда игра Г полностью определяется заданием матрицы  , где a_ij=K(i,j) – выигрыш 1-го игрока при условии, что он выбрал стратегию (т.е. строку) i, а 2-й игрок – стратегию (т.е. столбец) j (эти стратегии называют чистыми).

   Матрица А называется матрицей игры или платежной матрицей.

   Пусть матрица игры  . Цель каждого игрока – получить как можно больший выигрыш. Но 1-му игроку нет смысла выбирать стратегию i=1 в надежде выиграть 5 ед., так как 2-й игрок, действуя разумно, не станет выбирать стратегию j=2, чтобы не проиграть максимальную сумму 5 ед. Игрокам удобнее выбрать «осторожные» стратегии.

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

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

   Схема:

   

   Например, 

   Соответствующие стратегии: i₀=1 (максиминная), j₀=1,2 (минимаксная).

   Справедливо неравенство:  .

   В игре Г естественно считать оптимальной такую ситуацию (i,j), от которой ни одному из игроков невыгодно отклоняться.

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

   Ситуация  равновесия существует тогда и только тогда, когда   (это значение и является ценой игры v).

   Например, 

   (2,3)-ситуация  равновесия, v=4 – цена игры, i^*=2, j^*=3 – оптимальные стратегии 1-го и 2-го игроков. Выбрав их, 1-й игрок обеспечит себе выигрыш не менее 4 ед., а 2-й игрок проиграет не более 4 ед. при любом выборе другого игрока.

   Наряду  с чистыми стратегиями игроков  рассматривают также смешанные стратегии.

   Смешанной стратегией для 1-го игрока называется упорядоченная система m действительных чисел x=(x₁, x₂, …, x_m),  ,  , которые можно рассматривать как относительные частоты (вероятности), с которыми 1-й игрок выбирает чистые стратегии i=1, 2, …, m.

   Аналогично  определяется смешанная стратегия  для 2-го игрока: y=(y₁, y₂, …, y_n),  ,  .

   Множества всех смешанных стратегий 1-го и 2-го игроков будем обозначать соответственно S_m и S_n.

   Чистые  стратегии можно рассматривать  как частный случай смешанных  стратегий. Например, чистую стратегию j=2 можно рассматривать как смешанную y=(0,1,0,…,0), чистую стратегиюi=1 – как смешанную x=(1,0,…,0).

   Пару  смешанных стратегий (x,y) называют ситуацией в смешанных стратегиях.

Функция выигрыша K(x,y) в ситуации (x,y) определяется как математическое ожидание выигрыша 1-го игрока при условии, что 1-й и 2-й игроки выбрали соответственно стратегии x=(x₁, x₂, …, x_m) и y=(y₁, y₂, …, y_n):  .

   Если  для некоторых   и   и для всех   и   выполняется неравенство  , то x^*, y^* называются оптимальными смешанными стратегиями игроков, число  называется ценой игры, пара (x^*, y^*) – стратегической седловой точкой, а тройка x^*, y^*, v – решением игры.

   Основная  теорема теории матричных  игр, или теорема о минимаксе. Если  – матрица игры Г и для всех   и    , то величины   и   существуют и равны между собой (эта величина и является ценой игры v).

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

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

 Действительно, путь необходимо исследовать на экстремум  линейную функцию

 Z = С₁х₁+С₂х₂+... +С_Nx_N

 при линейных ограничениях

 a₁₁x₁ + a₂₂x₂ + ... + a_1NХ_N = b₁

 a₂₁x₁ + a₂₂x₂ + ... + a_2NХ_N = b₂

 . . . . . . . . . . . . . . .

 a_М1x₁ + a_М2x₂ + ... + a_МNХ_N 

 

 Так как Z - линейная функция, то Z = С_j, (j = 1, 2, ..., n), то все коэффициенты линейной функции не могут быть равны нулю, следовательно, внутри области, образованной системой ограничений, экстремальные точки не существуют. Они могут быть на границе области, но исследовать точки границы невозможно, поскольку частные производные являются константами.

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

Решение задач линейного  программирования средствами табличного процессора Excel.

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

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

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

Решение задачи линейного программирования средствами табличного процессора Excel осуществляется в режиме Сервис/Поиск  решения, открывается диалоговое окно «Поиск решения». Здесь указывается  ячейки целевой функции, переменных и устанавливаются ограничения  исходя из системы ограничений. Можно  начать решение, или установить «параметры»  решения .

Решением  задачи является рассчитываемый надстройкой  Поиск решения набор переменных X = (x1, x2 ,..., xn), обеспечивающий максимальное (минимальное, заданное) значение целевой  функции E(x1, x2 ,..., xn).

     Следующим этапом при подготовке задачи к решению  является программирование математических выражений, связывающих между собой  исходные числовые данные и вычисляемые выражения. Электронные таблицы Excel позволяют записывать в выбранную ячейку не только числа, но и математические выражения, составленные по общим правилам языков программирования с использованием символа присваивания =, знаков операций (+,–,*,/) и встроенных функций. В качестве операндов в таких выражениях могут использоваться константы или имена ячеек Excel.

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