Введение в теорию игр

Введение в теорию игр В коммерческой деятельности часто приходится принимать решения, учитывая множество факторов различной природы. Причем, спецификация коммерческой деятельности такова, что учитываемые при принятии решений факторы часто обладают свойством неопределенности, т.к. нельзя заранее определить точно, каково будет значение того или иного фактора или показателя. Следовательно, и результат принятия решения будет обладать свойством неопределенности. Неопределенность значений, управляемых факторов приводит к тому, что рекомендации по решению проблемы не могут быть столь же четкими и однозначными как в случаях полной определенности. В процессе принятия решений появляются возможные варианты решений. Поэтому можно считать, что принятие решения состоит в выборе наилучшего варианта из имеющихся. Для решения любой проблемы, независимо от ее характера, существенным является вопрос: кто должен быть поставлен перед проблемой? Т.е. должно существовать некое лицо, принимающее решение. Лицо, принимающее решение – это некий реально существующий индивидуум (или группа), которую не устраивает состояние дел или перспектива их будущего состояния, и который имеет полномочия действовать так, чтобы это состояние изменилось. Разработаны специальные математические методы, предназначенные для обоснования решений в условиях неопределенности. В простых случаях эти методы позволяют найти множество решений и выбрать из них оптимальное. В более сложных случаях эти методы дают вспомогательный материал, позволяющий глубже разобраться в сущности явлений и оценить каждое из возможных решений с различных точек зрения, взвесить все преимущества и недостатки и принять если не единственно правильное, то по крайней мере близкое к оптимальному решению. При выборе решения в условиях неопределенности всегда неизбежен элемент произвола, а значит и риска. Недостаточность информации всегда опасна и за нее приходится платить. Поэтому в условиях сложной ситуации необходимо представить варианты решения и их последствий в такой форме, чтобы сделать произвол выбора менее сильным, а риск – минимальным. Задачами о принятии решений в условиях полной или частичной неопределенности занимается теория игр и статистических решений. В коммерческой деятельности часто приходится принимать решения в условиях противодействия другой стороны, которая может преследовать противоположные или иные цели, добиваться других путей достижения цели, препятствовать теми или иными действиями или состояниями внешней среды достижению намеченной цели. Причем эти противодействия противоположной стороны могут носить пассивный или активный характер. В этих случаях приходится учитывать возможные варианты поведения противоположной стороны, ответные действия, возможную реакцию. Возможные варианты поведения обеих сторон, их исходов для каждого сочетания альтернатив математической модели, и состояний называемой можно игрой. представить Если в в виде качестве противоположности выступает неактивная, пассивная сторона, которая явно активно не противодействует достижению намеченной цели, то такие игры называются играми с природой. В других ситуациях противоположная сторона активно, сознательно может противостоять достижению намеченной цели. В подобных случаях происходит столкновение противоположных интересов. Такие ситуации называются конфликтными, а принятие решений в конфликтных ситуациях затрудняется из-за неопределенности поведения противника. Известно, что противник сознательно стремится предпринять наименее выгодные для вас действия, чтобы обеспечить себе наибольший успех. Неизвестно, в какой мере противник умеет оценивать обстановку и возможные последствия, как он оценивает ваши возможности и намеренья. Обе стороны конфликта не могут точно предсказать взаимные действия. Несмотря на такую неопределенность, принимать решение приходится каждой стороне конфликта. Теория игр – это математическая теория конфликтных ситуаций. Основными ограничениями этой теории являются предположения о полной («идеальной») разумности противника и принятие при разрешении конфликта наиболее осторожного «перестраховочного» решения. Основные понятия теории игр Конфликтующие в игре стороны называются игроками, одна реализация игры – партией, исход игры – выигрышем или проигрышем. Развитие игры во времени происходит последовательно, по этапам, называемым ходами. Ходом в теории игр называют выбор одного из предусмотренных правилами игры действий и его реализацию. Ходы бывают личные и случайные. Личным ходом называют сознательный выбор игроком одного из возможных вариантов действия и его осуществление. Случайным ходом называют выбор, осуществляемый не волевым решением игрока, а каким-либо механизмом случайного выбора. Одним из основных понятий теории игр является стратегия. Стратегией игрока называют совокупность правил, определяющий выбор варианта действия при каждом личном ходе этого игрока в зависимости от ситуации, сложившейся в процессе игры. Оптимальной стратегией игрока называется такая стратегия, которая при многократном повторении игры, содержащей личные и случайные ходы, обеспечивает игроку максимально возможный средний выигрыш (минимально возможный средний проигрыш). В большинстве конфликтных ситуаций при выборе разумной стратегии приходится принимать во внимание не один, а несколько показателей. Причем стратегия, оптимальная по одному показателю, не обязательно будет оптимальной по другому. В зависимости от причин, вызывающих неопределенность исходов игры делятся на следующие основные группы. 1. Комбинаторные игры, в которых правила дают возможность каждому игроку проанализировать все разнообразие своего поведения и, сравнив эти варианты, избрать тот из них, который ведет к наилучшему для этого игрока исходу. Неопределенность исхода связана обычно с тем, что количество возможных вариантов поведения слишком велико, практически игрок не в состоянии перебрать все ходы и проанализировать. 2. Азартные игры, в которых исход оказывается неопределенным в силу влияния различных случайных факторов. 3. Стратегические игры, в которых неопределенность исходов вызвана тем, что каждый из игроков, принимая решение о выборе предстоящего хода, не знает какой стратегии будут придерживаться другие участники игры. Если в игре сталкиваются интересы двух сторон, то игра называется парной, если более двух, то множественной. Участники множественной игры могут образовывать коалиции. Различают игры и по сумме выигрыша. Игра называется игрой с нулевой суммой, если каждый игрок выигрывает за счет других, а сумма выигрыша с одной стороны равна сумме проигрыша с другой. В парной игре с нулевой суммой интересы игроков прямо противоположны. Парная игра с нулевой суммой называется антагонистической игрой. Игры в которых выигрыш одного игрока и проигрыш другого не равны между собой называются играми с ненулевой суммой. В зависимости от числа возможных стратегий игры делятся на конечные и бесконечные. Игра называется конечной, если она имеет только конечное число стратегий. Игра называется бесконечной, если хотя бы у одного игрока имеется бесконечное число стратегий. По количеству ходов, которые делают игроки для достижения своих целей игры делятся на одношаговые и многошаговые. Одношаговые игры заключаются в том, что игрок выбирает одну из доступных ему стратегий и делает единственный ход. В многошаговых играх игроки, для достижения своих целей, делают последовательно ряд ходов, которые могут ограничиваться правилами игры либо могут продолжаться до тех пор, пока у одного из игроков не останется ресурсов для продолжения игры. Матрица игры Рассмотрим задачу о взаимозачетах. Для открытия дела необходимы средства, которые могут быть собственными и/или заемными. Предприятие создается с целью получать прибыль (доход) от своей деятельности, а для этого необходимо вложить (инвестировать) капитал в основные средства (в помещение оборудование), в оборотные средства (в материалы, товары), в рабочую силу. В процессе деятельности предприятия происходит изменение средств и источников этих средств т.е. происходит движение средств и их источников. При этом в любой момент времени будет выполняться закон сохранения средства-источники подразделяются на два средств. вида Т.к. собственные источники (капитал) и средств заемные (обязательства). Обязательства могут иметь различные формы: кредиты банков, акции, облигации, векселя, векселя, товары, отданные на реализацию или консигнацию. Все юридические или физические лица являются кредиторами предприятия и вправе рассчитывать на получение доходов (дивидендов) от совместной деятельности. Описание деятельности предприятия проводят на языке бухгалтерского учета. Бухгалтерский учет позволяет выделить финансовый результат – прибыль предприятия путем подсчета разности доходов и расходов за определенный период. Предприниматели А, В и С заключили договор для совместного проведения цепочки посреднических операций на условиях финансирования своей части. Взаимные переплетения трех вариантов коммерческих операций взаимозадолженностей, послужило поводом зарегистрированных к бухгалтером хронологическом порядке. № Долг Сумма К получению 1 А К оплате В 1000 образованию в 2 А В 2000 3 А С 500 4 В А 800 5 В С 400 6 С А 1500 7 С В 700 8 В С 400 Итого 7300 Всего 6 вариантов задолженностей при трех участниках: АВ, АС, ВА, ВС, СА, СВ Просуммируем одноименные варианты АВ=1000+2000=3000 ВС=400+400=800 Матрица взаимных задолженностей № Долг Сумма К получению К оплате 1 А В 3000 2 А С 500 4 В А 800 5 В С 800 6 С А 1500 7 С В 700 Итого 7300 Задача заключается в том, чтобы к концу расчетного периода произвести окончательные расчеты между участниками игры. При расчетах между А и В В→А 3000, А→В 800. Сальдо ΔΣ(АВ)=3000-800=+2200 (В→А при окончательном расчете). При расчетах между А и С С→А 500, А→С 1500. Сальдо ΔΣ(АС)=5001500=-1000 (А→С при окончательном расчете). При расчетах между В и С С→В 800, В→С 700. Сальдо ΔΣ(АС)=800700=+100 (С→В при окончательном расчете). Для систематизации таких расчетов запишем данные в виде матрицы выигрышей Матрица выигрышей Выигры ш-счета к Проигрыш-счета к оплате Итого к оплате А В С А 3000 500 3500 В 800 800 1600 С 1500 700 2200 Итого к 2300 3700 1300 7300 получению оплате Матрица проигрышей Проигр ыш-счета Выигрыш-счета к получению к Итого к А В С 800 1500 оплате оплате А 2300 В 3000 700 3700 С 500 800 1300 Итого к 3500 1600 2200 7300 оплате Если D - матрица выигрышей, DT-матрица проигрышей, ΔD=D-DT – матрица окончательных расчетов. Матрица окончательных расчетов Выигры ш-счета к Проигрыш-счета к оплате Итого к оплате А В С А +2200 -1000 +1200 В -2200 +100 -2100 С +1000 -100 +900 Итого к -1200 +2100 -900 получению оплате Рассмотрим парную игру с нулевой суммой. Игрок А имеет m стратегий A1, A2 ,..., Am , а игрок B имеет n стратегий B1, B2 ,..., Bn . Такая игра называется игрой размерностью m  n . Пусть каждый игрок выбирает определенную стратегию: игрок А – стратегию Ai , игрок В – стратегию B j . В этом случае игра приведена к матричному виду и называется матричной игрой. Пусть aij - выигрыш игрока А в ситуации когда игрок выбрал стратегию Ai , а игрок В выбрал стратегию B j . Выигрыш игрока В в данной ситуации будем обозначать bij , т.к. рассматриваемая игра с нулевой суммой, то aij  bij и для исследования необходимо знать выигрыш только одного из игроков, например, игрока А. Если игра состоит только из личных ходов, то выбор стратегии  Ai , B j  однозначно определяет исход игры, т.е. выигрыш игрока А - aij . Если игра содержит так же случайные ходы, то выигрыш при паре стратегий  Ai , B j  есть случайная величина, зависящая от исходов всех случайных ходов. В этом случае ожидаемый выигрыш – это среднее значение (математическое ожидание случайной величины). Пусть aij известны для каждой пары стратегий  A ,B . i j Составим прямоугольную таблицу, строки которой соответствуют стратегиям игрока А, а столбцы – стратегиям игрока В. Ai \ B j B1 B2 ………….. Bn A1 A2 a11 a21 a12 a22 …………. a1n a2n …………. …………. …………. Am am1 am 2 …………. …………. …………. …………. amn Если такая таблица составлена, то игра приведена к матричной форме и называется матричной игрой, таблица называется платежной матрицей. Каждый элемент aij  0 матрицы определяет величину выигрыша игрока А и проигрыш игрока В при применении пары стратегий  Ai , B j  . Цель игрока А – максимизировать свой выигрыш, а игрока В – минимизировать свой проигрыш. Принцип минимакса Пусть задана платежная матрица: Ai \ B j B1 B2 ………….. Bn A1 A2 a11 a21 a12 a22 …………. a1n a2n …………. …………. …………. …………. Am am1 am 2 …………. …………. …………. amn Необходимо определить: 1) наилучшую (оптимальную) стратегию игрока А из стратегий A1, A2 ,..., Am ; 2) наилучшую (оптимальную) стратегию игрока В из стратегий B1, B2 ,..., Bn . Для решения этой задачи применим принцип, согласно которому участники игры одинаково разумны и каждый из них делает все для того, чтобы добиться своей цели. Обозначим i  min aij -минимальный j выигрыш игрока А при применении им стратегии Ai . Выбирая стратегию Ai , игрок А должен рассчитывать на то, что в результате разумных действий игрока В он не выиграет больше, чем  i . Поэтому, далее игрок А должен выбрать стратегию для которой число  i   максимально   max i  max min aij . i i j Величина  - гарантированный выигрыш игрока А при любом поведении игрока В, которая называется нижней ценой игры. Стратегия Ai , обеспечивающая получение нижней цены игры называется максиминной чистой стратегией, при этом игрок А при любом поведении игрока В обеспечивает себе выигрыш i   . Игрок В заинтересован в уменьшении своего проигрыша, т.е. его цель обратить выигрыш игрока А в минимум. Для реализации этой цели игрок В сначала должен выбрать  j  max aij - максимальный проигрыш игрока В i при применении им стратегии B j . Выбирая стратегию B j , игрок В должен рассчитывать на то, что в результате разумных действий игрока А он не проиграет меньше, чем  j . Поэтому, далее игрок В должен выбрать стратегию для которой число  j   минимально   min  j  min max aij . j j i Величина  - гарантированный проигрыш игрока В при любом поведении игрока А, которая называется верхней ценой игры. Стратегия B j , обеспечивающая получение верхней цены игры называется минимаксной чистой стратегией, при этом игрок В при любом поведении игрока А обеспечивает себе проигрыш  j   . Таким образом придерживаясь максиминной стратегии Ai игрок А получает выигрыш не менее чем  , а игрок В придерживаясь минимаксной стратегии B j гарантирует себе проигрыш не более чем  . Понятие чистой стратегии. Игры с седловыми точками Существуют матрицы игры, для которых    . Такие игры называются играми с седловой точкой, в этом случае значение      называется чистой ценой игры, а стратегии Ai* и B*j , позволяющие достичь этого значения называются оптимальными. Игровая ситуация A ,B  называется седловой точкой матрицы игры. Матрица игры может обладить несколькими седловыми точками. Свойства седловых точек 1) Теорема (свойство равнозначности) Если ai j и ai 1 1 2 j2 седловые точки, то ai j  ai j . 1 1 2 2 2) Теорема (свойство взаимозаменяемости) * i * j Если ai j и ai 2 j2 1 1 седловые точки, то ai j и ai j - так же седловые точки. 1 2 2 1 Устойчивые и неустойчивые игровые ситуации. Рассмотрим матрицу игры: B1 B2 B3 i A1 -3 4 4 -3 A2 1 -2 1 -2 A3 4 4 -2 -2 j 4 4 4 4\-2 Ai Bj Максиминными стратегиями игрока А являются стратегии A2 и A3 , а минимаксными стратегиями игрока В являются стратегии B1 , B2 , B3 . Пусть игрок А придерживается стратегии A2 . Зная об этом игрок В, с целью получения наибольшего выигрыша выбирает стратегию B2 и получает выигрыш a22    2   2 . В ответ игрок А должен выбрать стратегию A1 или A3 . Так как в результате использования этих стратегий он получит максимальный выигрыш a12  a32  4 . При любом из этих выборов игрок А отклоняется от своей первоначальной стратегии A2 . Допустим, А остановился на стратегии A3 и получил выигрыш a32  4 . В ответ игрок В выберет стратегию B3 и получит максимальный выигрыш a33    2   2 . При этом В отклоняется от своей первоначальной стратегии B2 . Если В выбрал стратегию B3 , игрок А должен выбрать стратегию A1 , получив максимальный выигрыш a13  4 , отклонившись от предыдущей стратегии A3 и т.д. Таким образом, ситуации, складывающиеся после очередных ходов игроков, являются неустойчивыми. B1 B2 B3 i A1 0,7 0,5 0,3 0,3 A2 0,6 0,9 0,4 0,4 j 0,7 0,9 0,4 0,4\0,4 Ai Bj В данной игре имеем седловую точку т.к.     0,4 . Если игрок А придерживается максиминной стратегии A2 , то игрок В должен выбрать стратегию B3 , чтобы выигрыш игрока А был минимальным a23  0,4 . На это игрок А должен ответить выбором опять же стратегии A2 , чтобы получить максимальный выигрыш a23  0,4 . Далее игрок В опять выбирает стратегию B3 и т.д. Таким образом, если игроки А и В придерживаются своих максиминных и минимаксных стратегий соответственно, то ни один из них не может увеличить свой выигрыш отступая от своей стратегии. Ситуация  A2 , B3  является в данной игре устойчивой (или равновесной). Оптимальные чистые стратегии Показатели эффективности и неэффективности стратегий. C Рассмотрим игру m  n . Обозначим через S A   A1, A2 ,..., Am - множество C A B стратегий игрока А, через SB  B1, B2 ,..., Bn  . Стратегии i и j игроков А и В, создающие равновесную ситуацию седловой точке ai0 j0 A ,B  i0 j0 или соответствующие называются оптимальными чистыми стратегиями. CO CO Обозначим через S A и S B - множества чистых оптимальных стратегий игроков А и В. Если нижняя цена игры  равна верхней цене игры  , то их общее значение      называется ценой игры в чистых стратегиях. Совокупность S ACO , SBCO ,  CO CO множеств S A и S B чистых оптимальных стратегий игроков А и В и цены игры  называются полным решением игры в чистых стратегиях. Решение игры характеризуется тем свойством, что ни одному из игроков А и В, придерживающихся одной из своих оптимальных стратегий невыгодно от нее отклоняться, т.к. в этом случае он не увеличит своего выигрыша. Пусть задана матрица игры Ai \ B j B1 B2 ………….. Bn A1 A2 a11 a21 a12 a22 …………. a1n a2n …………. …………. …………. Am am1 am 2 …………. …………. Ситуация  Ai , B j  …………. …………. amn называется удовлетворительной для игрока А, если aij0  ai0 j0 и удовлетворительной для игрока В, если ai0 j0  ai0 j . Теорема1: ситуация  A , B  будет i0 j0 удовлетворительна для игрока А тогда и только тогда, когда его выигрыш ai 0 j0 j неэффективности стратегии B j0 совпадает с показателем игрока В, ai j   j , т.е. будет 0 0 максимальным в j0 -м столбце матрицы игры. Теорема2: ситуация  A , B  будет i0 j0 удовлетворительна для игрока В тогда и только тогда, когда его проигрыш ai 0 j0 эффективности i стратегии Ai0 игрока минимальным в i0 -й строке матрицы игры. совпадает с показателем А, ai0 j0  i0 , т.е. будет Алгоритм нахождения удовлетворительных ситуаций для игрока А: в каждом столбце B j0 j матрицы игры находится наибольший элемент показатель неэффективности стратегии которой стоит элемент j , ситуация B j0 Ai0 игрока В, затем строку A ,B  i0 j0 в будет удовлетворительной для игрока А. Алгоритм нахождения удовлетворительных ситуаций для игрока В: в каждой строке Ai0 матрицы игры находится наименьший элемент показатель эффективности стратегии которой стоит элемент i , ситуация Ai0 игрока А, затем столбец A ,B  i0 j0 i B j0 в будет удовлетворительной для игрока В. A ,B  Ситуация i0 называется равновесной или устойчивой или j0 седловой точкой игры, если она удовлетворительна для каждого из игроков А и В т.е. если выполняются неравенства aij  ai j  ai j или на основании 0 0 теорем 1 и 2 i  ai j   j . 0 0 Теорема: для того, чтобы существовала цена игры в чистых стратегиях (т.е.    ) необходимо и достаточно существования у матрицы этой игры седловой точки. Справедливы следующие утверждения: 1) Каждая оптимальная стратегия игрока А является его максиминной стратегией, а каждая оптимальная стратегия игрока В является его минимаксной стратегией. 2) В игре без седловых точек ни одна из максиминных и минимаксных стратегий не является оптимальной, в этой игре вообще нет оптимальных стратегий. 3) В игре с седловыми точками каждая максиминная и минимаксная стратегии игроков А и В являются оптимальными. Понятие смешанной стратегии. Рассмотрим игру без седловых точек    . Если такая игра повторяется многократно, то каждый из игроков имеет информацию о предыдущих ходах противника, а с другой стороны хочет скрыть информацию о своих намерениях и будущих ходах. В этом случае возникает вопрос: нельзя ли игрокам выбрать какой- то образ действий не сводящийся к использованию одной единственной чистой стратегии с тем, чтобы скрыть свои возможные действия от противника и в результате этого увеличить минимально гарантированный выигрыш  игрока А и уменьшить максимально гарантированный проигрыш  игрока В. Т.е. это вопрос о разделе разности     0 между игроками А и В с максимальной пользой для каждого из них. Такой способ состоит в случайном чередовании чистых стратегий. Стратегия игрока, состоящая в случайном выборе одной из его чистых стратегий называется смешанной стратегией. Смешанная стратегий представляет собой дискретную случайную величину, значениями которой являются номера его чистых стратегий. Показатели эффективности и неэффективности смешанных стратегий. Функция выигрыша. Из теории вероятностей известно, что случайная величина определяется законом распределения вероятностей. Обозначим через Р – смешанные стратегии игрока А, через Q – смешанные стратегии игрока В. Р задается законом распределения вероятностей: i 1 2 …. m P p1 p2 …. pm m p i i 1 1 Q задается законом распределения вероятностей: j 1 2 …. n Q q1 q2 …. qn n q j 1 j 1 C S   A1, A2 ,..., Am  A Если множество чистых стратегий игрока А и известно, что каждая смешанная стратегия Р определятся вероятностями p1, p2 ,..., pm с которыми выбираются игроком А соответствующие чистые стратегии, поэтому смешанную стратегию можно представить с помощью m-мерного вектора P   p1, p2 ,..., pm  . Аналогично определяются смешанные стратегии игрока В - Q  q1, q2 ,..., qn  . Если игроки А и В независимо друг от друга выбрали смешанные стратегии P   p1, p2 ,..., pm  и Q  q1, q2 ,..., qn  соответственно, то упорядоченная пара  P, Q  называется ситуацией в смешанных стратегиях. В условиях ситуации  P, Q  в смешанных стратегиях чистые стратегии Ai и B j выбираются независимо друг от друга с вероятностями pi и q j соответственно. Вероятность выбора пары  Ai , B j   pi q j , так как в ситуации A,B  i j в чистых стратегиях игрок получает выигрыш aij . Вероятность этого выигрыша составляет pi q j . Таким образом выигрыш игрока А в ситуации стратегиях представляет собой дискретную  P, Q  в смешанных случайную величину принимающую значение aij с вероятностью pi q j , а средний выигрыш игрока А равен математическому ожиданию этой случайной величины m n  a i 1 j 1 ij pi q j . m n Функция выигрыша в смешанных стратегиях H  P, Q    aij pi q j или i 1 j 1 в матричном виде H  P, Q   PAQT , где А – матрица игры. Теорема: Для каждой смешанной стратегии P  S A игрока А существует   P, S B   min H  P, Q  . QS B Для каждой смешанной стратегии Q  S B игрока В существует   Q, S A   max H  P, Q  . PS A Число   P, S B  называется показателем эффективности смешанной стратегии P  S A игрока А относительно множества S B смешанной стратегии игрока В. Если множество смешанных стратегий S B игрока В заменить на множество S BC - чистых   P, S BC   min H  P, Q   min H  P, B j  1 j n QS BC стратегий, - то показатель получим эффективности смешанной стратегии P  S A игрока А относительно множества S BC чистых стратегий игрока В. Число   P, S B   min H  P, Q   H  P, Q0  QSB называется показателем эффективности смешанной стратегии P  S A игрока А относительно множества S B смешанных стратегий игрока В. Теорема: Показателем эффективности любой смешанной стратегии P  S A игрока А относительно множеств S BC и S B чистых и смешанных стратегий игрока В равны т.е.   P, S BC     P, S B  . Число   Q, S A  называется показателем неэффективности смешанной стратегии Q  S B игрока В относительно множества S A смешанной стратегии игрока А. Если множество смешанных стратегий S A игрока А заменить на множество S AC - чистых   P, S AC   max H  P, Q   max H  Ai , Q  - 1i m PS AC стратегий, показатель то получим неэффективности смешанной стратегии Q  S B игрока В относительно множества S AC чистых стратегий игрока А. Число   Q, S A   max H  P, Q   H  Ai , Q  PS A называется показателем неэффективности смешанной стратегии Q  S B игрока В относительно множества S A смешанных стратегий игрока А. Теорема: Показателем неэффективности любой смешанной стратегии Q  S B игрока В относительно множеств S AC и S A чистых и смешанных стратегий игрока А равны т.е.   Q, S AC     Q, S A  . Нижняя и верхняя цены игры в смешанных стратегиях. Оптимальные смешанные стратегии. Нижней ценой игры или максимином матричной игры в смешанных стратегиях называется величина V  max   P   max min H  P, Q  PS A PS A QSB . Верхней ценой игры или минимаксом матричной игры в смешанных стратегиях называется величина V  min   Q   min max H  P, Q  QS B QS B PS A . Теорема: Для любой конечной матричной игры существует нижняя и верхняя цены игры в смешанных стратегиях. Теорема: Нижняя цена игры  и верхняя цена игры  в чистых стратегиях, нижняя цена игры V и верхняя цена игры V в смешанных стратегиях удовлетворяют неравенству:   V  V   . Для произвольной матрицы max min H  P, Q   min max H  P, Q   P* AQ*T PS A QSB QS B PS A игры А * * , где P и Q - смешанные * * стратегии на которых достигаются экстремумы. Стратегии P и Q для *T * *T * T PAQ  P AQ  P AQ которых выполняется соотношение называются оптимальными, пара  P ,Q  * * - седловой точкой функции H  P, Q   PAQT или ситуацией равновесия в смешанных стратегиях. * * Для того, чтобы стратегии P и Q были оптимальными в игре с матрицей А необходимо и достаточно чтобы выполнялось соотношение *T AQ  P* AQ*T  P*B j i Число . V  max min H  P, Q   min max H  P, Q   P* AQ*T PS A QSB QS B PS A называется ценой игры в смешанных стратегиях. Принцип доминирования Доминирующие и доминируемые строки (столбцы) игровой матрицы. Пусть задана матрица игры размерностью m  n Ai \ B j B1 B2 ………….. Bn A1 A2 a11 a21 a12 a22 …………. a1n a2n …………. …………. …………. Am am1 am 2 …………. …………. …………. …………. amn Каждой смешанной стратегии P   p1, p2 ,..., pm  игрока А поставим в соответствие строку  H  P, B  , H  P, B  ,..., H  P, B  1 2 n элементами которой являются выигрыши H  P, B j  игрока А в ситуациях  P, B j  . m m  m  pi ai1 ,  pi ai 2 ,...,  pi ain ,   PA     H  P, B1  , H  P, B2  ,..., H  P, Bn    i1 i 1 i 1  m   pi  ai1 , ai 2 ,..., ain  i 1 - комбинация строк матрицы А. Если для двух комбинаций строк матрицы А: m m  m      pi ai1 ,  pi ai 2 ,...,  piain  1 i 1 i 1  i 1  m m  m    p a , p a ,...,   i i1  i i 2  piain   2  i 1 i 1  i 1  Выполняются неравенства: m m i 1 i 1 m m i 1 i 1  piai1   piai1 ,  piai 2   piai 2 , …………………., m m i 1 i 1  piain   piain , То строка (2) доминирует строку (1), а строка (1) доминируется строкой (2). Если каждое из неравенств является равенством, то строки называют дублирующими друг друга. P   p1, p2,..., pm  Аналогично для стратегий игрока А: стратегия     доминирует (дублирует) стратегию P   p1, p2 ,..., pm  . Для игрока В: каждой смешанной стратегии Q  q1, q2 ,..., qn  игрока В T  H  A , Q  , H  A , Q  ,..., H  A , Q  T поставим в соответствие строку 1 2 m элементами которой являются выигрыши H  Ai , Q  игрока В в ситуациях  Ai , Q  . T  H  A , Q  , H  A , Q  ,..., H  A , Q  T 1 2 m n n  n  T   q j a1 j ,  q j a2 j ,...,  q j amj   AQ    j 1 j 1 j 1  T   q j  a1 j , a2 j ,..., amj  n j 1 - комбинация строк матрицы А. Если для двух комбинаций строк матрицы А: T n n  n     q a , q a ,..., q a   j 1 j  j 2 j  j mj   3 j 1 j 1  j 1  T n n  n     q a , q a ,..., q a   j 1 j  j 2 j  j mj   4  j 1 j 1  j 1  Выполняются неравенства: n  q a j 1 j 1j n   qj a1 j j 1 n n j 1 j 1 ,  qj a2 j   qj a2 j , …………………., n n j 1 j 1  qj amj   qj amj , То столбец (4) доминирует столбец (3), а столбец (3) доминируется столбцом (4). Если каждое из неравенств является равенством, то столбцы называют дублирующими друг друга. Q  q1, q2,..., qn T Аналогично для стратегий игрока В: стратегия Q  q1, q2 ,..., qn  T доминирует (дублирует) стратегию . Разбиение игровой матрицы на подматрицы. Иногда матрица игры бывает такой, что горизонтальными и вертикальными линиями ее можно разбить на подматрицы, в каждой из которых суммы элементов в строках равны между собой. Т.е. каждая из этих подматриц составлена из элементов стоящих на пересечениях некоторого числа соседних строк и некоторого числа соседних столбцов. Если подматрица образована k+1 строками с номерами  ,   1,   2,...,   k и l  1 столбцом с номерами  ,  1,  2,...,  l , то будем обозначать ее  ,  1,...,   k через A , 1,..., l . Теорема: Пусть подматрица 1,...,   k A,,1,...,  l обладает следующими свойствами:  l  l  l j  j  j   k  k  a pj   a p1 j  ...   a pkj  a    a  i i i i 1 (1)  k  ...   ai l (2) i Тогда справедливы следующие предложения: 1) Если данная подматрица состоит из единственной строки, т.е. если k=0, l  0 , то все элементы этой строки равны между собой. 2) Если данная подматрица состоит из единственного столбца, т.е. если , k  0 , l  0 , то все элементы этого столбца равны между собой. 3) Если данная подматрица квадратная, то сумма элементов каждой строки равна сумме элементов каждого столбца. Аналитическое решение игры 2х2 Рассмотрим игру с матрицей Аi\Bj B1 B2 A1 a11 a12 A2 a21 a22 Если матрица игры имеет седловую точку, то игра имеет решение в чистых стратегиях  A , B ,V  a  . i j ij Критерий существования седловой точки в игре 2х2. Теорема Пусть i, k 1, 2 , i  k ; j, l 1, 2 , j  l - А. Для того, чтобы элемент aij номера строк и столбцов матрицы был седловой точкой матрицы А необходимо и достаточно выполнение хотя бы одного из двух условий: 1) можно удалить k -ю строку, как доминируемую i -й строкой, а затем в оставшейся i -й строке можно удалить l -й столбец как доминируемый j м столбцом; 2) можно удалить l -й столбец, как доминируемый j -м столбцом, а затем в оставшемся j -м столбце удалить k -ю строку, как доминируемую i й строкой. Например, Аi\Bj B1 B2 A1 5 3 A2 1 2 Вторая строка доминируется первой строкой, следовательно, может быть удалена. Из оставшихся столбцов второй столбец доминирует первый, следовательно, первый столбец можно удалить. Получаем решение в чистых стратегиях  A1 , B2 ,V  3 . Или Аi\Bj B1 B2 A1 4 4 A2 1 2 Вторая строка доминируется первой строкой, следовательно, может быть удалена. Оставшиеся столбцы дублируют друг друга. Следовательно, у игрока А одна оптимальная стратегия A1, а у игрока В две оптимальных стратегии B1 и B2. Решение игры в чистых стратегиях  A1 , B1 , B2 ,V  3 . Теорема Для того, чтобы у матрицы А (2х2) существовала седловая точка необходимо и достаточно, чтобы сумма элементов главной диагонали матрицы А a11  a22  a12  a21 равнялась сумме элементов ее побочной диагонали (это условие является достаточным, но не является необходимым). Следствие Для того, чтобы у матрицы А (2х2) не существовало седловой точки необходимо и достаточно, чтобы сумма элементов главной диагонали матрицы А не равнялась сумме элементов ее побочной диагонали a11  a22  a12  a21 (это условие является необходимым, но не является достаточным). Теорема Пусть матрица А (2х2) не имеет седловой точки. Тогда каждый из игроков А и В обладает единственной оптимальной смешанной стратегией P0 ( p10 , p20 ) и Q0 (q10 , q20 ) . Которые находятся по формулам: p10  a22  a21  a11  a22    a12  a21  q10  a22  a12 ;  a11  a22    a12  a21  ; p20  1  p10  a11  a12 ;  a11  a22    a12  a21  q20  1  q10  a11  a21 ;  a11  a22    a12  a21  V a11a22  a12 a21 .  a11  a22    a12  a21  Доказательство: Пусть и P0 ( p10 , p20 ) Q0 (q10 , q20 ) - оптимальные смешанные стратегии игроков А и В. По определению оптимальных смешанных стратегий H ( P 0 , Q0 )  V . Так как матрица А не имеет седловых точек, пассивных стратегий в игре не существует, т.е. стратегии B1 и B2 активны. По теореме об активных стратегиях H ( P0 , B j )  V т.е. a11 p10  a21 p20  V  a12 p1  a22 p2  V  0  p1  p2  1 второе . Решим систему уравнений, приравняем первое и уравнения  a11 p1  a21 p2  a12 p1  a22 p2 ,  0 p  p  1   1 2  a11 p1  a12 p1  a22 p2  a21 p2 ,  0 p  p  1   1 2   p1 (a11  a12 )  p2 (a22  a21 ) ,  0 p  p  1   1 2  0 0 ( a22  a21 )  p1  p2 (a  a ) 11 12 ,   p0  p0  1  1 2  0 0 ( a22  a21 )  p1  p2 (a  a ) 11 12  ,   p 0  (a22  a21 )  (a11  a12 )   1   2  (a11  a12 )   0 (a11  a12 ) (a  a )  22 21  p1  (a22  a21 )  (a11  a12 ) (a11  a12 )   (a11  a12 )  0  p2  (a  a )  (a  a )  22 21 11 12  0 0 ( a22  a21 )  p1  p2 (a  a ) 11 12  ,   p 0  (a22  a21 )  1  1  2  (a11  a12 )   0 0 ( a22  a21 ) p  p 1 2  (a11  a12 )  ,   p 0 (a22  a21 )  p 0  1 2  2 (a11  a12 )  0 0 ( a22  a21 )  p1  p2 (a  a )  11 12 ,  (a11  a12 )  p0   2 (a22  a21 )  (a11  a12 ) , (a22  a21 )  0  p1  (a  a )  (a  a )  22 21 11 12 .  (a11  a12 )  p0   2 (a22  a21 )  (a11  a12 ) Геометрическое решение игры 2х2 Пусть дана матрица игры Аi\Bj B1 B2 A1 a11 a12 A2 a21 a22 Пусть Р(1-р,р) – смешанная стратегия игрока А, p  0;1 , при р=0 смешанная стратегия превращается в чистую стратегию A1 (1;0) , при р=1 в чистую стратегию A2 (0;1) . Пусть игрок А выбирает смешанную стратегию Р(1-р,р), а игрок В чистую стратегию B1 , тогда в ситуации  P, B1  игрок А получит выигрыш a  H  P, B1   1  p, p   11   1  p  a11  pa21  a11  pa11  pa21  p  a21  a11   a11  a21  H  P, B1  - линейная функция вероятности р, определенная на отрезке 0;1 . График такой функции – отрезок прямой, заключенный между перпендикулярами к отрезку 0;1 , проведенных в его концах. При р=0, H  A1 , B1   a11 ; при р=1, H  A2 , B1   a21 . Если игрок А выбирает стратегию Р(1-р,р), а игрок В чистую стратегию B2 , то a  H  P, B2   1  p, p   12   1  p  a12  pa22  a12  pa12  pa22  p  a22  a12   a12  a22  Показатель эффективности   P   min H  P, B1  , H  P, B2  - смешанной есть функция, стратегии Р(1-р,р) являющаяся нижней огибающей функций H  P, B1  и H  P, B2  (ломаная a11Na22 ). V  max   P  следовательно, V (цена игры) равна ординате точки N. Так как a11  a12 , то показатель эффективности стратегии A1   ( A1 )  1  a11 изображается точкой на левом перпендикуляре. А показатель эффективности стратегии A2   ( A2 )   2  a22 изображается нижней точкой на правом перпендикуляре. Так как a11  a22 нижняя цена игры в чистых стратегиях   a11 (верхняя из точек a11 и a22 . a21 a12   H  P, B1  N V H  P, B2    a11 a22 p 1 P Аналогично, показатель неэффективности стратегии B1 при a21  a11 равен a21 .   B1   1  a21 , а показатель неэффективности стратегии B2 при a12  a22 равен a12 т.е   B2   2  a12 и так как a21  a12 верхняя цена игры в чистых стратегиях   a12 ,   V   . Общий алгоритм геометрического нахождения оптимальных стратегий игрока А 1. Строим горизонтальный отрезок 0;1 . 2. Из концов отрезка точки 0 и точки 1 проводим 2 перпендикуляра. 3. На левом перпендикуляре от точки 0 откладываем элементы a11 и a12 . 4. На правом перпендикуляре от точки 1 откладываем a21 и a22 . 5. Соединяем точки, изображающие элементы с одинаковыми вторыми индексами a11 и a21 , a22 и a12 . 6. Если отрезки a11 a21 и a22 a12 возрастающие, то стратегия A2 доменирует стратегию A1 . 7. Если отрезок a11 a21 лежит ниже отрезка a22 a12 , то стратегия B2 доменирует стратегию B1 . 8. Находим нижнюю огибающую отрезков a11 a21 и a22 a12 . 9. Находим наивысшую точку (или точки) нижней огибающей. 10. Проектируем их ортогонально на отрезок 0;1 . 11. Полученная проекция определяет оптимальную стратегию игрока А - Р(1-р,р). 12. Ордината наивысшей точки нижней огибающей равна цене игры V. 13. Верхний, из двух концов нижней огибающей есть нижняя цена игры в чистых стратегиях  . 14. Нижний из двух верхних концов отрезков a11 a21 и a22 a12 есть верхняя цена игры в чистых стратегиях  . 15. Если элемент является нижним, на перпендикуляре, где он лежит и верхним концом отрезка a11 a21 или a22 a12 , на котором он лежит, то этот элемент является седловой точкой. В этом случае чистая стратегия игрока В, номер которой совпадает со вторым индексом седловой точки является оптимальной. Геометрическое решение игры 2х2 (продолжение) Пусть дана матрица игры Аi\Bj B1 B2 A1 a11 a12 A2 a21 a22 Пусть Q(1-q,q) – смешанная стратегия игрока B, q  0;1 , при q=0 смешанная стратегия превращается в чистую стратегию B1 (1;0) , при q=1 в чистую стратегию B2 (0;1) . Пусть игрок B выбирает смешанную стратегию Q(1-q,q), а игрок A чистую стратегию A1 , тогда в ситуации  A1 , Q  игрок B получит выигрыш 1  q  a12     a11 1  q   qa12  a11  qa11  qa12  q  a12  a11   a11 q   H  A1 , Q    a11 H  A1 , Q  - линейная функция вероятности q, определенная на отрезке 0;1 . График такой функции – отрезок прямой, заключенный между перпендикулярами к отрезку 0;1 , проведенных в его концах. При q=0, H  A1 , B1   a11 ; при р=1, H  A2 , B1   a12 . Если игрок B выбирает стратегию Q(1-q,q), а игрок A чистую стратегию A2 , то H  A2 , Q    a21 Показатель 1  q  a22     a21 1  q   qa22  a21  qa21  qa22  q  a22  a21   a21 q   неэффективности   Q   max H  A1, Q  , H  A2 , Q  смешанной стратегии Q(1-q,q) - есть функция, являющаяся верхней огибающей функций H  A1, Q  и H  A2 , Q  (ломаная a21Ma12 ). V  min   Q  следовательно, V (цена игры) равна ординате точки M. a12 a21 H  A1 , Q  M V H  A2 , Q  a11 a22 q 1 q Общий алгоритм геометрического нахождения оптимальных стратегий игрока B 1. Строим горизонтальный отрезок 0;1 . 2. Из концов отрезка точки 0 и точки 1 проводим 2 перпендикуляра. 3. На левом перпендикуляре от точки 0 откладываем элементы a11 и a21 . 4. На правом перпендикуляре от точки 1 откладываем a12 и a22 . 5. Соединяем точки, изображающие элементы с одинаковыми первыми индексами a11 и a12 , a22 и a21 . 6. Находим верхнюю огибающую отрезков a11 a12 и a22 a21 . 9. Находим наинизшую точку (или точки) верхней огибающей. 10. Проектируем их ортогонально на отрезок 0;1 . 11. Полученная проекция определяет оптимальную стратегию игрока B - Q(1-q,q). 12. Ордината наивысшей точки нижней огибающей равна цене игры V. 13. Нижний, из двух концов верхней огибающей, есть верхняя цена игры в чистых стратегиях  . 14. Верхний из двух нижних концов отрезков a11 a12 и a22 a21 есть нижняя цена игры в чистых стратегиях  . Пример. Найти оптимальную смешанную стратегию игрока В. Аi\Bj B1 B2 A1 2 5 A2 7 3 По принципу минимакса   3 ,   5 , 3  V  5 . a21  7 a12  5   M V a22  3   a11  2 q Найдем q и V из уравнений H  A1, Q   q  a12  a11   a11  V H  A2 , Q   q  a22  a21   a21  V q 5  2  2  V q 3  7  7  V 1 q 3q  2  V , 4q  7  V , 3q  2  4q  7 , 7q  5 , q  5 5 2 , 1 q 1  . 7 7 7 2 5   Искомая смешанная стратегия игрока B - Q  ,  . Найдем V. 7 7 3q  2  V , 5 15 14 29 1 V 3 2   4 7 7 7 7 7 . Таким образом выигрыш, 1 7 полученный для игрока А и для игрока В одинаков V  4 , это дает дополнительный контроль правильности решения. Совместим оба рисунка: a21  7 a21  7 a12  5   a12  5 V 4 1 7 a22  3   a11  2 p 3 7 q 5 7 1 Решение игры 2хn Пусть дана матрица игры p, q Ai \ B j B1 B2 ………… Bn ………… a1n ………… a2n .. A1 a11 a12 . A2 a22 a21 . Показатель эффективности стратегии P  p1, p2  игрока А:   P   min H  P, B j   min  p1a1 j  p2a2 j  . j j Пусть p2  p , p1  1  p , тогда     P   min  1  p  a1 j  pa2 j   min  a2 j  a1 j  p  a1 j . Таким образом, j j   P  есть нижняя огибающая n линейных функций H  P, B j    a2 j  a1 j  p  a1 j от вероятности p  0,1 , графиком каждой из которых является прямая. Стратегия P0  1  p0 , p0  , удовлетворяющая равенству     P0   max   P   max min  a2 j  a1 j  p 0  a1 j j i j  является оптимальной стратегией игрока А, т.е. абсцисса наивысшей точки нижней огибающей   P  определяет оптимальную стратегию P0  1  p0 , p0  , придерживаясь которой игрок А выбирает чистую стратегию A1 с вероятностью 1  p 0 , а чистую стратегию A2 с вероятностью p 0 . Цена игры V    P0  т.е. равна ординате максимальной точки нижней огибающей. Алгоритм геометрического нахождения оптимальных стратегий игрока А и цены игры V в игре 2хn 1) Строим горизонтальный отрезок 0,1 . 2) Из концов отрезка проводим два перпендикуляра. 3) На левом перпендикуляре от точки 0 откладываем, соблюдая масштаб, все элементы первой строки матрицы игры. 4) На правом перпендикуляре от точки 1 откладываем, соблюдая масштаб, все элементы второй строки матрицы игры. 5) Каждую пару точек, изображающих элементы a1 j и a2 j , стоящие в jм столбце матрицы игры соединяем отрезками a1 j a2 j . Таким образом получим n отрезков, представляющих собой графики n линейных функций H  P, B j    a2 j  a1 j  p  a1 j . 6) Если все отрезки a1 j a2 j возрастающие, то стратегия A2 доминирует стратегию A1 . 7) Если все отрезки a1 j a2 j убывающие, то стратегия A1 доминирует стратегию A2 . 8) Если отрезок a1 j a2 j , лежит не ниже отрезка a1 j a2 j , j1  j2 , то 1 1 2 2 стратегия B j доминирует стратегию B j . 2 1 9) Находим нижнюю огибающую семейства отрезков. 10) На нижней огибающей находим максимальную точку или точки. 11) Абсцисса p 0 этой точки является вероятностью выбора игроком А чистой стратегии A2 в оптимальной смешанной стратегии P0  1  p0 , p0  . 12) Ордината наивысшей точки нижней огибающей является ценой игры V. 13) Верхний из двух концов нижней огибающей есть нижняя цена игры в чистых стратегиях  14) Нижний, из верхних концов отрезков a1 j a2 j есть верхняя цена игры в чистых стратегиях  15) Элемент матрицы игры, изображающая точка которого является нижней на перпендикуляре, где она лежит и одновременно верхним концом одного из отрезков будет седловой точкой игры. Например, дана матрица игры Ai \ B j B1 B2 B3 B4 B5 B6 i A1 5 -1 1 -2 6 3 -2 A2 4 3 2 7 1 4 1 j 5 3 2 7 6 4  1  2 Применим принцип минимакса   1 ,   2 , 1  V  2 . Строим чертеж: a24  7 a15  6 a11  5 a21  a26  4 a16  3 a22  3 М V a23  2   a11 13  1 6 a25  1   a12  1 p0  5 6 1 a14  2 На чертеже 6 прямых линий, т.к. в матрице игры у игрока В 6 стратегий. Нижняя огибающая семейства прямых на чертеже выделена красным цветом. От максимальной точки М нижней огибающей идут синие пунктирные линии, они определяют p 0 и V. Точка М лежит на пересечении прямых a13a23 и a15a25 соответственно для нахождения смешанной стратегии игрока А и цены игры V используем формулу H  P, B j    a2 j  a1 j  p  a1 j , где за j возьмем 3 и 5. Получим два уравнения: H  P, B3    a23  a13  p  a13  V H  P, B5    a25  a15  p  a15  V Подставим значения:  2  1 p  1  V 1  6 p  6  V p 1  V 5 p  6  V 5 p  6  p  1 6 p  5 p  p0  5 6 1  p  1  p0  1 6 1 5 Смешанная стратегия игрока А - P  ,  совпадает с чертежом, что 6 6 важно! Найдем V из уравнения p  1  V . 5 1 V 6 V 11 , так же совпадает с графиком и с результатом полученным по 6 признаку минимакса 1  11  2. 6 Для игрока В найти оптимальную смешанную стратегию не возможно. Решение игры mx2 Пусть дана матрица игры Ai \ B j B1 B2 A1 a11 a12 A2 a21 a22 …… …… …… Am am1 am 2 Показатель неэффективности стратегии Q  q1, q2  игрока В:   Q   max H  Ai , Q   max  q1ai1  q2ai 2  . i i Пусть q2  q , q1  1  q , тогда   Q   max  1  q  ai1  qai 2   max   ai 2  ai1  q  ai1  . Таким образом, i i   Q  есть верхняя огибающая m линейных функций H  Ai , Q    ai 2  ai1  q  ai1 от вероятности q  0,1 , графиком каждой из которых является прямая. Стратегия Q0  1  q0 , q0  , удовлетворяющая равенству     Q0   min   Q   min max   ai 2  ai1  q 0  ai1  является оптимальной j j i стратегией игрока B, т.е. абсцисса наинизшей точки верхней огибающей   Q  определяет оптимальную стратегию Q0  1  q0 , q0  , придерживаясь которой игрок В выбирает чистую стратегию B1 с вероятностью 1  q 0 , а чистую стратегию B2 с вероятностью q 0 . Цена игры V    Q0  т.е. равна ординате минимальной точки верхней огибающей. Алгоритм геометрического нахождения оптимальных стратегий игрока В и цены игры V в игре mх2 1) Строим горизонтальный отрезок 0,1 . 2) Из концов отрезка проводим два перпендикуляра. 3) На левом перпендикуляре от точки 0 откладываем, соблюдая масштаб, все элементы первого столбца матрицы игры. 4) На правом перпендикуляре от точки 1 откладываем, соблюдая масштаб, все элементы второго столбца матрицы игры. 5) Каждую пару точек, изображающих элементы ai1 и ai 2 , стоящие в iй строке матрицы игры соединяем отрезками ai1ai 2 . Таким образом, получим m отрезков, представляющих собой графики m линейных функций H  Ai , Q    ai1  ai 2  q  ai1 . 6) Если все отрезки ai1ai 2 неубывающие, то стратегия B1 доминирует стратегию B2 . 7) Если все отрезки ai1ai 2 невозрастающие, то стратегия B2 доминирует стратегию B1 . 8) Если отрезок ai 1ai 2 , лежит не ниже отрезка ai 1ai 2 , i1  i2 , то 1 1 2 2 стратегия Ai доминирует стратегию Ai . 2 1 9) Находим верхнюю огибающую семейства отрезков. 10) На верхней огибающей находим минимальную точку или точки. 11) Абсцисса q 0 этой точки является вероятностью выбора игроком В чистой стратегии B2 в оптимальной смешанной стратегии Q0  1  q0 , q0  . 12) Ордината наивысшей точки нижней огибающей является ценой игры V. 13) Нижний из двух концов верхнй огибающей есть верхняя цена игры в чистых стратегиях  14) Верхний, из нижних концов отрезков ai1ai 2 , есть нижняя цена игры в чистых стратегиях  15) Элемент матрицы игры, изображающая точка которого является верхней на перпендикуляре, где она лежит и одновременно нижним концом одного из отрезков будет седловой точкой игры. Например, дана матрица игры Ai \ B j B1 B2 i A1 3 1 1 A2 -4 4 -4 A3 5 -6 -6 A4 2 2 2 A5 -3 -2 -3 j 5 4  1  4 Применим принцип минимакса   1 ,   4 , 1  V  4 . Строим чертеж: a31  5 a22  4   a11  3 М1 М2 a42  2 a41  2  V a12  1   1 q  2 1 q20  3 4 1 a52  2 a51  3 a21  4 a32  6 На чертеже 5 прямых линий, т.к. в матрице игры у игрока А 5 стратегий. Верхняя огибающая семейства прямых на чертеже выделена красным цветом. Минимальные точки верхней огибающей лежат на отрезке  q10 ; q20  т.е. их много, края отрезка спроектированы на отрезок 0;1 синими перпендикулярами, они определяют q10 , q20 и V. Точка М1 лежит на пересечении прямых a41a42 и a11a12 соответственно для нахождения смешанной стратегии игрока В и цены игры V используем формулу H  Ai , Q    ai 2  ai1  q  ai1 , где за i возьмем 4 и 1. Получим два уравнения: H  A4 , Q    a42  a41  q  a41  V H  A1, Q    a12  a11  q  a11  V Подставим значения:  2  2 q  2  V 1  3 q  3  V V 2 2q  3  2 2q  1 q  q10  1 2 1  q  1  q10  Смешанная 1 2 стратегия игрока В - 1 1 Q1  ,  является 2 2 крайней оптимальной стратегией, совпадает с чертежом, что важно! Аналогичным образом находим вторую крайнюю оптимальную стратегию как пересечение прямых a41a42 и a21a22 . Смешанная стратегия 1 3 Q2  ,  является второй крайней оптимальной стратегией. Цену игры V=2 4 4 нашли ранее. 1  V  2  4 . Для игрока А найти оптимальную смешанную стратегию не возможно. В данной задаче множество минимальных точек на нижней огибающей, т.е. у игрока В множество оптимальных смешанных стратегий. Но может быть и одна!!! Решение игры m  n методом Шепли-Сноу Теорема (Шепли-Сноу). Пусть P0   p10 , p20 ,..., pm0  и Q0   q10 , q20 ,..., qn0  оптимальные стратегии соответственно игроков А и В с платежной матрицей: Ai \ B j B1 B2 ………….. Bn A1 A2 a11 a21 a12 a22 …………. a1n a2n …………. …………. …………. am1 am 2 …………. …………. Am …………. …………. amn И ценой игры V. Тогда найдутся натуральное число r, 1  r  minm, n , номера строк i1, i2 ,..., ir и номера столбцов j1, j2 ,..., jr матрицы А такие, что оптимальная стратегия P0   p10 , p20 ,..., pm0  удовлетворяет системе уравнений  r  aik jl pik  V  0, l  1,..., r ,  k 1  r 0  pik  1, ,  k 1  p0  0  i  а крайняя оптимальная стратегия Q0   q10 , q20 ,..., qn0  удовлетворяет системе уравнений  r  aik jl q jl  V  0, k  1,..., r ,  l 1  r 0  q jl  1, .  l 1 q 0  0  j  При этом, если V  0 , то матрица Aij ,,ij ,...,,...,i j = 1 2 1 2 r r Aik \ B jl B j1 B j2 ………….. B jr Ai1 ai1 j1 ai1 j2 …………. ai1 jr Ai2 ai2 j1 ai2 j2 …………. ai2 jr …………. …………. …………. …………. Air air j1 air j2 …………. …………. системы и транспонированная матрица  Aij ,,ij ,...,,...,i j 1 2 1 2 r r  T air jr системы невырождены, т.е. их определители отличны от нуля. Для нахождения оптимальных стратегий игры m  n методом ШеплиСноу можно придерживаться следующего алгоритма. 1) В соответствии с принципом доминирования вычеркнуть строго доминируемые строки и столбы, это уменьшит размерность исходной матрицы. 2) В полученной матрице перебрать все ее квадратные подматрицы не ниже второго порядка и для каждой из них решить соответствующую систему r  1 линейных уравнений с r  1 неизвестными q 0j , а для l транспонированной матрицы – систему r  1 линейных уравнений с неизвестными pi0 . k 3) Полученные решения проверить на неотрицательность и на выполнение условий оптимальности:  aik j pi0k   aij pi0  H  P0 , B j   V , r m k 1 i 1  aijl q0jl   aij q0j  H  Ai , Q0   V . r n l 1 j 1 4) Найденные решения систем являются оптимальными стратегиями. Игры с природой В антагонистических играх присутствовала неопределенность, состоящая в том, что ни один из игроков не обладал информацией о действиях противника. Однако, эта неопределенность компенсировалась тем, что каждый из игроков не будет действовать себе во вред, выбирая стратегии наиболее выгодные для себя и наименее выгодные для противника, таким образом каждый игрок стремился увеличить свой выигрыш (уменьшить свой проигрыш). В экономических задачах часто приходится принимать решение в условиях неопределенности не связанной с сознательным целенаправленным противодействием противника и заключающейся в недостаточной информированности лица, принимающего решение, об объективных условиях происходящего. Неопределенность такого вида может порождаться различными причинами: нестабильностью экономической ситуации, покупательским спросом на товар конкретного вида, меняющимся объемом перевозок, рыночной конъюнктурой, политикой правительства, надежностью партнера, выходом из строя технического оборудования, курсом валюты, уровнем инфляции, налоговой политикой, биржевой ситуацией, экологической обстановкой, стихийными бедствиями и т.д. Во всех задачах такого рода выбор решения зависит от объективной действительности, называемой в математической модели «природой». Сама математическая модель подобных ситуаций называется «играми с природой». Таким образом, в игре с природой осознанно действует только один игрок – лицо, принимающее решение игрок А. Природа, будем обозначать ее через П, является вторым неактивным игроком, так как она активно не противодействует игроку А, а принимает неопределенным образом то или иное состояние, не преследуя конкретной цели и безразлично к результату игры. Пусть игрок А имеет m возможных стратегий  A1, A2 ,..., Am , а игрок П может находиться в одном из n возможных состояний Ï 1, Ï 2 ,..., Ï n , которые можно рассматривать как ее стратегии. Совокупность Ï 1, Ï 2 ,..., Ï n  формируется либо на основе имеющегося опыта анализа состояний природы, либо в результате предположений и интуиции экспертов. Выигрыш игрока А при выбранной им стратегии Ai при состоянии природы Ï j обозначим через aij . Составим матрицу игры игрока А: Ai \ Ï j Ï 1 Ï 2 …… Ï n A1 a11 a12 …… a1n A2 a21 a22 …… a2n ……. …… …… …… …… Am am1 am 2 …… amn Задача выбора игроком А чистой или смешанной стратегии в игре с природой осложняется наличием неопределенности, связанной с недостатком сведений о том или ином состоянии природы. При решении вопроса о выборе возможной стратегии в игре с природой игрок должен исходить из матрицы выигрышей. На выбор стратегии должны влиять не только выигрыши, составляющие матрицу игры, но и показатели «удачности» или «неудачности» выбора данной стратегии при данном состоянии природы и благоприятности этого состояния для увеличения выигрыша. Показателем благоприятности состояния Ï j природы П для увеличения выигрыша называется наибольший выигрыш при этом состоянии, т.е. наибольший элемент в j-м столбце матрицы игры:  j  max aij . 1i m Таким образом, благоприятность состояния природы рассматривается как фактор, благоприятствующий увеличению выигрыша игрока А при этом состоянии природы. В теории антагонистических матричных игр эта величина представляла собой показатель неэффективности стратегии B j игрока В. Для характеристики степени удачности применения игроком А стратегии Ai при Ï j состоянии природы П используют понятие риска. Риском rij игрока А при выборе им стратегии Ai при состоянии природы Ï j называется разность между показателем благоприятности  j состояния природы Ï j и выигрышем aij , т.е. выигрышем который игрок А получил бы, ели бы знал заранее, что природа примет состояние Ï j , и выигрышем, который он реально получит при этом же состоянии природы Ï j выбрав стратегию Ai . Таким образом, rij   j  aij . Риск rij игрока А при применении стратегии Ai при состоянии природы Ï j есть упущенная возможность максимального выигрыша  j при этом состоянии природы. Из формулы rij   j  aij следует, что риск всегда неотрицателен rij  0 . Можно установить верхнюю границу рисков для каждого состояния природы Ï j , для этого рассмотрим величину  j  min aij , которая является 1i m наименьшим выигрышем игрока при состоянии природы Ï j . Тогда rij   j   j , разность  j   j называют колебанием выигрышей при состоянии природы Ï j . Если aij   j , то rij  0 , т.е. стратегия Ai при состоянии природы Ï j является безрисковой. Если aij   j , то риск rij является максимальным, а стратегия Ai в этом случае наихудшая. Если  j   j , то все выигрыши в j-м столбце матрицы игры равны между собой  j  a1 j  a2 j  ...  amj   j и риск rij  0 . Поэтому в этом случае любая стратегия игрока А при состоянии природы Ï j - безрисковая. Для матрицы игры можно составить матрицу рисков R, она имеет ту же размерность, что и матрица игры: Ai \ Ï Ï j Ï 1 2 …… Ï n A1 r11 r12 …… r1n A2 r21 r22 …… r2n ……. …… …… …… …… Am rm1 rm 2 …… rmn Пример: Построить матрицу рисков для матрицы: Ai \ Ï j Ï 1 Ï 2 Ï 3 Ï 4 Ï A1 9 4 5 1 3 A2 4 8 3 1 A3 4 7 4 8 2 j 9 8 5 8 3 5 Рассмотрим состояние природы Ï 1 : если бы игрок А знал, что состояние природы будет Ï 1 , то он выбрал бы стратегию приносящую максимальный выигрыш т.е A1 , в этом случае выигрыш  j  9 . Но игрок А не знает какое состояние примет природа поэтому выбирая стратегию А рискует получить не максимальный выигрыш 9, а только ai1 . Рассчитаем риски при состоянии природы Ï 1 : r11  1  a11  9  9  0 ; r21  1  a21  9  4  5 ; r31  1  a31  9  4  5 1  min 9,4,4  4 1i m 1  1  9  4  5 -колебания выигрыша. Аналогичным образом определим риски при остальных состояниях природы, получим матрицу рисков: Ai \ Ï j Ï 1 Ï 2 Ï 3 Ï 4 Ï A1 4 7 A2 5 2 8 2 A3 5 1 1 1 2  2  8  4  4 ; 3  3  5  3  2 ; 4  4  8  0  8 ; 5  5  3  1  2 . Принятие решений в условиях неопределенности 5 Рассмотрим игру с природой, пусть известна матрица игры Ai \ Ï Ï j Ï 1 2 …… Ï n A1 a11 a12 …… a1n A2 a21 a22 …… a2n ……. …… …… …… …… Am am1 am 2 …… amn Игрок А имеет m возможных стратегий  A1, A2 ,..., Am  , а игрок П может находиться в одном из n возможных состояний Ï 1, Ï 2 ,..., Ï n  , которые можно рассматривать как ее стратегии. Неизвестно какое именно состояние примет природа и отсутствует всякая возможность получения какой-либо информации о состояниях природы. Такая ситуация называется ситуацией полной неопределенности. Рассмотрим критерии поведения игрока А в условиях полной неопределенности. Критерий Вальда (критерий крайнего пессимизма) Рассматривая стратегию Ai игрок А предполагает, что складывается самая плохая ситуация, т.е. ситуация, приносящая самый маленький выигрыш. Поэтому, рассматривая каждую стратегию игрок выбирает ситуации, приносящие минимальный выигрыш i  min aij , затем из минимально j возможных выигрышей  выбирается максимальный т.е. находится    max i  max min aij . Стратегия игрока А соответствующая значению  i i j считается оптимальной по критерию Вальда. Например, Ai \ Ï j Ï 1 Ï 2 Ï 3 Ï 4 Ï 5 i A1 9 4 5 1 3 1 A2 4 8 3 1 4 A3 7 4 8 2 2 1  min 9,4,5,1,3  3 j  2  min 4,8,3,0,1  0 j 3  min 4,7,4,8,2  2 j   max 1,0,2  2 i Значение   2 соответствует стратегии A3 , таким образом правило Вальда рекомендует использовать стратегию A3 . Критерий Вальда является критерием крайнего пессимизма, т.к. ориентирует игрока А на наихудшее состояние природы и, следовательно, на крайне осторожное, осмотрительное поведение при выборе стратегий. Этот критерий уместен в тех случаях, когда игрок А не столько хочет выиграть, сколько хочет не проиграть. Максимаксный критерий (критерий крайнего оптимизма) Противоположностью критерию Вальда является максимаксный критерий. В этом случае рассматривая каждую свою стратегию Ai игрок А предполагает, что складывается самая хорошая ситуация, т.е. ситуация, приносящая максимальный выигрыш i  max aij , затем из максимально j возможных выигрышей  выбирается максимальный т.е.    max i  max max aij . Стратегия игрока А соответствующая значению  i i j считается оптимальной по критерию максимаксной стратегии. Например, Ai \ Ï j Ï 1 Ï 2 Ï 3 Ï 4 Ï 5 i A1 9 4 5 1 3 9 A2 4 8 3 1 8 4 A3 7 4 2 8 8 1  max 9,4,5,1,3  9 j  2  max 4,8,3,0,1  8 j 3  max 4,7,4,8,2  8 j   max 9,8,8  9 i Значение   9 соответствует стратегии A1 , таким образом, максимаксный критерий рекомендует использовать стратегию A1 . Максимаксный критерий является критерием крайнего оптимизма, так как ориентирует игрока А на наилучшее, благоприятнейшее для него состояние природы и, как следствие, на неоправданно легкомысленное поведение при выборе стратегий. Вместе с тем, в некоторых случаях этим критерием пользуются осознанно, например, когда перед игрокам А стоит дилемма: либо получить наибольший выигрыш, либо стать банкротом. Критерий Сэвиджа Критерий Сэвиджа так же относится к критериям крайнего пессимизма, но применяется к матрице рисков. Применяя критерий Сэвиджа игрок А при рассматривании стратегии Ai предполагает, что складывается ситуация приносящая максимальный риск, таким образом сначала внутри каждой стратегии выбираются значения, приносящие максимальный риск i  max aij , потом из всех максимально возможных рисков выбирается j минимальный i i соответствующая значению  Сэвиджа. Например,     min i  min max aij . j Стратегия игрока А считается оптимальной по критерию Дана матрица игры Ai \ Ï Ï j 1 Ï 2 Ï Ï 3 Ï 4 A1 9 4 5 1 3 A2 4 8 3 1 A3 4 7 4 8 2 5 Построим матрицу рисков Ai \ Ï Ï j 1 Ï 2 Ï Ï 3 4 Ï i 5 A1 4 7 7 A2 5 2 8 2 8 A3 5 1 1 1 5 1  max 0,4,0,7,0  7 j 2  max 5,0,2,8,2  8 j 3  max 5,1,1,0,1  5 j   min 7,8,5  5 i Значение   5 соответствует стратегии A3 , таким образом, критерий Сэвиджа рекомендует использовать стратегию A3 . Критерий Гурвица Критерий Гурвица является как бы промежуточным критерием между критерием крайнего оптимизма и критерием крайнего пессимизма. Критерий Гурвица рекомендует принимать решение соответствующее показателю эффективности G     max 1    min aij   max aij  . i  j j  При   0 из критерия Гурвица получаем критерий Вальда, при   1 получаем максимаксный критерий. Критерий Гурвица позволяет взвешивать пессимистический и оптимистический подходы с показателем оптимизма  . Например, дана матрица игры и   0,5 Ai \ Ï Ï j Ï 1 2 Ï Ï 3 4 Ï 5 i i min max A1 9 4 5 1 3 1 9 A2 4 8 3 1 8 A3 4 7 4 8 2 2 8 G1     1  0,5 1  0,5  9  5 G2     1  0,5  0  0,5  8  4 G3     1  0,5  2  0,5  8  5 G     max 5,4,5  5 i Значение G     5 соответствует стратегии A1 и A3 , таким образом, критерий Гурвица при   0,5 рекомендует использовать стратегию A1 или A3 . Принятие решений в условиях риска Предположим, что в игре с природой имеется информация о возможности принятия природой того или иного состояния. Пусть p j вероятность того, что природа примет состояние Ï j , такое предположение называется частичной неопределенностью. Матрица выигрышей в этом случае примет вид: Ai \ Ï j Ï 1 Ï 2 …… Ï n A1 a11 a12 …… a1n A2 a21 a22 …… a2n ……. …… …… …… …… Am am1 am 2 …… amn pj p1 p2 …… pn n p j 1 j  1 . В этом случае для принятия решения можно использовать следующие правила. Критерий Байеса относительно выигрышей Выигрыш, получаемый игроком А при принятии i-го решения является случайной величиной Qi с рядом распределения: aij ai1 ai 2 ……. ain pj p1 p2 ……. pn Математическое ожидание M  Qi     aij  p j  n и есть средний j 1 ожидаемый выигрыш при принятии i-го решения. Правило Байеса относительно выигрышей рекомендует использовать приносящую максимальный средний выигрыш т.е стратегию, стратегия должна соответствовать значению Q  max  M  Qi  . i Например, пусть задана матрица игры: Ai \ Ï A1 j Ï 4 1 Ï 6 2 Ï 7 3 Ï 1 4 A2 3 5 2 3 A3 12 1 3 2 A4 5 8 4 10 pj 0,3 0,2 0,4 0,1 M  Q1   4  0,3  6  0,2  7  0,4  1  0,1  1,2  1,2  2,8  0,1  5,3 , M  Q2   3  0,3  5  0,2  2  0,4  3  0,1  0,9  1,0  0,8  0,3  3 , M  Q3   12  0,3  1 0,2  3  0,4  2  0,1  3,6  0,2  1,2  0,2  5,2 , M  Q4   5  0,3  8  0,2  4  0,4  10  0,1  1,5  1,6  1,6  1,0  5,7 . Q  max 5,3; 3; 5,2; 5,7   5,7 i соответствует стратегии A4 . Правило Байеса относительно выигрышей рекомендует использовать стратегию A4 . Критерий Байеса относительно рисков При использовании критерия Байеса относительно рисков используется матрица рисков. Ai \ Ï j Ï 1 Ï 2 …… Ï n A1 r11 r12 …… r1n A2 r21 r22 …… r2n ……. …… …… …… …… Am rm1 rm 2 …… rmn pj p1 p2 ……. pn Риск, получаемый игроком А при принятии i-го решения является случайной величиной Ri с рядом распределения: rij ri1 ri 2 ……. rin pj p1 p2 ……. pn Математическое M  Ri     rij  p j  n ожидание и есть средний j 1 ожидаемый риск при принятии i-го решения. Правило Байеса относительно рисков рекомендует использовать стратегию, приносящую минимальный средний риск т.е стратегия должна соответствовать значению R  min  M  Ri  . i Например, пусть задана матрица игры: Ai \ Ï j Ï 1 Ï 2 Ï 3 Ï 4 A1 4 6 7 1 A2 3 5 2 3 A3 12 1 3 2 A4 5 8 4 10 pj 0,3 0,2 0,4 0,1 Ï Ï Ï Построим матрицу рисков Ai \ Ï j Ï 1 2 3 4 A1 8 2 9 A2 9 3 5 7 A3 7 4 8 A4 7 3 pj 0,3 0,2 0,4 0,1 M  R1   8  0,3  2  0,2  0  0,4  9  0,1  2,4  0,4  0  0,9  3,7 , M  R2   9  0,3  3  0,2  5  0,4  7  0,1  2,7  0,6  2,0  0,7  6 , M  R3   0  0,3  7  0,2  4  0,4  8  0,1  0  1,4  1,6  0,8  3,8 , M  R4   7  0,3  0  0,2  3  0,4  0  0,1  2,1  0  1,2  0  3,3 . R  min 3,7; 6; 3,8; 3,3  3,3 i соответствует стратегии A4 . Правило Байеса относительно рисков рекомендует использовать стратегию A4 . Задачи оптимизации В некоторых случаях необходимо выбрать наилучшее решение из всех имеющихся решений, при этом все необходимые данные имеются. Такие задачи называются задачами оптимизации, они позволяют описать все множество имеющихся решений и выбрать из него наилучшее. Задача линейного программирования В общем случае задача линейного программирования записывается так, что ограничениями могут быть как уравнения, так и неравенства, а переменные могут быть как неотрицательными, так и произвольными. Если все ограничения являются уравнениями, а все переменные неотрицательны, то задачу линейного программирования называют канонической. Каноническая задача линейного программирования в координатной форме имеет вид a11x1  ...  a1n xn  b1 ,    . am1 x1  ...  amn xn  bm ,  x1 , x2 ,..., xn  0. Z ( X )  c1 x1  c2 x2  ...  cn xn  max (min) Каноническая задача линейного программирования в векторной форме имеет вид  AX  B,  .  X  0. Z ( X )  CX  max (min) Так как в большинстве методов решения задач линейного программирования предполагается, что система ограничений состоит из уравнений и естественных условий неотрицательности переменных, а при составлении математических моделей экономических задач ограничения формируются в основном в системы неравенств, необходимо выполнить переход от системы неравенств к системе уравнений. Это можно проделать следующим образом. К левой части неравенства a11x1  ...  a1n xn  b1 прибавляют некоторую величину xn 1 такую, чтобы неравенство превратилось в равенство a11x1  ...  a1n xn  xn 1  b1 , xn 1  0 здесь xn 1  b1  a11x1  a12x2  ...  a1n xn . Переменная величина называется дополнительной переменной. Дополнительные переменные вводятся в целевую функцию с нулевыми коэффициентами и поэтому не влияют на ее значение. Если возникает необходимость перейти в задаче от нахождения минимума к нахождению максимума и наоборот, достаточно изменить знаки всех коэффициентов целевой функции на противоположные. Наиболее известными методами решения задачи линейного программирования является графический метод и симплекс-метод. Теоретической основой линейного программирования являются две теоремы: Теорема №1. Задача линейного программирования имеет оптимальное решение тогда и только тогда, когда целевая функция ограничена на допустимом множестве в направлении экстремума. Теорема №2. Если экстремум целевой функции в задаче линейного программирования достигается, то он достигается в некоторой угловой точке допустимого множества. Рассмотрим задачу линейного программирования: 3x1  x2  6,   x1  2 x2  6,  x , x  0.  1 2 S ( x1 , x2 )  2 x1  2 x2  max Решение: На плоскости двух переменных x 1, x2 построим допустимое множество D, ограниченное 3x1  x2  6, линиями  x1  2 x2  6,  x , x  0.  1 2 x2 А В D n О С x1 2 x1  2 x2  const 2 x1  2 x2  0 Прямая АВ задается уравнением 3x1  x2  6 , а прямая x1  2 x2  6 . ВС уравнением Допустимое множество является четырехугольником АВСО. По теореме №2 максимальное значение целевая функция достигает в одной из вершин четырехугольника: О(0,0), А(0,3), С(2,0). Координаты вершины В находим из системы уравнений: 3x1  x2  6   x1  2 x2  6 значение целевой функции в этих точках Максимальное значение равно 36 5  6 12  B ,  . 5 5  Вычислим S (O)  0 , S ( A)  6 S ( B)  36 S (C )  4 . 5 ,  и достигается он при x1  6 5 и x2  12 5 . Однако чаще данную задачу решают следующим способом. Целевая функция при фиксированных значениях S ( x1, x2 ) является уравнением прямой линии 2 x1  2 x2  const . Построим прямую 2x1  2 x2  0 , она пройдет через начало координат. Все остальные прямые 2 x1  2 x2  const будут параллельны данной прямой, они называются линиями уровня. Из курса аналитической геометрии известно, что коэффициенты при переменных в уравнении прямой являются координатами нормального вектора к этой прямой. Значит, нормальный вектор линий уровня в данном случае имеет координаты n  2,2. Нормальный вектор показывает направление, в котором значения целевой функции S ( x1, x2 ) возрастают. Поэтому в поисках максимума нужно двигать линию уровня в направлении нормального вектора. Для данного случая, последней точкой в которой линия уровня коснется области допустимых решений будет точка максимум функции S  6 12  B ,  . 5 5  Значит, 36 5 . Если в задаче нужно было найти минимум линейной функции, то линию уровня надо было двигать в сторону, противоположную направлению нормального вектора. Линия уровня, имеющая общие точки с областью допустимых решений и расположенная так, что область допустимых решений целиком находится по одну сторону от данной линии, называется опорной прямой. Из курса математического анализа следует, что если допустимое множество в задаче линейного программирования ограничено, то целевая функция имеет на нем и минимум и максимум. Если же допустимое множество неограниченно, то экстремума может и не быть, тогда задача линейного программирования не имеет решения. Транспортная задача Еще одной стандартной оптимизационной задачей наряду с задачей линейного программирования является транспортная задача. Однородный груз находится у m поставщиков в объемах a1, a2 ,..., am , данный груз требуется доставить n потребителям в объемах b1, b2 ,..., bn , считаются известными cij - стоимости перевоза одной единицы груза от каждого i-го поставщика каждому j-му потребителю. Требуется составить такой план перевозок при котором запасы поставщика вывозятся полностью, запросы потребителя удовлетворяются полностью, общая стоимость перевозки грузов минимальна. Начальные условия транспортной задачи размещаются в таблице вида: ai \ b j b1 b2 ….. bn …… a1 c11 c12 c1n …… a2 c21 ….. c22 ….. c2 n ….. ….. ….. …… am cm1 cm 2 cmn Переменными транспортной задачи являются объемы перевозок от каждого i-го поставщика каждому j-му потребителю, будем обозначать их xij . Математическая модель транспортной задачи имеет вид: m  xij b j  i 1  n  xij ai  j 1  xij  0  i  1,.., m  j  1,..., n    m n Z  X    cij xij  min i 1 j 1 Для решения транспортной задачи составляем первоначальный опорный план. Рассмотрим конкретный пример: b1  11 ai \ b j b3  8 b2  7 b4  4 a1  9 2 5 8 1 8 3 9 2 7 4 6 3 a2  16 a3  5 Проверим баланс поставщиков и потребителей, найдем суммы 3 a i 1 i  9  16  5  30 , 4 b j 1 j  11  7  8  4  30 , т.к. m n  a  b i 1 i j 1 j данная задача является задачей с правильным балансом. Находим клетку таблицы с минимальной стоимостью (маленькие цифры) это 1 и в нее загружаем перевозку с учетом ограничений по строке или столбцу. В клетке с 1 (желтая) необходимость в поставке b4  4 единицы продукции, а на складе имеется a1  9 единиц продукции, следовательно со склада a1 привозим потребителю b4 4 единицы продукции. b1  11 ai \ b j b3  8 b2  7 b4  4 a1  9 2 5 8 8 3 9 2 7 4 6 3 4 1 a2  16 a3  5 Запросы потребителя b4 удовлетворены, следовательно, больше четвертый столбец не рассматриваем (я выделяю его желтым). Из оставшихся клеток вновь находим клетку с минимальной стоимостью. b1  11 ai \ b j b3  8 b2  7 b4  4 a1  9 5 2 5 8 8 3 9 2 7 4 6 3 4 1 a2  16 a3  5 Клетка стоимостью 2 потребность 11 ед., на складе a1  9  4  5 (т.к. 4 ед. уже увезли), загружаем 5 ед. и больше на складе a1 товара нет, исключаем из рассмотрения 1 строку. b1  11 ai \ b j b3  8 b2  7 b4  4 a1  9 5 2 5 8 3 9 2 4 6 3 4 1 a2  16 8 7 a3  5 7 Вновь выбираем наименьшую стоимость. Клетка стоимостью 3 потребность 7 ед., на складе a2  16 , загружаем 7 ед. и больше потребителю b2 не нужно, исключаем из рассмотрения 2 столбец. b1  11 ai \ b j b3  8 b2  7 b4  4 a1  9 5 2 5 8 3 9 2 6 3 4 1 a2  16 8 7 a3  5 7 4 5 Вновь выбираем наименьшую стоимость. Клетка стоимостью 6 потребность 8 ед., на складе a3  5 , загружаем 5 ед. и больше на складе a3 товара нет, исключаем из рассмотрения 3 строку. b1  11 ai \ b j b3  8 b2  7 b4  4 a1  9 5 2 6 8 5 8 3 9 2 6 3 4 1 a2  16 7 a3  5 7 4 5 Вновь выбираем наименьшую стоимость. Клетка стоимостью 8 потребность 6 ед.(5 ед. уже привезли), на складе a2  16  7  9 , загружаем 6 ед. и больше потребителю b1 не нужно, исключаем из рассмотрения 1 столбец. b1  11 ai \ b j b3  8 b2  7 b4  4 a1  9 5 2 5 8 6 8 3 9 3 2 4 5 6 3 4 1 a2  16 7 a3  5 7 Последняя клетка стоимостью 9 потребность 3 ед. (5 ед. уже привезли), на складе a2  16  7  6  3 , загружаем 3 ед. Таблица заполнена, получаем первоначальный опорный план. Проверим правильность составленного первоначального опорного плана для этого проверим все суммы больших цифр в строках и столбцах таблицы. b1  11 ai \ b j b3  8 b2  7 b4  4 54 9 a1  9 2 5 5 8 4 1 6  7  3  16 a2  16 6 8 7 3 9 2 3 a3  5 55 7   4 5  6  11 5 77 6 3 35 8 44 Суммы по строкам и столбцам совпадают, первоначальный опорный план составлен верно. Найдем стоимость процесса для этого в клетках, где 2 цифры умножаем большую цифру (объем перевезенной продукции) на маленькую (стоимость перевозки одной единицы) и все складываем. Z  X   5  2  4 1  6  8  7  3  3  9  5  6  140 у.е. Полученный первоначальный опорный план должен быть проверен на оптимальность (т.е. самый дешевый вариант перевозок найден или нет). Для проверки оптимальности используют метод потенциалов. Важно проверить, чтобы число заполненных клеток таблицы (где стоит большая цифра) равно m(число строк)+n(число столбцов)-1, если заполненных клеток меньше необходимо поставить 0 в одной из клеток (лучше, где стоимость поменьше). ai \ b j b1  11 b2  7 b3  8 b4  4 a1  9 54 9 2 5 5 8 4 1 a2  16 6  7  3  16 6 8 7 3 9 2 3 a3  5 55 7   5  6  11 4 77 5 6 3 35 8 44 В нашем случае заполненных клеток 6 (они выделены голубым), а должно быть 3+4-1=6 тоже 6, дозаполнять таблицу не нужно. Потенциалы (числа) поставщиков ui и потребителей vj должны удовлетворять следующим соотношениям: ui  v j  cij , ï ðè xij  0 (ò.å. äëÿ çàï î ëí åí í û õ êëåòî ê) (1) ui  v j  cij , ï ðè xij  0 (ò.å. äëÿ ï óñòû õ êëåòî ê) (2) Равенства (1) представляют собой систему уравнений для определения всех ui и v j . Одно неизвестное в системе задают самостоятельно, а остальные находят. Неравенства (2) служат для проверки оптимальности опорного плана, если хотя бы одно из неравенств не выполняется, опорный план не является оптимальным и его можно улучшить. Вернемся к задаче, каждая заполненная клетка имеет свое место (номер строки i и номер столбца j). Составим систему уравнений для заполненных клеток: (1,1) u1  v1  2 первая заполненная клетка 1 строка и 1 столбец, i=1, j=1, 2 –стоимость клетки. (1,4) u1  v4  1 , (2,1) u2  v1  8 , (2,2) u2  v2  3 , (2,3) u2  v3  9 , (3,3) u3  v3  6 Получаем систему из 6 уравнений, одну переменную задаем самостоятельно, например, u1  0 , а остальные находим. v1  2 v4  1 u2  v1  8 , u2  2  8 , u2  6 u2  v2  3 , 6  v2  3 , v2  3 u2  v3  9 , 6  v3  9 , v3  3 u3  v3  6 , u3  3  6 , u3  3 Все потенциалы найдены. Проверим пустые клетки, проверим выполняются ли оптимизационные неравенства для пустых клеток. (1,2) u1  v2  c12 , 0  3  5 - выполняется, (1,3) u1  v3  c13 , 0  3  8 - выполняется, (2,4) u2  v4  c24 , 6  1  2 - нарушение оптимальности, (3,1) u3  v1  c31 , 3  2  7 - выполняется, (3,2) u3  v2  c32 , 3  3  4 - выполняется, (3,4) u3  v4  c34 , 3  1  3 - нарушение оптимальности. Обнаружено две клетки в которых нарушено условие оптимальности, следовательно, опорный план не является оптимальным и его можно улучшить. Для улучшения опорного плана строят цикл пересчета. Циклом пересчета в таблице условий транспортной задачи называется замкнутая ломаная линия (квадрат, прямоугольник) вершины которой находятся в клетках таблицы (одна клетка свободная, остальные занятые), а звенья параллельны строкам и столбцам таблицы. Вершинам цикла, начиная с вершины в свободной клетке поочередно присваивают знаки +, -, +, - и т.д. Из клеток со знаком – выбирается минимальная перевозка (большая цифра) и она перемещается по циклу. В результате получаем новый опорный план, который вновь должен быть проверен на оптимальность. ai \ b j b1  11 a1  9 +4 a2  16 5 8 4 8 54 9 1 -4 6  b4  4 -4 2 5 b3  8 b2  7 6  7  3  16 +4 7 3 9 2 3 a3  5 55 7  5  6  11 4 5 77 6 3 35 8 44 Цикл изображен красной пунктирной линией, одна из вершин цикла в пустой «плохой» клетке (не выполняется условие оптимальности). В клетках со знаком – две большие перевозки 6 и 4. Минимальная из них 4, поэтому ко всем + и – подписываем по 4 единицы. ai \ b j b1  11 b2  7 b3  8 b4  4 a1  9  99 9 2 5 8 1 a2  16 2  7  3  4  16 2 8 7 3 9 3 4 2 a3  5 55 7  9  2  11 4 5 77 6 3 35 8 44 Обязательно нужно проверить суммы по строкам и столбцам, они должны сохраняться. Только тогда преобразования правильны!!! Получили новый опорный план «улучшенный», считаем затраты Z  X   9  2  2  8  7  3  3  9  4  2  5  6  120 у.е. Общая стоимость перевозок уменьшилась!!! Проверяем оптимальность: (1,1) u1  v1  2 (2,1) u2  v1  8 , (2,2) u2  v2  3 , (2,3) u2  v3  9 , (2,4) u2  v4  2 , (3,3) u3  v3  6 Получаем систему из 6 уравнений, одну переменную задаем самостоятельно, например, u1  0 , а остальные находим. v1  2 u2  v1  8 , u2  2  8 , u2  6 u2  v2  3 , 6  v2  3 , v2  3 u2  v3  9 , 6  v3  9 , v3  3 u2  v4  2 , 6  v4  2 , v4  4 u3  v3  6 , u3  3  6 , Все потенциалы u3  3 найдены. Проверим пустые клетки, проверим, выполняются ли оптимизационные неравенства для пустых клеток. (1,2) u1  v2  c12 , 0  3  5 - выполняется, (1,3) u1  v3  c13 , 0  3  8 - выполняется, (1,4) u1  v4  c14 , 0  4  2 - выполняется, (3,1) u3  v1  c31 , 3  2  7 - выполняется, (3,2) u3  v2  c32 , 3  3  4 - выполняется, (3,4) u3  v4  c34 , 3  4  3 - выполняется. Полученный опорный план является оптимальным, минимальная стоимость перевозки грузов 120 у.е. Получить меньшую стоимость в данных условиях невозможно! Планирование эксперимента в играх с природой Предположим, что в игре с природой П игрок А имеет m стратегий A1, A2 ,..., Am , природа П может находиться в одном из своих n состояний Ï 1, Ï 2 ,..., Ï n с соответствующими вероятностями q1, q2 ,..., qn и задана матрица выигрышей игрока А Ai \ Ï j Ï 1 Ï 2 …… Ï n A1 a11 a12 …… a1n A2 a21 a22 …… a2n ……. …… …… …… …… Am am1 am 2 …… amn qj q1 q2 …… qn Будем рассматривать «идеальный» эксперимент, который характеризуется тем, что в результате его проведения мы получим точное знание того состояния природы Ï j , которое имеет место в данной ситуации. Пусть материальные затраты на проведение эксперимента равны с. n Пусть a  max ai , где ai   q j aij - показатель эффективности стратегии 1i m j 1 Ai по критерию Байеса относительно выигрышей представляющий собой взвешенно средний выигрыш с весовыми коэффициентами q j . Тогда a это максимальный взвешенно средний выигрыш игрока А. n Пусть    q j  j , где  j  max aij j 1 - показатель благоприятности 1i  m состояния природы Ï j , представляющий собой максимальный выигрыш при состоянии природы Ï j . Тогда  - взвешенно среднее максимальных выигрышей  j . Теорема. Идеальный эксперимент целесообразно проводить при условии выполнения неравенства c    a , т.е. когда затраты с на проведение эксперимента меньше разности между взвешенно средним максимальным выигрышем  и максимальным взвешенно средним выигрышем a , и не целесообразно проводить при справедливости неравенства c    a . Данную теорему можно переформулировать в терминах рисков. n Пусть r  min ri , где ri   q j rij , rij   j  aij - риски игрока А при выборе 1i  m j 1 им стратегии Ai в условиях состояния природы Ï j . ri - показатель неэффективности стратегии Ai по критерию Байеса относительно рисков, r - минимальный взвешенно средний риск. Теорема. Целесообразность идеального эксперимента имеет место, если затраты с на его проведение меньше минимально взвешенно среднего риска r : c  r , и его не нужно проводить, если выполняется неравенство cr .