Элементы теории игр в системном анализе

Введение
Актуальность темы исследования. Теория игр – это раздел теории исследования операций, предметом которого является анализ принятия решений в условиях конфликта. Возникнув из задач классической теории вероятностей, теория игр превратилась в самостоятельный раздел в 1945–1955 годах. Таким образом, теория игр – один из новейших разделов математики. Достаточно полное изложение идей и методов теории игр впервые появилось в 1944 году в труде «Теория игр и экономическое поведение» математика Дж. фон Неймана и экономиста О. Моргенштерна. Первые приложения теория игр нашла в решении некоторых возникших во время II мировой войны военных проблем специального характера.В последние годы значение теории игр существенно возросло во многих областях экономических и социальных наук. В экономике она применима не только для решения общехозяйственных задач, но и для анализа стратегических проблем предприятий, разработок организационных структур и систем стимулирования.Изучение многофакторной системы можно представить как исследование формы этой поверхности, называемой поверхностью отклика. Пространство в котором строится поверхность отклика (или совокупность уровней факторов, используемых в планировании, эксперимента) называется факторным пространством.Цель данной работы – рассмотреть элементы теории игр в системном анализе, а также поверхность отклика и метод крутого восхождения.Для достижения поставленной цели необходимо решить следующие задачи:1. Охарактеризовать элементы теории игр в системном анализе.2. Изучить поверхность отклика и метод крутого восхождения.1. Элементы теории игр в системном анализеКлассическими задачами системного анализа являются игровые задачи принятия решений в условиях риска и неопределенности.Неопределенными могут быть как цели операции, условия выполнения операции, так и сознательные действия противников или других лиц, от которых зависит успех операции.Разработаны специальные математические методы, предназначенные для обоснования решений в условиях риска и неопределенности. В некоторых, наиболее простых случаях эти методы дают возможность фактически найти и выбрать оптимальное решение. В более сложных случаях эти методы доставляют вспомогательный материал, позволяющий глубже разобраться в сложной ситуации и оценить каждое из возможных решений с различных точек зрения, и принять решений с учетом его возможных последствий. Одним из важных условий принятия решений в этом случае является минимизация риска.При решении ряда практических задач исследования операций (в области экологии, обеспечения безопасности жизнедеятельности и т. д.) приходится анализировать ситуации, в которых сталкиваются две (или более) враждующие стороны, преследующие различные цели, причем результат любого мероприятия каждой из сторон зависит от того, какой образ действий выберет противник. Такие ситуации мы можно отнести к конфликтным ситуациям.Теория игр является математической теорией конфликтных ситуаций, при помощи которой можно выработать рекомендации по рациональному образу действий участников конфликта. Чтобы сделать возможным математический анализ ситуации без учета второстепенных факторов, строят упрощенную, схематизированную модель ситуации, которая называется игрой. игра ведется по вполне определенным правилам, под которыми понимается система условий, регламентирующая возможные варианты действий игроков; объем информации каждой стороны о поведении другой; результат игры, к которому приводит каждая данная совокупность ходов.Результат игры (выигрыш или проигрыш) вообще не всегда имеет количественное выражение, но обычно можно, хотя бы условно, выразить его числовым значением.Ход — выбор одного из предусмотренных правилами игры действий и его осуществление. Ходы делятся на личные и случайные. Личным ходом называется сознательный выбор игроком одного из возможных вариантов действий и его осуществление. Случайным ходом называется выбор из ряда возможностей, осуществляемый не решением игрока, а каким-либо механизмом случайного выбора (бросание монеты, выбор карты из перетасованной колоды и т. п.). Для каждого случайного хода правила игры определяют распределение вероятностей возможных исходов. Игра может состоять только их личных или только из случайных ходов, или из их комбинации. Следующим основным понятием теории игр является понятие стратегии. Стратегия — это априори принятая игроком система решений (вида «если — то»), которых он придерживается во время ведения игры, которая может быть представлена в виде алгоритма и выполняться автоматически.Целью теории игр является выработка рекомендаций для разумного поведения игроков в конфликтной ситуации, т. е. определение «оптимальной стратегии» для каждого из них. Стратегия, оптимальная по одному показателю, необязательно будет оптимальной по другим. Сознавая эти ограничения и поэтому не придерживаясь слепо рекомендаций, полученных игровыми методами, можно все же разумно использовать математический аппарат теории игр для выработки, если не в точности оптимальной, то, во всяком случае «приемлемой» стратегии.Игры можно классифицировать: по количеству игроков, количеству стратегий, характеру взаимодействия игроков, характеру выигрыша, количеству ходов, состоянию информации и т.д. В зависимости от количества игроков различают игры двух и n игроков. Первые из них наиболее изучены. Игры трех и более игроков менее исследованы из-за возникающих принципиальных трудностей и технических возможностей получения решения.В зависимости от числа возможных стратегий игры делятся на «конечные» и «бесконечные».Игра называется конечной, если у каждого игрока имеется только конечное число стратегий, и бесконечной, если хотя бы у одного из игроков имеется бесконечное число стратегий.По характеру взаимодействия игры делятся на бескоалиционные: игроки не имеют права вступать в соглашения, образовывать коалиции; коалиционные (кооперативные) — могут вступать в коалиции.В кооперативных играх коалиции заранее определены.По характеру выигрышей игры делятся на: игры с нулевой суммой (общий капитал всех игроков не меняется, а перераспределяется между игроками; сумма выигрышей всех игроков равна нулю) и игры с ненулевой суммой.По виду функций выигрыша игры делятся на: матричные, биматричные, непрерывные, выпуклые и др.Матричная игра — это конечная игра двух игроков с нулевой суммой, в которой задается выигрыш игрока 1 в виде матрицы (строка матрицы соответствует номеру применяемой стратегии игрока 1, столбец — номеру применяемой стратегии игрока на пересечении строки и столбца матрицы находится выигрыш игрока 1, соответствующий применяемым стратегиям).Для матричных игр доказано, что любая из них имеет решение и оно может быть легко найдено путем сведения игры к задаче линейного программирования.Биматричная игра — это конечная игра двух игроков с ненулевой суммой, в которой выигрыши каждого игрока задаются матрицами отдельно для соответствующего игрока (в каждой матрице строка соответствует стратегии игрока 1, столбец — стратегии игрока 2, на пересечении строки и столбца в первой матрице находится выигрыш игрока 1, во второй матрице — выигрыш игрока).Непрерывной считается игра, в которой функция выигрышей каждого игрока является непрерывной. Доказано, что игры этого класса имеют решения, однако не разработано практически приемлемых методов их нахождения.Если функция выигрышей является выпуклой, то такая игра называется выпуклой. Для них разработаны приемлемые методы решения, состоящие в отыскании чистой оптимальной стратегии (определенного числа) для одного игрока и вероятностей применения чистых оптимальных стратегий другого игрока. Такая задача решается сравнительно легко.2. Поверхность отклика. Метод крутого восхожденияПоверхность отклика (ндп. Поверхность регрессии) - геометрическое представление функции отклика.Методология анализа поверхности отклика полезна для реализации 3 типа вычислительного эксперимента, связанного с отысканием оптимальных условий.Во многих случаях целью моделирования является отыскание таких величин или уровней независимых переменных, при которых отклик или зависимая переменная достигает оптимальных (максимальных или минимальных) значений. Если зависимая и независимая переменные количественны и непрерывны, то для решения задачи поиска оптимума обычно используется методология поверхности отклика (RSO), которая состоит в отыскании оптимальной комбинации уровней – количественных факторов.Если обозначить зависимую переменную через у, а независимые переменные через (х1 ,x2, ..., хk), где k — число факторов, и предположить, что все переменные количественны, непрерывны и измеримы, то уравнение поверхности отклика можно записать в следующем виде:y=F(x1,x2,...,хk).Очень полезно иметь геометрическое представление поверхности отклика. На рис. 1 изображена поверхность отклика, изображающая зависимость отклика у от двух независимых переменных в прямоугольной системе координат.1570355338645500Рисунок 1 – Поверхность откликаДругое полезное представление поверхности отклика можно получить, изображая на плоскости х1 x2 проекции на нее линий постоянного отклика у = у0, проведенных на поверхности отклика (контуры отклика).Такое изображение поверхностей отклика аналогично изображению на топографических картах рельефа местности посредством контуров равной высоты или изображению на картах погоды изобар, показывающих распределение атмосферного давления на поверхности Земли.Безусловно, геометрические представления поверхности отклика ограничены трехмерными изображениями. Однако геометрическое представление трехмерных поверхностей отклика вида y=f (x1, x2) помогает понять, что происходит в более общем случае — при k независимых переменных. Поэтому дальше мы ограничимся рассмотрением трехмерных поверхностей отклика.Методология поверхности отклика обычно основана на исследовании поверхности отклика с помощью ряда небольших полных или неполных факторных экспериментов. В имитационном моделировании используется технология последовательного планирования. Такого рода последовательные планы используются в методологии анализа поверхности отклика (RSО), которая состоит в отыскании оптимальной комбинации уровней k количественных факторов, где реализуется пошаговая процедура движения к точке оптимума.Сделаем небольшое пояснение. Если известно точное математическое выражение функции отклика, то отыскание оптимальной точки можно сравнительно просто осуществить аналитическими методами. Так как обычно мы не знаем вид поверхности отклика, то необходимо использовать в качестве аппроксимации какую-либо гибкую, плавно изменяющуюся функцию. В качестве такой функции обычно используют полином первого порядка или полином второго порядка, где коэффициенты этого полинома оцениваются с помощью эксперимента.В этом случае наша задача состоит в том, чтобы как можно быстрее выйти в близкую к оптимуму область, а затем воспользоваться аналитическими методами локального представления этой функции в окрестности точки оптимума. Эти эксперименты могут использоваться для разрешения двух вопросов.Первый из них связан с выбором такого направления перемещения для проведения следующего эксперимента, чтобы приблизиться к оптимальной точке. К точке оптимума (вернее в область оптимума) надо придти наискорейшим образом в RSО для этого используется метод наискорейшего подъема (или Крутое восхождение по поверхности отклика). С этой целью реализуются планы 2k или 2k-p, используется линейная регрессия.Второй вопрос возникает тогда, когда мы уже находимся в достаточной близости к точке экстремума. Этот второй вопрос — вопрос о виде уравнения поверхности отклика вблизи оптимальной точки. Можно воспользоваться аналитическими методами для локального представления этой функции в окрестности точки оптимума. Вблизи точки оптимума линейная аппроксимация перестает быть удовлетворительной, и используется полином более высокого порядка. Для этого необходимо использовать планы 3k и др., -и квадратичные полиномы.Предлагаемая концепция оптимизации условно включает 2 этапа:1 этап оптимизации — крутое восхождение с целью скорейшего достижения области оптимума. Используется линейное планирование и реализуется пошаговая итерационная процедура движения в направлении градиента.Однако область оптимума не может быть описана линейным приближением.2 этап — описание области оптимума методами нелинейного планирования и исследование почти стационарной области.Наиболее часто используется в МПО так называемый метод наискорейшего подъема — крутого восхождения. Наиболее короткий путь к вершине направление градиента функции отклика, на рис. 2 — это направление Q, перпендикулярное линиям уровня. Это так называемый градиентный метод поиска оптимума. Вы знаете, что, градиент непрерывной однозначной функции:Yi = b0 + b1 Хi1 + b2 Xi2 +…+ bkXik + ei (i = 1, …, N)есть частная производная функции Y .Составляющие градиента суть частные производные функции отклика, оценками которых являются коэффициенты регрессии.1615440-2476500Рисунок 2 – Контуры отклика с изображением 2'-факторного планаОсновная идея метода состоит в построении линейной аппроксимации поверхности отклика в окрестности данной точки с помощью простого факторного эксперимента. По построенной линейной функции определяется направление наискорейшего подъема к точке оптимума -в направлении градиента функции отклика. По этому направлению делается небольшой шаг, затем повторяется процедура определения направления наискорейшего подъема и т.д.Этот метод не позволяет определять длину шага (длина шага определяется экспериментатором, она не должна быть очень большой, чтобы не проскочить оптимум, и не должна быть очень маленькой -чтобы не проводить большое количество шагов), однако показывает направление движения.Предположим, что исследователь провел в точке Р эксперимент с 22 комбинациями плюс два наблюдения в центре. Эксперимент позволил оценить a0, а1и а2определяющие наклон плоскости аппроксимации, и вычислить направление наискорейшего возрастания или максимального наклона плоскости. Это направление показывает относительные величины изменения факторов, обеспечивающие увеличение отклика. Продвинувшись по этому направлению до некоторой точки Q, следует повторить всю процедуру.Такая пошаговая процедура позволяет достигать все больших и больших откликов.Итак, изменяя независимые переменные пропорционально коэффициентам регрессии (с учетом их знаков), мы будем двигаться в направлении градиента функции отклика по самому крутому пути. Поэтому процедура движения к почти стационарной области называется крутым восхождением.
Заключение

Таким образом, теория игр — это раздел математической экономики, изучающий решение конфликтов между игроками и оптимальность их стратегий. Конфликт может относиться к разным областям человеческого интереса: чаще всего это экономика, социология, политология, реже биология, кибернетика и даже военное дело. Конфликтом является любая ситуация, в которой затронуты интересу двух и более участников, традиционно называемых игроками. Для каждого игрока существует определенный набор стратегий, которые он может применить. Пересекаясь, стратегии нескольких игроков создают определенную ситуацию, в которой каждый игрок получает определенный результат, называемый выигрышем, положительным или отрицательным. При выборе стратегии важно учитывать не только получение максимального профита для себя, но так же возможные шаги противника, и их влияние на ситуацию в целом.Поверхность отклика (поверхность регрессии) – геометрическое представление функции отклика. Изменяя независимые переменные пропорционально коэффициентам регрессии (с учетом их знаков), мы будем двигаться в направлении градиента функции отклика по самому крутому пути. Поэтому процедура движения к почти стационарной области называется крутым восхождением.
Список использованной литературы
Качала, В.В. Основы теории систем и системного анализа [Электронный ресурс] : учебное пособие / В.В. Качала. — Электрон. дан. — Москва : Горячая линия-Телеком, 2016. — 210 с. — Режим доступа: https://e.lanbook.com/book/111061Овчаренко, А. Г. Системный анализ [Электронный ресурс]: методические рекомендации по изучению дисциплины, организации самостоятельной работы студентов и выполнению контрольной работы для студентов направления подготовки 15.03.05 «Конструкторско- технологическое обеспечение машиностроительных производств» всех форм обучения / А. Г. Овчаренко. - [Б. м.] : Алт. гос. техн .ун-т, БТИ. - Бийск: Изд-во Алт. гос. техн. ун-та, 2020. - 11 с. http://irbis.bti.secna.ru/doc10/2020-20.pdfПоверхность отклика. - https://studfile.net/preview/8912962/page:5/Теория игр и принятие решений. - https://victor-safronov.ru/systems-analysis/lectures/rodionov/10.html Элементы теории игр в системном анализе. - https://vuzdoc.org/77765/tehnika/elementy_teorii_sistemnom_analizeЯковлев, С.В. Теория систем и системный анализ : учебное пособие / С.В. Яковлев. — 3-е изд. — Москва : Горячая линия-Телеком, 2015. — 320 с. — ISBN 978-5-9912-0496-5. — Текст : электронный // Электронно-библиотечная система «Лань» : [сайт]. — https://e.lanbook.com/book/107636.