- •1. Введение
- •Основные разделы курса
- •3. Основная задача линейного программирования. Различные формы записи задачи.
- •6. Алгоритм симплекс-метода.
- •1.3. Реализация симплекс-метода в виде симплексных таблиц.
- •8Транспортная задача. Описание и примеры применения метода потенциалов.
- •29.Метод ветвей и границ. Задача о рюкзаке.
- •Задача о рюкзаке
- •30. Метод ветвей и границ. Задача коммивояжера.
- •28. Методы перебора вариантов. Метод вариаций.
- •31.Задачей целочисленного программирования называется задача линейного программирования, в которой имеется дополнительное условие, требующее, чтобы часть переменных принимала только целые значения.
- •35.Общие принципы дискретного динамического программирования. Уравнение Беллмана.
- •36. Задача распределения ресурсов.
- •38. Построение кратчайшего пути на сети.
- •37. Задача оптимального планирования. Обработка деталей на двух станках.
- •10. Выпуклые множества и выпуклые функции.
- •13.Двойственность в задачах выпуклого программирования
- •14. Квадратичное программирование
- •12. Постановка задачи. Теорема Куна – Таккера.
- •16. Геометрическое программирование
- •11. Свойства выпуклых множеств и выпуклых функций
- •19. Общая задача нелинейного программирования.
- •22.Свойства дифференцируемых функций.
- •24. Дифференцируемость оператора Немыцкого.
- •25. Необходимый признак экстремума в задачах без ограничений первого и второго порядков.
- •27 . Правило множителей Лагранжа для гладких нелинейных задач.
- •41. Простейшая вариационная задача (пвз), исследование необходимых условий экстремума первого порядка.
- •45. Вариационная задача с кусочно-гладкими кривыми.
- •46. Исследование необходимых условий экстремума второго порядка. Условия Лежандра и Якоби.
- •42.. Алгоритм Гюйгенса исследования пвз.
- •48.. Поле экстремалей. Достаточные условия сильного экстремума.
- •Задача Больца.
- •6.9. Изопериметрические задачи.
- •51. Принцип максимума Понтрягина.
46. Исследование необходимых условий экстремума второго порядка. Условия Лежандра и Якоби.
Решить уравнение Эйлера для задачи (6.1.1) – это значит проверить необходимое условие экстремума первого порядка: Df(x)=0. Однако, для задач без ограничений известны также необходимые условия второго порядка, использующие вторую производную D2f(x).
Всюду в этом пункте мы предполагаем, что x(t) - это допустимая экстремаль задачи, найденная при решении уравнения Эйлера.
Найдем второй дифференциал от f при условии, что L∈C2(R×Rn×Rn). Как уже было найдено для функции φh(t) =f(x+th) = ∫[a; b] L(s, x(s)+th(s), x'(s)+th'(s)) ds, ее производная равна
φh'(t) = ∫[a; b] Lx(s, x(s)+th(s), x'(s)+th'(s))h(s) + Lx '(s, x(s)+th(s), x'(s)+th'(s))h'(s) ds, аналогично
φh''(0) = ∫[a; b] h(s)TLxx(s, x(s), x'(s))h(s) + 2h(s)TLxx '(s, x(s), x'(s))h'(s) + h'(s)TLx 'x '(s, x(s), x'(s))h'(s)ds.
Таким образом, если функционал f дважды дифференцируем, то
D2f(x)(h;h) = ∫[a; b] h(s)TLxx(s, x(s), x'(s))h(s) + 2h(s)TLxx '(s, x(s), x'(s))h'(s) + h'(s)TLx 'x '(s, x(s), x'(s))h'(s)ds.
Докажем, что функционал f действительно дважды дифференцируем.
По формуле Тейлора для функций нескольких переменных для каждого t∈[a, b] найдется число Q(t), таое что |Q(t)|≤1 и
L(t, x(t)+h(t), x'(t)+h'(t)) = L(t, x(t), x'(t)) +{ Lx(t, x(t), x'(t))h(t) + Lx'(t, x(t), x'(t))h'(t)} +
+ 1/2 {h(t)TLxx(t, x(t)+Q(t)h(t), x'(t)+Q(t)h'(t))h(t) + 2h(t)TLxx '(t, x(t)+Q(t)h(t), x'(t)+Q(t)h'(t))h'(t) +
+ h'(t)TLx 'x '(t, x(t)+Q(t)h(t), x'(t)+Q(t)h'(t))h'(t)}.
Сделаем некоторые обозначения:
Lx x (t) = Lx x (t, x(t), x'(t)); Lx x ' (t) = Lx x ' (t, x(t), x'(t)); Lx ' x ' (t) = Lx ' x ' (t, x(t), x'(t));
L~x x (t) = Lx x (t, x(t)+Q(t)h(t), x'(t)+Q(t)h'(t)); L~x x ' (t) = Lx x ' (t, x(t)+Q(t)h(t), x'(t)+Q(t)h'(t));
L~x ' x ' (t) = Lx ' x ' (t, x(t)+Q(t)h(t), x'(t)+Q(t)h'(t));
Тогда:
f(x+h) - f(x) - Df(x)h - 1/2 D2f(x)[h,h] =
= 1/2 ∫[a; b] h(s)T{L~xx(s) - Lxx(s)}h(s) + 2h(s)T{L~xx '(s) - Lxx '(s)}h'(s) + h'(s)T{L~x 'x '(s) - Lx 'x '(s)}h'(s)ds.
Нетрудно показать (используя непрерывность функций Lxx , Lxx’и Lx’x’), что
∫[a; b] h(s)T{L~xx(s) - Lxx(s)}h(s) + 2h(s)T{L~xx '(s) - Lxx '(s)}h'(s) + h'(s)T{L~x 'x '(s) - Lx 'x '(s)}h'(s)ds = o(||h||2).
Таким образом,
D2f(x)(h;h) = ∫[a; b] h(s)TLxx(s)h(s) + 2h(s)TLxx '(s)h'(s) + h'(s)TLx 'x '(s)h'(s)ds. (6.4.1)
Рассмотрим необходимые условия 2-го порядка: если x – точка минимума (максимума) функционала f, то для всех h∈M0 выполняется неравенство g(h) = D2(x)[h,h] ≥ 0 (соответственно, g(h) = D2(x)[h,h] ≤ 0).
На эти условия можно посмотреть как на другую простейшую вариационную задачу, а именно (в случае минимума):
g(h) = ∫[a; b] h(t)TLxx(t)h(t) + 2h(t)TLxx '(t)h'(t) + h'(t)TLx 'x '(t)h'(t)dt → min.
h∈M0={C1[a, b] | h(a)=0, h(b)=0}. (6.4.2)
При этом, если h0 – решение задачи (6.4.2), то достаточные условия для задачи (6.1.1) говорят о том, что g(h0) ≥ 0 (при других h значение g(h) будет еще больше). Нетрудно проверить, что при h0=0 получается g(h0)=0.
Поскольку (6.4.2) – простейшая вариационная задача, для нее тоже должно выполняться уравнение Эйлера.
Обозначим через F(t, h, h') = h(t)TLxx(t)h(t) + 2h(t)TLxx '(t)h'(t) + h'(t)TLx 'x '(t)h'(t) лагранжиан данной задачи.
Тогда Fh = 2Lxx(t)h(t) + 2Lxx '(t)h'(t); Fh ' = 2{Lxx' (t)}Th(t) + 2Lx 'x '(t)h'(t).
Таким образом, для каждого решения h0 задачи (6.4.2) выполняется уравнение Эйлера
d/dt F h ' (t, h0, h0')= F h (t, h0, h0'), т.е.
d/dt ({Lxx' (t)}Th0(t) + Lx 'x '(t)h0'(t)) = Lxx(t)h0(t) + Lxx '(t)h0'(t) (6.4.3)
Определение. Уравнение (6.4.3) называется уравнением Якоби для задачи 6.1.1.
Рассмотрим функции h(t) вида Hu(t), где H – постоянный вектор, ||H||2 = HTH=1, u(t) – скалярная функция. В этом случае h∈M0, если u∈{C1[a, b] | u(a)=0, u(b)=0}, причем
g(h) = ∫[a; b] HTLxx(t)H u2(t) + 2HTLxx '(t)H u(t)u'(t) + H TLx 'x '(t)H (u'(t))2dt =
= ∫[a; b] (HTLxx(t)H - d/dt HTLxx '(t)H) u2(t) + H TLx 'x '(t)H (u'(t))2dt =
= ∫[a; b] SH(t) u2(t) + RH(t) (u'(t))2dt .
где SH(t) = HT(Lxx – d/dt(Lxx'))H, RH(t) = HT(Lx'x')H.
При фиксированном H можно решать задачу минимизации, считая переменной функцию u. В этом случае также для решения u0 выполняется уравнение Эйлера: d/dt (RH(t) u'(t)) = SH(t) u(t).
Покажем, что из условия g(h)≥0 для всех h следует, что RH(t)=HT(Lx'x')H ≥ 0 при всех H и всех t∈[a, b], т.е. для всех t∈[a, b] матрица Lx'x'(t) является неотрицательно определенной.
Теорема 6.4.1. Если x0(t) – точка минимума (максимума) в задаче 6.1.1, то для всех t∈[a, b] матрица Lx'x'(t)= Lx'x'(t, x0(t), x0'(t)) является неотрицательно (неположительно) определенной.
Определение. Пусть x*(t) – допустимая экстремаль задачи 6.1.1, Lx'x'(t)= Lx'x'(t, x*(t), x*'(t)). Если для всех t∈[a, b] матрица Lx'x'(t) неотрицательно (положительно) определена, то говорят, что x*(t) удовлетворяет условию Лежандра для минимума (соответственно, усиленному условию Лежандра для минимума)).
Неположительная и отрицательная опредленность Lx'x'(t) дают условия Лежандра для максимума.
Замечание. С учетом данного определения теорему 6.4.1 можно сформулировать следующим образом: выполнение условия Лежандра является необходимым условием для решения задачи 6.1.1.
Определение. Если для точки с∈(a, b) найдется нетривиальное решение h0 уравнения Якоби, удовлетворяющее условиям h0(a) = h0(с)=0, говорят, что точка c является точкой, сопряженной к точке a . Если на интервале (a, b) нет точек, сопряженных с точкой a, то говорят, что выполняется условие Якоби, если таких точек нет на полуинтервале (a, b] -- выполняется усиленное условие Якоби
Теорема 6.4.2. Если x* - решение задачи (6.1.1), для которого выполнено усиленное условие Лежандра, то для него выполнено и условие Якоби.