Задачи целочисленного программирования. Метод Гомори. 2 страница

Некоторые авторы считают отнюдь не бесспорным и принципиальное, лежащее в основе теории игр предположение о так называемом “общем знании”. Оно гласит: игра со всеми правилами известна игрокам и каждый из них знает, что все игроки осведомлены о том, что известно остальным партнерам по игре. И такое положение, естественно, сохраняется на все время игры.

Но чтобы предприятие в конкретном случае приняло предпочтительное для себя решение, данное условие требуется далеко не всегда. Для этого могут оказаться достаточными менее жесткие предпосылки, например “взаимное знание” или “рационализируемые стратегии”. Однако эти термины говорят только лишь о вероятностном характере восприятия «общего знания».

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

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

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

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

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

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

Игра - упрощенная формализованная модель реальной конфликтной ситуации. Математически формализация означает, что выработаны определенные правила действия сторон в процессе игры:

варианты действия сторон;

исход игры при данном варианте действия;

объем информации каждой стороны о поведении все других сторон.

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

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

Платежная матрица (матрица эффективности, матрица игры) включает все значения выигрышей (в конечной игре). Пусть игрок 1 имеет т стратегий А_i,а игрок 2 – n стратегий B_j . Игра может быть названа игрой т ´ n. Представим матрицу эффективности игры двух лиц с нулевой суммой, сопроводив ее необходимыми обозначениями (табл.).

Таблица 3.

Игрок 2 Игрок 1	В1	В2	…	Вn	ai
А1	а11	а12	…	а1n	a1
А2	a21	a22	…	а2n	a2
…	…	…	…	…	…
Аm	аm1	аm2	…	аmn	am
bj	b1	b2	…	bn

В данной матрице элементы а_ij - значения выигрышей игрока 1 - могут означать математическое ожидание выигрыша (среднее зна­чение), если выигрыш является случайной величиной. Величины a_i, и b_j, – соответственно минимальные значения элементов а_ij по строкам и максимальные - по столбцам. Их содержательный смысл будет отражен ниже.

В теории игр не существует установившейся классификации видов игр. Однако по определенным критериям некоторые виды можно выделить.

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

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

Взаимоотношения сторон. Согласно данному критерию игры делятся на кооперативные, коалиционные и бескоалиционные. Если игроки не имеют права вступать в соглашения, образовывать коалиции, то такая игра относится к бескоалиционным; если игроки могут вступать в соглашения, создавать коалиции - коалиционной. Кооперативная игра - это игра, в которой заранее определены коалиции.

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

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

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

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

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

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

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

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

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

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

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

Рассмотрим матричную игру, представленную матрицей выигрышей m´n, где число строк i, = а число столбцов j = . Применим принцип получения максимального гарантированного результата при наихудших условиях. Игрок 1 стремится принять такую стратегию, которая должна обеспечить максимальный проигрыш игрока 2. Соответственно игрок 2 стремится принять стратегию, обеспечивающую минимальный выигрыш игрока 1. Рассмотрим оба этих подхода.

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

a._i = . (19)

Чтобы этот гарантированный эффект в наихудших условиях был максимальным, нужно из всех a._i, выбрать наибольшее значение. Обозначим его a и назовем чистой нижней ценой игры (максимин):

a. = (20)

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

Подход игрока 2. Своими оптимальными стратегиями он стремится уменьшить выигрыш игрока 1, поэтому при каждой j -й чистой стратегии он отыскивает величину своего максимального проигрыша

Рисунок 38.

в каждом j -м столбце, т.е. определяет максимальный выигрыш игро­ка 1, если игрок 2 применит j -ю чистую стратегию. Из всех своих п. 7-х чистых стратегий он отыскивает такую, при которой игрок 1 получит минимальный выигрыш, т.е. определяет чистую верхнюю цену игры (минимакс):

Рисунок 39.

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

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

2.3.9. Стратегии теории игр

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

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

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

• игра без седловой точки;

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

• игра многократно повторяется в сходных условиях;

• при каждом из ходов ни один игрок не информирован о выборе стратегии другим игроком;

• допускается осреднение результатов игр.

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

Для игрока 1 смешанная стратегия, заключающаяся в применении чистых стратегий А₁, А₂, ..., А_т с соответствующими вероятностями р₁, р_2, ..., р_т.

Рисунок 40.

где . (21)

Для игрока 2

Рисунок 40

где . (22)

q_j — вероятность применения чистой стратегии B_j.

В случае, когда р_i = 1, для игрока 1 имеем чистую стратегию

Рисунок 41.

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

Рисунок 42.

где и – векторы;

p_i и q_i – компоненты векторов.

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

(23)

Игрок 2 добивается того, чтобы выполнялось условие

(24)

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

(25)

Цена игры - средний выигрыш игрока 1 при использовании обо­ими игроками смешанных стратегий. Следовательно, решением матричной игры является:

1) – оптимальная смешанная стратегия игрока 1;

2) – оптимальная смешанная стратегия игрока 2;

3) g – цена игры.

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

(26)

Существует основная теорема математических игр.

Для матричной игры с любой матрицей А величины

и (27)

существуют и равны между собой: a = b = g.

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

Решить игру - означает найти три цены игры и оптимальные страте­гии. Рассмотрение методов нахождения оптимальных смешанных стратегий для матричных игр начнем с простейшей игры, описываемой матрицей 2´2. Игры с седловой точкой специально рассматриваться не будут. Если получена седловая точка, то это означает, что имеются невыгодные стратегии, от которых следует отказываться. При отсутствии седловой точки можно получить две оптимальные смешанные стратегии. Как уже отмечалось, эти смешанные стратегии записываются так:

Рисунок 43

Значит, имеется платежная матрица

Рисунок 44.

При этом

a₁₁p₁ + a₂₁p₂ = g;

a₁₂p₁ + a₂₂p₂ = g;

p₁ + p₂ = 1.

a₁₁p₁ + a₂₁(1 – p₁) = a₁₂p₁ + a₂₂(1 – p₁);

a₁₁p₁ + a₂₁ – a₂₁p₁ = a₁₂p₁ + a₂₂ – a₂₂p₁,

Рисунок 46.

откуда получаем оптимальные значения и :

(28)

(29)

Зная и , находим g:

(30)

Вычислив g, находим и :

a₁₁q₁ + a₁₂q₂ = g; q₁ + q₂ = 1; (31)

a₁₁q₁ + a₁₂ (1 – q₁) = g. (32)

при a₁₁ ¹ a₁₂. (33)

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

1. По оси абсцисс откладывается отрезок единичной длины.

2. По оси ординат откладываются выигрыши при стратегии А₁.

3. На линии, параллельной оси ординат, в точке 1 откладываются выигрыши при стратегии a₂.

4. Концы отрезков обозначаются для a₁₁-b₁₁, a₁₂-b₂₁, a₂₂-b₂₂ , a₂₁-b₁₂ и проводятся две прямые линии b₁₁b₁₂ и b₂₁b₂₂.

5. Определяется ордината точки пересечения с. Она равна g. Абсцисса точки с равна р₂ (р₁ = 1 – р₂).

Рис. 48. Оптимальная смешанная стратегия

Данный метод имеет достаточно широкую область применения. Это основано на общем свойстве игр т´п., состоящем в том, что в любой игре т´п. каждый игрок имеет оптимальную смешанную стратегию, в которой число чистых стратегий не больше, чем min(m, n). Из этого свойства можно получить известное следствие: в любой игре 2´п. и т´2 каждая оптимальная стратегия и содержит не более двух активных стратегий. Значит, любая игра 2´п. и т´2 может быть сведена к игре 2´2. Следовательно, игры 2´п. и т´2 можно решить графически. Если матрица конечной игры имеет раз­мерность т´п., где т > 2 и п. > 2, то для определения оптимальных смешанных стратегий используется линейное программирование.

Мажорирование (доминирование) стратегий

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

Рисунок 49.

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

Рисунок 50.

С позиции игрока 1 его первая стратегия оказывается хуже второй, так как по первой стратегии он только проигрывает. Поэтому первую стратегию можно исключить, а матрицу игры преобразовать к виду: (0 0,5).

Учитывая интересы игрока 2, следует оставить только его первую стратегию, поскольку, выбирая вторую стратегию, игрок 2 оказывается в проигрыше (0,5 - выигрыш игрока 1), и матрица игры принимает простейший вид: (0), то есть имеется седловая точка.

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

В качестве иллюстрации к сказанному рассмотрим матрицу игры:

Рисунок 51.

Для первых двух чистых стратегий игрока 1 возьмем частоты их применения (вероятности) равными 0,25 и 0,75.

Третья стратегия игрока 1 мажорируется линейной выпуклой комбинацией первой и второй чистых стратегий, взятых с частотами 0,25 и 0,75 соответственно, т.е. смешанной стратегией:

24 × 0,25 + 0 × 0,75 = 6 > 4;

0 × 0,25 + 8 × 0,75 = 6 > 5.

Поэтому третью стратегию игрока 1 можно исключить, используя вместо нее указанную выше смешанную стратегию.

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

Рисунок 52.

третья стратегия игрока 2 мажорируется смешанной стратегией из первой и второй его чистых стратегий, взятых с частотами 0,5 и 0,5:

10 × 0,5 + 0×0,5 = 5 < 6;

0 × 0,5 + 10 × 0,5 = 5 < 7.

Рисунок 53.

Таким образом, исходная матрица игры эквивалентна матрице следующего вида:

Рисунок 54.

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

2.4. Теория статистических решений (Игры с природой)

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

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

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

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