- •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. Принцип максимума Понтрягина.
10. Выпуклые множества и выпуклые функции.
Определение. Пусть X – векторное пространство, a, b∈X . Множество
[a, b] = {x∈X| ∃λ∈[0, 1] : x = λa+(1-λ)b}
называется отрезком, соединяющим точки a и b.
Нетрудно убедиться, что такое определение отрезка согласуется с обычным определением отрезка на плоскости и в трехмерном пространстве.
Определение. Пусть X – векторное пространство. Множество M⊆X называется выпуклым, если для всех a, b∈M выполняется условие [a, b] ⊆ M, т.е. множество M с любыми двумя точками содержит соединяющий их отрезок.
Определение. Пусть X – векторное пространство, M⊆X выпуклое подмножество. Функция f:M→R называется выпуклой, если для всех a, b∈M выполняется условие
∀λ∈[0, 1] f(λa+(1-λ)b) ≤ λf(a)+(1-λ)f(b), (4.1.1)
т.е. если две точки графика функции соединить отрезком, то график функции будет лежать ниже этого отрезка.
Иногда удобнее считать, что функция определена не на подмножестве M⊆X, а на всем векторном пространстве X. Для этого мы будем использовать следующее правило: в тех точках x∈X, в которых функция была неопределена, будем полагать, что f(x) = +∞.
Таким образом, мы будем иметь дело с функциями, значениями которых могут быть не только действительные числа, но и символ +∞. Если такие функции проверять на выпуклость, надо уметь совершать арифметические операции над символом +∞. Определим их естественным путем:
∀λ≥ 0 λ(+∞) = +∞, (+∞)+(+∞) = +∞, ∀y∈R y + (+∞) = +∞.
Важным примером таких функций являются индикаторные функции множеств.
Определение. Пусть X – векторное пространство, M⊆X – его подмножество. Функция
cM(x) = 0, если x∈M; cM(x) =+∞ в противном случае (4.1.2)
называется индикаторной функцией подмножества M.
Понятие индикаторной функции позволяет свести выпуклость множеств к выпуклости функций.
Теорема 4.1.1. Множество M⊆X является выпуклым тогда и только тогда, когда индикаторная функция cM является выпуклой.
Доказательство. Пусть M⊆X – выпуклое множество. Если cM(a)=+∞ или cM(b) = +∞, равенство (4.1.1) выполняется по правилам действий с бесконечностью.
Если же cM(a)≠+∞ и cM(b) ≠ +∞, то cM(a) = cM(b) =0, т.е. a, b∈M. В силу выпуклости множества М для всех λ∈[0, 1] имеем (λa+(1-λ)b)∈M, или cM(λa+(1-λ)b)=0. В таком случае cM(λa+(1-λ)b) = λcM(a)+(1-λ)cM(b) =0.
Обратно, пусть функция cM является выпуклой. Множество М не является выпуклым, если существуют a, b∈M и λ∈[0, 1], для которых (λa+(1-λ)b) ¬ ∈ M. Тогда λcM(a)+(1-λ)cM(b) = 0+0 =0, cM(λa+(1-λ)b)= +∞, что противоречит условию выпуклости функции cM (4.1.1).
Теорема доказана.
Определение. Пусть функция f: M→R. Множество Epi(f) = {(x,y)∈M×R| f(x) ≤ y} называется надграфиком функции f.
Для числовых функций название этого множества особенно наглядно: оно состоит из точек плоскости, находящихся над графиком функции f(x).
Понятие надграфика позволяет сформулировать критерий выпуклости функции, сводящий проверку выпуклости функций к проверке выпуклости множеств.
Теорема 4.1.2. Функция f: M→R является выпуклой тогда и только тогда, когда ее надграфик Epi(f) является выпуклым подмножеством в M×R.
Доказательство. Условие (x,a), (y,b)∈Epi(f) означает, что f(x) ≤ a, f(x) ≤ b. Тогда для всех λ∈[0, 1] справедливо λf(x)+(1-λ)f(y) ≤ λa+(1-λ)b.
Если f – выпуклая функция, то f(λx+(1-λ)y) ≤ λf(x)+(1-λ)f(y) ≤ λa+(1-λ)b,
т.е. (λx+(1-λ)y, λa+(1-λ)b) ∈ Epi(f), а это – условие выпуклости множества Epi(f).
Пусть Epi(f) выпукло. Для всех x, y ∈ М всегда (x,f(x)), (y,f(y) ∈Epi(f), поэтому (в виду выпуклости) (λx+(1-λ)y, λf(x)+(1-λ)f(y)) ∈Epi(f), т.е. f(λx+(1-λ)y) ≤ λf(x)+(1-λ)f(y).
Теорема доказана.
Замечание. Если функция f определена на открытом подмножестве M из RN и является дифференцируемой на этом множестве, то можно использовать дополнительные критерии выпуклости (см. соответствующие теоремы математического анализа):
1) Если f непрерывно дифференцируема на M, то ее выпуклость равносильна выполнению следующего условия: для всех a, b∈M выполняется неравенство f(a) – f(b) ≥ grad f(b)(a-b);
2) Если f дважды непрерывно дифференцируема на M, то ее выпуклость равносильна неотрицательной определенности матрицы ее вторых производных (которую можно проверять по критерию Сильвестра).