«В. А.МАТВЕЕВ Конечные бескоалиционные игры и равновесия Учебное пособие Псков 2005 1 ББК 22.18 М333 Печатается по решению кафедры алгебры и геометрии и редакционноиздательского совета ПГПИ им.С.М. Кирова. Матвеев В. А. ...»

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

ПСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ ИНСТИТУТ

им. С.М.КИРОВА

В. А.МАТВЕЕВ

Конечные бескоалиционные игры

и равновесия

Учебное пособие

Псков

2005

1

ББК 22.18

М333

Печатается по решению кафедры алгебры и геометрии и редакционноиздательского совета ПГПИ им.С.М. Кирова.

Матвеев В. А.

М 333 Конечные бескоалиционные игры и равновесия. Псков. 2005. 176с.

ISBN 5-87854-335-4 М 333 В учебном пособии представлено элементарное введение в теорию бескоалиционных игр, подготовленное для студентов гуманитарных специальностей. Теория игр изучает рациональное поведение людей с несовпадающими интересами. Это модели, описывающие конфликты и кооперацию. Рассмотрены антагонистические (матричные) и бескоалиционные (биматричные) игры. Исследование игровых задач проводится с позиций равновесия по Нэшу. Приведены свойства такого решения и указаны методы его нахождения. Подробно изложен алгоритм Лемке – Хаусона вычисления равновесия в биматричной игре. Изучение представленного материала не требует специальных знаний по математике, достаточно знакомства с основами высшей математики в объёме стандартного одногодичного курса “Высшая математика для гуманитариев”. Изложенный в пособии материал может составить содержание курса (спецкурса, спецсеминара) “Математические методы для экономики” (для социологии, психологии, юриспруденции).

Рецензенты:

кандидат физико-математических наук, доцент Мельник В.Н. (ПСковский государственный педагогический институт им. С.М.Кирова);

кандидат технических наук, доцент Кошмак В.К. (Псковский государственный политехнический институт).

ISBN 5-87854-335-4 © Матвеев В.А., © Псковский государственный педагогический институт им. С.М. Кирова, (ПГПИ им. С.М.Кирова), Содержание Введение

§1. Бескоалиционная игра в нормальной форме

§2. Удаление строго доминируемых стратегий

§3. Ситуация равновесия по Нэшу

§4. Гарантированные решения

§5. Смешанное расширение

§6. Графоаналитический метод решения матричных игр 2 n и m 2

§7. Выпуклые множества

§8. Линейное программирование: графический метод.............. §9. Двойственная задача линейного программирования.......... §10. Линейное программирование: симплексный метод........... §11. Матричная игра и задачи линейного программирования. §12. Биматричная игра

§13. Существование равновесия по Нэшу в бескоалиционной игре

§14. Свойства седловых точек

§15. Бескоалиционная игра с бесконечным числом равновесных ситуаций

§16. Алгоритм Лемке -Хаусона

Литература

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

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

По мере расширения и усложнения задач растёт потребность в научных способах выбора методов их решения. Это объясняется тем, что ошибки выбора в задачах большого масштаба или неоптимальные их решения приводят к огромным, а иногда и невосполнимым потерям. Крайним примером в этом ряду является взрыв на Чернобыльской АЭС. Здесь ошибки при решении сложной технической проблемы – вывода четвертого блока из эксплуатации, наложились на стратегические просчёты развития атомной энергетики, что и привело к взрыву.

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

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

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

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

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

“Математическое моделирование является одним из методов изучения сложных социально – экономических явлений, позволяет исследователю проникнуть в существо изучаемого процесса, вскрыть логику его развития. Применение этого метода требует совершенствования математического аппарата, его приспособления к запросам практики.” [1].

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

Здесь представлено элементарное введение в теорию бескоалиционных игр для студентов гуманитарных специальностей. Рассмотрены антагонистические (матричные) и бескоалиционные (биматричные) игры. Изучение игровых задач проводится с позиций равновесия по Нэшу. Приведены свойства такого решения и указаны методы его вычисления. Этот материал традиционно излагается в курсах по теории игр. Новым является включение алгоритма Лемке – Хаусона нахождения равновесия в биматричной игре. Эта тема будет интересна студентам и математических специальностей. В российской учебно – методической, да и научной, литературе эта тема представлена недостаточно.

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

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

При написании пособия использовался опыт преподавания элементов теории игр в курсе “Математические методы для экономики”.

§1. Бескоалиционная игра в нормальной форме В работе рассматриваются математические модели, представляющие взаимодействие, совместное функционирование нескольких объектов. Традиционно к таким моделям относят модели конфликта и кооперации. Задача изучения произвольного взаимодействия нескольких сторон является очень общей.

“Обладая большим логическим объёмом, она по необходимости имеет бедное содержание, в каком бы мы аспекте её ни рассматривали”. [6, с.26].

индивидуальных участников. Каждый из них характеризуется возможными действиями и своими целями. Каждый участник, действуя самостоятельно, стремится получить свой возможно лучший результат. Такие модели составляют содержание бескоалиционной теории игр [6, 7, 19, 25]. Исходя из классификации [6, c.26] это игры, в которой коалиции действий и интересов совпадают и каждая такая коалиция называется индивидуальным игроком.

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

Задаётся конечное множество игроков. Часто в модели они представлены списком N = {1,2,3,..., n}, где 1 представляет первого игрока, 2 – второго игрока и так далее, n – представляет последнего, n-го игрока.

Во-вторых, игроки предпринимают действия, оказывающие влияние на процесс взаимодействия. Фактически взаимодействие определяется набором действий всех участников или игроков. В теоретических моделях каждому игроку i N приписывается множество X i всех возможных действий и его влияние на процесс сводится к выбору конкретного элемента xi из этого множества.

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

Развитие процесса взаимодействия определяется выбором действий всех игроков. В модели рассматриваются упорядоченные наборы стратегий x = ( x1, x 2,..., x n ). Здесь стратегия xi X i есть выбор игрока i N. Такой набор называется ситуацией игры и множество всех ситуаций есть декартово произведение соответствующих множеств стратегий X = Xi.

В третьих, игроки делают выборы на основании своих предпочтений. В работе рассматривается теория игр с выигрышами [7, с.9]. В такой модели цель игрока определяется функцией выигрыша, т.е. отображением из множества ситуаций в множество выигрышей. Считаем, что выигрыш представляется действительным числом, которое показывает степень достижения желаемого результата. Итак, f i : X R является функцией выигрыша игрока i N.

Три основные характеристики взаимодействия определяются списком участников (множество игроков N ), множествами их возможных действий (множество стратегий X i ) и целями взаимодействующих сторон (функцией Математической моделью, учитывающей указанные свойства, называется бескоалиционная игра n –лиц в нормальной форме На содержательном уровне цель игрока i N в бескоалиционной игре (1.1) состоит в выборе такой “своей” стратегии xi X i, что его оценка сложившейся ситуации будет возможно большей. Напомним, что ситуация определяется стратегиями всех игроков, поэтому выбор игрока должен учитывать выборы остальных игроков.

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

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

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

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

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

Антагонистической игрой называется тройка множеств где X и Y – множества стратегии первого и второго игроков x X и y Y, а f : X Y R функция выигрыша первого игрока.

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

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

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

Пример 1.1. (Камень, ножницы, бумага) [11, c.45]. Каждый из двух игроков одновременно называет один из трёх предметов:

камень, ножницы, бумага. “Бумага” побеждает “камень”, “камень” - “ножницы”, ножницы” - “бумагу”. Игрок, выбирающий выигрывающий предмет получает у противника единицу; если оба игрока выберут одинаковые предметы, то игра закончится вничью.

В модели этой игры два игрока. Обозначим их: игрок 1, игрок 2. Тогда в игре N = {1, 2}. У игроков одинаковые возможности – выбрать “камень” (К), “ножницы” (Н), “бумагу” (Б). Значит множества стратегий игроков X 1 = X 2 = {K, Н, Б}. Эта игра является матричной (1.2), т.к. она конечная и выигрыш первого игрока равен проигрышу второго игрока (выигрышу первого игрока с противоположным знаком). Запишем выигрыши первого игрока в таблице.

Здесь строки соответствуют выборам (стратегиям) первого игрока, а столбцы таблицы – выборам (стратегиям) второго игрока. На пересечении, выбранных строки и столбца, в клетке показан выигрыш (проигрыш) первого (второго) игрока. Так ситуации (К, Н) в таблице записан выигрыш первого игрока, равный 1. В этой ситуации первый игрок выбрал “камень”, а второй игрок – “ножницы”. По условию камень” побеждает “ножницы”. Это значит, что первый игрок получает 1, а второй теряет 1. По другому, в этой ситуации выигрыш второго игрока равен –1.

В математике принято табличные данные представлять в матричной форме. Напомним, что матрица – это просто таблица из чисел. Данная игра задаётся матрицей выигрыша первого игрока Пример 1.2. (Игра полковника Блотто) [11, с.106 - 107]. Игра полковника Блотто – общее название большого класса тактических военных игр. Приведём один из наиболее простых вариантов этой игры.

Две воюющие армии ведут борьбу за два пункта. Первая армия под командованием полковника Блотто состоит из четырёх (m = 4) полков; вторая под командованием капитана Киже [6] состоит из трёх (n = 3) полков. Армия, которая посылает больше полков на тот или иной пункт, занимает его и уничтожает все направленные на этот пункт силы противоположной стороны, получая единицу, как за занятый пункт, так и за каждый уничтоженный полк противника. Полковник Блотто (и капитан Киже) должен решить, как распределить силы, чтобы выиграть как можно больше очков.

В модели представлены два игрока, т.е. N = {Блотто, Киже}.

Стратегии игроков есть распределение полков между двумя пунктами. Стратегии полковника Блотто есть распределение четырёх полков между первым и вторым пунктами. Имеется пять таких распределений. Они и составляют множество чистых стратегий первого игрока. Вот это множество X 1 = {( 4,0), (3,1), (2,2), (1,3), (0,4)}. Точно также у капитана Киже его четыре чистые стратегии могут быть представлены парами и множество стратегий X 2 = {(3,0), (2,1), (1, 2), (0,3)}. В каждой паре первое число указывает число полков, направленных на первый пункт, второе число – на второй пункт.

По условию игра является антагонистической. В таблице 1.2 представлены выигрыши полковника Блотто в зависимости от действий, выбранных игроками. Эти же числа указывают проигрыши капитана Киже. Эта игра симметрична для полковника Блотто относительно стратегий (4, 0) и (0, 4), а также относительно стратегий (3, 1) и (1, 3); для капитана Киже стратегии (3, 0), (0, 3) и (2, 1), (1, 2) также являются симметричными. Эти свойства симметрии позволят найти оптимальное решение игры полковника Блотто.

Как обычно такую игру задают одной матрицей выигрышей первого игрока (полковника Блотто).

Пример 1.3. (Семейный спор). [19, c.114-115]. Он и Она независимо решают, как провести выходной: пойти на футбол (Ф) или на балет (Б). Если они вместе пойдут на футбол, то Он получит больше удовольствия, чем Она; если они оба пойдут на балет, то – наоборот. Наконец, если они окажутся в разных местах, то они не получат никакого удовольствия.

Рассмотрим игровую модель этого семейного спора. В задаче представлены два игрока, т.е. N = {Он, Она}. Игроки имеют одинаковые возможности действий: пойти на Футбол или пойти на Балет. Их множества действий равны X1 = X2 = {Ф, Б}, где Ф – пойти на футбол, Б – пойти на балет.

Обозначим числом ( ) – меру удовольствия, что получает Он от совместного посещения Футбола (Балета). По условию >. Симметрично, ( ) – мера удовольствия, что получает Она от совместного посещения Балета (Футбола). Игровая модель данного явления является бескоалиционной игрой, но это не антагонистическая игра, т.к. совместное посещение одного мероприятия даёт положительную меру удовольствия каждому, а раздельное проведение времени - нулевое удовольствие.

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

Обычно такую игру задают двумя матрицами выигрышей первого (матрица А) и второго (матрица В) игроков.

Задачи для самостоятельного решения Задача 1.1. Построить игровую модель для задачи полковника Блотто в случая m = 4 и n = 4 полков у полковника Блотто и капитана Киже.

Задача 1.2. Построить игровую модель для задачи полковника Блотто в случая m = 4 и n = 3 полков у полковника Блотто и капитана Киже. Оценивать захваченный пункт числом > 0, а за каждый разбитый полк противника добавлять командиру – победителю число.

Задача 1.3. Построить игровую модель для задачи полковника Блотто для случая, когда борьба ведётся за три пункта и число полков у полковника Блотто и капитана Киже равно m = и n = 4.

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

Соответствующий метод называется последовательное удаление строго доминируемых стратегий [7, с.78 - 79] Продемонстрируем метод на примере, наверное самом известном в теории игр. Это знаменитая “Дилемма заключенных”, для которой существует несколько различных вариантов. Приведенный далее пример [20, c.45имеет яркий экономический смысл.

Пример 2.1. (Дилемма заключённых). Рассмотрим две нефтедобывающие страны, которые назовём А и В. Эти две страны могут кооперироваться (a), договариваясь об объёмах ежедневной добычи нефти, ограничиваясь добычей в 2 млн. баррелей в день, для каждой страны. С другой стороны страны могут действовать некооперативно (b), добывая, скажем, 4 млн. баррелей в день.

Выявить оптимальный режим поведения стран.

В модели представлено два игрока: страна А и страна В.

Взаимодействие стран представлено в таблице 2.1. Здесь указаны прибыли стран в зависимости от объёмов добычи нефти.

Это достаточно типичная для картеля картина, когда у каждого его члена картеля есть стимул отклониться от договора, чтобы за счёт увеличения объёмов продаж получить дополнительную прибыль. В игре множества стратегий у обоих игроков XА = XВ = {a, b}. Такую игру задают двумя матрицами выигрышей первого и второго игроков Здесь у страны А стратегия b строго доминирует стратегию a, т.к выигрыши от применения стратегии b будут больше, чем выигрыши от применения стратегии a. Действительно (f1(b,a), f1(b,b)) = (52, 32) > (46, 26) = (f1(a,a), f1(a,b)) т.е. вектор (52, 32) по обоим компонентам больше, чем вектор (46, 26). Рациональные игроки не будет рассматривать в качестве решения доминируемую стратегию. Они исключают стратегию a из рассмотрения. Получаем или в форме двух матриц (каждая из них размера 1х2) Далее рассматриваем игру, полученную после исключения доминируемой стратегии первого игрока. Она представлена в таблице 2.2. В этой игре у второго игрока имеется две стратегии и одна из них, именно b, доминирует другую, a. Действительно, f 2 (b,b) = 24 > 22 = f 2 (b,a) Рациональные игроки не будут рассматривать, как решение, доминируемую стратегию a. Эту стратегию можно удалить.

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

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

Рациональные игроки, анализируя бескоалиционную игру в таблице 2.1., выберут стратегии (b,b) X A X B, т.к. исключат нерациональные (неэффективные) действия.

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

Эта информации тем более ценна, что имеет логическое основание. Всё это относится и к игровым моделям.

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

Представление результата должно отвечать на два вопроса: Что делать? Что при этом получится? В игровых задачах ответ на первый доставляет полученная ситуация. На второй вопрос отвечает значение функций выигрыша игроков в выбранной ситуации.

В бескоалиционной игре, представленной в таблице 2.1, решением является ситуация (b,b), при этом игроки получат выигрыши (32, 24).

Рассмотренную задачу можно решить другим способом.

Вначале удалить строго доминируемую стратегию второго игрока, а затем у первого. В результате будет получен тот же результат. Это общее Свойство 2.1. Если в бескоалиционной игре (1.1) последовательно удалить все строго доминируемые стратегии, то последовательности удаления.

Перейдём к общим формулировкам. Пусть рассматривается бескоалиционная игра (1.1). Здесь и далее будем использовать обозначение для набора стратегий всех игроков, кроме i N стратегию xi X i, если j i, x j X j, выполнены неравенства Это условие соответствует использованию покоординатного отношения порядка для векторов, составленных из выигрышей игрока i N в ситуациях, где он использует стратегию x i* Хi (первый вектор) и в ситуациях со стратегией xi Х i (второй вектор).

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

Рассмотренная процедура применяется и в матричной игре.

В такой игре последовательно удаляются строго доминируемые стратегии. Этим стратегиям соответствует доминируемая (доминирующая) строка (столбец) матрицы выигрышей.

Пример 2.2. В матричной игре, представленной матрицей А, выделить рациональные стратегии, т.е. стратегии, остающиеся после удаления строго доминируемых стратегий В игре у первого игрока четыре стратегии (в матрице четыре строки). Эти стратегии (строки) А 1, А 2, А 3, А 4. Аналогично столбцы у второго игрока В1, В2, В3, В4. В предложенной игре стратегия А2 доминирует стратегию А3 и А4, которые удаляются на первом шаге. Рассмотрим матричную игру после удаления двух строк, представленную матрицей А’ Здесь стратегии В 2 и В 4 доминируют стратегию В 3.

Напомним, что данная игра антагонистическая и в столбцах матрицы представлены проигрыши второго игрока. После удаления доминирующих стратегий второго игрока, получается матрица, представленная в А" Теперь последовательно удаляются стратегии А 1 (она доминируется стратегией А 2 ) и затем стратегия В 1 (она доминирует стратегией В 3 ). После этого у каждого игрока осталось по одной стратегии, т.е. ситуация (А2, В3), в которой игроки получат выигрыши 4 и –4 соответственно. Принято выигрыш первого игрока в антагонистической игре называть ценой игры и обозначать v*. В рассмотренном примере v* = 4.

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

Стратегия xi* X i игрока i N слабо доминирует стратегию x X i, если для любого набора стратегий всех остальных игроков выигрыш от стратегии xi* для игрока i не меньше, чем выигрыш от стратегии xi и найдётся набор стратегий остальных игроков, т.е. x j X j, j i, что выполнено неравенство f i ( x1,..., xi 1, xi*, xi +1,..., x n ) > f i ( x1,..., xi 1, xi, x i +1,...,x n ). (2.2) Это условие соответствует использованию отношения порядка для векторов, составленных из выигрышей игрока i в ситуациях, где он использует свою стратегию x i* Х i (первый вектор) и в ситуациях, где он использует свою стратегию xi Хi (второй вектор).

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

Но результаты могут существенно различаться. Для стратегий выдержавших последовательное удаление слабо доминируемых стратегий не выполнен аналог утверждения 2.1. Если в задаче 1. последовательно удалять слабо доминируемые стратегии, то результат (оставшиеся стратегии) будет зависеть от последовательности удаления стратегий. Соответствующий пример и обсуждения можно найти в [20, c.41-43].

Задачи для самостоятельного решения Задача 2.1. Проанализировать матричную игру, используя алгоритм удаления строго доминируемых стратегий Задача 2.2. Какие стратегии в биматричной игре выдерживают последовательное удаление строго доминируемых стратегий §3. Ситуация равновесия по Нэшу Последовательное удаление строго доминируемых стратегий сокращает множество ситуаций, претендующих на роль решения.

Существуют даже такие задачи, в которых после применения этого алгоритма остаётся одна ситуация (см. пример 2.1 и 2.2).

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

В этой игре представлены два игрока: N = {1, 2}. Множества их стратегий X 1 = {B, C, H } и X 2 = {Л, С, П}. В клетках таблицы указаны выигрыши первого и второго игроков: в левом верхнем углу приведён выигрыш первого игрока, в правом нижнем углу представлен выигрыш второго игрока.

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

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

Определение 3.1. Ситуация x* X в бескоалиционной игре (1.1) в нормальной форме называется равновесием по Нэшу, если i N, x i X i выполнены неравенства где ситуация ( x i, xi ) = ( x1,..., xi1, xi, x i+1,..., x n ).

Замечание 3.1. Условие (3.1) означает, что стратегия x X i игрока i N входит в равновесную по Нэшу ситуацию x* = ( x1,..., xi1, xi, xi+1,..., x n ). тогда и только тогда, когда Выбор равновесия по Нэшу мотивирован тем, что если в качестве решения будут предложено не равновесное решение, то найдётся игрок, который, уклонившись в одностороннем порядке от предложенной ситуации, получит больший выигрыш. Таким образом, рациональный игрок будет придерживаться только равновесной ситуации.

В игре примера 3.1 ситуация ( Н, П ) X является равновесием по Нэшу. Действительно, Другой такой ситуации в предложенной игре нет.

Равновесной по Нэшу ситуацией является пара x* = ( H, П ) X.

В этом случае игроки получают выигрыши f1 ( x*) = f 2 ( x*) = 6.

В примере 2.1 (Дилемма заключённых) единственная ситуация (b,b) X A X B удовлетворяет определению 3.1 ситуации равновесия по Нэшу. Эта же ситуация выделяется и алгоритмом удаления строго доминируемых стратегий.

В тоже время в биматричной игре представленной в таблице3.1 алгоритм удаления стратегий не работает, т.к. нет строго доминируемой стратегии. Говорят, что в этой игре все стратегии переживают процедуру удаления строго доминируемых стратегий. Равновесная по Нэшу ситуация находится среди ситуаций “переживших” эту процедуру. Аналогичные свойства имеют место и в общем случае бескоалиционной игры.

Сформулируем это в виде Утверждение 3.1. Пусть в бескоалиционной игре (1.1) после применения алгоритма удаления строго доминируемых стратегий осталась одна ситуация x* X, тогда эта ситуация является единственным равновесием по Нэшу в игре.

Утверждение 3.2. Пусть в бескоалиционной игре (1.1) ситуация x* X является равновесием по Нэшу, тогда каждая входящая в эту ситуацию стратегия не может быть удалена алгоритмом удаления строго доминируемых стратегий.

Приведённые утверждения показывают, что равновесие по Нэшу является уточнением решения, получаемого после алгоритма удаления строго доминируемых стратегий. Пример 3. устанавливает, что это строгое уточнение. В этом примере шесть ситуаций (т.е. все ситуации исходной игры) пережили процедуру удаления строго доминируемых стратегий. Алгоритм удаления не может предсказать поведение игроков в конфликте. В тоже время равновесие по Нэшу выделяет одну ситуацию, т.е.

предсказывает действия сторон.

Продолжим рассмотрение примера 1.3 Семейный спор. Эта биматричная игра представлена матрицами выигрыша первого и второго игрока Здесь Он и Она независимо решают, куда пойти вечером – на балет (Б) или на футбол (Ф). Если они вместе пойдут на футбол, то Он получит большее удовольствие, чем Она; если они вместе пойдут на балет, то – наоборот. Наконец, если они окажутся в разных местах, то они не получат никакого удовольствия. Проанализировать проблему наилучшего проведения вечера семьёй.

Положим, что совместный поход на футбол приносит Ему единицы удовольствия, а Её – только 1 единицу. Совместный поход на балет наоборот приносит Ему и Ей удовольствие в 1 и 2 единицы соответственно. Раздельное проведение вечера доставляет удовольствия обоим. В этом случае проблема проведения вечера с наибольшей пользой может быть смоделирована биматричной игрой, представленной в таблице 3.2.

В этой задаче две ситуации удовлетворяют определению 3. равновесия по Нэшу. Это ситуации (Ф, Ф), (Б, Б) X.

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

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

Антагонистическая игра (1.2) и матричная игра являются специальным видом бескоалиционной игры. К ним применимо определение равновесие по Нэшу. В таких играх равновесная по Нэшу ситуации имеет специальное название – седловая точка.

Определение 3.2. Ситуация ( x, y) X Y в антагонисти-ческой игре (1.2) называется седловой точкой, если В матричной игре ситуация соответствующая i-ой строке и j-ому столбцу матрицы выигрышей является седловой точкой тогда и только тогда, соответствующий выигрыш aij R является наибольшим в i-ом столбце и наименьшим в j-ой строке этой матрицы. В игре примера 3.1 таким свойством обладает ситуация x* = ( H, П ) X = X 1 X 2. В матричной игре примера 2.2 сформулированному выше условию удовлетворяет ситуация Пример 3.2. (Орлянка, начало). Игрок 1 выкладывает монету на стол, а игрок 2, не видя монеты, угадывает, какой стороной (т.е. “орлом” (о) или “решкой” (р)) вверх она положена. В случае угадывания он получает от игрока 1 одну единицу выигрыша, в противном случае уплачивает ему единицу.

Данная игра является матричной. Матрица выигрышей представлена в таблице 3.3.

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

Существуют игры, в которых равновесие нет.

Подход к изучению таких задач основан на стандартном математическом подходе. В случае отсутствия решения среди заданных ситуаций следует расширить их множество и анализировать задачу в этом расширенном множестве. Расширение игровых задач и решение примера 3.2. – в следующих параграфах.

Задачи для самостоятельного решения Задача 3.1. Найти седловые точки в матричных играх Задача 3.2. Указать ситуации равновесия в биматричных играх с матрицами выигрыша Задача 3.3. Найти все ситуации равновесия в биматричной игре с одинаковыми матрицами выигрыша А в общем виде Задача 3.4. Найти все ситуации равновесия в биматричной игре с матрицами выигрыша Ответ к задачи 3.3.

§4. Гарантированные решения Равновесие по Нэшу, как решение бескоалиционной игры, предполагает некоторый (минимальный) уровень договорённости между игроками. Выбирая стратегию из равновесной ситуации, игрок предполагает, что другие игроки рациональны, и они считают, что и он рациональный игрок. На этом основан уровень минимальной совместной договорённости (кооперации) между игроками. Так думает каждый игрок, и, если равновесие единственно, то все они придерживаются равновесного выбора.

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

Рассматривается матричная игра, заданная матрицей Amn = (aij ). Конечные множества стратегий X 1 = X = {1,2,..., m} первого и X 2 = Y = {1,2,..., n} второго игроков соответствуют номерам строк и столбцов матрицы A.

Пусть первый игрок выбирает строку i X, тогда, независимо от выбора второго игрока, его выигрыш будет больше или равен числа min aij. Но поскольку он может выбрать строку как угодно, он может сделать эту величину возможно большей.

Значит, он выбирает строку из условия В этом случае стратегия i* X называется максиминной стратегией первого игрока, а соответствующее значение Н – максимином. Это число является гарантией для первого игрока.

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

Пример 3.2. (Продолжение). Найти гарантии игроков в игре Семейный спор.

Вычисления проведём в таблице, представленной в 4.1.

В игре Семейный спор игроки имеют одинаковые максимины, они равны 0, т.е. гарантированный вектор выигрышей двух игроков – (0, 0). Напомним, что в этой игре две точки равновесия по Нэшу дают выигрыши первому и второму игроку (2, 1) и (1, 2). У каждого игрока максимин не больше его же выигрыша в любой равновесной ситуации. Последнее утверждение верно и в любой бескоалиционной игре. Отметим, что в игре Семейный спор каждая стратегия первого и второго игроков является максиминной.

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

В матричной игре это означает min ( aij ) = max aij.

В этом случае стратегия j* X 2 называется минимаксной стратегией второго игрока, а соответствующее значение B – минимаксом или верхней ценой игры. В этом случае минимакс Н называю нижней ценой игры. Число является гарантией для второго игрока. При таком выборе второй игрок получит выигрыш B, либо меньший выигрыш. Напомним, что второй игрок стремится увеличить выигрыш для матрицы Amn = ( aij ) что равносильно выбору наименьшего числа из выделенных наибольших чисел в столбцах матрицы Amn.

антагонистической игре (1.2) следует из неравенства минимаксов.

Утверждение 4.1. (неравенство минимаксов). Пусть задана функция f : X Y R, тогда Доказательство этого общематематического факта можно найти в [1, c.31; 4, с.15-16]. Тем более он будет верен для конечных множеств стратегий. В случае матричной игры (4.1) означает Это неравенство оправдывает термины: нижняя и верхняя цена игры.

антагонистические игры на два больших класса. Во-первых, это антагонистические игры, у которых (4.2) выполняется как равенство, т.е. Н = B. Это общее значение называется ценой игры и обозначается *. В этом случае существует зависимость между гарантированными решениями и седловой точкой в антагонистической игры (3.3), которая представлена Утверждение 4.2. Для того, чтобы в антагонистической игре (1.2) ситуация ( x*, y*) X Y была седловой точкой необходимо и достаточно, чтобы существовали максимин и минимакс и выполнялось равенство Доказательство этого утверждения можно найти в [1, c.38c.18-20].

Во-вторых, это антагонистические игры, у которых (4.2) выполняется как строгое неравенство, т.е. Н < B. В этом случае в игре нет седловой точки. Напомним, что в антагонистической игре седловые точки и только они являются равновесиями по Нэшу.

Пример 4.3. (Орлянка, продолжение). Гарантированные решения в игре Орлянка найдём в таблице 4.2.

Итак, в игре 3.3. нижняя цена игры Н = -1 и обе стратегии первого игрока являются максиминными. Верхняя цена игры B = 1 и две стратегии второго игрока являются минимаксными. Так как Н = -1 < 1 = B, то, согласно утверждению 4.2 в этой игре нет седловой точки и, значит, нет равновесия Нэша.

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

где * = f(x*, y*) – цена игры.

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

Задачи для самостоятельного решения Задача 4.1. Определить верхнюю и нижнюю цену игры, заданной матрицей Задача 4.2. Найти гарантированные решения для первого и второго игроков и седловую точку в матричной игре с матрицей Задача 4.3. Пусть в антагонистической игре множества стратегии игроков X = Y = [-1, 1] и функция выигрыша первого игрока f(x, y) = -x2 + 2xy + y2. Найти гарантированные решения игроков и седловую точку.

Задача 4.4. Пусть функция f(x, y) определена и непрерывна на множестве X Y, где X Rm, Y R n выпуклые компактные множества. При каждом y Y функция f(x, y) вогнута по x X и при любом x X она выпукла по y Y. Тогда выполнено равенство §5. Смешанное расширение Рассмотрим антагонистическую игру (1.2). Если в ней нет седловой точки, то гарантированные выигрыши игроков различны (Утверждение 4.2). В этом случае максиминная стратегия первого игрока и минимаксная стратегия второго игрока позволяет им получить выигрыш, не хуже их гарантированного результата.

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

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

Определение 5.1. Смешанной стратегией игрока в бескоалиционной игры (1.1) является случайная величина, значениями которой являются первоначальные стратегии этого игрока.

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

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

Рассматривается матричная игра, заданная матрицей Amn = (aij ). Тогда конечные множества стратегий X 1 = {1,2,..., m} первого и X 2 = {1, 2,..., n} второго игроков соответствуют номерам строк и столбцов матрицы. Эти числа представляют чистые стратегии игроков. Смешанную стратегию первого и второго игроков будем обозначать За множеством всех смешанных стратегий сохраним обозначения иэ (1.1), т.е. x X, y Y.

В матричной игре множества смешанных стратегия первого игрока X, подчинённые условию (5.1), составляют (m-1) – мерный симплекс, натянутый на орты Такой симплекс называют фундаментальным. Аналогично определяется (n - 1) - мерный симплекс для смешанных стратегий второго игрока (5.2). В случае m = фундаментальный симплекс является отрезком (см. рис. 5.1), при m = 3 треугольником (см. рис. 5.2).

Отметим, что при любом натуральном m фундаментальный симплекс является компактным множеством в R. Иногда удобно рассматривать смешанную стратегию и соответствующую ей точку фундаментального симплекса. Тогда смешанная стратегия представляет барицентрические координаты этой точки. Чистые стратегии, представленные в (5.3), являются вершинами фундаментального симплекса.

Для каждой смешанной стратегии игрока x X ( y Y ) множество его чистых стратегий, которые входят в эту смешанную стратегию с положительной вероятностью, называют спектром стратегии и обозначают sup p( x) (sup( y )). Конечно для чистой стратегии спектр состоит из одной этой стратегии.

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

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

Тогда в качестве выигрыша первого игрока в условиях ситуации в смешанных стратегиях x X, y Y естественно принять математическое ожидание его выигрыша, т.е.

или, употребляя векторную запись, где x R m, y R n векторы – столбцы и T – операция транспонирования. Так как рассматривается матричная игра (антагонистическая игра), то выигрыш второго игрока Формально смешанное расширение матричной игры представлено в (1.2).

Определение 5.2. Смешанным расширением матричной игры является система (1.2), где X R m, Y R n множества смешанных стратегий, определено в (5.1) и (5.2), а функция выигрышей первого игрока представлена в (5.4).

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

Смешанная стратегия в этом случае будет вероятностной мерой на пространстве стратегий игрока. Такие игры называются бесконечными. Они активно изучались, но теория таких игр выходит за рамки этой работы. Заинтересованным лицам укажем литературу [2, c.92 – 159; 4, с.60 – 113; 7].

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

В этом случае применяются условия строгого доминирования (2.3) и f i ( x i, xi* ) в них определяется по правилу аналогичному (5.4).

Пример 5.1. Решить матричную игру с матрицей Обозначим чистые стратегии первого игрока строки матрицы 1, 2, 3. Решим игровую задачу последовательным удалением строго доминируемых стратегий. В этой задаче смешанная стратегия первого игрока x 12 = (0,5; 0,5; 0) доминирует чистую стратегию a 3 = (0, 0, 1), поэтому последняя удаляется. Действительно, 0,5(9, 2, 0) + 0,5(2, 9, 1) +0(5, 5, 0) = (5,5, 5,5, 0,5) > (5, 5, 0).

Здесь чистая стратегия b3 = (0, 0, 1) доминирует чистые стратегии b1 = (1, 0, 0) и b2 = (0, 1, 0). Значит стратегии b1 и b2 удаляются.

Стратегия a 1 удаляется в силу строгого доминирования. В результате анализа игры выделили ситуацию x* = (a2, b3 ) или в новых обозначениях x* = ((0, 1, 0), (0, 0, 1)) X. Согласно утверждения 3.1, эта ситуация является единственным равновесием по Нэшу в задаче. Цена игры * = 1.

Задачи для самостоятельного решения Задача 5.1. Найти цену игры и седловую точку в смешанных стратегиях на основании критерия из утверждения 4.2 для матричной игры с матрицей Задача 5.2. Проанализировать матричную игру, используя последовательное удаление строго доминируемых стратегий в смешанном расширении §6. Графоаналитический метод решения матричных игр 2 n и m Для некоторых классов матричных игр практический интерес представляет графоаналитический метод. Этот метод состоит из двух частей. Вначале в матричной игре графически выявляются качественные особенности решения, затем полная характеристика решения находится аналитически.

В основе метода лежит утверждение 4.2, которое остаётся верным и в смешанном расширении игры. Седловая точка в матричной игре существует тогда и только тогда, когда выполняется равенство причём седловую точку составляют стратегии, доставляющие внешние экстремумы в последнем равенстве.

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

с позиций игрока, имеющего две чистые стратегии.

Вычислим Обозначим Для нахождения максимина приведём геометрическую иллюстрацию на рис.6.1.

Вначале для каждого [0,1] найдём На рис.6.1 такие минимумы для каждого [0,1] образуют ломаную – нижнюю огибающую АВСD. Затем на огибающей находим наибольшее значение, которое достигается в точке В.

Эта точка реализуется при [0,1], которое является решением смешанном расширении данной игры Максиминная стратегия первого игрока xн = (, 1- ) = (3/11, 8/11).

По аналогичной схеме найдём минимаксную стратегию y = (0,, 1 ), 0 1. Первая компонента вектора y равна 0, т.к. максиминная стратегия определяется вторым и третьим столбцом матрицы А. В этом случае в максиминной стратегии первая компонента равна 0. Для нахождения [0, 1] в матрице А оставим только второй и третий столбцы.

Обозначим Найдём иллюстрацию на рис.6.2.

Вначале для каждого [0,1] найдём На рис.6.2 такие минимумы для каждого [0,1] образуют ломаную – верхнюю огибающую KLM. Затем на огибающей находим наименьшее значение, которое достигается в точке L.

Эта точка появляется при [0,1], которое является решением уравнения f1 = f 2, т.е. 11-8 = 2+3. Здесь = 911. Вторая координата точки L будет 11 8 9 11 = 49 11. Итак L(, ). В смешанном расширении данной игры Минимаксная стратегия второго игрока yB = (0,, 1- ) = (0, 9/ 11, 2/11).

В примере выполнены условия утверждения 4.2. В самом деле, минимакс и максимин существуют и выполнено равенство Значит цена игры * = 49/11 и седловая точка (x*, y*) = ((3/11, 8/ 11), (0, 9/11, 2/11)).

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

Ответ : (x*, y*) = ((3/11, 8/11), (0, 9/11, 2/11)), * = 49/11.

Пример 6.2. Найти седловую точку матричной игры, заданной матрицей Здесь игрок 1 имеет три чистые стратегии, а второй игрок две стратегии. Решаем игру с позиций второго игрока, т.е. с позиций игрока, имеющего две чистые стратегии.

Вычислим Обозначим Для нахождения минимакса приведём геометрическую иллюстрацию на рис.6.3.

Вначале для каждого [0,1] найдём На рис.6.3 такие максимумы для каждого [0,1] образуют ломаную – верхнюю огибающую HJKL. Затем на огибающей находим наименьшее значение, которое достигается в точке K.

Эта точка будет при [0,1], которое является решением уравнения f1 = f 2, т.е. 4-3 = 5 -2. Значит = 3 4. Вторая смешанном расширении данной игры Определим и минимаксную стратегию второго игрока. Это По аналогичной схеме найдём максиминную стратегию x = (, 1, 0), 0 1. Третья компонента вектора x равна 0, т.к. минимаксная стратегия второго игрока определяется первым и вторым строками матрицы А. В этом случае в максиминной стратегии третья компонента равна 0.

Вычислим Обозначим Найдём иллюстрацию на рис.6.4.

Вначале для каждого [0,1] найдём На рис.6.4 такие минимумы для каждого [0,1] образуют ломаную – нижнюю огибающую MNP. Затем на огибающей находим наибольшее значение, которое достигается в точке N. Эта точка появляется при [0,1] и является решением уравнения f1 = f 2, т.е. 3-2a = 6a-2. Здесь a = 5 8. Вторая координата точки N будет 3 2 5 = 7. Итак N(, ). В смешанном расширении данной игры Максиминная стратегия первого игрока xН = (, 1-, 0) = (5/8, 3/8, 0).

В примере выполнены условия утверждения 4.2. В самом деле, минимакс и максимин существуют и выполнено равенство Значит цена игры * = 7/4 и седловая точка (x*, y*) = ((5/8, 3/8, 0), (3/4, 1/4)).

В итоговой проверке следует продемонстрировать выполнение равенства ( x *)T A ( y *) = v *. В данном примере получаем верное равенство.

Ответ : (x*, y*) = ((5/8, 3/8, 0), (3/4, 1/4)), * = 7/4.

Наконец, решим отложенный из § Пример 3.3. (Орлянка, окончание ). Напомним, что эта игра представлена матрицей Здесь игрок 1 и игрок 2 имеет две чистые стратегии. Решаем игру с позиций первого игрока.

Пусть его стратегия x = (, 1 ),0 1. Вычислим Обозначим Найдём иллюстрацию на рис.6.5.

Вначале для каждого [0,1] найдём На рис.6.5 такие минимумы для каждого [0,1] образуют ломаную – нижнюю огибающую MPQ. Затем на огибающей находим наибольшее значение, которое будет в точке P. Эта точка достигается при [0,1], которое является решением уравнения f1 = f 2, т.е. 2 - 1 = 1 - 2. Здесь = 1 2. Вторая координата точки P будет 2 1 2 1 = 0. Итак P( 1 2, 0). В смешанном расширении данной игры Максиминная стратегия первого игрока x н = (, 1- ) = (1/2, 1/2).

По аналогичной схеме найдём минимаксную стратегию Вычислим Обозначим Найдём Для нахождения минимакса приведём геометрическую иллюстрацию на рис.6.6.

Вначале для каждого [0,1] найдём На рис.6.6 такие минимумы для каждого [0,1] образуют т ломаную – верхнюю огибающую RST. Затем на огибающей находим наименьшее значение, которое достигается в точке S.

Эта точка появляется при [0,1], которое является решением уравнения f1 = f 2, т.е. 2 - 1 = 1 - 2. Здесь = 1 2. Вторая координата точки S будет 2 1 2 1 = 0. Итак S(,0). В смешанном расширении данной игры Минимаксная стратегия второго игрока yB = (b, 1- b) = (1/2, 1/2).

В примере выполнены условия утверждения 4.2. В самом деле, минимакс и максимин существуют и выполнено равенство Значит цена игры * = 0 и седловая точка (x*, y*) = ((1/2, 1/2), (1/2, 1/2)).

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

Ответ : (x*, y*) = ((1/2, 1/2), (1/2, 1/2)), * = 0.

В последнем примере в силу симметрии матрицы выигрыша игроки находятся в равных условиях. Поэтому следует ожидать равные выигрыши в этой антагонистической игре. Но в такой игре выигрыши отличаются знаком. Поэтому для цены игры может быть только одна возможность - * = 0. Такой же результат получен графоаналитическим методом. Имеется симметрия и в оптимальных стратегиях игроков. Проведённое исследование рекомендует следующее поведение в игре Орлянка.

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

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

Задачи для самостоятельного решения Задача 6.1. Найти решение матричной игры, используя графоаналитический метод Задача 6.2. Первый игрок выбирает одно из двух чисел: или 2. Второй игрок выбирает одно из трёх чисел: 1 или 2 или 3.

Если оба числа одинаковой чётности, то первый игрок выигрывает у второго сумму выбранных чисел. Если чётность выбранных чисел не совпадает, то сумму чисел выигрывает второй игрок у первого. Построить соответствующую матричную игру и найти равновесие.

Задача 6.3. Найти решение матричной игры, предварительно упростив её §7. Выпуклые множества Интуитивное представление о выпуклом множестве формируется в школьном курсе математики. Так многоугольник называется выпуклым, если целиком расположен по одну сторону от прямых, на которых лежат его стороны. Например, на рисунке 7.1а) пятиугольник АВСДЕ – выпуклый, а на рисунке 7.1б) пятиугольник MNPQR – не является выпуклым. Он расположен по обе стороны от прямой PQ.

Определяющим свойством, которое отличает выпуклое множество от невыпуклого, является то, что если взять две любые его точки и соединить их отрезком, то весь отрезок будет принадлежать этому множеству. Согласно этому свойству пятиугольник ABCDE – выпуклый, а MNPQR таковым не является, ибо отрезок XY между двумя его точками не полностью принадлежим многоугольнику.

Определение 7.1. Множество точек называется выпуклым, если вместе с любыми двумя своими точками содержит весь отрезок, соединяющий эти точки.

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

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

Будем рассматривать множества в конечномерном евклидовом пространстве R n, n 1. Среди точек выпуклого множества можно выделить внутренние, граничные и угловые точки. Точка множества называется внутренней, если найдётся окрестность этой точки, содержащая только точки этого множества. Под произвольной окрестностью точки в евклидовом пространстве понимают круг (шар) с центром в этой точке и произвольного радиуса.

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

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

Выделяются ограниченные и неограниченные множества в евклидовом пространстве. Множество в пространстве R n называется ограниченным, если найдётся окрестность точки этого множества (достаточно большого радиуса), содержащая всё данное множество. В противном случае множество называется неограниченным.

Определение 7.2. Множество точек евклидового пространства называется компактным, если оно является ограниченным и замкнутым.

Точка множества называется угловой (или крайней), если она не является внутренней ни для какого отрезка, целиком принадлежащего данному множеству. На рисунке 7.1 а) каждая точка ломаной замкнутой линии ABCDE является граничной точкой для пятиугольника. У этого множества имеется ровно пять угловых точек. Их множество U1 = {A, B, C, D, E}. У невыпуклого пятиугольника MNPQR границу составляют точки замкнутой ломаной MNPQR. У этого множества четыре угловых точек U 2 = {M, N, Q, R}. Точка P является вершиной пятиугольника, но не является угловой точкой. У круга (шара) соответствующая окружность (сфера) состоит из всех граничных точек этого множества. Здесь каждая точка окружности (сферы) является угловой точкой.

Выпуклые множества и угловые точки рассматриваются в n – мерном векторном пространстве. Множество V R n называется выпуклым, если x 1, x 2 V, [0,1] линейная формулировка для выпуклого множества, т.к. множество соответствует отрезку с концами x 1 и x 2 в векторном пространстве R n.

Обобщением понятия отрезка в векторном пространстве является выпуклая линейная комбинация точек. Точка x R n называется выпуклой линейной комбинацией точек x 1, x 2, …, x k R n, если выполнены условия Если в (7.2) используется две точки (k = 2), то получается определение отрезка (7.1). С применением выпуклой линейной комбинации точек, можно дать ещё одно, эквивалентное определение выпуклости. Множество V R выпуклым, если вместе с любой системой из k точек содержит и их выпуклую линейную комбинацию (7.2).

Рассмотрим отрезок (7.1) в векторном пространстве. У него две угловые точки: x 1, x 2 R n. Выпуклая линейная комбинация этих точек образует весь отрезок. Рассмотрим три точки x 1, x 2, x 3 R n и их выпуклую линейную комбинацию треугольником с вершинами в точках x 1, x 2, x 3 R n. Эти же точки являются угловыми для треугольника. Более того, треугольник и есть выпуклая линейная комбинация угловых точек, вершин треугольника. Примеры отрезка (7.1), треугольника (7.3) позволяют дать Определение 7. 3. Выпуклым многогранником в векторном пространстве R n называется выпуклая линейная комбинация k точек x 1, x 2, …, x k R n. Угловые точки этого множества называются его вершинами.

Выпуклый многогранник порождается своими угловыми точками или вершинами: отрезок – двумя вершинами (7.1), треугольник – тремя вершинами (7.3), n – угольник – n вершинами (7.2).

Выпуклая оболочка из k точек может быть обобщена на более широкое понятие – выпуклая оболочка множества в векторном пространстве. Пусть задано множество M R n (конечное или бесконечное) Существует бесконечное число выпуклых множеств в векторном пространстве, содержащих M.

Рассмотрим пересечение этих выпуклых множеств. Во – первых, по теореме о пересечение такое множество выпукло, во – вторых, оно содержит данное множество M. Это пересечение является наименьшим множеством с указанными двумя свойствами и оно определяется по M однозначно. Это пересечение называется выпуклой оболочкой множества M в векторном пространстве R n и обозначается co (M). Отметим, что выпуклая оболочка множества совпадает с множеством всех выпуклых комбинаций точек из M, как это определено в (7.2). В этом случае можно ограничиться и конечным числом точек из множества M. Всё это представлено в Теорема (Каратеодори). Пусть M множество в R. Тогда В этом случае говорят, что каждая точка их co(M) представима в виде линейной комбинации не более чем n+1 точки из M. Если множество М компакт, то и множество co(M) также является компактом.

Выпуклые множества и многогранники используются при изучении решений систем линейных неравенств. Рассмотрим линейное уравнение Множество его решений называется гиперплоскостью в векторном пространстве R. В частном случае при n = 2 гиперплоскость в (7.5) геометрически представляется прямой на плоскости. При n = 3 эта гиперплоскость есть плоскость в пространстве.

Рассмотрим линейное неравенство, соответствующее (7.5) Множество точек, удовлетворяющее (7.6), называется полупространством, на которое делится всё пространство гиперплоскостью (7.5), включая и эту гиперплоскость. Отметим, что гиперплоскость и полупространство являются выпуклыми множествами.

Перейдём к системе m линейных неравенств Решение каждого неравенства в (7.7) является полупространством, т.е. выпуклым множеством. Тогда, согласно теореме о пересечении выпуклых множеств, множество решений такой системы также выпукло. Если это решение ограничено, то оно является многогранником и выпуклой оболочкой конечной системы угловых точек.

Пример 7.1. Решить графически систему неравенств. Найти угловые решения. Если множество решений ограничено, то указать общее решение На плоскости каждому неравенству соответствует полуплоскость, её граница – прямая линия. Для построения полуплоскостей запишем уравнения прямых в отрезках Соответствующие прямые – границы построены на рисунке 7.2.

Для каждой из них штриховкой выделена полуплоскость, являющаяся решением соответствующего неравенства. Решение системы неравенств есть выпуклое множество - пересечение полуплоскостей. Из рисунка видно, что пересечение пяти полуплоскостей является выпуклый четырёхугольник АВСD.

Найдём координаты его вершин. Они определяются, как пересечения сторон Согласно результатам параграфа множество всех решений системы неравенств является четырёхугольник АВСD.

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

Ответ: угловые точки общее решение Кратко решение записывается в форме выпуклой оболочки Пример 7.2. Решить графически систему неравенств. Найти угловые решения. Если множество решение неограничено, то указать неограниченную последовательность решений На плоскости каждому неравенству соответствует полуплоскость, её граница – прямая линия. Границы полуплоскостей представлены в форме (7.8). Полуплоскости для решения системы данной системы неравенств – на рисунке 7.3 и выделены штриховкой. Решение есть выпуклое множество – пересечение полуплоскостей. Из рисунка видно, что пересечение пяти полуплоскостей является неограниченное множество с границей - ломанной KGBEFL. Найдём координаты угловых точек. Они определяются, как пересечения прямых или из рисунка 7.3. Это точки с координатими K (12,0), G (8,0), B (40, 24 ), L(12,5).

Неограниченное множество решений выделено штриховкой на рис. 7.3. У этого множества четыре угловые точки: G, B, E, F.

Но всё множество решений уже не представляется выпуклой комбинацией угловых точек. На рисунке 7.3 указана бесконечная неограниченная последовательность точек из множества решений системы неравенств. Это множество T = {T1(4, 2), T2(5, 2) T3(6,2),…..} = {Tn(n+3, 2) n = 1, 2, …} Ответ: угловые точки неограниченная последовательность решений Задачи для самостоятельного решения Задача 7.1. Решить графически систему неравенств. Найти угловые решения. Если множество решений ограничено, то указать общее решение Задача 7.2. Решить графически систему неравенств. Найти угловые решения. Если множество решение неограниченно, то указать неограниченную последовательность решений §8. Линейное программирование: графический метод Важное место в математике, а особенно в приложениях математики к реальным практическим задачам, занимает математическое программирование. Это математическая дисциплина, посвящена теории и методам решения задач о нахождении экстремумов функций на множествах конечномерного векторного пространства, определяемых линейными и нелинейными ограничениями (равенствами и неравенствами).

Если в задаче математического программирования целевая функция линейная и ограничения в форме равенств и неравенств заданы линейными функциями, то это задача линейного программирования. Такие задачи имеют огромную область применения, не в последнюю очередь потому, что “любой процесс в первом приближении является линейным”. Теория таких задач обстоятельно разработана [8, 9, 10]. Особенно большое значение имеет этот раздел для изучения конечных игровых задач [2, с. 83c. 28-32]. Далее будет представлены элементы теории линейного программирования, в той мере, как это потребуется для изучения игровых задач.

Рассматривается задача максимизации на множестве заданном ограничениями – неравенствами Функция f (x) в (8.1) называется целевой функцией.

Ограничения – неравенства в (8.2) и (8.3) определяют область допустимых значений X R m. Содержательно задача линейного программирования состоит в поиске x* X, доставляющего наибольшее значение функции f (x ), когда x X. Существуют различные формы представления задачи линейного программирования в зависимости от вида ограничений для области допустимых значений. Говорят, что в (8.1) – (8.3) задана стандартная задача линейного программирования.

Если в задаче линейного программирования разыскивается x* X, доставляющий наименьшее значение функции f (x ), когда x X., то получается задача минимизации на множестве заданном ограничениями – неравенствами.

Существование решения в задаче линейного программирования следует из Теорема (Вторая теорема Вейерштрасса). Пусть в задаче математического программирования область допустимых значений X R m является компактом, а целевая функция f (x) непрерывна на X. Тогда Так как линейная функция непрерывна, то из теоремы следует условие существования решения в задаче линейного программирования.

Следствие. Пусть в задаче линейного программирования (8.1) – (8.3) область допустимых решений X R m непуста и ограничена. Тогда Рассмотрим графический метод решения задачи линейного программирования. Этот метод применим, когда X R 2 или задача сводится к задаче с двумя переменными.

Графический метод разбивается на два этапа.

Первый этап. Используя условия (8.2) – (8.3) на плоскости строится область допустимых решений X R2.

Второй этап. На плоскости строятся прямые - линии уровня c1 x1 + c 2 x 2 =, R. В точках касания линий уровня с областью X достигаются наибольшие и наименьшие значения функции f.

Отметим, что линия уровня касается области X, если 1) область и прямая имеют общие точки;

2) область расположена по одну сторону от прямой – линии уровня/ Пример 8.1. Решить задачу линейного программирования графически В задаче линейного программирования extr означает единый термин для экстремума, т.е. для нахождения максимума и минимума функции. Построим область X на плоскости. Она расположена в первой четверти ( x1 0, x 2 0) и ограничена прямыми m и n. Для удобства построения запишем уравнения этих прямых в отрезках.

Здесь a1 = 30, a2 = 10 пересечение прямых m и n с осью OX, а b1 = 10, b2 = 20 – пересечение с осью OY. Соответствующий чертёж представлен на рис.8.1. Здесь m представлена прямой АВ, а n представлена прямой ДВ.

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

Построим прямые уровня, которые касаются области X.

Таких прямых две Прямая l1 касается области X в точке О(0, 0), а прямая l 2 - в точке В(6, 8). Отметим, что координаты точки В являются решением системы уравнений Точки касания О(0, 0) и В(6, 8) определяют решение задачи линейного программирования. Именно, Пример 8.2. Решить задачу линейного программирования графически Постоим область X на плоскости. Она расположена в первой четверти, т.к. x1 0, x 2 0, и ограничена прямыми m, n, p, q. Для удобства построения приведём уравнения этих прямых в отрезках.

Здесь a1 = 5, a2 = 10, a3 = 4, a4 = 3, пересечение прямых m, n, p, q с осью OX, а b1 = 4, b2 = 3, b3 = 8, b4 = 10 – пересечение с осью OY. Соответствующий чертёж представлен на рис.8.2. Здесь m представлена прямой СF, n представлена прямой DE, p представлена прямой BG, и, наконец, q представлена прямой AH.

Каждая прямая, как решение соответствующего неравенства, определяет полуплоскость. Для всех прямых CF, DE, BG, AH это будут полуплоскости, содержащие начало отсчёта O. Тогда область допустимых значений в задаче линейного программирования представляется пятиугольником OALKE.

Построим прямые уровня, которые касаются области X. Таких прямых две Прямая l1 касается области X в точке О(0, 0), а прямая l 2 - в точке K(2, 2,4). Отметим, что точка K является пересечением прямых m, n и её координаты аналитически находятся как решение системы уравнений Решение системы x1 = 2, x 2 = 2,4, значит K(2, 2,4). Точки касания K(2, 2,4) определяют решение задачи линейного программирования. Именно, Отметим, что в этой задаче в определении допустимого множества X не использовалась ограничение Граница соответствующей полуплоскости не является частью границы множества X. Если удалить это ограничение из условия задачи линейного программирования, то результат (оптимальное решение) не изменится. Это похоже на аналогичное явление в теории матричных игр, именно, на удаление строго доминируемой стратегии.

Задачи для самостоятельного решения Задача 8.1. Предприятие производит два вида продукции:

П 1, П 2, которые потом поступают в оптовую продажу. В производстве продукции используются два вида сырья – А, В.

Максимальные запасы сырья составляют 9 и 13 единиц соответственно. Расход сырья на единицу продукции вида П1, П представлен в таблице 8.1 Оптовые цены на продукцию П1 равны 3 руб., для продукции П2 – 4 руб. Какое количество продукции каждого вида должно производить предприятие, чтобы доход от реализации продукции был максимальным?

Ответ: x* = (4,2; 0,2), f* = 13,2.

Задача 8.2. Решить графически задачу линейного программирования, с ограничениями в форму равенств §9. Двойственная задача линейного программирования Вместе с задачей линейного программирования изучается тесно с ней связанная двойственная или сопряжённая задача.

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

Пусть рассматривается стандартная прямая задача линейного программирования (8.1) – (8.3).

Двойственной ей является задача Особенно удобно запоминать прямую и двойственную задачи линейного программирования, записанные в матричной форме. Задачу (8.1) – (8.3) можно представить Аналогично для задачи (9.1) – (9.3) верна запись Здесь индексы у матриц – их размерности, т.е. число строк, затем число столбцов. Векторы X m, Yn представлены столбцовыми матрицами. Знак T – транспонирование.

Для двойственной задачи условия (9.2) и (9.3) определяют область допустимых значений Y Rn. Целевая функция fd(y) задаёт прямые уровня в пространстве Rn. Значит, для двойственной задачи можно применять графический метод решения. Следует помнить, что, несмотря на формальное сходство задачи (8.1) – (8.3) и (9.1) – (9.3), их решения находятся, вообще говоря, в разных пространствах, т.е. x* X Rm и y* YRn.

По аналогичной схеме можно определить двойственную задачу для задачи линейного программирования (на минимизацию целевой функции) (9.1) – (9.3). В этом случае двойственная задача будет задача линейного программирования (на максимизацию целевой функции), представленная в (8.1) – (8.3). В этом смысле можно говорить о задаче (8.1) – (8.3) и о задаче (9.1) – (9.3), как о паре двойственных (сопряжённых) задач линейного программирования.

Прямая (8.1) – (8.3) и двойственная (9.1) – (9.3) задачи линейного программирования (пара двойственных задач) имеют общие свойства:

1°. Число неизвестных в первой задаче равно числу ограничений во второй задаче;

2°. Матрица коэффициентов системы ограничений получается одна из другой путём транспонирования;

3°. Неравенства в системах ограничений имеют противоположный смысл;

4°. Свободные члены системы ограничений одной задачи становятся коэффициентами целевой функции и наоборот.

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

Аналогичные построения для двойственной задачи можно провести для задач в канонической форме (ограничения в форме равенств) и в общей форме (ограничения в форме равенств и неравенств).

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

Двойственная задача в матричной форме записи представлена в (9.7), если прямая задача задана в (9.6). Решим прямую задачу.

Область допустимых значений X представлена на рис.9.1. Область расположена в первой четверти и ограничена прямыми На рис.9.1 эта область есть четырёхугольник ОАВС. Через точку В проходит линия уровня, которая определяет решение.

Отметим, что точка В является пересечением прямых a, b и её координаты аналитически находятся как решение системы уравнений Тогда В(1/9, 2/ 9). Значит Аналогично находится область допустимых значений Y в двойственной задаче. Область расположена в первой четверти, ограничена прямыми и не содержит начало координат. Область Y не ограничена и изображена на рис.9.2. У этой области только одна касательная из множества линий уровня. Она проходит через точку Е, координаты которой есть решение системы двух уравнений, т.е.

уравнений прямых с, d. Уравнение касательной y1 + y 2 = 1 3.

Тогда двойственная задача имеет решение Пара двойственных задач линейного программирования имеет общие свойства, представленные в пунктах 1° - 4°. Это свойства связаны с представлением задач. Имеется более глубокая связь, обусловленная зависимостью решений. Приведём соответствующую Теорема (теорема двойственности). Рассматривается пара двойственных задач линейного программирования: прямая (8.1) – (8.3) и двойственная (9.1) – (9.3). Если одна из них имеет оптимальное решение, то и другая имеет решение. Экстремальные значения целевых функций совпадают. Если в одной из задач нет оптимального решения по причине неограниченности области допустимых решений, то в двойственной ей задаче область допустимых решений пуста. Для последнего верно и обратное утверждение.

Свойства прямой и двойственной задачи линейного программирования рассматриваются в учебниках и пособиях по линейному программированию [9, с.239 – 244; 10, с.72 –81]. Вообще теория двойственности является сердцевиной линейного (и более широко – математического) программирования.

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

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

Можно выделить два подхода к её изучению. Один из них связан с максимизацией прибыли. Другой основан на минимизации издержек.

Двум этим подходам соответствует пара двойственных задач линейного программирования. Первый подход состоит в том, чтобы составить такой план выпуска продукции x = (x1, x2, …, xm), при котором прибыль (выручка) от реализации продукции будет максимальной при условии, что потребление ресурсов по каждому виду продукции не превзойдёт имеющихся запасов. Этот взгляд соответствует прямой задаче линейного программирования.

Второй подход состоит в том, что выбирается такая система цен (оценок) для ресурсов y = (y1, y2, …, yn), при которой общие затраты на ресурсы будут минимальны при условии, что затраты на ресурсы при производстве каждого вида продукции будут не менее прибыли (выручки) от реализации этого вида продукции.

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

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

Пример 9.2. Решить задачу линейной программирования с использованием двойственной задачи Графически эту стандартную задачу решить не удаётся, т.к.

число неизвестных n = 4 > 2. Запишем для неё соответствующую двойственную задачу В этой задаче только одна переменная – y1. более того, здесь область допустимых значений состоит из одной точки, числа y1 = 1. Эта точка определяет оптимальное решение двойственной задачи. Именно, По теоремы двойственности f max = f ( x*) = 1. Осталось подобрать допустимое (с неотрицательными координатами) x* векторов, например, x* = ( x1, x 2, x3, x 4 ) = (0, 1, 0, 0) X. По теореме двойственности получили одно из решений прямой задачи Отметим, что в этой задаче существуют и другие решения задачи максимизации.

Пример 9.3. Решить задачу линейной программирования с использованием двойственной задачи Графически эту стандартную задачу решить не удаётся, т.к.

число неизвестных n = 4 > 2. Перепишем данную задачу в стандартной форме (как задачу минимизации) В этой задаче по-прежнему четыре переменные, именно y1, y2, y3, y4. Запишем двойственную задачу максимизации (8.1) – (8.3).

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

Рассмотрим линии уровня, имеющие вид 2x1 + x2 = с, где с– любое действительное число. Максимальное решение реализуется в точке С(9, 1). Это общая точка шестиугольника ABCDEF и линии уровня p: 2x1 + x2 = 19. Тогда решение двойственной задачи для задачи из данного примера будет По теореме двойственности имеем условие для исходной задачи Несложно подобрать решение y* = (0, 1, 1, 0). Таким образом, получаем решение исходной задачи Задачи для самостоятельного решения Задача 9.1 Для прямой задачи линейного программирования записать двойственную задачу и решить их обе графически Задача 9.2. Решить задачу линейной программирования с использованием двойственной задачи Задача 9.3. Решить задачу линейной программирования с использованием двойственной задачи §10. Линейное программирование: симплексный метод Успешное применение задачи линейного программирования во многом связано с удобным вычислительным методом для её решения – с симплексным методом. Суть метода состоит в последовательном улучшении допустимого вектора, претендующего на роль решения. За конечное число итераций находится решение или устанавливается его отсутствие.

Рассмотрим задачу линейного программирования в стандартной форме (8.1) – (8.3) и разберём её решение симплекс – методом. Этот метод применяется и для задач лиейного программирования в других формах, но изложение материала ориентировано на решение игровых задач, в первую очередь матричных игр. В этом случае соответствующая задача линейного программирования записывается в стандартной форме.

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

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

* Определять (первоначальное) допустимое решение.

* Проверять допустимое решение на оптимальность.

* Переходить к лучшему (точнее, не худшему) допустимому решению.

От задачи в стандартной форме переходим к канонической форме задачи линейного программирования. Такая задача отличается от (8.1) – (8.3) тем, что ограничения в форме неравенств из (8.2) представляются в форме равенств. Задача линейного программирования в канонической форме имеет вид Будем считать, что числа bj, j = 1,…,n неотрицательны. Если это не так, то умножим равенство из (10.2) на –1. Переход от стандартной формы к канонической форме можно осуществлять следующим образом.

Пусть задана задача (8.1) – (8.3), значит m определено.

Перейдём к (10.1) – (10.3) по формулам В этом случае условие (10.3) выполнено. Формально, получили задачу (10.1) – (10.3). Область допустимых решений в задаче (8.1) – (8.3) есть множество X Rm, в задаче (10.1) – (10.3) это множество Y R m+n. Вообще говоря, X Y, но из определения коэффициентов в (10.1) – (10.3) следует, что проекция множества Y на пространство R m совпадает с множеством X. В этом смысле задачи (8.1) – (8.3) и (10.1) – (10.3) равносильны.

Определим первоначальное допустимое решение задачи (10.1) – (10.3). Нетрудно видеть, что таким решением будет x(0) = (0, …, 0, b1, …, bn) Y Rm+n, что соответствует нулевому решению задачи (8.1) – (8.3).

Выполним проверку на оптимальность. Если для (10.1) выполнены условия cj 0, j = 1,…,m+n, то x(0) = (0, …, 0, b1, …, bn) является оптимальным решением. Если в (10.1) найдётся сj* > 0 и все a ij* 0, i = 1,…,n, то x (0) = (0, …, 0, b 1, …, b n ) является оптимальным решением. И, наконец, если найдётся сj* > 0 и найдётся aij* > 0, то от допустимого решения x(0) = (0, …, 0, b1, …, bn) следует перейти к новому решению x(1) (выполнить первую итерацию) и уже его проверять на оптимальность.

Для нового решения x (1) Y R m+n все повторяется. В зависимости от результатов проверки либо получают окончательный результат, либо переходят к следующей итерации.

Допустимое решение, полученное на каждой итерации, соответствует вершине многогранной области.

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

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

Пример 10.1. Решить задачу линейного программирования симплекс - методом Задача задана в стандартной форме. Перепишем её в равносильной канонической форме Данные полученной задачи заносим в симплекс таблицу.

В таблице 10.1 первая и вторая строки соответствуют ограничениям задачи, последняя строка – функции цели. Это оценочная строка. Значение функции цели берём 0. Выделяем базисные переменные. Эта переменная находится в столбце для которой имеется одна единица, остальные нули.

В столбце “Базис” отмечаем одноимённые переменные в той строке, где расположена эта единственная единица. Остальные переменные называются свободными.

По заполненной симплекс таблице определяем решение, соответствующее этой (нулевой) итерации. Свободные переменные равны 0. Базисные переменные и значение функции находим из таблицы. Они представлены в столбце “Значение”.

Отметим, что значение функции цели берём с противоположным знаком. Итак, x(0) = (0, 0, 30, 20), f (0) =0.

В оценочной строке имеются положительные числа. Значит, решение можно улучшить. Выберем наибольшее из положительных чисел. Если таких чисел несколько – берём любое из них. Соответствующий столбец называют ведущим. По ведущему столбу и столбцу “Значения” определяем оценку для каждой строки. Число из столбца “Значение” делим на соответствующее число из ведущего столбца. Получаем оценку строки. По условию задачи это положительное число. Объявляем ведущей строкой ту, оценка у которой наименьшее положительное число. В таблице 10.2 ведущая строка и столбец выделены цветом. На их пересечении находится ведущий элемент.

В нашем случае это число 2.

Переходим к первой итерации. Её суть состоит в том, чтобы свободную переменную x1 сделать базисной, а базисную переменную x4 - свободной. В таблице выполняем преобразования аналогичные элементарным строчным преобразованиям в методе Гаусса при решении системы линейных уравнений. В результате преобразований получаем Из таблицы находим базисные переменные и значение функции x(1) = (10, 0, 20, 0), f (1) =10. Этот результат можно проверить. Полученные результаты должны удовлетворять функции цели в канонической (стандартной) задаче линейного программирования. Действительно, 1 10 + 1 0 + 0 20 + 0 0 = получили верное равенство.

В оценочной строке таблицы 10.2 имеется положительное число, значит можно перейти к следующей итерации. В таблице 10.2 цветом выделены ведущий столбец и ведущая строка. Суть второй итерации состоит в том, чтобы свободную переменную x преобразовать в базисную, а базисную переменную x3 сделать свободной. Преобразования проводим по методу Гаусса.

Результаты представлены в таблице 10.3.

Из таблицы находим базисные переменные и значение функции x(2) = (6, 8, 0, 0), f (1) =14. Этот результат можно проверить.

Действительно, 1 6 + 1 8 + 0 0 + 0 0 = 14 получили верное равенство.

В оценочной строке нет положительных чисел. Значит симплекс – метод завершён. Результат последней итерации даёт ответ канонической задачи. По нему можно записать решение исходной стандартной задачи линейного программирования Рассмотренный вариант записи решения в симплекс – таблице имеет одно очень важное преимущество. В последней таблице представлено решение двойственной задачи к стандартной задаче линейного программирования. Напомним, что целевая функция для неё Тогда по теореме их §9 значение целевой функции в двойственной задаче f min = f ( x* ) = 1 4. Выберем базисные переменный при постановке канонической задачи. В таблице 10.1 это переменные x3, x4. В последней симплекс – таблице (таблица 10.3) в оценочной строке этим выделенным переменным соответствуют решения двойственной задачи. Координаты двойственного решения из таблицы следует взять с противоположным знаком. Значит y 1 = 0,2, y2 = 0,4. Действительно, подставив найденные значения в функцию цели двойственной задачи, получим верное равенство Тогда по теореме из §9 можно записать решение двойственной задачи Таким образом, симплекс – метод, рассмотренный выше, позволяет одновременно решать прямую и двойственную задачу линейного программирования.

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

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

Выделяем базисные переменные. Это переменные, для которых столбцы образуют единичную матрицу. Базис образуют x4, x5, x6.

Остальные переменные являются свободными.

По заполненной симплекс таблице определяем решение, соответствующее этой (нулевой) итерации. Свободные переменные равны 0. Базисные переменные и значение функции находим из таблицы. Они представлены в столбце “Значение”.

Отметим, что значение функции цели берём с противоположным знаком. Итак, x(0) = (0, 0, 0, 1, 1, 1), f (0) =0.

В оценочной строке имеются положительные числа. Значит, решение можно улучшить. Выберем наибольшее из положительных чисел. Если таких чисел несколько – берём любое из них, например, первое. Соответствующий столбец называем ведущим. По ведущему столбу и столбцу “Значения” определяем оценку строки.

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

В нашем случае это число 4.

Переходим к первой итерации. Её суть состоит в том, чтобы свободную переменную x 1 сделать базисной, а базисную переменную x5 - свободной. В таблице выполняем преобразования аналогичные элементарным строчным преобразованиям в методе Гаусса при решении системы линейных уравнений. В результате преобразований получаем Из таблицы 10.5 находим базисные переменные (свободные переменные равны 0) и значение функции. Получаем x(1) = (1/4, 0, 0, 3/4, 0, 1/2), f (1) =1/4. Этот результат можно проверить. Полученные результаты должны удовлетворять функции цели в канонической (стандартной) задаче линейного программирования. Действительно 1 1 + 1 0 + 1 0 = 1, т.е. получили верное равенство.

В оценочной строке имеется положительное число, значит можно перейти к следующей итерации. В таблице 10.5 цветом выделены ведущий столбец и ведущая строка. Суть второй итерации состоит в том, чтобы свободную переменную x2 преобразовать в базисную, а базисную переменную x 6 сделать свободной. Преобразования проводим по методу Гаусса. Результаты представлены в таблице 10.6.

Из последней таблицы находим базисные переменные и значение функции цели. Получаем x(2) = (1/4, 1/6, 0, 5/37, 0, 0), f (2) =5/12. Этот результат можно проверить. Действительно, 1 1 4 + 1 1 6 + 1 0 = 512. И так мы, получили верное равенство.

В оценочной строке есть одно положительных чисел. Значит можно перейти к следующей итерации. В таблице 10.6 цветом выделены ведущий столбец и ведущая строка. Суть третьей итерации состоит в том, чтобы свободную переменную x преобразовать в базисную, а базисную переменную x4 сделать свободной. Преобразования проводим по методу Гаусса.

Результаты представлены в таблице 10.7.

В оценочной строке нет положительных чисел. Таблица 10. будет последней. По нему можно записать решение исходной стандартной задачи линейного программирования Выпишем из проверочной строке решение двойственной задачи Задачи для самостоятельного решения Задача 10.1. Для задачи линейного программирования записать двойственную задачу и решить их обе графически и симплексным методом Задача 10.2. Решить задачу линейного программирования симплекс - методом Задача 10.3. Решить задачу линейного программирования симплекс - методом §11. Матричная игра и задачи линейного программирования Задачи линейного программирования (прямая и двойственная) тесно связаны с матричной игрой, т.е. с конечной антагонистической игрой.

Пусть игра задана платёжной матрицей Am n = (aij), i = 1,…,m, j = 1,…,n. Будем считать, что все элементы этой матрицы положительны. Если это не так, то в матрице А найдутся отрицательные числа. Выберем среди их наименьшее. Пусть это будет число -k. Прибавим во всем элементам матрицы число k+1. Тогда все элементы матрицы станут положительными. В новой задаче с матрицей, составленной их положительных элементов, седловая точка будет такая же, как у исходной матрицы. Если цену этой новой игры уменьшить на k+1, то получим цену первоначальной игры. В дальнейших рассуждениях, не уменьшая общности, будем считать, что все элементы матрицы А положительны.

В матричной игре первого игрока обозначим W, второй игрок – V. Игрок W обладает m чистыми стратегиями, именно, Wi = (0,…, 1,…,0)T, i = 1,…,m и единица расположена на месте i.

Игрок V располагает n чистыми стратегиями Vj = (0,…, 1,…,0)T, j = 1,…,n и единица расположена на месте j. Будем определять оптимальные стратегии первого и второго игроков Здесь координаты векторов есть вероятности выбора ими соответствующих чистых стратегий. Про такие стратегии известно, что Оптимальная стратегия P обеспечивает игроку W средний выигрыш, не меньше, чем цена игры, при любой стратегии второго игрока. В том числе и против каждой чистой стратегии второго игрока. Для n чистых стратегий второго игрока получаем т.е. выполнены неравенства Каждое из полученных неравенств разделим на, при этом можно считать, что > 0. Введём новые переменные Тогда (11.3) примет вид Разделим равенство (11.1) на цену игры > 0. Тогда, используя обозначения (11.4), получаем Максимизация цены игры величины 1/. Поэтому задачу определения xi, i = 1,…,m, можно переформулирована следующим образом.

Определить значения переменных xi 0, i = 1,…,m, так, чтобы они удовлетворяли линейным ограничениям (11.5) и при этом линейная функция обращалась в минимум.

Это задача линейного программирования на минимизацию функции Z. Решая задачу (11.5), (11.7) для неотрицательных xi 0, i = 1,…,m, можно найти величину 1/ и, значит, цену исходной игры. По решению задачи линейного программирования (из формул (11.4)) определяется оптимальная стратегия первого игрока.

Рассуждения для второго игрока аналогичны. Оптимальная стратегия Q обеспечивает игроку V средний выигрыш, не больше, чем цена игры, при любой стратегии первого игрока. В том числе и против каждой чистой стратегии первого игрока. Для m чистых стратегий первого игрока получаем и выполнены неравенства Каждое из полученных неравенств разделим на, при этом можно считать, что > 0. Введём новые переменные Тогда (11.7) примет вид Разделим равенство (11.2) на цену игры > 0. Тогда, используя обозначения (11.9), получаем Минимизация цены игры эквивалентна максимизации величины 1/. Поэтому задачу определения yi, i = 1,…,n, можно переформулирована следующим образом.

Определить значения переменных yi 0, i = 1,…,n, так, чтобы они удовлетворяли линейным ограничениям (11.10) и при этом линейная функция обращалась в максимум.