Метод множителей Лангранжа

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

Пусть требуется найти экстремум функции , которая зависит от n переменных, связанных в свою очередь отношениями . Достигаемый функцией экстремум с учетом выполнения условий называется относительным, или условным. Если же число переменных равно числу соотношений ( ), то искомые неизвестные находятся решением системы уравнений, описываемых соотношениями . Решение задачи оптимизации сводится к проверке найденным таким способом значений переменных на функции . Таким образом, экстремальную задачу можно решить простым перебором переменных, удовлетворяющих условиям .

Если m < n, то можно из уравнений связи найти зависимость m переменных от n - m остальных переменных, т.е.

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

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

,

т.е. функцию m + n переменных, в которую ограничения, накладываемые системой функций входят как составная часть.

Экстремальное значение функции совпадает с экстремальным значением функции , если выполняется условие по ограничениям . Необходимым условием экстремума функции многих переменных является равенство нулю дифференциала этой функции в экстремальной точке, т.е.

.

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

(1)

При этом новых независимых определяются из условия

(2)

Объединение систем (6.1.1) и (6.1.2) можно получить

(3)

Таким образом, задача в форме (3) сводится к задаче: найти

(4)

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

· Основной метод решения задачи об оптимизации качества кодирования аудио и видео информации при заданном среднем битрейте (оптимизация искажений — англ. Rate-Distortion optimization).

. Метод Гомори решения задачи целочисленного программирования

Метод Гомори. Нахождение решения задачи целочисленного программирования методом Гомори начинают с определения симплексным методом оптимального плана задачи (78) – (80) без учета целочисленности переменных. После того как этот план найден, просматривают его компоненты. Если среди компонент нет дробных чисел, то найденный план является оптимальным планом задачи целочисленного программирования (78) – (81). Если же в оптимальном плане задачи (78) – (80) переменная принимает дробное значение, то к системе уравнений (79) добавляют неравенство

(82)

и находят решение задачи (78) – (80), (82).

В неравенстве (82) и – преобразованные исходные величины и значения которых взяты из последней симплекс–таблицы, а и – дробные части чисел (под дробной частью некоторого числа а понимается наименьшее неотрицательное число b такое, что разность между а и b есть целое). Если в оптимальном плане задачи (78) – (80) дробные значения принимают несколько переменных, то дополнительное неравенство (82) определяется наибольшей дробной частью.

Если в найденном плане задачи (78) – (80), (82) переменные принимают дробные значения, то снова добавляют одно дополнительное ограничение и процесс вычислений повторяют. Проводя конечное число итераций, либо получают оптимальный план задачи целочисленного программирования (78) – (81), либо устанавливают ее неразрешимость.

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

(83)

где определяются из следующих соотношений:

1) для , которые могут принимать нецелочисленные значения,

(84)

2) для , которые могут принимать только целочисленные значения,

(85)

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

1. Используя симплексный метод, находят решение задачи (78) – (80) без учета требования целочисленности переменных.

2. Составляют дополнительное ограничение для переменной, которая в оптимальном плане задачи (78) – (80) имеет максимальное дробное значение, а в оптимальном плане задачи (78) – (81) должна быть целочисленной.

3. Используя двойственный симплекс–метод, находят решение задачи, получающейся из задачи (78) – (80) в результате присоединения дополнительного ограничения.

4. В случае необходимости составляют еще одно дополнительное ограничение и продолжают итерационный процесс до получения оптимального плана задачи (78) – (81) или установления ее неразрешимости.

Основные понятия теории игр

Теория игр занимается изучением т.н. конфликтных ситуаций, где сталкиваются интересы индивидов, партий, государств и т. п.

Как утверждал Г.Лейбниц, "...и игры заслуживают изучения; и если какой-нибудь проницательный математик посвятит себя их изучению, то получит много важных результатов, ибо нигде человек не показывает столько изобретательности, как в игре ".

Нет математической теории, которая могла бы дать алгоритм любой ре-альной игры, но существуют ситуации, подобные игровым и допускающие математический анализ.

Остановимся на классификации игр.

Интересы участников игры (игроков) могут оказаться несовпадающими и даже противоположными. В последнем случае игра называетсяантагонистической.

В игре могут участвовать два или более игроков. Случай игры с одним участником (пасьянс, управление физическим объектом и т.д.) в сущности является игрой двух лиц, где вторым участником выступает природа (судьба, рок, провидение).

Игроки могут в игре выступать каждый за себя или объединяться в группы. В последнем случае игра называется коалиционной.

Игры, в которых игроки осведомлены о состоянии своем и партнеров, а также о прошлом поведении участников игры, относятся к категории игр сполной информацией (типичные примеры - шахматы, " крестики-нолики" и т.п.). Большинство же игр протекает в условиях неполной информации, где сведения о состоянии партнеров исчерпываются лишь вероятностными характеристиками (домино, карточные игры, игры против " природы" ).

Антагонистическую игру, где выигрыш одного коллектива равен проигрышу другого, называют игрой с нулевой суммой.

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

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

Простейшими являются игры 2 лиц с нулевой суммой.

Пусть в такой игре игрок 1 имеет m выборов и игрок 2 - n выборов. Если игрок 1 делает свой i-й выбор, а игрок 2 - свой j-й выбор, то выигрыш игрока 1 (проигрыш игрока 2) равен Rij. Такая игра называется матричной и матрица R = [ R_ij / i=1..m, j=1..n ] называется матрицей выигрышей (пла-тежной матрицей).

При ведении игры игрок должен ориентироваться на оптимальную политику партнера и наказывать его за отступления от таковой.

Проведем рассуждения за игрока 1. Если Я воспользуюсь i-м выбором, мой противник для минимизации моего выигрыша сделает тот из своих выборов, который даст min R_ij. Соответственно, Я должен использовать тот выбор, который гарантирует мне выигрыш, не меньший

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

Если в матрице выигрышей существует элемент R_kl = V₁ = V₂, то говорят о наличии оптимальной политики " в пространстве чистых стратегий" и оптимальными выборами для игроков соответственно являются выборы k и l. Пару (k, l) называют седловой точкой.

Пример 1. Пусть игра определяется матрицей

Седловые точки - (4, 1) и (4, 2). Цена игры = 6; оптимальный выбор для игрока 1 - четвертый, для игрока 2 равнозначны первый и второй (под ценой игры понимают гарантированный выигрыш-проигрыш при оптимальной политике обоих игроков).

Пример 2. Пусть игра определяется матрицей

Здесь равенство V₁ = V₂ не выполняется; оптимальной чистой стратегии для игроков нет.

При анализе игр часто прибегают к попыткам обнаружить доминирование между строками и столбцами. Так в примере 1 элементы четвертой строки больше элементов других строк: использование выбора 4 выгоднее других выборов при любой политике противника. Противник видит, что в такой ситуации использовать выборы 3 и 4 неразумно.

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

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

Если игрок 1 прибегает к своему выбору i с вероятностью P_i, а игрок 2 - к своему j-му выбору с вероятностью Q_j, то ожидаемый выигрыш игрока 1 (проигрыш игрока 2) равен

Основная теорема теории игр (теорема Джона фон Неймана) утверждает, что любая матричная игра с нулевой суммой всегда имеет седловую точку, т.е. существуют векторы P и Q такие, что

(V - цена игры).

Платежная матрица

По словам Н. Пола Лумбы: «Платеж представляет собой денежное вознаграждение или полезность, являющиеся следствием конкретной стратегии в сочетании с конкретными обстоятельствами. Если платежи представить в форме таблицы (или матрицы), мы получаем платежную матрицу», как показано на 8.4, Слова «в сочетании с конкретными обстоятельствами» очень важны, чтобы понять, когда можно использовать платежную матрицу и оценить, когда решение, принятое на ее основе, скорее всего будет надежным. В самом общем виде матрица означает, что платеж зависит от определенных событий, которые фактически свершаются. Если такое событие или состояние природы не случается на деле, платеж неизбежно будет иным.

В целом платежная матрица полезна, когда:

1. Имеется разумно ограниченное число альтернатив или вариантов стратегии для выбора между ними.

2. То, что может случиться, с полной определенностью не известно.

3. Результаты принятого решения зависят от того, какая именно выбрана альтернатива и какие события в действительности имеют место.

Платежная матрица. Нижняя и верхняя
цена игры.

Оглавление | Назад | Далее| Глоссарий понятий

Рассмотрим парную конечную игру. Пусть игрок А располагает m личными стратегиями, которые обозначим A₁, A₂, ..., A_m. Пусть у игрока В имеется n личных стратегий, обозначим их B₁, B₂, ..., B_m. Говорят, что игра имеет размерность m × n. В результате выбора игроками любой пары стратегий

A_i и B_j (i = 1, 2, ..., m; j = 1, 2, ..., n)

однозначно определяется исход игры, т.е. выигрыш a_ij игрока А (положительный или отрицательный) и проигрыш ( - a_ij ) игрока В. Предположим, что значения о, у известны для любой пары стратегий (A_i, B_j ). Матрица P = (a_ij ), i = 1, 2, ..., m; j = 1, 2, ..., n, элементами которой являются выигрыши, соответствующие стратегиям A_i и B_j , называется платежной матрицей или матрицей игры. Общий вид такой матрицы представлен в таблице 3.1.

Таблица 3.1

Строки этой таблицы соответствуют стратегиям игрока А, а столбцы — стратегиям игрока В. Составим платежную матрицу для следующей игры.

Седлова точка

Седловая точка в математическом анализе — такая точка из области определения функции, которая является стационарной для данной функции, однако не является её локальным экстремумом. В такой точке, если рассматривается функция двух переменных, образованная графиком функцииповерхность обычно напоминает по форме седло или горный перевал — выпуклая в одном направлении и вогнутая в другом. На карте высот седловая точка может быть в общем случае обнаружена в месте пересечения изолиний. Например, два холма, между которыми находится высокий перевал, образуют седловую точку в вершине этого перевала: на карте высот это будет выглядеть как центр «восьмерки», образованной соответствующими изолиниями. Проверить, является ли данная стационарная точка функции F(x, y) двух переменных седловой, можно, вычислив матрицу Гессе функции в этой точке: если гессиан будет неопределенной квадратичной формой, то данная точка — седловая. Например, составив матрицу Гессе функции в стационарной точке получим матрицу:

которая является неопределенной. Поэтому, точка данной функции — седловая. Однако вышеприведенный критерий предоставляет только достаточное условие наличия седловой точки. Например, является седловой точкой функции , но матрица Гессе в данном случае будет нулевой матрицей, которую, по определению, нельзя назвать неопределенной.

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

График y = x³ с седловой точкой в 0

В случае функции одной переменной, седловая точка — такая точка, которая одновременно является и стационарной точкой, и точкой перегиба (точка перегиба не является локальным экстремумом).!

⇐ Предыдущая3456789101112Следующая ⇒

Поделиться: