Опорный конспект лекции дисциплины «Методы оптимизации и исследование операции» (стр. 4 )

Метод решения в целом состоит из последовательности шагов перечисленных двух типов. Поскольку на шаге В) число элементов в множестве I возрастает, то между двумя соседними шагами типа А) может располагаться лишь конечное число шагов типа В).

С другой стороны, для конечного шага типа А) значение функции в точке однозначно определяется множеством I , и если окажется, что от одного шага к другому функция строго убывает, то одно и то же множество I на шагах типа А) не может встретиться дважды, и окажется конечным.

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

Пример: (13)

Начав с точки (0,0), что соответствует и системе мы совершаем шаг типа А), т. к. наша грань состоит из - той точки и в точке (0,0) тривиально достигается минимум функции . Так как в нашем случае

С=

то из (8), находим, что , так что оба индекса в I можно взять в качестве . Пусть =1 и переход к следующему шагу с =(0,0) и . Теперь система (7) будет состоять из уравнения и множество её решений будет совпадать с осью абсцисс. Минимум функции достигается в точке (3/4, 0), удовлетворяет системе ограничений. Поэтому в результате шага типа В) мы сместимся в эту точку, сохранив . В результате следующим снова оказывается шаг типа А), причём система (8) принимает вид

отсюда и следует положить

К следующему шагу переходим с и Æ. В соответствии с этим минимум функции нужно искать на всей плоскости и поэтому (3/4,3/4) . Однако точка не удовлетворяет третьему ограничению. Поэтому двигаясь по направлению к ней, определим z=(0,3/4) и при =1/3 перейдём к точке (3/4,1/4) и множеству .

Снова должен совершить шаг типа В), поскольку точка =(1/2,1/2) на множестве решения уравнения не совпадает с . Поскольку, однако, эта точка является допустимой, то окажется, что =1 и мы получим решение задачи (1/2,1/2) .

Численные методы для задачи выпуклого программирования:

1) Метод условного градиента.

2) Метод проекции градиента.

3) Метод возможного направления.

Динамическое программирование.

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

Будем рассматривать задачи оптимального управления на примере управляемого объекта, поведение которого описывается системой обыкновенных дифференциальных уравнений:

(5.1)

j (0) = j0 ,

где

j = {j1 , …,jn}, f = {f1 , …,fn}, u = {u1 , …,um}.

Допустимыми управлениями будем считать произвольные кусочно-непрерывные измеримые функции u = u(t), принимающие значения из замкнутой области UÌ Em.

В классе допустимых управлений требуется найти такое управление u(t) и соответствующее ему решение j(t) задачи (5.1), чтобы функционал

J[u]== (5.2)

При этом предполагается, что каждое допустимое управление определяет единственное решение задачи (5.1).

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

Оптимальное управление в любой момент времени не зависит от предыстории системы и определяется только целью управления и состоянием системы в этот момент времени.

Если ввести обозначение

Q(j, t)=, (5.3)

То из принципа оптимальности имеем

Q(j(t), t)=, (5.4)

Второе слагаемое в скобках, по определению, есть , где .

Предполагая, что возможно разложение обоих членов в скобках по формуле Тейлора и устремляя затем ∆t→0, получим из (5.4) уравнение в частных производных (уравнение Беллмана):

(5.6)

Q(j,T)=0.

Пусть минимум в правой части (5.6) достигается лишь в единственной точке u*ÎU, тогда u*есть функция от j и :

u*= u*( j, ). (5.7)

Подставляя эту функцию в уравнение (5.6) будем иметь нелинейную систему уравнений

(5.8)

Если считать u* некоторой функцией j, t, то система (5.8) будет гиперболической системой уравнений, характеристики которой направлены от t=0 к t=Т. Строгое обоснование метода динамического программирования, применительны к непрерывным задачам оптимального управления, было дано , получившим необходимое и достаточное условие оптимальности в терминах Q(j, t).

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

i=0,1,….,N-1 (5.9)

Здесь ji ÎЕn – n-мерный вектор состояния, uiÎЕm – m-мерный вектор управления.

Разностное уравнение (5.9) могут возникать из физического описания процесса, так и при дискретизации системы (5.1). На решениях системы требуется минимизировать функционал вида

J[u]= (5.10)

Из постановки задачи видно, что оптимальное значение функционала, если решение задачи (5.9), (5.10) существует, зависит от начального состояния j0 и числа шагов N. Обозначив это оптимальное значение через , запишем задачу минимизации следующим образом:

. (5.11)

Поскольку в силу структуры системы (5.9) изменения (u1,…,uN-1) не влияют на φ0 и выбор u0, то (5.11) можно переписать следующим образом:

(5.12)

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

(5.13)

Рассуждая аналогичным образом, получаем следующие реккурентные соотношения:

j0 – задано,

(5.14)

(5.15)

Из системы (5.14), (5.15) следует, что, считая известной и решая относительно простую задачу минимизации функции m переменных, то можем из (5.14) последовательно найти

Но поскольку система (9) определяет последовательно j1, j2,…, jN-1 , то на самом деле получается типичная для оптимального управления двухточечная краевая задача. Уравнения (14)-(15), дающие необходимые и достаточные условия оптимальности управления (u1, u2,…, uN-1 ), являются следствиями структуры системы (9) (при известных jj, uj ), решение (9) не зависит от jj-1, uj-1,…(так называемые марковские системы) и аддитивности функционала (10).

Рассмотрим на простом примере использование динамического программирования. Процесс описывается одним уравнением (16)

И требуется минимизировать функционал . Уравнение Беллмана (16) запишется следующим образом (17)

Поскольку линейная функция достигает минимума на границе отрезка, то (18)

Дискретизируем задачу (16) следующим образом (T=5, N=5, τ=T/N=1): (19)

Выражение для Q1(φΝ-1) имеет вид

Введение в теорию игр

Жить в обществе и быть свободным от общества нельзя! Живя в обществе, мы неизбежно сталкиваемся с другими людьми, и интересы различных людей практически никогда не совпадают между собой. В обществе неизбежны столкновения интересов различных людей, противоречия между этими интересами.

В художественной литературе этому столкновению интересов уделялось не меньше внимания, чем любви и Богу. Это столкновение интересов является предметом целого ряда наук  психологии, социологии, политологии. Даже экономическая наука по большому счету изучает столкновение интересов, так как конкуренция является именно таким столкновением. Но лишь в 40-е годы двадцатого века это столкновение интересов стало предметом математического исследования, прежде всего в области экономики. Первая значительная книга по теории игр  книга Дж. фон Неймана и С. Моргенштерна, изданная в 1944 году так и называлась  “Теория игр и экономическое поведение”.

Предмет оказался чрезвычайно сложным, даже для математики. И сейчас, 60 лет спустя, успехи теории игр довольно ограничены. Тем не менее, она нашла своё применение особенно в военном деле, так как война  это столкновение интересов практически в чистом виде. Организация тыла, поиски подводных лодок, противовоздушная оборона, дуэль двух противников  всё это приложение теории игр в настоящее время. В экономике теория игр также находит своё применение.

Определение теории игр

От той теории, которая существует в настоящее время, не следует ждать чудодейственных рецептов. Она не предписывает поведение, ведущее к выигрышу. Она лишь указывает, чего может добиться игрок в наихудшей для него ситуации и как он должен действовать, чтобы в этой наихудшей ситуации добиться минимального проигрыша (или максимального выигрыша). Но и это, безусловно, полезно. А рекомендации по выигрышу  дело будущей теории игр.

1. Неформальное описание игры

Всякая игра предполагает следующее:

1. Наличие некоторого числа n участвующих в ней лиц (игроков). Могут быть игры с одним игроком (пасьянс), двумя игроками игрок получает доход (если  значит, игрок проиграл), зависящий от его поведения и поведения других игроков.

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

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

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

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

2. Игры двух лиц с нулевой суммой

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

Итак, пусть имеется два игрока. В распоряжении первого игрока имеется всего n возможных ходов i=1,2,3,...,n; в распоряжении второго игрока имеется m возможных ходов j=1,2,3,...,n. Эти возможные ходы называются чистыми стратегиями игроков.

Оба игрока делают одновременно по одному ходу, после чего партия считается законченной. Если первый игрок делает ход i, а второй  ход j, то первый игрок получает выигрыш, равный . Очевидно, что выигрыш второго игрока равен .

Эти данные можно записать в виде матрицы

,

в которой строки соответствуют ходу первого игрока, а столбцы  ходу второго игрока. Эта матрица носит название платёжной матрицы игры.

Как же должны действовать игроки в такой ситуации? Какие ходы они должны делать?

3. Игры с седловой точкой

Рассмотрим с этих позиций игру со следующей платёжной матрицей

.

Попробуем порассуждать с точки зрения

Аналогично, при i=3 он в наихудшем случае получит 4 (при j=2), при i=4  2 (при j=3 ) и, наконец, при i=5 он в наихудшем случае получит 0 (при j=3).

Стремясь сделать свой гарантированный выигрыш как можно больше, первый игрок должен выбрать ход i=3, так как в этом случае он гарантирует себе выигрыш, равный 4 (правда, и его максимальный выигрыш невелик  всего 5).

А теперь попробуем посмотреть на эту же матрицу с точки зрения второго игрока. Для него это  матрица его проигрыша.

Если он выберет ход j=1, то его максимальный проигрыш будет равен 18 (если первый игрок сделает ход i=1). Аналогично, при j=2 его максимальный проигрыш будет равен 4, при j=3 8, и, наконец, при j=4 его максимальный проигрыш будет равен 25. Стремясь сделать свой максимальный проигрыш как можно меньше, второй игрок должен выбрать ход j=2, так как в этом случае его максимальный проигрыш, равный 4, самый маленький.

Итак, мы пришли к выводу, что первый игрок должен ходить i=3, а второй j=2. Допустим теперь, что второй игрок, как говорят, “открывает карты” и заявляет первому игроку: “Я буду делать ход j=2”. Есть ли первому игроку необходимость менять свой ход? Нет, так как в этом случае его наилучший ход всё равно i=3.

Аналогично, если первый игрок заявит второму, что он будет ходить i=3, то второму игроку также нет смысла менять свой ход, так как наилучшим ответом будет всё равно j=2. Пара i=3, j=2 является, как говорят, уравновешенной парой, так как “открытие карт” игроками не даёт поводов противнику менять свою стратегию. Как говорят, пара i=3, j=2 есть решение игры, а величина выигрыша при этом первого игрока (и одновременно величина проигрыша второго)  4  это цена игры.

Оформим всё это математически. Итак, пусть первый игрок выбирает ход i. В наихудшей для него ситуации он выиграет .

Стремясь сделать свой минимальный выигрыш максимальным, он выбирает свой ход из условия . Такая стратегия называется максиминной.

Аналогично, второй игрок, выбирая ход j, в наихудшей для себя ситуации проигрывает . Стремясь сделать свой максимальный проигрыш минимальным, он должен выбирать свой ход из условия . Такая стратегия называется минимаксной. Каково же соотношение между и ?

Теорема 1. Пусть имеются два числовых множества и ; есть вещественная функция двух переменных при и . Тогда , если и существуют.