У вас вопросы?
У нас ответы:) SamZan.net

Игроки

Работа добавлена на сайт samzan.net: 2015-07-05

Поможем написать учебную работу

Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Предоплата всего

от 25%

Подписываем

договор

Выберите тип работы:

Скидка 25% при заказе до 7.6.2025

Задача 1

Свести матричную игру к  задачам  линейного программирования  и  найти  её  решение:

Решение

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

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

Игроки

-5

2

3

-5

3

-5

2

-5

2

3

-5

-5

3

3

3

Находим гарантированный выигрыш, определяемый нижней ценой игры  , которая указывает на максимальную чистую стратегию A1. Верхняя цена игры  . Это свидетельствует об отсутствии седловой точки, так как  , тогда цена игры находится в пределах   . Находим решение игры в смешанных стратегиях. Объясняется это тем, что игроки не могут объявить противнику свои чистые стратегии: им следует скрывать свои действия. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии).

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

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

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

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

0

7

8

8

0

7

7

8

0

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

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

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

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

Можно решить одну из систем, например решим вторую систему.

Цена игры будет равна  , а вероятности применения стратегий игроков:

,  .

Цена игры: ,

 

Оптимальная смешанная стратегия игрока 1:  P = (1/3; 1/3; 1/3).

Оптимальная смешанная стратегия игрока 2: Q = (1/3; 1/3; 1/3). Поскольку ранее к элементам матрицы было прибавлено число 5, то вычтем это число из цены игры.

5 - 5 = 0

Цена игры:   

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

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

Задача 2

Записать двойственную  задачу.  Симплекс – методом найти решение исходной и двойственной задач:

Решение

Найдём  решение  прямой  задачи,  приведя  её  к  каноническому  виду.  Там,  где  знак    вводим  дополнительную  переменную  со  знаком плюс,  а  там где  знак    вводим  дополнительную  переменную  со  знаком минус,  при этом  ещё  вводим  искусственный  базис.   Запишем данную  математическую  модель  в  каноническом  виде.

Решим  данную  задачу  симплекс – методом.

В  индексной  строке  выбираем  наибольшую  по  модулю  отрицательную  оценку (-2),  выделяем столбец.  У  нас  это  второй  столбец.  Находим  оценочные  отношения:  делим  столбец  С  на  столбец  Е  и  выбираем  наименьшее  отношение – у нас  это 1,5. Выделяем первую строку.  Выводим  из  базиса  переменную  ,  при  этом  в  базис  вводим  переменную .  Делим выделенную строку  на  ключевой  элемент, т.е.  на  4.  Записываем  пересчитывающие  коэффициенты  в  последний  столбец  - делением  генерального  столбца  на  ключевой  элемент,  кроме    строки  с  ключевым  элементом.  Все  остальные  элементы  пересчитываем  по  методу  Гаусса.  В результате  перейдём  к  следующей  симплекс – таблице.

Так  как  в  индексной  строке  есть  отрицательная  оценка,  следовательно,  требуется  улучшение  оптимального   плана.  Выделяем   столбец  с  отрицательной  оценкой – это  первый  столбец.  Находим  оценочные  отношения,  делением   столбца  В  на  столбец  ,   выбираем  наименьшее  отношение – это  третья строка  с  отношением  3,14,  выделяем  её. Из  базиса  выводим  переменную  ,  при  этом  в  базис  вводим  переменную  .  Аналогично  пересчитываем  все невыделенные  элементы.    Получим  новую  симплекс – таблицу.

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

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

 Решим  двойственную  задачу прямой задачи.

Правило   построения  двойственной  задачи  состоит  в  следующем.  Каждому  равенству   прямой  задачи  соответствует   двойственная  переменная

Стрелки   показывают,  что  первому  равенству  соответствует  переменная  ,    второму – переменная  ,  третьему .

Для  определения  целевой  функции    двойственной  задачи  двойственные  переменные   ,   и     умножаются  на  правые  части   равенств  и  складываются:

.

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

Аналогично,  записываются  левые  части  ограничений  для  переменной   .  Двойственные  переменные  ,   и   умножаются  на  коэффициенты  перед  переменной    и  складываются:  .  

Для  переменной    .

Левая  часть   ограничений  для  переменной    равна   ,  а для   переменной  , для  переменной  .  Правые  части   ограничений  равны  коэффициентам  1,  2, -1  целевой  функции   .

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

В результате математическая   модель двойственной  задачи  имеет  вид:

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

 

при  ограничениях

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

Решим  данную  задачу  симплекс – методом,  для  этого  приведём  математическую модель задачи  к  канонической  форме.  Введём дополнительные  переменные  .

Но коэффициенты  при  новых  переменных  отрицательны,  так  как  знак  ,  а  решения  симплекс-методом  все  коэффициенты  при базисных  переменных  должны  быть  равны (+1), поэтому  вводим три  искусственные  базиса  .

Строим симплекс таблицу.  Так  как  задача на  нахождения  минимального значения,  то  в индексной  строке  выбираем наибольшую по модулю  отрицательную  оценку – это  первый  столбец,  выделяем  его. Далее  находим оценочные  отношения,  из  них  выбираем наименьшее, выделим  эту строку – у  нас  это  третья строка,  а  также  вычислим   коэффициенты  в  последнем столбце.  

Итерации  проводим  до  тех  пор,  пока  в  индексной  строке  не  будут  все  отрицательные  элементы  либо  равны  нулю.

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

Сравнивая  прямую  и  двойственную  задачи,  видим,  что  целевые  функции  равны:  ,  а  это  значит,  что  полученное  решение верно.

PAGE  4




1. тема права Система права это внутреннее строение структурных элементов права
2. Методичні рекомендації до педагогічної практики бакалавра фізикоматематичного факультету
3. Цифровой кухонный таймер
4. Прометей Скрябина
5. Русская интеллигенция как специфический феномен русской культуры
6.  На уровне значимости проверить гипотезу о нормальном распределении с
7. Эдельвейс Наш телефон - 88462415468 Ул.
8. Муми терапия
9. Некапиталистические системы хозяйства по А Чаянову- основания типологии
10. Исследование товарной продукции компании Nestle