Пример решения матричной игры методом линейного программирования

Решить матричную игру методом линейного программирования.
6 5 7
10 4 7
13 10 4
7 11 5

Решение находим через сервис матричная игра.

A/B B1 B2 B3 a = min(Ai)
A1 6 5 7 5
A2 10 4 7 4
A3 13 10 4 4
A4 7 11 5 5
b = max(Bi ) 13 11 7 0


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

-6 -10 -13 -7 1 0 0
-5 -4 -10 -11 0 1 0
-7 -7 -4 -5 0 0 1


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

План Базис B x1 x2 x3 x4 x5 x6 x7
0 x5 -1 -6 -10 -13 -7 1 0 0
  x6 -1 -5 -4 -10 -11 0 1 0
  x7 -1 -7 -7 -4 -5 0 0 1
Индексная строка F(X0) 0 1 1 1 1 0 0 0


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

План Базис B x1 x2 x3 x4 x5 x6 x7
  x1 1 /6 1 12/3 21/6 11/6 -1 /6 0 0
  x6 -1 /6 0 41/3 5 /6 -51/6 -5 /6 1 0
  x7 1 /6 0 42/3 111/6 31/6 -11/6 0 1
Индексная строка F(X) -1 /6 0 -2 /3 -11/6 -1 /6 1 /6 0 0


 Представим расчет каждого элемента в виде таблицы:


B

x 1

x 2

x 3

x 4

x 5

x 6

x 7

1 /6 : 1

1 : 1

12/3 : 1

21/6 : 1

11/6 : 1

-1 /6 : 1

0 : 1

0 : 1

-1 /6-(1/6 • 0):1

0-(1 • 0):1

41/3-(12/3 • 0):1

5 /6-(21/6 • 0):1

-51/6-(11/6 • 0):1

-5 /6-(-1/6 • 0):1

1-(0 • 0):1

0-(0 • 0):1

1 /6-(1/6 • 0):1

0-(1 • 0):1

42/3-(12/3 • 0):1

111/6-(21/6 • 0):1

31/6-(11/6 • 0):1

-11/6-(-1/6 • 0):1

0-(0 • 0):1

1-(0 • 0):1

-1 /6-(1/6 • 0):1

0-(1 • 0):1

-2 /3-(12/3 • 0):1

-11/6-(21/6 • 0):1

-1 /6-(11/6 • 0):1

1 /6-(-1/6 • 0):1

0-(0 • 0):1

0-(0 • 0):1


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

План Базис B x1 x2 x3 x4 x5 x6 x7
  x1 4 /31 1 220/31 211/31 0 -11 /31 7 /31 0
  x4 1 /31 0 -26 /31 -5 /31 1 5 /31 -6 /31 0
  x7 2 /31 0 710/31 1121/31 0 -121/31 19 /31 1
Индексная строка F(X) -5 /31 0 -25 /31 -16/31 0 6 /31 -1 /31 0


 Представим расчет каждого элемента в виде таблицы:


B

x 1

x 2

x 3

x 4

x 5

x 6

x 7

4 /31-(1/31 • 0):1

1-(0 • 0):1

220/31-(-26/31 • 0):1

211/31-(-5/31 • 0):1

0-(1 • 0):1

-11 /31-(5/31 • 0):1

7 /31-(-6/31 • 0):1

0-(0 • 0):1

1 /31 : 1

0 : 1

-26 /31 : 1

-5 /31 : 1

1 : 1

5 /31 : 1

-6 /31 : 1

0 : 1

2 /31-(1/31 • 0):1

0-(0 • 0):1

710/31-(-26/31 • 0):1

1121/31-(-5/31 • 0):1

0-(1 • 0):1

-121/31-(5/31 • 0):1

19 /31-(-6/31 • 0):1

1-(0 • 0):1

-5 /31-(1/31 • 0):1

0-(0 • 0):1

-25 /31-(-26/31 • 0):1

-16/31-(-5/31 • 0):1

0-(1 • 0):1

6 /31-(5/31 • 0):1

-1 /31-(-6/31 • 0):1

0-(0 • 0):1


 В базисном столбце все элементы положительные.
 Переходим к основному алгоритму симплекс-метода.

План Aacen B x1 x2 x3 x4 x5 x6 x7 min
1 x1 4 /31 1 220/31 211/31 0 -11 /31 7 /31 0 4 /73
  x4 1 /31 0 -26 /31 -5 /31 1 5 /31 -6 /31 0 -
  x7 2 /31 0 710/31 1121/31 0 -121/31 19 /31 1 1 /181
F(X1) -5 /31 0 -25 /31 -16/31 0 6 /31 -1 /31 0 0


 Итерация №0.
 Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
 В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент по модулю.
 Вычислим значения Di по строкам как частное от деления:
bi / ai3
 и из них выберем наименьшее:
 min (4/31 : 211/31 , - , 2/31 : 1121/31 ) = 1/181
 Следовательно, 3-ая строка является ведущей.
 Разрешающий элемент равен (1121/31) и находится на пересечении ведущего столбца и ведущей строки.
 Формируем следующую часть симплексной таблицы.
 Вместо переменной x в план 1 войдет переменная x3 .
 Строка, соответствующая переменной x3  в плане 1, получена в результате деления всех элементов строки x7 плана 0 на разрешающий элемент РЭ=1121/31
 На месте разрешающего элемента в плане 1 получаем 1.
 В остальных клетках столбца x3 плана 1 записываем нули.
 Таким образом, в новом плане 1 заполнены строка x3  и столбец x3 .
 Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
 Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
 НЭ = СЭ - (А*В)/РЭ
 СТЭ - элемент старого плана, РЭ - разрешающий элемент (1121/31), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
 Представим расчет каждого элемента в виде таблицы:


B

x 1

x 2

x 3

x 4

x 5

x 6

x 7

4 /31-(2/31 • 211/31):1121/31

1-(0 • 211/31):1121/31

220/31-(710/31 • 211/31):1121/31

211/31-(1121/31 • 211/31):1121/31

0-(0 • 211/31):1121/31

-11 /31-(-121/31 • 211/31):1121/31

7 /31-(19/31 • 211/31):1121/31

0-(1 • 211/31):1121/31

1 /31-(2/31-5/31):1121/31

0-(0 • -5/31):1121/31

-26 /31-(710/31-5/31):1121/31

-5 /31-(1121/31-5/31):1121/31

1-(0 • -5/31):1121/31

5 /31-(-121/31-5/31):1121/31

-6 /31-(19/31-5/31):1121/31

0-(1 • -5/31):1121/31

2 /31 : 1121/31

0 : 1121/31

710/31 : 1121/31

1121/31 : 1121/31

0 : 1121/31

-121/31 : 1121/31

19 /31 : 1121/31

1 : 1121/31

-5 /31-(2/31 • -16/31):1121/31

0-(0 • -16/31):1121/31

-25 /31-(710/31 • -16/31):1121/31

-16/31-(1121/31 • -16/31):1121/31

0-(0 • -16/31):1121/31

6 /31-(-121/31 • -16/31):1121/31

-1 /31-(19/31 • -16/31):1121/31

0-(1 • -16/31):1121/31


 

План Базис B x1 x2 x3 x4 x5 x6 x7 min
2 x1 21 /181 1 161/362 0 0 -3 /181 37 /362 -73 /362 14 /141
  x4 6 /181 0 -267 /362 0 1 25 /181 -67 /362 5 /362 -
  x3 1 /181 0 227 /362 1 0 -26 /181 19 /362 31 /362 2 /227
Eiaaeniay no?iea F(X2) -28 /181 0 -21 /362 0 0 4 /181 11 /362 37 /362 0


 Итерация №1.
 Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
 В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.
 Вычислим значения Di по строкам как частное от деления:
bi / ai2
и из них выберем наименьшее:
min (21/181 : 161/362 , - , 1/181 : 227/362) = 2/227
Следовательно, 3-ая строка является ведущей.
Разрешающий элемент равен (227/362) и находится на пересечении ведущего столбца и ведущей строки.
Формируем следующую часть симплексной таблицы.
Вместо переменной x в план 2 войдет переменная x2 .
Строка, соответствующая переменной x2  в плане 2, получена в результате деления всех элементов строки x3 плана 1 на разрешающий элемент РЭ=227/362
На месте разрешающего элемента в плане 2 получаем 1.
В остальных клетках столбца x2 плана 2 записываем нули.
Таким образом, в новом плане 2 заполнены строка x2  и столбец x2 .
Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
 Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
 НЭ = СЭ - (А*В)/РЭ
 СТЭ - элемент старого плана, РЭ - разрешающий элемент (227/362), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
 Представим расчет каждого элемента в виде таблицы:


B

x 1

x 2

x 3

x 4

x 5

x 6

x 7

21 /181-(1/181 • 161/362):227/362

1-(0 • 161/362):227/362

161/362-(227/362 • 161/362):227/362

0-(1 • 161/362):227/362

0-(0 • 161/362):227/362

-3 /181-(-26/181 • 161/362):227/362

37 /362-(19/362 • 161/362):227/362

-73 /362-(31/362 • 161/362):227/362

6 /181-(1/181-267/362):227/362

0-(0 • -267/362):227/362

-267 /362-(227/362-267/362):227/362

0-(1 • -267/362):227/362

1-(0 • -267/362):227/362

25 /181-(-26/181-267/362):227/362

-67 /362-(19/362-267/362):227/362

5 /362-(31/362-267/362):227/362

1 /181 : 227/362

0 : 227/362

227 /362 : 227/362

1 : 227/362

0 : 227/362

-26 /181 : 227/362

19 /362 : 227/362

31 /362 : 227/362

-28 /181-(1/181-21/362):227/362

0-(0 • -21/362):227/362

-21 /362-(227/362-21/362):227/362

0-(1 • -21/362):227/362

0-(0 • -21/362):227/362

4 /181-(-26/181-21/362):227/362

11 /362-(19/362-21/362):227/362

37 /362-(31/362-21/362):227/362


 
 Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план
 Окончательный вариант симплекс-таблицы:

План Базис B x1 x2 x3 x4 x5 x6 x7
3 x1 24 /227 1 0 -1196/227 0 57 /227 1 /227 -82 /227
  x4 9 /227 0 0 140/227 1 -7 /227 -28 /227 26 /227
  x2 2 /227 0 1 1135/227 0 -52 /227 19 /227 31 /227
Индексная строка F(X3) -35 /227 0 0 21 /227 0 2 /227 8 /227 25 /227


 Оптимальный план можно записать так:
 x1 = 24/227
 x4 = 9/227
 x2 = 2/227
 F(X) = 1•24/227 + 1•2/227 = 35/227
 Составим двойственную задачу к прямой задаче.
 6y1 + 5y2 + 7y3≤1
 10y1 + 4y2 + 7y3≤1
 13y1 + 10y2 + 4y3≤1
 7y1 + 11y2 + 5y3≤1
 y1 + y2 + y3 → max
 y1 ≥ 0
 y2 ≥ 0
 y3 ≥ 0
Данную двойственную задачу можно решить двумя способами – используя снова прямой симплексный метод и воспользовавшись теоремой двойственности.

Первый способ нахождений двойственной задачи


Решим прямую задачу линейного программирования  симплексным методом, с использованием симплексной таблицы.
 Определим максимальное значение целевой функции F(X) = x1 + x2 + x3 при следующих условиях-ограничений.
 6x1 + 5x2 + 7x3≤1
 10x1 + 4x2 + 7x3≤1
 13x1 + 10x2 + 4x3≤1
 7x1 + 11x2 + 5x3=1
 Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
 6x1 + 5x2 + 7x3 + 1x4 + 0x5 + 0x6 = 1
 10x1 + 4x2 + 7x3 + 0x4 + 1x5 + 0x6 = 1
 13x1 + 10x2 + 4x3 + 0x4 + 0x5 + 1x6 = 1
 7x1 + 11x2 + 5x3 + 0x4 + 0x5 + 0x6 = 1
 Введем искусственные переменные x.
 6x1 + 5x2 + 7x3 + 1x4 + 0x5 + 0x6 + 0x7= 1
 10x1 + 4x2 + 7x3 + 0x4 + 1x5 + 0x6 + 0x7= 1
 13x1 + 10x2 + 4x3 + 0x4 + 0x5 + 1x6 + 0x7= 1
 7x1 + 11x2 + 5x3 + 0x4 + 0x5 + 0x6 + 1x7= 1
 Для постановки задачи на максимум целевую функцию запишем так:
 F(X) = x1+x2+x3 - Mx7 => max
 За использование искусственных переменных, вводимых в целевую функцию, накладывается так называемый штраф величиной М, очень большое положительное число, которое обычно не задается.
 Полученный базис называется искусственным, а метод решения называется методом искусственного базиса.
 Причем искусственные переменные не имеют отношения к содержанию поставленной задачи, однако они позволяют построить стартовую точку, а процесс оптимизации вынуждает эти переменные принимать нулевые значения и обеспечить допустимость оптимального решения.
 Из уравнений выражаем искусственные переменные:
  x7 = 1-7x1-11x2-5x3
 которые подставим в целевую функцию:
 F(X) = x1 + x2 + x3 - M(1-7x1-11x2-5x3) => max
 или
 F(X) = (1+7M)x1+(1+11M)x2+(1+5M)x3+(-1M) => max
 Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

6 5 7 1 0 0 0
10 4 7 0 1 0 0
13 10 4 0 0 1 0
7 11 5 0 0 0 1


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

План Базис B x1 x2 x3 x4 x5 x6 x7
0 x4 1 6 5 7 1 0 0 0
  x5 1 10 4 7 0 1 0 0
  x6 1 13 10 4 0 0 1 0
  x7 1 7 11 5 0 0 0 1
Индексная строка F(X0) -1M -1-7M -1-11M -1-5M 0 0 0 0


 Переходим к основному алгоритму симплекс-метода.

План Базис B x1 x2 x3 x4 x5 x6 x7 min
1 x4 1 6 5 7 1 0 0 0 1 /5
  x5 1 10 4 7 0 1 0 0 1 /4
  x6 1 13 10 4 0 0 1 0 1 /10
  x7 1 7 11 5 0 0 0 1 1 /11
Индексная строка F(X1) -1M -1-7M -1-11M -1-5M 0 0 0 0 0


 Итерация №0.
 Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
 В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.
 Вычислим значения Di по строкам как частное от деления:
 и из них выберем наименьшее:
 min (1 : 5 , 1 : 4 , 1 : 10 , 1 : 11 ) = 1/11
 Следовательно, 4-ая строка является ведущей.
 Разрешающий элемент равен (11) и находится на пересечении ведущего столбца и ведущей строки.
 Формируем следующую часть симплексной таблицы.
 Вместо переменной x в план 1 войдет переменная x2 .
 Строка, соответствующая переменной x2  в плане 1, получена в результате деления всех элементов строки x7 плана 0 на разрешающий элемент РЭ=11
 На месте разрешающего элемента в плане 1 получаем 1.
 В остальных клетках столбца x2 плана 1 записываем нули.
 Таким образом, в новом плане 1 заполнены строка x2  и столбец x2 .
 Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника (метод Жордано-Гаусса).
 Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
 НЭ = СЭ - (А*В)/РЭ
 СТЭ - элемент старого плана, РЭ - разрешающий элемент (11), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
 Представим расчет каждого элемента в виде таблицы:


B

x 1

x 2

x 3

x 4

x 5

x 6

x 7

1-(1 • 5):11

6-(7 • 5):11

5-(11 • 5):11

7-(5 • 5):11

1-(0 • 5):11

0-(0 • 5):11

0-(0 • 5):11

0-(1 • 5):11

1-(1 • 4):11

10-(7 • 4):11

4-(11 • 4):11

7-(5 • 4):11

0-(0 • 4):11

1-(0 • 4):11

0-(0 • 4):11

0-(1 • 4):11

1-(1 • 10):11

13-(7 • 10):11

10-(11 • 10):11

4-(5 • 10):11

0-(0 • 10):11

0-(0 • 10):11

1-(0 • 10):11

0-(1 • 10):11

1 : 11

7 : 11

11 : 11

5 : 11

0 : 11

0 : 11

0 : 11

1 : 11

(-1M)-(1 • (-1-11M)):11

(-1-7M)-(7 • (-1-11M)):11

(-1-11M)-(11 • (-1-11M)):11

(-1-5M)-(5 • (-1-11M)):11

(0)-(0 • (-1-11M)):11

(0)-(0 • (-1-11M)):11

(0)-(0 • (-1-11M)):11

(0)-(1 • (-1-11M)):11


 

План Базис B x1 x2 x3 x4 x5 x6 x7 min
2 x4 6 /11 29/11 0 48/11 1 0 0 -5 /11 3 /26
  x5 7 /11 75/11 0 52/11 0 1 0 -4 /11 7 /57
  x6 1 /11 67/11 0 -6 /11 0 0 1 -10 /11 -
  x2 1 /11 7 /11 1 5 /11 0 0 0 1 /11 1 /5
Индексная строка F(X2) 1 /11 -4 /11 0 -6 /11 0 0 0 1 /11+1M 0


 Итерация №1.
 Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
 В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент по модулю.
 Вычислим значения Di по строкам как частное от деления:
bi / ai3
 и из них выберем наименьшее:
 min (6/11 : 48/11 , 7/11 : 52/11, - , 1/11 : 5/11 ) = 3/26
 Следовательно, 1-ая строка является ведущей.
 Разрешающий элемент равен (48/11) и находится на пересечении ведущего столбца и ведущей строки.
 Формируем следующую часть симплексной таблицы.
 Вместо переменной x в план 2 войдет переменная x3 .
 Строка, соответствующая переменной x3  в плане 2, получена в результате деления всех элементов строки x4 плана 1 на разрешающий элемент РЭ=48/11
 На месте разрешающего элемента в плане 2 получаем 1.
 В остальных клетках столбца x3 плана 2 записываем нули.
 Таким образом, в новом плане 2 заполнены строка x3  и столбец x3 .
 Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
 Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
 НЭ = СЭ - (А*В)/РЭ
 СТЭ - элемент старого плана, РЭ - разрешающий элемент (48/11), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
 Представим расчет каждого элемента в виде таблицы:


B

x 1

x 2

x 3

x 4

x 5

x 6

x 7

6 /11 : 48/11

29/11 : 48/11

0 : 48/11

48/11 : 48/11

1 : 48/11

0 : 48/11

0 : 48/11

-5 /11 : 48/11

7 /11-(6/11 • 52/11):48/11

75/11-(29/11 • 52/11):48/11

0-(0 • 52/11):48/11

52/11-(48/11 • 52/11):48/11

0-(1 • 52/11):48/11

1-(0 • 52/11):48/11

0-(0 • 52/11):48/11

-4 /11-(-5/11 • 52/11):48/11

1 /11-(6/11-6/11):48/11

67/11-(29/11-6/11):48/11

0-(0 • -6/11):48/11

-6 /11-(48/11-6/11):48/11

0-(1 • -6/11):48/11

0-(0 • -6/11):48/11

1-(0 • -6/11):48/11

-10 /11-(-5/11-6/11):48/11

1 /11-(6/115/11):48/11

7 /11-(29/115/11):48/11

1-(0 • 5/11):48/11

5 /11-(48/115/11):48/11

0-(1 • 5/11):48/11

0-(0 • 5/11):48/11

0-(0 • 5/11):48/11

1 /11-(-5/115/11):48/11

(1/11)-(6/11 • (-6/11)):48/11

(-4/11)-(29/11 • (-6/11)):48/11

(0)-(0 • (-6/11)):48/11

(-6/11)-(48/11 • (-6/11)):48/11

(0)-(1 • (-6/11)):48/11

(0)-(0 • (-6/11)):48/11

(0)-(0 • (-6/11)):48/11

(1/11+1M)-(-5/11 • (-6/11)):48/11


 

План Базис B x1 x2 x3 x4 x5 x6 x7 min
3 x3 3 /26 31 /52 0 1 11 /52 0 0 -5 /52 6 /31
  x5 1 /26 419/52 0 0 -15/52 1 0 7 /52 2 /227
  x6 2 /13 625/26 0 0 3 /26 0 1 -25 /26 4 /181
  x2 1 /26 19 /52 1 0 -5 /52 0 0 7 /52 2 /19
Индексная строка F(X3) 2 /13 -1 /26 0 0 3 /26 0 0 1 /26+1M 0


 Итерация №2.
 Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
 В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.
 Вычислим значения Di по строкам как частное от деления:
bi / ai1
 и из них выберем наименьшее:
 min (3/26 : 31/52 , 1/26 : 419/52, 2/13 : 625/26 , 1/26: 19/52 ) = 2/227
 Следовательно, 2-ая строка является ведущей.
 Разрешающий элемент равен (419/52) и находится на пересечении ведущего столбца и ведущей строки.
 Формируем следующую часть симплексной таблицы.
 Вместо переменной x в план 3 войдет переменная x1 .
 Строка, соответствующая переменной x1  в плане 3, получена в результате деления всех элементов строки x5 плана 2 на разрешающий элемент РЭ=419/52
 На месте разрешающего элемента в плане 3 получаем 1.
 В остальных клетках столбца x1 плана 3 записываем нули.
 Таким образом, в новом плане 3 заполнены строка x1  и столбец x1 .
 Все остальные элементы нового плана 3, включая элементы индексной строки, определяются по правилу прямоугольника.
 Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
 НЭ = СЭ - (А*В)/РЭ
 СТЭ - элемент старого плана, РЭ - разрешающий элемент (419/52), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
 Представим расчет каждого элемента в виде таблицы:


B

x 1

x 2

x 3

x 4

x 5

x 6

x 7

3 /26-(1/2631/52):419/52

31 /52-(419/5231/52):419/52

0-(0 • 31/52):419/52

1-(0 • 31/52):419/52

11 /52-(-15/5231/52):419/52

0-(1 • 31/52):419/52

0-(0 • 31/52):419/52

-5 /52-(7/5231/52):419/52

1 /26 : 419/52

419/52 : 419/52

0 : 419/52

0 : 419/52

-15/52 : 419/52

1 : 419/52

0 : 419/52

7 /52 : 419/52

2 /13-(1/26 • 625/26):419/52

625/26-(419/52 • 625/26):419/52

0-(0 • 625/26):419/52

0-(0 • 625/26):419/52

3 /26-(-15/52 • 625/26):419/52

0-(1 • 625/26):419/52

1-(0 • 625/26):419/52

-25 /26-(7/52 • 625/26):419/52

1 /26-(1/2619/52):419/52

19 /52-(419/5219/52):419/52

1-(0 • 19/52):419/52

0-(0 • 19/52):419/52

-5 /52-(-15/5219/52):419/52

0-(1 • 19/52):419/52

0-(0 • 19/52):419/52

7 /52-(7/5219/52):419/52

(2/13)-(1/26 • (-1/26)):419/52

(-1/26)-(419/52 • (-1/26)):419/52

(0)-(0 • (-1/26)):419/52

(0)-(0 • (-1/26)):419/52

(3/26)-(-15/52 • (-1/26)):419/52

(0)-(1 • (-1/26)):419/52

(0)-(0 • (-1/26)):419/52

(1/26+1M)-(7/52 • (-1/26)):419/52


 Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план
 Окончательный вариант симплекс-таблицы:

План Базис B x1 x2 x3 x4 x5 x6 x7
4 x3 25 /227 0 0 1 82 /227 -31 /227 0 -26 /227
  x1 2 /227 1 0 0 -57 /227 52 /227 0 7 /227
  x6 21 /227 0 0 0 1196/227 -1135/227 1 -140/227
  x2 8 /227 0 1 0 -1 /227 -19 /227 0 28 /227
Индексная строка F(X4) 35 /227 0 0 0 24 /227 2 /227 0 9 /227+1M


Оптимальный план можно записать так:
x3 = 25/227
x1 = 2/227
x6 = 21/227
x2 = 8/227
F(X) = 1•25/227 + 1•2/227 + 1•8/227 = 35/227

Второй способ нахождений двойственной задачи

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

Как видно из последнего плана симплексной таблицы, обратная матрица A-1 расположена в столбцах дополнительных переменных .
Тогда
как найти двойственную задачу
Оптимальный план двойственной задачи равен:
y1 = 2/227
y2 = 8/227
y3 = 25/227
Z(Y) = 1*2/227+1*8/227+1*25/227= 35/227

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

Цена игры будет равна g = 1/F(x), а вероятности применения стратегий игроков:
pi = g*xi; qi = g*yi.
Цена игры: g = 1 : 35/227 = 617/35
p1 = 617/3524/227 = 24/35
p2 = 617/352/227 = 2/35
p3 = 617/35 • 0 = 0
p4 = 617/359/227 = 9/35
Оптимальная смешанная стратегия игрока I:
P = (24/35; 2/35; 0; 9/35)
q1 = 617/352/227 = 2/35
q2 = 617/358/227 = 8/35
q3 = 617/3525/227 = 5/7
Оптимальная смешанная стратегия игрока II:
Q = (2/35; 8/35; 5/7)

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

загрузка...