Вариант 6 Теория игр

Контрольная работа по предмету Теория игр. ...

1.
а) Решить игру с природой по критерию Гурвица, α=0,4;
б) Решить игру с природой по критерию Лапласа;
Если вероятности состояний природы правдоподобны, для их оценки используют принцип недостаточного основания Лапласа, согласно которого все состояния природы полагаются равновероятными, т.е.:
q1 = q2 = ... = qn = 1/n.
qi = 1/3
в)Решить игру с природой по критерию Сэвиджа;
г) Решить игру с природой по критерию Вальда.
2) Решить игру методом Брауна, выполнить 20 итераций
3) Решить игру симплекс-методом.
4) Решить игру графически
5) Найти верхнюю и нижнюю цену игры, проверить игру на наличие седловой точки.

Если да, то выписываем решение игры в чистых стратегиях. Считаем, что игрок I выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а игрок II выбирает свою стратегию так, чтобы минимизировать выигрыш игрока I. ИгрокиB1B2B3B4a = min(Ai)A191300A2-8361-8A357262A432100b = max(Bi)9766 Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(ai) = 2, которая указывает на максимальную чистую стратегию A3. Верхняя цена игры b = min(bj) = 6. Что свидетельствует об отсутствии седловой точки, так как a ≠ b, тогда цена игры находится в пределах 2 ≤ y ≤ 6. Находим решение игры в смешанных стратегиях. Объясняется это тем, что игроки не могут объявить противнику свои чистые стратегии: им следует скрывать свои действия. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии). Так как игроки выбирают свои чистые стратегии случайным образом, то выигрыш игрока I будет случайной величиной. В этом случае игрок I должен выбрать свои смешанные стратегии так, чтобы получить максимальный средний выигрыш. Аналогично, игрок II должен выбрать свои смешанные стратегии так, чтобы минимизировать математическое ожидание игрока I. В матрице присутствуют отрицательные элементы. Для упрощения расчетов добавим к элементам матрицы (8). Такая замена не изменит решения игры, изменится только ее цена (по теореме фон Неймана). 17911801114913151014111098 3. Находим решение игры в смешанных стратегиях. Математические модели пары двойственных задач линейного программирования можно записать так: найти минимум функции F(x) при ограничениях: 17x1+13x3+11x4 ≥ 1 9x1+11x2+15x3+10x4 ≥ 1 11x1+14x2+10x3+9x4 ≥ 1 8x1+9x2+14x3+8x4 ≥ 1 F(x) = x1+x2+x3+x4 → min найти максимум функции Ф(y) при ограничениях: 17y1+9y2+11y3+8y4 ≤ 1 11y2+14y3+9y4 ≤ 1 13y1+15y2+10y3+14y4 ≤ 1 11y1+10y2+9y3+8y4 ≤ 1 Ф(y) = y1+y2+y3+y4 → max Решаем эти системы симплексным методом. Решим прямую задачу линейного программирования двойственным симплексным методом, с использованием симплексной таблицы. Приведем систему ограничений к системе неравенств смысла ≤, умножив соответствующие строки на (-1). Определим минимальное значение целевой функции F(X) = x1 + x2 + x3 + x4 при следующих условиях-ограничений. - 17x1 - 13x3 - 11x4≤-1 - 9x1 - 11x2 - 15x3 - 10x4≤-1 - 11x1 - 14x2 - 10x3 - 9x4≤-1 - 8x1 - 9x2 - 14x3 - 8x4≤-1 Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме). В 1-м неравенстве смысла (≤) вводим базисную переменную x5. В 2-м неравенстве смысла (≤) вводим базисную переменную x6. В 3-м неравенстве смысла (≤) вводим базисную переменную x7. В 4-м неравенстве смысла (≤) вводим базисную переменную x8. -17x1 + 0x2-13x3-11x4 + 1x5 + 0x6 + 0x7 + 0x8 = -1 -9x1-11x2-15x3-10x4 + 0x5 + 1x6 + 0x7 + 0x8 = -1 -11x1-14x2-10x3-9x4 + 0x5 + 0x6 + 1x7 + 0x8 = -1 -8x1-9x2-14x3-8x4 + 0x5 + 0x6 + 0x7 + 1x8 = -1 Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид: -170-13-111000-9-11-15-100100-11-14-10-90010-8-9-14-80001Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом. Экономический смысл дополнительных переменных: дополнительные переменные задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана. Решим систему уравнений относительно базисных переменных: x5, x6, x7, x8 Полагая, что свободные переменные равны 0, получим первый опорный план: X1 = (0,0,0,0,-1,-1,-1,-1) Базисное решение называется допустимым, если оно неотрицательно. БазисBx1x2x3x4x5x6x7x8x5-1-170-13-111000x6-1-9-11-15-100100x7-1-11-14-10-90010x8-1-8-9-14-80001F(X0)0-1-1-1-100001. Проверка критерия оптимальности. План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец. 2. Определение новой свободной переменной. Среди отрицательных значений базисных переменных выбираем наибольший по модулю. Ведущей будет 1-ая строка, а переменную x5 следует вывести из базиса. 3. Определение новой базисной переменной. Минимальное значение θ соответствует 1-му столбцу, т.е. переменную x1 необходимо ввести в базис. На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-17). БазисBx1x2x3x4x5x6x7x8x5-1-170-13-111000x6-1-9-11-15-100100x7-1-11-14-10-90010x8-1-8-9-14-80001F(X0)0-1-1-1-10000θ -1 : (-17) = 1/17 - -1 : (-13) = 1/13-1 : (-11) = 1/11 - - - - 4. Пересчет симплекс-таблицы. Выполняем преобразования симплексной таблицы методом Жордано-Гаусса. БазисBx1x2x3x4x5x6x7x8x11/171013/1711/17-1/17000x6-8/170-11-138/17-71/17-9/17100x7-6/170-14-27/17-32/17-11/17010x8-9/170-9-134/17-48/17-8/17001F(X0)1/170-1-4/17-6/17-1/17000Представим расчет каждого элемента в виде таблицы: Bx1x2x3x4x5x6x7x8-1 : -17-17 : -170 : -17-13 : -17-11 : -171 : -170 : -170 : -170 : -17-1-(-1 • -9):-17-9-(-17 • -9):-17-11-(0 • -9):-17-15-(-13 • -9):-17-10-(-11 • -9):-170-(1 • -9):-171-(0 • -9):-170-(0 • -9):-170-(0 • -9):-17-1-(-1 • -11):-17-11-(-17 • -11):-17-14-(0 • -11):-17-10-(-13 • -11):-17-9-(-11 • -11):-170-(1 • -11):-170-(0 • -11):-171-(0 • -11):-170-(0 • -11):-17-1-(-1 • -8):-17-8-(-17 • -8):-17-9-(0 • -8):-17-14-(-13 • -8):-17-8-(-11 • -8):-170-(1 • -8):-170-(0 • -8):-170-(0 • -8):-171-(0 • -8):-170-(-1 • -1):-17-1-(-17 • -1):-17-1-(0 • -1):-17-1-(-13 • -1):-17-1-(-11 • -1):-170-(1 • -1):-170-(0 • -1):-170-(0 • -1):-170-(0 • -1):-171. Проверка критерия оптимальности. План 1 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец. 2. Определение новой свободной переменной. Среди отрицательных значений базисных переменных выбираем наибольший по модулю. Ведущей будет 4-ая строка, а переменную x8 следует вывести из базиса. 3. Определение новой базисной переменной. Минимальное значение θ соответствует 3-му столбцу, т.е. переменную x3 необходимо ввести в базис. На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-715/17). БазисBx1x2x3x4x5x6x7x8x11/171013/1711/17-1/17000x6-8/170-11-82/17-43/17-9/17100x7-6/170-14-110/17-115/17-11/17010x8-9/170-9-715/17-214/17-8/17001F(X0)1/170-1-4/17-6/17-1/17000θ - -1 : (-9) = 1/9-4/17 : (-715/17) = 2/67-6/17 : (-214/17) = 1/8-1/17 : (-8/17) = 1/8 - - - 4. Пересчет симплекс-таблицы. Выполняем преобразования симплексной таблицы методом Жордано-Гаусса. БазисBx1x2x3x4x5x6x7x8x11/1341-117/134025/67-7/670013/134x65/670-116/670-85/67-3/6710-69/67x7-33/1340-1633/1340-88/67-37/6701-27/134x39/1340153/134124/674/6700-17/134F(X1)5/670-49/670-18/67-3/6700-2/67Представим расчет каждого элемента в виде таблицы: Bx1x2x3x4x5x6x7x81/17-(-9/17 • 13/17):-715/171-(0 • 13/17):-715/170-(-9 • 13/17):-715/1713/17-(-715/17 • 13/17):-715/1711/17-(-214/17 • 13/17):-715/17-1/17-(-8/17 • 13/17):-715/170-(0 • 13/17):-715/170-(0 • 13/17):-715/170-(1 • 13/17):-715/17-8/17-(-9/17 • -82/17):-715/170-(0 • -82/17):-715/17-11-(-9 • -82/17):-715/17-82/17-(-715/17 • -82/17):-715/17-43/17-(-214/17 • -82/17):-715/17-9/17-(-8/17 • -82/17):-715/171-(0 • -82/17):-715/170-(0 • -82/17):-715/170-(1 • -82/17):-715/17-6/17-(-9/17 • -110/17):-715/170-(0 • -110/17):-715/17-14-(-9 • -110/17):-715/17-110/17-(-715/17 • -110/17):-715/17-115/17-(-214/17 • -110/17):-715/17-11/17-(-8/17 • -110/17):-715/170-(0 • -110/17):-715/171-(0 • -110/17):-715/170-(1 • -110/17):-715/17-9/17 : -715/170 : -715/17-9 : -715/17-715/17 : -715/17-214/17 : -715/17-8/17 : -715/170 : -715/170 : -715/171 : -715/171/17-(-9/17 • -4/17):-715/170-(0 • -4/17):-715/17-1-(-9 • -4/17):-715/17-4/17-(-715/17 • -4/17):-715/17-6/17-(-214/17 • -4/17):-715/17-1/17-(-8/17 • -4/17):-715/170-(0 • -4/17):-715/170-(0 • -4/17):-715/170-(1 • -4/17):-715/171. Проверка критерия оптимальности. План 2 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец. 2. Определение новой свободной переменной. Среди отрицательных значений базисных переменных выбираем наибольший по модулю. Ведущей будет 3-ая строка, а переменную x7 следует вывести из базиса. 3. Определение новой базисной переменной. Минимальное значение θ соответствует 2-му столбцу, т.е. переменную x2 необходимо ввести в базис. На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-1225/134). БазисBx1x2x3x4x5x6x7x8x11/1341-117/134025/67-7/670013/134x65/670-149/670-118/67-3/6710-12/67x7-33/1340-1225/1340-121/67-37/6701-27/134x39/1340119/134124/674/6700-17/134F(X0)5/670-49/670-18/67-3/6700-2/67θ - -49/67 : (-1225/134) = 98/1633 - -18/67 : (-121/67) = 9/44-3/67 : (-37/67) = 3/37 - - -2/67 : (-27/134) = 4/274. Пересчет симплекс-таблицы. Выполняем преобразования симплексной таблицы методом Жордано-Гаусса. БазисBx1x2x3x4x5x6x7x8x141/1633100763/1633-106/16330-117/1633182/1633x6179/1633000-1767/163355/16331-232/1633-1635/1633x233/1633010176/163374/16330-134/163327/1633x372/1633001384/163313/16330153/1633-238/1633F(X2)146/1633000-310/1633-19/16330-98/1633-29/1633Представим расчет каждого элемента в виде таблицы: Bx1x2x3x4x5x6x7x81/134-(-33/134 • -117/134):-1225/1341-(0 • -117/134):-1225/134-117/134-(-1225/134 • -117/134):-1225/1340-(0 • -117/134):-1225/13425/67-(-121/67 • -117/134):-1225/134-7/67-(-37/67 • -117/134):-1225/1340-(0 • -117/134):-1225/1340-(1 • -117/134):-1225/13413/134-(-27/134 • -117/134):-1225/1345/67-(-33/134 • -149/67):-1225/1340-(0 • -149/67):-1225/134-149/67-(-1225/134 • -149/67):-1225/1340-(0 • -149/67):-1225/134-118/67-(-121/67 • -149/67):-1225/134-3/67-(-37/67 • -149/67):-1225/1341-(0 • -149/67):-1225/1340-(1 • -149/67):-1225/134-12/67-(-27/134 • -149/67):-1225/134-33/134 : -1225/1340 : -1225/134-1225/134 : -1225/1340 : -1225/134-121/67 : -1225/134-37/67 : -1225/1340 : -1225/1341 : -1225/134-27/134 : -1225/1349/134-(-33/134 • 119/134):-1225/1340-(0 • 119/134):-1225/134119/134-(-1225/134 • 119/134):-1225/1341-(0 • 119/134):-1225/13424/67-(-121/67 • 119/134):-1225/1344/67-(-37/67 • 119/134):-1225/1340-(0 • 119/134):-1225/1340-(1 • 119/134):-1225/134-17/134-(-27/134 • 119/134):-1225/1345/67-(-33/134 • -49/67):-1225/1340-(0 • -49/67):-1225/134-49/67-(-1225/134 • -49/67):-1225/1340-(0 • -49/67):-1225/134-18/67-(-121/67 • -49/67):-1225/134-3/67-(-37/67 • -49/67):-1225/1340-(0 • -49/67):-1225/1340-(1 • -49/67):-1225/134-2/67-(-27/134 • -49/67):-1225/134В базисном столбце все элементы положительные. Переходим к основному алгоритму симплекс-метода. 1. Проверка критерия оптимальности. Среди значений индексной строки нет положительных. Поэтому эта таблица определяет оптимальный план задачи.