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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ

ФГБОУ ВО «Уральский государственный экономический университет»

Центр дистанционного образования

Контрольная работа по дисциплине «Теория игр»

Исполнитель: А.М. Поздеева

Студент группы: ФБУ-16ТД

Екатеринбург

2017



1

0	-3	4
8	5	7
1	8	6
1	3	2

Критерий Лапласа.

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

q₁ = q₂ =... = q_n = 1/n.

q_i = 1/3

Ai	П1	П2	П3	?(aij)
A1	0	-1	1.333	0.333
A2	2.667	1.667	2.333	6.667
A3	0.333	2.667	2	5
A4	0.333	1	0.667	2
pj	0.333	0.333	0.333

Выбираем из (0.33; 6.67; 5; 2) максимальный элемент max=6.67

Вывод: выбираем стратегию N=2.

Критерий Вальда.

По критерию Вальда за оптимальную принимается чистая стратегия, которая в наихудших условиях гарантирует максимальный выигрыш, т.е. a = max(min a_ij)

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

Ai	П1	П2	П3	min(aij)
A1	0	-3	4	-3
A2	8	5	7	5
A3	1	8	6	1
A4	1	3	2	1

Выбираем из (-3; 5; 1; 1) максимальный элемент max=5

Вывод: выбираем стратегию N=2.

Критерий Севиджа.

Критерий минимального риска Севиджа рекомендует выбирать в качестве оптимальной стратегии ту, при которой величина максимального риска минимизируется в наихудших условиях, т.е. обеспечивается: a = min(max r_ij)

Критерий Сэвиджа ориентирует статистику на самые неблагоприятные состояния природы, т.е. этот критерий выражает пессимистическую оценку ситуации.

Находим матрицу рисков.

Риск - мера несоответствия между разными возможными результатами принятия определенных стратегий. Максимальный выигрыш в j-м столбце b_j = max(a_ij) характеризует благоприятность состояния природы.

1. Рассчитываем 1-й столбец матрицы рисков.

r₁₁ = 8 - 0 = 8; r₂₁ = 8 - 8 = 0; r₃₁ = 8 - 1 = 7; r₄₁ = 8 - 1 = 7;

2. Рассчитываем 2-й столбец матрицы рисков.

r₁₂ = 8 - (-3) = 11; r₂₂ = 8 - 5 = 3; r₃₂ = 8 - 8 = 0; r₄₂ = 8 - 3 = 5;

3. Рассчитываем 3-й столбец матрицы рисков.

r₁₃ = 7 - 4 = 3; r₂₃ = 7 - 7 = 0; r₃₃ = 7 - 6 = 1; r₄₃ = 7 - 2 = 5;

Ai	П1	П2	П3
A1	8	11	3
A2	0	3	0
A3	7	0	1
A4	7	5	5

Результаты вычислений оформим в виде таблицы.

Ai	П1	П2	П3	max(aij)
A1	8	11	3	11
A2	0	3	0	3
A3	7	0	1	7
A4	7	5	5	7

Выбираем из (11; 3; 7; 7) минимальный элемент min=3

Вывод: выбираем стратегию N=2.

Критерий Гурвица.

Критерий Гурвица является критерием пессимизма - оптимизма. За оптимальную принимается та стратегия, для которой выполняется соотношение: max(s_i) где s_i = y min(a_ij) + (1-y)max(a_ij)

При y = 1 получим критерий Вальде, при y = 0 получим - оптимистический критерий (максимакс).

Критерий Гурвица учитывает возможность как наихудшего, так и наилучшего для человека поведения природы. Как выбирается y? Чем хуже последствия ошибочных решений, тем больше желание застраховаться от ошибок, тем y ближе к 1.

Рассчитываем s_i.

s₁ = 0.4*(-3)+(1-0.4)*4 = 1.2

s₂ = 0.4*5+(1-0.4)*8 = 6.8

s₃ = 0.4*1+(1-0.4)*8 = 5.2

s₄ = 0.4*1+(1-0.4)*3 = 2.2

Ai	П1	П2	П3	min(aij)	max(aij)	y min(aij) + (1y)max(aij)
A1	0	-3	4	-3	4	1.2
A2	8	5	7	5	8	6.8
A3	1	8	6	1	8	5.2
A4	1	3	2	1	3	2.2

Выбираем из (1.2; 6.8; 5.2; 2.2) максимальный элемент max=6.8

Вывод: выбираем стратегию N=2.

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

2

Игроки	B1	B2	B3	a = min(Ai)
A1	-1	6	8	-1
A2	9	6	5	5
A3	7	8	3	3
b = max(Bi)	9	8	8

Итерация №1. Минимальный элемент для нее равен -1 и находится под номером j=1. Следовательно, игрок II выбирает стратегию №1

Максимальный элемент равен 9 и находится под номером j=2. Следовательно, игрок I выбирает стратегию №2

Итерация №2. Минимальный элемент для нее равен 8 и находится под номером j=1. Следовательно, игрок II выбирает стратегию №1

Максимальный элемент равен 18 и находится под номером j=2. Следовательно, игрок I выбирает стратегию №2

k	i	B1	B2	B3	j	A1	A2	A3	Vmin	Vmax	Vср
1	1	-1	6	8	1	-1	9	7	-1	9	4
2	2	8	12	13	1	-2	18	14	4	9	13/2
3	2	17	18	18	1	-3	27	21	17/3	9	22/3
4	2	26	24	23	3	5	32	24	23/4	8	55/8
5	2	35	30	28	3	13	37	27	28/5	37/5	13/2
6	2	44	36	33	3	21	42	30	11/2	7	25/4
7	2	53	42	38	3	29	47	33	38/7	47/7	85/14
8	2	62	48	43	3	37	52	36	43/8	13/2	95/16
9	2	71	54	48	3	45	57	39	16/3	19/3	35/6
10	2	80	60	53	3	53	62	42	53/10	31/5	23/4
11	2	89	66	58	3	61	67	45	58/11	67/11	125/22
12	2	98	72	63	3	69	72	48	21/4	6	45/8
13	2	107	78	68	3	77	77	51	68/13	77/13	145/26
14	1	106	84	76	3	85	82	54	38/7	85/14	23/4
15	1	105	90	84	3	93	87	57	28/5	31/5	59/10
16	1	104	96	92	3	101	92	60	23/4	101/16	193/32
17	1	103	102	100	3	109	97	63	100/17	109/17	209/34
18	1	102	108	108	1	108	106	70	17/3	6	35/6
19	1	101	114	116	1	107	115	77	101/19	115/19	108/19
20	2	110	120	121	1	106	124	84	11/2	31/5	117/20

здесь:

k - номер партии.

i - номер стратегии, выбираемой игроком A.

j - номер стратегии, выбираемой игроком В.

B_i - накопленный игроком А выигрыш за k партий, при условии, что в данной партии B выбирает стратегию B_i.

А_j - накопленный игроком В проигрыш за k партий, при условии, что в данной партии A выбирает стратегию А_j.

V_min - нижняя оценка игры = min (накопленный выигрыш)/k.

V^max - верхняя оценка игры = max (накопленный проигрыш)/k.

Доказано, что:

W=(V_min+V^max)/2, при k > ? и

p_i = N_i/k

q_j = N_j/k

N_i - сколько раз выбирается Аi стратегия.

N_j - сколько раз выбирается Bj стратегия.

N_A1 = 7

P(A₁) = 7/20 = ⁷/₂₀

N_A2 = 13

P(A₂) = 13/20 = ¹³/₂₀

N_A3 = 0

P(A₃) = 0/20 = 0

N_B1 = 6

P(B₄) = 6/20 = ³/₁₀

N_B2 = 0

P(B₄) = 0/20 = 0

N_B3 = 14

P(B₄) = 14/20 = ⁷/₁₀

Цена игры, W = ¹¹⁷/₂₀

Стратегия игрока I: p = (⁷/₂₀, ¹³/₂₀, 0)

Стратегия игрока II: q = (³/₁₀, 0, ⁷/₁₀)

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

3

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

С позиции проигрышей игрока В стратегия B₄ доминирует над стратегией B₂ (все элементы столбца 4 меньше элементов столбца 2), следовательно, исключаем 2-й столбец матрицы. Вероятность q₂ = 0.

9	3	0
-8	6	1
5	2	6

В матрице присутствуют отрицательные элементы. Для упрощения расчетов добавим к элементам матрицы (8). Такая замена не изменит решения игры, изменится только ее цена (по теореме фон Неймана).

17	11	8
0	14	9
13	10	14

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

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

17x₁+13x₃ ? 1

11x₁+14x₂+10x₃ ? 1

8x₁+9x₂+14x₃ ? 1

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

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

17y₁+11y₂+8y₃ ? 1

14y₂+9y₃ ? 1

13y₁+10y₂+14y₃ ? 1

Z(y) = y₁+y₂+y₃ > max

вероятность правдоподобие стратегия симплексный

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

Определим максимальное значение целевой функции Z(Y) = y₁+y₂+y₃ при следующих условиях-ограничений.

17y₁+11y₂+8y₃?1

14y₂+9y₃?1

13y₁+10y₂+14y₃?1

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

17y₁ + 11y₂ + 8y₃ + 1y₄ + 0y₅ + 0y₆ = 1

0y₁ + 14y₂ + 9y₃ + 0y₄ + 1y₅ + 0y₆ = 1

13y₁ + 10y₂ + 14y₃ + 0y₄ + 0y₅ + 1y₆ = 1

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

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

Базис	B	y1	y2	y3	y4	y5	y6
y4	1	17	11	8	1	0	0
y5	1	0	14	9	0	1	0
y6	1	13	10	14	0	0	1
Z(Y0)	0	-1	-1	-1	0	0	0

Переходим к основному алгоритму симплекс-метода.

Итерация №0.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

В качестве ведущего выберем столбец, соответствующий переменной y₃, так как это наибольший коэффициент по модулю.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i3

и из них выберем наименьшее: min (1: 8, 1: 9, 1: 14) = ¹/₁₄

Следовательно, 3-ая строка является ведущей.

Разрешающий элемент равен (14) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	y1	y2	y3	y4	y5	y6	min
y4	1	17	11	8	1	0	0	1/8
y5	1	0	14	9	0	1	0	1/9
y6	1	13	10	14	0	0	1	1/14
Z(Y1)	0	-1	-1	-1	0	0	0

Формируем следующую часть симплексной таблицы. Вместо переменной y₆ в план 1 войдет переменная y₃.

Получаем новую симплекс-таблицу:

Базис	B	y1	y2	y3	y4	y5	y6
y4	3/7	67/7	37/7	0	1	0	-4/7
y5	5/14	-117/14	53/7	0	0	1	-9/14
y3	1/14	13/14	5/7	1	0	0	1/14
Z(Y1)	1/14	-1/14	-2/7	0	0	0	1/14

Итерация №1.

Текущий опорный план не оптимален, так как в индексной строке находятся отрицательные коэффициенты.

В качестве ведущего выберем столбец, соответствующий переменной y₂, так как это наибольший коэффициент по модулю.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i2

и из них выберем наименьшее:

min (³/₇: 5²/₇, ⁵/₁₄: 7⁴/₇, ¹/₁₄: ⁵/₇) = ⁵/₁₀₆

Следовательно, 2-ая строка является ведущей.

Разрешающий элемент равен (7⁴/₇) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	y1	y2	y3	y4	y5	y6	min
y4	3/7	67/7	37/7	0	1	0	-4/7	3/37
y5	5/14	-117/14	74/7	0	0	1	-9/14	5/106
y3	1/14	13/14	5/7	1	0	0	1/14	1/10
Z(Y2)	1/14	-1/14	-2/7	0	0	0	1/14

Формируем следующую часть симплексной таблицы. Вместо переменной y₅ в план 2 войдет переменная y₂.

Получаем новую симплекс-таблицу:

Базис	B	y1	y2	y3	y4	y5	y6
y4	19/106	1633/106	0	0	1	-37/53	-13/106
y2	5/106	-117/106	1	0	0	7/53	-9/106
y3	2/53	91/53	0	1	0	-5/53	7/53
Z(Y2)	9/106	-41/106	0	0	0	2/53	5/106

Итерация №2.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

В качестве ведущего выберем столбец, соответствующий переменной y₁, так как это наибольший коэффициент по модулю.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i1

и из них выберем наименьшее: min (¹⁹/₁₀₆: 15⁴³/₁₀₆, -, ²/₅₃: 1³⁸/₅₃) = ¹⁹/₁₆₃₃

Следовательно, 1-ая строка является ведущей.

Разрешающий элемент равен (15⁴³/₁₀₆) и находится на пересечении ведущего столбца и ведущей строки

Базис	B	y1	y2	y3	y4	y5	y6	min
y4	19/106	1543/106	0	0	1	-37/53	-13/106	19/1633
y2	5/106	-117/106	1	0	0	7/53	-9/106	-
y3	2/53	91/53	0	1	0	-5/53	7/53	2/91
Z(Y3)	9/106	-41/106	0	0	0	2/53	5/106



Формируем следующую часть симплексной таблицы. Вместо переменной y₄ в план 3 войдет переменная y₁.

Получаем новую симплекс-таблицу:

Базис	B	y1	y2	y3	y4	y5	y6
y1	19/1633	1	0	0	106/1633	-74/1633	-13/1633
y2	98/1633	0	1	0	117/1633	134/1633	-153/1633
y3	29/1633	0	0	1	-182/1633	-27/1633	238/1633
Z(Y3)	146/1633	0	0	0	41/1633	33/1633	72/1633

Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план

Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.

Окончательный вариант симплекс-таблицы:

Базис	B	y1	y2	y3	y4	y5	y6
y1	19/1633	1	0	0	106/1633	-74/1633	-13/1633
y2	98/1633	0	1	0	117/1633	134/1633	-153/1633
y3	29/1633	0	0	1	-182/1633	-27/1633	238/1633
Z(Y4)	146/1633	0	0	0	41/1633	33/1633	72/1633

Оптимальный план можно записать так:

y₁ = ¹⁹/₁₆₃₃, y₂ = ⁹⁸/₁₆₃₃, y₃ = ²⁹/₁₆₃₃

Z(Y) = 1*¹⁹/₁₆₃₃ + 1*⁹⁸/₁₆₃₃ + 1*²⁹/₁₆₃₃ = ¹⁴⁶/₁₆₃₃

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

x₁=⁴¹/₁₆₃₃, x₂=³³/₁₆₃₃, x₃=⁷²/₁₆₃₃

Это же решение можно получить, применив теоремы двойственности.

Из теоремы двойственности следует, что X = C*A^-1.

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

A = (A1, A2, A3) =	17 11 8 0 14 9 13 10 14

Определив обратную матрицу D = А^-1 через алгебраические дополнения, получим:

D = A-1 =	106/1633 -74/1633 -13/1633 117/1633 134/1633 -153/1633 -182/1633 -27/1633 238/1633

Как видно из последнего плана симплексной таблицы, обратная матрица A^-1 расположена в столбцах дополнительных переменных.

Тогда

X = C*A^-1 =

(1, 1, 1) x	106/1633 -74/1633 -13/1633 117/1633 134/1633 -153/1633 -182/1633 -27/1633 238/1633	= (41/1633;33/1633;72/1633)

Оптимальный план двойственной задачи равен:



x₁ = ⁴¹/₁₆₃₃, x₂ = ³³/₁₆₃₃, x₃ = ⁷²/₁₆₃₃

F(X) = 1*⁴¹/₁₆₃₃+1*³³/₁₆₃₃+1*⁷²/₁₆₃₃ = ¹⁴⁶/₁₆₃₃

Цена игры будет равна g = 1/F(x), а вероятности применения стратегий игроков:

q_i = g*y_i; p_i = g*x_i.

Цена игры: g = 1: ¹⁴⁶/₁₆₃₃ = ¹⁶³³/₁₄₆

p₁ = ¹⁶³³/₁₄₆*⁴¹/₁₆₃₃ = ⁴¹/₁₄₆

p₂ = ¹⁶³³/₁₄₆*³³/₁₆₃₃ = ³³/₁₄₆

p₃ = ¹⁶³³/₁₄₆*⁷²/₁₆₃₃ = ³⁶/₇₃

Оптимальная смешанная стратегия игрока I:

P = (⁴¹/₁₄₆; ³³/₁₄₆; ³⁶/₇₃)

q₁ = ¹⁶³³/₁₄₆*¹⁹/₁₆₃₃ = ¹⁹/₁₄₆

q₂ = ¹⁶³³/₁₄₆*⁹⁸/₁₆₃₃ = ⁴⁹/₇₃

q₃ = ¹⁶³³/₁₄₆*²⁹/₁₆₃₃ = ²⁹/₁₄₆

Оптимальная смешанная стратегия игрока II:

Q = (¹⁹/₁₄₆; ⁴⁹/₇₃; ²⁹/₁₄₆)

Поскольку ранее к элементам матрицы было прибавлено число (8), то вычтем это число из цены игры. 11²⁷/₁₄₆ - 8 = 3²⁷/₁₄₆

Цена игры: v=⁴⁶⁵/₁₄₆

4. Проверим правильность решения игры с помощью критерия оптимальности стратегии.

?a_ijq_j ? v

?a_ijp_i ? v

M(P₁;Q) = (9*¹⁹/₁₄₆) + (3*⁴⁹/₇₃) + (0*²⁹/₁₄₆) = 3.185 = v

M(P₂;Q) = (-8*¹⁹/₁₄₆) + (6*⁴⁹/₇₃) + (1*²⁹/₁₄₆) = 3.185 = v

M(P₃;Q) = (5*¹⁹/₁₄₆) + (2*⁴⁹/₇₃) + (6*²⁹/₁₄₆) = 3.185 = v

M(P;Q₁) = (9*⁴¹/₁₄₆) + (-8*³³/₁₄₆) + (5*³⁶/₇₃) = 3.185 = v

M(P;Q₂) = (3*⁴¹/₁₄₆) + (6*³³/₁₄₆) + (2*³⁶/₇₃) = 3.185 = v

M(P;Q₃) = (0*⁴¹/₁₄₆) + (1*³³/₁₄₆) + (6*³⁶/₇₃) = 3.185 = v

Все неравенства выполняются как равенства или строгие неравенства, следовательно, решение игры найдено верно.

Поскольку из исходной матрицы были удалены строки и столбцы, то найденные векторы вероятности можно записать в виде:

P(⁴¹/₁₄₆,³³/₁₄₆,³⁶/₇₃,0)

Q(¹⁹/₁₄₆,0,⁴⁹/₇₃,²⁹/₁₄₆)

4

A1	32
A2	56
A3	89
b = max(Bi)	89

1. В декартовой системе координат по оси абсцисс откладывается отрезок, длина которого равна 1. Левый конец отрезка (точка х = 0) соответствует стратегии B₁, правый - стратегии B₂ (x = 1). Промежуточные точки х соответствуют вероятностям некоторых смешанных стратегий S₁ = (p₁,p₂).

2. 2. На левой оси ординат откладываются выигрыши стратегии B₁. На линии, параллельной оси ординат, из точки 1 откладываются выигрыши стратегии B₂.

3. Решение игры (m x 2) проводим с позиции игрока B, придерживающегося максиминной стратегии. Доминирующихся и дублирующих стратегий ни у одного из игроков нет.

4. Максиминной оптимальной стратегии игрока B соответствует точка N, для которой можно записать следующую систему уравнений:

5. q₁ = 0

6. q₂ = 1

7. Цена игры, y =

8. Теперь можно найти минимаксную стратегию игрока A, записав соответствующую систему уравнений, исключив стратегию A₃, которая дает явно больший проигрыш игроку A, и, следовательно, p₃ = 0.

9. p₁ = 1.

10. p₂ = 0.



Ответ:

Цена игры: y =, векторы стратегии игроков: P(1, 0, 0), Q(0, 1)

4. Проверим правильность решения игры с помощью критерия оптимальности стратегии.

?a_ijq_j ? v

?a_ijp_i ? v

M(P₁;Q) = (32*0) + (*1) = 0 = v

M(P₂;Q) = (56*0) + (*1) = 0 = v

M(P₃;Q) = (89*0) + (*1) = 0 = v

M(P;Q₁) = (32*1) + (56*0) + (89*0) = 32 ? v

M(P;Q₂) = (*1) + (*0) + (*0) = 0 = v

Все неравенства выполняются как равенства или строгие неравенства, следовательно, решение игры найдено верно.

5

Игроки	B1	B2	B3	a = min(Ai)
A1	5	1	0	0
A2	2	5	9	2
A3	9	0	6	0
A4	1	3	2	1
b = max(Bi)	9	5	9

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

Верхняя цена игры b = min(b_j) = 5.

Что свидетельствует об отсутствии седловой точки, так как a ? b, тогда цена игры находится в пределах 2 ? y ? 5.

Размещено на Allbest.ru

...