4329
.pdf31
Прямая (исходная) задача:
m
L(x) xi min,
i 1
m
aij xi 1 ( j 1, 2, ... , n) ,
i 1
Двойственная задача:
n
L( y) y j max,
|
j 1 |
n |
|
aij y j |
1 (i 1, 2, ... , m), |
j 1 |
|
xi 0 |
( i 1, 2, ... , m). |
|
|
y j 0 |
( j 1, 2, ... , n) . |
||
При этом |
|
|
|
|
|
|
|
|
|
1 |
1 |
|
|||
|
|
|
|
|
, |
||
|
min L( x) |
max L( y) |
|||||
|
p* x |
(i 1,2,..., m), |
|||||
|
i |
|
i |
|
|
|
|
|
q*j |
y j |
( j 1,2,..., n). |
Замечание. Для любой задачи линейного программирования может быть также построена эквивалентная ей задача теории матричных игр. Эта связь задач теории матричных игр с задачами линейного программирования оказывается полезной не только для теории игр, но и для линейного программирования. Дело в том, что существуют приближенные численные методы решения матричных игр, которые при большой размерности задачи могут оказаться проще, чем симплекс–метод.
3.2. Практическая часть
Пример. Решить игру с платежной матрицей
|
1 |
2 |
3 |
|
P |
3 |
1 |
1 |
. |
|
|
|
|
|
|
1 |
3 |
1 |
|
|
|
Решение. Найдем нижнюю и верхнюю цены игры
|
|
32 |
|
|
|
|
1 |
2 |
3 |
1 |
|
|
3 |
1 |
1 |
|
1 |
|
|
||||
|
1 |
3 |
1 |
|
1 |
|
|
||||
|
3 |
3 |
3 |
|
|
Нижняя цена игры max 1;1;1 1, |
верхняя цена игры min 3;3;3 3. |
Так как , то игра не имеет седловой точки. Решим игру сведением ее к паре двойственных задач линейного программирования.
Составим математические модели пары двойственных задач линейного программирования.
Прямая (исходная) задача. Найти неотрицательные переменные х1 , х2 ,
х3, минимизирующие функцию |
L (x) |
= х1 + х2 + х3 m i n при |
|||||
ограничениях |
|
|
|
|
|
|
|
x1 3x2 x3 1 |
|||||||
|
|
x2 3x3 1 |
|||||
2x1 |
|||||||
|
3x |
x |
|
x 1 . |
|||
|
1 |
|
2 |
|
3 |
|
|
|
|
|
|
||||
|
|
|
|
|
|||
x |
0, (i 1,3) |
||||||
|
i |
|
|
|
|
|
|
Двойственная задача. Найти неотрицательные переменные y1, y2, y3, максимизирующие функцию L (x) = y1 + y2 + y3 max при ограничениях
y1 2 y2 3y3 1 |
||||||||||
3y |
|
y |
2 |
y |
|
1 |
||||
|
1 |
|
|
3 |
|
|
|
|||
y |
3y |
|
y |
|
|
|
1. |
|||
|
1 |
|
|
2 |
|
3 |
|
|
|
|
|
y |
j |
0,( j 1,3) |
|
||||||
|
|
|
|
|
|
|
|
|
|
Поскольку в двойственной задаче ограничения имеют вид « », то ее решать проще (не нужно вводить искусственные переменные). Оптимальное решение исходной задачи можно будет непосредственно получить из данных симплексной таблицы для оптимального решения двойственной задачи. Приведем двойственную задачу к каноническому виду
33
y1 2 y2 3y3 y4 1 |
||||||||
|
3y y |
2 |
y y 1 |
|||||
|
1 |
|
3 |
5 |
|
|||
y 3y |
|
y |
|
y |
|
1 |
||
|
1 |
2 |
|
3 |
|
|
6 |
|
|
|
|
|
|
|
|
|
|
y j 0,( j 1, 6) |
|
|||||||
|
|
и составим симплексную таблицу |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 1 |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
С |
Б |
f |
-1 |
-1 |
|
-1 |
0 |
0 |
|
0 |
|
∑ |
|
|
fi |
|
|
|
|
|
|
|
|
y1 |
y2 |
|
y3 |
y4 |
y5 |
|
y6 |
|
|
|
|
his |
|
|
|
0 |
y |
4 |
1 |
1 |
2 |
|
3 |
1 |
0 |
|
0 |
|
8 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
y5 |
1 |
[3] |
1 |
|
1 |
0 |
1 |
|
0 |
|
7 |
|
1 3 |
|
|||
|
0 |
y6 |
1 |
1 |
3 |
|
1 |
0 |
0 |
|
1 |
|
7 |
|
1 |
|
|
||
|
|
L(Y0 ) 0 |
-1 |
-1 |
|
-1 |
0 |
0 |
|
0 |
|
-3 |
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
В последней строке таблицы 1 |
оценки переменных |
|
y1 , |
y2 и y3 |
отрицательны, то есть опорный план Y0 (0;0;0;1;1;1) не является оптимальным. Выберем за ключевой столбец первый и для выбора ключевой строки
посчитаем отношение |
fi hi1 |
(в последнем столбце). Вторая строка является |
|||||||||||||||
ключевой, так как min 1;1 3;1 1 3, |
а ключевым элементом – элемент |
[3]. |
|||||||||||||||
Пересчитаем симплексную таблицу |
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
Продолжение табл. 1 |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
С |
Б |
f |
y |
y |
2 |
y |
3 |
y |
4 |
y |
y |
6 |
∑ |
|
f |
h |
|
|
|
|
|
1 |
|
|
|
5 |
|
|
|
|
i is |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
0 |
|
y4 |
2 3 |
0 |
5 3 |
8 3 |
1 |
1 3 |
0 |
17 3 |
|
0,4 |
|||||
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
1 |
|
y1 |
1 3 |
1 |
1 3 |
1 3 |
0 |
1 3 |
0 |
7 3 |
|
|
1 |
||||
|
|
|
|
|
|
|
|
|
|
||||||||
0 |
|
y6 |
2 3 |
0 |
[8 3] |
2 3 |
0 |
1 3 |
1 |
14 3 |
|
0,25 |
|||||
|
|
|
|
|
|
|
|
|
|
||||||||
|
L(Y1) 1 3 |
0 |
2 3 |
2 3 |
0 |
1 3 |
0 |
2 3 |
|
|
|
||||||
|
|
|
|
|
|
|
|
|
34
Продолжение табл. 1
С |
Б |
f |
y |
y |
2 |
y |
3 |
|
y |
4 |
y |
y |
6 |
∑ |
f |
h |
|
|
|
|
|
1 |
|
|
|
|
5 |
|
|
|
i is |
||||
0 |
|
y4 |
1 4 |
0 |
0 |
[ 9 4 |
] |
1 |
1 8 |
5 8 |
11 4 |
1 9 |
|||||
|
|
|
|
|
|
|
|||||||||||
1 |
|
y1 |
1 4 |
1 |
0 |
1 4 |
|
0 |
3 8 |
1 8 |
7 4 |
|
1 |
||||
|
|
|
|
|
|
|
|
|
|
||||||||
1 |
|
y2 |
1 4 |
0 |
1 |
1 4 |
|
0 |
1 8 |
3 8 |
7 4 |
|
1 |
||||
|
|
|
|
|
|
|
|
|
|
||||||||
|
L(Y2 ) 1 2 |
0 |
0 |
1 2 |
0 |
1 4 |
1 4 |
1 2 |
|
|
|||||||
|
|
|
|
|
|
|
|
||||||||||
1 |
|
y3 |
1 9 |
0 |
0 |
1 |
|
4 9 |
1 18 |
5 18 |
11 9 |
|
|
||||
|
|
|
|
|
|
|
|
|
|
||||||||
1 |
|
y1 |
2 9 |
1 |
0 |
0 |
|
1 9 |
7 18 |
1 18 |
13 9 |
|
|
||||
|
|
|
|
|
|
|
|
|
|
||||||||
1 |
|
y2 |
2 9 |
0 |
1 |
0 |
|
1 9 |
1 9 |
4 9 |
5 9 |
|
|
||||
|
|
|
|
|
|
|
|
|
|
||||||||
|
L(Y3) 5 9 |
0 |
0 |
0 |
|
2 9 |
2 9 |
1 9 |
10 9 |
|
|
||||||
|
|
|
|
|
|
|
|
|
Мы добились того, что в нижней строке таблицы нет отрицательных оценок. Это говорит о том, что мы получили оптимальное решение двойственной задачи
|
|
y1 = 2 9, |
y2 = 2 9, |
y3 =1 9 , |
|
L(Y ) 5 9 |
─ max. |
|
|
|
|
||||||||||||||||||||||||||||||||
|
Находим оптимальную смешанную стратегию |
S* |
игрока В |
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
В |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
9 |
, |
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
2 |
|
|
|
|
2 |
|
|
1 |
|
5 |
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
y j |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
9 |
|
9 |
|
9 |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
j 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
q* y |
2 |
|
9 |
|
2 |
, |
|
|
q* |
y |
2 |
|
|
9 |
|
2 |
, |
|
q* y |
1 |
|
9 |
|
1 |
. |
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||
1 |
1 |
9 |
5 |
|
5 |
|
|
|
2 |
|
|
|
2 |
|
|
|
|
|
9 |
|
5 |
|
5 |
|
|
|
3 |
3 |
9 |
|
5 |
|
5 |
||||||||||
|
|
|
|
|
|
|
|
* |
|
2 |
|
2 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
Следовательно, |
S |
|
|
|
; |
|
; |
|
|
|
. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
В |
|
5 5 5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Оптимальное решение исходной задачи ЛП находим, используя двойственные оценки из симплекс – таблицы для оптимального решения двойственной задачи. Получаем
x1 = 2 9, x2 2 9, |
x3 1 9 , |
L( X ) 5 9 – min. |
35
Теперь определим вероятности применения своих активных стратегий игроком А
р* х |
2 |
|
9 |
|
|
2 |
, |
|
|
р* х |
2 |
|
9 |
|
2 |
, |
||||||
|
|
|
|
|
|
|
|
|
||||||||||||||
1 |
1 |
9 |
|
5 |
|
|
5 |
|
|
|
2 |
|
2 |
9 |
|
5 |
|
5 |
|
|||
|
р* х |
1 |
|
9 |
|
|
1 |
. |
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
3 |
|
|
3 |
|
|
|
9 |
|
5 |
|
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
S* |
|
2 |
|
2 |
|
1 |
|
|
Следовательно, |
|
|
; |
|
; |
|
|
. |
|||||||||||||
|
|
|
|
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
А |
|
5 5 |
|
5 |
|
|||
О т в е т : |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
S* |
|
|
2 |
; |
2 |
; |
1 |
|
|
– оптимальная смешанная стратегия игрока А , |
|||||||||||
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
||||||||||||||||||
А |
|
|
|
5 |
|
|
5 |
|
|
5 |
|
|
|
|
|
|
|
|
|
|
|
S* |
|
|
2 |
|
; |
2 |
|
; |
1 |
|
|
. – оптимальная смешанная стратегия игрока В , |
|||||||||
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
||||||||||||||||
В |
|
|
|
5 |
|
|
5 |
|
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
9 |
– цена игры. |
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|||||||||||||
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3.3. Индивидуальные задания
Свести матричную игру к задачам линейного программирования и решить ее симплексным методом.
2 |
4 |
6 |
|
1 |
3 |
2 |
|
5 |
7 |
1 |
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1. Р |
6 |
2 |
2 |
, |
2. Р |
3 |
1 |
3 |
, |
3. Р |
5 |
5 |
1 |
|
, |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
6 |
|
|
|
2 |
3 |
1 |
|
|
|
2 |
2 |
|
|
|
|
2 |
|
|
|
|
|
6 |
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
6 |
4 |
|
|
||
|
|
|
|
|
|
|
|
4. |
Р |
6 |
2 |
6 |
, |
|
|
|
|
|
|
|
|
|
|
|
|
4 |
6 |
|
|
|
|
|
|
2 |
|
|
|||
|
|
|
|
|
|
|
|
|
4 |
6 |
1 |
|
|
||
|
|
|
|
|
|
|
|
7. |
Р |
4 |
4 |
1 |
, |
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
|
|
|
|
|
|
6 |
|
|
|||
|
|
|
|
|
|
|
|
|
|
1 |
2 |
3 |
|
||
|
|
|
|
|
|
|
|
10. |
Р |
|
6 |
1 |
2 |
, |
|
|
|
|
|
|
|
|
|
|
|
|
3 |
5 |
0 |
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
1 |
4 |
1 |
|
||
|
|
|
|
|
|
|
|
13. |
Р |
|
2 |
3 |
4 |
, |
|
|
|
|
|
|
|
|
|
|
|
|
3 |
1 |
6 |
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
36
|
3 |
6 |
9 |
|
|
|
|
|
|
|
|
5. |
Р |
9 |
3 |
3 |
, |
|
|
|
|
|
|
|
|
3 |
9 |
|
|
|
|
3 |
|
||
|
|
|
|
|
|
|
1 |
1 |
5 |
|
|
|
|
|
|
|
|
8. |
Р |
3 |
2 |
1 |
, |
|
|
|
|
|
|
|
|
4 |
3 |
|
|
|
|
1 |
|
||
|
|
|
|
|
|
|
3 |
7 |
6 |
|
||
|
|
|
|
|
|
|
11. |
Р |
3 |
1 |
0 |
, |
|
|
|
|
|
|
|
|
|
|
2 |
2 |
1 |
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
2 |
2 |
5 |
|
|
|
|
|
|
|
|
|
|
14. |
Р |
3 |
3 |
6 |
|
, |
|
|
|
|
|
|
|
|
|
4 |
5 |
|
|
|
|
|
4 |
|
|||
|
|
|
|
|
|
|
|
2 |
1 |
0 |
|
|
|
|
|
|
|
|
|
|
6. |
Р |
1 |
2 |
1 |
|
, |
|
|
|
|
|
|
|
|
|
0 |
1 |
|
|
|
|
|
2 |
|
|||
|
|
|
|
|
|
|
|
1 |
0 |
3 |
|
||
|
|
|
|
|
|
|
9. |
Р |
3 |
1 |
7 |
|
, |
|
|
|
|
|
|
|
|
|
2 |
4 |
8 |
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
3 |
5 |
5 |
|
|
|
|
|
|
|
|
|
|
|
12. |
Р |
7 |
1 |
2 |
, |
|
|
|
|
|
|
|
|
|
|
|
|
1 |
6 |
0 |
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
1 |
|
7 |
3 |
||
|
|
|
|
|
|
|
|
15. |
Р |
4 |
|
9 |
4 . |
||
|
|
|
|
|
|
|
|
|
|
2 |
|
3 |
1 |
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
37
Библиографический список
Основная литература
1. Математические методы и модели исследования операций [Текст] : рек. УМО по образованию в обл. математ. методов в экономике в качестве учеб. для студентов высш. учеб. заведений / под ред. В. А. Колемаева. - М. : ЮНИТИ,
2008. - 592 с.
Дополнительная литература
1. Красс М. С. Математика для экономического бакалавриата [Электронный ресурс]: рек. УМО по образованию в области финансов, учета и мировоя экономики в качестве учеб. пособия для студентов / М.С. Красс, Б.П. Чупрынов. - М.: НИЦ ИНФРА-М, 2013. - 472 с. - ЭБС " Знаниум".