- •Тема 1. Математическая модель задачи линейного программирования (злп)
- •1. Предмет математического программирования
- •2. Математическая модель мп
- •3. Основные типы задач мп:
- •4. Многокритериальная оптимизация
- •5. Основные понятия теории оптимизации
- •6. Постановка злп. Различные формы записи ее математической модели
- •Тема 2. Графический метод решения злп. Закономерности и общие свойства решения злп
- •1. Геометрическая интерпретация решения злп
- •2. Алгоритм решения злп графическим методом
- •3. Возможные случаи области допустимых решений при решении злп графическим методом:
- •4. Основные свойства решений злп:
- •5. Классификация решений злп
- •6. Решение злп с точки зрения линейной алгебры
- •Тема 3. Симплексный метод решения задач линейного программирования
- •1. Суть симплексного метода
- •2. Критерий оптимальности решения злп
- •3. Алгоритм основного симплекс-метода:
- •4. Алгоритм двойственного симплекс-метода:
- •5. Алгоритм смешанного симплекс-метода:
- •6. Особые случаи симплекс-метода:
- •Тема 4. Модифицированный симплекс-метод решения злп. Устойчивость оптимального решения злп
- •1. Обращенный базис и симплекс-множители
- •2. Модифицированный симплекс-метод
- •3. Устойчивость оптимального решения злп:
- •Тема 5. Двойственность в линейном программировании
- •1. Понятие двойственности и теневой цены
- •2. Правила построения двойственной злп
- •3. Основные теоремы двойственности и их экономическое содержание
- •Тема 6. Элементы теории матричных игр
- •1. Основные понятия
- •2. Теоремы теории игр для парных матричных игр с нулевой суммой
- •3. Способы решения задач ти:
- •Тема 7. Матричные статистические игры
- •1. Понятие статистической игры
- •2. Критерии выбора оптимальной стратегии при решении статистической игры
- •3. Кооперативные игры
- •Тема 8. Транспортная задача (тз)
- •1. Постановка тз
- •2. Математическая модель тз
- •3. Решение тз методом потенциалов
- •4. Проверка плана на оптимальность
- •5. Цикл пересчета
- •6. Метод дифференциальных рент
- •7. Дополнительные ограничения тз
- •Тема 9. Дискретное программирование
- •1. Задача целочисленного линейного программирования
- •2. Метод Гомори
- •3. Метод ветвей и границ
- •Тема 10. Элементы нелинейного программирования
- •1. Постановка задачи нелинейного программирования
- •2. Метод множителей Лагранжа
- •3. Задача выпуклого программирования
- •4. Задача квадратического программирования
- •Тема 11. Метод динамического программирования
- •1. Общая постановка задачи динамического программирования
- •2. Принцип оптимальности. Функциональные уравнения Беллмана
- •3. Задача оптимального распределения инвестиций
- •4. Задача о замене оборудования
- •Тема 12. Программирование на сетях
- •1. Основные понятия теории графов
- •2. Экстремальное дерево графа
- •3. Матричные способы задания графов. Упорядочение элементов орграфа
- •4. Потоки на сетях. Постановка задачи о максимальном потоке
- •5. Разрез на сети. Теорема Форда-Фалкерсона. Алгоритм решения задачи о максимальном потоке
- •Тема 13. Планирование на сетях
- •1. Понятие сетевого графика
- •2. Основные параметры сг
- •3. Связь временных параметров сг
- •4. Алгоритм расчета параметров сг:
Тема 10. Элементы нелинейного программирования
План лекции:
1. Постановка задачи нелинейного программирования (ЗНП)
2. Метод множителей Лагранжа
3. Задача выпуклого программирования
4. Задача квадратического программирования
1. Постановка задачи нелинейного программирования
В общем виде ЗНП формулируется след образом:
где и (или) нелинейны.
Например,
Для ЗНП, в отличие от ЗЛП, нет единого метода решения. В зависимости от вида целевой функции и ограничений разработано несколько специальных методов решения, к которым относятся методы множителей Лагранжа, квадратичное и выпуклое программирование, градиентные методы, ряд приближенных методов решения, графический метод.
2. Метод множителей Лагранжа
Пусть требуется решить ЗНП следующего вида
где и (или) непрерывны и дифференцируемы.
Для решения задачи вводят так называемую функцию Лагранжа L(x, l):
.
Метод функции Лагранжа сводит ЗНП на условный экстремум к задаче нахождения локального экстремума.
Алгоритм метода:
1) Составляют функцию Лагранжа.
2) Находят стационарные точки функции Лагранжа из системы уравнений:
3) Из найденных стационарных точек выбирают те, в которых функция L(x, l) имеет локальные экстремумы. Функция L(x, l) имеет в стационарной точке локальный максимум, если в ней дифференциал второго порядка меньшего нуля (d2L<0), и локальный минимум, если дифференциал второго порядка больше нуля (d2L>0).
Множителям Лагранжа можно придать экономический смысл. Если F(x1,x2…xn) – доход, соответствующий плану x=(x1,x2…xn), – затраты некоторых ресурсов, тогда множители будут показывать как изменится максимальный доход, если количество ресурса i-го вида увеличится на единицу.
Задача. Найти условный минимум функции при ограничениях
Составим функцию Лагранжа:
.
Найдем стационарные точки функции Лагранжа из системы уравнений:
Решая систему, получаем .
Запишем дифференциал второго порядка функции Лагранжа. Поскольку все частные производные второго порядка, в записи которых присутствуют , равны нулю, то формула дифференциала второго порядка для функции Лагранжа примет вид:
.
Так как , , , , , , то
.
Следовательно, точка является точкой минимума функции . Найдем значение функции в данной точке:
.
Ответ: , .
3. Задача выпуклого программирования
Пусть дана система неравенств вида:
причем все функции являются выпуклыми на некотором выпуклом множестве М, а функция либо выпукла вверх (выпукла), либо выпукла вниз (вогнута) на множестве М. З ВП состоит в отыскании такого решения системы ограничений, при котором выпуклая функция достигает минимального значения, или вогнутая функция достигает максимального значения.
Определение 10.1. Точка (x*, λ*) называется седловой точкой функции Лагранжа, если n-мерная точка x* является точкой минимума функции L(x, λ*), а m-мерная точка λ* – точкой максимума функции L(x*, λ), так что x и λ выполняется неравенство:
.
Теорема 10.1. (Условие регулярности Слейтера) Множество Х допустимых решений ЗВП удовлетворяет условию регулярности Слейтера, если существует по крайне мере одно точка , такая что .
Теорема 10.2 (теорема Куна-Таккера). Чтобы точка x* была оптимальным решением ЗВП, множество допустимых решений которой обладают свойством регулярности Слейтера, необходимо и достаточно, чтобы существовала такая пара (x*, λ*), которая являлась бы седловой точкой функции Лагранжа данной ЗВП.
Замечание 10.1. Если ограничения задачи – линейные функции, то выполнение условия регулярности не требуется.
Для того чтобы найти седловые точки необходимо и достаточно составить систему: