некоторые нецелочисленные точки. Он существенно использует известную

симплексную процедуру. Отправной точкой для решения задачи 1-4 является

решение ее непрерывного аналога, т.е. ЗЛП без учета целочисленности. Если

получаемый в результате оптимальный план содержит только целые компоненты, то

автоматически получается ЗЦЛП. В противном случае в системе ограничений

задачи д/б добавлено такое ограничение, для которого:

1)найденный нецелочисленный оптимальный план не удовлетворяет вновь

добавляемому ограничению,

2)любой допустимый целочисленный план задачи 1-4 удовлетворяет вновь

добавляемому ограничению

10. Основные понятия теории игр.

Игрой называется математическая модель конфликтной ситуации.Стороны, участвующие

в конфликте называются участниками игры или игроками, а исход

конфликта-выигрыш.В систему условий, регламентирующих возможные варианты

действия сторон, объем информации каждой стороны о поведении другой, а также

результат, к которому приводит данная совокупность действий составляет правила

игры. Игра состоит из ходов. Причем под ходом понимается выбор одного из

предусмотренных правилами игры действий. Ходы бывают личные и случайные.

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

ходом называется выбор и осуществление одного из предписанных правилами игры

действия, которое производится не самим игроком, а некоторым механизмом

случайного выбора. Для каждого случайного хода аправила игры определяют

распределение ероятностей возможных исходов. Возможное для игрока действие

называют стратегией. Стратегия называется оптимальной, если она при

многократном повторении игры обеспечивает игроку максимальную возможность

среднего выигрыша. Заинтересованность игроков в ситуации проявляется в том, что

каждому игроку I в каждой ситуации

приписывается число, выражающее степень удовлетворения его интересов в этой

ситуации. Это число называется выигрышом игрока I в ситуации

и обозначается через H(

). Если число стратегий у каждого игрока конечно, то игра называется крнечной.

Если у игрока А m-стратегии, а у игрока В n-стратегии, то игра называется игрой

M×N. В общем виде постановка задачи теории игр производится следующим

образом. Имеется некоторая операция,в которой участвуют 2 игрока А и В с

противоположными интересами. Имеются правила, регламентирующие результаты, к

которым приводят возможные варианты действий игроков. Результаты действий

выражены в количественной форме и обозначены

(математическое ожидание выигрыша игрока А, сделавшего свой i-ый ход при j-ом

ходе игрока В. Тогда целью теории игр является выработка оптимальных для

игроков стратегий, которые при многократном повторении игры обеспечивают

максимально возможный выигрыш и минимально возможный средний проигрыш.

Рассмотрим конечную игру m×n, в которой игрок А имеет m-стратегию (а1,а2,

. . .аn), а игрок В n-стратегию(b1,b2, .bn). Если игроки используют только

личные ходы, то выбор стратегии А и В однозначно определяет

, т.е. число, характеризующее выигрыш игрока А при проигрыше игрока В. Причем

может быть и положительным и отрицательным. Будем считать, что при

≥0 игрок аА выигрывает, а игрок В проигрывает величину

.Если < 0, то

выигрывает игрок В и проигрывает игрок А. В этом случае вместо проигрыша

говорят об отрицательном выигрыше игрока А. Если в игре используют случайные

ходы, то выигрыш при 2 стратегии ai и aj является случайным. В этом случае за

оценку ожидания выирыша берется его мат.ожидание. Предположим, что нам известны

все значения в

игре m×n. Эти значения запишем в виде таблицы, называемой платежной

матрицей. Строки матрицы соответствуют стратегии ai, а столбцы – стратегии aj.

Построение платежной матрицы не всегда просто, поскольку количество

стратегий m,n могут оказаться очень большими. Однако любая конечная игра

может быть приведена к матричному виду.

Игры с нулевой суммой относят к классу антогонистических игр.

Среди всех чисел ai выберем наибольшее:

{}. Число а

называется нижней ценой игры. Это гарантированный выигрыш игрока А при любой

стратегии игрока В.

Среди всех чисел выберем наименьшее. Это гарантированный проигрыш игрока В.

Фактический выигрыш игрока А при разумных действиях партнеров ограничен нижней и

верхней ценой игры. Если верхняя и нижняя цены игры совпадают, то общее

значение верхней и нижней цены игры

называется ценой игры. В эом случае игра называется вполне определенной или

игрой с Седловой точкой. Седловой точкой называется элемент платежной матрицы,

одновременно мин в своей строке и макс в своем столбце. Седловой точке

соответствуют оптимальные стратегии игроков Ai и Bj, их совокупность – это

решение игры, которое обладает следующим свойством: если один из игроков

придерживается своей оптимальной стратегии, то для другого отклонение от его

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

в чистых стратегиях.

11. принципы составления платежной матрицы. Примеры.

Пример 1.

Командир В охраняет город 5-ю ротами. К городу ведут 2 дороги, по которым

может подойти противник, имеющий 4 роты под командованием А. В может

приказать любой из 5 рот оборонять любую дорогу. А выигрывает, если на какой-

нибудь дороге у него будет больше рот, чем у В. Как должен распорядиться

ротами А, чтобы обеспечить себе максимальный шанс прорваться в город?

Решение:

Выигрыш игрока А обозначим через +1, проигрыш через -1. Из условия задачи

получим таблицу, в которой в символе 0-4 первая цифра показывает число рот на

1 дороге, а 2-ая - на 2 дороге. То же для командира В.

	0-5	1-4	2-3	3-2	4-1	5-0
0-4	-1	-1	-1	-1	1	1
1-3	1	-1	-1	-1	1	1
2-2	1	1	-1	-1	1	1
3-1	1	1	1	-1	-1	1
4-0	1	1	1	1	-1	-1

Пример 2.

Игрок А выбирает число из множества 1,2,3, а игрок В из 1,2,3,4. Если при

этом получается четное число, то эту сумму выигрывает А. Если же получится

нечетное число, то В.

Какое число должен выбрать игрок А, чтобы обеспечить себе макс. выигрыш. Или,

если это невозможно, то это мин. выигрыш.

Составим матрицу.

	1	2	3	3	αi
1	+2	-3	+4	-5	-5
2	-3	+4	-5	+6	-5
3	4	-5	+6	-7	-7
βi	4	4	6	6

Β=4

-5<= v <=4

13. Игрой называется математическая модель конфликтной ситуации. Стороны,

участвующие в конфликте, называют участниками игры или игроками, а исход

конфликта- выигрышем. Игра ведется по определенным правилам, которые

представляют собой систему условий, регламентирующих возможные действия

игроков.

Ходом называется выбор одного из предложенных правилами игры действий и его

осуществление. Стратегией наз-ся совокупность правил, определяющих выбор его

действий при каждом личном ходе в зависимости от сложившейся ситуации.

Для того чтобы найти решение игры следует для каждого игрока выбрать

стратегию которая удовлетворяет условию оптимальности, т.е. один из игроков

должен получить максимальный выигрыш, когда второй придерживается своей

стратеги. Такие стратегии наз-ся оптимальными, любому игроку невыгодно

отказаться от своей стратегии в игре.

Если игра не имеет Седловой точки, то применении чистых стратегий не дает

оптимального решения игры. В таком случае можно получить оптимальное решение,

случайным образом чередуя чистые стратегии.

Смешенной стратегией SA игрока А наз-ся применение чистых стратегий

А1,А2,..Аi,.Am с вероятностями р1,р2,..рi

.pm, причем Sрi=1. Смешенные стратегии игрока А

записываются в виде матрицы:

SA=[A1 A2 ...Ai.Am]

p1 p2..pi.pm

или в виде строки SA=(p1,p2,,,,,pi.pm).

Аналогично смешенные стратегии игрока В обозначаются

SB= [B1 B2 ..Bj,,,,,,,Bn]

Q1 q2,,,,,qj ..qn

Или SB =(q1 q2 ..qj..qn) где Sqj=1

Чистая стратегия, которая входит в оптимальную смешенную стратегию с отличной

от нуля вероятностью, называется активной.

Если один из игроков придерживается своей оптимальной смешенной стратегии, то

выигрыш остается неизменным и равным цене игры v , если игры удовлетворяют

неравенстве alfa £v£betta.

Рассмотрим игру, заданную платежной матрицей:

Р= а11 а12.а1n

а21 а22.а2n

.......

аm1 am2..amn

Если такая игра имеет седловую точку, то оптимальное решение игры- это пара

чистых стратегий, соответствующей это точке.

Предположим что игра не имеет Седловой точки. Найдем ее решение в смешенных

стратегиях SA= (p1,p2.,pi.pm) и SB

=(q1,q2,.qj.qn)

Применение игроком А оптимальной стратегии SA должно обеспечивать ему

при любых действиях игрока В выигрыш не менее цены игры v. Поэтому выполняются

след. соотношения:

Spiaij³v,i=1,2..n причем Spi=1

Аналогично для игрока В оптимальная стратегия SB должна обеспечить

при любых стратегиях игрока А проигрыш, не превышающий величину v

,т.е.справедливо соотношение:

Sqjaij£v, i=1,2,.m,где Sqj=1

j

Для решения этих задач используют методы линейного программирования.

14. В некоторых случаях успех экономической деятельности зависит не от

сознательно противодействующего конкурента, а от объективной

действительности, которую принято называть «природой».

Пусть игрок А располагает m стратегиями, которые обозначим А1,А2,.,Аm, а

относительно «природы» известно, что она может принимать n различных

состояний, обозначим их Р1,Р2,.,Рn.

Известен также выигрыш аij игрока А при каждой паре стратегий игрока

и «природы», т.е. известна платежная матрица:

Р= а11 а12..а1n

а21а22...а2n

......

аm1 аm2..аmn

Игрок А в играх с №природой» старается действовать осмотрительно, используя

стратегию, позволяющую получить наибольший выигрыш (наименьший проигрыш).

Страницы: 1, 2, 3, 4, 5