Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Задача 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