Нелинейные модели. Методы одномерной оптимизации

 

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

 

Постановка задачи нелинейного программирования

 

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

при ограничениях                                                                    (2.1)

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

 

Методы нелинейной одномерной оптимизации

 

Пусть функция  определена на . Задача одномерной оптимизации – задача, в которой требуется найти мах(min) , . Решение (точка максимума (минимума)) задачи одномерной оптимизации – точка , при условии  для всех .

                                                                       (2.2)

 

Функция  называется унимодальной на множестве , если существует единственная точка  её максимума на  и для любых ,

, если ;

, если

Унимодальная функция монотонно возрастает слева от точки максимума и монотонно убывает справа от неё.

В процессе применения методов одномерной оптимизации выделяют два этапа:

· поиск отрезка, содержащего точку максимума;

· уточнение координаты точки максимума на данном отрезке.

 

Алгоритм Свенна

 

Исходные данные:  – начальная точка,  – шаг поиска ().

Этап 1. Определить , , , .

Этап 2. Если , то  перейти на 4 этап.

Этап 3. Если , то ,  перейти на 4 этап, в противном случае (), , , конец.

Этап 4. . Определить .

Этап 5. Если , то , переход на 4 этап.

Этап 6. Если , то , , конец. В противном случае , , конец.

Случай  (этап 3) не рассматривается, так как он противоречит предположению о модальности функции .

 

Метод золотого сечения

 

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

 

 

 

 

Рисунок 2.1 – Золотое сечение

 

Точка производит золотое сечение отрезка , а точка  производит золотое сечение отрезка . На этом свойстве, позволяющем вычислять значение функции в одной пробной точке основан алгоритм золотого сечения.

Алгоритм золотого сечения включает этапы:

Исходные данные:  – отрезок, содержащий точку максимума,  – параметр окончания счёта.

Этап 1. ; , , ;

; ;

; ;

Этап 2. Если , то перейти на 4 этап.

Этап 3. ; ;

; ;

;

, перейти на 5 этап.

Этап 4. ; ; ; ;

;

Этап 5. Если , то , конец.

Этап 6. , перейти на этап 2.

 

Практическая работа №2