методичка Теория игр 2014. Методические указания и контрольные задания по дисциплине теория игр для студентовзаочников 2 курса, специальности 080100 семестр 4 Москва 2014

• Название: Методические указания и контрольные задания по дисциплине теория игр для студентовзаочников 2 курса, специальности 080100 семестр 4 Москва 2014
• Анкор: методичка Теория игр 2014.pdf
• Дата: 26.04.2017
• Размер: 1.28 Mb.
• Имя файла: методичка Теория игр 2014.pdf
• Тип: Методические указания; #5966
• страница: 4 из 8

Симплекс-таблица 1 (нулевое решение б б б
2
x
3
x
4
x
5
x
6
x
7
x
8
x
9
x

7
x
M
1 1
0 4
–1 0
0 1
0 0 1/4 8
x
M
1 0
3 1
0
–1 0
0 1
0 1
9
x
M
1 2
1 0
0 0
–1 0
0 1
–
)
0
(
j

M
3
M
3 1

1–4M
1–5M
M
M
M
0 0
0 Коэффициенты
)
0
(
j

вычислялись по формулам (44)-(45):
M
M
M
M
3 1
1 1
)
0
(
0








,


M
M
M
M
3 1
2 0
1 1
)
0
(
1










,


M
M
M
M
4 1
1 3
0 1
)
0
(
2










,


M
M
M
M
5 1
0 1
4 1
)
0
(
3










,


M
M
M
M










0 0
)
1
(
0
)
0
(
4
,


M
M
M
M










0
)
1
(
0 0
)
0
(
5
,


M
M
M
M










)
1
(
0 Фактически
M
x
F
3
)
(
)
0
(
0



, те. это большое положительное число, которое желательно уменьшить. Здесь три отрицательных коэффициента
)
0
(
j

:
)
0
(
1

,
)
0
(
2

,
)
0
(
3

, значит решение
)
0
(
x
не является оптимальным (точкой минимума, поэтому нужно, используя алгоритм симплекс-метода, перейти к другому более оптимальному решению. Наибольшим по модулю отрицательным коэффициентом
)
0
(
j

здесь будет
)
0
(
3

(смотрим по наибольшему числу при коэффициенте
M
). Поэтому переменную
3
x следует ввести в базис (
3
X – это разрешающий столбец. Столбец

показывает, за счет какой базисной переменной это можно сделать (см. (47)):
4
/
1 7


,
1
/
1 8


,



0
/
1 9

. Наименьшим из этих чисел является
7

, поэтому искусственную переменную
7
x следует вывести из базиса (первая строка таблицы
7
x – разрешающая строка. В

таблице квадратом выделен разрешающий элемент. Далее переходим к новой симплекс-таблице, проделывая преобразования элементов таблицы по формулам (48). В результате получим таблицу 2.
Симплекс-таблица 2 (первое решение б б б
2
x
3
x
4
x
5
x
6
x
7
x
8
x
9
x

3
x 1 1/4 1/4 0
1
–1/4 0
0 1/4 0
0
–
8
x
M
3/4 –1/4 3
0 1/4
–1 0
–1/4 1 0 1/4 9
x
M
1 2
1 0
0 0
–1 0
0 1
1
)
1
(
j

)
1
(
0

)
1
(
1

1–4M
0
)
1
(
4

M
M
)
1
(
7

0 0 Таким образом, допустимое базисное решение будет следующим
)
1
,
4
/
3
,
0
,
0
,
0
,
0
,
4
/
1
,
0
,
0
(
)
1
(

x
. Здесь для
)
1
(
j

имеем
)
(
4
/
1 4
/
7 1
4
/
3 4
/
1 1
)
1
(
)
1
(
0
x
F
M
M
M










,


4
/
7 4
/
3 2
)
4
/
1
(
4
/
1 1
1
)
1
(
1
M
M
M











,


M
M
M
4 1
1 3
0 1
1
)
1
(
2










,
,


4
/
4
/
1 0
4
/
1
)
4
/
1
(
1 0
)
1
(
4
M
M
M











,


M
M
M










0
)
1
(
0 1
0
)
1
(
5
,


M
M
M










)
1
(
0 0
1 0
)
1
(
6
,


4
/
4
/
1 0
)
4
/
1
(
/4 Отрицательными коэффициентами
)
1
(
j

здесь будут
)
1
(
1

,
)
1
(
2

и Из них выбираем
)
1
(
2

как наибольший по модулю, тогда столбец
2
X становится разрешающими соответствующую переменную
2
x нужно ввести в базис. Вычисляем ограничения на
2
x :



0
:
4
/
1 3

,
4
/
1 3
:
4
/
3 8



,
1 1
/
1 9



. Таким образом, из базиса следует вывести переменную
8
x
, и на ее место ввести переменную
2
x . Далее, проделывая преобразования элементов таблицы 2 по формулам (48), приходим к новой симплекс-таблице 3.
Симплекс-таблица 3 (второе решение б б б
2
x
3
x
4
x
5
x
6
x
7
x
8
x
9
x

3
x 1 1/4 1/4 0
1
–1/4 0
0 1/4 0
0 2
x 1 1/4 –1/12 1
0 1/12
–1/3 0
–1/12 1/3 0
–
9
x
M
3/4 25/12 0
0
–1/12 1/3 –1 1/12
–1/3 1
)
2
(
j

)
2
(
0

–25M/12 0 0
M/12 –M/3 M 11M/124M/3 0

Здесь допустимое базисное решение будет следующим
)
4
/
3
,
0
,
0
,
0
,
0
,
0
,
4
/
1
,
4
/
1
,
0
(
)
2
(

x
. Здесь для
)
2
(
j

имеем
)
(
2 1
4 3
4
/
3 4
/
1 1
4
/
1 1
)
2
(
)
2
(
0
x
F
M
M










,


12
/
25 6
/
5 12
/
25
)
12
/
1
(
1 4
/
1 1
1
)
2
(
1
M
M











,


12
/
6
/
1
)
12
/
1
(
12
/
1 1
)
4
/
1
(
1 0
)
2
(
4
M
M












,


3
/
3
/
1 3
/
1
)
3
/
1
(
1 0
1 0
)
2
(
5
M
M











,


M
M










)
1
(
0 1
0 1
0
)
2
(
6
,


12
/
11 6
/
1 12
/
1
)
12
/
1
(
1
/4 1
1
)
2
(
7
M
M
M












,


3
/
4 3
/
1
)
3
/
1
(
3
/
1 1
0 Отрицательными коэффициентами
)
2
(
j

являются
)
2
(
1

и
)
2
(
5

, при этом наибольшим по модулю из них будет
)
2
(
1

. Значит, столбец
1
X становится разрешающими переменную
1
x необходимо ввести в базис. Вычисляем ограничения на
1
x :
1 4
/
1
:
4
/
1 3



,
25
/
9 12
/
25
:
4
/
3 9



Т.к.
3 9



, то переменную
9
x следует вывести из базиса. Далее, проделывая преобразования элементов таблицы 3 по формулам (48), приходим к новой симплекс-таблице 4.
Симплекс-таблица 4 (третье решение б б б
2
x
3
x
4
x
5
x
6
x
7
x
8
x
9
x

3
x 1 4/25 0 0
1 –6/25
–
1/25 3/25 6/25 1/25
–3/25 2
x 1 7/25 0 1
0 2/25
–
8/25
–1/25 –2/25 8/25 1/25 1
x 1 9/25 1 0
0 –1/25 4/25
–12/25 1/25 –4/25 12/25
)
3
(
j

4/5 0 0
0 1/5 1/5 2/5 Итак, допустимое базисное решение
)
3
(
x
имеет вид Для коэффициентов
)
3
(
j

имеем
)
(
5
/
4 25
/
20 25
/
9 1
25
/
7 1
25
/
4 1
)
3
(
)
3
(
0
x
F










,


5
/
1
)
25
/
1
(
1 25
/
2 1
)
25
/
6
(
1 0
)
3
(
4











,


5
/
1 25
/
4 1
)
25
/
8
(
1
)
25
/
1
(
1 0
)
3
(
5











,


5
/
2
)
25
/
12
(
1
)
25
/
1
(
1 25
/
3 1
0
)
3
(
6











,


M
M












5
/
1 25
/
1 1
)
25
/
2
(
1
/25 6
1
)
3
(
7
,



M
M












5
/
1
)
25
/
4
(
1 25
/
8 1
25
/
1 1
)
3
(
8
,


M
M












5
/
2 25
/
12 1
25
/
1 Так как все коэффициенты
)
3
(
j

неотрицательны (
)
3
(
0

не учитывается, то достигнутое решение
)
3
(
x
является оптимальным (в данном случае – минимальным, те.
)
25
/
4
,
25
/
7
,
25
/
9
(
*

x
(здесь учтены только исходные переменные
3 2
1
,
,
x
x
x
, остальные переменные были либо дополнительными, либо искусственными, при этом
5
/
4
)
(
)
(
min
*


x
F
x
F
. Это означает, что
4
/
5
)
(
min
1



x
F
v
A
. Отсюда имеем
4
/
1 1




A
A
v
v
. Из решения
*
x можно легко получить оптимальную стратегию для игрока A : Оптимальную стратегию для игрока B можно найти двумя способами либо составить и решить двойственную задачу линейного программирования (см. (33)-(34)), либо, исходя из принципа двойственности, получить решение из последней симплекс-таблицы предыдущего решения. Подробнее о принципе двойственности и свойствах двойственных задач линейного программирования можно почитать в [1, глава 6] и [2, глава 4]. Итак, составим вторую (двойственную к первой) задачу линейного программирования для нахождения оптимальной стратегии игрока B . По формулами матрице P

получим следующее. задача 2. Найти максимум линейной функции
y
A
v
y
y
y
y
G
max
1
)
(
3 2
1






при ограничениях















3
,
1
,
0
,
1 4
,
1 3
,
1 2
2 1
3 2
3 1
i
y
y
y
y
y
y
y
i
(50) После приведения системы ограничений к каноническому виду, получим


















6
,
1
,
0
,
1 4
,
1 3
,
1 2
6 2
1 5
3 2
4 а) Примем дополнительные переменные
4
y ,
5
y ,
6
y в качестве основных (базисных) переменных, тогда
1
y ,
2
y ,
3
y – свободные

переменные, и при
0 3
2 1



y
y
y
получим начальное базисное решение
)
1
,
1
,
1
,
0
,
0
,
0
(
)
0
(

y
. Это решение допустимо, поэтому, используя (а, можно решить задачу 2 симплекс-методом точно также как и предыдущую задачу 1. Отметим, что в этой задаче ненужно вводить искусственные переменные, но это не означает, что она будет легче решаться, чем задача 1. Укажем сначала решение задачи 2, исходя из свойств взаимно двойственных задач линейного программирования. Так, если была получена последняя симплекс-таблица предыдущей задачи 1, то решение задачи 2 ищется из последней строки этой таблицы. Именно,
)
3
(
4
*
1


y
(те. коэффициенты дополнительных переменных
4
x ,
5
x ,
6
x соответствуют оптимальному решению второй двойственной задачи,
)
3
(
5
*
2


y
,
)
3
(
6
*
3


y
. Тогда отсюда имеем Теперь решим задачу 2 непосредственно, используя двойственный симплекс-метод и таблицы. На основании (аи начального решения
)
0
(
y
составим первую симплекс-таблицу:
симплекс-таблица 1 (нулевое решение б б б
2
y
3
y
4
y
5
y
6
y

4
y 0 1
1 0
2 1
0 0
1/1 5
y 0 1
0 3
1 0
1 0
–
6
y 0 1
4 1
0 0
0 1
1/4
)
0
(
j

0
–1
–1
–1 0
0 0 Приведем расчеты коэффициентов
)
0
(
j

(см. (44), (46))
0 1
0 1
0 1
0
)
0
(
0








,


1 1
4 0
0 0
1 0
)
0
(
1










,


1 1
1 0
3 0
0 0
)
0
(
2










,


1 1
0 0
1 0
2 0
)
0
(
3










,


0 0
0 0
0 0
1 0
)
0
(
4









,


0 0
0 0
1 0
0 0
)
0
(
5









,


0 0
1 0
0 0
0 Есть три одинаковых максимальных по модулю отрицательных коэффициента
)
0
(
j

:
)
0
(
1

,
)
0
(
2

и
)
0
(
3

. Выбираем из них первый, те.
)
0
(
1

, что означает, что переменную
1
y нужно ввести в базис. Далее находим ограничения на переменную
1
y
, те. коэффициенты
i

(см. (47)). Результат приведен в столбце "

" симплекс-таблицы 1. Видно, что переменную
6
y нужно выводить из базиса и заменить ее на
1
y .

Используя общие правила перехода к новой симплекс-таблице и формулы
(48), получим следующую таблицу
симплекс-таблица 2 (первое решение б б б
2
y
3
y
4
y
5
y
6
y

4
y 0 3/4 0
–1/4 2
1 0
–1/4 3/8 5
y 0 1
0 3
1 0
1 0
1/1 1
y 1 1/4 1
1/4 0
0 0
1/4
–
)
1
(
j

1/4 0
–3/4
–1 0
0 1/4 Опустим подробные вычисления коэффициентов
)
(s
j

и приведем остальные симплекс-таблицы.
симплекс-таблица 3 (второе решение б б б
2
y
3
y
4
y
5
y
6
y

3
y 1 3/8 0
–1/8 1
1/2 0
–1/8
–
5
y 0 5/8 0
25/8 0
–1/2 1
1/8 1/5 1
y 1 1/4 1
1/4 0
0 0
1/4 1
)
2
(
j

5/8 0
–7/8 0
1/2 0
1/8
симплекс-таблица 4 (третье решение б б б
2
y
3
y
4
y
5
y
6
y

3
y 1 2/5 0
0 1
12/25 1/25
–3/25 2
y 1 1/5 0
1 0
–4/25 8/25 1/25 1
y 1 1/5 1
0 0
1/25
–2/25 6/25
)
3
(
j

4/5 0
0 0
9/25 7/25 4/25 В четвертой таблице все коэффициенты
)
3
(
j

неотрицательны, поэтому достигнутое решение
)
3
(
y
является оптимальным (в данном случае – максимальными (такое же решение получилось выше из предыдущей задачи на основании принципа двойственности, при этом
5
/
4
)
(
)
(
max
*


y
G
y
G
, те.
4
/
5
)
(
max
1



y
G
v
A
. Отсюда
4
/
1 1



