Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Тема 1. ТЕОРИЯ ИГР И ПРИНЯТИЕ РЕШЕНИЙ
В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ
Задание 1. Решение игры с заданной матрицей платежей
Порядок выполнения:
|
Вариант 11 |
|
В1 |
В2 |
В3 |
В4 |
|
|
А1 |
-8 |
6 |
7 |
|
|
А2 |
3 |
-1 |
4 |
4 |
|
А3 |
5 |
4 |
3 |
4 |
Ход работы:
1. Проверяем, имеет ли платежная матрица седловую точку. Если да, то выписываем решение игры в чистых стратегиях.
Считаем, что игрок I выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а игрок II выбирает свою стратегию так, чтобы минимизировать выигрыш игрока I.
|
Игроки |
B1 |
B2 |
B3 |
B4 |
a = min(Ai) |
|
A1 |
-8 |
6 |
0 |
7 |
-8 |
|
A2 |
3 |
-1 |
4 |
4 |
-1 |
|
A3 |
5 |
4 |
3 |
4 |
3 |
|
b = max(Bi) |
5 |
6 |
4 |
7 |
|
Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(ai) = 3, которая указывает на максимальную чистую стратегию A3.
Верхняя цена игры b = min(bj) = 4.
Что свидетельствует об отсутствии седловой точки, так как a ≠ b, тогда цена игры находится в пределах 3 ≤ y ≤ 4. Находим решение игры в смешанных стратегиях. Объясняется это тем, что игроки не могут объявить противнику свои чистые стратегии: им следует скрывать свои действия. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии).
2. Проверяем платежную матрицу на доминирующие строки и доминирующие столбцы.
Иногда на основании простого рассмотрения матрицы игры можно сказать, что некоторые чистые стратегии могут войти в оптимальную смешанную стратегию лишь с нулевой вероятностью.
Говорят, что i-я стратегия 1-го игрока доминирует его k-ю стратегию, если aij ≥ akj для всех j Э N и хотя бы для одного j aij > akj. В этом случае говорят также, что i-я стратегия (или строка) – доминирующая, k-я – доминируемая.
Говорят, что j-я стратегия 2-го игрока доминирует его l-ю стратегию, если для всех j Э M aij ≤ ail и хотя бы для одного i aij < ail. В этом случае j-ю стратегию (столбец) называют доминирующей, l-ю – доминируемой.
С позиции проигрышей игрока В стратегия B4 доминирует над стратегией B2 (все элементы столбца 4 больше элементов столбца 2), следовательно исключаем 4-й столбец матрицы. Вероятность q4 = 0.
|
-8 |
6 |
0 |
|
3 |
-1 |
4 |
|
5 |
4 |
3 |
В платежной матрице отсутствуют доминирующие строки.
Мы свели игру 3 x 4 к игре 3 x 3.
Так как игроки выбирают свои чистые стратегии случайным образом, то выигрыш игрока I будет случайной величиной. В этом случае игрок I должен выбрать свои смешанные стратегии так, чтобы получить максимальный средний выигрыш.
Аналогично, игрок II должен выбрать свои смешанные стратегии так, чтобы минимизировать математическое ожидание игрока I.
В матрице присутствуют отрицательные элементы. Для упрощения расчетов добавим к элементам матрицы (8). Такая замена не изменит решения игры, изменится только ее цена (по теореме фон Неймана).
0
|
14 |
8 |
|
|
11 |
7 |
12 |
|
13 |
12 |
11 |
3. Находим решение игры в смешанных стратегиях.
Математические модели пары двойственных задач линейного программирования можно записать так:
найти минимум функции F(x) при ограничениях:
11x2+13x3 ≥ 1
14x1+7x2+12x3 ≥ 1
8x1+12x2+11x3 ≥ 1
F(x) = x1+x2+x3 → min
найти максимум функции Ф(y) при ограничениях:
14y2+8y3 ≤ 1
11y1+7y2+12y3 ≤ 1
13y1+12y2+11y3 ≤ 1
Ф(y) = y1+y2+y3 → max
Решаем эти системы симплексным методом.
Решим прямую задачу линейного программирования двойственным симплексным методом, с использованием симплексной таблицы.
Приведем систему ограничений к системе неравенств смысла ≤, умножив соответствующие строки на (-1).
Определим минимальное значение целевой функции F(X) = x1 + x2 + x3 при следующих условиях-ограничений.
- 11x2 - 13x3≤-1
- 14x1 - 7x2 - 12x3≤-1
- 8x1 - 12x2 - 11x3≤-1
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x4. В 2-м неравенстве смысла (≤) вводим базисную переменную x5. В 3-м неравенстве смысла (≤) вводим базисную переменную x6.
0x1-11x2-13x3 + 1x4 + 0x5 + 0x6 = -1
-14x1-7x2-12x3 + 0x4 + 1x5 + 0x6 = -1
-8x1-12x2-11x3 + 0x4 + 0x5 + 1x6 = -1
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Экономический смысл дополнительных переменных: дополнительные перемены задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана.
Решим систему уравнений относительно базисных переменных:
x4, x5, x6,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,0,-1,-1,-1)
Базисное решение называется допустимым, если оно неотрицательно.
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
x4 |
-1 |
0 |
-11 |
-13 |
1 |
0 |
0 |
|
x5 |
-1 |
-14 |
-7 |
-12 |
0 |
1 |
0 |
|
x6 |
-1 |
-8 |
-12 |
-11 |
0 |
0 |
1 |
|
F(X0) |
0 |
-1 |
-1 |
-1 |
0 |
0 |
0 |
1. Проверка критерия оптимальности.
План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
2. Определение новой свободной переменной.
Среди отрицательных значений базисных переменных выбираем наибольший по модулю.
Ведущей будет 1-ая строка, а переменную x4 следует вывести из базиса.
3. Определение новой базисной переменной.
Минимальное значение θ соответствует 3-му столбцу, т.е. переменную x3 необходимо ввести в базис.
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-13).
Базис
|
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
|
x4 |
-1 |
0 |
-11 |
-13 |
1 |
0 |
0 |
|
x5 |
-1 |
-14 |
-7 |
-12 |
0 |
1 |
0 |
|
x6 |
-1 |
-8 |
-12 |
-11 |
0 |
0 |
1 |
|
F(X0) |
0 |
-1 |
-1 |
-1 |
0 |
0 |
0 |
|
θ |
0 |
- |
-1 : (-11) = 1/11 |
-1 : (-13) = 1/13 |
- |
- |
- |
4. Пересчет симплекс-таблицы.
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
x3 |
1/13 |
0 |
11/13 |
1 |
-1/13 |
0 |
0 |
|
x5 |
-1/13 |
-14 |
32/13 |
0 |
-12/13 |
1 |
0 |
|
x6 |
-2/13 |
-8 |
-29/13 |
0 |
-11/13 |
0 |
1 |
|
F(X0) |
1/13 |
-1 |
-2/13 |
0 |
-1/13 |
0 |
0 |
Представим расчет каждого элемента в виде таблицы:
|
B |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
x 6 |
|
-1 : -13 |
0 : -13 |
-11 : -13 |
-13 : -13 |
1 : -13 |
0 : -13 |
0 : -13 |
|
-1-(-1 •-12):-13 |
-14-(0 •-12):-13 |
-7-(-11 •-12):-13 |
-12-(-13 •-12):-13 |
0-(1 •-12):-13 |
1-(0 •-12):-13 |
0-(0 •-12):-13 |
|
-1-(-1 •-11):-13 |
-8-(0 •-11):-13 |
-12-(-11 •-11):-13 |
-11-(-13 •-11):-13 |
0-(1 •-11):-13 |
0-(0 •-11):-13 |
1-(0 •-11):-13 |
|
0-(-1 •-1):-13 |
-1-(0 •-1):-13 |
-1-(-11 •-1):-13 |
-1-(-13 •-1):-13 |
0-(1 •-1):-13 |
0-(0 •-1):-13 |
0-(0 •-1):-13 |
1. Проверка критерия оптимальности.
План 1 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
2. Определение новой свободной переменной.
Среди отрицательных значений базисных переменных выбираем наибольший по модулю.
Ведущей будет 3-ая строка, а переменную x6 следует вывести из базиса.
3. Определение новой базисной переменной.
Минимальное значение θ соответствует 2-му столбцу, т.е. переменную x2 необходимо ввести в базис.
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-29/13).
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
x3 |
1/13 |
0 |
11/13 |
1 |
-1/13 |
0 |
0 |
|
x5 |
-1/13 |
-14 |
32/13 |
0 |
-12/13 |
1 |
0 |
|
x6 |
-2/13 |
-8 |
-29/13 |
0 |
-11/13 |
0 |
1 |
|
F(X0) |
1/13 |
-1 |
-2/13 |
0 |
-1/13 |
0 |
0 |
|
θ |
0 |
-1 : (-8) = 1/8 |
-2/13 : (-29/13) = 2/35 |
- |
-1/13 : (-11/13) = 1/11 |
- |
- |
4. Пересчет симплекс-таблицы.
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
x3 |
1/35 |
-218/35 |
0 |
1 |
-12/35 |
0 |
11/35 |
|
x5 |
-9/35 |
-2313/35 |
0 |
0 |
-132/35 |
1 |
16/35 |
|
x2 |
2/35 |
234/35 |
1 |
0 |
11/35 |
0 |
-13/35 |
|
F(X1) |
3/35 |
-19/35 |
0 |
0 |
-1/35 |
0 |
-2/35 |
Представим расчет каждого элемента в виде таблицы:
|
B |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
x 6 |
|
1/13-(-2/13 •11/13):-29/13 |
0-(-8 •11/13):-29/13 |
11/13-(-29/13 •11/13):-29/13 |
1-(0 •11/13):-29/13 |
-1/13-(-11/13 •11/13):-29/13 |
0-(0 •11/13):-29/13 |
0-(1 •11/13):-29/13 |
|
-1/13-(-2/13 •2/13):-29/13 |
-14-(-8 •2/13):-29/13 |
32/13-(-29/13 •2/13):-29/13 |
0-(0 •2/13):-29/13 |
-12/13-(-11/13 •2/13):-29/13 |
1-(0 •2/13):-29/13 |
0-(1 •2/13):-29/13 |
|
-2/13 : -29/13 |
-8 : -29/13 |
-29/13 : -29/13 |
0 : -29/13 |
-11/13 : -29/13 |
0 : -29/13 |
1 : -29/13 |
|
1/13-(-2/13 •-2/13):-29/13 |
-1-(-8 •-2/13):-29/13 |
-2/13-(-29/13 •-2/13):-29/13 |
0-(0 •-2/13):-29/13 |
-1/13-(-11/13 •-2/13):-29/13 |
0-(0 •-2/13):-29/13 |
0-(1 •-2/13):-29/13 |
1. Проверка критерия оптимальности.
План 2 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
2. Определение новой свободной переменной.
Среди отрицательных значений базисных переменных выбираем наибольший по модулю.
Ведущей будет 2-ая строка, а переменную x5 следует вывести из базиса.
3. Определение новой базисной переменной.
Минимальное значение θ соответствует 4-му столбцу, т.е. переменную x4 необходимо ввести в базис.
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-132/35).
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
x3 |
1/35 |
-218/35 |
0 |
1 |
-12/35 |
0 |
11/35 |
|
x5 |
-9/35 |
-2313/35 |
0 |
0 |
-132/35 |
1 |
16/35 |
|
x2 |
2/35 |
234/35 |
1 |
0 |
11/35 |
0 |
-13/35 |
|
F(X0) |
3/35 |
-19/35 |
0 |
0 |
-1/35 |
0 |
-2/35 |
|
θ |
0 |
-19/35 : (-2313/35) = 19/818 |
- |
- |
-1/35 : (-132/35) = 1/67 |
- |
- |
4. Пересчет симплекс-таблицы.
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
x3 |
5/67 |
145/67 |
0 |
1 |
0 |
-12/67 |
7/67 |
|
x4 |
9/67 |
1214/67 |
0 |
0 |
1 |
-35/67 |
-41/67 |
|
x2 |
1/67 |
-58/67 |
1 |
0 |
0 |
11/67 |
-12/67 |
|
F(X2) |
6/67 |
-13/67 |
0 |
0 |
0 |
-1/67 |
-5/67 |
Представим расчет каждого элемента в виде таблицы:
|
B |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
x 6 |
|
1/35-(-9/35 •-12/35):-132/35 |
-218/35-(-2313/35 •-12/35):-132/35 |
0-(0 •-12/35):-132/35 |
1-(0 •-12/35):-132/35 |
-12/35-(-132/35 •-12/35):-132/35 |
0-(1 •-12/35):-132/35 |
11/35-(16/35 •-12/35):-132/35 |
|
-9/35 : -132/35 |
-2313/35 : -132/35 |
0 : -132/35 |
0 : -132/35 |
-132/35 : -132/35 |
1 : -132/35 |
16/35 : -132/35 |
|
2/35-(-9/35 •11/35):-132/35 |
234/35-(-2313/35 •11/35):-132/35 |
1-(0 •11/35):-132/35 |
0-(0 •11/35):-132/35 |
11/35-(-132/35 •11/35):-132/35 |
0-(1 •11/35):-132/35 |
-13/35-(16/35 •11/35):-132/35 |
|
3/35-(-9/35 •-1/35):-132/35 |
-19/35-(-2313/35 •-1/35):-132/35 |
0-(0 •-1/35):-132/35 |
0-(0 •-1/35):-132/35 |
-1/35-(-132/35 •-1/35):-132/35 |
0-(1 •-1/35):-132/35 |
-2/35-(16/35 •-1/35):-132/35 |
В базисном столбце все элементы положительные.
Переходим к основному алгоритму симплекс-метода.
1. Проверка критерия оптимальности.
Среди значений индексной строки нет положительных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
x3 |
5/67 |
145/67 |
0 |
1 |
0 |
-12/67 |
7/67 |
|
x4 |
9/67 |
1214/67 |
0 |
0 |
1 |
-35/67 |
-41/67 |
|
x2 |
1/67 |
-58/67 |
1 |
0 |
0 |
11/67 |
-12/67 |
|
F(X1) |
6/67 |
-13/67 |
0 |
0 |
0 |
-1/67 |
-5/67 |
Оптимальный план можно записать так:
x3 = 5/67
x2 = 1/67
F(X) = 1•5/67 + 1•1/67 = 6/67
Составим двойственную задачу к прямой задаче.
+ 14y2 + 8y3≤1
11y1 + 7y2 + 12y3≤1
13y1 + 12y2 + 11y3≤1
y1 + y2 + y3 → max
y1 ≥ 0
y2 ≥ 0
y3 ≥ 0
Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.
Из теоремы двойственности следует, что Y = C*A-1.
Составим матрицу A из компонентов векторов, входящих в оптимальный базис.
Определив обратную матрицу D = А-1 через алгебраические дополнения, получим:
Как видно из последнего плана симплексной таблицы, обратная матрица A-1 расположена в столбцах дополнительных переменных.
Тогда Y = C*A-1 =
Оптимальный план двойственной задачи равен:
y1 = 0
y2 = 1/67
y3 = 5/67
Z(Y) = 1*0+1*1/67+1*5/67 = 6/67
Критерий оптимальности полученного решения. Если существуют такие допустимые решения X и Y прямой и двойственной задач, для которых выполняется равенство целевых функций F(x) = Z(y), то эти решения X и Y являются оптимальными решениями прямой и двойственной задач соответственно.
Цена игры будет равна g = 1/F(x), а вероятности применения стратегий игроков:
pi = g*xi; qi = g*yi.
Цена игры: g = 1 : 6/67 = 111/6
p1 = 111/6 •= 0
p2 = 111/6 •1/67 = 1/6
p3 = 111/6 •5/67 = 5/6
Оптимальная смешанная стратегия игрока I:
P = (0; 1/6; 5/6)
q1 = 111/6 •= 0
q2 = 111/6 •1/67 = 1/6
q3 = 111/6 •5/67 = 5/6
Оптимальная смешанная стратегия игрока II:
Q = (0; 1/6; 5/6)
Поскольку ранее к элементам матрицы было прибавлено число (8), то вычтем это число из цены игры.
111/6 - 8 = 31/6
Цена игры: v=31/6
4. Проверим правильность решения игры с помощью критерия оптимальности стратегии.
∑aijqj ≤ v
∑aijpi ≥ v
M(P1;Q) = (-8•) + (6•1/6) + (0•5/6) = 1 ≤ v
M(P2;Q) = (3•) + (-1•1/6) + (4•5/6) = 3.167 = v
M(P3;Q) = (5•) + (4•1/6) + (3•5/6) = 3.167 = v
M(P;Q1) = (-8•) + (3•1/6) + (5•5/6) = 4.667 ≥ v
M(P;Q2) = (6•) + (-1•1/6) + (4•5/6) = 3.167 = v
M(P;Q3) = (0•) + (4•1/6) + (3•5/6) = 3.167 = v
Все неравенства выполняются как равенства или строгие неравенства, следовательно, решение игры найдено верно.
Решение с помощью пакета MS Excel:
Задание 2. Решение игры
Порядок выполнения:
|
T |
A |
B |
|
|
A |
0.3 |
0.4 |
0.1 |
|
B |
0.5 |
0.2 |
0.7 |
Ход работы:
Решение с помощью пакета MS Excel:
Тема 2. ПРИНЯТИЕ РЕШЕНИЙ В УСЛОВИЯХ РИСКА
Задание Определение наилучшей альтернативы в условиях риска и построение индивидуальной функции полезности
Порядок выполнения работы.
|
Недельный спрос, ящиков |
Вероятность |
|
11 |
0,4 |
|
12 |
0,4 |
|
13 |
0,2 |
Дерево решений запишется в виде
Решение с помощью пакета MS Excel:
Ожидаемый чистый доход максимален при выборе альтернативы А (330 долл.). С учетом штрафов за неудовлетворенный спрос максимальный чистый доход дает альтернатива В (319 долл.).
Министерство образования, науки, молодежи и спорта Украины
Одесский национальный политехнический университет
Институт промышленных технологий, дизайна и менеджмента
Кафедра информационных технологий проектирования в машиностроении
Расчетно-графическая работа
по дисциплине «Теория принятия решений»
Выполнил:
Ст.гр. М-102
Седашов Я.С.
Проверила:
Иващенко И.Н.
Одесса,2013