Матричная игра. Использование симплексного метода

Задание. Предприятие выпускает скоропортящуюся продукцию, которую сразу можно доставить потребителю (А1 стратегия). Отправить на склад для хранения (А2 стратегия) или подвергнуть обработке для длит. Хранения (А3 стратегия) . Потребитель может приобрести немедленно (В1 стратег) ,через некоторое время (В2 стратег) или после длительного периода (В3 стратегия).
В случае стратегий А2 и А3 предприятие несет дополнительные затраты на хранение и обработку продукции. Однако, при А2 следует вычесть убытки, если потребитель выберет стратегию В2 или В3 . Определить оптимальные пропорции для применения стратегий А1,А2,А3. Руководствуясь минимаксным критерием, гарантирует средний уровень убытка. Пользуясь минимальным критерием из таблицы.
Игроки B1 B2 B3 a = min(Ai)
A1 2 3 2 2
A2 4 2 1 1
A3 1 3 3 1
b = max(Bi ) 4 3 3 0

Решение матричной игры находим через сервис решение матричной игры.
Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(ai) = 2, которая указывает на максимальную чистую стратегию A1.
Верхняя цена игры b = min(bj) = 3.
Что свидетельствует об отсутствии седловой точки, так как a<>b, тогда цена игры находится в пределах 2 <= y <= 3. Находим решение игры в смешанных стратегиях. Переходим к этапу сведения матричной игры к задаче линейного программирования.
Математические модели пары двойственных задач линейного программирования можно записать так:
найти минимум функции F(x) при ограничениях:
2x1+4x2+x3 >= 1
3x1+2x2+3x3 >= 1
2x1+x2+3x3 >= 1
F(x) = x1+x2+x3 = min
найти максимум функции Ф(y) при ограничениях:
2y1+3y2+2y3 <= 1
4y1+2y2+y3 <= 1
y1+3y2+3y3 <= 1
Ф(y) = y1+y2+y3 = max
Решаем эти системы симплекс-методом.
Решим прямую задачу линейного программирования  симплексным методом, с использованием симплексной таблицы.
Определим минимальное значение целевой функции F(X) = x1 + x2 + x3 при следующих условиях-ограничений.
2x1 + 4x2 + x3≥1
3x1 + 2x2 + 3x3≥1
2x1 + x2 + 3x3≥1
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
2x1 + 4x2 + 1x3-1x4 + 0x5 + 0x6 = 1
3x1 + 2x2 + 3x3 + 0x4-1x5 + 0x6 = 1
2x1 + 1x2 + 3x3 + 0x4 + 0x5-1x6 = 1
Поскольку задача решается на минимум и элементы единичной матрицы отрицательны, сведем задачу к нахождению максимума. Для этого умножим все строки на (-1) и будем искать первоначальный опорный план.
-2x1-4x2-1x3 + 1x4 + 0x5 + 0x6 = -1
-3x1-2x2-3x3 + 0x4 + 1x5 + 0x6 = -1
-2x1-1x2-3x3 + 0x4 + 0x5 + 1x6 = -1
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных:
x4, x5, x6,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,0,-1,-1,-1)

План Базис B x1 x2 x3 x4 x5 x6
0 x4 -1 -2 -4 -1 1 0 0
x5 -1 -3 -2 -3 0 1 0
x6 -1 -2 -1 -3 0 0 1
Индексная строка F(X0) 0 1 1 1 0 0 0

В столбце свободных членов есть отрицательные элементы. Используем двойственный симплекс-метод. Выберем из них наибольший по модулю, а в его строке – любой отрицательный. Взяв этот элемент в качестве разрешающего пересчитаем таблицу.
В качестве ведущего выберем столбец, соответствующий переменной x1.
1-ая строка является ведущей.
План Базис B x1 x2 x3 x4 x5 x6 min
x1 1/2 1 2 1/2 -1/2 0 0 0
x5 1/2 0 4 -11/2 -11/2 1 0 0
x6 0 0 3 -2 -1 0 1 0
Индексная строка F(X) -1/2 0 -1 1/2 1/2 0 0 0

Представим расчет каждого элемента в виде таблицы:
B x1 x2 x3 x4 x5 x6
1/2 : 1 1 : 1 2 : 1 1/2 : 1 -1/2 : 1 0 : 1 0 : 1
1/2-(1/2•0):1 0-(1•0):1 4-(2•0):1 -11/2-(1/2•0):1 -11/2-(-1/2•0):1 1-(0•0):1 0-(0•0):1
0-(1/2•0):1 0-(1•0):1 3-(2•0):1 -2-(1/2•0):1 -1-(-1/2•0):1 0-(0•0):1 1-(0•0):1
-1/2-(1/2•0):1 0-(1•0):1 -1-(2•0):1 1/2-(1/2•0):1 1/2-(-1/2•0):1 0-(0•0):1 0-(0•0):1

В базисном столбце все элементы положительные.
Переходим к основному алгоритму симплекс-метода.
План Базис B x1 x2 x3 x4 x5 x6 min
1 x1 1/2 1 2 1/2 -1/2 0 0 1/4
x5 1/2 0 4 -11/2 -11/2 1 0 1/8
x6 0 0 3 -2 -1 0 1 0
Индексная строка F(X1) -1/2 0 -1 1/2 1/2 0 0 0

Итерация №0.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления:

и из них выберем наименьшее:
min (1/2 : 2 , 1/2 : 4 , - ) = 0
Следовательно, 3-ая строка является ведущей.
Разрешающий элемент равен (3) и находится на пересечении ведущего столбца и ведущей строки.
Формируем следующую часть симплексной таблицы.
Вместо переменной x в план 1 войдет переменная x2 .
Строка, соответствующая переменной x2  в плане 1, получена в результате деления всех элементов строки x6 плана 0 на разрешающий элемент РЭ=3
На месте разрешающего элемента в плане 1 получаем 1.
В остальных клетках столбца x2 плана 1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x2  и столбец x2 .
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (3), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:
B x1 x2 x3 x4 x5 x6
1/2-(0•2):3 1-(0•2):3 2-(3•2):3 1/2-(-2•2):3 -1/2-(-1•2):3 0-(0•2):3 0-(1•2):3
1/2-(0•4):3 0-(0•4):3 4-(3•4):3 -11/2-(-2•4):3 -11/2-(-1•4):3 1-(0•4):3 0-(1•4):3
0 : 3 0 : 3 3 : 3 -2 : 3 -1 : 3 0 : 3 1 : 3
-1/2-(0•-1):3 0-(0•-1):3 -1-(3•-1):3 1/2-(-2•-1):3 1/2-(-1•-1):3 0-(0•-1):3 0-(1•-1):3

План Базис B x1 x2 x3 x4 x5 x6 min
2 x1 1/2 1 0 15/6 1/6 0 -2/3 3 /11
x5 1/2 0 0 11/6 -1/6 1 -11/3 3/7
x2 0 0 1 -2/3 -1/3 0 1/3 -
Индексная строка F(X2) -1/2 0 0 -1 /6 1/6 0 1/3 0

Итерация №1.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления:

и из них выберем наименьшее:
min (1/2 : 15/6 , 1/2 : 11/6, - ) = 3/11
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (15/6) и находится на пересечении ведущего столбца и ведущей строки.
Формируем следующую часть симплексной таблицы.
Вместо переменной x в план 2 войдет переменная x3 .
Строка, соответствующая переменной x3  в плане 2, получена в результате деления всех элементов строки x1 плана 1 на разрешающий элемент РЭ=15/6
На месте разрешающего элемента в плане 2 получаем 1.
В остальных клетках столбца x3 плана 2 записываем нули.
Таким образом, в новом плане 2 заполнены строка x3  и столбец x3 .
Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (15/6), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:
B x1 x2 x3 x4 x5 x6
1/2 : 15/6 1 : 15/6 0 : 15/6 15/6 : 15/6 1/6 : 15/6 0 : 15/6 -2/3 : 15/6
1/2-(1/2•11/6):15/6 0-(1•11/6):15/6 0-(0•11/6):15/6 11/6-(15/6•11/6):15/6 -1/6-(1/6•11/6):15/6 1-(0•11/6):15/6 -11/3-(-2/3•11/6):15/6
0-(1/2-2/3):15/6 0-(1•-2/3):15/6 1-(0•-2/3):15/6 -2/3-(15/6-2/3):15/6 -1/3-(1/6-2/3):15/6 0-(0•-2/3):15/6 1/3-(-2/3-2/3):15/6
-1/2-(1/2-1/6):15/6 0-(1•-1/6):15/6 0-(0•-1/6):15/6 -1/6-(15/6-1/6):15/6 1/6-(1/6-1/6):15/6 0-(0•-1/6):15/6 1/3-(-2/3-1/6):15/6


Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план
Окончательный вариант симплекс-таблицы:
План Базис B x1 x2 x3 x4 x5 x6
3 x3 3/11 6/11 0 1 1/11 0 -4/11
x5 2/11 -7/11 0 0 -3/11 1 -10/11
x2 2/11 4/11 1 0 -3/11 0 1/11
Индексная строка F(X3) -5/11 1/11 0 0 2/11 0 3/11

Оптимальный план можно записать так:
x3 = 3/11
x5 = 2/11
x2 = 2/11
F(X) = 1•3/11 + 1•2/11 = 5/11
Составим двойственную задачу к прямой задаче.
2y1 + 3y2 + 2y3≤1
4y1 + 2y2 + y3≤1
y1 + 3y2 + 3y3≤1
y1 + y2 + y3 => max
y1 ≥ 0
y2 ≥ 0
y3 ≥ 0

Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.
Из теоремы двойственности следует, что Y = C*A-1.
Составим матрицу A из компонентов векторов, входящих в оптимальный базис.


Определив обратную матрицу А-1через алгебраические дополнения, получим:

Как видно из последнего плана симплексной таблицы, обратная матрица A-1расположена в столбцах дополнительных переменных .
Тогда Y = C*A-1=

Оптимальный план двойственной задачи равен:
y1 = 2/11
y2 = 0
y3 = 3/11
Z(Y) = 1*2/11+1*0+1*3/11 = 5/11

Цена игры будет равна g = 1/F(x), а вероятности применения стратегий игроков:
pi = g*xi; qi = g*yi.
Цена игры: g = 1 : 5/11 = 21/5
p1 = 21/5•0 = 0
p2 = 21/52/11 = 2/5
p3 = 21/53/11 = 3/5
q1 = 21/52/11 = 2/5
q2 = 21/5•0 = 0
q3 = 21/53/11 = 3/5

Оптимальная  стратегия  игрока А:
P( 0; 2/5; 3/5)
Оптимальная стратегия игрока B:
Q(2/5;0;3/5)

Перейти к онлайн решению своей задачи

загрузка...