Задание 6.Дана платежная матрица игры. Найти седловые точки и оптимальные стратегии игроков.
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
Задание 7. Дана платежная матрица игры. Решить графически игру.
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
Задание 8. Дана платежная матрица игры. Найти решение игры путем сведения ее к задаче линейного программирования.
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
27.
29.
30.
Примеры решения заданий
Задачи линейного программирования
Пример 1.Решить ЗЛП f(x) =3x1 + 2x2 ® max
x1 + x2 £ 4,
2x1 + x2 £ 6,
x1 ³ 0, x2 ³ 0,
a) графически, b) симплекс-методом.
a) Шаг 1. Строится множество D допустимых решений задачи, оно представляет собой четырехугольник ОABC на плоскости x1О x2 с вершинами в точках О, А, В, С, с координатами (0; 0), (0; 4), (2; 2), (3; 0), соответственно.
Шаг 2. Из начала координат откладывается вектор-градиент функции f(x), указывающий направления ее возрастания.
Шаг 3. Строится прямая 3x1 + 2x2 = const– линия уровня функции f(x), перпендикулярная вектору градиента .
Шаг 4. Линия уровня 3x1 + 2x2 = constпередвигается в направлении вектора до тех пор, пока она не покинет область D. Крайняя точка области, в которой линия уровня покидает допустимую область, и является решением задачи. В данном случае – это точка В(2; 2).
Шаг 5.Находится оптимальное значение функции.
f *(2; 2) =3x1 + 2x2 = 3 × 2 + 2 × 2 = 10.
b) Шаг 1. Задача приводится к специальному виду, для этого к левым частям неравенств прибавляются дополнительные переменные x3 и x4, превращающие неравенства в равенства.
f(x) =3x1 + 2x2 ® max
x1 + x2 + x3 = 4,
2x1+ x2 + x4 = 6,
xj ³ 0,
Переменные x3 и x4 входят в первое и второе уравнения соответственно с коэффициентами единица, тогда х3 , х4 – начальный базис, x1 , x2 – свободные переменные, b– вектор ограничений.
Шаг 4. Разрешающую строку определяют следующим образом: рассчитываются так называемые симплексные отношения, т. е. отношения текущих значений базисных переменных к положительным коэффициентам разрешающего столбца, соответствующим данным базисным переменным. Затем берется минимальное из этих отношений и по тому, какой строке оно соответствует, определяется ведущая строка.
Шаг 5. Находится разрешающий элемент, он расположен на пересечении разрешающей строки и разрешающего столбца (в нашем случае он равен 2).
Шаг 6. Определяются переменные, которые будут исключены из базиса и включены в него. Переменную, которой соответствует разрешающий столбец, включаются в базис вместо переменной, которой соответствует разрешающая строка. В базис вводим переменную x1, которому соответствует минимальное значение cj. Из базиса выводится x4, так как минимальное q достигается в этой строке формулой .
Таким образом, элемент a41 будет разрешающим (в таблице выделен серым цветом).
Шаг 7. Заполняем таблицу, соответствующую новому базисному решению.
свободные
q
базис
х4
х2
b
х3
- 0,5
0,5
0,5 / 1Ü min
х1
0,5
0,5
0,5 / 3
f(x)
1,5
- 0,5
Ýmin
Шаг 8. Так как в строке f(x) оценок полученного нового плана имеется отрицательное значение сj , приступаем к следующей итерации, продолжая улучшать план.
б\с
x4
x3
b
x2
x1
f(x)
Поскольку все сj ³ 0, то план, представленный в данной таблице, будет оптимальным.
Ответ: f *(x) =10; x1* = 0; x2*= 6
Пример 2. Решить каноническую задачу линейного программирования:
f(Х) = х1 - 2х2 - 2x3 ® max
x1 + 4x2 + x3 = 5,
x1 - 2x2 - x3 = -1,
xj ³ 0,
Данная каноническая задача линейного программирования (КЗЛП) не является специальной (СЗЛП), поэтому применяем метод искусственного базиса. Строим вспомогательную задачу линейного программирования и приводим ее к специальному виду, выражая целевую функцию через небазисные переменныеxj , j=1,…,3. Эта задача имеет вид:
функции f(x), указывающий направления ее возрастания.
.