Выбор стратегии в теории игр

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

Федеральное государственное образовательное бюджетное учреждение высшего профессионального образования

«ФинансоВЫЙ УНИВЕРСИТЕТ при Правительстве Российской Федерации» (Финуниверситет)

Калужский филиал Финуниверситета

Факультет «Управления и бизнес-технологий»

Кафедра «Бухгалтерский учет, анализ и аудит»

контрольная работа

ПО ДИСЦИПЛИНЕ: «Теория игр»

Выбор стратегии в теории игр

Выполнил студент: 3 курса,

заочной формы обучения

Свечников Ю.О.

Преподаватель:

Зайчикова И. В.

Калуга 2015



Задание 1

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

Решение: Проверяем, имеет ли платежная матрица седловую точку.

Если да, то выписываем решение игры в чистых стратегиях.

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

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

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

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

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

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

Запишем систему уравнений.

Для игрока I

8p₁+7p₂+8p₃+8p₄ = y

9p₁+6p₂+5p₃+3p₄ = y

9p₁+5p₂+3p₃+7p₄ = y

4p₁+9p₂+6p₃+7p₄ = y

p₁+p₂+p₃+p₄ = 1

Для игрока II

8q₁+9q₂+9q₃+4q₄ = y

7q₁+6q₂+5q₃+9q₄ = y

8q₁+5q₂+3q₃+6q₄ = y

8q₁+3q₂+7q₃+7q₄ = y

q₁+q₂+q₃+q₄ = 1

Решая эти системы методом Гаусса (решение см. ниже), находим:

y = 7³/₁₀

p₁ = ⁴⁴⁵³/₁₀₂₂₀ (вероятность применения 1-ой стратегии).

P₂ = ⁵¹¹/₇₃₀ (вероятность применения 2-ой стратегии).

P₃ = ^-2117/₁₀₂₂₀ (вероятность применения 3-ой стратегии).

P₄ = ¹/₁₄ (вероятность применения 4-ой стратегии).

Вероятность получилась отрицательная. Следовательно, данный метод не применим при решении игры для исходных данных. Необходимо решать симплекс-методом.

Q₁ = ⁵¹¹/₇₃₀ (вероятность применения 1-ой стратегии).

Q₂ = ¹/₁₀ (вероятность применения 2-ой стратегии).

Q₃ = 0 (вероятность применения 3-ой стратегии).

Q₄ = ¹/₅ (вероятность применения 4-ой стратегии).

Оптимальная смешанная стратегия игрока II: Q = (⁵¹¹/₇₃₀; ¹/₁₀; 0; ¹/₅)

Задание 2

Условие: Провести возможные упрощения платежной матрицы и решить игру аналитическим методом.

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

Если да, то выписываем решение игры в чистых стратегиях.

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

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

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

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

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

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-ю - доминируемой.

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

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

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



7	16	8	9	2
9	17	6	10	9

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

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

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

8	2
6	9

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

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

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

Запишем систему уравнений.

Для игрока I

8p₁+6p₂ = y

2p₁+9p₂ = y

p₁+p₂ = 1



Для игрока II

8q₁+2q₂ = y

6q₁+9q₂ = y

q₁+q₂ = 1

Решая эти системы методом Гаусса (решение см. ниже), находим:

y = 6²/₃

p₁ = ¹/₃ (вероятность применения 1-ой стратегии).

P₂ = ²/₃ (вероятность применения 2-ой стратегии).

Оптимальная смешанная стратегия игрока I: P = (¹/₃; ²/₃)

q₁ = ⁷/₉ (вероятность применения 1-ой стратегии).

Q₂ = ²/₉ (вероятность применения 2-ой стратегии).

Оптимальная смешанная стратегия игрока II: Q = (⁷/₉; ²/₉)

Цена игры:

y = 6²/₃

Задание 3

Условие: Решить игру графо-аналитическим методом игру, заданную платежной матрицей:

Решение: Проверяем, имеет ли платежная матрица седловую точку.

Если да, то выписываем решение игры в чистых стратегиях.

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

Игроки	B1	B2	a = min(Ai)
A1	7	-1	-1
A2	5	4	4
A3	1	5	1
A4	3	-2	-2
A5	2	1	1
b = max(Bi)	7	5

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

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

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

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

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

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

9	1
7	6
3	7
5	0
4	3

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

Решим задачу геометрическим методом, который включает в себя следующие этапы:

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

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

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

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

y = 7 + (6 - 7)q₂

y = 3 + (7 - 3)q₂

Откуда

q₁ = ¹/₅

q₂ = ⁴/₅

Цена игры, y = ³¹/₅

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

7p₂+3p₃ = y

6p₂+7p₃ = y

p₂+p₃ = 1

или

7p₂+3p₃ = ³¹/₅

6p₂+7p₃ = ³¹/₅

p₂+p₃ = 1

Решая эту систему, находим:

p₂ = ⁴/₅.

P₃ = ¹/₅.

Поскольку ранее к элементам матрицы было прибавлено число (2), то вычтем это число из цены игры.

Цена игры: y = ³¹/₅ - 2 = ²¹/₅

Ответ:

Цена игры: y = ²¹/₅, векторы стратегии игроков:

P(0, ⁴/₅, ¹/₅, 0, 0), Q(¹/₅, ⁴/₅)

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

?a_ijq_j ? v

?a_ijp_i ? v

M(P₁;Q) = (7*¹/₅) + (-1*⁴/₅) = 0.6 ? v

M(P₂;Q) = (5*¹/₅) + (4*⁴/₅) = 4.2 = v

M(P₃;Q) = (1*¹/₅) + (5*⁴/₅) = 4.2 = v

M(P₄;Q) = (3*¹/₅) + (-2*⁴/₅) = -1 ? v

M(P₅;Q) = (2*¹/₅) + (1*⁴/₅) = 1.2 ? v

M(P;Q₁) = (7*0) + (5*⁴/₅) + (1*¹/₅) + (3*0) + (2*0) = 4.2 = v

M(P;Q₂) = (-1*0) + (4*⁴/₅) + (5*¹/₅) + (-2*0) + (1*0) = 4.2 = v

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

Задание 4

Условие: Предприятие выпускает скоропортящуюся продукцию А и В. Данные о ее себестоимости, отпускных ценах и объемах реализации приведены в таблице.

1) Составить математическую модель для определения ежедневного объема производства продукции, обеспечивающего предприятию наибольшую прибыль.

2) Определить ежедневный объем производства продукции, обеспечивающий предприятию наибольшую прибыль

Вид продукции	Себестоимость единицы продукции	Отпускная цена, ден. ед.	Объем реализации, ед.
		В день изготовления	Позже	В теплую погоду	В холодную погоду
А В	8 4	15 8	9 5	200 410	520 150

математический игра стратегия выигрыш гаусс

Решение: Игрок А - предприятие, цель которого максимизировать прибыль.

Стратегия А₁ - ориентация на теплую погоду.

Стратегия А₂ - ориентация на холодную погоду.

1. Составим математическую модель:

а_1.1 = 200Ч(15-8)+410Ч(8-4) = 3040

а_1.2 = 200Ч(15-8)+150Ч(8-4)+260Ч(5-4) = 2260

а_2.1 = 200Ч(15-8)+320Ч(9-8)+150Ч(8-4) = 2320

а_2.2 = 520Ч(15-8)+150Ч(8-4) = 4240

Получится математическая модель:

б = 2320 ? в = 3040 , следовательно решение игры в чистых стратегиях отсутствует.

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

Пусть S_А ( р₁;р₂)

3040 р₁ + 2320 р₂ = 2260 р₁ + 4240 р₂

р₁ =

+ р₂ = 1

р₂ = 0,289

р₁ = 1-0,289 = 0,711

V = 3040Ч0,711 + 2320Ч0,289 = 2831,92

Предприятие получит гарантированную прибыль 2831,92, если с вероятностью 0,711 (71,1%) будет ориентироваться на теплую погоду, и с вероятностью 0,289 (28,9%) на холодную.

3. Определим ежедневный объём продукции:

V_А = 200Чр₁ + 520Чр₂ = 292

V_В = 410Чр₁ + 150Чр₂ = 335

Вывод: таким образом предприятию необходимо ежедневно выпускать 292 ед. продукции А, и 335 продукции В. Тем самым предприятие обеспечит себе гарантированную прибыль не менее чем 2831,92.

Задание 5

Условие: Решить игру, заданную платежной матрицей

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

Если да, то выписываем решение игры в чистых стратегиях.

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

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

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

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

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

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-ю - доминируемой.

В платежной матрице отсутствуют доминирующие строки.

В платежной матрице отсутствуют доминирующие столбцы.

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

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

В матрице присутствуют отрицательные элементы. Для упрощения расчетов добавим к элементам матрицы (3).

Такая замена не изменит решения игры, изменится только ее цена (по теореме фон Неймана).

3	4	1
2	3	6
5	0	3

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

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

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

3x₁+2x₂+5x₃ ? 1

4x₁+3x₂ ? 1

x₁+6x₂+3x₃ ? 1

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

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

3y₁+4y₂+y₃ ? 1

2y₁+3y₂+6y₃ ? 1

5y₁+3y₃ ? 1

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

Решаем эти системы симплексным методом.

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

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

3x₁ + 4x₂ + x₃?1

2x₁ + 3x₂ + 6x₃?1

5x₁ + 3x₃?1

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

В 1-м неравенстве смысла (?) вводим базисную переменную x₄. В 2-м неравенстве смысла (?) вводим базисную переменную x₅. В 3-м неравенстве смысла (?) вводим базисную переменную x₆.

3x₁ + 4x₂ + 1x₃ + 1x₄ + 0x₅ + 0x₆ = 1

2x₁ + 3x₂ + 6x₃ + 0x₄ + 1x₅ + 0x₆ = 1

5x₁ + 0x₂ + 3x₃ + 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	3	4	1	1	0	0
x5	1	2	3	6	0	1	0
x6	1	5	0	3	0	0	1
F(X0)	0	-1	-1	-1	0	0	0

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

Итерация №0.

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

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

3. Определение новой свободной переменной. Вычислим значения D_i по строкам как частное от деления: b_i / a_i3 и из них выберем наименьшее:

min (1 : 1 , 1 : 6 , 1 : 3 ) = ¹/₆

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

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

Базис	B	x1	x2	x3	x4	x5	x6	min
x4	1	3	4	1	1	0	0	1
x5	1	2	3	6	0	1	0	1/6
x6	1	5	0	3	0	0	1	1/3
F(X1)	0	-1	-1	-1	0	0	0	0

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

Строка, соответствующая переменной x₃ в плане 1, получена в результате деления всех элементов строки x₅ плана 0 на разрешающий элемент РЭ=6. На месте разрешающего элемента в плане 1 получаем 1.

В остальных клетках столбца x₃ плана 1 записываем нули.

Таким образом, в новом плане 1 заполнены строка x₃ и столбец x₃.

Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника. Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.

НЭ = СЭ - (А*В)/РЭ

СТЭ - элемент старого плана, РЭ - разрешающий элемент (6), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ. Представим расчет каждого элемента в виде таблицы:

B	x1	x2	x3	x4	x5	x6
1-(1 * 1):6	3-(2 * 1):6	4-(3 * 1):6	1-(6 * 1):6	1-(0 * 1):6	0-(1 * 1):6	0-(0 * 1):6
1 : 6	2 : 6	3 : 6	6 : 6	0 : 6	1 : 6	0 : 6
1-(1 * 3):6	5-(2 * 3):6	0-(3 * 3):6	3-(6 * 3):6	0-(0 * 3):6	0-(1 * 3):6	1-(0 * 3):6
0-(1 * -1):6	-1-(2 * -1):6	-1-(3 * -1):6	-1-(6 * -1):6	0-(0 * -1):6	0-(1 * -1):6	0-(0 * -1):6



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

Базис	B	x1	x2	x3	x4	x5	x6
x4	5/6	8/3	7/2	0	1	-1/6	0
x3	1/6	1/3	1/2	1	0	1/6	0
x6	1/2	4	-3/2	0	0	-1/2	1
F(X1)	1/6	-2/3	-1/2	0	0	1/6	0

Итерация №1.

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

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

3. Определение новой свободной переменной. Вычислим значения D_i по строкам как частное от деления: b_i / a_i1 и из них выберем наименьшее:

min (⁵/₆ : 2²/₃ , ¹/₆ : ¹/₃ , ¹/₂ : 4 ) = ¹/₈

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

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

Базис	B	x1	x2	x3	x4	x5	x6	min
x4	5/6	22/3	31/2	0	1	-1/6	0	5/16
x3	1/6	1/3	1/2	1	0	1/6	0	1/2
x6	1/2	4	-11/2	0	0	-1/2	1	1/8
F(X2)	1/6	-2/3	-1/2	0	0	1/6	0	0

4. Пересчет симплекс-таблицы. Формируем следующую часть симплексной таблицы. Вместо переменной x₆ в план 2 войдет переменная x₁.

Строка, соответствующая переменной x₁ в плане 2, получена в результате деления всех элементов строки x₆ плана 1 на разрешающий элемент РЭ=4

На месте разрешающего элемента в плане 2 получаем 1.

В остальных клетках столбца x₁ плана 2 записываем нули.

Таким образом, в новом плане 2 заполнены строка x₁ и столбец x₁.

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

Представим расчет каждого элемента в виде таблицы:

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

Базис	B	x1	x2	x3	x4	x5	x6
x4	1/2	0	9/2	0	1	1/6	-2/3
x3	1/8	0	5/8	1	0	5/24	-1/12
x1	1/8	1	-3/8	0	0	-1/8	1/4
F(X2)	1/4	0	-3/4	0	0	1/12	1/6

Итерация №2.

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

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

3. Определение новой свободной переменной. Вычислим значения D_i по строкам как частное от деления: b_i / a_i2 и из них выберем наименьшее:

min (¹/₂ : 4¹/₂ , ¹/₈ : ⁵/₈ , - ) = ¹/₉

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

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

Базис	B	x1	x2	x3	x4	x5	x6	min
x4	1/2	0	41/2	0	1	1/6	-2/3	1/9
x3	1/8	0	5/8	1	0	5/24	-1/12	1/5
x1	1/8	1	-3/8	0	0	-1/8	1/4	-
F(X3)	1/4	0	-3/4	0	0	1/12	1/6	0

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

Строка, соответствующая переменной x₂ в плане 3, получена в результате деления всех элементов строки x₄ плана 2 на разрешающий элемент РЭ=4¹/_2. На месте разрешающего элемента в плане 3 получаем 1.

В остальных клетках столбца x₂ плана 3 записываем нули. Таким образом, в новом плане 3 заполнены строка x₂ и столбец x₂. Все остальные элементы нового плана 3, включая элементы индексной строки, определяются по правилу прямоугольника. Представим расчет каждого элемента в виде таблицы:



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

Базис	B	x1	x2	x3	x4	x5	x6
x2	1/9	0	1	0	2/9	1/27	-4/27
x3	1/18	0	0	1	-5/36	5/27	1/108
x1	1/6	1	0	0	1/12	-1/9	7/36
F(X3)	1/3	0	0	0	1/6	1/9	1/18

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

Базис	B	x1	x2	x3	x4	x5	x6
x2	1/9	0	1	0	2/9	1/27	-4/27
x3	1/18	0	0	1	-5/36	5/27	1/108
x1	1/6	1	0	0	1/12	-1/9	7/36
F(X4)	1/3	0	0	0	1/6	1/9	1/18

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

x₂ = ¹/₉

x₃ = ¹/₁₈

x₁ = ¹/₆

F(X) = 1*¹/₉ + 1*¹/₁₈ + 1*¹/₆ = ¹/₃

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

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

Составим матрицу A из компонентов векторов, входящих в оптимальный базис. Определив обратную матрицу D = А^-1 через алгебраические дополнения, получим:



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

Тогда

Y = C*A^-1 =

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

y₁ = ¹/₆

y₂ = ¹/₉

y₃ = ¹/₁₈

Z(Y) = 1*¹/₆+1*¹/₉+1*¹/₁₈ = ¹/₃

Критерий оптимальности полученного решения. Если существуют такие допустимые решения X и Y прямой и двойственной задач, для которых выполняется равенство целевых функций F(x) = Z(y), то эти решения X и Y являются оптимальными решениями прямой и двойственной задач соответственно.

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

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



Цена игры:

g = 1 : ¹/₃ = 3

p₁ = 3 * ¹/₆ = ¹/₂

p₂ = 3 * ¹/₉ = ¹/₃

p₃ = 3 * ¹/₁₈ = ¹/₆

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

P = (¹/₂; ¹/₃; ¹/₆)

q₁ = 3 * ¹/₆ = ¹/₂

q₂ = 3 * ¹/₉ = ¹/₃

q₃ = 3 * ¹/₁₈ = ¹/₆

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

Q = (¹/₂; ¹/₃; ¹/₆)

Поскольку ранее к элементам матрицы было прибавлено число (3), то вычтем это число из цены игры.

3 - 3 = 0

Цена игры: v=0

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

?a_ijq_j ? v

?a_ijp_i ? v

M(P₁;Q) = (0*¹/₂) + (1*¹/₃) + (-2*¹/₆) = 0 = v

M(P₂;Q) = (-1*¹/₂) + (0*¹/₃) + (3*¹/₆) = -0 = v

M(P₃;Q) = (2*¹/₂) + (-3*¹/₃) + (0*¹/₆) = 0 = v

M(P;Q₁) = (0*¹/₂) + (-1*¹/₃) + (2*¹/₆) = -0 = v

M(P;Q₂) = (1*¹/₂) + (0*¹/₃) + (-3*¹/₆) = 0 = v

M(P;Q₃) = (-2*¹/₂) + (3*¹/₃) + (0*¹/₆) = -0 = v

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

Задание 6

Условие: Решить игру с природой, заданную платежной матрицей

ь по критерию Гурвица, б=0,3;

ь по критерию Лапласа;

ь по критерию Сэвиджа;

ь по критерию Вальда

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

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

q_i = 1/4

Ai	П1	П2	П3	П4	?(aij)
A1	1.5	1.25	0.25	-0.75	2.25
A2	1	-0.5	2.5	0.25	3.25
A3	-0.75	2.25	-0.5	1.75	2.75
A4	0.25	1.5	0.5	2.5	4.75
pj	0.25	0.25	0.25	0.25

Выбираем из (2.25; 3.25; 2.75; 4.75) максимальный элемент max=4.75

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

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

a = max(min a_ij)

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

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

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

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

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

a = min(max r_ij)

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

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

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

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

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

r₁₁ = 6 - 6 = 0; r₂₁ = 6 - 4 = 2; r₃₁ = 6 - (-3) = 9; r₄₁ = 6 - 1 = 5;

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

r₁₂ = 9 - 5 = 4; r₂₂ = 9 - (-2) = 11; r₃₂ = 9 - 9 = 0; r₄₂ = 9 - 6 = 3;

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

r₁₃ = 10 - 1 = 9; r₂₃ = 10 - 10 = 0; r₃₃ = 10 - (-2) = 12; r₄₃ = 10 - 2 = 8;

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

r₁₄ = 10 - (-3) = 13; r₂₄ = 10 - 1 = 9; r₃₄ = 10 - 7 = 3; r₄₄ = 10 - 10 = 0;

Ai	П1	П2	П3	П4
A1	0	4	9	13
A2	2	11	0	9
A3	9	0	12	3
A4	5	3	8	0

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

Ai	П1	П2	П3	П4	max(aij)
A1	0	4	9	13	13
A2	2	11	0	9	11
A3	9	0	12	3	12
A4	5	3	8	0	8

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

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

Критерий Гурвица. Критерий Гурвица является критерием пессимизма - оптимизма.

За оптимальную принимается та стратегия, для которой выполняется соотношение:

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.3*(-3)+(1-0.3)*6 = 3.3

s₂ = 0.3*(-2)+(1-0.3)*10 = 6.4

s₃ = 0.3*(-3)+(1-0.3)*9 = 5.4

s₄ = 0.3*1+(1-0.3)*10 = 7.3

Ai	П1	П2	П3	П4	min(aij)	max(aij)	y min(aij) + (1-y)max(aij)
A1	6	5	1	-3	-3	6	3.3
A2	4	-2	10	1	-2	10	6.4
A3	-3	9	-2	7	-3	9	5.4
A4	1	6	2	10	1	10	7.3

Выбираем из (3.3; 6.4; 5.4; 7.3) максимальный элемент max=7.3

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

<...