Алгоритм решения тз методом потенциалов

	B1	B2	B3	B4	B5
A1	7	3	5	4	2	40
	-	0	-	-	40
A2	- 6	2	+ 3	1	7	150
	1 0	80	-	60	-
A3	+ 3	5	- 2	6	4	100
	10	-	90	-	-
	20	80	90	60	40

1. Построить опорный план по одному из трех правил (см. выше).

2. Вычислить потенциалы поставщиков и потребителей, решив систему уравнений вида u_i + v_j = c_ij.

3. Вычислить оценки для всех свободных клеток по формуле S_ij = c_ij – (u_i + v_j). Если все S_ij0, следовательно, план оптимален, иначе строится цикл по более перспективной клетке.

Пример

С трех складов необходимо доставить овощи в пять торговых точек. Требуется закрепить за торговыми точками склады так, чтобы общая сумма затрат на перевозку была минимальна.

_i a_i = _j b_j: 290 = 290.

m + n – 1 = 7

7	3	5	4	2
-	0	-	-	40
- 6	2	+ 3	1	7
0	80	10	60	-
+ 3	5	- 2	6	4
20	-	80	-	-

S₁₁ = 7 – (u₁+v₁) = 7 - (0+7) = 0

S₁₃ = 5 – (u₁+v₃) = 5 – (0+6) = -1 < 0 !

S₁₄ = 4 – (0+2) = 2

S₂₃ = 3 – (-1+6) = -2 < 0 !

S₂₅ = 7 – (-1+2) = 6

S₃₂ = 5 – (-4+3) = 6

S₃₄ = 6 – (2-4) = 8

S₃₅ = 4 – (2-4) = 6

min {S₁₃; S₂₃} = S₂₃ = -2  цикл (2,3)(2,1)(3,1)(3,3)(2,3)

S₁₁ = 7 – (u₁+v₁) = 7 - (0+5) = 2

S₁₃ = 5 – (u₁+v₃) = 5 – (0+4) = 1

S₁₄ = 4 – (0+2) = 2

S₂₃ = 3 – (-1+4) = 0

S₂₅ = 7 – (-1+2) = 6

S₃₂ = 5 – (-2+3) = 4

S₃₄ = 6 – (-2+2) = 6

S₃₅ = 4 – (-2+2) = 4

f(x) = 2*40 + 2*80 + 3*10 + 1*60 + 3*20 + 2*80 = 550

Матричные игры. Решение матричных игр в чистых стратегиях. Сведение матричной игры к задаче линейного программирования.

Матричные игры (ми) с нулевой суммой

Теория игр занимается разработкой различного рода рекомендаций по принятию решений в условиях конфликтных ситуаций. Конфликтные ситуации математически можно представить как игру из 2-х, 3-х или более игроков, каждый их которых преследует цель максимизации своего выигрыша за счет другого игрока.

Стратегия – совокупность правил, однозначно определяющих последовательность действий стороны в конкретной конфликтной ситуации.

Игра – это совокупность оговоренных правил и условий. Термин «партия» связан с частично возможной реализацией этих правил.

Суть теории МИ состоит в следующем: изучается проблема – если в игре участвуют n игроков P₁, P₂, …, P_n, то как должен вести себя j-й игрок для достижения наиболее благоприятного для себя исхода. В конце каждой партии (игры) игрок P_j получает v_j, которая называется выигрышем. При этом каждый игрок стремится максимизировать общую сумму выигрыша. Числа v_j (j=1,n) могут быть положительными, отрицательными или равными нулю. Если v_j>0  игрок в выигрыше, v_j<0  игрок в проигрыше, если v_j=0  ничья.

В большинстве случаев имеем игры с нулевой суммой, т.е. v₁+v₂+…+v_n=0, где сумма выигрыша переходит от одного игрока к другому, не поступая из внешних источников.

Ход – принятие игроком того или иного решения в процессе игры и его реализация. Если ход выбирается сознательно, то это личный ход, а если с помощью случайного выбора, то случайный ход.

Будем рассматривать игры двух партнеров с нулевой суммой и конечным числом возможных ходов.

Конечная игра – игра, где каждый из игроков имеет конечное число возможных стратегий.

Стратегии игроков		Р2
		Орел	Решка
Р1	Орел	1	-1
	Решка	-1	1

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

Пример

Первый игрок Р₁ выбирает одну из сторон монеты, второй игрок Р₂, не зная выбора первого, также выбирает одну из сторон монеты. После того, как оба игрока произвели свой выбор и монета брошена, игрок Р₂ платит игроку Р₁ одну единицу, если выбранные стороны монеты совпали, и –1 единицу, если не совпали. –1 означает проигрыш Р₁. Р₁ играет на максимум, а Р₂ на минимум. Условия игры задаются матрицей. Строки матрицы соответствуют возможным стратегиям игрока Р₁, а столбцы – возможным стратегиям игрока Р₂. Если Р₁ выбирает строку, а Р₂ – столбец, партия завершается, и выигрыш игрока Р₁ равен числу, стоящему на пересечении строки и столбца.