Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







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





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

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

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



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

.

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

 

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

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

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

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

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

 

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

 

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

 

.[3] (5.1)

 

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


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

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

 

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

Шаг 0. Выбирается точка начального приближения , параметр длины шага , параметр дробления шага и точность решения .

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

(5.2)

Если при этом происходит «переход» через точку экстремума, то есть оказываются справедливыми неравенства

то длина шага уменьшается в m раз.

Критерием останова алгоритма является неравенство

. (5.3)

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

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

 

 

Рис. 5.1

 









Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:


©2015- 2018 zdamsam.ru Размещенные материалы защищены законодательством РФ.