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

Пример 1.

Командир В охраняет город 5-ю ротами. К городу ведут 2 дороги, по которым может подойти противник, имеющий 4 роты под командованием А. В может приказать любой из 5 рот оборонять любую дорогу. А выигрывает, если на какой-нибудь дороге у него будет больше рот, чем у В. Как должен распорядиться ротами А, чтобы обеспечить себе максимальный шанс прорваться в город?

Решение:

Выигрыш игрока А обозначим через +1, проигрыш через -1. Из условия задачи получим таблицу, в которой в символе 0-4 первая цифра показывает число рот на 1 дороге, а 2-ая - на 2 дороге. То же для командира В.

Пример 2.

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

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

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

Β=4

-5<= v <=4

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

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

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

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

Смешенной стратегией S_A игрока А наз-ся применение чистых стратегий А1,А2,….А_i,…A_m с вероятностями р1,р2,….р_i…p_m, причем Sр_i=1. Смешенные стратегии игрока А записываются в виде матрицы:

S_A=[A1 A2 …..A_i…A_m]

p1 p2……p_i…p_m

или в виде строки S_A=(p1,p2,,,,,p_i…p_m).

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

S_B= [B1 B2 ….B_j,,,,,,,B_n]

Q1 q2,,,,,q_j ….q_n

Или S_B =(q1 q2 ….q_j….q_n) где Sq_j=1

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

Если один из игроков придерживается своей оптимальной смешенной стратегии, то выигрыш остается неизменным и равным цене игры v, если игры удовлетворяют неравенстве alfa £v£betta.

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

Р= а11 а12…а1n

а21 а22…а2n

……………..

аm1 am2….amn

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

Предположим что игра не имеет Седловой точки. Найдем ее решение в смешенных стратегиях S_A= (p1,p2…,p_i…p_m) и S_B=(q1,q2,…q_j…q_n)

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

Sp_ia_ij³v,i=1,2….n причем Sp_i=1

Аналогично для игрока В оптимальная стратегия S_B должна обеспечить при любых стратегиях игрока А проигрыш, не превышающий величину v,т.е.справедливо соотношение:

Sq_ja_ij£v, i=1,2,…m,где Sq_j=1

j

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

14. В некоторых случаях успех экономической деятельности зависит не от сознательно противодействующего конкурента, а от объективной действительности, которую принято называть «природой».

Пусть игрок А располагает m стратегиями, которые обозначим А1,А2,…,Аm, а относительно «природы» известно, что она может принимать n различных состояний, обозначим их Р1,Р2,…,Рn.

Известен также выигрыш а_ij игрока А при каждой паре стратегий игрока и «природы», т.е. известна платежная матрица:

Р= а₁₁ а_12……а_1n

а₂₁а_22…….а_2n

…………..

а_m1 а_m2……а_mn

Игрок А в играх с №природой» старается действовать осмотрительно, используя стратегию, позволяющую получить наибольший выигрыш (наименьший проигрыш). «Природа» (игрок Р) действует случайно, возможные стратегии определяются как ее состояние (погода, спрос на определенную продукцию, сочетание производственных факторов).

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

Риском игрока А при использовании стратегии А_i при состоянии «природы» Р_j называется разность между выигрышем, который он получил бы, если бы знал Р_j и выигрышем, который он получит в обычных условиях, применяя стратегию А_i:

r_ij= Betta_j- alfa_ij,где Betta_j= max{alfa_i}

i

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

Критерий Бейеса- Лапласа.

При известном распределении вероятностей различных состояний природы Р= (р1,р2,…р_n) где р1+р2+…рn=1, критерием принятия решений яв-ся максимум математического ожидания выигрыша, т.е.

V_B-L= max Sa_ijp_j где i=1,2,…m

i j

Критерий Лапласа.

Если ни одно из состояний «природы» нельзя предпочесть другим, выдвигают гипотезу о том, что все они равновероятны: р1=р2=рn=1/n

Тогда V_L=maxSa_ij1/n

i j

максиминный критерий Вальда.

Он основан на выборе стратегии игрока А, позволяющей гарантировать ему получение нижней цены игры:

V_w=max min a_ij

i j

Критерий минимального риска Сэвиджа.

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

V_s=min max r_il

i j

Критерий Вальда и Сэвиджа основаны на пессимистической оценке обстановки. В отличии от них следующий критерий использует как пессимистический, так и оптимистический подход к ситуации.

Критерий Гурвитца.

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

V_H= max {lmin a_ij+ (1-l)max a_ij}

i j j

Если l=1, критерий Гурвитца превращается в пессимистический критерий Вальда. При l=0 в критерии крайнего оптимизма, рассчитанный на наилучшее стечение обстоятельств. Обычноl принимают в пределах от 0,5 до 0,7

Основные понятия теории СМО.

При исслед-ии операций часто приходится сталкиваться с системами предназначеннемыми для многоразового использования при решении однотипных задач, возникающих при этом процессы получили название процессов обслуживание, а системы – системы массового обслуживания. Примерами таких систем являются: телефонные системы, ремонтные мастерские,вычислительные комплексы,билетные,кассы,магазины, парикмахерские и т.п. каждое СМО состоит из определенного числа обслуживающих единиц: приборы,устройства,пункты,станции, к-ые будем называть каналами обслуживания. Каналами могут быть линии связи,рабочие точки,вычислительные миашины,продавцы и т.д. по числу каналов СМО подразделяют на одноканальные и многоканальные. Заявки поступают в СМО обычно не регулярно, образуя так называемый случайный поток требований. Обслуживание заявки также продолжается какое-то случайное время. Случайный характер истока заявок и времени обслуживания приводит к тому, что СМО оказывается загруженной неравномерно; какие-то периоды времени скапливается очень большое количество заявок(они либо становятся в очередь, либо покидают СМО необслуженными). Другие же периоды СМО работает с недогрузкой или простаивает. Предметом теории массового обслуживание является построение математических моделей, связывающих заданные условия работы СМО(число каналов их производителей потоков заявок и т.п.), показатели эффективности СМО, описывающие ее способность справляться с потоком заявок. В качестве показателей эффективности СМО исп-ся: среднее число заявок, обслуживаемых единиц времени, среднее число заявок в очереди, среднее время ожидания обслуживания, вероятность отказа обслуживания без ожидания вероятности того, что число заявок в очереди превысит опред. значение и т.п. СМО делят на 2 осн типа: 1) СМО с отказами; 2) СМО с ожиданием(очереди). СМО с отказами – заявка, поступившая в момент, когда все каналы заняты, получает отказ, покидает СМО и в дальнейшем в процессе обслуживания не участвует(напр. Заявка на телеф разговор в момент, когда все каналы заняты, получает отказ и покидает СМО необслуженным). СМО с ожиданием – заявка, пришедшая в момент, когда все каналы заняты, не уходят, а становится в очередь на обслуживание. СМО с ожиданием подразделяется на разные виды, в зависимости от того, как организована очередь: с ограниченной или неограниченной длинной очередью и с ограниченным временем ожидания и т.п. для классификации СМО важное значение имеет дисциплина обслуживания, определяющая порядок выбора заявки из числа поступивших и порядок распределения их между свободными каналами. По этому признаку обслуживания заявки может быть организовано по принципу: «первая пришла - первая обслужена, последняя пришла – первая обслужена». Такой порядок может применятся, напр., при извлечении для обслуживания изделий со склада (ибо последнее из них оказывается часто более доступным) или обслуживание с приоритетом (когда в первую очередь обслуживаются наиболее важные заявки). Приоритет может быть как абсолютным, когда более важная заявка «вытесняет» из-под обслуживания обычную заявку (напр., в случае аварийной ситуации плановой работы ремонтных бригад прерывается до ликвидации аварии), так и относительным, когда более важная заявка получает лишь лучшее место в очереди.