Вопрос 26. Формулировка задачи Больца. Принцип максимума как распространение метода множителей Лагранжа на решение задачи Больца

Динамическая задача – это задача распределения ограниченных ресурсов для достижения комплекса конкурирующих целей на протяжении некоторого промежутка времени от начального момента до конечного. Сформулируем эту задачу в математических терминах. Рассмотрим некоторые переменные величины, называемые управляющими параметрами. Задано некоторое множество функций времени, называемое множеством управления (control set). Задача состоит в выборе управляющих параметров как функций времени, принадлежащих множеству управлений. Выбранные функции времени в свою очередь определяют, какой вид имеют функции времени некоторых других переменных, с помощью которых описывается поведение системы. Эти переменные называют фазовыми координатами. Значения фазовых координат в каждый момент времени выбираются таким образом, чтобы максимизировать заданный целевой функционал, зависящий от фазовых координат и управляющих параметров (и те, и другие рассматриваются как функции времени). Функции времени для управляющих параметров и для фазовых координат связаны с помощью системы дифференциальных уравнений, называемых уравнениями движения. Задача, представленная в указанной форме, называется задачей управления.

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

Время t измеряется как непрерывная величина. Предполагается, что t изменяется в некотором фиксированном промежутке: от начального момента t₀, который обычно известен, до конечного момента t₁, который часто требуется определить. Следовательно, время задано на промежутке

. (11.1.1)

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

x (t) = , (11.1.2)

называемый фазовым вектором (фазовой точкой), можно геометрически интерпретировать как точку в n-мерном евклидовом пространстве Eⁿ. Каждая фазовая координата считается непрерывной функцией времени, поэтому фазовая траектория

{x (t)} = {x (t) } (11.1.3)

представляет собой непрерывную вектор-функцию времени, значениями которой в каждый момент времени t из указанного промежутка являются фазовые векторы (11.1.2). С геометрической точки зрения фазовая траектория представляет собой некоторую кривую, состоящую из точек пространства Eⁿ. Началом этой кривой является фиксированное начальное состояние

x (t₀) = x₀, (11.1.4)

а окончанием – конечное состояние

x (t₁) = x₁, (11.1.5)

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

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

u (t) = , (11.1.6)

называемый управляющим вектором, можно интерпретировать геометрически как точку в E^r. Управлением («траекторией управления») называется функция

{u (t)} = {u (t) }. (11.1.7)

Требуется, чтобы каждый управляющий параметр являлся кусочно-непрерывной функцией времени. Поэтому управление представляет собой кусочно-непрерывную функцию времени. Значениями этой функции в каждый данный момент времени t из указанного промежутка являются управляющие векторы (11.1.6). С геометрической точки зрения управление представляет собой некоторую кривую, состоящую из точек пространства, причем эта кривая непрерывна всюду, за исключением, возможно, некоторого конечного числа точек разрыва второго рода.

Предполагается, что возможные значения управляющих параметров удовлетворяют некоторым ограничениям. Эти ограничения в общей форме состоят в том, что управляющий вектор в каждый момент времени из интервала должен принадлежать некоторому фиксированному непустому подмножеству Ω r-мерного евклидова пространства

u (t) . (11.1.8)

Обычно предполагается, что множество Ω является выпуклым и компактным (т.е. замкнутым и ограниченным) и что оно инвариантно относительно времени. Управление (11.1.7) называется допустимым, если оно представляет собой кусочно-непрерывную вектор-функцию времени, значения которой в любой момент времени из указанного интервала принадлежат Ω. Множество управлений U – это множество всех допустимых управлений, т.е. таких управлений, которые являются кусочно-непрерывными функциями времени, заданными в промежутке , значения которых в любой момент из указанного промежутка принадлежат Ω. Управление должно принадлежать указанному множеству управлений, т.е.

{u (t)} . (11.1.9)

Фазовая траектория {x (t)} определяется из уравнений движения, т.е. из системы дифференциальных уравнений, в которых скорость изменения каждой фазовой координаты представлена в виде функции фазовых координат, управляющих параметров и времени

(t) = f (x (t), u (t), t), (11.1.10)

или в развернутом виде

(11.1.11)

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

= Ax + Bu, (11.1.12)

где А – фиксированная матрица размерности , а В – фиксированная матрица размерности .

Фиксированные начальные значения фазовых координат (11.1.4) являются граничными условиями для уравнений движения. Если заданы эти начальные значения и управление {u (t)}, то существует единственная фазовая траектория {x (t)}, удовлетворяющая уравнениям движения и граничным условиям. Эту траекторию можно найти интегрированием дифференциальных уравнений при данных начальных условиях x (t₀) = x₀. Фазовая траектория, найденная в результате решения уравнений движения при данном начальном состоянии с использованием допустимого управления, называется допустимой, а любая фазовая точка на фазовой траектории, которую можно достичь за конечное время, называется достижимой.

Конечный момент времени t₁ определяется условием

(x (t), t) при t = t₁, (11.1.13)

где T – заданное подмножество в Eⁿ⁺¹, называемое конечной поверхностью.

Важными частными случаями задачи управления являются задача с фиксированным временем, когда конечный момент времени t₁ задан в явной форме как параметр задачи, и задача с фиксированным конечным моментом времени, когдаx (t₁) задан в явной форме как вектор параметров задачи.

Целевой функционал, максимум которого требуется найти, представляет собой отображение управлений (функций времени) на точки вещественной прямой. Этот функционал будет рассматриваться, как правило, в следующей форме:

J = J {u (t)} = (x (t), u (t), t)dt + F (x₁, t₁). (11.1.14)

Подынтегральная функция I (…) показывает, что функционал зависит от фазовых координат и управляющих параметров, являющихся функциями времени, и от времени, т.е.

I (x, u, t) = , (11.1.15)

где .

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

F (x₁, t₁) = . (11.1.16)

Предполагается, что как I (…), так и F (..) являются фиксированными непрерывно дифференцируемыми функциями. Целевой функционал записан в (11.1.14) как функционал, зависящий от управлений, потому что если вектор-функция f (…) и вектор x₀ заданы, то управление {u (t)} определяет фазовую траекторию {x (t)}.

Задачу с целевым функционалом такого вида, как в (11.1.14), обычно называют задачей Больца.

Принцип максимума применяется к общей задаче управления, имеющей вид

= (x, u, t)dt + F (x₁, t₁)

= f (x, u, t),

x (t₀) = x₀, (14.0.1)

x (t₁) = x₁,

{u (t)} .

Здесь I (…), F (..) и f (…) – заданные непрерывно дифференцируемые функции; t₀, x₀ – фиксированные параметры; t₁ или x₁ – фиксированные параметры (либо с помощью уравнения T (x, t) = 0 определяется конечная поверхность). Траектория управления {u (t)} должна принадлежать фиксированному множеству управлений U, причем u (t) – кусочно-непрерывная функция времени, значения которой должны принадлежать некоторому фиксированному множеству Ω, являющемуся непустым компактным подмножеством пространства E^r.

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

J = (x, u, t)dt + F (x₁, t₁), (14.1.1)

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

f (x, u, t) – (t) = 0, . (14.1.2)

Введем вектор (вектор-строку) новых переменных – по одной переменной для каждого из n ограничений

y (t) = . (14.1.3)

Эти новые переменные, называемые сопряженными переменными, представляют собой динамические эквиваленты множителей Лагранжа в статических задачах максимизации при наличии ограничений. Так как каждая из сопряженных переменных соответствует одному из дифференциальных уравнений движения, определенных на промежутке времени от t₀ до t₁, то и сопряженные переменные, вообще говоря, зависят от времени, что и отмечено в (14.1.3), причем предполагается, что эти переменные являются ненулевыми непрерывными функциями времени.

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

L = J + [f (x, u, t) – ]dt = {I (x, u, t) + y[f (x, u, t) – ]} + F (x₁, t₁). (14.1.4)

Седловая точка лагранжиана определяет решение. В данном случае седловая точка принадлежит пространству функций. Точка ({u*(t)}, {y*(t)}) представляет собой седловую точку в том случае, если

L ({u(t)}, {y*(t)}) L ({u*(t)}, {y*(t)}) L ({u*(t)}, {y(t)}). (14.1.5)

Тогда траектория управления {u*(t)} является решением задачи управления.

В самом деле, второе неравенство

y* – y)[f (x*, u*, t) – x*]}dt 0 (14.1.6)

выполняется для всех непрерывных функций {y(t)} только тогда, когда

* = f (x*, u*, t). (14.1.7)

Действительно, в противном случае можно было бы взять такую функцию {y(t)}, значения которой в тех точках, где это равенство не выполняется, подобраны с учетом того, чтобы интеграл в 14.1.6 был больше нуля. Следовательно, оптимальная траектория удовлетворяет уравнениям движения. С другой стороны, первое из неравенств 14.1.5 показывает, что

J {u*(t)} J {u(t)} + y*[f (x, u, t) – ]}dt. (14.1.8)

Следовательно, при всех траекториях {u(t)}, удовлетворяющих уравнениям движения, выполняется неравенство

J {u*(t)} J {u(t)}, (14.1.9)

и, следовательно, {u*(t)} является оптимальной траекторией. Оптимальное значение целевого функционала равно значению функции Лагранжа в седловой точке.

Рассмотрим теперь необходимые условия для существования такой седловой точки. Из (14.1.4) следует, что переход от сопряженных переменных у (t) к {y (t) + Δy (t)}, где Δy (t) – произвольная непрерывная функция времени, изменит функцию Лагранжа на

ΔL = y[f (x, u, t) – ]dt. (14.1.10)

Так как необходимое условие первого порядка для существования минимума L относительно {у (t)} требует, чтобы ΔL = 0, то, согласно основной лемме вариационного исчисления, должны выполняться уравнения движения, т.е.

=f (x, u, t). (14.1.11)

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

Выведем теперь остальные необходимые условия.

Отметим, что если в (14.1.4) проинтегрировать по частям выражение у (t) (t), то L преобразуется к виду

L = (x, y, t) + yf (x, u, t) + х}dt + F (x₁, t₁) – [у (t₁) x (t₁) – у (t₀) x (t₀)]. (14.1.12)

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

H (x, u, y, t) = I (x, u, t) + yf (x, y, t). (14.1.13)

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

L = (x, u, y, t) + х}dt + F (x₁, t₁) – [у (t₁) x (t₁) – у (t₀) x (t₀)]. (14.1.14)

Исследуем теперь, каков результат перехода от траектории управления {u (t)} к траектории управления {u (t) + Δu (t)} и соответствующего перехода с фазовой траектории {x (t)} на фазовую траекторию {x (t) + Δx (t)}. При этом

ΔL = , (14.1.15)

где

. (14.1.16)

Так как для существования максимума необходимо, чтобы приращение лагранжиана ΔL обращалось в ноль, и поскольку (14.1.15) должно выполняться при любых {Δu (t)}, то

, (14.1.17)

, (14.1.18)

. (14.1.19)

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

(x, u, y, t) при всех t, , (14.1.20)

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

, (14.1.21)

либо максимум достигается на границе. В последнем случае, как в нелинейном программировании,

, (14.1.22)

где n – вектор нормали к границе области Ω.

Необходимые условия (14.1.18) и (14.1.19) представляют собой соответственно дифференциальные уравнения и граничные условия для сопряженных переменных. Дифференциальные уравнения показывают, что скорость изменения каждой из сопряженных переменных равняется частной производной функции Гамильтона по соответствующей фазовой координате, взятой со знаком минус. Граничные условия показывают, что конечное значение каждой из сопряженных переменных равно частной производной функции F (x, t) по соответствующей фазовой координате.

Используя функцию Гамильтона, можно представить дифференциальные уравнения для фазовых координат, т.е. уравнения движения, в виде

. (14.1.23)

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

, x (t₀) = x₀

, . (14.1.24)

Эта система состоит из 2n дифференциальных уравнений, на одну половину которых наложены граничные условия, заданные в начальный момент, а для оставшихся n уравнений граничные условия заданы в конечный момент.

Рассмотрим теперь, как функция Гамильтона изменяется во времени. Так как H = H (x, u, y, t), то

. (14.1.25)

Преобразуем это выражение, используя уравнения движения

. (14.1.26)

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

. (14.1.27)

В частности, если задача является автономной, т.е. если I (…) и f (…) не зависят явно от времени, то и гамильтониан не зависит явно от времени и, следовательно, функция Гамильтона постоянна во времени в точках оптимальных траекторий, так как dH/dt = 0.

Итак, при решении задачи с помощью принципа максимума сначала вводятся n сопряженных переменных y (t) и определяется функция Гамильтона

H (x, u, y, t) = I (x, u, t) + yf (x, y, t). (14.1.28)

Затем отыскиваются функции {u (t)}, {у (t)} и {x (t)}, удовлетворяющие следующим условиям:

(x, u, y, t) при всех t, ,

, x (t₀) = x₀ (14.1.29)

, .

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

Вопрос 27: основные понятия теории линейного программирования. Теоретические основы симплекс-метода.

Задача ЛП – однокритериальная задача условной (с ограничениями) оптимизации с линейным функционалом и линеными ограничениями.

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

Графический метод решения задач.

Тут нужен любой пример. В лекциях была такая задача:

«Полезные выводы», которые надо делать на основе графического решения:

1. решение задачи ЛП находится на границе допустимого множества;

2. множеством решений может быть: ø, точка, отрезок, луч, прямая.

3. Если решение достигается, то это присходит в одной крайних точек.

В силу конечности крайних точек, задача сводится к их перебору.

4. Хотелось бы от общего перебора перейти к направленному, например, с постоянным улучшением функционала.

Можно предложить геометрические наброски для организации подобного: рассматривать углы между и ребрами. Если нет острого, то крайняя точка – решение.

Во всех случаях задача ЛП сводится к стандартной по форме записи:

.

Все взаимосвязи носят линейный характер.

m – количество ограничений, n – количество переменных, n > m.

, x_b – базисные, x_s – свободные.

– базисные столбцы.

– свободные столбцы.

Если x_s = 0, – базисное решение.

Базисное решение может оказаться недопустимым.

Теорема. Если множество допустимых значений задачи ЛП не пусто, то в нем $ хотя бы одно базисное решение.

Теорема. Множество допустимых базисных решений задачи ЛП совпадает множество крайних точек допустимого множества решений этой задачи.

Теорема. Если задача ЛП имеет решение, то оно достигается хот бы в одной из крайних точек.

Симплекс метод.

Предполагается, что есть допустимое базисное решение – x_b x_s (базисные и свободные компоненты этого решения).

Из предыдущего можно отметить, что . Функционал тоже можно разделить на c_b и c_s.

– симплекс разности.

Важные выводы:

1. если все симплес разности £ 0, то значение целевой финкции улучшить нельзя, то есть перед нами решение задачи;

2. не базисный столбец a_j имеет смысл вводить в базис, если симплекс разность > 0;

3. можно выбирать наибольшую из положительных симплекс разностей d_j.

Пусть a_r – столбец, который было решено ввести в базис.

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

.

® l

l – это одна из базисных переменных, индекс той переменной, которая реально выводится из базиса.

Значение x_l = 0 для этого нового базиса.

Отдельно возможно рассматривать вырожденные задачи ЛП (именно там может произойти зацикливание), но это вне основного вопроса.

Сам симплекс метод сводится к следующему:

1. Имеем базисное решение. Для него формируем A_b, A_s, C_b, C_s, X_b, X_s.

2. Вычисляем сиплекс разности. Если все они £ 0, получено решение, конец процедуры. Если нет, вводим в базис столбец a_r.

3. Если , то функционал можно увести в +¥, а если нет – .

4. Вычисление нового базисного решения

5. Переход к 1.

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