- •Введение
- •1. Основы математического программирования
- •1.1. Постановка задачи математического программирования
- •1.2. Разновидности змп
- •1.3. Базовые понятия и терминология математического программирования
- •1.4. Производная по направлению. Градиент
- •1.5. Касательные гиперплоскости и нормали
- •1.6. Разложение Тейлора
- •1.7. Задача нелинейного программирования и условия существования ее решения
- •1.8. Задачи
- •2. Решение задачи нелинейного программирования без ограничений
- •2.1. Необходимые условия существования безусловного экстремума функции
- •2.2. Достаточные условия существования безусловного экстремума функции
- •2.3. Классический метод поиска безусловного экстремума
- •2.4. Задачи
- •3. Решение задачи нелинейного программирования при ограничениях-равенствах
- •3.1. Метод множителей Лагранжа
- •3.1.1. Назначение и обоснование метода
- •3.1.2. Схема реализации метода множителей Лагранжа
- •3.1.3. Интерпретация множителей Лагранжа
- •3.2. Метод подстановки
- •3.3. Задачи
- •4. Решение задачи нелинейного программирования при ограничениях-неравенствах
- •4.1. Обобщенный метод множителей Лагранжа
- •4.2. Условия Куна-Таккера
- •4.2.1. Необходимость условий Куна-Таккера
- •4.2.2. Достаточность условий Куна-Таккера в задачах выпукло-вогнутого программирования
- •4.2.3. Метод Куна-Таккера решения задачи выпукло-вогнутого программирования
- •4.3. Задачи
- •5. Численные методы решения знлп
- •5.1. Понятие алгоритма
- •5.3.2. Метод сопряженных градиентов
- •Описание алгоритма
- •5.3.3. Метод Ньютона
- •5.3.4. Метод Ньютона-Рафсона
- •Литература
- •Оглавление
5. Численные методы решения знлп
Численными методами называются методы решения математических задач, сводящиеся к выполнению конечного числа элементарных операций над числами. В качестве элементарных операций фигурируют арифметические действия, а также вспомогательные операции – записи промежуточных результатов, выборки из таблиц, файлов и т.д. В отличие от аналитических методов, решения, получаемые численными методами, как правило, являются приближенными, то есть не абсолютно точными, хотя в некоторых случаях могут достигаться и абсолютно точные решения. Численные методы рассчитаны на применение специальных вычислительных устройств (как правило, ЭВМ). Основными требованиями к численным методам являются требования устойчивости и сходимости. Численные методы называются устойчивыми, если результаты непрерывно зависят от входных данных задачи. Численные методы называются сходящимися, если результаты стремятся к точному решению задачи при стремлении параметров численных методов к определенным предельным значениям. Основным вопросом теории численных методов является получение численных методов, удовлетворяющих требованиям высокой точности, устойчивости и экономичности. Получение искомых решений при этом производится с помощью алгоритмов.
5.1. Понятие алгоритма
Алгоритмом решения задачи называется система правил, следуя которым в твердо установленном порядке и производя вполне определенные операции, можно решить эту задачу. Мы будем рассматривать алгоритмы решения задач математического программирования (оптимизационных задач). Алгоритмом решения таких задач называется процедура, порождающая последовательность точек (приближений к решению) в соответствии с предписанным набором правил. Преобразование k-го приближения в (k+1)-е приближение представляет собой k-ю итерацию алгоритма. Итерация реализуется некоторым заданным набором действий.
Алгоритм называется сходящимся на множестве S, если при произвольном начальном приближении предел любой сходящейся последовательности приближений, порождаемой этим алгоритмом, равен истинному (точному) решению , то есть
.
Остановка реализации алгоритма происходит, как только выполняется критерий останова, задаваемый перед началом запуска алгоритма. Критерии останова определяются исходя из особенностей конкретной задачи. Самым главным фактором, определяющим критерий останова, является величина отклонения текущего приближения от истинного решения задачи.
5.2. Классификация численных методов
Численные методы условно разбиваются на следующие классы:
1) методы нулевого порядка (не требуют использования производных функций, участвующих в задаче);
2) методы первого порядка (требуют использования производных первого порядка);
3) методы второго порядка (требуют использования производных второго и более высокого порядков).
5.3. Алгоритмы численных методов решения задач математического программирования
Рассмотрим несколько классических численных методов решения задач математического программирования (ЗМП) без ограничений
.3 (5.1)
Идеи, лежащие в основе этих методов, могут быть использованы для построения аналогичных методов решения ЗМП с ограничениями.
5.3.1. Метод наискорейшего спуска (подъема)
Метод предназначен для решения задачи (5.1) и принадлежит классу методов первого порядка. Метод основан на том факте, что градиент целевой функции указывает направление ее максимального возрастания.
Описание алгоритма
Шаг 0. Выбирается точка начального приближения , параметр длины шага , параметр дробления шага и точность решения .
Шаг k. На k-м шаге пересчет приближений производится по формулам
(5.2)
Если при этом происходит «переход» через точку экстремума, то есть оказываются справедливыми неравенства
то длина шага уменьшается в m раз.
Критерием останова алгоритма является неравенство
. (5.3)
Алгоритм завершает свою работу, как только выполнится (5.3). В качестве решения исходной задачи берется последнее полученное приближение .
На рис. 5.1 показана схема реализации метода наискорейшего спуска при поиске минимума выпуклой функции одной переменной.
Рис. 5.1