Алготирм симплекс-метода с помощью симплексных таблиц.

Алготирм симплекс-метода с помощью симплексных таблиц.

 

 

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

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

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

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

1.Анализ сокращения или увеличения ресурсов:

• на сколько можно увеличить (ограничения типа ≤) запас

дефицитного ресурса для улучшения оптимального значения ЦФ?

• на сколько можно уменьшить (ограничения типа ≤) запас

недефицитного ресурса при сохранении оптимального значения ЦФ?

2. Увеличение (ограничения типа ≤) запаса какого из ресурсов

наиболее выгодно?

3. Анализ изменения коэффициентов ЦФ: каков диапазон изменения

коэффициентов ЦФ, при котором не меняется оптимальное решение?

 

Антагонистические игры и их свойства.

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

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

Пример. Рассмотрим игру, в которой участвуют два игрока и каждый из них имеет по две стратегии. Выигрыши игроков определяются следующими правилами: в том случае если оба игрока независимо друг от друга выбирают стратегии с одинаковыми номерами (первый игрок - первую и второй игрок - первую или первый игрок - вторую и второй игрок - вторую), то первый игрок выигрывает рубль, а второй проигрывает рубль. В том случае, если оба игрока выбирают разные стратегии (первый игрок - первую, а второй игрок вторую - или первый игрок - вторую и второй игрок - первую), то первый игрок проигрывает рубль, а второй выигрывает рубль. В этом случае биматрица выигрышей игроков будет иметь вид:

Таблица 2.1. Биматрица выигрышей.

	Стратегии II-го игрока
Стратегии 1-го игрока

Таблица 2.2 Биматрица выигрышей

	Стратегии II-го игрока
Стратегии 1-го игрока		(+1;-1)	(-1;+1)
	(-1;+1)	(+1;-1)

 

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

Из-за этого свойства антагонистические игры называют играми с нулевой суммой.

В этих играх выполняется соотношение:

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

 

Вектор Шепли.

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

вектор-функция

Вектор Шепли удовлетворяет следующим свойствам(аксиомы):

1. Линейность. Отображение Φ(v) представляет собой линейный оператор, то есть для любых двух игр с характеристическими функциями v и w

Φ(v + w) = Φ(v) + Φ(w);

и для любой игры с характеристической функцией v и для любого α

Φ(αv) = αΦ(v).

2. Симметричность. Получаемый игроком выигрыш не зависит от его номера. Это означает, что если игра w получена из игры v перестановкой игроков, то ее вектор Шепли Φ(w) есть вектор Φ(v) с соответствующим образом переставленными элементами.

3. Аксиома болвана. Болваном в теории кооперативных игр называется бесполезный игрок, не вносящий вклада ни в какую коалицию, то есть игрок i,такой что для любой коалиции K, содержащей i, выполнено:

Аксиома болвана состоит в том, что если игрок i — болван, то Φ(v)i = 0.

4. Эффективность. Вектор Шепли позволяет полностью распределить имеющееся в распоряжении тотальной коалиции благосостояние, то есть сумма компонент вектора Φ(v) равна v(N).

Кооперативные игры.

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

Обозначим через N множество всех игроков, причем игроков принято различать по их номерам, т.е. N={1,2,...,n}, а через S – любое его подмножество, которое является коалицией. Очевидно, что число коалиций, состоящих из k игроков, равно числу сочетаний из n по k, то есть , а число всевозможных коалиций равно

Из этой формулы видно, что число всевозможных коалиций значительно растёт в зависимости от количества n всех игроков в данной игре. Образовав коалицию, множество игроков S действует как один игрок против остальных игроков, и выигрыш этой коалиции зависит от применяемых стратегий каждым из n игроков. Общность интересов игроков из S означает, что выигрыш объединенного игрока есть сумма выигрышей составляющих его игроков из S.

Пусть игроки из N, образуя различные коалиции, могут получать некоторые сравнимые между собой выигрыши. Обозначим выигрыш, который может уверенно обеспечить себе коалиция S ⊂ N, через V(S). Функция V, ставящая в соответствие каждой коалиции S наибольший уверенно получаемый ею выигрыш V(S), называется характеристической функцией.

Если для всех непересекающихся подмножеств А и В выполняется неравенство V(A ∪ B) ≥ V(A) + V(B) (1), то характеристическая функция является супераддитивной. Свойство супераддитивности означает, что если нет ни одного игрока, который входил бы одновременно в обе коалиции А и В, то коалиция, составленная как объединение этих двух подмножеств, будет иметь выигрыш не меньший, чем сумма выигрышей А и В. Предположение о супераддитивности является вполне логичным, т.к. создание коалиций было бы бессмысленным, если бы величина выигрыша уменьшалась с увеличением числа участников коалиции.

Игра называется существенной в том случае, если

Содержательно выполнение этого неравенства означает, что если игра является существенной, то при объединении всех участников конфликта возникает дополнительный выигрыш:

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

Игра называется несущественной в том случае, если вместо этого неравенства выполняется равенство:

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

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

16.Линейное программирование как метод оптимального планирования.

В настоящее время для решения оптимальных задач применяют в основном следующие методы:

· методы исследования функций классического анализа;

· методы, основанные на использовании неопределенных множителей Лагранжа;

· вариационное исчисление;

· динамическое программирование;

· принцип максимума;

· линейное программирование;

· нелинейное программирование.

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

Для решения большого круга задач линейного программирования имеется практически универсальный алгоритм - симплексный метод, позволяющий за конечное число итераций находить оптимальное решение подавляющего большинства задач. Тип используемых ограничений (равенства или неравенства) не сказывается на возможности применения указанного алгоритма. Дополнительной проверки на оптимальность для получаемых решений не требуется. Как правило, практические задачи линейного программирования отличаются весьма значительным числом независимых переменных. Поэтому для их решения обычно используют вычислительные машины, необходимая мощность которых определяется размерностью решаемой задачи.

17.Метод наименьшей стоимости, распределительный метод оптимального планирования.

При использование метода наименьших затрат, выбирается клетка с наименьшими затратами на транспортировку единицы товара. Если такие клеток несколько, то из них необходимо выбрать ту, которая соответствует наименьшей поставке. Заполняем эту клетку, вписав в нее требуемое значение единиц товара.

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

Метод потенциалов.

Существующий алгоритм решения транспортных задач (метод потенциалов) предполагает, что ЦФ стремится к минимуму. Однако существуют ситуации, когда в рамках транспортной модели требуется максимизировать ЦФ, например, общий доход, объем продаж, прибыль, качество выполняемых работ и т.д. В этом случае в модель вместо искомой ЦФ L(X) водится ЦФ L1(X)= −L(X,) в которой тарифы умножаются на (-1). Таким образом, максимизация L(X) будет соответствовать минимизации L1 (X).

 

Оптимизационные модели.

Оптимизационные модели – это модели, предполагающие нахождение экстремума (минимума или максимума) целевой функции цели оптимизации, при заданной системе ограничений на целевую функцию. Например, целевой функцией может быть максимизацию прибыли предприятия при ограничениях на наличие трудовых ресурсов (материальных, трудовых, финансовых).

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

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

В общем виде схема построения математической оптимизационной модели состоит из следующих этапов:

Этап 1. Выбор и обозначение переменных задачи.

Этап 2. Представление целевой функции задачи (способ расчета значений критерия эффективности задачи).

Этап 3. Представление ограничений задачи.

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

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

 

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

Математическим описанием конфликтных ситуаций занимается тео­рия игр. Не цель - выработка рекомендаций по разумному поведению участников конфликта.

Каждая конкретная конфликтная ситуация очень сложна. Чтобы сделать возможным математический анализ конфликта, отбрасываются несущественные факторы и строится ма­тематическая модель, которую называют игрой. Стороны, участвующие в конфликте, называются игроками, исход игры называется выигрышем. Oт реального конфликта игра отличается наличием формальных правил. Правила устанавливают возможные варианты действий игроков и исход игры, то есть выигрыш или проигрыш участников в зависимости от сложившейся обстановки. Будем считать, что выигрыши участников имеют количественное выражение.

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

Игра называется игрой с нулевой суммой, если выигрыш одной стороны равен проигрышу другой.

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

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

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

Понятие дележа.

Дележ – это результат соглашения игроков, он является решением игры.

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

Так же понятие дележа широко используется и в С-ядро, там множество недоминируемых дележей кооперативной игры называется С – ядром.

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

Пример содержательной постановки задач, сводящихся арбитражной схеме.

Три фирмы, занимающиеся перевозкой грузов в различных регионах с помощью автотранспортных средств, обратились к консультационной фирме (арбитру) с просьбой определить возможную прибыль каждой из них в том случае, если они объединятся. При этом все три фирмы, занимающиеся перевозкой грузов, обязались предоставить арбитру всю информацию, необходимую для проведения расчетов.

В соответствии с полученной информацией было установлено, что: П₁=V(1)=600 тыс. руб. - прибыль, которую первая фирма стабильно получает на протяжении последнего времени;

П₂=V(2)=700 тыс. руб. - прибыль, которую вторая фирма стабильно получает на протяжении последнего времени;

П₃=V(3)=900 тыс. руб. - прибыль, которую третья фирма стабильно получает на протяжении последнего времени.

На основании проведенных расчетов стало известно, что:

• при объединении первой и второй фирм их совместная прибыль составит П_1,2=V(1, 2)=1300 тыс. руб.,

• при объединении первой и третьей фирм их совместная прибыль составит П_1,3=V(1, 3)=1500 тыс. руб.,

• при объединении второй и третьей фирм их совместная прибыль составит П_2,3=V(2, 3)=2100 тыс. руб.,

• при объединении первой, второй и третьей фирм их совместная прибыль составит П_1,2,3=V(1, 2, 3) = 2700 тыс. руб.

В рассматриваемой задаче:

• игроками являются фирмы, имеющие намерение объединиться;

• количество участников рассматриваемого неантагонистического конфликта равно трем игрокам (n=3);

• V(S)=П(S), так как значение характеристической функции V определяется той возможной прибылью, которую могут получить транспортные фирмы, образуя различные коалиции S;

• область определения характеристической функции состоит из 2³ возможных подмножеств S.

Докажем, что в рассматриваемой нами игре существует «болван»:

• V(2,1)=V(2Èl)=1300, V(2)+V(1)=700+600=1300, следовательно, V(2Èl)=V(2)+V(l);

• V(3, l)=V(3Èl)=1500, V(3)+V(l)=900+600=1500, следовательно, V(3Èl)=V(3)+V(l);

• V(2,3)=V(2È3), V(2)+V(3)=700+900=1600, следовательно, V(2È3)>V(2)+V(3);

• V(2, 3, l)=V(2È3Èl)=2700, V(2È3)+V(1)=2100+600=2700, следовательно, V(2È3È1)=V(2È3)+V(l).

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

«Носителем» игры в данном случае являются 2-ой и 3-ий игроки, так как Т=N\B.

 

Пример содержательной постановки задач, сводящихся кооперативной игре.

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

• у скрипача - 600 руб.;

• у гитариста - 700 руб.;

• у певицы - 900 руб.

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

· совместное выступление скрипача и гитариста приносит им 1500 руб.;

· совместное выступление скрипача и певицы приносит им 1800 руб.;

· совместное выступление гитариста и певицы приносит им 1900 руб.;

· совместное выступление всех троих - скрипача, гитариста и певицы приносит им 3000 руб.

Необходимо определить, выгодно ли им объединять свои усилия и если да, то на каких условиях? Ответить на этот вопрос можно, применяя формализованный аппарат теории кооперативных игр.

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

В нашем примере n=3, следовательно, область определения характеристической функции состоит из 2³ = 8 возможных подмножеств множества I.

Возможными коалициями S в данном случае могут быть:

· одноэлементные коалиции, т.е. коалиции, состоящие из одного игрока-музыканта: S{1}, S{2}, S{2};

· двухэлементные коалиции: S{1,2}, S{1, 3}, S{2, 3};

· трехэлементная коалиция S{ 1,2,3}.

Присвоим каждому из игроков соответствующий порядковый номер:

• скрипач - 1-ый игрок;

• гитарист - 2-ой игрок;

• певица - 3-ий игрок.

На основе имеющихся данных определим значения характеристической функции игры V:

V(S{1})=600 руб.; V{S{2})=700 руб.; V(S{3})=900 руб.; эти значения характеристической функции определяются соответственно выигрышами первого, второго и третьего игроков, когда каждый из них выступает в одиночку, не кооперируясь ни с кем из своих друзей-музыкантов;

V(S{1, 2})=1500 руб.; V(S{1, 3})=1800 руб.; V(S{2, 3})=1900 руб.; эти значения характеристической функции определяются средним общим заработком за вечер, который могут обеспечить себе студенты, выступая попарно, т.е. образуя соответствующие парные коалиции (скрипач - гитарист S{1, 2}, скрипач - певица S{1,3}, гитарист - певица S{2, 3});

V(S{1, 2, 3})=3000 руб.; это значение характеристической функции определяется средним общим за вечер заработком, который могут обеспечить себе студенты, выступая втроем, т.е. образуя в данном случае максимально большую коалицию I, состоящую из трех игроков (певицы, скрипача и гитариста).

Число подмножеств, на которых определена характеристическая функция V, равно 2ⁿ=2³=8. Это число в рассматриваемом нами примере складывается из трех одноэлементных коалиций, трех двухэлементных коалиций, одной трехэлементной коалиции и пустого множества, при котором V(Æ)=0.

Очевидно, что, прежде чем объединяться, игрокам необходимо понять, выгодно ли им это с точки зрения увеличения выигрыша.

Проиллюстрируем выполнение свойства супераддитивности в рассматриваемом нами примере. Прежде всего определим, каким образом формируются непересекающиеся коалиции S и Т. Если часть игроков из I входит в коалицию S, то все другие игроки образуют коалицию Т, так как по определению эта коалиция формируется как I\S. Соответственно, если S представляет собой одноэлементную коалицию, состоящую из первого игрока, то в коалицию Т войдут второй и третий игроки, если же в коалицию S войдут первый и третий игроки, то коалиция Т будет состоять только из второго игрока, и т.д.

Определим, обладает ли характеристическая функция рассматриваемой нами игры свойством супераддитивности.

V(S{1})+V(S{2, 3})<V(SÈT)=V(I), 600+1900=2500<3000,

V(S{2})+V{S{1, 3})<V(SÈT)=V(I), 700+1800=2500<3000,

V(S{3})+F(S{1, 2})<V{SÈT)=V(I), 900+1500=2400<3000.

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

Наличие свойства супераддитивности говорит о целесообразности объединения игроков с точки зрения увеличения выигрыша.

Определим, является ли рассматриваемая нами игра существенной.

600+700+900=2200, V(I) = 3000,

т.е. выполняется неравенство: V(i), значит, рассматриваемая нами игра является существенной, следовательно, ее решение нужно искать среди множества недоминируемых дележей.

Примеры содержательных постановок задач, сводящихся к антагонистическим играм.

Предположим, что предприятие может выпускать четыре вида продукции: A₁, A₂, A₃, А₄, получая при этом прибыль. Ее величина определяется состоянием спроса, который может находиться в одном из трех возможных состояний: В₁ В₂, B_3.

Таблица 2.8.3 Прибыль предприятия при различных состояниях спроса

Виды продукции	Возможные состояния спроса
В1	В2	B3
A1
А2
А3
А4

Элементы матрицы H¢=||h¢_ij|| характеризуют величину прибыли, которую получит предприятие, если будет выпускать i-й вид продукции (i=1,2,3,4) при j-ом состоянии спроса (j=1,2,3,4).

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

Эта задача может быть сведена к антагонистической игре.

В данном случае в качестве первого игрока выступает предприятие, а в качестве второго - природа, которая влияет на состояние спроса.

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

Выступая в качестве первого игрока, предприятие может использовать четыре стратегии:

• первую чистую стратегию, соответствующую выпуску предприятием только продукции А₁

• вторую чистую стратегию, соответствующую выпуску предприятием только продукции А₂

• третью чистую стратегию, соответствующую выпуску предприятием только продукции А₃,

• четвертую чистую стратегию, соответствующую выпуску предприятием только продукции А₄.

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

• первую чистую стратегию, при которой реализуется состояние спроса B₁

• вторую чистую стратегию, при которой реализуется состояние спроса В₂;

• третью чистую стратегию, при которой реализуется состояние спроса В₃.

Задана платежная матрица Н¢ этой игры:

H¢=

Анализ платежной матрицы показывает, что первая стратегия первого игрока доминирует его последнюю – четвертую - стратегию (каждый из элементов первой строки матрицы больше соответствующего элемента последней строки матрицы), следовательно, вероятность использования четвертой стратегии первым игроком равна нулю.

Из проведенного анализа следует, что размерность матрицы H¢ можно уменьшить, убрав из нее четвертую строку, в результате платежная матрица может быть сведена к матрице H:

H=

Проверим, имеет ли данная игра седловую точку. Найдем верхнюю и нижнюю цену игры:V_Ù=max_imin_jh_ij=2, V^Ù=min_jmax_ih_ij=4.

Так как нижняя цена игры не равна верхней, то эта антагонистическая игра не имеет седловой точки, следовательно, ее решение нужно искать в смешанных стратегиях.

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

Задача второго игрока Задача первого игрока
Целевая функция
F(x)=x1+х2+x3®max	Z(y)=y1+y2+y3®min
Функциональные ограничения
4х1+2х2+2х3≤1 2x1+5х2≤1 2x2+5х3≤1	4y1+y2≥1 2y1+5y2+2y3≥1 2y1+5y2≥1
Прямые ограничения
x1≥0 x2≥0 x3≥0 y1≥0 y2≥0 y3≥0

Смешанные стратегии.

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

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

Смешанная стратегия первого игрока задается m-мерным вектором Р = (р₁, р₂, р₃,…., p_m), где p_i - вероятность выбора первым игроком стратегии i, при этом p_i≥0, так как вероятности не могут быть отрицательными, и

Смешанная стратегия второго игрока задается n-мерным вектором Q=(q₁, q₂,q₃,, q_n) где q_j - вероятность выбора вторым игроком стратегии j, при этом q_j≥0, так как вероятности не могут быть отрицательными, и .

Пример. Вектор (1/3, 1/3, 0, 0,..., 0, 1/3) соответствует смешанной стратегии, при которой первый игрок применяет первую, вторую и последнюю (m-ю) стратегии, используя их с вероятностью 1/3, а остальные стратегии - с нулевыми вероятностями. Из вышесказанного можно сделать вывод, что чистые стратегии игроков являются частным случаем их смешанных стратегий:

• чистую i-ю стратегию первого игрока можно представить как m мерный вектор p=(0, 0,..., 0, 1, 0,..., 0), i-ая компонента которого равна 1, а остальные нулю;

• чистую j-ю стратегию второго игрока можно представить как n-мерный вектор q = (0, 0,..., 0, 1, 0,..., 0), j-ая компонента которого равна 1, а остальные нулю.

Основной теоремой в теории конечных антагонистических игр является теорема Неймана: каждая конечная игра имеет, по крайней мере, одно оптимальное решение, возможно, среди смешанных стратегий. Из этой теоремы следует, что не полностью определенная игра имеет хотя бы одно решение, возможно, не единственное, при котором хотя бы один из игроков или оба применяют смешанную стратегию. В таких играх решением будет пара оптимальных смешанных стратегий Р* и Q*, таких, что если один из игроков придерживается своей оптимальной стратегии, то и другому игроку не выгодно отклоняться от своей оптимальной стратегии. Выигрыш, соответствующий решению игры, называется ценой игры V, которая удовлетворяет следующему неравенству:

V_^≤V≤V^{^}

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

С-ядро.

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

и для любой коалиции выполнено:

где v — характеристическая функция игры.

Свойства:

Эквивалентным является определение С-ядра кооперативной игры в терминах блокирования распределений выигрыша коалициями. Говорят, что коалиция K блокирует распределение выигрыша x, если найдётся другое распределение выигрыша y, такое, что

и для любого участника выполнено

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

 

41.Теорема Неймана. Решение игры 2*2 в смешанных стратегиях.

Предположим, что в не полностью определенной игре, заданной платежной матрицей m*n, найдено оптимальное решение, состоящее из двух оптимальных стратегий Р*=(р , р ,…, р ) и Q*=(q , q ,…, q ), где некоторые из компонент векторов р