Беклемишев - Дополнительные главы линейной алгебры (947281), страница 72
Текст из файла (страница 72)
Стратегия х удовлетворяет системе неравенств с ~, 'ассхс~п, )=1, ..., л, с=! х'+...+х"=1, (9) При этом первый игрок стремится так выбрать х, чтобы о было максимальным. Для того чтобы свести эту задачу к задаче линей- ного программирования, потребуется преобразование матрицы А, Именно, прибавим ко всем элементам А одно и то же число, на- столько большое, чтобы все элементы стали положительными, Это равносильно тому, что первый игрок получает определенную сумму ва участие в игре.
Поэтому преобразование ие влияет на выбор стратегии каждым игроком. Итак, положим асс — — ау+ а и А = )) Юсс )), где а ) шах ) асс ). Величина о, составленная для матс,с рицы А, положительна, и мы можем ввести новые переменные в!=о-схс, 1=1, ..., си. Это приведет систему неравенств (9) для матрицы А к виду 'Я дсЯс ~- 1, с 1. .. „ л, с $1+ +$!!! о 1 3' рв О„ ..., $ ~ О, 324 ГЛ, М СИСТЕМЫ НЕРАВЕНСТВ И ЛИНЕИНОЕ ПРОГРАММИРОВАНИЕ Теперь стремление увеличить и приводит к следующей задаче ли- нейного программирования: 'Я пса ==: 1, 1 = 1, ..., а, с с сс р: О, с = 1, ..., пс, ас+...+$" — ипи'и. Мы сможем запасать эту задачу в матричной форме, если введем столбец с, все элементы которого равны 1. Нам потребуются также столбцы высоты лс и и, но высоту мы указывать не будем, так как она ясна из употребления столбца.
Задача первого игрока принимает внд Агф)У, В="О, с'Г$- ии'и. (10) Эта задача разрешима. Действительно, целевая функция ограничена снизу, так как очевидно, что о = шах хглу. Система ограничений и у задачи (10) совместна, потомУ что все аи ) О, и, выбРав $с ~ гпах ас), с мы сделаем в каждом неравенстве одно из слагаемых большим единицы. Построим теперь задачу второго игрока. Если второй игрок выберет стратегию у, то его проигрыш будет не больше чем пс = = шах ~ а; ус.
При этом с йссрс =.нс, с=! с+ +уи д О, ..., д О. 1=1, ..., Вс, Преобразования, аналогичные примененным в задаче первого игрока, приводят задачу минимизации максимального проигрыша к виду )ГАГ(с', Ч~о. Чтс'-э- спал (11) „Гс. т ГАтй сгз (12) Перейдем к старым переменным х и у, учитывая, что в, и т)а где Ч = пг'у.
Нетрудно заметить, что задачи первого и второго игроков— взаимно двойственная пара задач. Из теоремы 3 5 3 и формулы (9) $3 следует, что для решений $, и 41, задач (10) и (11) выполнены ра- венства о $. ПРИЛОЖЕНИЯ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ соответствуют во= щ!П.У', ассхо 1 1 нсо=гпах ~, аууо. чо- 1 с Умножая (12) почленно на ооисо, получаем гп! П,т', а. х ' = утА тх, = гпах ~Ч ', а.
ус. 1 1 Теперь мы можем вернуться к исходной матрипе А. Имеем ппп ~ч"„(ас1+ сс) х,' = гп!п ~ ассхс+ а.У', х' = ппп ~; асгтос+ а гпах,У' ,(ау+а) ус = щах ~ анус+а, ч о с с! о а также Х (ау+ а) х,'у,'= Х анхосуос+ а Х хХ=.т,' асгх уо+а 1. 1 Позтому ппп ~„'анхс=утдтх,=щах )~ ~а, у1, Отсюда немедленно следует щ1путДтх утдтх щзхутДтх о о о о г к (13) Действительно, в двойном неравенстве щсп ) а хс щгпу А,с -у Атхо знр щгп хтАу = !и! щах хтДу хтДу Х о .о Отсюда следует не только равенство верхней и нижней граней но и то, что зти грани достижимы. Мы можем сформулировать результат так: Т е о р е и а 2. Для произвольной матричной игры существуют спакие смешанные стратегии х, и у„при которых гпах пнп хтАу = ппп гпах хтАу = хтАу,.
х о Р Ф крайние члены равны. Отсюда следует первое из доказываемых равенств, а второе доказывается аналогично. Теперь из неравенства (8) и равенств (13) таким же приемом получаем ГЛ. К СИСТЕМЫ НЕРАВЕНСТВ И ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ Число хГАу, называется значением игры, а стратегии л, и у,— оптимальными стратегиями.
Пара оптимальных стратегий хА. УА носит название решения игры. Чистые оптимальные стратегии, которые существуют для вполне определенной игры, являются оптимальными в этом смысле. Можно сказать, что игра является вполне определенной, если значение игры равно одному из элементов матрицы. Равенства (13) показывают, что, выбрав свою оптимальную стратегию х„первый игрок обеспечивает себе выигрыш, равный значению игры. Больше этого он получить не сможет, если только второй игрок также выберет свою оптимальную стратегию.
Если один из игроков выберет оптимальную стратегию, то второй, уклоняясь от оптимальной стратегии, может только ухудшить свой выигрыш. Оптимальные стратегии игроков не единственны, но все, сказанное выше, относится к любой паре оптимальных стратегий, так как ка;дая из них получается из какого-нибудь решения соответств) ющей задачи линейного программирования, а равенство (12) нз котгрого следует (13), имеет место для любых двух решений пары сопряженных задач. Совокупно=ть оптимальных стратегий, например, первого игрока образует выпуклое подмножество в множестве его смешанных стратегий, и ка ндая из оптимальных стратегий — выпуклая комбинация некоторых, но, возмохгно, не всех чистых стратегий.
В разные оптимальные стратегии могут входить разные выборы чистых стратегий. Впрочем, возможно, что и одна и та же смешанная стратегия раскладывается в выпуклую комбинацию двух различных наборов чистых стратегий. Надо помнить, что значение игры — это математическое ожидание выигрыша первого игрока.
В любом случае может быть реализована только конечная последовательность повторений .игры. Пусть игроками приняты их оптимальные стратегии ~х,', ..., х, ~~ и ~ у,', ..., у," ~ и при каждом повторении игры 1-я и 1'-я чистые стратегии выбираются с вероятностями х,' и п( соответственно. Тогда средний выигрыш первого игрока при увеличении числа повторений стремится к значению игры. Все рассуждения о свойствах оптимальных стратегий следует понимать только в таком смысле. Можно ли извлечь пользу из смешанных стратегий, если реализуется небольшое число повторений, или просто игра играется один раз? Ответ на этот вопрос, так же как и подробное изложение теории матричных игр, можно найти в книге Льюса и Райфы 120). В заключение хотелось бы сделать замечание о логической связи некоторых теорем этой главы.
Одной из основных теорем является теорема Фаркаша о неравенствах — следствиях системы $ К ПРИЛОЖЕНИЯ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ зят линейных неравенств. Теорема двойственности в линейном программировании, по существу, прямо из нее вытекает, так как при доказательстве теоремы двойственности, кроме теоремы Фаркаша, используется только принцип Дедекинда непрерывности множества вещественных чисел. В свою очередь теорема о максимальном потоке и основная теорема теории матричных игр получены прямым применением теоремы двойственности.
Доказательство предложения 15 5 1, играющего роль леммы при доказательстве теоремы Фаркаша, довольно тяжелое. Но как мы видим, усилия, на него затраченные, приводят к замечательным результатам, лов а В ли н и и ВЫЧИСЛЕНИЕ КОВЕЭИЦИЕНТОВ ХАРАКТЕРИСТИЧЕСКОГО МНОГОЧЛЕНА Рассмотрим квадратную матрицу А порядка п. Ее характеристический многочлен мы запишем в виде бе((А ХВ) ( 1)п(У+ат)л — 1+ +ал) и найдем числа а„..., а„, только множителем ( — 1)" отличающиеся от коэффйцнентов характеристического многочлена. Пусть )ч, ..., 1< — характеристические числа матрицы А, причем каждое нз них повторено столько раз, какова его кратность. Вещественности характеристических чисел не требуется. Введем обозначение для суммы степеней характеристических чисел. Предложение 1. Коэффициенты им ..., и„удовлетворяют соотношениям — Йх~ — — о„+а,о~,+...+измом А=1, ..., л.
(2) Для доказательства воспользуемся выражением коэффициентов многочлена через его корни а„=( — 1)а ~, Х, ...ц„. (3) С1«- Са Формулы (3), называемые формулами Виета, легко ' получить, если записать многочлен в виде произведения (Х вЂ” Хт)... (Х вЂ” Х,) и раскрыть скобки. НайДем пРоизвеДение аэоэ э пРи пРоизвольном 1. СогЛасно равенствам (1) и (3) ( — 1)» 'а,я~ г — — (,У, 'М) ~ .У,' )и,...)< ), ы ь /\к,«...ю Перемножая суммы почленио, мы можем записать произведение в виде Лэ+Мг, где Л/ Х Л()ч,.")и +" + Х )<," Лг и (4) !<ь«...1а г 4~<- <1~ г<~ довхвленнв — сумма тех членов, которые получаются при 1, отличном от лд, ..., !» !, а М! = ,У', Л',,+ ' ... Л!„ , + .. -1- „5', Л!, " Л! + ! (5) ! <...(!» сдс...<!» ~ — сумлда членов, получающихся при 1, равном одному из !„..., 1» г.
Как нетрудно заметить, Мг — — Л»„. Поэтому, складывая произведения о»а„» мы сможем привести подобные члены: ! — ! »-! оуа» д= ~~ ( — 1)» !(Лг+Мг)=( — 1)» »Лд — М» д. (6) 1=! л=! При 1=1 все суммы в равенстве (4) совпадают, и мы имеем Л,=( — 1)»йа». Прн 1'=й — 1 в формулах (5) остается только одна сумма, и в ней в каждом слагаемом только один множитель Л1,. Итак, М„=о». Теперь в силу (6) мы имеем »-! Х о;а, != — /га„— о„, что совпадает с доказываемым равенством.
Пока мы не использовали того, что рассматриваемый много- член — характеристический многочлен некоторой матрицы. Это обстоятельство можно использовать для нахождения сумм (1). Действительно, согласно предложению 9 $ 4 гл. П характеристические числа матрицы А равны Л»„..., Л».
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
