Теория принятия решений
–
–
––
После этого повторяем 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 –
= –
![]()
Пересчитываем и заполняем строку оценок:
![]()
–
–
–
![]()
–
–
–
![]()
––
––
–
–
![]()
– 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. Это гораздо быстрее и удобнее.#
Ответ:
смешанная
стратегия для
первого игрока
Р =
,
смешанная
стратегия для
второго игрока
Q =
,
цена игры
n =
.
4.2.3 Решение задачи графическим методом
Симплекс-методом можно найти решение матричной игры произвольной размерности. Графическим же способом найти решение можно лишь для игры размерности 2 х n.
В ответе мы должны получить смешанные стратегии – два вектора PA = (p1, p2) и QB = (q1, q2, …, qn). Причем, p2 = 1 – p1.
В этом случае выигрыш игрока А, соответствующий j-той чистой стратегии игрока В, будет вычисляться по формуле:
aj* = a1j p1 + a2j p2 = a1j p1 + a2j (1 – p1) = (a1j – a2j) p1 + a2j
Нахождение наименьшего гарантированного выигрыша для игрока А подразумевает минимизацию данного выражения.
По условию
наша игра имеет
размерность
2 х n.
То есть j =
. В итоге будем
иметь n аналогичных
выражений,
которые надо
минимизировать.
После этого
согласно принципу
максимина из
найденных
минимумов нужно
выбрать наибольший:
a =
![]()
Решим графическим способом предыдущий числовой пример.

В данном случае будем иметь четыре уравнения, соответствующие четырем возможным чистым стратегиям игрока В:a1* = р1 + 3
a2* = –4р1 + 7
a3* = 7р1 + 1
a4* = –р1 + 3
Чтобы определить наилучший результат из наихудших, построим нижнюю огибающую четырех заданных прямых (на рисунке выделена жирной линией). Эта огибающая представляет минимальный гарантированный выигрыш игрока А, независимо от того, что делает игрок В. Точка максимума нижней огибающей – это и есть решение задачи по принципу максимина. Координатами этой точки будут р1 – одна из вероятностей смешанной стратегии игрока А и a – выигрыш игрока А.
# Заметим, что содержательной является только часть графика, заключенная в интервале 0 ≤ р1 ≤ 1 . Все линии и точки, лежащие за пределами этого интервала не принимаются во внимание. #
"На глаз" координаты точки максимума нижней огибающей видны плохо. Точка максимума нижней огибающей – это точка пересечения прямой 3 и прямой 4. Найдем её точные координаты, решив систему соответствующих уравнений:
Ю
Ю
Ю
Далее находим
p2: p2 = 1 –
p1 = 1 –
=
![]()
Итак, для игрока А все ясно:
смешанная
стратегия
игрока А: Р =
,
выигрыш игрока
А:a =
.
Аналогичные рассуждения нужно повторить и для игрока В.
Точка максимума нижней огибающей – это точка пересечения прямой 3 и прямой 4. Значит оптимальная смешанная стратегия игрока В определяется двумя стратегиями В3 и В4 соответственно.
Проигрыш игрока В, соответствующий i-той чистой стратегии игрока A, будет вычисляться по формуле:
вi* = ai3 q3 + ai4 q4