Методы решения конечных игр: сведение игры к задаче линейного программирования
Анализ метода сведения матричной игры к задаче линейного программирования для реализации поставленных задач. Оформление соответствующей программному обеспечению документации. Характеристика симплекс-метода, его алгоритм и особенности использования.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 17.04.2013 |
| Размер файла | 215,1 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Содержание
- Введение
- 1. Цели и задачи курсовой работы
- 2. Методы решения конечных игр: сведение игры mxn к задаче линейного программирования
- 2.1 Симплекс-метод
- 2.2 Алгоритм симплекс-метода
- 3. Использование симплексного метода
- 4. Задача по курсовой работе
- 4.1 Решение задачи
- Заключение
- Список используемой литературы
Введение
Курсовое проектирование по дисциплине "Математические методы" является неотъемлемой частью подготовки специалистов в среднем профессиональным образованием.
Теория игр находится в тесной связи с линейным программированием, так как каждая конечная игра двух лиц с нулевой суммой может быть представлена как задача линейного программирования и решена симплексным методом и, наоборот, задача линейного программирования может быть представлена как игра.
1. Цели и задачи курсовой работы
Цель курсовой работы:
Изучить метод сведения матричной игры к задаче линейного программирования для реализации поставленных задач и овладеть навыками оформления соответствующей программному обеспечению документации.
Задачи курсовой работы:
а) закрепить, углубить и обобщить теоретические знания, полученные по изучаемым дисциплинам, и применить эти знаний к комплексному решению конкретной информационной задачи;
б) развить навыки работы со справочной литературой, материалами ГОСТов;
в) проанализировать полученные результаты работы;
2. Методы решения конечных игр: сведение игры mxn к задаче линейного программирования
2.1 Симплекс-метод
Симплекс-метод - алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве. Метод был разработан советским математиком Канторовичем Л.В. в 1937 году.
Задача линейного программирования состоит в том, что необходимо максимизировать или минимизировать некоторый линейный функционал на многомерном пространстве при заданных линейных ограничениях. Заметим, что каждое из линейных неравенств на переменные ограничивает полупространство в соответствующем линейном пространстве. В результате все неравенства ограничивают некоторый многогранник (возможно, бесконечный), называемый также полиэдральным комплексом. Уравнение W (x) = c, где W (x) - максимизируемый (или минимизируемый) линейный функционал, порождает гиперплоскость L (c). Зависимость от c порождает семейство параллельных гиперплоскостей. Тогда экстремальная задача приобретает следующую формулировку - требуется найти такое наибольшее c, что гиперплоскость L (c) пересекает многогранник хотя бы в одной точке. Заметим, что пересечение оптимальной гиперплоскости и многогранника будет содержать хотя бы одну вершину, причём, их будет более одной, если пересечение содержит ребро или k-мерную грань. Поэтому максимум функционала можно искать в вершинах многогранника. Принцип симплекс-метода состоит в том, что выбирается одна из вершин многогранника, после чего начинается движение по его рёбрам от вершины к вершине в сторону увеличения значения функционала. Когда переход по ребру из текущей вершины в другую вершину с более высоким значением функционала невозможен, считается, что оптимальное значение c найдено.
Последовательность вычислений симплекс-методом можно разделить на две основные фазы:
1. нахождение исходной вершины множества допустимых решений,
2. последовательный переход от одной вершины к другой, ведущий к оптимизации значения целевой функции.
При этом в некоторых случаях исходное решение очевидно или его определение не требует сложных вычислений, например, когда все ограничения представлены неравенствами вида "меньше или равно" (тогда нулевой вектор совершенно точно является допустимым решением, хотя и, скорее всего, далеко не самым оптимальным). В таких задачах первую фазу симплекс-метода можно вообще не проводить. Симплекс-метод, соответственно, делится на однофазный и двухфазный.
2.2 Алгоритм симплекс-метода
Усиленная постановка задачи
Рассмотрим следующую задачу линейного программирования:
Теперь поставим эту задачу в эквивалентной усиленной форме. Необходимо максимизировать Z:
(1)
Где, x - переменные из исходного линейного функционала,
xs - новые переменные, дополняющие старые таким образом, что неравенство переходит в равенство,
c - коэффициенты исходного линейного функционала,
Z - переменная, которую необходимо максимизировать.
Полупространства и в пересечении образуют многогранник, представляющий множество допустимых решений. Разница между числом переменных и уравнений даёт нам число степеней свободы. Проще говоря, если мы рассматриваем вершину многогранника, то это число рёбер, по которым мы можем продолжать движение. Тогда мы можем присвоить этому числу переменных значение 0 и назвать их "непростыми". Остальные переменные при этом будут вычисляться однозначно и называться "простыми". Полученная точка будет вершиной в пересечении соответствующих непростым переменным гиперплоскостей. Для того, чтобы найти т. н. начальное допустимое решение (вершину, из которой мы начнём движение), присвоим всем изначальным переменным x значение 0 и будем их считать непростыми, а все новые будем считать простыми. При этом начальное допустимое решение вычисляется однозначно: .
Алгоритм
Теперь приведём шаги алгоритма. На каждом шаге мы будем менять множества простых и непростых векторов (двигаться по рёбрам), и матрица будет иметь следующий вид:
(2)
где cB - коэффициенты вектора c соответствующие простым переменным (переменным xs соответствуют 0), B - столбцы АЕ, соответствующие простым переменным. Матрицу, образованную оставшимися столбцами обозначим D. Почему матрица будет иметь такой вид поясним в описании шагов алгоритма.
Первый шаг
Выбираем начальное допустимое значение, как указано выше. На первом шаге B - единичная матрица, так как простыми переменными являются xs. cB - нулевой вектор по тем же причинам.
Второй шаг
Покажем, что в выражении только непростые переменные имеют ненулевой коэффициент. Заметим, что из выражения Ax+xs=b простые переменные однозначно выражаются через непростые, так как число простых переменных равно числу уравнений. Пусть x ' - простые, а x ' ' - непростые переменные на данной итерации. Уравнение Ax+xs=b можно переписать, как Bx '+Dx ' '=b. Умножим его на слева:. +=
Таким образом мы выразили простые переменные через непростые, и в выражении, эквивалентному левой части равенства, все простые переменные имеют единичные коэффициенты. Поэтому, если прибавить к равенству равенство, то в полученном равенстве все простые переменные будут иметь нулевой коэффициент - все простые переменные вида x сократятся, а простые переменные вида xs не войдут в выражение.
Выберем ребро, по которому мы будем перемещаться. Поскольку мы хотим максимизировать Z, то необходимо выбрать переменную, которая будет более всех уменьшать выражение
Для этого выберем переменную, которая имеет наибольший по модулю отрицательный коэффициент. Если таких переменных нет, то есть все коэффициенты этого выражения неотрицательны, то мы пришли в искомую вершину и нашли оптимальное решение. В противном случае начнём увеличивать эту непростую переменную, то есть перемещаться по соответствующему ей ребру. Эту переменную назовём входящей.
Третий шаг
Теперь необходимо понять, какая простая переменная первой обратится в ноль по мере увеличения входящей переменной. Для этого достаточно рассмотреть систему:
При фиксированных значениях непростых переменных система однозначно разрешима относительно простых, поэтому мы можем определить, какая из простых переменных первой достигнет нуля при увеличении входящей. Эту переменную назовем выходящей. Это будет означать, что мы натолкнулись на новую вершину. Теперь входящую и выходящую переменную поменяем местами - входящая "войдёт" в простую, а выходящая из них "выйдет" в непростые. Теперь перепишем матрицу B и вектор cB в соответствии с новыми наборами простых и непростых переменных, после чего вернёмся ко второму шагу.
Поскольку число вершин конечно, то алгоритм однажды закончится. Найденная вершина будет являться оптимальным решением.
симплекс игра линейное программирование
3. Использование симплексного метода
Предприятие выпускает скоропортящуюся продукцию, которую сразу можно доставить потребителю (А1 стратегия).
Отправить на склад для хранения (А2 стратегия) или подвергнуть обработке для длит. Хранения (А3 стратегия). Потребитель может приобрести немедленно (В1 стратегия), через некоторое время (В2 стратегия) или после длительного периода (В3 стратегия). В случае стратегий А2 и А3 предприятие несет дополнительные затраты на хранение и обработку продукции.
Однако, при А2 следует вычесть убытки, если потребитель выберет стратегию В2 или В3.
Определить оптимальные пропорции для применения стратегий А1, А2, А3.
Руководствуясь минимаксным критерием, гарантирует средний уровень убытка. Пользуясь минимальным критерием из таблицы.
Таблица 1 - Оптимальные стратегии
|
Игроки |
B1 |
B2 |
B3 |
a =min (Ai) |
|
|
A1 |
2 |
3 |
2 |
2 |
|
|
A2 |
4 |
2 |
1 |
1 |
|
|
A3 |
1 |
3 |
3 |
1 |
|
|
b = max (Bi) |
4 |
3 |
3 |
0 |
Решение матричной игры. Находим гарантированный выигрыш, определяемый нижней ценой игры a = max (ai) = 2, которая указывает на максимальную чистую стратегию A1. Верхняя цена игры b = min (bj) = 3. Что свидетельствует об отсутствии седловой точки, так как a<>b, тогда цена игры находится в пределах 2<= y <= 3. Находим решение игры в смешанных стратегиях.
Математические модели пары двойственных задач линейного программирования можно записать так:
найти минимум функции F (x) при ограничениях:
2x1+4x2+x3 >= 1, 3x1+2x2+3x3 >= 1, 2x1+x2+3x3 >= 1
F (x) = x1+x2+x3 = min
Найти максимум функции Ф (y) при ограничениях:
2y1+3y2+2y3 <= 1, 4y1+2y2+y3 <= 1, y1+3y2+3y3 <= 1
Ф (y) = y1+y2+y3 = max
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим минимальное значение целевой функции F (X) = x1 + x2 + x3 при следующих условиях-ограничениях.
2x1 + 4x2 + x3?1, 3x1 + 2x2 + 3x3?1, 2x1 + x2 + 3x3?1
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
2x1 + 4x2 + 1x3-1x4 + 0x5 + 0x6 = 1
3x1 + 2x2 + 3x3 + 0x4-1x5 + 0x6 = 1
2x1 + 1x2 + 3x3 + 0x4 + 0x5-1x6 = 1
Поскольку задача решается на минимум и элементы единичной матрицы отрицательны, сведем задачу к нахождению максимума.
Для этого умножим все строки на (-1) и будем искать первоначальный опорный план.
2x1-4x2-1x3 + 1x4 + 0x5 + 0x6 = - 1
3x1-2x2-3x3 + 0x4 + 1x5 + 0x6 = - 1
2x1-1x2-3x3 + 0x4 + 0x5 + 1x6 = - 1
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных:
x4, x5, x6,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,0,-1,-1,-1)
Таблица 2 - Первый опорный план
|
План |
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
|
0 |
x4 |
-1 |
-2 |
-4 |
-1 |
1 |
0 |
0 |
|
|
x5 |
-1 |
-3 |
-2 |
-3 |
0 |
1 |
0 |
||
|
x6 |
-1 |
-2 |
-1 |
-3 |
0 |
0 |
1 |
||
|
Индексная строка |
F (X0) |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
В столбце свободных членов есть отрицательные элементы. Используем двойственный симплекс-метод. Выберем из них наибольший по модулю, а в его строке - любой отрицательный. Взяв этот элемент в качестве разрешающего пересчитаем таблицу.
В качестве ведущего выберем столбец, соответствующий переменной x1. 1-ая строка является ведущей.
Таблица 3 - Расчет двойственного симплекс-метода
|
План |
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
min |
|
|
x1 |
1/2 |
1 |
2 |
1/2 |
-1/2 |
0 |
0 |
0 |
||
|
x5 |
1/2 |
0 |
4 |
-11/2 |
-11/2 |
1 |
0 |
0 |
||
|
x6 |
0 |
0 |
3 |
-2 |
-1 |
0 |
1 |
0 |
||
|
Индексная строка |
F (X) |
-1/2 |
0 |
-1 |
1/2 |
1/2 |
0 |
0 |
0 |
Представим расчет каждого элемента в виде таблицы:
Таблица 4 - Расчет каждого элемента
|
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
|
1/2: 1 |
1: 1 |
2: 1 |
1/2: 1 |
-1/2: 1 |
0: 1 |
0: 1 |
|
|
1/2- (1/20): 1 |
0- (10): 1 |
4- (20): 1 |
-11/2- (1/20): 1 |
-11/2- (-1/20): 1 |
1- (00): 1 |
0- (00): 1 |
|
|
0- (1/20): 1 |
0- (10): 1 |
3- (20): 1 |
-2- (1/20): 1 |
-1- (-1/20): 1 |
0- (00): 1 |
1- (00): 1 |
|
|
-1/2- (1/20): 1 |
0- (10): 1 |
-1- (20): 1 |
1/2- (1/20): 1 |
1/2- (-1/20): 1 |
0- (00): 1 |
0- (00): 1 |
В базисном столбце все элементы положительные.
Переходим к основному алгоритму симплекс-метода.
Таблица 5 - Конечный опорный план
|
План |
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
min |
|
|
1 |
x1 |
1/2 |
1 |
2 |
1/2 |
-1/2 |
0 |
0 |
1/4 |
|
|
x5 |
1/2 |
0 |
4 |
-11/2 |
-11/2 |
1 |
0 |
1/8 |
||
|
x6 |
0 |
0 |
3 |
-2 |
-1 |
0 |
1 |
0 |
||
|
Индексная строка |
F (X1) |
-1/2 |
0 |
-1 |
1/2 |
1/2 |
0 |
0 |
0 |
Итерация №0.Текущий опорный план не оптимален, так как в индексной строке находятся отрицательные коэффициенты. В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю. Вычислим значения Di по строкам как частное от деления:
и из них выберем наименьшее:
min (1/2: 2, 1/2: 4, - ) = 0
Следовательно, 3-ая строка является ведущей. Разрешающий элемент равен (3) и находится на пересечении ведущего столбца и ведущей строки.
Формируем следующую часть симплексной таблицы. Вместо переменной (x) в план 1 войдет переменная x2. Строка, соответствующая переменной x2 в плане 1, получена в результате деления всех элементов строки x6 плана 0 на разрешающий элемент РЭ=3
На месте разрешающего элемента в плане 1 получаем 1. В остальных клетках столбца x2 плана 1 записываем нули. Таким образом, в новом плане 1 заполнены строка x2 и столбец x2.
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника. Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В) /РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (3), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:
Таблица 6 - Расчет опорного плана
|
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
|
1/2- (02): 3 |
1- (02): 3 |
2- (32): 3 |
1/2- (-22): 3 |
-1/2- (-12): 3 |
0- (02): 3 |
0- (12): 3 |
|
|
1/2- (04): 3 |
0- (04): 3 |
4- (34): 3 |
-11/2- (-24): 3 |
-11/2- (-14): 3 |
1- (04): 3 |
0- (14): 3 |
|
|
0: 3 |
0: 3 |
3: 3 |
-2: 3 |
-1: 3 |
0: 3 |
1: 3 |
|
|
-1/2- (0-1): 3 |
0- (0-1): 3 |
-1- (3-1): 3 |
1/2- (-2-1): 3 |
1/2- (-1-1): 3 |
0- (0-1): 3 |
0- (1-1): 3 |
Таблица 7 - План 2
|
План |
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
min |
|
|
2 |
x1 |
1/2 |
1 |
0 |
15/6 |
1/6 |
0 |
-2/3 |
3 /11 |
|
|
x5 |
1/2 |
0 |
0 |
11/6 |
-1/6 |
1 |
-11/3 |
3/7 |
||
|
x2 |
0 |
0 |
1 |
-2/3 |
-1/3 |
0 |
1/3 |
- |
||
|
Индексная строка |
F (X2) |
-1/2 |
0 |
0 |
-1 /6 |
1/6 |
0 |
1/3 |
0 |
Итерация №1. Текущий опорный план не оптимален, так как в индексной строке находятся отрицательные коэффициенты. В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления:
и из них выберем наименьшее:
min (1/2: 15/6, 1/2: 11/6, - ) = 3/11
Следовательно, 1-ая строка является ведущей. Разрешающий элемент равен (15/6) и находится на пересечении ведущего столбца и ведущей строки.
Формируем следующую часть симплексной таблицы.
Вместо переменной x в план 2 войдет переменная x3. Строка, соответствующая переменной x3 в плане 2, получена в результате деления всех элементов строки x1 плана 1 на разрешающий элемент РЭ=15/6. На месте разрешающего элемента в плане 2 получаем 1.
В остальных клетках столбца x3 плана 2 записываем нули. Таким образом, в новом плане 2 заполнены строка x3 и столбец x3. Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника. Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В) /РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (15/6), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:
Таблица 8 - Расчет элементов старого плана
|
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
|
1/2: 15/6 |
1: 15/6 |
0: 15/6 |
15/6: 15/6 |
1/6: 15/6 |
0: 15/6 |
-2/3: 15/6 |
|
|
1/2- (1/211/6): 15/6 |
0- (111/6): 15/6 |
0- (011/6): 15/6 |
11/6- (15/611/6): 15/6 |
-1/6- (1/611/6): 15/6 |
1- (011/6): 15/6 |
-11/3- (-2/311/6): 15/6 |
|
|
0- (1/2-2/3): 15/6 |
0- (1-2/3): 15/6 |
1- (0-2/3): 15/6 |
-2/3- (15/6-2/3): 15/6 |
-1/3- (1/6-2/3): 15/6 |
0- (0-2/3): 15/6 |
1/3- (-2/3-2/3): 15/6 |
|
|
-1/2- (1/2-1/6): 15/6 |
0- (1-1/6): 15/6 |
0- (0-1/6): 15/6 |
-1/6- (15/6-1/6): 15/6 |
1/6- (1/6-1/6): 15/6 |
0- (0-1/6): 15/6 |
1/3- (-2/3-1/6): 15/6 |
Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план.
Таблица 9 - Окончательный вариант симплекс-таблицы
|
План |
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
|
3 |
x3 |
3/11 |
6/11 |
0 |
1 |
1/11 |
0 |
-4/11 |
|
|
x5 |
2/11 |
-7/11 |
0 |
0 |
-3/11 |
1 |
-10/11 |
||
|
x2 |
2/11 |
4/11 |
1 |
0 |
-3/11 |
0 |
1/11 |
||
|
Индексная строка |
F (X3) |
-5/11 |
1/11 |
0 |
0 |
2/11 |
0 |
3/11 |
Оптимальный план можно записать так:
x3 = 3/11
x5 = 2/11
x2 = 2/11
F (X) = 13/11 + 12/11 = 5/11
Составим двойственную задачу к прямой задаче.
2y1 + 3y2 + 2y3?1
4y1 + 2y2 + y3?1
y1 + 3y2 + 3y3?1
y1 + y2 + y3 =>max
y1 ? 0; y2 ? 0; y3?0
Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.
Из теоремы двойственности следует, что Y = C*A-1. Составим матрицу A из компонентов векторов, входящих в оптимальный базис.
Определив обратную матрицу А-1 через алгебраические дополнения, получим:
Как видно из последнего плана симплексной таблицы, обратная матрица A1 расположена в столбцах дополнительных переменных.
Тогда Y = C*A-1=
Оптимальный план двойственной задачи равен:
y1 = 2/11
y2 = 0
y3 = 3/11
Z (Y) = 1*2/11+1*0+1*3/11 = 5/11
Цена игры будет равна g = 1/F (x), а вероятности применения стратегий игроков:
pi = g*xi; qi = g*yi.
Цена игры:
g = 1: 5/11 = 21/5
p1 = 21/50 = 0
p2 = 21/52/11 = 2/5
p3 = 21/53/11 = 3/5
q1 = 21/52/11 = 2/5
q2 = 21/50 = 0
q3 = 21/53/11 = 3/5
Оптимальная стратегия игрока А:
P (0; 2/5; 3/5)
Оптимальная стратегия игрока B:
Q (2/5; 0; 3/5)
4. Задача по курсовой работе
Игра "Три пальца". Два игрока К и С одновременно и не сговариваясь показывают друг другу один, два или три пальца. Если всего показанных пальцев (первым и вторым вместе) будет четное число, то выигрывает К: он получает столько очков, сколько всего было пальцев, если нечетное - выигрывает С, на тех же условиях. Требуется записать игру в нормальной форме.
4.1 Решение задачи
Расчёт оптимальных стратегий для игры "Три пальца"
Перенумеруем стратегии по числу показанных пальцев. Игра 3x3. Матрица игры будет:
Таблица 10 - Матрица игры "Три пальца"
|
C1 |
C2 |
C3 |
||
|
К1 |
2 |
-3 |
4 |
|
|
К2 |
-3 |
4 |
-5 |
|
|
К3 |
4 |
-5 |
6 |
Проверяем, имеет ли платежная матрица седловую точку. Если да, то выписываем решение игры в чистых стратегиях. Считаем, что игрок I выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а игрок II выбирает свою стратегию так, чтобы минимизировать выигрыш игрока I.
Таблица 11 - Нахождение гарантированного выигрыша
|
Игроки |
B1 |
B2 |
B3 |
a = min (Ai) |
|
|
A1 |
2 |
-3 |
4 |
-3 |
|
|
A2 |
-3 |
4 |
-5 |
-5 |
|
|
A3 |
4 |
-5 |
6 |
-5 |
|
|
b = max (Bi) |
4 |
4 |
6 |
Находим гарантированный выигрыш, определяемый нижней ценой игры a = max (ai) = - 3, которая указывает на максимальную чистую стратегию A1. Верхняя цена игры b = min (bj) = 4.
Что свидетельствует об отсутствии седловой точки, так как a ? b, тогда цена игры находится в пределах - 3 ? y ? 4. Находим решение игры в смешанных стратегиях. Объясняется это тем, что игроки не могут объявить противнику свои чистые стратегии: им следует скрывать свои действия. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии).
Проверяем платежную матрицу на доминирующие строки и доминирующие столбцы. Иногда на основании простого рассмотрения матрицы игры можно сказать, что некоторые чистые стратегии могут войти в оптимальную смешанную стратегию лишь с нулевой вероятностью.
Говорят, что i-я стратегия 1-го игрока доминирует его k-ю стратегию, если aij ? akj для всех j Э N и хотя бы для одного jaij>akj. В этом случае говорят также, что i-я стратегия (или строка) - доминирующая, k-я - доминируемая.
Говорят, что j-я стратегия 2-го игрока доминирует его l-ю стратегию, если для всех j ЭMaij ? ail и хотя бы для одного i aij<ail. В этом случае j-ю стратегию (столбец) называют доминирующей, l-ю - доминируемой.
В платежной матрице отсутствуют доминирующие строки.
В платежной матрице отсутствуют доминирующие столбцы.
Так как игроки выбирают свои чистые стратегии случайным образом, то выигрыш игрока I будет случайной величиной. В этом случае игрок I должен выбрать свои смешанные стратегии так, чтобы получить максимальный средний выигрыш. Аналогично, игрок II должен выбрать свои смешанные стратегии так, чтобы минимизировать математическое ожидание игрока I. В матрице присутствуют отрицательные элементы. Для упрощения расчетов добавим к элементам матрицы пятерку. Такая замена не изменит решения игры, изменится только ее цена (по теореме фон Неймана).
Таблица 12 - Добавочная пятерка
|
7 |
2 |
9 |
|
|
2 |
9 |
0 |
|
|
9 |
0 |
11 |
Находим решение игры в смешанных стратегиях.
Математические модели пары двойственных задач линейного программирования можно записать так: найти минимум функции F (x) при ограничениях:
7x1+2x2+9x3 ? 1
2x1+9x2 ? 1
9x1+11x3 ? 1
F (x) = x1+x2+x3 > min
найти максимум функции Ф (y) при ограничениях:
7y1+2y2+9y3 ? 1
2y1+9y2 ? 1
9y1+11y3 ? 1
Ф (y) = y1+y2+y3 > max
Решаем эти системы симплексным методом.
Цена игры будет равна g = 1/F (x), а вероятности применения стратегий игроков:
pi = g*xi; qi = g*yi.
Цена игры:
g = 1: 1/5 = 5
p1 = 5 1/20 = 1/4
p2 = 5 1/10 = 1/2
p3 = 5 1/20 = ј
Оптимальная смешанная стратегия игрока I:
P = (1/4; 1/2; 1/4)
q1 = 5 1/20 = 1/4
q2 = 5 1/10 = 1/2
q3 = 5 1/20 = ј
Оптимальная смешанная стратегия игрока II:
Q = (1/4; 1/2; 1/4)
Поскольку ранее к элементам матрицы было прибавлено число (5), то вычтем это число из цены игры.
5 - 5 = 0
Цена игры: v=0
Проверим правильность решения игры с помощью критерия оптимальности стратегии.
?aijqj ? v
?aijpi ? v
M (P1; Q) = (21/4) + (-31/2) + (41/4) = 0 = v
M (P2; Q) = (-31/4) + (41/2) + (-51/4) = 0 = v
M (P3; Q) = (41/4) + (-51/2) + (61/4) = 0 = v
M (P; Q1) = (21/4) + (-31/2) + (41/4) = 0 = v
M (P; Q2) = (-31/4) + (41/2) + (-51/4) = 0 = v
M (P; Q3) = (41/4) + (-51/2) + (61/4) = 0 = v
Все неравенства выполняются как равенства или строгие неравенства, следовательно, решение игры найдено верно.
Заключение
В наше время достаточно часто решения приходиться принимать в условиях неопределённости, то есть, в таких условиях, когда или процесс выполнения операции является неопределённым, или нам сознательно противодействует противник, или нет ясных и чётких целей операций.
Наличие неопределённости значительно усложняет процесс выбора эффективных (оптимальных) решений и может привести к не предсказуемым результатам. На практике, при проведении экономического анализа, во многих случаях пытаются не замечать указанное "зло", вызванное фактором неопределённости и действуют (принимают решение) на основе детерминированных моделей. Иначе говоря, предполагается, что факторы, влияющие на принимаемые решения, известны точно. К сожалению, действительность часто не соответствует таким представлениям. Поэтому политика выбора эффективных решений без учета неконтролируемых факторов во многих случаях приводит к значительным потерям экономического, социального и иного содержания.
Рассматривая неопределённость, которая является наиболее характерной причиной риска в экономической деятельности, необходимо отметить, что выделение и изучение её применительно к процессу экономической, управленческой, финансовой и других видов деятельности является крайне необходимым, поскольку при этом отображается практическая ситуация, когда нет возможности осуществлять перечисленные виды деятельности в условиях, которых не могут быть однозначно определены.
В целом ряде экономических задач приходиться анализировать ситуации, в которых необходимо принимать решения в условиях неопределённости, то есть, например, возникают ситуации, в которых сталкиваются интересы двух или более конкурирующих сторон, каждая из которых преследует свою цель, причём, результат любого мероприятия каждой из сторон зависит от того, какие действия предпримет противник. Это особенно характерно в условиях рыночной экономики. Такие ситуации называются конфликтными. Научно обоснованные методы решения задач с конфликтными ситуациями даёт теория игр.
Список используемой литературы
1. Вентцель Е.С. Исследование операций: задачи, принципы, методология. - М.: Высшая школа, 2001.
2. Акулич И.Л. Математическое программирование в примерах и задачах. - М.: Высшая школа, 1986.
3. Шапкин А.С., Мазаева Н.П. Математические методы и модели исследования операций. - М.: 2006.
4. Агальцов В.П., Волдайская И.В. Математические методы в программировании. - М.: "Форум"-ИНФРА-М, 2006.
5. Партыка Т.Л., Попов И.И. Математические методы. - М.: "Форум"-ИНФРА-М, 2005.
6. Хемди А. ТахаГлава 3. Симплекс-метод // Введение в исследование операций = OperationsResearch: AnIntroduction. - 7-е изд. - М.: "Вильямс", 2007. - С.95-141. - ISBN 0-13-032374-8
7. АкуличИ.Л. Глава 1. Задачи линейного программирования // Математическое программирование в примерах и задачах. - М.: Высшая школа, 1986. - 319 с. - ISBN 5-06-002663-9
8. Томас Х. Кормен и др. Глава 29. Линейное программирование // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. - 2-е изд. - М.: "Вильямс", 2006. - С.1296. - ISBN 5-8459-0857-4
9. Емельянов А.А. Имитационное моделирование экономических процессов [Текст]: Учеб. пособие для вузов / А.А. Емельянов, Е.А. Власова, Р.В. Дума. - М.: Финансы и статистика, 2002. - 368с.
10. Бусленко, Н.П. Моделирование сложных систем [Текст] / Н.П. Бусленко. - М.: Наука, 1978. - 399с.
11. Советов Б.Я. Моделирование систем [Текст]: Учеб. для вузов / Б.Я. Сове тов, С.А. Яковлев. - М.: Высш. школа, 1985. - 271 с.4 Советов Б.Я. Моделирование систем [Текст]: Лабораторный практи кум:
Учеб. пособие для вузов по специальности: "Автом. сист. обработ. инф. и управл." / Б.Я. Советов, С.А. Яковлев. - М.: Высш. шк., 1989. - 80 с.
12. МаксимейИ.В. Имитационное моделирование на ЭВМ [Текст] / Максимей, И.В. - М: РАДИО И СВЯЗЬ, 1988. - 231с.
13. Вентцель Е.С. Теория вероятностей [Текст]: учеб. для вузов / Е.С. Вент цель. - М.: Высш. шк., 2001. - 575 с.
14. Гмурман, В.Е. Теория вероятностей и математическая статисти ка [Текст]: учеб. пособие / В.Е. Гмурман. - М.: Высш. шк., 2001. - 479 с.
15. Теоретические сведения о симплекс-методе [электронный ресурс]: http://ru. wikipedia.org/wiki
16. Алгоритм решения функции симплекс-методом [электронный ресурс]: http://math. semestr.ru/simplex/simplex. php
17. Исследовано в России [Электронный ресурс]: многопредмет. науч. журн. / Моск. физ. - техн. ин-т. - Электрон. журн. - Долгопрудный: МФТИ, 1998. - Режим доступа: http://zhurnal. mipt. rssi.ru. - Загл. с экрана.
Размещено на Allbest.ru
...Подобные документы
Сущность линейного программирования. Математическая формулировка задачи ЛП и алгоритм ее решения с помощью симплекс-метода. Разработка программы для планирования производства с целью обеспечения максимальной прибыли: блок-схема, листинг, результаты.
курсовая работа [88,9 K], добавлен 11.02.2011Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции.
курсовая работа [1,1 M], добавлен 21.03.2012Классификация задач математического программирования. Сущность графического метода решения задач линейного программирования, алгоритм табличного симплекс-метода. Описание логической структуры и текст программы по решению задачи графическим методом.
курсовая работа [263,5 K], добавлен 27.03.2011Характеристика параметрических методов решения задач линейного программирования: методы внутренней и внешней точки, комбинированные методы. Алгоритм метода барьерных поверхностей и штрафных функций, применяемых для решения задач большой размерности.
контрольная работа [59,8 K], добавлен 30.10.2014Анализ метода линейного программирования для решения оптимизационных управленческих задач. Графический метод решения задачи линейного программирования. Проверка оптимального решения в среде MS Excel с использованием программной надстройки "Поиск решения".
курсовая работа [2,2 M], добавлен 29.05.2015Характеристика основных методов линейного программирования с n- переменными, в частности, графического и симплекс-метода. Способы решения задачи по определению оптимальной структуры товарооборота, обеспечивающей торговому предприятию максимум прибыли.
курсовая работа [678,7 K], добавлен 03.04.2011Особенности метода ветвей и границ как одного из распространенных методов решения целочисленных задач. Декомпозиция задачи линейного программирования в алгоритме метода ветвей и границ. Графический, симплекс-метод решения задач линейного программирования.
курсовая работа [4,0 M], добавлен 05.03.2012Изучение экстремальных задач и поиск их решений. Выбор метода решения и приведения задачи к каноническому виду и к задаче линейного программирования. Метод искусственного базиса. Модифицированный симплекс-метод. Написание программы на языке С++Builder 6.
курсовая работа [343,0 K], добавлен 28.11.2010Постановка задач линейного программирования. Примеры экономических задач, сводящихся к задачам линейного программирования. Допустимые и оптимальные решения. Алгоритм Флойда — алгоритм для нахождения кратчайших путей между любыми двумя узлами сети.
контрольная работа [691,8 K], добавлен 08.09.2010Общие задачи линейного программирования. Описание алгоритма симплекс-метода, записанного в канонической форме с односторонними ограничениями. Алгоритм построения начального опорного плана для решения задачи. Расширенный алгоритм искусственного базиса.
курсовая работа [142,9 K], добавлен 24.10.2012Оптимизационные исследования задач линейного и нелинейного программирования при заданных математических моделях. Решение задач линейного программирования и использование геометрической интерпретации и табличного симплекс-метода, транспортная задача.
курсовая работа [408,7 K], добавлен 13.06.2019Теоретическая основа линейного программирования. Задачи линейного программирования, методы решения. Анализ оптимального решения. Решение одноиндексной задачи линейного программирования. Постановка задачи и ввод данных. Построение модели и этапы решения.
курсовая работа [132,0 K], добавлен 09.12.2008Описание симплекс метода решения задачи линейного программирования. Решение задачи методом Литла на нахождение кратчайшего пути в графе, заданном графически в виде чертежа. Из чертежа записываем матрицу расстояний и поэтапно находим кратчайший путь.
задача [390,4 K], добавлен 10.11.2010Постановка задачи линейного программирования. Решение системы уравнений симплекс-методом. Разработка программы для использования симплекс-метода. Блок-схемы основных алгоритмов. Создание интерфейса, инструкция пользователя по применению программы.
курсовая работа [1,7 M], добавлен 05.01.2015Разработка программы, решающей базовую задачу линейного программирования симплекс-методом с помощью симплекс-таблиц. Выбор языка программирования и среды разработки, программные модули и их взаимодействие между собой. Листинг разработанной программы.
курсовая работа [415,8 K], добавлен 08.09.2013Методы определения оптимального плана производства (приобретения) продукции с учетом ограниченного обеспечения ресурсами различного вида. Технология поиска оптимального решения задач линейного программирования (ЗЛП) с помощью итоговой симплекс-таблицы.
лабораторная работа [42,8 K], добавлен 11.03.2011Особенности задач линейного программирования. Симплексный метод решения задач линейного программирования. Обоснование выбора языка, инструментария программирования, перечень идентификаторов и блок-схема алгоритма. Логическая схема работы программы.
дипломная работа [2,4 M], добавлен 13.08.2011Широкое применение вычислительной техники как в общей математике, так и в одном из её разделов – математических методах. Ознакомление с решением задач линейного программирования симплекс-методом и графически. Составлена программа на языке Delphi.
курсовая работа [57,1 K], добавлен 04.05.2010Графический метод как наиболее простой и наглядный метод линейного программирования, его сущность и содержание, особенности применения на современном этапе. Этапы реализации данного метода. Описание интерфейса разработанного программного продукта.
контрольная работа [318,0 K], добавлен 11.06.2011Построение математической модели. Выбор, обоснование и описание метода решений прямой задачи линейного программирования симплекс-методом, с использованием симплексной таблицы. Составление и решение двойственной задачи. Анализ модели на чувствительность.
курсовая работа [100,0 K], добавлен 31.10.2014
