Теория игр. Оуэн (1971) (1186151), страница 16
Текст из файла (страница 16)
В каждой из них (а их только конечное число) возмущение увеличит (или уменьшит) целевую функцию на некоторое кратное числа е. Предположим теперь, что решение задачи достигается в крайней точке Рь Существует такое положительное число т(, что если Ре — любая другая крайняя точка (не являющаяся решением задачи), то ш(Ре) ~ ~ ш(Р~) — е) (где ш(Р) — значение целевой функции в точке Р), Ясно, что если все е достаточно малы, то целевая функция не может увеличиться более чем на т) ни в какой крайней точке. Отсюда следует, что Ре не может быть решением модифицированной задачи, так как она не была решением исходной задачи, Следовательно, решение модифицированной задачи всегда дает решение исходной задачи.
Вообще говоря, решение задачи методом возмущения, хотя он и полезен (главным образом для доказательства конечности симплекс-алгорифма),— дело достаточно утомительное, особенно из-за того, что никогда ие известно, сколь малыми должны быть зти е, чтобы гарантировать, что решение модифицированной задачи будет давать решение исходной задачи. При проведении вычислений оказывается легче поручать вычислительной машине действовать случайным образом, когда нужно выбирать один из нескольких возможных ведущих элементов.
Это гарантирует с вероятностью единица, что зацикливания, которое усложняет алгорифм в подобных случаях, не произойдет (поскольку в действительности такое зацикливание происходит только тогда, когда существует систематический метод выбора ведущего элемента). П1.6. ПРИМКРЫ Теперь рассмотрим несколько примеров решения задач линейного программирования симплекс-методом. 1П.6.1.
П р и м е р. Максимизировать бхг + 2хе+ хз 1П.е, Примеры 77 при условиях Строим таблицу: 6 2 1 О Так как все столбцы имеют положительные элементы в нижней строке, в качестве ведущего можно выбрать любой столбец. Можно, например, выбрать первый столбец: тогда ведущим будет отмеченный звездочкой элемент. Совершая ведущее преобразование, мы получаем таблицу из хз хз 1 /з — 4 (3.6.2) 7/ /з /з 1 Снова используя отмеченный элемент в качестве ведущего, получаем из хз из 1 2З/ — 4 (3.6.3) -7/з з/ 2/ 47/ Очевидно, что здесь мы получили решение: ('/з, 0,4). Для этого набора переменных значение нз равно 4'/з. х, + Зхз — хз «6, хз+ хз «4, Зх~+ хз «7, х„х„хз ~ О.
1 3 — 1 О 1 1 3' ! О /з /з О 1 1' '/, '/, О /з /з О 1 1 /з /з — и„ вЂ” и„ вЂ” из — и„ вЂ” и„ вЂ” Хо — мо хз~ — х1р Гл, Пп Линейное орограммировоние 78 П1.62. Пример. Минимизировать бд! + 4дз + удз при условиях д, + Здз~5, Зд,+д,+ Уз~2, У!+Уз ~ 1 У! Уь Уз = О. и, 1 1/ 11/ О 1 1 /з /з О 23/ — 4 = — иь хз~ = — х„ (3.6.4) 7/ 3/ 2/ 47/ ! - ! уз п2 11 !1 У2 Следовательно, решением задачи П1.6.2 будет (О, 1, '/3). Значение атой задачи то же, что и задачи П1.6.1, т.
е. и/3. П!.6.3. Пример. Решить матричную игру 5 2 4 2 Р е ш е н и е. Запишем задачу максимизации в форме: максимизировать Х Зх1+ бхз+ хз ~ Х, бх,+2хз+4хз~Л, при условиях х! + 4хз+ Зхз ~ ~» 4х, + 2хз+ 5хз ~ Х, х1 + х2+ хз х! ~ хм хз мь О. Легко видеть, что эта задача является двойственной для задачи 1П.6.1. Если записать таблицу (3.6.1) так, чтобы она включала обе задачи, и действовать, как выше, то последняя таблица будет иметь вид П1.6, Примеры Это дает таблицу Х! Х2 ХЗ вЂ” 3 — 5 — 1 — 6 — 2 — 4 — 1 — 4 — 3 -4 -2 -5 — 1 — 1 — 1 (3.6.5) — и„ вЂ” 1 Здесь нужно прежде всего совершить такое ведущее преобразование, чтобы перевести Х в число базисных переменных, а 1 в число небазисных.
К сожалению, элемент, расположенный ниже Х в строке, содержащей 1, равен нулю; поэтому придется сделать не одно, а два ведущих преобразования. В следующих далее таблицах для обозначения ведущих элементов на каждом шаге используются звездочки: Х4 Хз Хз из 1 — 3 4 — 1 -2 О 1 3 — 2 2 — 4 -2 — 5 — 1 — 1 — 1' (3.6.6) х, х, 1 — 3 -7 4 — 1 — 1 1 — 1 — Из, — из* (3.6.7) — 1 1 Π— х. з Теперь переставим строки и столбцы так, чтобы правый столбец отвечал свободному члену, а нижняя строка — целевой функции )з. — 3 1 ! 1 — 4 2 3 -5 1 — 1 ! 1 1 ! ° Π— 1 ! О и!» — и,, — и„ вЂ” и„ вЂ” и 2» из — )4» — 1, 1"е.
П/. Линейное ирогроммировоние 80 Изменив также знаки в нижней строке, мы получим таблицу х, хз и4 1 -3 — 7 — 1 — 3 — 1 — 1 (3,6.6) 1 — 4 — 1" 1 1 Π†! — 3 — 1 Далее действуем по правилам (3.5.1), пока не получим базисную допустимую точку: х, хз из 1 (3.6.9) — 2 1 и1 1 (3.6.10) 2 4 — 1 п1 1 (3.6.11) =Л, — 4 3 — 1 4 1 1 4 3 О 6' 3 7 1 1 Теперь, имея базисную правилам (3.5.2): Х! Пз — и 1> — и„ вЂ” й з> — х з> — ро П2 = — ми = — х„ Пе — мо хз> допустимую точку, мы действуем по пз> -"' хм р4 з> х> 111.
б Примеры 81 ПЗ "2 П1 /4 /8 /8 0 '/, /4 /24 /24 1/4 1/м 2/24 /8 /2 1/ з/ = — Х„ О1 = — Хз, (3.6.1 2) /2 /12 /12 13/ !! !! !! !! Уз Уз У1 !з Таблица (3.6.12) дает решение: оптимальная стратегия игрока1 есть (1/8, '/м з/8). Двойственные переменные, которые были опущены в промежуточных таблицах, указывают, что оптимальная стратегия игрока 11 есть ('/12, з/12, '/2, О). Значение игры равно 'з/ь В связи с этим примером можно сделать несколько замечаний. Первое состоит в том, что при проведении ведущего преобразования в таблице (3.6.8) поменялись местами две переменные из и из. Но следующий шаг меняет местами из и из.
Мы могли бы сэкономить шаг, сразу поменяв местами из и и1, и тем самым перейти от таблицы (3.6.8) к (3.6.10) за один шаг. Таким образом, мы видим, что правила (3,5.1) не всегда дают результаты самым быстрым способом; можно сделать видоизменения, которые значительно сократят число необходимых операций (а следовательно, и время), Второе замечание следующее. Таблица (3.6.8) не дает базисной допустимой точки. Однако она дает базисную двойственно допустимую точку.
Можно видоизменить правила (3.5.1) так, чтобы двигаться не по базисным допустимым точкам, а по базисным двойственно допустимым точкам, пока не получим решение. Другими словами, наш метод начинает с базисной двойственно допустимой точки из (3.6.8), но не использует тот факт, что это базисная двойственно допустимая точка. Вместо этого сначала находятся базисные допустимые точки, после чего ищется решение.
Если при поиске базисной допустимой точки мы стремимся придерживаться таблиц, соответствующих базисным двойственно допустимым точкам, то ясно, что первая полученная базисная допустимая точка будет решением. Третье замечание относится к тому, что не нужно следить за двойственными переменными у; и оь На самом деле каждое уз необходимо будет расположено против соответствующего и, задачи максимизации; то же верно для оз и хь Действительно, очевидно, что каждое ведущее преобразование сохраняет такое взаимное расположение. Га. ИЛ Линейное программирование 88 Ш.6.4.
П р и м е р. Максимизировать х4 + х2 — 2хг+ х2~ — 3, х,— 2х2~ 4, Х„Х2 ~ О. при условиях Р е ш е н и е. Мы получаем таблицу Х, Х2 ! = — иь = — и„ (3.6.13) Делая ведущие преобразования с отмеченными звездочкой эле- ментами, получаем таблицы Х! П2 Х2г (3.6.14) и, и2 1 294 24/ = — хп (3.6.15) — Х2, в! ~зг 44/ Из (3.6.15) ясно, что эта задача неограниченна. Ш.7. ИРРЫ С ОГРАНИЧННИЯМИ Теория линейного программировайия имеет много применений помимо теории игр. Хотя многие из них сами по себе весьма интересны, мы не можем детально на них останавливаться.
Укажем здесь одно применение, которое имеет отношение к теории игр. Рассмотрим игру, в которой допускаются не все смешанные стратегии. Обычно для этого имеются определенные практические основания. Итак предположим, что смешанные стратегии х и у со- П!. 7. Иери е оеранииеииеии 83 ответственно должны выбираться из некоторых выпуклых многогранников, т. е. из допустимых множеств, определяемых линейными неравенствами и уравнениями. Если матрица игры есть А = (ап), то задача игрока 1 состоит и том, чтобы найти шах (ппп хАуг), еих и~г (3.7.1) уЕт ~ Е у = — О. (3.7.4) (3.7.5) Аналогично, задача игрока 11 состоит в том, чтобы найти ш(п (гпах хАуг).
(3.7.6) и г е х Рассмотрим выражение (3.7.1). Величина, стоящая в скобках, очевидно, является функцией х. Точнее, она является значением задачи линейного программирования, целевая функция которой имеет коэффициенты, зависящие от х. По теоремам двойственности из $ 111.2 мы знаем, что если эта задача допустима и ограничена (что, вообще говоря, не зависит от х), то две задачи минимизировать (хА)ут (3.7.7) при условиях уЕ МЕ, (3.7.8) у~О (3.7.9) максимизировать грт гЕ:- хА, г '=" О (3.7.!О) (3.7.11) (3.7.12) при условиях будут иметь одно и то же значение. Значит, задача игрока 1 сво- дится просто к задаче максимизации: максимизировать грт гŠ— хАЯ О, хВ ~ С, г, х~О. (3.7.13) (3.7.14) (3.7.15) (3.7.16) при условиях Эта задача, конечно, может быть решена обычными методами ли- нейного программирования (симплекс-методом), где два множества Х и У определяются соответственно неравенствами хВ<С, (3.7.2) х~О (3.7.3) Гл.
Пй Линейное программирование 84 Задачи 1. Записать двойственные задачи для следующих задач линейного програм- мирования: (а) максимизировать х, + Зх, — хе при условиих Зх~ + хз 5, х1 - Зх, + х, ~ -5, хе+ Зхз ~ 4. хгт» О, 1=1 2 3; 2х, + 5х, + бхз х, + Зхе+ х, ~ 5, Зхг + 2хз х1 + хз «3, х = О, 1 = 1, 2, 3. (б) минимизировать при условиях 2.
Показать, что задача минимизировать 2х, — Зхз+ при условиях 2хз— -2х1 + х,-Зхз 4хз хз Зхз «-2, 3, « — 4, О, 1 = 1, 2, 3, имеет значение, равное нулю. (Указание: показать, что она допустима; затем найти двойственную задачу). 3. Пусть А (х, у) — непрерывная функция х и у в единичном квадрате 10, Ц Х (О, Ц. Пусть Ь(у) и с(х) определены и непрерывны на 10, Ц. Показать, что если 1(х) и у(у) — непрерывные неотрицательные функции на 10, Ц, такие, что ~ А (х, у) 7 (х) е(х = Ь (у) ~ А(х, у) у(у) Ау ~ е(х), о Аналогично, можно показать, что задача (3.7.6) игрока П сводится к задаче минимизации: минимизировать Сит (3.7.17) при условиях ЗЗт Ат»0 ' (3.7.18) уЕт=- Р (3.7.19) з, у = О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
