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

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

· управляющие параметры – нек-е переменные величины.

· Мн-во управления – мн-во ф-ций времени

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

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

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

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

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

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

Фазовый вектор:Составленный из фазовых координат n-мерный вектор-столбец

x (t) = ,можно геометрически интерпретировать как точку в n-мерном евклидовом пространстве Eⁿ.

Фазовая траектория: Каждая фазовая координата считается непрерывной функцией времени, поэтому фазовая траектория{x (t)} = {x (t) }

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

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

Управляющий в-р:Составленный из управляющих параметров r-мерный вектор-столбец

u (t) = , называемый управляющим вектором, геометрически как точка в E^r.

Управлением («траекторией управления») называется функция

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

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

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

u (t) . (11.1.8)

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

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

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

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

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

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

Задача Больца.

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

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

= f (x, u, t),

x (t₀) = x₀,

x (t₁) = x₁,

{u (t)} .

Здесь I (…), F (..) и f (…) – заданные непрерывно дифференцируемые функции;

t₀, x₀ – фиксированные параметры;

t₁ или x₁ – фиксированные параметры

Траектория управления {u (t)} должна принадлежать фиксированному множеству управлений U, причем u (t) – кусочно-непрерывная функция времени, значения которой должны принадлежать некоторому фиксированному множеству Ω, являющемуся непустым компактным подмножеством пространства E^r.

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

при решении задачи с помощью принципа максимума сначала вводятся n сопряженных переменных y (t) и определяется ф-я Гамильтона H (x, u, y, t) = I (x, u, t) + yf (x, y, t).

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

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

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

, .

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

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

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

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

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

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

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

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

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

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

Каноническая(для нее симплекс-метод)

Общая

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

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

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

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

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

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

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

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

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

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

Предполагается, что есть допустимое базисное решение – x_bx_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.