- •1.Понятие решения задачи мат. Программиров.
- •2. Основн. Формы злп. Правила сведения злп к канон.Форме. Геометр.Интерпретация злп. Понятие угловой точки мн-ва.
- •4. Определение базиса угловой точки. Невырожденные угловые точки. Примеры.
- •5. Связь между переменными задачи лп
- •6. Формула приращения целевой функции злп.
- •7. Достаточное условие оптимальности в злп. Достаточное условие неразрешимости злп
- •8. Итерация симплекс–метода
- •11. Нахождение базиса угловой точки. Пример
- •12. Постановка тз. Построение нач. Плана перевозок методом северо-западного угла, методом мин. Элемента.
- •13. Определение закрытой модели тз. Критерий существования решения тз.
- •14. Исследование мн-ва клеток транспортной таблицы
- •15. Достаточное условие минимальности стоимости перевозок
- •16. Классический метод решения задачи безусловной минимизации функции многих переменных. Пример.
- •17. Метод исключения решения задачи на условный минимум. Пример.
- •18. Обобщенное правило множителей Лагранжа в задаче оптимизации с ограничениями типа равенств.
- •19. Классическое правило множителей Лагранжа в задаче оптимизации с ограничениями типа равенств. Необходимые условия второго порядка в задаче оптимизации типа равенств.
- •20. Достаточные условия экстремума в задаче оптимизации с ограничениями типа равенств
- •21.Опр-ия выпуклого мн-ва, выпуклой функции. Св-ва выпуклых множеств. Сумма выпуклых функций. Св-во неотрицательности остатка выпуклой функции
- •22.Теорема о точках минимума выпуклой функции. Теорема о стационарной точке выпуклой функции
- •26.Теорема о седловой точке функции Лагранжа (достаточные условия оптимальности).
- •27. Критерий существования седловой точки функции Лагранжа для задачи выпуклого программирования.
- •28.Определение двойственной задачи к задаче математического программирования.
- •29. Связь между двойственной и прямой задачами математического программирования.
- •30.Пример решения задачи оптимизации с помощью теории двойственности
- •31.Основные определения в задаче одномерной минимизации. Примеры.
- •33. Метод золотого сечения решения задачи одномерной минимизации.
- •34. Обоснование метода ломаных решения задачи одномерной минимизации.
- •35. Алгоритм и условия сходимости метода ломаных решения задачи одномерной минимизации. Пример. Описание метода ломаных
- •36.Алгоритм метода скорейшего спуска решения змм.
- •37.Алгоритмы метода условного градиента и метода проекции градиента решения задачи многомерной условной минимизации.
- •38.Алгоритм метода покоординатного спуска решения задачи многомерной минимизации. Геометрическая иллюстрация.
- •39.Сходимость метода скорейшего спуска.
- •41. Метод вариаций Лагранжа
- •42. Уравнение Эйлера
- •43. Случаи интегрируемости ур-ния Эйлера. Примеры.
- •44.Задача вариационного исчисления с незакрепленными концами и фиксированным отрезком интегрирования.
- •45.Задача вариационного исчисления с незакрепленными концами и нефиксированным отрезком интегрирования
- •46. Задача вариационного исчисления с движущимся по кривой концом.
- •47. Примеры задач динамического программирования, их особенности
- •48.Принципы динамического программирования и функциональные уравнения Беллмана.
26.Теорема о седловой точке функции Лагранжа (достаточные условия оптимальности).
Рассм.задачу(1), (2)
где - заданное мн-во и ф-ииопределены на.
Для задачи (1), (2) рассмю нормированную ф-цию Лагранжа: (3)определенную на мн-ве (4)
Опр. Точканаз. седловой точкой функции Лагранжа (3), в области, если
Теорема1 (о седловой точке ф-ии Лагранжа) Пусть точка явлю седловой точкой ф-ции Лагранжа (3), тогда явлюрешение задачи (1)-(2).
Док-во: 1.Покажем сначала, что в условия теоремы точка уд. ограничениям (2) задачи (1)-(2). Т.к.-седловая точка ф-ции Лагранжа, то выполняется нер-ва:
(5)
Рассмю левое из (5):(6)
В нер-во (6) подставляем
вып-ся огранич. рав-ва.
Выберем некоторый индекс положимостальные. Подставим это в (6):выполняются ограничения неравенства.
Точка , т.к. она является седловой точкой функции Лагранжа. Т.е.удовл-ет огр-ям задачи (1)-(2).
2.Покажем, что для значения выполняется условие дополнительной нежесткости, а имеено, если
Предположим противное: пусть для некоторого индексаВ нер-ве (6) положим, тогда получимпоследнее нер-во будет вып-ся дляа не длячто противоречит определению седловой точки.
3.Покажем, что точка - решение задачи (1)-(2). Рассмотрим правое из нер-в (5), из которого в силу условия дополнительной нежесткости
Рассмотрим последнее нер-во для:
Доказан
27. Критерий существования седловой точки функции Лагранжа для задачи выпуклого программирования.
Рассм.задачу (1), (2)
где -заданное мн-во и ф-ииопределены на.
Для задачи (1), (2) рассм. нормированную ф-ию Лагранжа: (3) определенную на мн-ве
(4)
Теор2 (Критерий сущ.седловой точки ф-ии Лагранжа для задачи выпуклого прогр-ния) Пусть в задаче (1)-(2) функции являются выпуклыми, т.е задача (1)-(2)-задачи выпуклого программирования, (-выпуклое мн-во) и функцииявл. дифференцируемыми в точкеТогда точкаявл.седловой точкой ф-ции Лагранжа тогда и только тогда, когда
Док-во: (Необходимость). Пусть точка - седлова точка ф-ии Лагранжа, тогдаТ.к. ф-иидиф-мы, то ф-ия Лагранжа диф-ма:
Последнее нер-во разделим на ,получим (5)
Покажем, что для значения вып-ся условие доп-ной нежесткости, а именно, если
Предположим противное: пусть для некоторого индексаВ нер-ве (6) положим, тогда получимпоследнее нер-во будет вып-ся дляа не длячто противоречит определению седловой точки.
Достаточность: Пусть вып-ся соотношения (5)-(6), покажем тогда, что точка явл-ся седловой точкой ф-ии Лагранжа. Т.к. ф-ии -выпуклые по условию теоремы, то ф-ия Лагранжа выпуклая по х.
По св-ву неотр-ти остатка для выпуклой ф-ии вып-ся:
т.е. правая точка из опр. седловой точки. Точка
а из условия (6)
отсюда следует правая часть нер-ва из определения седловой точки. Теорема доказана.
28.Определение двойственной задачи к задаче математического программирования.
где заданное мн-во, ф-цииопределены на мн-веПереформулируем задачу (1) при помощи нормальной классической ф-ции Лагранжа:Ф-ция Лагранжа определяется на мн-ве. Переформулируем задачу (1) при помощи нормальной классической ф-ции Лагранжа:
Ф-ция Лагранжа определена на мн-ве Рассм. Ф-цию
Рассм. задачу .
Точную нижнюю граньВ силу зависимости ф-иис задачей (1):В предположении, чтои мн-во решений задачи (1) не пусто, т.е.Задача (3) то же будет иметь мн-во решенийс тем жеmin значением.
Аналогично с функцией (2) рассмотрим ф-цию которая будет определена наИ рассм. задачу
Задача (4) наз. двойственной к задаче (3) или к задаче (1). Переменные двойственные переменные,наз. основными.
При подстановке задачи (1) предполаг., что ф-ия приним. Конечные значения на мн-ве, поэтому ф-ия. Однако определение ф-иине исключает возможности принятия значений разных. Чтобы подчеркнуть конечность ф-ииговорят, что рассматривается задача(5)
гдеОбозначими через
Теор Дляимеет место нер-во(6)
Док-во: По определению функции Если
то Переходя в последнем нер-ве к точной нижней грани по мн-ву, получаем нер-воОстальные два нер-ва в (6) очевидны.
Теорема доказана.