Металлургический факультет

Кафедра информационных технологий

в металлургии

АЛГОРИТМЫ И ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ ОДНОМЕРНОЙ ОПТИМИЗАЦИИ

Новокузнецк

2004

Министерство образования Российской Федерации

Сибирский государственный индустриальный университет

Кафедра информационных технологий в металлургии

Алгоритмы и примеры решения задач одномерной оптимизации

Методические указания к выполнению лабораторно-практических работ по курсу «Оптимизация в технике и технологиях»

Специальности: «Информационные системы и технологии» (071900), специализации «Прикладное математическое и программное обеспечение», по курсу «Методы оптимизации в металлургии»

Специальности: «Металлургия черных металлов» (110100),

специализации «Информационные технологии и предпринимательство в металлургии» (110107).

Новокузнецк

2004

УДК 681.3.06

Алгоритмы и примеры решения задач одномерной оптимизации: Метод. указ./ Сост.: С.П Мочалов, И.А. Рыбенко.: СибГИУ.- Новокузнецк, 2004.- 18с., ил.

Изложены теоретические аспекты методов поиска экстремума функции одной переменной, представлены алгоритмы методов, приведены примеры решения задач одномерной оптимизации и варианты заданий.

Предназначены для студентов специальности «Информационные системы и технологии» (071900), специализации «Прикладное математическое и программное обеспечение» и «Металлургия черных металлов» (110100), специализации «Информационные технологии и предпринимательство в металлургии» (110107).

Рецензент - кафедра систем автоматизации (зав. кафедрой С.М.Кулаков)

Печатается по решению редакционно-издательского совета университета.

1. Общие положения

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

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

Постановка задачи одномерной оптимизации заключается в нахождении точки х^*, в которой целевая функция f(х^*) принимает минимальное (максимальное) значение. Функция f(x) имеет локальный минимум в точке х⁰, если при >0 существует окрестность [x-; x+ ], такая, что для всех значений х в этой окрестности f(x) больше f(x^*). Функция f(x) имеет глобальной минимум в точке х^*, если для всех х справедливо неравенство f(x) >f(x^*).

Аналитический анализ функции. Классический подход к задаче нахождения экстремума функции состоит в поиске условий, которым они должны удовлетворять. Необходимым условием экстремума в точке x^* является равенство нулю первой производной, т.е. требуется решить уравнение f ^’(x)=0.

Данному уравнению удовлетворяет как локальные и глобальные экстремумы, так и точки перегиба функции, поэтому приведенное условие является необходимым, но не достаточным.

С целью получения более определенных выводов требуется расчет значений вторых производных в точках, удовлетворяющих уравнению равенства нулю первой производной. При этом доказано, что минимуму функции соответствует положительной значение второй производной (f^’”(x)>0), а максимальному – отрицательное (f^’”(x)<0). Однако, если вторая производная равна нулю, ситуация остается неопределенной.

Классификация численных методов. Для определения экстремума функции одной переменной можно применять поисковые методы и методы с использованием производных. Среди методов поиска выделяют методы последовательного сокращения интервала (сканирования, локализации оптимума, половинного деления, золотого сечения, Фибоначчи) и методы точечного оценивания (Пауэлла, квадратичной аппроксимации, обратного переменного шага). На основе использования производных построены методы: средней точки, секущих, кубичной аппроксимации, Ньютона и др.

Целью выполнения лабораторно-практических работ является: формирование навыков решения оптимизационных задач с использованием различных методов поиска экстремума функции одной переменной.