METODY_REShENIYa_ZNLP

5. ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ ЗНЛП

Численными методами называются методы решения математических задач, сводящиеся к выполнению конечного числа элементарных операций над числами. В качестве элементарных операций фигурируют арифметические действия, а также вспомогательные операции – записи промежуточных результатов, выборки из таблиц, файлов и т.д. В отличие от аналитических методов, решения, получаемые численными методами, как правило, являются приближенными, то есть не абсолютно точными, хотя в некоторых случаях могут достигаться и абсолютно точные решения. Численные методы рассчитаны на применение специальных вычислительных устройств (как правило, ЭВМ). Основными требованиями к численным методам являются требования устойчивости и сходимости. Численные методы называются устойчивыми, если результаты непрерывно зависят от входных данных задачи. Численные методы называются сходящимися, если результаты стремятся к точному решению задачи при стремлении параметров численных методов к определенным предельным значениям. Основным вопросом теории численных методов является получение численных методов, удовлетворяющих требованиям высокой точности, устойчивости и экономичности. Получение искомых решений при этом производится с помощью

алгоритмов.

5.1. Понятие алгоритма

Алгоритмом решения задачи называется система правил, следуя которым в твердо установленном порядке и производя вполне определенные операции, можно решить эту задачу. Мы будем рассматривать алгоритмы решения задач математического программирования (оптимизационных задач). Алгоритмом решения таких задач называется процедура, порождающая последовательность точек

предписанным набором правил. Преобразование k-го приближения

рацию алгоритма. Итерация реализуется некоторым заданным набором действий.

Алгоритм называется сходящимся на множестве S, если при про-

извольном начальном приближении x(0) S предел любой сходя-

51

щейся последовательности приближений, порождаемой этим алго-

Остановка реализации алгоритма происходит, как только выполняется критерий останова, задаваемый перед началом запуска алгоритма. Критерии останова определяются исходя из особенностей конкретной задачи. Самым главным фактором, определяющим критерий останова, является величина отклонения текущего приближения от истинного решения задачи.

5.2. Классификация численных методов

Численные методы условно разбиваются на следующие классы:

1)методы нулевого порядка (не требуют использования производных функций, участвующих в задаче);

2)методы первого порядка (требуют использования производных первого порядка);

3)методы второго порядка (требуют использования производных второго и более высокого порядков).

5.3.Алгоритмы численных методов решения задач матема-

тического программирования

Рассмотрим несколько классических численных методов решения задач математического программирования (ЗМП) без ограничений

Идеи, лежащие в основе этих методов, могут быть использованы для построения аналогичных методов решения ЗМП с ограничениями.

52

5.3.1. Метод наискорейшего спуска (подъема)

Метод предназначен для решения задачи (5.1) и принадлежит классу методов первого порядка. Метод основан на том факте, что

градиент f (x) целевой функции указывает направление ее максимального возрастания.

Описание алгоритма

Шаг 0. Выбирается точка начального приближения x(0) , пара-

метр длины шага 0 , параметр дробления шага m 1 и точность решения 0 .

Шаг k. На k-м шаге пересчет приближений производится по

Если при этом происходит «переход» через точку экстремума, то

Алгоритм завершает свою работу, как только выполнится (5.3). В качестве решения исходной задачи берется последнее полученное

приближение x(k 1) .

На рис. 5.1 показана схема реализации метода наискорейшего спуска при поиске минимума выпуклой функции одной переменной.

53

Формула (5.4) может быть переписана в эквивалентном виде

Алгоритм завершает свою работу, как только выполнится усло-

5.3.3. Метод Ньютона

Метод предназначен для решения задачи (5.1) и принадлежит классу методов второго порядка. В основе метода лежит разложение

Формулу (5.5) перепишем в матричной форме, учитывая при

Формула (5.7) определяет алгоритм метода Ньютона: пересчет приближений на k-й итерации выполняется в соответствии с форму-

Алгоритм заканчивает свою работу, как только выполнится условие

55

| x(k 1) x(k) | ,

где заданная точность решения; в качестве решения принимает-

ся значение последнего полученного приближения x(k 1) .

5.3.4. Метод Ньютона-Рафсона

Метод является методом первого порядка и предназначен для решения систем n нелинейных уравнений c n неизвестными:

В частности, этот метод может быть применен при поиске стационарных точек целевой функции задачи (5.1), когда необходимо

решить систему уравнений из условия f (x) 0 .

Формула (5.12) определяет алгоритм метода Ньютона-Рафсона: пересчет приближений на k-й итерации выполняется в соответствии

56

Замечание 5.1. Сходимость численных методов, как правило, сильно зависит от начального приближения.

Замечание 5.2. Методы Ньютона и Ньютона-Рафсона требуют большого объема вычислений (надо на каждом шаге вычислять и обращать матрицы Гессе и Якоби).

Замечание 5.3. При использовании методов обязательно следует учитывать возможность наличия многих экстремумов у целевой функции (свойство мультимодальности).

57

2.4.Задачи…………….............................................................................................. 23

3.РЕШЕНИЕ ЗАДАЧИ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ПРИ

3.2.Метод подстановки……………………………................................................. 34

3.3.Задачи………………………….......................................................................... 35

4.РЕШЕНИЕ ЗАДАЧИ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ПРИ

4.3.Задачи………………………….......................................................................... 47

5.ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ НЕЛИНЕЙНОГО ПРО-

5.3.2.Метод сопряженных градиентов…………………………......................... 53

5.3.3.Метод Ньютона…………………………..................................................... 54

5.3.4.Метод Ньютона-Рафсона………………………………………………... 55 ЛИТЕРАТУРА……………………………….............................................................. 57

59