|
||||||||||||
Примеры решения заданий. свободные. свободные. Теория игр ⇐ ПредыдущаяСтр 2 из 2 В 1 |
В 2 | |||||||||||
B1 | B2 | B3 | B4 | B1 | B2 | B3 | B4 | |||||
A1 | A1 | |||||||||||
A2 | A2 | |||||||||||
A3 | A3 | |||||||||||
В 3 |
В 4 | |||||||||||
B1 | B2 | B3 | B4 | B1 | B2 | B3 | B4 | |||||
A1 | A1 | |||||||||||
A2 | A2 | |||||||||||
A3 | A3 | |||||||||||
В 5 |
В 6 | |||||||||||
B1 | B2 | B3 | B4 | B1 | B2 | B3 | B4 | |||||
A1 | A1 | |||||||||||
A2 | A2 | |||||||||||
A3 | A3 | |||||||||||
В 7 | В 8 | |||||||||||
B1 | B2 | B3 | B4 | B1 | B2 | B3 | B4 | |||||
A1 | A1 | |||||||||||
A2 | A2 | |||||||||||
A3 | A3 | |||||||||||
В 9 |
В 10 | |||||||||||
B1 | B2 | B3 | B4 | B1 | B2 | B3 | B4 | |||||
A1 | A1 | |||||||||||
A2 | A2 | |||||||||||
A3 | A3 | |||||||||||
В 11 |
В 12 | |||||||||||
B1 | B2 | B3 | B4 | B1 | B2 | B3 | B4 | |||||
A1 | A1 | |||||||||||
A2 | A2 | |||||||||||
A3 | A3 | |||||||||||
В 13 | В 14 | |||||||||||
B1 | B2 | B3 | B4 | B1 | B2 | B3 | B4 | |||||
A1 | A1 | |||||||||||
A2 | A2 | |||||||||||
A3 | A3 | |||||||||||
В 15 | В 16 | |||||||||||
B1 | B2 | B3 | B4 | B1 | B2 | B3 | B4 | |||||
A1 | A1 | |||||||||||
A2 | A2 | |||||||||||
A3 | A3 | |||||||||||
В 17 | В 18 | |||||||||||
B1 | B2 | B3 | B4 | B1 | B2 | B3 | B4 | |||||
A1 | A1 | |||||||||||
A2 | A2 | |||||||||||
A3 | A3 | |||||||||||
В 19 | В 20 | |||||||||||
B1 | B2 | B3 | B4 | B1 | B2 | B3 | B4 | |||||
A1 | A1 | |||||||||||
A2 | A2 | |||||||||||
A3 | A3 | |||||||||||
В 21 | В 22 | |||||||||||
B1 | B2 | B3 | B4 | B1 | B2 | B3 | B4 | |||||
A1 | A1 | |||||||||||
A2 | A2 | |||||||||||
A3 | A3 | |||||||||||
В 23 | В 24 | |||||||||||
B1 | B2 | B3 | B4 | B1 | B2 | B3 | B4 | |||||
A1 | A1 | |||||||||||
A2 | A2 | |||||||||||
A3 | A3 | |||||||||||
В 25 | В 26 | |||||||||||
B1 | B2 | B3 | B4 | B1 | B2 | B3 | B4 | |||||
A1 | A1 | |||||||||||
A2 | A2 | |||||||||||
A3 | A3 | |||||||||||
В 27 | В 28 | |||||||||||
B1 | B2 | B3 | B4 | B1 | B2 | B3 | B4 | |||||
A1 | A1 | |||||||||||
A2 | A2 | |||||||||||
A3 | A3 | |||||||||||
В 29 | В 30 | |||||||||||
B1 | B2 | B3 | B4 | B1 | B2 | B3 | B4 | |||||
A1 | A1 | |||||||||||
A2 | A2 | |||||||||||
A3 | A3 | |||||||||||
Задание 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 – вектор ограничений.
Шаг 2. Составляется соответствующая симплекс - таблица:
базис |
свободные
Ýmin
Так как свободные переменные всегда равны нулю, то для данного начального базиса f(x) будет равна нулю:
f(x) = с0 - åci хi = 0 × 2 + 0 × 6 = 0.
Так как имеются сj < 0, приступаем к улучшению плана.
Шаг 3. Выбирается разрешающий j-й столбец, соответствующий наименьшему отрицательному сj.
Шаг 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. Эта задача имеет вид:
h(Х) = – ( t1+ t2) = – 6 + 6 x2 + 2 x3 ® max
x1 + 4x2 + x3 + t1 = 5,
x1 - 2x2 - x3 + t2 = -1,
все xj ≥ 0, ti ≥ 0.
Решаемспециальную задачу линейного программирования симплекс-методом:
б\с | x1 | x2 | x3 | b | б\с | x1 | x2 | t2 | b | б\с | t1 | x2 | t2 | b | ||
t1 | t1 | -1 | x1 | 0.5 | -0,5 | |||||||||||
t2 | -1 | x3 | -1 | x3 | 0,5 | 0,5 | ||||||||||
h | -6 | -2 | -6 | h | -2 | -2 | -4 | h | ||||||||
| | |||||||||||||||
f | -1 | f | -2 | -2 | f | -0,5 | -3 | 5/2 | -4 |
Так как max h = 0, то множествоХ допустимых решений КЗЛП не пусто, т. е.
Х ¹ Æ, поэтому существует СЗЛП, эквивалентная данной КЗЛП. Эта задача имеет вид: f(Х) = - 4 + 3х2 ® max
x1 + x2 = 2,
3x2 + x3 = 3,
все xj ≥ 0.
Линейные уравнения этой системы и f(Х) получены из завершающей симплекс-таблицы вспомогательной задачи.
Решаем специальную задачу линейного программирования симплекс-методом:
б\с | х2 | b | б\с | х3 | b | |
х1 | х1 | -1/3 | ||||
х3 | х2 | 1/3 | ||||
f | -3 | -4 | f | -1 | ||
|
Отсюда оптимальный план Х*(1; 1; 0), fmax = -1.
Пример 3.Решить задачу линейного программирования симплекс-методом, составить двойственную задачу и найти ее решение.
Z = 6x1 + 5 x2 + 4x3 + 3x4 ® max
2x1+ 3x2 + 2x3 + x4 £ 25,
4x1 + x2 + 3x3 + 2x4 £ 30,
3x1 +5 x2 + 2x3 + 2x4 £ 42,
все xj ≥ 0.
Математическая модель прямой задачи Z = 6x1 + 5x2 + 4x3 + 3x4 ® max 2x1 + 3x2 + 2x3 + x4 £ 25, 4x1 + x2 + 3x3 +2x4 £ 30, 3x1 + 5x2 + 2x3 + 2x4 £ 42, x1≥ 0, x2≥ 0, x3≥ 0, x4≥ 0. | Математическая модель двойственной задачи f = 25y1+ 30y2 + 42y3 ® min y1 ≥ 0, y2 ≥ 0, y3 ≥ 0, 2y1 + 4y2 + 3y3 ≥ 6, 3y1 + y2 + 5y3 ≥ 5, 2y1 + 3y2 + 2y3 ≥ 4, y1 + 2y2 + 2y3 ≥ 3. |
Специальный вид Z= 6x1+5x2+4x3+3x4 ® max 2x1+3x2+2x3+x4+S1=25, 4x1+x2+3x3+2x4+S2=30, 3x1+5x2+2x3+2x4+S3=42, x1, x2, x3, x4, S1, S2, S3 ≥ 0 |
| S2 | x2 | x3 | x4 | b |
| |||||||||||||||
S1 | -0,5 | 2,5 | 0,5 | |||||||||||||||||||
x1 | 0,25 | 0,25 | 0,75 | 0,5 | 7,5 | |||||||||||||||||
S3 | -0,75 | 4,25 | -0,25 | 0,5 | 19,5 | 4,58 | ||||||||||||||||
Z | 1,5 | -3,5 | 0,5 |
| ||||||||||||||||||
|
| |
|
|
|
| ||||||||||||||||
x1 | x2 | x3 | x4 | b |
|
|
| S2 | x2 | x3 | x4 | b | ||||||||||
S1 | 12,5 |
| x2 |
|
| |||||||||||||||||
S2 | 7,5 |
| x1 |
|
| 6,5 | ||||||||||||||||
S3 |
| S3 |
|
| 2,5 | |||||||||||||||||
Z | -6 | -5 | -4 | -3 |
|
| Z | 0,8 | 1,4 | 1,2 | ||||||||||||
|
|
|
|
|
|
|
|
| ||||||||||||||
Х*(6.5, 4, 0, 0), Z*=59.
Решение двойственной задачи можно найти с помощью второй теоремы двойственности:
(2x1+ 3x2 + 2x3 + x4 - 25) у1 = 0 Þ(2 • 6,5 + 3 • 4 - 25) у1 = 0 Þ 0 = 0,
(4x1+ x2 + 3x3 + 2x4 - 30) у2 = 0 Þ (4 • 6,5 + 4 - 30) у2 = 0 Þ 0 = 0,
(3x1 + 5x2 + 2x3 + 2x4 – 42) у3 = 0 Þ (3 • 6,5 + 5 • 4 - 42) у3 = 0Þ
Þ -2,5у3 = 0 Þ у3 = 0,
(2y1 + 4y2 + 3y3 – 6) х1 = 0 Þ (2y1 + 4y2 + 3y3 –6) 6,5 = 0 Þ (2y1 + 4y2 +3y3 – 6 = 0),
(3y1 + y2 + 5y3 – 5) х2 = 0 Þ (3y1 + y2 + 5y3 – 5) 4 = 0 Þ (3y1 + y2 + 5y3 – 5 = 0),
(2y1 + 3y2 + 2y3 – 4) х3 = 0 Þ (2y1 + 3y2 + 2y3 – 4) 0 = 0 Þ 0 = 0,
(y1 + 2y2 + 2y3 – 3) х4 = 0 Þ 0 = 0.
Решая систему у3 = 0; 2y1 + 4y2 + 3y3 – 6 = 0; 3y1 + y2 + 5y3 – 5 = 0,
находим у1 = 1,4; у2 = 0,8; у3 = 0; f * = 25 • 1,4 + 30 • 0,8 + 42 • 0 = 59.
Пример 4.Решить целочисленную задачу линейного программирования методом Гомори. f(Х) =2х1+х2® max
2x1 + x3 =3,
2х1+ 3x2 +x4 =6,
все xj ≥ 0.
Сначала находится решение задачи симплекс-методом.
б\с | x1 | x2 | b | б\с | x3 | x2 | b | б\с | x3 | x4 | b | ||
x3 | x1 | 1/2 | 3/2 | x1 | 1/2 | 3/2 | |||||||
x4 | x4 | -1 | x2 | -1/3 | 1/3 | ||||||||
|
© helpiks.su При использовании или копировании материалов прямая ссылка на сайт обязательна.
|
|