- •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.Принципы динамического программирования и функциональные уравнения Беллмана.
4. Определение базиса угловой точки. Невырожденные угловые точки. Примеры.
Опр. Система векторов входящие в рав-во , еслиназ. базисом угловой точки х, координатыназ. базисными, остальные координаты – небазисными.
Опр. Если все базисные координаты точки х строго больше 0, тогда точка х называется невырожденной.
Следствие. Если точка х – невырожденная угловая точка, то для нее существует единственный базис. Вырожденная угловая точка может обладать несколькими базисами.
Пример:
–невырожденная угловая точка, проверим это.
, , где,.
–вырожденная угловая точка, так как при рассмотрении рав-ва , гдеточка– не является угловой точкой, так как.
Зам: Из nстолбцов м-цы А можно выбрать r ЛНЗ столбцов конечным числом способов, поэтому число угл.т. мн-ва Х конечно.
5. Связь между переменными задачи лп
Пусть ,Аm*n,. Из системы осн. ограничений можно удалить ЛЗ ур-я, тогда. Если, то системаимеют единств. решение. Если это реш-е не уд. прямым огр-ям, то, иначе. Рассм. Найдена угл. т-ка,- базисные компоненты,. Базис состоит из- ЛНЗ.Обозначения:
Умножим на:
Т.к. у – угловая, то , т.е.. Рав-вом. привести в виду. Из определения В(*) примет вид:. Из (3) выражаем- (4), обозначаем(3) перепишем в виде:(5)
(3), (4), (5) – зависимость между базисными и небазисными переменными.
6. Формула приращения целевой функции злп.
Рассм знач целев ф-ии в некот точке , т.е.
,
На основании того, что y есть угловая точка, имеем рав-ва
Поэтому (1),
где
Вектор в-р оценок. Он имеет размерность n − r.Заметим, что величины имеют смысл и при k =.
Действительно, при k=по определению обратной матрицы имеем, где черезобозначен единичный вектор с единицей в k-ой координате.Поэтому
Замеч: Величина имеет смысл и дляk=1,…,r; действительно, - единичный в-р
Замеч:Величинаполностью определяются коэф. матрицы, в-раи бази-сом угловой точки, при этом не зав-т от в-ра ресурсов
Замеч: Из (1) виден физический смысл оценок. Величиныпредставляют собой взятую с обратным знаком скорость зменения целев ф-ии при измененииi-ой небазисной переменной.
7. Достаточное условие оптимальности в злп. Достаточное условие неразрешимости злп
Исходную задачу ,можно переформулировать след. обр.: найти максимум ф-ции, гдепри ограничениях:,
где
и неотрицательности.
Будем искать некот. точку , в которойне уменьшится по сравнению с найденным знач. в точкеy.
Выберем некот. небазисную перем. ,и будем подбирать для нее неотрицат. значения. Остальные базисные перем.,,. Тогда соотнош.
примет вид:, а выражение целевой ф-ции.
Достаточное усл. оптимальности: Т.: Если , то планy является оптимальным.
Рассм. произв. точку и целев. ф-ю
Достаточное усл. неразрешимости:
Т.: Если найдется небазисная переменная точки упри,к=r+1,n, то целевая ф-ция неограниченно возрастаетна Х.
Док-во: в усл. Теор. Любой выбор полож. Небаз. Коорд. Приводит к построению точки, удовлт. Всем огр-ниям задачи, увеличивая только знач Хк, а остал оставляя без изм-ия, можно неогр увелич зн целевой ф-ции.