Методы оптимальных решений

 

	B1		B2		B3		B4		B5		Запасы	Ui
A1		5		4		10		7		8	740	5
	80		660
A2		7		6		7		10		6	600	6
									600
A3		2		9		5		3		4	560	2
	560
A4		6		11		4		12		5	600	5
					470				130
A5		0		0		0		0		0	500	0
	0						250		250
Потребности	640		660		470		250		980
Vj	0		-1		-1		0		0

 

Общие затраты на перевозку всей продукции, для оптимального плана составляют:

Pопт=

10290

 

 

Теория игр

 

1. Решить игру  с матрицей (тип 2хn). В ответе указать цену игры и вероятности применения стратегий, т.е. v, p, q.

Решение

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

Игроки	B1	B2	B3	B4	B5	a = min(Ai)
A1	-9	0	-4	3	7	-9
A2	2	-1	0	-2	-3	-3
b = max(Bi)	2	0	0	3	7

 
Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(ai) = -3, которая указывает на максимальную чистую стратегию A2. 
Верхняя цена игры b = min(bj) = 0.

Cедловая точка отсутствует, так как a ≠ b, тогда цена игры находится в пределах -3 ≤ y ≤ 0. Находим решение игры в смешанных стратегиях.

Доминирующихся и дублирующих стратегий ни у одного из игроков нет.

Максиминной оптимальной стратегии игрока A соответствует точка N, лежащая на пересечении прямых B3B3 и B4B4, для которых можно записать следующую систему уравнений:

 
Цена игры,

Теперь можно найти минимаксную стратегию игрока B, записав соответствующую систему уравнений, исключив стратегию B1,B2,B5, которая дает явно больший проигрыш игроку B, и, следовательно,

Цена игры: ,

стратегии игроков:   

2. Решить игру  с матрицей (тип mх2). В ответе указать цену игры и вероятности применения стратегий, т.е. v, p, q.

 

Решение

Исследуем на наличие седловой точки

Седловой точки нет, нет и решения в чистых стратегиях. 

Решаем в смешанных стратегиях

Запишем систему уравнений. 
Для игрока I

Для игрока II

 
Решаем симплекс-методом

 

 

Базис
	-4	-1	1	0	0	0	0	1	-
	4	-7	0	1	0	0	0	1	1.4
	1	-5	0	0	1	0	0	1	1
	0	-4	0	0	0	1	0	1	-
	3	-1	0	0	0	0	1	1	1/3
	1	1	0	0	0	0	0	0
	0	-8	1	1	0	0	0	2
	1	-7/4	0	1/4	0	0	0	1/4
	0	-13/4	0	-1/4	1	0	0	3/4
	0	-3/2	0	3/2	0	1	0	5/2
	0	-4	0	0	0	0	1	1
	1	11/4	0	-1/4	0	0	0	1/4

 

            Цена игры равна  

Для игрока A оптимальная стратегия, учитывая, что имеем:

Согласно двойственной задаче для игрока Б оптимальная стратегия, учитывая,

что имеем:

 

3. Найти точки равновесия в биматричной игре (A – матрица выигрышей игрока 1, B – матрица выигрышей игрока 2)

 

 

Решение

В каждом столбце матрицы A найдем максимальный элемент. Эти элементы подчеркнуты в матрице A.

Затем в каждой строке матрицы B выберем наибольший элемент. Эти элементы подчеркнуты в матрице B. Их положение будет определять приемлемые ситуации 2-го игрока, когда первый игрок выбрал стратегию i соответственно. 
Платежная матрица игрока А:

9	6
4	10

 
Платежная матрица игрока B:

0	4
11	7

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

Итак, чтобы в биматричной игре:  А=(a), В = (b) пара (p,q);

определяемая равновесную ситуацию, необходимо и достаточно одновременное выполнение следующих неравенств:

(p–1)(Cq-α) ≥ 0, p(Cq-α) ≥ 0; 0 ≤ p ≤ 1

(q-1)(Dp-β) ≥ 0, q(Dp-β) ≥ 0; 0 ≤ q ≤ 1

C = a11 - a12 - a21 + a22

α = a22- a12

D = b11-b12-b21+b22

β = b22-b21 
C = 9 - 6 - 4 + 10 = 9

α = 10 - 6 = 4

D = 0 - 4 - 11 + 7 = -8

β = 7 - 11 = -4

(p–1)(9q-4) ≥ 0

p(9q-4) ≥ 0

(q-1)(-8p+4) ≥ 0

q(-8p+4) ≥ 0

получаем, что:

1) p=1,q ≥4/9 
p=0, q ≤ 4/9 
0 ≤ p ≤ 1, q=4/9 
2) q=1,p ≥ 1/2 
q=0, p ≤ 1/2 
0 ≤ q ≤ 1, p=1/2 
Цена игры 
Ha(1/2;4/9) = 71/3 
Hb(1/2;4/9) = 51/2 
P* = (1/2;1/2); Q* = (4/9;5/9). 
Выигрыш игроков в равновесной ситуации: 
f(P*,Q*) = (71/3;51/2).

 

 

4. Имеется три предприятия (I, II, III); которые выпускают продукцию №1, продукцию №2 и продукцию №3.Следующая таблица представляет общие выпуски продукции по каждому предприятию. Продукция продается комплектами (1ед. №1, 1ед. №2 и 1ед. №3). Спрос неограничен. Комплект стоит 1 тыс. руб. Требуется решить вопрос о целесообразности объединения предприятий, найти максимальный возможный доход объединения, справедливый дележ – вектор Шепли. В левом верхнем углу указан номер варианта.

 

 

5. Располагая информацией о количестве голосов, которыми располагают партии, и о размере выигрывающей коалиции, найти веса партий при голосовании.

    1              2                 3               4                       Размер выигрывающей коалиции                          

36,9%      28,2%       17,4%        17,4%                                           58%

 

 

Решение

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

{1; 2} {1; 2; 3}, {1; 2; 4},  {1; 3; 4}, {2; 3; 4} {1; 2; 3; 4}.

Определяем все выигрывающие коалиции, но не выигрывающие без 3-го игрока:

{1; 3; 4}, {2; 3; 4}.

В коалиции  имеется  t = 3 игрока, поэтому

.

Аналогично получаем, что .

При нахождении j2 необходимо учитывать, что имеется 3 коалиции, которые выигрывают, а коалиция без 2-й партии не выигрывает. Определяем все выигрывающие коалиции, но не выигрывающие без 2-го игрока: {1; 2} {1; 2; 3}, {1; 2; 4},  {2; 3; 4} .

.

И на первую партию остается

В результате получаем, что вектор Шепли равен .

Веса партий (72%; 12%; 8%;8%)

6. Найти гарантированные выигрыши игроков без кооперирования, Парето- оптимальное множество, переговорное множество, точку Нэша для задания 3.

 

Решение

	A	B
A	9,0	6,4
B	4,11	10,7

Равновесия по Нэшу в чистых стратегиях не существует. Будем искать решение в смешанных стратегиях x={x1, x2} и y={y1, y2} соответственно, где 0≤xi≤1, 0≤yj≤1, x1+x2=1, y1+y2=1.

Легко проверить, что в этой игре нет доминирующих стратегий, нет также равновесных исходов, так как от любого исхода игроки могут отклониться, действуя в своих интересах.

Имеем систему:

Подставляя, имеем

Точки равновесия нет,