Дайте определение методы оптимизации теория игр оптимальное решение Оптимизация

3 - оптимальное решение

Общая запись задач оптимизации задаёт большое разнообразие их классов. От класса задачи зависит подбор метода (эффективность её решения). Классификацию задач определяют: целевая функция и допустимая область (задаётся системой неравенств и равенств или более сложным алгоритмом).

Методы оптимизации классифицируют в соответствии с задачами оптимизации:

• 
  Локальные методы: сходятся к какому-нибудь локальному экстремуму целевой функции. В случае унимодальной целевой функции, этот экстремум единственен, и будет глобальным максимумом/минимумом.
  
• 
  Глобальные методы: имеют дело с многоэкстремальными целевыми функциями. При глобальном поиске основной задачей является выявление тенденций глобального поведения целевой функции.
  

1. 
   детерминированные;
   
2. 
   случайные (стохастические);
   
3. 
   комбинированные.
   

По виду целевой функции и допустимого множества, задачи оптимизации и методы их решения можно разделить на следующие классы:

• 
  Задачи оптимизации, в которых целевая функция f ( x → ) {\displaystyle f({\vec {x}})} и ограничения g i ( x → ) , i = 1 , … , m {\displaystyle g_{i}({\vec {x}}),\;i=1,\ldots ,m} являются линейными функциями, разрешаются так называемыми методами линейного программирования.
  
• 
  В противном случае имеют дело с задачей нелинейного программирования и применяют соответствующие методы. В свою очередь из них выделяют две частные задачи:
  
  • 
    если f ( x → ) {\displaystyle f({\vec {x}})} и g i ( x → ) , i = 1 , … , m {\displaystyle g_{i}({\vec {x}}),\;i=1,\ldots ,m}  — выпуклые функции, то такую задачу называют задачей выпуклого программирования;
    
  • 
    если X ⊂ Z {\displaystyle \mathbb {X} \subset \mathbb {Z} } , то имеют дело с задачей целочисленного (дискретного) программирования.
    

• 
  прямые методы, требующие только вычислений целевой функции в точках приближений;
  
• 
  методы первого порядка: требуют вычисления первых частных производных функции;
  
• 
  методы второго порядка: требуют вычисления вторых частных производных, то есть гессиана целевой функции.
  

• 
  аналитические методы (например, метод множителей Лагранжа и условия Каруша — Куна — Таккера);
  
• 
  численные методы;
  
• 
  графические методы.
  

• 
  задачи дискретного программирования (или комбинаторной оптимизации) — если X конечно или счётно;
  
• 
  задачи целочисленного программирования — если X является подмножеством множества целых чисел;
  
• 
  задачи нелинейного программирования, если ограничения или целевая функция содержат нелинейные функции и X является подмножеством конечномерного векторного пространства.
  
• 
  Если же все ограничения и целевая функция содержат лишь линейные функции, то это — задача линейного программирования.
  

Математическое программирование используется при решении оптимизационных задач исследования операций.

Способ нахождения экстремума полностью определяется классом задачи. Но перед тем, как получить математическую модель, нужно выполнить 4 этапа моделирования:

• 
  Определение границ системы оптимизации
  
  • 
    Отбрасываем те связи объекта оптимизации с внешним миром, которые не могут сильно повлиять на результат оптимизации, а, точнее, те, без которых решение упрощается
    
• 
  Выбор управляемых переменных
  
  • 
    «Замораживаем» значения некоторых переменных (неуправляемые переменные). Другие оставляем принимать любые значения из области допустимых решений (управляемые переменные)
    
• 
  Определение ограничений на управляемые переменные
  
  • 
    … (равенства и/или неравенства)
    
• 
  Выбор числового критерия оптимизации (например, показателя эффективности)
  
  • 
    Создаём целевую функцию
    

Определения. Классификация игр. Решение игр в чистых и смешанных стратегиях. Теорема Неймана

Обычно математики для изучения конфликтных ситуаций. Позволяющий вырабо­тать оптимальные правила поведения каждой стороны.В экономике, например, оказался недостаточным аппарат ма­тематического анализа, занимающийся определением экстрему­мов функций. Появилась необходимость изучения так называе­мых оптимальных минимаксных и максиминных решений. Сле­довательно, теорию игр можно рассматривать как новый раздел оптимизационного подхода, позволяющего решать новые задачи при принятии решений.

Игра- упрощенная формализованная модель реальной кон­фликтной ситуации. Математически формализация означает, что выработаны определенные правила действия сторон в процессе игры: варианты действия сторон; исход игры при данном вари­анте действия; объем информации каждой стороны о поведении всех других сторон.

Выигрыш или проигрыш сторон оценивается численно, дру­гие случаи в теории игр не рассматриваются, хотя не всякий выигрыш в действительности можно оценивать количественно.

Игрок - одна из сторон в игровой ситуации. Стратегия иг­рока - его правила действия в каждой из возможных ситуаций игры. Существуют игровые системы управления, если процесс управления в них рассматривается как игра.

Платежная матрица(матрица эффективности, матрица игры) включает все значения выигрышей (в конечной игре). Пусть игрок 1 имеет стратегий , а игрок 2 – стратегий . Игра может быть названа игрой . Представим мат­рицу эффективности игры двух лиц с нулевой суммой.
В данной матрице элементы – значения выигрышей игро­ка 1 – могут означать и математическое ожидание выигрыша (среднее значение), если выигрыш является случайной величи­ной. Величины – соответственно мини­мальные значения элементов , по строкам и максимальные - по столбцам.

Количество игроков. Если в игре участвуют две сто­роны, то ее называют игрой двух лиц. Если число сторон больше двух, ее относят к игре п игроков. Наибольший интерес вызыва­ют игры двух лиц.

Классификация игр.

Количество стратегий игры. По этому критерию игры делятся на конечные и бесконечные. В конечной игре каж­дый из игроков имеет конечное число возможных стратегий. Если хотя бы один из игроков имеет бесконечное число возможных стратегий, игра является бесконечной.

Взаимоотношения сторон. Согласно данному кри­терию игры делятся на кооперативные, коалиционные и бескоа­лиционные. Если игроки не имеют право вступать в соглашения, образовывать коалиции, то такая игра относится к бескоалицион­ным; если игроки могут вступать в соглашения, создавать коали­ции - коалиционной. Кооперативная игра - это игра, в которой заранее определены коалиции.

Характер выигрышей. Этот критерий позволяет клас­сифицировать игры снулевой и с ненулевой суммой. Игра с ну­левой суммой предусматривает условие: «сумма выигрышей всех игроков в каждой партии равна нулю». Игры двух игроков с нулевой суммой относят к классу антагонистических. Естествен­но, выигрыш одного игрока при этом равен проигрышу другого. Примерами игр с нулевой суммой служат многие экономические задачи. В них общий капитал всех игроков перераспределяется между игроками, но не меняется. К играм с ненулевой суммой также можно отнести большое количество экономических задач. Например, в результате торговых взаимоотношений стран, уча­ствующих в игре, все участники могут оказаться в выигрыше. Игра, в которой нужно вносить взнос за право участия в ней, является игрой с ненулевой суммой.

Вид функции выигрышей. По этому критерию игры подразделяются на:

Матричная игра - конечная игра двух игроков с нулевой суммой. В общем случае ее платежная матрица является прямо­угольной (см. табл. 2.1). Номер строки матрицы соответствует номеру стратегии, применяемой игроком 1. Номер столбца соот­ветствует номеру стратегии игрока 2. Выигрыш игрока 1 являет­ся элементом матрицы. Выигрыш игрока 2 равен проигрышу игрока 1. Как показано в приложении, матричные игры всегда имеют решения в смешанных стратегиях. Они могут быть реше­ны методами линейного программирования.

Биматричная игра- конечная игра двух игроков с ненулевой суммой. Выигрыши каждого игрока задаются своей матрицей, в которой строка соответствует стратегии игрока 1, а столбец — стратегии игрока 2. Однако элемент первой матрицы показывает выигрыш игрока 1, а элемент второй матрицы - выигрыш игро­ка 2. Для биматричных игр так же, как и для матричных, разра­ботана теория оптимального поведения игроков.

Если функция выигрышей каждого игрока в зависимости от стратегий является непрерывной, игра считается непрерывной. Если функция выигрышей выпуклая, то и игра - выпуклая.

Если функция выигрышей может быть разделена на сумму произведений функций одного аргумента; то игра относится к сепарабельной.

Количество ходов. Согласно этому критерию игры можно разделить на одношаговые и многошаговые. Одношаго­вые игрызаканчиваются после одного хода каждого игрока. Так, в матричной игре после одного хода каждого из игроков проис­ходит распределение выигрышей. Многошаговые игры бывают позиционными, стохастическими, дифференциальными и др.

Информированность сторон. По данному крите­рию различают игры с полной и неполной информацией. Если каждый игрок на каждом ходу игры знает все ранее приме­ненные другими игроками на предыдущих ходах стратегии, такая игра определяется какигра с полной информацией. Если игроку не все стратегии предыдущих ходов других игроков известны, то игра классифицируетсякак игра с неполной ин­формацией. Мы далее убедимся, что игра с полной информа­цией имеет решение. Решением будет седловая точкапри чистых стратегиях.

Степень неполноты и формации. По этому кри­терию игры подразделяются на статистические (в условиях час­тичной неопределенности) и стратегические (в условиях полной неопределенности). Игры с природой часто относят к статистическим играм. В статистической игре имеется возможность получения информации на основе статис­тического эксперимента, при котором вычисляется или оценива­ется распределение вероятностей состояний (стратегий) приро­ды. С теорией статистических игр тесно связана теория приня­тия экономических решений.

Минимакс. Максимин.

Рассмотрим матричную игру, представленную матрицей вы­игрышей где число строк , а число столбцов (см. табл. выше). Применим принцип получения максимального га­рантированного результата при наихудших условиях. Игрок 1 стремится принять такую стратегию, которая должна обеспечить максимальный проигрыш игрока 2. Соответственно игрок 2 стре­мится принять стратегию, обеспечивающую минимальный вы­игрыш игрока 1. Рассмотрим оба этих подхода.

Подход игрока 1.Он должен получить максимальный гарантированный результат при наихудших условиях. Значит, при выборе отвечающей этим условиям своей чистой страте­гии он должен выбрать гарантированный результат в наихудших условиях, т.е. наименьшее значение своего выигрыша а,. Обозначим: . Чтобы этот гарантированный эффект в наихудших условиях был максимальным, нужно из всех а, выбрать наибольшее зна­чение. Обозначим его α и назовем чистой нижней ценой игры(«максимин»): . Таким образом, максиминной стратегии отвечает строка мат­рицы, которой соответствует элемент . Какие бы стратегии ни применял игрок 2, игрок 1 максиминной чистой стратегией га­рантировал себе выигрыш, не меньший, чем . Таково оптималь­ное поведение игрока 1.

Подход игрока 2. Своими оптимальными стратегиями он стремится уменьшить выигрыш игрока 1, поэтому при каж­дой j-й чистой стратегии он отыскивает величину своего макси­мального проигрыша: . в каждом j-м столбце, т.е. определяет максимальный выигрыш игрока 1, если игрок 2 применит j-ю чистую стратегию. Из всех своих nj-х чистых стратегий он отыскивает такую, при которой игрок 1 получит минимальный выигрыш, т.е. определяет чистуюверхнюю цену игры(«минимакс»): . Чистая верхняя цена игры показывает, какой максимальный выигрыш может гарантировать игрок 1, применяя свои чистые стратегии, - выигрыш, не меньший, чем a. Игрок 2 за счет ука­занного выше выбора своих чистых стратегий не допустит, что­бы игрок 1 мог получить выигрыш, больший, чем b. Таким об­разом, минимаксная стратегия отображается столбцом платеж­ной матрицы, в котором находится элемент b (см. табл. 2.1). Она является оптимальной чистой гарантирующей стратегией игро­ка 2, если он ничего не знает о действиях игрока 1.

Чистая цена игры v - цена данной игры, если нижняя и вер­хняя ее цены совпадают: . В этом случае игра называется игрой с седловой точкой.