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

Введение в теорию игр В коммерческой деятельности часто приходится принимать решения, учитывая множество факторов различной природы. Причем, спецификация коммерческой деятельности такова, что учитываемые при принятии решений факторы часто обладают свойством неопределенности, т.к. нельзя заранее определить точно, каково будет значение того или иного фактора или показателя. Следовательно, и результат принятия решения будет обладать свойством неопределенности. Неопределенность значений, управляемых факторов приводит к тому, что рекомендации по решению проблемы не могут быть столь же четкими и однозначными как в случаях полной определенности. В процессе принятия решений появляются возможные варианты решений. Поэтому можно считать, что принятие решения состоит в выборе наилучшего варианта из имеющихся. Для решения любой проблемы, независимо от ее характера, существенным является вопрос: кто должен быть поставлен перед проблемой? Т.е. должно существовать некое лицо, принимающее решение. Лицо, принимающее решение – это некий реально существующий индивидуум (или группа), которую не устраивает состояние дел или перспектива их будущего состояния, и который имеет полномочия действовать так, чтобы это состояние изменилось. Разработаны специальные математические методы, предназначенные для обоснования решений в условиях неопределенности. В простых случаях эти методы позволяют найти множество решений и выбрать из них оптимальное. В более сложных случаях эти методы дают вспомогательный материал, позволяющий глубже разобраться в сущности явлений и оценить каждое из возможных решений с различных точек зрения, взвесить все преимущества и недостатки и принять если не единственно правильное, то по крайней мере близкое к оптимальному решению. При выборе решения в условиях неопределенности всегда неизбежен элемент произвола, а значит и риска. Недостаточность информации всегда опасна и за нее приходится платить. Поэтому в условиях сложной ситуации необходимо представить варианты решения и их последствий в такой форме, чтобы сделать произвол выбора менее сильным, а риск – минимальным. Задачами о принятии решений в условиях полной или частичной неопределенности занимается теория игр и статистических решений. В коммерческой деятельности часто приходится принимать решения в условиях противодействия другой стороны, которая может преследовать противоположные или иные цели, добиваться других путей достижения цели, препятствовать теми или иными действиями или состояниями внешней среды достижению намеченной цели. Причем эти противодействия противоположной стороны могут носить пассивный или активный характер. В этих случаях приходится учитывать возможные варианты поведения противоположной стороны, ответные действия, возможную реакцию. Возможные варианты поведения обеих сторон, их исходов для каждого сочетания альтернатив и состояний можно представить в виде математической модели, называемой игрой. Если в качестве противоположности выступает неактивная, пассивная сторона, которая явно активно не противодействует достижению намеченной цели, то такие игры называются играми с природой. В других ситуациях противоположная сторона активно, сознательно может противостоять достижению намеченной цели. В подобных случаях происходит столкновение противоположных интересов. Такие ситуации называются конфликтными, а принятие решений в конфликтных ситуациях затрудняется из-за неопределенности поведения противника. Известно, что противник сознательно стремится предпринять наименее выгодные для вас действия, чтобы обеспечить себе наибольший успех. Неизвестно, в какой мере противник умеет оценивать обстановку и возможные последствия, как он оценивает ваши возможности и намеренья. Обе стороны конфликта не могут точно предсказать взаимные действия. Несмотря на такую неопределенность, принимать решение приходится каждой стороне конфликта. Теория игр – это математическая теория конфликтных ситуаций. Основными ограничениями этой теории являются предположения о полной («идеальной») разумности противника и принятие при разрешении конфликта наиболее осторожного «перестраховочного» решения. Основные понятия теории игр Конфликтующие в игре стороны называются игроками, одна реализация игры – партией, исход игры – выигрышем или проигрышем. Развитие игры во времени происходит последовательно, по этапам, называемым ходами. Ходом в теории игр называют выбор одного из предусмотренных правилами игры действий и его реализацию. Ходы бывают личные и случайные. Личным ходом называют сознательный выбор игроком одного из возможных вариантов действия и его осуществление. Случайным ходом называют выбор, осуществляемый не волевым решением игрока, а каким-либо механизмом случайного выбора. Одним из основных понятий теории игр является стратегия. Стратегией игрока называют совокупность правил, определяющий выбор варианта действия при каждом личном ходе этого игрока в зависимости от ситуации, сложившейся в процессе игры. Оптимальной стратегией игрока называется такая стратегия, которая при многократном повторении игры, содержащей личные и случайные ходы, обеспечивает игроку максимально возможный средний выигрыш (минимально возможный средний проигрыш). В большинстве конфликтных ситуаций при выборе разумной стратегии приходится принимать во внимание не один, а несколько показателей. Причем стратегия, оптимальная по одному показателю, не обязательно будет оптимальной по другому. В зависимости от причин, вызывающих неопределенность исходов игры делятся на следующие основные группы. 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. Сальдо ΔΣ(АС)=500-1500=-1000 (А→С при окончательном расчете). При расчетах между В и С С→В 800, В→С 700. Сальдо ΔΣ(АС)=800-700=+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 стратегий , а игрок B имеет n стратегий . Такая игра называется игрой размерностью . Пусть каждый игрок выбирает определенную стратегию: игрок А – стратегию , игрок В – стратегию . В этом случае игра приведена к матричному виду и называется матричной игрой. Пусть - выигрыш игрока А в ситуации когда игрок выбрал стратегию , а игрок В выбрал стратегию . Выигрыш игрока В в данной ситуации будем обозначать , т.к. рассматриваемая игра с нулевой суммой, то и для исследования необходимо знать выигрыш только одного из игроков, например, игрока А. Если игра состоит только из личных ходов, то выбор стратегии однозначно определяет исход игры, т.е. выигрыш игрока А - . Если игра содержит так же случайные ходы, то выигрыш при паре стратегий есть случайная величина, зависящая от исходов всех случайных ходов. В этом случае ожидаемый выигрыш – это среднее значение (математическое ожидание случайной величины). Пусть известны для каждой пары стратегий . Составим прямоугольную таблицу, строки которой соответствуют стратегиям игрока А, а столбцы – стратегиям игрока В. ………….. …………. …………. …………. …………. …………. …………. …………. …………. Если такая таблица составлена, то игра приведена к матричной форме и называется матричной игрой, таблица называется платежной матрицей. Каждый элемент матрицы определяет величину выигрыша игрока А и проигрыш игрока В при применении пары стратегий . Цель игрока А – максимизировать свой выигрыш, а игрока В – минимизировать свой проигрыш. Принцип минимакса Пусть задана платежная матрица: ………….. …………. …………. …………. …………. …………. …………. …………. …………. Необходимо определить: 1) наилучшую (оптимальную) стратегию игрока А из стратегий ; 2) наилучшую (оптимальную) стратегию игрока В из стратегий. Для решения этой задачи применим принцип, согласно которому участники игры одинаково разумны и каждый из них делает все для того, чтобы добиться своей цели. Обозначим -минимальный выигрыш игрока А при применении им стратегии . Выбирая стратегию , игрок А должен рассчитывать на то, что в результате разумных действий игрока В он не выиграет больше, чем . Поэтому, далее игрок А должен выбрать стратегию для которой число максимально . Величина - гарантированный выигрыш игрока А при любом поведении игрока В, которая называется нижней ценой игры. Стратегия , обеспечивающая получение нижней цены игры называется максиминной чистой стратегией, при этом игрок А при любом поведении игрока В обеспечивает себе выигрыш . Игрок В заинтересован в уменьшении своего проигрыша, т.е. его цель обратить выигрыш игрока А в минимум. Для реализации этой цели игрок В сначала должен выбрать - максимальный проигрыш игрока В при применении им стратегии . Выбирая стратегию , игрок В должен рассчитывать на то, что в результате разумных действий игрока А он не проиграет меньше, чем . Поэтому, далее игрок В должен выбрать стратегию для которой число минимально . Величина - гарантированный проигрыш игрока В при любом поведении игрока А, которая называется верхней ценой игры. Стратегия , обеспечивающая получение верхней цены игры называется минимаксной чистой стратегией, при этом игрок В при любом поведении игрока А обеспечивает себе проигрыш . Таким образом придерживаясь максиминной стратегии игрок А получает выигрыш не менее чем , а игрок В придерживаясь минимаксной стратегии гарантирует себе проигрыш не более чем . Понятие чистой стратегии. Игры с седловыми точками Существуют матрицы игры, для которых . Такие игры называются играми с седловой точкой, в этом случае значение называется чистой ценой игры, а стратегии и , позволяющие достичь этого значения называются оптимальными. Игровая ситуация называется седловой точкой матрицы игры. Матрица игры может обладить несколькими седловыми точками. Свойства седловых точек 1) Теорема (свойство равнозначности) Если и седловые точки, то . 2) Теорема (свойство взаимозаменяемости) Если и седловые точки, то и - так же седловые точки. Устойчивые и неустойчивые игровые ситуации. Рассмотрим матрицу игры: -3 4 4 -3 1 -2 1 -2 4 4 -2 -2 4 4 4 4\-2 Максиминными стратегиями игрока А являются стратегии и , а минимаксными стратегиями игрока В являются стратегии , , . Пусть игрок А придерживается стратегии . Зная об этом игрок В, с целью получения наибольшего выигрыша выбирает стратегию и получает выигрыш . В ответ игрок А должен выбрать стратегию или . Так как в результате использования этих стратегий он получит максимальный выигрыш . При любом из этих выборов игрок А отклоняется от своей первоначальной стратегии . Допустим, А остановился на стратегии и получил выигрыш . В ответ игрок В выберет стратегию и получит максимальный выигрыш . При этом В отклоняется от своей первоначальной стратегии . Если В выбрал стратегию , игрок А должен выбрать стратегию , получив максимальный выигрыш , отклонившись от предыдущей стратегии и т.д. Таким образом, ситуации, складывающиеся после очередных ходов игроков, являются неустойчивыми. 0,7 0,5 0,3 0,3 0,6 0,9 0,4 0,4 0,7 0,9 0,4 0,4\0,4 В данной игре имеем седловую точку т.к. . Если игрок А придерживается максиминной стратегии , то игрок В должен выбрать стратегию , чтобы выигрыш игрока А был минимальным . На это игрок А должен ответить выбором опять же стратегии , чтобы получить максимальный выигрыш . Далее игрок В опять выбирает стратегию и т.д. Таким образом, если игроки А и В придерживаются своих максиминных и минимаксных стратегий соответственно, то ни один из них не может увеличить свой выигрыш отступая от своей стратегии. Ситуация является в данной игре устойчивой (или равновесной). Оптимальные чистые стратегии Показатели эффективности и неэффективности стратегий. Рассмотрим игру . Обозначим через - множество стратегий игрока А, через . Стратегии и игроков А и В, создающие равновесную ситуацию или соответствующие седловой точке называются оптимальными чистыми стратегиями. Обозначим через и - множества чистых оптимальных стратегий игроков А и В. Если нижняя цена игры равна верхней цене игры , то их общее значение называется ценой игры в чистых стратегиях. Совокупность множеств и чистых оптимальных стратегий игроков А и В и цены игры называются полным решением игры в чистых стратегиях. Решение игры характеризуется тем свойством, что ни одному из игроков А и В, придерживающихся одной из своих оптимальных стратегий невыгодно от нее отклоняться, т.к. в этом случае он не увеличит своего выигрыша. Пусть задана матрица игры ………….. …………. …………. …………. …………. …………. …………. …………. …………. Ситуация называется удовлетворительной для игрока А, если и удовлетворительной для игрока В, если . Теорема1: ситуация будет удовлетворительна для игрока А тогда и только тогда, когда его выигрыш совпадает с показателем неэффективности стратегии игрока В, , т.е. будет максимальным в -м столбце матрицы игры. Теорема2: ситуация будет удовлетворительна для игрока В тогда и только тогда, когда его проигрыш совпадает с показателем эффективности стратегии игрока А, , т.е. будет минимальным в -й строке матрицы игры. Алгоритм нахождения удовлетворительных ситуаций для игрока А: в каждом столбце матрицы игры находится наибольший элемент - показатель неэффективности стратегии игрока В, затем строку в которой стоит элемент , ситуация будет удовлетворительной для игрока А. Алгоритм нахождения удовлетворительных ситуаций для игрока В: в каждой строке матрицы игры находится наименьший элемент - показатель эффективности стратегии игрока А, затем столбец в которой стоит элемент , ситуация будет удовлетворительной для игрока В. Ситуация называется равновесной или устойчивой или седловой точкой игры, если она удовлетворительна для каждого из игроков А и В т.е. если выполняются неравенства или на основании теорем 1 и 2 . Теорема: для того, чтобы существовала цена игры в чистых стратегиях (т.е. ) необходимо и достаточно существования у матрицы этой игры седловой точки. Справедливы следующие утверждения: 1) Каждая оптимальная стратегия игрока А является его максиминной стратегией, а каждая оптимальная стратегия игрока В является его минимаксной стратегией. 2) В игре без седловых точек ни одна из максиминных и минимаксных стратегий не является оптимальной, в этой игре вообще нет оптимальных стратегий. 3) В игре с седловыми точками каждая максиминная и минимаксная стратегии игроков А и В являются оптимальными. Понятие смешанной стратегии. Рассмотрим игру без седловых точек . Если такая игра повторяется многократно, то каждый из игроков имеет информацию о предыдущих ходах противника, а с другой стороны хочет скрыть информацию о своих намерениях и будущих ходах. В этом случае возникает вопрос: нельзя ли игрокам выбрать какой- то образ действий не сводящийся к использованию одной единственной чистой стратегии с тем, чтобы скрыть свои возможные действия от противника и в результате этого увеличить минимально гарантированный выигрыш игрока А и уменьшить максимально гарантированный проигрыш игрока В. Т.е. это вопрос о разделе разности между игроками А и В с максимальной пользой для каждого из них. Такой способ состоит в случайном чередовании чистых стратегий. Стратегия игрока, состоящая в случайном выборе одной из его чистых стратегий называется смешанной стратегией. Смешанная стратегий представляет собой дискретную случайную величину, значениями которой являются номера его чистых стратегий. Показатели эффективности и неэффективности смешанных стратегий. Функция выигрыша. Из теории вероятностей известно, что случайная величина определяется законом распределения вероятностей. Обозначим через Р – смешанные стратегии игрока А, через Q – смешанные стратегии игрока В. Р задается законом распределения вероятностей: i 1 2 …. m P …. Q задается законом распределения вероятностей: j 1 2 …. n Q …. Если - множество чистых стратегий игрока А и известно, что каждая смешанная стратегия Р определятся вероятностями с которыми выбираются игроком А соответствующие чистые стратегии, поэтому смешанную стратегию можно представить с помощью m-мерного вектора . Аналогично определяются смешанные стратегии игрока В - . Если игроки А и В независимо друг от друга выбрали смешанные стратегии и соответственно, то упорядоченная пара называется ситуацией в смешанных стратегиях. В условиях ситуации в смешанных стратегиях чистые стратегии и выбираются независимо друг от друга с вероятностями и соответственно. Вероятность выбора пары , так как в ситуации в чистых стратегиях игрок получает выигрыш . Вероятность этого выигрыша составляет . Таким образом выигрыш игрока А в ситуации в смешанных стратегиях представляет собой дискретную случайную величину принимающую значение с вероятностью , а средний выигрыш игрока А равен математическому ожиданию этой случайной величины . Функция выигрыша в смешанных стратегиях или в матричном виде , где А – матрица игры. Теорема: Для каждой смешанной стратегии игрока А существует . Для каждой смешанной стратегии игрока В существует . Число называется показателем эффективности смешанной стратегии игрока А относительно множества смешанной стратегии игрока В. Если множество смешанных стратегий игрока В заменить на множество - чистых стратегий, то получим - показатель эффективности смешанной стратегии игрока А относительно множества чистых стратегий игрока В. Число называется показателем эффективности смешанной стратегии игрока А относительно множества смешанных стратегий игрока В. Теорема: Показателем эффективности любой смешанной стратегии игрока А относительно множеств и чистых и смешанных стратегий игрока В равны т.е. . Число называется показателем неэффективности смешанной стратегии игрока В относительно множества смешанной стратегии игрока А. Если множество смешанных стратегий игрока А заменить на множество - чистых стратегий, то получим - показатель неэффективности смешанной стратегии игрока В относительно множества чистых стратегий игрока А. Число называется показателем неэффективности смешанной стратегии игрока В относительно множества смешанных стратегий игрока А. Теорема: Показателем неэффективности любой смешанной стратегии игрока В относительно множеств и чистых и смешанных стратегий игрока А равны т.е. . Нижняя и верхняя цены игры в смешанных стратегиях. Оптимальные смешанные стратегии. Нижней ценой игры или максимином матричной игры в смешанных стратегиях называется величина . Верхней ценой игры или минимаксом матричной игры в смешанных стратегиях называется величина . Теорема: Для любой конечной матричной игры существует нижняя и верхняя цены игры в смешанных стратегиях. Теорема: Нижняя цена игры и верхняя цена игры в чистых стратегиях, нижняя цена игры и верхняя цена игры в смешанных стратегиях удовлетворяют неравенству: . Для произвольной матрицы игры А , где и - смешанные стратегии на которых достигаются экстремумы. Стратегии и для которых выполняется соотношение называются оптимальными, пара - седловой точкой функции или ситуацией равновесия в смешанных стратегиях. Для того, чтобы стратегии и были оптимальными в игре с матрицей А необходимо и достаточно чтобы выполнялось соотношение . Число называется ценой игры в смешанных стратегиях. Принцип доминирования Доминирующие и доминируемые строки (столбцы) игровой матрицы. Пусть задана матрица игры размерностью ………….. …………. …………. …………. …………. …………. …………. …………. …………. Каждой смешанной стратегии игрока А поставим в соответствие строку элементами которой являются выигрыши игрока А в ситуациях . - комбинация строк матрицы А. Если для двух комбинаций строк матрицы А: Выполняются неравенства: , , …………………., , То строка (2) доминирует строку (1), а строка (1) доминируется строкой (2). Если каждое из неравенств является равенством, то строки называют дублирующими друг друга. Аналогично для стратегий игрока А: стратегия доминирует (дублирует) стратегию . Для игрока В: каждой смешанной стратегии игрока В поставим в соответствие строку элементами которой являются выигрыши игрока В в ситуациях . - комбинация строк матрицы А. Если для двух комбинаций строк матрицы А: Выполняются неравенства: , , …………………., , То столбец (4) доминирует столбец (3), а столбец (3) доминируется столбцом (4). Если каждое из неравенств является равенством, то столбцы называют дублирующими друг друга. Аналогично для стратегий игрока В: стратегия доминирует (дублирует) стратегию . Разбиение игровой матрицы на подматрицы. Иногда матрица игры бывает такой, что горизонтальными и вертикальными линиями ее можно разбить на подматрицы, в каждой из которых суммы элементов в строках равны между собой. Т.е. каждая из этих подматриц составлена из элементов стоящих на пересечениях некоторого числа соседних строк и некоторого числа соседних столбцов. Если подматрица образована k+1 строками с номерами и столбцом с номерами , то будем обозначать ее через . Теорема: Пусть подматрица обладает следующими свойствами: (1) (2) Тогда справедливы следующие предложения: 1) Если данная подматрица состоит из единственной строки, т.е. если k=0, , то все элементы этой строки равны между собой. 2) Если данная подматрица состоит из единственного столбца, т.е. если , , , то все элементы этого столбца равны между собой. 3) Если данная подматрица квадратная, то сумма элементов каждой строки равна сумме элементов каждого столбца. Аналитическое решение игры 2х2 Рассмотрим игру с матрицей Аi\Bj B1 B2 A1 a11 a12 A2 a21 a22 Если матрица игры имеет седловую точку, то игра имеет решение в чистых стратегиях . Критерий существования седловой точки в игре 2х2. Теорема Пусть ; - номера строк и столбцов матрицы А. Для того, чтобы элемент был седловой точкой матрицы А необходимо и достаточно выполнение хотя бы одного из двух условий: 1) можно удалить -ю строку, как доминируемую -й строкой, а затем в оставшейся -й строке можно удалить -й столбец как доминируемый -м столбцом; 2) можно удалить -й столбец, как доминируемый -м столбцом, а затем в оставшемся -м столбце удалить -ю строку, как доминируемую -й строкой. Например, Аi\Bj B1 B2 A1 5 3 A2 1 2 Вторая строка доминируется первой строкой, следовательно, может быть удалена. Из оставшихся столбцов второй столбец доминирует первый, следовательно, первый столбец можно удалить. Получаем решение в чистых стратегиях . Или Аi\Bj B1 B2 A1 4 4 A2 1 2 Вторая строка доминируется первой строкой, следовательно, может быть удалена. Оставшиеся столбцы дублируют друг друга. Следовательно, у игрока А одна оптимальная стратегия A1, а у игрока В две оптимальных стратегии B1 и B2. Решение игры в чистых стратегиях . Теорема Для того, чтобы у матрицы А (2х2) существовала седловая точка необходимо и достаточно, чтобы сумма элементов главной диагонали матрицы А равнялась сумме элементов ее побочной диагонали (это условие является достаточным, но не является необходимым). Следствие Для того, чтобы у матрицы А (2х2) не существовало седловой точки необходимо и достаточно, чтобы сумма элементов главной диагонали матрицы А не равнялась сумме элементов ее побочной диагонали (это условие является необходимым, но не является достаточным). Теорема Пусть матрица А (2х2) не имеет седловой точки. Тогда каждый из игроков А и В обладает единственной оптимальной смешанной стратегией и . Которые находятся по формулам: ; ; ; ; . Доказательство: Пусть и - оптимальные смешанные стратегии игроков А и В. По определению оптимальных смешанных стратегий . Так как матрица А не имеет седловых точек, пассивных стратегий в игре не существует, т.е. стратегии B1 и B2 активны. По теореме об активных стратегиях т.е. . Решим систему уравнений, приравняем первое и второе уравнения , , , , , , , , , . Геометрическое решение игры 2х2 Пусть дана матрица игры Аi\Bj B1 B2 A1 a11 a12 A2 a21 a22 Пусть Р(1-р,р) – смешанная стратегия игрока А, , при р=0 смешанная стратегия превращается в чистую стратегию , при р=1 в чистую стратегию . Пусть игрок А выбирает смешанную стратегию Р(1-р,р), а игрок В чистую стратегию , тогда в ситуации игрок А получит выигрыш - линейная функция вероятности р, определенная на отрезке . График такой функции – отрезок прямой, заключенный между перпендикулярами к отрезку , проведенных в его концах. При р=0, ; при р=1, . Если игрок А выбирает стратегию Р(1-р,р), а игрок В чистую стратегию , то Показатель эффективности смешанной стратегии Р(1-р,р) - есть функция, являющаяся нижней огибающей функций и (ломаная ). следовательно, V (цена игры) равна ординате точки N. Так как , то показатель эффективности стратегии изображается точкой на левом перпендикуляре. А показатель эффективности стратегии изображается нижней точкой на правом перпендикуляре. Так как нижняя цена игры в чистых стратегиях (верхняя из точек и . Аналогично, показатель неэффективности стратегии при равен . , а показатель неэффективности стратегии при равен т.е и так как верхняя цена игры в чистых стратегиях , . Общий алгоритм геометрического нахождения оптимальных стратегий игрока А 1. Строим горизонтальный отрезок . 2. Из концов отрезка точки 0 и точки 1 проводим 2 перпендикуляра. 3. На левом перпендикуляре от точки 0 откладываем элементы и . 4. На правом перпендикуляре от точки 1 откладываем и . 5. Соединяем точки, изображающие элементы с одинаковыми вторыми индексами и , и . 6. Если отрезки и возрастающие, то стратегия доменирует стратегию . 7. Если отрезок лежит ниже отрезка , то стратегия доменирует стратегию . 8. Находим нижнюю огибающую отрезков и . 9. Находим наивысшую точку (или точки) нижней огибающей. 10. Проектируем их ортогонально на отрезок . 11. Полученная проекция определяет оптимальную стратегию игрока А - Р(1-р,р). 12. Ордината наивысшей точки нижней огибающей равна цене игры V. 13. Верхний, из двух концов нижней огибающей есть нижняя цена игры в чистых стратегиях . 14. Нижний из двух верхних концов отрезков и есть верхняя цена игры в чистых стратегиях . 15. Если элемент является нижним, на перпендикуляре, где он лежит и верхним концом отрезка или , на котором он лежит, то этот элемент является седловой точкой. В этом случае чистая стратегия игрока В, номер которой совпадает со вторым индексом седловой точки является оптимальной. Геометрическое решение игры 2х2 (продолжение) Пусть дана матрица игры Аi\Bj B1 B2 A1 a11 a12 A2 a21 a22 Пусть Q(1-q,q) – смешанная стратегия игрока B, , при q=0 смешанная стратегия превращается в чистую стратегию , при q=1 в чистую стратегию . Пусть игрок B выбирает смешанную стратегию Q(1-q,q), а игрок A чистую стратегию , тогда в ситуации игрок B получит выигрыш - линейная функция вероятности q, определенная на отрезке . График такой функции – отрезок прямой, заключенный между перпендикулярами к отрезку , проведенных в его концах. При q=0, ; при р=1, . Если игрок B выбирает стратегию Q(1-q,q), а игрок A чистую стратегию , то Показатель неэффективности смешанной стратегии Q(1-q,q) - есть функция, являющаяся верхней огибающей функций и (ломаная ). следовательно, V (цена игры) равна ординате точки M. Общий алгоритм геометрического нахождения оптимальных стратегий игрока B 1. Строим горизонтальный отрезок . 2. Из концов отрезка точки 0 и точки 1 проводим 2 перпендикуляра. 3. На левом перпендикуляре от точки 0 откладываем элементы и . 4. На правом перпендикуляре от точки 1 откладываем и . 5. Соединяем точки, изображающие элементы с одинаковыми первыми индексами и , и . 6. Находим верхнюю огибающую отрезков и . 9. Находим наинизшую точку (или точки) верхней огибающей. 10. Проектируем их ортогонально на отрезок . 11. Полученная проекция определяет оптимальную стратегию игрока B - Q(1-q,q). 12. Ордината наивысшей точки нижней огибающей равна цене игры V. 13. Нижний, из двух концов верхней огибающей, есть верхняя цена игры в чистых стратегиях . 14. Верхний из двух нижних концов отрезков и есть нижняя цена игры в чистых стратегиях . Пример. Найти оптимальную смешанную стратегию игрока В. Аi\Bj B1 B2 A1 2 5 A2 7 3 По принципу минимакса , , . Найдем q и V из уравнений , , , , , . Искомая смешанная стратегия игрока B - . Найдем V. , . Таким образом выигрыш, полученный для игрока А и для игрока В одинаков , это дает дополнительный контроль правильности решения. Совместим оба рисунка: Решение игры 2хn Пусть дана матрица игры ………….. …………. …………. Показатель эффективности стратегии игрока А: . Пусть , , тогда . Таким образом, есть нижняя огибающая n линейных функций от вероятности , графиком каждой из которых является прямая. Стратегия , удовлетворяющая равенству является оптимальной стратегией игрока А, т.е. абсцисса наивысшей точки нижней огибающей определяет оптимальную стратегию , придерживаясь которой игрок А выбирает чистую стратегию с вероятностью , а чистую стратегию с вероятностью . Цена игры т.е. равна ординате максимальной точки нижней огибающей. Алгоритм геометрического нахождения оптимальных стратегий игрока А и цены игры V в игре 2хn 1) Строим горизонтальный отрезок . 2) Из концов отрезка проводим два перпендикуляра. 3) На левом перпендикуляре от точки 0 откладываем, соблюдая масштаб, все элементы первой строки матрицы игры. 4) На правом перпендикуляре от точки 1 откладываем, соблюдая масштаб, все элементы второй строки матрицы игры. 5) Каждую пару точек, изображающих элементы и , стоящие в j-м столбце матрицы игры соединяем отрезками . Таким образом получим n отрезков, представляющих собой графики n линейных функций . 6) Если все отрезки возрастающие, то стратегия доминирует стратегию . 7) Если все отрезки убывающие, то стратегия доминирует стратегию . 8) Если отрезок , лежит не ниже отрезка , , то стратегия доминирует стратегию . 9) Находим нижнюю огибающую семейства отрезков. 10) На нижней огибающей находим максимальную точку или точки. 11) Абсцисса этой точки является вероятностью выбора игроком А чистой стратегии в оптимальной смешанной стратегии . 12) Ордината наивысшей точки нижней огибающей является ценой игры V. 13) Верхний из двух концов нижней огибающей есть нижняя цена игры в чистых стратегиях 14) Нижний, из верхних концов отрезков есть верхняя цена игры в чистых стратегиях 15) Элемент матрицы игры, изображающая точка которого является нижней на перпендикуляре, где она лежит и одновременно верхним концом одного из отрезков будет седловой точкой игры. Например, дана матрица игры 5 -1 1 -2 6 3 -2 4 3 2 7 1 4 1 5 3 2 7 6 4 Применим принцип минимакса , , . Строим чертеж: На чертеже 6 прямых линий, т.к. в матрице игры у игрока В 6 стратегий. Нижняя огибающая семейства прямых на чертеже выделена красным цветом. От максимальной точки М нижней огибающей идут синие пунктирные линии, они определяют и V. Точка М лежит на пересечении прямых и соответственно для нахождения смешанной стратегии игрока А и цены игры V используем формулу , где за j возьмем 3 и 5. Получим два уравнения: Подставим значения: Смешанная стратегия игрока А - совпадает с чертежом, что важно! Найдем V из уравнения . , так же совпадает с графиком и с результатом полученным по признаку минимакса . Для игрока В найти оптимальную смешанную стратегию не возможно. Решение игры mx2 Пусть дана матрица игры …… …… …… Показатель неэффективности стратегии игрока В: . Пусть , , тогда . Таким образом, есть верхняя огибающая m линейных функций от вероятности , графиком каждой из которых является прямая. Стратегия , удовлетворяющая равенству является оптимальной стратегией игрока B, т.е. абсцисса наинизшей точки верхней огибающей определяет оптимальную стратегию , придерживаясь которой игрок В выбирает чистую стратегию с вероятностью , а чистую стратегию с вероятностью . Цена игры т.е. равна ординате минимальной точки верхней огибающей. Алгоритм геометрического нахождения оптимальных стратегий игрока В и цены игры V в игре mх2 1) Строим горизонтальный отрезок . 2) Из концов отрезка проводим два перпендикуляра. 3) На левом перпендикуляре от точки 0 откладываем, соблюдая масштаб, все элементы первого столбца матрицы игры. 4) На правом перпендикуляре от точки 1 откладываем, соблюдая масштаб, все элементы второго столбца матрицы игры. 5) Каждую пару точек, изображающих элементы и , стоящие в i-й строке матрицы игры соединяем отрезками . Таким образом, получим m отрезков, представляющих собой графики m линейных функций . 6) Если все отрезки неубывающие, то стратегия доминирует стратегию . 7) Если все отрезки невозрастающие, то стратегия доминирует стратегию . 8) Если отрезок , лежит не ниже отрезка , , то стратегия доминирует стратегию . 9) Находим верхнюю огибающую семейства отрезков. 10) На верхней огибающей находим минимальную точку или точки. 11) Абсцисса этой точки является вероятностью выбора игроком В чистой стратегии в оптимальной смешанной стратегии . 12) Ордината наивысшей точки нижней огибающей является ценой игры V. 13) Нижний из двух концов верхнй огибающей есть верхняя цена игры в чистых стратегиях 14) Верхний, из нижних концов отрезков , есть нижняя цена игры в чистых стратегиях 15) Элемент матрицы игры, изображающая точка которого является верхней на перпендикуляре, где она лежит и одновременно нижним концом одного из отрезков будет седловой точкой игры. Например, дана матрица игры 3 1 1 -4 4 -4 5 -6 -6 2 2 2 -3 -2 -3 5 4 Применим принцип минимакса , , . Строим чертеж: На чертеже 5 прямых линий, т.к. в матрице игры у игрока А 5 стратегий. Верхняя огибающая семейства прямых на чертеже выделена красным цветом. Минимальные точки верхней огибающей лежат на отрезке т.е. их много, края отрезка спроектированы на отрезок синими перпендикулярами, они определяют и V. Точка М1 лежит на пересечении прямых и соответственно для нахождения смешанной стратегии игрока В и цены игры V используем формулу , где за i возьмем 4 и 1. Получим два уравнения: Подставим значения: Смешанная стратегия игрока В - является крайней оптимальной стратегией, совпадает с чертежом, что важно! Аналогичным образом находим вторую крайнюю оптимальную стратегию как пересечение прямых и . Смешанная стратегия является второй крайней оптимальной стратегией. Цену игры V=2 нашли ранее. . Для игрока А найти оптимальную смешанную стратегию не возможно. В данной задаче множество минимальных точек на нижней огибающей, т.е. у игрока В множество оптимальных смешанных стратегий. Но может быть и одна!!! Решение игры методом Шепли-Сноу Теорема (Шепли-Сноу). Пусть и - оптимальные стратегии соответственно игроков А и В с платежной матрицей: ………….. …………. …………. …………. …………. …………. …………. …………. …………. И ценой игры V. Тогда найдутся натуральное число r, , номера строк и номера столбцов матрицы А такие, что оптимальная стратегия удовлетворяет системе уравнений , а крайняя оптимальная стратегия удовлетворяет системе уравнений . При этом, если , то матрица = ………….. …………. …………. …………. …………. …………. …………. …………. …………. системы и транспонированная матрица системы невырождены, т.е. их определители отличны от нуля. Для нахождения оптимальных стратегий игры методом Шепли-Сноу можно придерживаться следующего алгоритма. 1) В соответствии с принципом доминирования вычеркнуть строго доминируемые строки и столбы, это уменьшит размерность исходной матрицы. 2) В полученной матрице перебрать все ее квадратные подматрицы не ниже второго порядка и для каждой из них решить соответствующую систему линейных уравнений с неизвестными , а для транспонированной матрицы – систему линейных уравнений с неизвестными . 3) Полученные решения проверить на неотрицательность и на выполнение условий оптимальности: , . 4) Найденные решения систем являются оптимальными стратегиями. Игры с природой В антагонистических играх присутствовала неопределенность, состоящая в том, что ни один из игроков не обладал информацией о действиях противника. Однако, эта неопределенность компенсировалась тем, что каждый из игроков не будет действовать себе во вред, выбирая стратегии наиболее выгодные для себя и наименее выгодные для противника, таким образом каждый игрок стремился увеличить свой выигрыш (уменьшить свой проигрыш). В экономических задачах часто приходится принимать решение в условиях неопределенности не связанной с сознательным целенаправленным противодействием противника и заключающейся в недостаточной информированности лица, принимающего решение, об объективных условиях происходящего. Неопределенность такого вида может порождаться различными причинами: нестабильностью экономической ситуации, покупательским спросом на товар конкретного вида, меняющимся объемом перевозок, рыночной конъюнктурой, политикой правительства, надежностью партнера, выходом из строя технического оборудования, курсом валюты, уровнем инфляции, налоговой политикой, биржевой ситуацией, экологической обстановкой, стихийными бедствиями и т.д. Во всех задачах такого рода выбор решения зависит от объективной действительности, называемой в математической модели «природой». Сама математическая модель подобных ситуаций называется «играми с природой». Таким образом, в игре с природой осознанно действует только один игрок – лицо, принимающее решение игрок А. Природа, будем обозначать ее через П, является вторым неактивным игроком, так как она активно не противодействует игроку А, а принимает неопределенным образом то или иное состояние, не преследуя конкретной цели и безразлично к результату игры. Пусть игрок А имеет m возможных стратегий , а игрок П может находиться в одном из n возможных состояний , которые можно рассматривать как ее стратегии. Совокупность формируется либо на основе имеющегося опыта анализа состояний природы, либо в результате предположений и интуиции экспертов. Выигрыш игрока А при выбранной им стратегии при состоянии природы обозначим через . Составим матрицу игры игрока А: …… …… …… ……. …… …… …… …… …… Задача выбора игроком А чистой или смешанной стратегии в игре с природой осложняется наличием неопределенности, связанной с недостатком сведений о том или ином состоянии природы. При решении вопроса о выборе возможной стратегии в игре с природой игрок должен исходить из матрицы выигрышей. На выбор стратегии должны влиять не только выигрыши, составляющие матрицу игры, но и показатели «удачности» или «неудачности» выбора данной стратегии при данном состоянии природы и благоприятности этого состояния для увеличения выигрыша. Показателем благоприятности состояния природы П для увеличения выигрыша называется наибольший выигрыш при этом состоянии, т.е. наибольший элемент в j-м столбце матрицы игры: . Таким образом, благоприятность состояния природы рассматривается как фактор, благоприятствующий увеличению выигрыша игрока А при этом состоянии природы. В теории антагонистических матричных игр эта величина представляла собой показатель неэффективности стратегии игрока В. Для характеристики степени удачности применения игроком А стратегии при состоянии природы П используют понятие риска. Риском игрока А при выборе им стратегии при состоянии природы называется разность между показателем благоприятности состояния природы и выигрышем , т.е. выигрышем который игрок А получил бы, ели бы знал заранее, что природа примет состояние , и выигрышем, который он реально получит при этом же состоянии природы выбрав стратегию . Таким образом, . Риск игрока А при применении стратегии при состоянии природы есть упущенная возможность максимального выигрыша при этом состоянии природы. Из формулы следует, что риск всегда неотрицателен . Можно установить верхнюю границу рисков для каждого состояния природы , для этого рассмотрим величину , которая является наименьшим выигрышем игрока при состоянии природы . Тогда , разность называют колебанием выигрышей при состоянии природы . Если , то , т.е. стратегия при состоянии природы является безрисковой. Если , то риск является максимальным, а стратегия в этом случае наихудшая. Если , то все выигрыши в j-м столбце матрицы игры равны между собой и риск . Поэтому в этом случае любая стратегия игрока А при состоянии природы - безрисковая. Для матрицы игры можно составить матрицу рисков R, она имеет ту же размерность, что и матрица игры: …… …… …… ……. …… …… …… …… …… Пример: Построить матрицу рисков для матрицы: 9 4 5 1 3 4 8 3 1 4 7 4 8 2 9 8 5 8 3 Рассмотрим состояние природы : если бы игрок А знал, что состояние природы будет , то он выбрал бы стратегию приносящую максимальный выигрыш т.е , в этом случае выигрыш . Но игрок А не знает какое состояние примет природа поэтому выбирая стратегию А рискует получить не максимальный выигрыш 9, а только . Рассчитаем риски при состоянии природы : ; ; -колебания выигрыша. Аналогичным образом определим риски при остальных состояниях природы, получим матрицу рисков: 4 7 5 2 8 2 5 1 1 1 ; ; ; . Принятие решений в условиях неопределенности Рассмотрим игру с природой, пусть известна матрица игры …… …… …… ……. …… …… …… …… …… Игрок А имеет m возможных стратегий , а игрок П может находиться в одном из n возможных состояний , которые можно рассматривать как ее стратегии. Неизвестно какое именно состояние примет природа и отсутствует всякая возможность получения какой-либо информации о состояниях природы. Такая ситуация называется ситуацией полной неопределенности. Рассмотрим критерии поведения игрока А в условиях полной неопределенности. Критерий Вальда (критерий крайнего пессимизма) Рассматривая стратегию игрок А предполагает, что складывается самая плохая ситуация, т.е. ситуация, приносящая самый маленький выигрыш. Поэтому, рассматривая каждую стратегию игрок выбирает ситуации, приносящие минимальный выигрыш , затем из минимально возможных выигрышей выбирается максимальный т.е. находится . Стратегия игрока А соответствующая значению считается оптимальной по критерию Вальда. Например, 9 4 5 1 3 1 4 8 3 1 4 7 4 8 2 2 Значение соответствует стратегии , таким образом правило Вальда рекомендует использовать стратегию . Критерий Вальда является критерием крайнего пессимизма, т.к. ориентирует игрока А на наихудшее состояние природы и, следовательно, на крайне осторожное, осмотрительное поведение при выборе стратегий. Этот критерий уместен в тех случаях, когда игрок А не столько хочет выиграть, сколько хочет не проиграть. Максимаксный критерий (критерий крайнего оптимизма) Противоположностью критерию Вальда является максимаксный критерий. В этом случае рассматривая каждую свою стратегию игрок А предполагает, что складывается самая хорошая ситуация, т.е. ситуация, приносящая максимальный выигрыш , затем из максимально возможных выигрышей выбирается максимальный т.е. . Стратегия игрока А соответствующая значению считается оптимальной по критерию максимаксной стратегии. Например, 9 4 5 1 3 9 4 8 3 1 8 4 7 4 8 2 8 Значение соответствует стратегии , таким образом, максимаксный критерий рекомендует использовать стратегию . Максимаксный критерий является критерием крайнего оптимизма, так как ориентирует игрока А на наилучшее, благоприятнейшее для него состояние природы и, как следствие, на неоправданно легкомысленное поведение при выборе стратегий. Вместе с тем, в некоторых случаях этим критерием пользуются осознанно, например, когда перед игрокам А стоит дилемма: либо получить наибольший выигрыш, либо стать банкротом. Критерий Сэвиджа Критерий Сэвиджа так же относится к критериям крайнего пессимизма, но применяется к матрице рисков. Применяя критерий Сэвиджа игрок А при рассматривании стратегии предполагает, что складывается ситуация приносящая максимальный риск, таким образом сначала внутри каждой стратегии выбираются значения, приносящие максимальный риск , потом из всех максимально возможных рисков выбирается минимальный . Стратегия игрока А соответствующая значению считается оптимальной по критерию Сэвиджа. Например, Дана матрица игры 9 4 5 1 3 4 8 3 1 4 7 4 8 2 Построим матрицу рисков 4 7 7 5 2 8 2 8 5 1 1 1 5 Значение соответствует стратегии , таким образом, критерий Сэвиджа рекомендует использовать стратегию . Критерий Гурвица Критерий Гурвица является как бы промежуточным критерием между критерием крайнего оптимизма и критерием крайнего пессимизма. Критерий Гурвица рекомендует принимать решение соответствующее показателю эффективности . При из критерия Гурвица получаем критерий Вальда, при получаем максимаксный критерий. Критерий Гурвица позволяет взвешивать пессимистический и оптимистический подходы с показателем оптимизма . Например, дана матрица игры и 9 4 5 1 3 1 9 4 8 3 1 8 4 7 4 8 2 2 8 Значение соответствует стратегии и , таким образом, критерий Гурвица при рекомендует использовать стратегию или . Принятие решений в условиях риска Предположим, что в игре с природой имеется информация о возможности принятия природой того или иного состояния. Пусть - вероятность того, что природа примет состояние , такое предположение называется частичной неопределенностью. Матрица выигрышей в этом случае примет вид: …… …… …… ……. …… …… …… …… …… …… . В этом случае для принятия решения можно использовать следующие правила. Критерий Байеса относительно выигрышей Выигрыш, получаемый игроком А при принятии i-го решения является случайной величиной с рядом распределения: ……. ……. Математическое ожидание и есть средний ожидаемый выигрыш при принятии i-го решения. Правило Байеса относительно выигрышей рекомендует использовать стратегию, приносящую максимальный средний выигрыш т.е стратегия должна соответствовать значению . Например, пусть задана матрица игры: 4 6 7 1 3 5 2 3 12 1 3 2 5 8 4 10 0,3 0,2 0,4 0,1 , , , . соответствует стратегии . Правило Байеса относительно выигрышей рекомендует использовать стратегию . Критерий Байеса относительно рисков При использовании критерия Байеса относительно рисков используется матрица рисков. …… …… …… ……. …… …… …… …… …… ……. Риск, получаемый игроком А при принятии i-го решения является случайной величиной с рядом распределения: ……. ……. Математическое ожидание и есть средний ожидаемый риск при принятии i-го решения. Правило Байеса относительно рисков рекомендует использовать стратегию, приносящую минимальный средний риск т.е стратегия должна соответствовать значению . Например, пусть задана матрица игры: 4 6 7 1 3 5 2 3 12 1 3 2 5 8 4 10 0,3 0,2 0,4 0,1 Построим матрицу рисков 8 2 9 9 3 5 7 7 4 8 7 3 0,3 0,2 0,4 0,1 , , , . соответствует стратегии . Правило Байеса относительно рисков рекомендует использовать стратегию . Задачи оптимизации В некоторых случаях необходимо выбрать наилучшее решение из всех имеющихся решений, при этом все необходимые данные имеются. Такие задачи называются задачами оптимизации, они позволяют описать все множество имеющихся решений и выбрать из него наилучшее. Задача линейного программирования В общем случае задача линейного программирования записывается так, что ограничениями могут быть как уравнения, так и неравенства, а переменные могут быть как неотрицательными, так и произвольными. Если все ограничения являются уравнениями, а все переменные неотрицательны, то задачу линейного программирования называют канонической. Каноническая задача линейного программирования в координатной форме имеет вид . Каноническая задача линейного программирования в векторной форме имеет вид . Так как в большинстве методов решения задач линейного программирования предполагается, что система ограничений состоит из уравнений и естественных условий неотрицательности переменных, а при составлении математических моделей экономических задач ограничения формируются в основном в системы неравенств, необходимо выполнить переход от системы неравенств к системе уравнений. Это можно проделать следующим образом. К левой части неравенства прибавляют некоторую величину такую, чтобы неравенство превратилось в равенство , здесь . Переменная величина называется дополнительной переменной. Дополнительные переменные вводятся в целевую функцию с нулевыми коэффициентами и поэтому не влияют на ее значение. Если возникает необходимость перейти в задаче от нахождения минимума к нахождению максимума и наоборот, достаточно изменить знаки всех коэффициентов целевой функции на противоположные. Наиболее известными методами решения задачи линейного программирования является графический метод и симплекс-метод. Теоретической основой линейного программирования являются две теоремы: Теорема №1. Задача линейного программирования имеет оптимальное решение тогда и только тогда, когда целевая функция ограничена на допустимом множестве в направлении экстремума. Теорема №2. Если экстремум целевой функции в задаче линейного программирования достигается, то он достигается в некоторой угловой точке допустимого множества. Рассмотрим задачу линейного программирования: Решение: На плоскости двух переменных построим допустимое множество , ограниченное линиями А В D О С Прямая АВ задается уравнением , а прямая ВС уравнением . Допустимое множество является четырехугольником АВСО. По теореме №2 максимальное значение целевая функция достигает в одной из вершин четырехугольника: О(0,0), А(0,3), С(2,0). Координаты вершины В находим из системы уравнений: . Вычислим значение целевой функции в этих точках , , . Максимальное значение равно и достигается он при и . Однако чаще данную задачу решают следующим способом. Целевая функция при фиксированных значениях является уравнением прямой линии . Построим прямую , она пройдет через начало координат. Все остальные прямые будут параллельны данной прямой, они называются линиями уровня. Из курса аналитической геометрии известно, что коэффициенты при переменных в уравнении прямой являются координатами нормального вектора к этой прямой. Значит, нормальный вектор линий уровня в данном случае имеет координаты . Нормальный вектор показывает направление, в котором значения целевой функции возрастают. Поэтому в поисках максимума нужно двигать линию уровня в направлении нормального вектора. Для данного случая, последней точкой в которой линия уровня коснется области допустимых решений будет точка . Значит, максимум функции . Если в задаче нужно было найти минимум линейной функции, то линию уровня надо было двигать в сторону, противоположную направлению нормального вектора. Линия уровня, имеющая общие точки с областью допустимых решений и расположенная так, что область допустимых решений целиком находится по одну сторону от данной линии, называется опорной прямой. Из курса математического анализа следует, что если допустимое множество в задаче линейного программирования ограничено, то целевая функция имеет на нем и минимум и максимум. Если же допустимое множество неограниченно, то экстремума может и не быть, тогда задача линейного программирования не имеет решения. Транспортная задача Еще одной стандартной оптимизационной задачей наряду с задачей линейного программирования является транспортная задача. Однородный груз находится у m поставщиков в объемах , данный груз требуется доставить n потребителям в объемах , считаются известными - стоимости перевоза одной единицы груза от каждого i-го поставщика каждому j-му потребителю. Требуется составить такой план перевозок при котором запасы поставщика вывозятся полностью, запросы потребителя удовлетворяются полностью, общая стоимость перевозки грузов минимальна. Начальные условия транспортной задачи размещаются в таблице вида: ….. …… …… ….. ….. ….. ….. ….. …… Переменными транспортной задачи являются объемы перевозок от каждого i-го поставщика каждому j-му потребителю, будем обозначать их . Математическая модель транспортной задачи имеет вид: Для решения транспортной задачи составляем первоначальный опорный план. Рассмотрим конкретный пример: Проверим баланс поставщиков и потребителей, найдем суммы , , т.к. данная задача является задачей с правильным балансом. Находим клетку таблицы с минимальной стоимостью (маленькие цифры) это 1 и в нее загружаем перевозку с учетом ограничений по строке или столбцу. В клетке с 1 (желтая) необходимость в поставке единицы продукции, а на складе имеется единиц продукции, следовательно со склада привозим потребителю 4 единицы продукции. Запросы потребителя удовлетворены, следовательно, больше четвертый столбец не рассматриваем (я выделяю его желтым). Из оставшихся клеток вновь находим клетку с минимальной стоимостью. Клетка стоимостью 2 потребность 11 ед., на складе (т.к. 4 ед. уже увезли), загружаем 5 ед. и больше на складе товара нет, исключаем из рассмотрения 1 строку. Вновь выбираем наименьшую стоимость. Клетка стоимостью 3 потребность 7 ед., на складе , загружаем 7 ед. и больше потребителю не нужно, исключаем из рассмотрения 2 столбец. Вновь выбираем наименьшую стоимость. Клетка стоимостью 6 потребность 8 ед., на складе , загружаем 5 ед. и больше на складе товара нет, исключаем из рассмотрения 3 строку. Вновь выбираем наименьшую стоимость. Клетка стоимостью 8 потребность 6 ед.(5 ед. уже привезли), на складе , загружаем 6 ед. и больше потребителю не нужно, исключаем из рассмотрения 1 столбец. Последняя клетка стоимостью 9 потребность 3 ед. (5 ед. уже привезли), на складе , загружаем 3 ед. Таблица заполнена, получаем первоначальный опорный план. Проверим правильность составленного первоначального опорного плана для этого проверим все суммы больших цифр в строках и столбцах таблицы. Суммы по строкам и столбцам совпадают, первоначальный опорный план составлен верно. Найдем стоимость процесса для этого в клетках, где 2 цифры умножаем большую цифру (объем перевезенной продукции) на маленькую (стоимость перевозки одной единицы) и все складываем. у.е. Полученный первоначальный опорный план должен быть проверен на оптимальность (т.е. самый дешевый вариант перевозок найден или нет). Для проверки оптимальности используют метод потенциалов. Важно проверить, чтобы число заполненных клеток таблицы (где стоит большая цифра) равно m(число строк)+n(число столбцов)-1, если заполненных клеток меньше необходимо поставить 0 в одной из клеток (лучше, где стоимость поменьше). В нашем случае заполненных клеток 6 (они выделены голубым), а должно быть 3+4-1=6 тоже 6, дозаполнять таблицу не нужно. Потенциалы (числа) поставщиков и потребителей должны удовлетворять следующим соотношениям: Равенства (1) представляют собой систему уравнений для определения всех и . Одно неизвестное в системе задают самостоятельно, а остальные находят. Неравенства (2) служат для проверки оптимальности опорного плана, если хотя бы одно из неравенств не выполняется, опорный план не является оптимальным и его можно улучшить. Вернемся к задаче, каждая заполненная клетка имеет свое место (номер строки i и номер столбца j). Составим систему уравнений для заполненных клеток: (1,1) первая заполненная клетка 1 строка и 1 столбец, i=1, j=1, 2 –стоимость клетки. (1,4) , (2,1) , (2,2) , (2,3) , (3,3) Получаем систему из 6 уравнений, одну переменную задаем самостоятельно, например, , а остальные находим. , , , , , , , , Все потенциалы найдены. Проверим пустые клетки, проверим выполняются ли оптимизационные неравенства для пустых клеток. (1,2) , - выполняется, (1,3) , - выполняется, (2,4) , - нарушение оптимальности, (3,1) , - выполняется, (3,2) , - выполняется, (3,4) , - нарушение оптимальности. Обнаружено две клетки в которых нарушено условие оптимальности, следовательно, опорный план не является оптимальным и его можно улучшить. Для улучшения опорного плана строят цикл пересчета. Циклом пересчета в таблице условий транспортной задачи называется замкнутая ломаная линия (квадрат, прямоугольник) вершины которой находятся в клетках таблицы (одна клетка свободная, остальные занятые), а звенья параллельны строкам и столбцам таблицы. Вершинам цикла, начиная с вершины в свободной клетке поочередно присваивают знаки +, -, +, - и т.д. Из клеток со знаком – выбирается минимальная перевозка (большая цифра) и она перемещается по циклу. В результате получаем новый опорный план, который вновь должен быть проверен на оптимальность. +4 -4 -4 +4 Цикл изображен красной пунктирной линией, одна из вершин цикла в пустой «плохой» клетке (не выполняется условие оптимальности). В клетках со знаком – две большие перевозки 6 и 4. Минимальная из них 4, поэтому ко всем + и – подписываем по 4 единицы. Обязательно нужно проверить суммы по строкам и столбцам, они должны сохраняться. Только тогда преобразования правильны!!! Получили новый опорный план «улучшенный», считаем затраты у.е. Общая стоимость перевозок уменьшилась!!! Проверяем оптимальность: (1,1) (2,1) , (2,2) , (2,3) , (2,4) , (3,3) Получаем систему из 6 уравнений, одну переменную задаем самостоятельно, например, , а остальные находим. , , , , , , , , , , Все потенциалы найдены. Проверим пустые клетки, проверим, выполняются ли оптимизационные неравенства для пустых клеток. (1,2) , - выполняется, (1,3) , - выполняется, (1,4) , - выполняется, (3,1) , - выполняется, (3,2) , - выполняется, (3,4) , - выполняется. Полученный опорный план является оптимальным, минимальная стоимость перевозки грузов 120 у.е. Получить меньшую стоимость в данных условиях невозможно! Планирование эксперимента в играх с природой Предположим, что в игре с природой П игрок А имеет m стратегий , природа П может находиться в одном из своих n состояний с соответствующими вероятностями и задана матрица выигрышей игрока А …… …… …… ……. …… …… …… …… …… …… Будем рассматривать «идеальный» эксперимент, который характеризуется тем, что в результате его проведения мы получим точное знание того состояния природы , которое имеет место в данной ситуации. Пусть материальные затраты на проведение эксперимента равны с. Пусть , где - показатель эффективности стратегии по критерию Байеса относительно выигрышей представляющий собой взвешенно средний выигрыш с весовыми коэффициентами . Тогда это максимальный взвешенно средний выигрыш игрока А. Пусть , где - показатель благоприятности состояния природы , представляющий собой максимальный выигрыш при состоянии природы . Тогда - взвешенно среднее максимальных выигрышей . Теорема. Идеальный эксперимент целесообразно проводить при условии выполнения неравенства , т.е. когда затраты с на проведение эксперимента меньше разности между взвешенно средним максимальным выигрышем и максимальным взвешенно средним выигрышем , и не целесообразно проводить при справедливости неравенства . Данную теорему можно переформулировать в терминах рисков. Пусть , где , - риски игрока А при выборе им стратегии в условиях состояния природы . - показатель неэффективности стратегии по критерию Байеса относительно рисков, - минимальный взвешенно средний риск. Теорема. Целесообразность идеального эксперимента имеет место, если затраты с на его проведение меньше минимально взвешенно среднего риска : , и его не нужно проводить, если выполняется неравенство .