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

	B1	B2	B3	B4	B5
A1
-		-	-
A2	- 6		+ 3
10		-		-
A3	+ 3		- 2
	-		-	-

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

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

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

Пример

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

S_i a_i = S_j b_j: 290 = 290.

m + n – 1 = 7

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 получает Sv_j, которая называется выигрышем. При этом каждый игрок стремится максимизировать общую сумму выигрыша. Числа v_j (j=1,n) могут быть положительными, отрицательными или равными нулю. Если v_j>0 Þ игрок в выигрыше, v_j<0 Þ игрок в проигрыше, если v_j=0 Þ ничья.

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

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

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

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

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

Пример

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

Пример «Игра в 3 пальца».

Игроки Р₁ и Р₂ одновременно и независимо друг от друга показывают 1, 2 или 3 пальца. Размер выигрыша определяется общим количеством показанных пальцев. Если число пальцев четное, то выигрывает игрок Р₁, если нечетное – игрок Р₂.

i – количество пальцев игрока Р₁,

j – количество пальцев игрока Р₂.

Матрица построена для игрока Р₁.

Элемент а₂₃ = -5 означает проигрыш игрока Р₁ в 5 единиц и выигрыш этих единиц игрока Р₂.

В общем случае МИ задается прямоугольной матрицей размерности mxn. Номер строки матрицы соответствует номеру A_i – стратегии игрока P₁; номер столбца соответствует B_j стратегии игрока Р₂. Эта игра однозначно определяется следующей матрицей A=[a_ij]_mxn, где a_ij - действительное число, которое представляет собой сумму выигрыша, уплачиваемую игроком Р₂ игроку Р₁, если Р₁ выбирает стратегию, которая соответствует i-й строке, а Р₂ выбирает стратегию j-го столбца. МИ записывают в виде таблицы, которая называется платежной матрицей.

Каждый игрок выбирает наиболее выгодную стратегию. Первый игрок всегда стремится выбрать стратегию с максимальным выигрышем, тогда второй игрок стремится выбрать стратегию с минимальным проигрышем.

Нижняя чистая цена игры – максимин – число, равное максимальному по j из минимальных по i.

a = max_j(min_i a_ij).

Верхняя чистая граница – минимакс– число, равное минимальному по j из максимальных по i.

b = min_j(max_i a_ij).

Стратегии игроков, соответственно называются минимаксными или максиминными.

Пример.Найти минимаксную и максиминную стратегии игроков в МИ.

a = max_j (min_i a_ij) = max a_i = 3;

b = min_j (max_i a_ij) = min b_j = 5.

Вывод. Какой бы выбор по столбцам ни сделал игрок В, выигрыш игрока А в худшем случае составит –3, 3, 1, 2. Игрок А выбирает стратегию с макс. выигрышем, a = 3, т.е. выбирается стратегия А₂. В худшем случае игрок В может проиграть 5, 7, 8, 9. Игрок В минимизирует свой проигрыш, поэтому он выбирает стратегию В₁.