Экономико-математические методы и иодели

 

Наибольшая сумма констант приведения равна (6 + 0) = 6 для ребра (3,5), значит, множество разбивается на два подмножества (3,5) и (3*,5*). Нижняя граница гамильтоновых циклов этого подмножества:

i  j	1	4	5	di
3	6	∞	∞	6
5	0	0	∞	0
6	∞	5	0	0
dj	0	0	0	6

 

В результате получим  другую сокращенную матрицу (2 x 2), которая подлежит операции приведения. После операции приведения сокращенная матрица будет иметь вид:

i  j	1	4	di
5	0	0	0
6	∞	5	5
dj	0	0	5

 

Поскольку нижняя граница  этого подмножества (3,5) меньше, чем  подмножества (3*,5*), то ребро (3,5) включаем в маршрут.

В соответствии с этой матрицей включаем в гамильтонов  маршрут ребра (5,1) и (6,4).

В результате по дереву ветвлений  гамильтонов цикл образуют ребра:

(1,6), (6,4), (4,2), (2,3), (3,5), (5,1), длина маршрута равна F(M) = 17

В данной задаче требуется посетить все вершины графа и вернуться в исходную вершину, минимизировав затраты на проезд (или минимизировав время).

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

 

Ответ:  маршрут  (1,6), (6,4), (4,2), (2,3), (3,5), (5,1), длина маршрута равна F(M) = 17

 

 

Задание № 3

Решить матричную игру, заданную ниже платёжной матрицей, сведя ее к парам двойственных задач линейного программирования:

Решение

1. Проверяем, имеет ли платежная матрица седловую точку. Если да, то выписываем решение игры в чистых стратегиях.

Считаем, что игрок I выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а игрок II выбирает свою стратегию так, чтобы минимизировать выигрыш игрока I.

Игроки	B1	B2	B3	B4	a = min(Ai)
A1	6	5	7	10	5
A2	7	2	6	4	2
A3	2	0	6	8	0
A4	9	7	10	5	5
b = max(Bi)	9	7	10	10	0

 

Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(a_i) = 5, которая указывает на максимальную чистую стратегию A₁. Верхняя цена игры b = min(b_j) = 7.

Что свидетельствует  об отсутствии седловой точки, так как a ≠ b, тогда цена игры находится в пределах 5 ≤ y ≤ 7. Находим решение игры в смешанных стратегиях. Объясняется это тем, что игроки не могут объявить противнику свои чистые стратегии: им следует скрывать свои действия. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии).

 

2. Проверяем платежную матрицу на доминирующие строки и доминирующие столбцы.

Иногда на основании  простого рассмотрения матрицы игры можно сказать, что некоторые  чистые стратегии могут войти в оптимальную смешанную стратегию лишь с нулевой вероятностью.

Говорят, что i-я стратегия 1-го игрока доминирует его k-ю стратегию, если a_ij ≥ a_kj для всех j Э N и хотя бы для одного j a_ij > a_kj. В этом случае говорят также, что i-я стратегия (или строка) – доминирующая, k-я – доминируемая.

Говорят, что j-я стратегия 2-го игрока доминирует его l-ю стратегию, если для всех j Э M  a_ij ≤ a_il и хотя бы для одного i a_ij < a_il. В этом случае j-ю стратегию (столбец) называют доминирующей, l-ю – доминируемой.

Стратегия A1 доминирует над стратегией A3 (все элементы строки 1 больше или равны значениям 3-ой строки), следовательно исключаем 3-ую строку матрицы. Вероятность p3 = 0.

6	5	7	10
7	2	6	4
9	7	10	5

 

С позиции проигрышей игрока В стратегия B3 доминирует над  стратегией B2 (все элементы столбца 3 больше элементов столбца 2), следовательно исключаем 3-ой столбец матрицы.

Вероятность q3 = 0.

6	5	10
7	2	4
9	7	5

 

Мы свели игру 4 x 4 к  игре 3 x 3.

Так как игроки выбирают свои чистые стратегии случайным  образом, то выигрыш игрока I будет случайной величиной. В этом случае игрок I должен выбрать свои смешанные стратегии так, чтобы получить максимальный средний выигрыш.

Аналогично, игрок II должен выбрать свои смешанные стратегии  так, чтобы минимизировать математическое ожидание игрока I.

 

3. Найдем решение игры в смешанных стратегиях.

Математические модели пары двойственных задач линейного  программирования можно записать так:

найти минимум функции F(x) при ограничениях:

6x₁+7x₂+9x₃ ≥ 1

5x₁+2x₂+7x₃ ≥ 1

10x₁+4x₂+5x₃ ≥ 1

F(x) = x₁+x₂+x₃ → min

найти максимум функции  Ф(y) при ограничениях:

6y₁+5y₂+10y₃ ≤ 1

7y₁+2y₂+4y₃ ≤ 1

9y₁+7y₂+5y₃ ≤ 1

Ф(y) = y₁+y₂+y₃ → max

 

Решаем первую систему симплексным методом..

Для построения первого  опорного плана систему неравенств приведем к канонической форме путем введения дополнительных переменных.

6x₁ + 7x₂ + 9x₃-1x₄ + 0x₅ + 0x₆ = 1

5x₁ + 2x₂ + 7x₃ + 0x₄-1x₅ + 0x₆ = 1

10x₁ + 4x₂ + 5x₃ + 0x₄ + 0x₅-1x₆ = 1

Умножим все строки на (-1) и будем искать первоначальный опорный план.

-6x₁-7x₂-9x₃ + 1x₄ + 0x₅ + 0x₆ = -1

-5x₁-2x₂-7x₃ + 0x₄ + 1x₅ + 0x₆ = -1

-10x₁-4x₂-5x₃ + 0x₄ + 0x₅ + 1x₆ = -1

Матрица коэффициентов A = a(ij) этой системы уравнений имеет  вид:

 

Решим систему уравнений относительно базисных переменных:

x₄, x₅, x₆,

Полагая, что свободные переменные равны 0, получим первый опорный план: X1 = (0,0,0,-1,-1,-1)

Базис	B	x1	x2	x3	x4	x5	x6
x4	-1	-6	-7	-9	1	0	0
x5	-1	-5	-2	-7	0	1	0
x6	-1	-10	-4	-5	0	0	1
F(X0)	0	1	1	1	0	0	0

 

План 0 в симплексной  таблице является псевдопланом, поэтому  определяем ведущие строку и столбец.

На пересечении ведущих  строки и столбца находится разрешающий элемент = -9.

 

Базис	B	x1	x2	x3	x4	x5	x6
x4	-1	-6	-7	-9	1	0	0
x5	-1	-5	-2	-7	0	1	0
x6	-1	-10	-4	-5	0	0	1
F(X0)	0	1	1	1	0	0	0
θ	0	1 : (-6) = -1/6	1 : (-7) = -1/7	1 : (-9) = -1/9	-	-	-

Выполняем преобразования симплексной таблицы методом  Жордано-Гаусса.

 

Базис	B	x1	x2	x3	x4	x5	x6
x3	1/9	2/3	7/9	1	-1/9	0	0
x5	-2/9	-1/3	34/9	0	-7/9	1	0
x6	-4/9	-62/3	-1/9	0	-5/9	0	1
F(X0)	-1/9	1/3	2/9	0	1/9	0	0

 

План 1 в симплексной  таблице является псевдопланом, поэтому  определяем ведущие строку и столбец.

На пересечении ведущих  строки и столбца находится разрешающий  элемент (РЭ), равный (^-5/₉).

 

Базис	B	x1	x2	x3	x4	x5	x6
x3	1/9	2/3	7/9	1	-1/9	0	0
x5	-2/9	-1/3	34/9	0	-7/9	1	0
x6	-4/9	-62/3	-1/9	0	-5/9	0	1
F(X0)	-1/9	1/3	2/9	0	1/9	0	0
θ	0	1/3 : (-62/3) = -1/20	2/9 : (-1/9) = -2	-	1/9 : (-5/9) = -1/5	-	-