Теория игр. Оуэн (1971) (Теория игр. Оуэн (1971).djvu), страница 12

Предположим, что за первые Ь разыгрываний игрок ! использовал 1.ю стратегию Хг раз (1 1, ..., т), а игрок П использовал )сю стратегию У раз ь ь (1 = 1, ..., л). Тогда прн (Ь+ 1)-м разыгрыванин нгрок ! будет нсяользовать макю стратегию, а игрок П вЂ” свою )ь+гю стратегню, где ~~~ аг уа шах ~ амуа уь а+и Х ог, ! «г ш'и Х иВХг (гь ! ' «+3 1 г (Такнм образом, при каждом разыгрывании каждый игрон выбирает такую стратегию, которая является наилучшей по отношению к накопленным прошлым выборам противника,) Показать, что любая предельная точка пары последовательностей Хь/Ь, Уг/й есть решенне игры А. а) Будем говорнть, что !а-я строка является подходящей в интервале (й,й'), если существует такое Йь й б й, Я Ь', что ~ч" аг гу!' Вз,, ! Задачи и аналогично [э-й столбец является подходящим в интервале [й,й'), если существует такое йг, й Ы йз ~ й', что эт' аг Хг' Уь.

Тогда, если все строки являются подходящими для [й, !), то )г! — у! ~ 4а (й-!), где а = шах)аы[. б) Для любого в > О существует такое йэ, что (гь — Уь э йе для всех й 2 йэ. Доказательство вести индукпией по размерам матрицы. Если А есть (1 Х 1)-матрица, это очевидно. Предположим, что это верно для всех подмат. рнц А матрицы А. Выберем й" так, что )гь,— Уь ~ йег2 для всех А. Тогда йэ й Зайэ(е удовлетворяет нашему требованию. (Показатгч что если какая-либо строка или какой-либо столбец являются неподходящими для некоторого интервала, то их можно в этом интервале вычеркнуть н исследовать только осташ. щуюся подматрицу; рассмотреть интервалы вида (й,й+ й"), где й+ й* "Я йэ.) Глава 111 ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ Н1.

Е ВВЕДЕНИЕ максимизировать ~ с;х, ~=1 ~~'.~ а, х, = Ьп !'= 1, ..., а, х,~О, (3.1.!) (3.1.2) (3.1.3) при условиях или в матричных обозначениях: максимизировать хСт (3.1.4) (3.1.5) (3.1.6) хА ~ В, х ) О. при условиях Следует указать, что такая форма записи задачи линейного программирования не является наиболее общей. Действительно, может потребоваться не максимизировать целевую функцию, а минимизировать ее. Некоторые ограничения могут иметь форму равенств, а некоторые переменные принимать и отрицательные значения. Следует, однако, указать, что минимизация функции равносильна максимизации этой функции, взятой с противоположным знаком, равеяство можно заменить двумя противоположными неравенствами, а переменную, не имеющую ограничения на знак, можно выразить в виде разности двух неотрицательных переменных.

Поэтому, строго говоря, при рассмотрении задачи в виде (3.1.1) — (3.1.6) мы не теряем общности. Ш.1.1. О п р е д е л е н и е. Множество всех точек, удовлетворяющих ограничениям (3.1.2) и (3.!.3), мы будем называть допустимым множеством задачи (ЗА.!) — (3.1.3). Максимум выражения (3.1.1) называется значением задачи. Коротко говоря, задача линейного программирования есть задача максимизации (или минимизации) линейной функции (называемой целевой 4>ункцией) при наличии линейных ограничений. Обычно ограничения имеют вид нестрогих неравенств, а на переменные налагается условие неотрицательности. Таким образом, самая обычная форма задачи линейного программирования такова: найти (хь..., х, ) так, чтобы /Н, д двоаственнос/ь 59 Можно показать, что решение матричной игры можно свести к задаче линейного программирования.

Лействительно, если игрок 1 использует стратегию (хь ..., х ), он обеспечивает себе ожидаемый выигрыш не менее Х, где Х вЂ” любое число, такое, что ~~'„/ а!/х! ~: Я,, 1 = 1, ..., /!. ! 1 Поэтому задача нахождения оптимальной стратегии для игрока ! сводится к задаче линейного программирования: максимизировать /! (3.1,7) (3.1.8) ~, х! = 1, ! ! х,=.О, !=1,..., т, (3.1.9) (3.1.10) Аналогично задача для игрока П сводится к задаче линейного программирования: минимизировать // (3.! !1) (3.1.12) (3.1,13) (3.1.1 4) 111. 2. ДВОИСТВЕННОСТЬ хА~ В, при условиях при условиях при условиях — ~ч.", ацх, ч- Х ~ О, / 1, ..., п, ! ! при условиях — ~.'~~ ацу/+//='О, !=1, ..., т, / ! л Ху/=! / ! Рассмотрим две задачи линейного программирования: максимизировать хСт к ~ О минимизировать Вут уА/-:С, у а О.

(3.2.1) (3.2.2) (3.2.3) (3.2.4) (3.2.5) (3.2.6) Гл. В(. Линейное прогромиировоние Задача (3.2.4) — (3.2.6) называется двойственной к задаче (3.2.1) — (3.2.3). Кроме того, если изменить знаки у А, В и С, то (3.2.4) — (3.2.6) можно переписать как задачу максимизации: максимизировать у (- В) (3.2.7) у(- Ат) ~ — С, у .=. О. (3.2.8) (3.2.9) при условиях Двойственной задачей для (3.2.7) — (3.2.9), как определено выше, должна быть задача; минимизировать — Схт (3.2.10) х( — А) = — В, х ) О.

(3.2.1 1) (3.2. 12) при условиях Но очевидно, что (3.2,10) — (3.2.12) эквивалентно (3.2.1)— (3,2,3). Следовательно, можно утверждать, что двойственной задачей для (3.2.4) — (3.2.6) является задача (3.2.1) — (3.2.3). Поэтому двойственность является взаимно обратным отношением: две задачи (3.2.1) — (3.2.3) и (3.2.4) — (3.2.6) двойственны одна другой. Следующие далее теоремы уточняют это соотношение между двойственными задачами линейного программирования. П1.2.1. Теорема.

Пусть х и у принадлежат допустимым множествам задач (3.2.1) — (3.2.3) и (3.2.4) — (3.2.6) соответственно. Тогда ХСТ ( Вут. До к аз а тельство. Мы имеем хСт = ~~ хгс, ~ ~ х, (~'.~~ аиУ() = (по (3.2.3) и (3.2.5) ) г-! г-1 ~ г и ( т л = .Е~ ( ~ хгаг(/У( ( ~ч.', о(У( = ВУт г=~ г-1 (по (3.2.2) и (3.2.6)). !П.2.2. Следствие. Предположим, что векторы х* и у' принадлежат допустимым множествам задач (3.2.1) — (3,2,3) и (3.2.4) — (3.2.6) соответственно и что х*Ст = Ву*т. Тогда х' и у' являются решениями этих двух задач. Задача линейного программирования в общем случае не обязательно имеет решение. Это может произойти по следующим двум причинам. С одной стороны, если система ограничений окажется несовместной, то допустимое множество пусто.

В этом случае задача называется недопустимой. С другой стороны, может случиться, В1. 2. Двойственность в! что искомый максимум (илн минимум) не существует, даже если задача допустима, так как целевая функция может принимать на допустимом множестве произвольно большие (или малые в случае задачи минимизации) значения.

Например, задача максимизировать 2х — х~1, х= О, при условиях не имеет решения,так как целевая функция может принимать произвольно большие значения. Такая задача называется неограниченной. Укажем еше одно следствие из теоремы П1.2.1. П1. 2.3. С л е д с т в и е. Если задача линейного программирования (3.2.1) — (3.2.3) неограниченна, то двойственная задача (3.2.4)— (3.2.6) недопустима. Аналогично, если задача (3.2.4) — (3.2.6) неограниченна, то (3.2.1) — (3.2,3) недопустима. Доказательство.

Предположим, что задача (3.2.4)— (3.2.6) допустима, т. е. у принадлежит допустимому множеству для (3.2.4) — (3.2.6).Тогда целевая функцияхСтограничена сверху величиной Вут. Следовательно, задача (3.2.1) — (3.2.3) не будет неограниченной. Обращение следствия П1.2.3 не имеет места. Иначе говоря, если задача недопустима, то отсюда не следует, что двойственная ей задача неограниченна. Может оказаться, что обе задачи недопустимы. 1!!.2.4.

Пример. Двойственные задачи: максимизировать 5хь + хз х~ — хе~ 1, — х, + хг ~ — 2, хо хзИО, при условиях минимизировать уь — 2уг У~ Уз ~ бь — у,+уз~1, „„„,~О при условиях обе являются недопустимыми. Таким образом, если задача недопустима, то двойственная ей задача может быть неограниченной или недопустимой. Мы покажем сейчас, что других воэможностей нет. Гл. !П. Линейное орограммироеоиие ШИ2. Теорема. Пусть задача (32,!) — (323) допустима, а двойственная задача (3.2.4) — (3,2.6) недопустима.

Тогда задача (3.2.1) — (3.2.3) неограниченна, Д о к а з а т е л ь с т в о. Пусть задача (3.2.4) — (3.2.6) недопустима. Рассмотрим игру с (и! Х (и +1))-матрицей ( — А! Ст) полученной добавлением вектора-столбца Ст к матрице — А. Предположим, что значение этой игры отрицательно. Тогда, если з = = (з„..., з„, з„+,) — оптимальная стратегия игрока И, то о — ~~.", а!!з!+с!э„.„<0, !=1, ..., и!. ! ! Если зо+! = О, то ~~~~ а,!з!)О, !=1, ..., т, так что для достаточно больших /г ;Рга,!(йз!))сг, !=1, ..., т, ! ! йз, ) О, т.

е, вектор йз удовлетворяет (3.2.5) и (3.2.6), так что задача (3.2.4) — (3.2.6) допустима. Если же з„+, ) О, то положим у! = = з;/з„+!., тогда у удовлетворяет (3.2.5) и (3.2.6). Таким образом, значение этой игры должно быть нулевь!м или положительным. Предположим теперь, что значение этой игры равно нулю; предположим также, что игрок И имеет оптимальную стратегию з, в которой з„+, ) О. Если положить у! = зз/з„+!, то снова окажется, что у удовлетворяет (3.2.5) и (3.2.6), а это противоречит предпо- ложению о недопустимости задачи (3.2.4) — (3.2.6).