Пусть мы выбрали свою оптимальную стратегию S*_A . Тогда наш средний выигрыш при стратегии противника будет равен:

 

  
Наша оптимальная стратегия S*_A обладает тем свойством, что при любом поведении противника обеспечивает выигрыш не меньший, чем ; следовательно, любое из чисел не может быть меньше . Получаем ряд условий:

  (1)

 Разделим  неравенства (1) на положительную величину и обозначим :

 

   Тогда условие (1) запишется виде

  (2)

 где — неотрицательные числа. Так как величины удовлетворяют условию

  (3)

 Мы  хотим сделать свой гарантированный  выигрыш максимально возможным; очевидно, при этом правая часть  равенства (3) принимает минимальное значение.

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

 была  минимальной.

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

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

 Задача  линейного программирования ставится следующим образом.

 Дана  система линейных уравнений:

  (4)

 Требуется найти неотрицательные значения величин удовлетворяющие условиям (4) и вместе с тем обращающие в минимум заданную однородную линейную функцию величин (линейную форму):

 

 Легко убедиться, что поставленная выше задача теории игр является частным случаем  задачи линейного программирование при 

 С первого  взгляда может показаться, что  условия (2) не эквивалентны условиям (4), так как вместо знаков равенства они содержат знаки неравенства. Однако от знаков неравенства легко избавиться, вводя новые фиктивные неотрицательные переменные и записывая условия (2) в виде:

  (5)

 Форма Ф , которую нужно обратить в минимум, равна

 

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

1.3 Симплекс метод (минимум)

 Симплекс  метод - универсальный метод для  решения линейной системы уравнений  или неравенств и линейного функционала.

 Общая идея симплексного метода (метода последовательного улучшения плана) для решения ЗЛП (задачи линейного программирования) состоит

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

 Пусть ЗЛП представлена системой ограничений  в каноническом виде:

.

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

 Пусть система ограничений имеет вид

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

 

,

   которая имеет предпочтительный  вид 

 

.

 В целевую  функцию дополнительные переменные вводятся с коэффициентами, равными нулю .

 Пусть далее система ограничений имеет  вид

 

 Сведём  её к эквивалентной вычитанием дополнительных переменных   из левых частей неравенств системы. Получим систему

 

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

 Пусть исходная ЗЛП имеет вид 

        (1)

      (2)

             (3)

 причём  ни одно из ограничений не имеет предпочтительной переменной. М-задача запишется так:

       (4)

             (5)

    , ,         (6)

 Задача (4)-(6) имеет предпочтительный план. Её начальный опорный план имеет  вид

 

 Если  некоторые из уравнений (2) имеют предпочтительный вид, то в них не следует вводить искусственные переменные.

Теорема. Если в оптимальном плане 

           (7)

 М-задачи (4)-(6) все искусственные переменные , то план является оптимальным планом исходной задачи (1)-(3).

 Для того чтобы решить задачу с ограничениями, не имеющими предпочтительного вида, вводят искусственный базис и  решают расширенную М-задачу, которая  имеет начальный опорный план

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

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

 Теорема. Если в оптимальном плане М-задачи хотя бы одна из искусственных переменных отлична от нуля, то исходная задача не имеет допустимых планов, т. е. ее условия несовместны.

 Признаки  оптимальности.

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

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

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

1. Ограничения вида «0»- ресурсные ограничения. Справа находится то что мы используем на производстве, слева - то что получаем. При таких ограничения вводят дополнительные переменные с коэффициентом «+1», образующие единичный базис. В целевую функцию эти переменные войдут с коэффициентом «0».
2. Ограничения вида «=». Часто бывает, что несмотря на то что ограничения имеют вид равенства, единичный базис не выделяется или трудно выделяется. В этом случае вводятся искусственные переменные для создания единичного базиса - Yi. В систему ограничений они входят с коэффициентом «1». а в целевую функцию с коэффициентом «M», стремящимся к бесконечности (при Fmin - «+M», при Fmax - «-M»).
3. Ограничения вида «0» - Плановые ограничения. Дополнительные переменные (X), несущие определенный экономический смысл - перерасход ресурсов или перевыполнение плана, перепроизводство, добавляются с коэффициентом «-1», в целевую функцию - с коэффициентом «0». А искусственные переменные (Y) как в предыдущем случае.

1.4 Алгоритм решения задач теории игр

 Обозначим некоторые определения.

 Седловой  точкой называется А_ij, которая является наименьшим элементом в своей строке и наибольшим элементом в столбце.

 Доминирующая  строка – все элементы этой строки не превосходят соответствующих  элементов другой строки.

 Доминирующий  столбец – все элементы не меньше соответствующих элементов какого-либо другого столбца.

 Доминирующие  столбцы и строки можно удалить из матрицы. 

 Алгоритм  решения

1. Проверить наличие седловой точки. Если есть седловая точка, то пишем ответ, если нет - продолжаем решение дальше
2. Удаляем доминирующие строки доминирующие столбцы. Их може6т быть несколько. На их место в оптимальной стратегии соответствующие компоненты будут равны 0
3. Решаем матричную игру (линейное программирование, графическое решение, приближенное решение)

В своей  задаче я решаю матричную игру линейным программированием. (Симплекс метод)

Алгоритм  решения симплекс методом (на максимум):

1. Привести задачу линейного программирования к каноническому виду.
2. Найти начальное опорное решение с базисом из единичных векторов и коэффициенты разложений векторов условий по базису опорного решения. Если опорное решение отсутствует, задача не имеет решения ввиду несовместности системы ограничений.
3. Вычислить оценки разложений векторов условий по базису опорного решения и заполнить симплексную таблицу.
4. Если выполняется признак единственности оптимального решения, то решение задачи заканчивается.
5. Если выполняется условие существования множества оптимальных решений, то путем простого перебора найти все оптимальные решения.
6. Если имеют место условия неограниченности целевой функции, то задача не имеет решения.
7. Если пункты 4—6 алгоритма не выполняются, найти новое опорное решение и перейти к пункту 3.

 

2 СПЕЦИАЛЬНАЯ ЧАСТЬ (РАСЧЕТНАЯ)

2.1 Исходные данные