диплом крнфликты. Ю. В. Литвинов Моделирование конфликтов в двухсторонней теории игр Учебное пособие
 Скачать 0.67 Mb.
|
|
0 1 А.Б. Бушуев, Ю.В. Литвинов Моделирование конфликтов в двухсторонней теории игр Учебное пособие РЕКОМЕНДОВАНО К ИСПОЛЬЗОВАНИЮ В УНИВЕРСИТЕТЕ ИТМО по направлениям подготовки 27.04.03, 15.04.06, 27.04.04 в качестве учебного пособия для реализации основных образовательных программ высшего образования магистратуры. Санкт-Петербург 2018 2 А.Б. Бушуев, Ю.В.Литвинов. Моделирование конфликтов в двухсторонней теории игр – СПб: СПб НИУ ИТМО, 2018. – с. © А.Б.Бушуев, Ю.В. Литвинов, 2018. Рецензент Быстров СВ, к.т.н., доцент факультета Систем управления и робототехники Университета ИТМО. В учебном пособии рассмотрены методы моделирования конфликтного поведения в экономических и технических системах, основанные на математической теории игр двух лиц и теории решения изобретательских задач. Пособие предназначено для студентов (магистров) технических вузов по направлениям 27.04.03 Системный анализ и управление 15.04.06 «Мехатроника и робототехника, 27.04.04 Управление в технических системах. Учебное пособие может быть полезно для краткого первичного знакомства с основными положениями линейного и нелинейного программирования, используемыми на практических занятиях, а также с задачей двухсторонней монополии при выполнении домашнего задания. Университет ИТМО–ведущий вуз России в области информационных и фотонных технологий, один из немногих российских вузов, получивших в 2009 г статус национального исследовательского университета. С 2013 г Университет ИТМО – участник программы повышения конкурентноспособности российских университетов среди ведущих мировых научно-образовательных центров, известной как программа «5 в 100». Цель Университета ИТМО–становление исследовательского университета мирового уровня, предпринимательского по типу, ориентированного на интернационализацию всех направлений деятельности. Университет ИТМО, 2018 © А.Б.Бушуев, Ю.В. Литвинов 2018 3 Оглавление Введение 1. Некоторые сведения о задачах линейного и нелинейного программирования ……………………………………………….………….….4 1.1. Безусловный экстремум 1.2. Задача линейного программирования ………………………………...…....7 1.3. Задача нелинейного программирования 2. Введение в матричную теорию игр двух лиц 2.1. Игра с нулевой суммой. Минимаксная стратегия 2.2. Смешанные стратегии 2.3. Рандомизированное управление 3. Двухсторонняя монополия в теории игр 3.1. Этапы конфликта. Нахождение состояния равновесия 3.2. Построение перил и ядра игры ……………………………………....…...33 3.3. Игровая модель конфликта в изобретательской задаче Литература 4 Введение Пособие предназначено для изучения дисциплин Теория решения изобретательских задачи Моделирование процессов технического творчества. Новизна предлагаемого материала заключается в использовании математического аппарата теории игр двух лиц для моделирования противоречий в технических и технико-экономических системах. Цель пособия – изучение вопросов системного анализа в задачах технического творчества для моделирования и принятия решений в конфликтных ситуациях. В первом разделе приводятся некоторые теоретические сведения о задачах линейного и нелинейного программирования, необходимые для следующих двух разделов, и методы их решения. Во втором разделе рассматриваются основные понятия теории матричных игр двух лиц, основной результат теории игр, осторожные и смешанные стратегии для принятия решений с риском. Материалы этого раздела используются для практических занятий и требуют элементарных навыков работы в программной среде «Mathcad». В третьем разделе рассматривается двухсторонняя монополия, как игра с непрерывными платежными функциями и с ненулевой суммой. В первых двух параграфах раздела двухсторонняя монополия выступает как экономическая задача, находятся условия равновесия и возможности его достижения в условиях ограничений, в третьем-двухсторонняя монополия и алгоритм решения изобретательских задач. Этот раздел используется для выполнения самостоятельного домашнего задания в соответствии с заданным вариантом в виде патента-прототипа. Патент-прототип должен быть найден студентом самостоятельно по номеру в базе данных Федерального института промышленной собственности (ФИПС). В целом пособие позволяет вырабатывать компетенции по применению системных решений в области проектирования, конструирования, разработки и управления жизненным циклом электронных средств, технических, технико- экономических и киберфизических систем. Некоторые сведения о задачах линейного и нелинейного программирования Для решения задач теории игр используются методы линейного и нелинейного программирования и предполагают нахождение программы действий или ходов в игре, которые дают максимальный выигрыш или минимальный проигрыш. Такие задачи сводятся к нахождению экстремума заданной функции с ограничениями. Задача программирования ставится следующим образом. Заданы целевая функция J = J(x), где J - скалярная величина, а x - мерный вектор, уравнение ограничений G(x) ≥ 0, где G(x) – векторозначная функция переменной х мерностью m. 5 Необходимо найти такое значение x*, которое дает экстремальное значение целевой функции J(x*) при ограничениях G(x) ≥ 0, те. решением задачи программирования является вектор x*. Если целевая функция J(x) и уравнения ограничений G(x)≥0 являются линейными относительно переменной х, то задача нахождения экстремума относится к задачам линейного программирования. Если целевая функция J(x) или уравнения ограничений являются нелинейными относительно переменной х, то задача нахождения экстремума относится к задачам нелинейного программирования. Если уравнения ограничений не заданы, то задача нахождения экстремума называется задачей на безусловный экстремум, в противном случае - задачей на условный экстремум. Отметим важное обстоятельство задача линейного или нелинейного программирования не всегда имеет решение. 1.1. Безусловный экстремум Из математики известно [1], что необходимым условием решения задач на безусловный экстремум является равенство нулю первой производной от целевой функции J(x) попеременной х, те. где первая производная от скалярной функции по векторному аргументу или градиент является также n -мерным вектором Решением уравнения является вектор х, задающий в мерном пространстве точку, подозрительную на экстремум. Она будет максимумом целевой функции, если вторая производная от целевой функции в этой точке будет отрицательной, и минимумом - если вторая производная будет положительной. Вторая производная от скалярной функции J(x) по векторному аргументу х будет квадратной матрицей размером n на n. Эта матрица Г называется матрицей Гессе или гессианом 6 n x n x x J x n x x J x n x x J n x x x J x x x J x x x J n x x x J x x x J x x x J x x J ) ( 2 2 ) ( 2 1 ) ( 2 2 ) ( 2 2 2 ) ( 2 1 2 ) ( 2 1 ) ( 2 2 1 ) ( 2 Так как вторая производная от целевой функции является матрицей, то условие положительности Г > 0 означает, что матрица Г является положительно определенной, а условие отрицательности второй производной Г < 0 означает, что матрица Г является отрицательно определенной. Положительная или отрицательная определенность квадратной матрицы, в том числе, и матрицы Гессе, может быть установлена по критерию Сильвестра: - если все главные последовательные миноры матрицы положительны, то и матрица является положительно определенной, - если нечетные главные миноры отрицательны, а четные главные миноры положительны, то матрица является отрицательно определенной Последовательные главные миноры матрицы находятся как определители последовательно нарастающего порядка, составленные из элементов матрицы, расположенных симметрично относительно ее главной диагонали. Например, для матрицы Г последовательность главных миноров равна ) ( 2 2 ) ( 2 1 ) ( 2 2 ) ( 2 2 2 ) ( 2 1 2 ) ( 2 1 ) ( 2 2 1 ) ( 2 1 1 ) ( 2 ...Ã ,... 2 2 ) ( 2 1 2 ) ( 2 2 1 ) ( 2 1 1 ) ( 2 2 Ã , 1 1 ) ( 2 Рассмотрим пример. Пусть целевая функция равна где 22 10 , 5 1 1 3 p Q 7 Находим градиент целевой функции и приравниваем его нулю 0 0 22 10 2 1 5 1 1 3 Решение этой системы уравнений дает вектор 2 1 2 Находим матрицу Гессе 10 2 2 Главные миноры равны 56 2 2 10 6 2 Ã , 6 Первый (нечетный) и второй (четный) главные миноры положительны, следовательно, матрица Га найденная точка x* является точкой минимума. 1.2. Задача линейного программирования Целевая функция задается в виде линейной формы , 2 2 1 или в векторно-матричной форме где n c c c C 2 1 T - матрица-строка постоянных коэффициентов линейной формы. Если не заданы уравнения ограничений, то задача линейного программирования не имеет решения. Действительно, вектор-градиент от линейной целевой функции равен матрице С постоянных коэффициентов и никак не может быть равен нулевому вектору, что необходимо для экстремума. Уравнения ограничений задаются системой линейных алгебраических уравнений c неизвестными m b n x mn a x m a x m a b n x n a x a x a b n x n a x a x a 2 2 1 1 2 2 2 22 1 21 1 1 2 12 причем число уравнений меньше числа неизвестных, те. m < n. В векторно-матричном виде система может быть записана как 8 Ax=B, где m b b b B mn a m a m a n a a a n a a a A 2 1 , 2 1 2 22 21 1 12 и коэффициенты матриц Аи В заданы. Кроме того, в задаче линейного программирования задаются ограничения на знак координат векторах, обычно они должны быть неотрицательными n i i x ,... 1 , 0 В задаче необходимо найти вектор х для нахождения минимума целевой функции. Для нахождения максимума знак min в формуле меняется на знак max. Как же решать такую задачу Если бы число уравнений m равнялось числу переменных n, то можно было бы решить систему Ах=В (конечно, при условии detA≠0) и найти некоторое решение. Но, поскольку m<n, то имеется бесконечное число решений, те. наборов векторов х, которые удовлетворяют системе Ах=В. Учтем, что не допускаются решения с отрицательными значениями координат векторах. Это несколько сокращает число возможных решений, которые называются допустимыми, и все же их число может быть также очень большим (принципиально, тоже до ∞). Из всех допустимых решений надо выбрать одно, которое минимизирует (или максимизирует) целевую функцию q(x). Намечается следующий возможный путь решения задачи. Так как m<n, то часть неизвестных переменных (n-m штук) можно обнулить, поскольку допускаются нулевые значения переменных х. Тогда оставшиеся m штук переменных в системе Ах=В определяются однозначно (при условии detA≠0). Если же detA=0, то можно попробовать обнулить другие n-m переменных и снова попробовать решить задачу. Полученное решение называется базисным, а m штук переменных, которые дают это решение, называются базисом. Остальные, обнуляемые n-m штук переменных, называются свободными. В общем случае может существовать множество базисных решений (если перебрать всевозможные наборы обнуляемых и не обнуляемых переменных. Из всех базисных решений выбираем допустимые (неотрицательные значения всех координат векторах. Наконец, из всех допустимых значений выбираем одно, которое дает экстремум целевой функции q(x). 9 В случае двух свободных переменных геометрическое пояснение может быть представлено на плоскости (рис. 1.1.) Всего имеется 5 переменных в системе уравнений-ограничений, x 1 и x 2 свободные, а x 3 , x 4 , образуют базис Рисунок 1.1. Геометрическое пояснение задачи линейного программирования Уравнения x 1 =0 и x 2 =0 на рис задают оси ординат и абсцисса уравнения базисных переменных x 3 =0, x 4 =0, x 5 =0 замыкают выпуклый многоугольник abcde, который является частным случаем симплекса. Для более высокой мерности пространства свободных переменных (больше двух) симплексом будет выпуклый многогранник. Таким образом, симплекс геометрически представляет систему линейных уравнений ограничений Ах=В. Линии постоянного уровня целевой функции q(x)=Const на рис. 1.1 представляют прямые, проходящие параллельно друг другу. Для решения задачи максимизации линии перемещаются параллельно вправо вниз, пока не достигают максимального значения q(x) = q 2 в точке d симплекса. Координаты точки d и задают решение задачи максимума с ограничениями. Для решения задачи минимизации линии перемещаются параллельно влево вверх, пока не достигают минимального значения q(x) = q 1 в точке с симплекса. Координаты точки си задают решение задачи минимума с ограничениями. Обратим внимание, что в системе уравнений-ограничений могут быть не только равенства, но и неравенства (или даже все неравенства, например 1 1 2 12 Тогда каждое неравенство приводится к эквивалентному равенству путем введения в систему дополнительной фиктивной переменной 0 1 n x 10 Значение ее также неизвестно и находится в результате решения задачи линейного программирования. Эта переменная вычитается из левой части неравенства 1 1 1 2 12 Так как дополнительная переменная может быть больше нуля, то ее вычитание из левой части неравенства приводит его к равенству. Если исходное неравенство имеет знак « ≤ », то дополнительную переменную уже прибавляют клевой части неравенства, выравнивая его до равенства. Таким же образом все остальные неравенства приводятся к равенствам, причем для каждого неравенства нужна своя дополнительная переменная. Мерность неизвестного векторах еще больше возрастает по сравнению с числом уравнений-ограничений m, увеличивается и число возможных переборов базисных и свободных переменных, возрастает трудоемкость решения. В дальнейшем будем предполагать, что все неравенства в системе уравнений- ограничений Ах=В выровнены. Из наиболее известных компьютерных методов решения задачи линейного программирования является так называемый симплекс-метод [2]. Более подробно программа для решения задачи линейного программирования рассмотрена в главе 2. 1.3. Задача нелинейного программирования Рассмотрим частный случай задачи нелинейного программирования, когда уравнение ограничений представляет собой строгое равенство G(x) = 0. Для нахождения точки экстремума в этом случае можно использовать метод неопределенных множителей Лагранжа. Для нахождения экстремума функции х) составляем функцию Лагранжа ) ( T ) ( ) , ( x G x J x L , где λ - мерный вектор неопределенных множителей Лагранжа, G(x) - функция ограничений, по сути являющаяся также мерным вектором m 2 Таким образом, первое уравнение ограничений будет иметь вид G 1 (x) = 0, второе G 2 (x) = 0 и т.д. Всего будет m штук уравнений-равенств. Поэтому и вектор λ является мерным вектором. 11 Необходимым условием экстремума является равенство нулю первой производной от функции Лагранжа. Так как функция Лагранжа зависит от двух переменных, то находим частные производные и приравниваем их нулю где n x x m G x x m G x x m G n x x G x x G x x G n x x G x x G x x G dx dG ) ( 2 ) ( 1 ) ( ) ( 2 2 ) ( 2 1 ) ( 2 ) ( 1 2 ) ( 1 Решением этой системы уравнений Лагранжа будет вектор хи вектор λ, при которых функция Лагранжа будет иметь экстремальное значение. Утверждается также, что тот же самый вектор х дает и экстремальное значение исходной целевой функции J(x). Действительно, если поддерживать выполнение второго уравнения системы G(x) = 0 (являющегося и уравнением ограничений, то функция Лагранжа L(x,λ) и целевая функция J(x) будут совпадать, поскольку от прибавления нуля значение функции не меняется. Рассмотрим пример. Пусть J(x) = (x 1 )² + (x 2 )², а уравнение ограничений имеет вид 0.25(x 1 )²+ (x 2 )²=1. Так как в целевую функцию ив уравнения ограничений входят две переменных векторах, те. x 1 и x 2 , то вектор х будет двухмерным (n=2). Необходимо найти экстремум J(x) при выполнении ограничений. Найдем левую часть уравнения ограничений, те. G(x) = 0.25(x 1 )²+ (x 2 )²-1. Так как уравнений ограничений имеется всего одно, то множитель λ Лагранжа будет скалярной величиной (m=1). Составим функцию Лагранжа L(x,λ)=( x 1 )² + (x 2 )²+ λ[0.25(x 1 )²+ (x 2 )²-1]. Находим частные производные и приравниваем их нулю 0 1 25 , 0 ) , ( , 0 2 5 , 0 2x 2x ) , ( 2 2 2 1 2 1 2 1 x x x L x x x x L 12 Первое уравнение системы в скалярной форме записи превращается в два уравнения 2x 1 +λ·0,5 x 1 =0 2x 2 +λ·2 x 2 =0 Откуда имеем решение x 1 *=0, которое подставляем во второе уравнение системы Лагранжа, тогда x 2 * = ± 1, λ=-2. Аналогично при x 2 *=0 имеем x 1 *=± 2, λ=-0.5. Множитель λ находим из уравнений скалярной формы записи при x 2 ≠0 и x 1 ≠0. Решение этой задачи имеет простое геометрическое построение (рис. В плоскости координат x 1 и x 2 построим уравнение ограничений G(x)=0 или 0.25(x 1 )²+ (x 2 )²=1. Нетрудно заметить, что это уравнение эллипса. Рис. Геометрическое пояснение задачи нелинейного программирования Если в целевую функцию подставить решение x 1 *=0, x 2 *=1 или x 1 *=0, x 2 *=-1, получим значение J(x*)=1. Для построения линии постоянного уровня целевой функции J(x)=Const=1 значение целевой функции приравниваем 1, те. (x 1 )² + (x 2 )²=1. Получаем уравнение окружности с радиусом, равным единице. Видно, что эта окружность вписывается в эллипс ограничений. Если в целевую функцию подставить решение x 1 *=2, x 2 *=0 или x 1 *=-2, x 2 *=0, получим значение J(x*)=4. Для построения линии постоянного уровня целевой функции J(x)=Const=4 значение целевой функции приравниваем 4, те. (x 1 )² + (x 2 )²=4. Получаем уравнение окружности с радиусом, равным двум. Видно, что эта окружность описывает эллипс ограничений. Координаты оптимального векторах определяют точки касания описанной и вписанной геометрических фигур целевой функции относительно фигуры ограничения. Если нет ограничений, то минимум J(x)=0, и линия постоянного уровня представляет собой точку вначале координат. При |