Суть этого алгоритма [92] состоит в соединении основной схемы итеративного алгоритма решения соответствующей нецелочисленной задачи с идеей доводки его до целочисленного методом случайного поиска. Итеративный алгоритм, основанный на идее известного метода Брауна— Робинсона решения матричных игр, дает возможность получить приближенное решение задачи линейного программирования при небольших затратах машинного времени. Проведенные эксперименты доказывают, что в применении к некоторым классам задач линейного программирования итеративные алгоритмы могут конкурировать с симплексными [92]. [c.190]
Решение матричной игры можно свести к решению стандартной задачи линейного программирования. [c.83]
В предыдущих пунктах мы убедились, что решение матричной игры может быть сведено к решению пары двойственных друг другу задач линейного программирования. Покажем, что и наоборот, если пара двойственных задач имеет решения, то их множество полностью описывается множеством решений некоторой матричной игры. Тем самым будет установлено, что теория матричных игр в некотором смысле эквивалентна теории стандартных задач линейного программирования. [c.84]
Подробное описание связи между разрешимостью пар двойственных задач линейного программирования и нахождением их решений, с одной стороны, и решениями матричных игр - с другой, содержится в следующей теореме. [c.85]
Из нее следует, что любой метод решения задач линейного программирования может быть без труда приспособлен для решения матричных игр. [c.87]
Теория игр разработана пока еще недостаточно. Существуют методы решения для игр двух лиц с нулевой суммой при ограниченном числе возможных стратегий. Для решения матричных игр можно использовать методы линейного программирования и итерационные методы. Наиболее просто решаются матричные игры, имеющие седловую точку. Слабее разработаны методы решения др. игр, в особенности бесконечных. Научная работа в области Т. и. направлена не только на совершенствование ее математич. аппарата, но и на подбор и соответствующую формулировку реальных задач, в частности экономических. [c.154]
Для решения матричных игр существуют различные методы напр., методы, основанные на сведении матричной игры к задаче линейного программирования итеративный процесс Брауна и его модификации. [c.113]
Другой метод решения матричных игр базируется на указанном выше свойстве, гарантирующем, что применение чистых стратегий Игроком 2 (Игроком 1) против оптимальной смешанной стратегии Игрока 1 не позволяет ему проиграть меньше (выиграть больше), чем значение цены игры v. Это позволяет сформулировать следующую задачу для Игрока 1 [c.229]
Решение матричных игр методами линейного программирования. Рассмотрим некоторые способы решения матричных игр. Задача, решаемая первым игроком, (6.10) была сформулирована как максимизация наименьшей из сумм [c.193]
Рассуждения предыдущего параграфа фактически уже содержат некоторый прием симметризации игры. В самом деле, согласно сказанному в пп. 25.1 — 25.2 решение всякой матричной игры может быть сведено к решению пары двойственных друг другу задач линейного программирования. А на основе сказанного в пп. 25.3 — 25.6 решение такой пары задач сводится к решению некоторой симметричной игры. Опишем в явном виде последовательное проведение этих двух приемов. [c.88]
Количественный анализ предполагает численную оценку рисков, определение их степени и выбор оптимального решения. Во второй главе рассмотрена система количественных оценок экономического риска. Опираясь на теорию матричных игр, применяя различные критерии эффективности, используя теорию двойственных задач линейного программирования дан целостный подход для различных экономических задач выбора оптимальных решений в условиях неопределенности. Количественная оценка риска проводится также с использованием методов математической статистики и теории вероятностей, которые позволяют предвидеть возникновение неблагоприятной ситуации и по возмож- [c.274]
Таким образом, в общем случае для решения матричной антагонистической игры размерностью /ихл необходимо решить пару двойственных задач линейного программирования, в результате чего находится набор оптимальных стратегий , / и цена игры v. [c.229]
Эквивалентность матричной игры и задачи линейного программирования. Чрезвычайно важным и исключительно полезным оказался тот факт, что всякая игра двух лиц с нулевой суммой эквивалентна некоторой задаче линейного программирования. Это означает, что по заданной платежной матрице игры можно построить такую пару задач линейного программирования, решения которых определяют оптимальные стратегии обоих игроков. И, наоборот, всякой задаче линейного программирования можно сопоставить игру так, что оптимальные стратегии игроков дадут решения исходной задачи и двойственной к ней. Мы не будем приводить здесь полного доказательства эквивалентности, а ограничимся тем, что покажем, как от игры перейти к задаче линейного программирования. [c.135]
Графические методы решения игр. Следует отметить, что применение для решения задач (6.16)-(6.17), (6.18)-(6.19) стандартных алгоритмов линейного программирования далеко не всегда является рациональным. Помимо этого существуют иные методы, которые основываются на использовании специфики данных задач. В настоящем пункте мы остановимся на очень простом классическом способе поиска оптимальных смешанных стратегий в матричных играх, где один из участников имеет только две стратегии (это так называемые 2 х п и т х 2 игры). [c.194]
Известны следующие методы линейное программирование, динамическое программирование, теория игр и массового обслуживания, матричный метод затраты — выпуск и др. Наибольшее распространение получили методы линейного программирования. Задачи, решаемые с помощью этих методов, носят экстремальный характер. Результатом решения является определение максимума или минимума какой-то целевой функции, в качестве которой может приниматься прибыль, выработка товарной продукции, себестоимость и др. Выбор целевой функции зависит от пели задачи. В связи с переходом на новые условия планирования для предприятия в целом более целесообразна постановка задачи на максимум прибыли (П). Математически такая задача формулируется следующим образом [c.127]
МАТРИЧНЫЕ ИГРЫ [matrix games] — класс антагонистических игр, в которых участвуют два игрока, причем каждый игрок располагает конечным числом стратегий. Если один игрок имеет т стратегий, а второй — п, то можно построить матрицу игры размерностью тхп. М.и. могут иметь седловую точку, но могут и не иметь ее. В последнем случае решение игры в чистых стратегиях невозможно и оптимальные стратегии игроков отыскиваются среди их смешанных стратегий. М.и. для нахождения таких стратегий удобно преобразовывать в задачи линейного программирования. [c.189]
Следующее свойство оптимальных стратегий игроков в матричной игре называется "дополняющей нежесткостью" по аналогии со сходным свойством решений пар двойственных задач линейного программирования (ср. далее в 26). По своей формулировке и своему доказательству оно сходно с частью 1) теоремы предыдущего пункта и двойственным ей утверждением. [c.60]
Из сказанного выше видно, что с ростом формата матричной игры весьма резко возрастает сложность анализа игры и трудоемкость ее решения. Поэтому любые приемы, позволяющие сводить решение игры к решению другой игры, меньшего формата, представляются весьма полезными. Если выражаться более точно, то здесь, говоря о "сведении", мы имеем в виду две задачи. Во-первых, более легкую построить по игре 1 такую ее подыгру Г , что с (А )С ( (А), а, во-вторых, — более трудную построить по игре Г такую ее подыгру Г >, что ё (Аг) = (А). При этом в обоих случаях, в соответствии со сказанным в п. 8.5, мы отождествляем смешанные стратегии игроков в подыгре ГА со смешанными стратегиями этих игроков в игре 1 , получаемыми из стратегий в игре Г путем надлежащего их пополнения нулевыми компонентами. [c.76]
Показано, что синтез робастных регуляторов для линейных неопределенных систем с ограниченными по норме неизвестными параметрами может быть осуществлен на основе решений некоторого класса дифференциальных игр между управлением и противником, включающим возмущение "неопределенность в системе. При этом множество всех таких линейных регуляторов характеризуется в терминах решений матричных неравенств Лурье-Риккати или линейных матричных неравенств, а также, решая соответствующую обратную задачу, непосредственно в терминах частотных неравенств. [c.268]
Далее, среди найденных обратных связей выделяются так называемые центральные, соответствующие минимаксным законам управления в указанных выше играх. Применяя подход обратных вариационных задач [5], показывается, что для харак-териэацих центральных робастных законов управления можно избежать необходимости решения уравнения Лурье-Рнккати или линейного матричного неравенства и получить частотные условия, непосредственно выделяющие значения параметров центральных робастных Ям законов управления. [c.269]
Смотреть страницы где упоминается термин Задача решения матричных игр
: [c.244]Смотреть главы в:
Теория игр для экономистов-кибернетиков -> Задача решения матричных игр