Проверим, имеет ли наша матричная игра седловую точку? Для этого используем принцип максимина.
Выигрыш игрока А:a = = 2 он достигается в первой строке.
Выигрыш игрока В:в = = 3 он достигается в четвертом столбце.
Как видим, выигрыши игроков не совпадают, значит у матрицы нет седловой точки. Значит, нужно искать смешанные стратегии.
В данном конкретном случае в множестве ограничений будет четыре неравенства (т.к. в условии задачи четыре столбца). Пересчитывать симплекс- таблицы с четырьмя строками не очень сильно хочется, поэтому удобнее решить двойственную задачу (для коэффициентов вектора смешанной стратегии второго игрока), в которой будет всего две строки (т.к. в условии задачи две строки):
найти вектор двойственных переменных Y = {y1, y2, … yn}, такой что:
целевая функция g = max
при множестве ограничений:АY ≤ Е
Для нашего примера задача линейного программирования будет такой:
найти вектор Y = {y1, y2, y3, y4}, такой что:
целевая функция g = max
при множестве ограничений:
Далее нужно вспомнить методику применения симплекс-метода и использовать её для нашей задачи.
Однако, как показывает многолетняя практика, студенты обладают так называемой "краткосрочной памятью", которая работает только до сдачи необходимого экзамена. Поэтому вспомнить сейчас методику применения симплекс-метода вряд ли кто-то сможет. Для этого нужно сходить в библиотеку, найти специальную литературу и умело ей воспользоваться. Осмелимся заметить, что и этого половина студентов сделать поленится и благополучно завалит данную тему J . #
Поэтому для всеобщего блага приведем здесь методику применения симплекс-метода (пройденного и успешно сданного в математическом программировании) для нашей конкретной задачи.
1 этап – приведение задачи линейного программирования к каноническому виду.
Неравенства во множестве ограничений нужно превратить в равенства с помощью добавления искусственных переменных. Для того чтобы неравенства превратить в равенства, надо в каждое неравенство добавить (или отнять – в зависимости от знака неравенства) искусственную переменную:
Целевая функция при этом будет выглядеть так:g = y1 + y2 + y3 + y4 + 0y5 + 0y6
2 этап – определение начального опорного плана.
В полученном случае начальный опорный план будут составлять искусственные переменные, входящие в ограничения с коэффициентами +1 :{ y5 ; y6 }. Новых искусственных переменных для данной задачи вводить не требуется.
3 этап – заполнение исходной симплекс-таблицы.
Исходная симплекс-таблица для нашей двойственной задачи будет иметь вид:
В столбец "текущий базис" ставим переменные, начального опорного плана : { y5 ; y6 }.
В столбец "сi" ставим их коэффициенты в целевой функции.
В столбец "А0" ставим вектор ограничений Е : а10 = 1 ;а20 = 1 .
В самую верхнюю строку таблицы ставим коэффициенты cj при соответствующих переменных в целевой функции:c1 = 1 ; c2 = 1 ; c3 = 1 ; c4 = 1 ; c5 = 0 ; c6 = 0 .
В столбцы "А1", ...., "А6" ставим соответствующие коэффициенты матрицы ограничений А.
Вычисляем оценки по формулам
D0 = ; .Dj = – cj
и ставим их в самую нижнюю строку симплекс-таблицы (строку оценок) :
1. Если j ³ 0 для всех j = 1, 2, .... , n , то данный план (в столбце "текущий базис") – оптимален. В нашем случае это условие не выполняется, значит, текущий базис можно улучшить.
2. Если имеются k < 0 и в столбце Аk все элементы aik 0 , то целевая функция не ограничена сверху на допустимом множестве и данная задача не имеет смысла. В нашем случае видим, что целевая функция сверху ограничена.
3. Если имеются j < 0 и в столбцах Аj , соответствующих этим оценкам, существует хотя бы один элемент aik > 0, то возможен переход к новому лучшему плану, связанному с большим значением целевой функции. У нас так и есть.
4. Переменная хk, которую необходимо ввести в базис, для улучшения плана соответствует наименьшей отрицательной оценке j. Столбец Ak, содержащий эту оценку называется ведущим. В нашем случае все оценки одинаковы. Поэтому в качестве ведущего столбца выберем любую оценку, например, третью: k = 3.
5. Ищем min{ ai0 / ai1 } = min{ 1/8 ; 1/1 } = 1/8– этот минимум достигается при i = 1. Значит, r = 1первая строка – ведущая. (на рисунке помечена стрелкой)
Ведущий элементark = a13 = 8 (на рисунке выделен)
6. Заполняем новую симплекс-таблицу.
В столбец "текущий базис" вместо переменной у5 ставим переменную у3 .
В столбец "сi" ставим коэффициент переменной у3 в целевой функции.
Самая верхняя строка таблицы всегда остаётся неизменной.
Пересчитываем ведущую строку по формуле :
После этого пересчитываем остальные строки по формуле
После этого повторяем 4 этап до тех пор, пока не будет выполнен п.1 (все j ³ 0).
В нашем случае имеются j < 0 и наименьшая среди них 4 . Значит ведущим столбцом на данном шаге будет A4 (пометим его стрелкой).
Ищем min{ ai0 / ai4 } = min{ : ; : } = min{ ; } = – этот минимум достигается при i = 2. Значит, r = 2вторая строка – ведущая (на рисунке помечена стрелкой).
Таким образом, в новый текущий базис вместо переменной у6 надо ввести переменную у4 .
Пересчитываем все элементы новой симплекс-таблицы.
Пересчитываем ведущую строку (вторую):
= : = = = : = =
= : = = = 0 : = 0
= : = 1 = – : = – = 1 : =
Приведенные выше и ниже вычисления представлены в весьма подробном виде. Это сделано из тех соображений, что как опять таки показывает практика, даже не смотря на достаточно хорошее понимание и усвоение теоретического материала, ошибки зачастую возникают именно при выполнении элементарных арифметических операций. Не следует думать, что средняя школа осталась позади, и вы всё можете посчитать в уме. Поэтому всем студентам мы советуем не лениться и подробно расписывать все арифметические действия (особенно с дробями).#
Пересчитываем оставшуюся строку (первую):
= – = – = =
= – = – = =
= – = – = – = –
= 1 – 0 = 1 = – = 0
= – = + = =
= 0 – = –
Пересчитываем и заполняем строку оценок:
D0 = = 1 * + 1 * = =
D1 = – c1 = 1 * + 1 * – 1 = – =
D2 = – c2 = 1 * + 1 * – 1 = – = =
D3 = – c3 = 1 * 1 + 1 * 0 – 1 = 0
D4 = – c4 = 1 * 0 + 1 * 1 – 1 = 0
D5 = – c5 = 1 * + 1 * – 0 = =
D6 = – c6 = 1 + 1 – 0 =
Повторяем 4-й этап. При проверке п. 1 видим, что все j ³ 0 . Следовательно, данный план {у3, у4} (в столбце "текущий базис") – оптимален. Больше пересчитывать симплекс-таблицу не нужно.
Решение задачи линейного программирования полностью содержится в последней симплекс-таблице.
Значения переменных находятся в столбце А0 возле соответствующих переменных. В нашем случае, мы видим, что у3 = , у4 = . Переменные у1 и у2 не входят в базис, поэтому их значения будут равны нулю. Таким образом, вектор переменных будет выглядеть так: Y = .
Значение целевой функции – это значение оценки 0 . В нашем случае g = 0 = .
Значения двойственных переменных находятся в строке оценок возле искусственных переменных. В нашем случае это 5 и 6 , то есть х1 = , х2 = . Таким образом, вектор двойственных переменных будет выглядеть так:Х = .
Итак, мы получили решение прямой задачи (которая у нас была двойственной): Y =
и двойственной задачи к данной (которая у нас была прямой):
Х =
Значения целевых функций при этом будут совпадать:f = g = .
Найдем цену игры:n = =
Далее найдем коэффициенты смешанной стратегии
для первого игрока по формуле рi = :
Р = = ,
для второго игрока по формуле qi = :
Q = = .
Особо "продвинутые" студенты при нахождении решения задачи линейного программирования, чтобы не считать симплекс-метод вручную академическим способом, могут воспользоваться средствами MS Excel. Это гораздо быстрее и удобнее.#
Ответ: смешанная стратегия для первого игрока Р = ,
= 2 он достигается в первой строке.
= 3 он достигается в четвертом столбце.
max
max
; .Dj = 
– cj
– c1 = 0 * 4 + 0 * 3 – 1 = – 1
– c2 = 0 * 3 + 0 * 7 – 1 = – 1D3 = 
– c3 = 0 * 8 + 0 * 1 – 1 = – 1
– c4 = 0 * 2 + 0 * 3 – 1 = – 1D5 = 
– c5 = 0 * 1 + 0 * 0 – 0 = 0
– c6 = 0 * 0 + 0 * 1 – 0 = 0
0 , то целевая функция не ограничена сверху на допустимом множестве и данная задача не имеет смысла. В нашем случае видим, что целевая функция сверху ограничена.
:
:
+ 0 * 
= 
+ 0 * 
– 1 = – 
+ 0 * 
– 1 = – 
D3 = 
+ 0 * 
– 1 = – 
– 0 = 
} = 
= 
= 
= 
= 
= 0 : 
= 
= – 
= 1 : 
= 
– 
= 
= 
= 
– 
= 
= 
= 
– 
= – 
= – 
= 1 – 0 
= 
= 
= 
= 
= 0 – 
= 
– 
= 
+ 1 * 
– 
= 
= 
= 
+ 1 
.
.
= 
:
= 
,
:
= 
.
,