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

Кафедра компьютерных систем управления и обработки информации

З.Г. Насибов, Н.С. Нестерова, Г.Д. Нестеров

Методы оптимизации

Учебное пособие для студентов специальностей

Программное обеспечение вычислительной техники и

Автоматизированных систем

Вычислительные машины, комплексы, системы и сети

Прикладная информатика (в экономике)

Организация и технология защиты информации

Краснодар

Насибов З.Г., Нестерова Н.С., Нестеров Г.Д.

Методы оптимизации. Учебное пособие для студентов инженерных специальностей по дисциплинам «Методы оптимизации» и «Методы оптимизации и теория принятия решений».

В пособии изложены методы одномерной оптимизации, поисковые методы многомерной оптимизации, методы многомерной оптимизации на основе преобразования задач, рассмотрены некоторые аспекты линейной оптимизации.

Может использоваться при выполнении контрольных и курсовых работ, а также дипломных проектов, связанных с разработкой оптимальных автоматизированных информационных систем.

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

Протокол 1 от 29 августа 2008г.

Утверждено НМС Академии ИМСИТ

Протокол от 13.10.2008г. № 2

Рецензенты:

Д.т.н., профессор Видовский Л.А.

Д.ф-м.н., профессор Лебедев К.Н.

ВВЕДЕНИЕ

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

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

- недостаток математических знаний у инженеров;

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

- отсутствие вычислительных мощностей.

Сфера применения теории оптимизации в инженерном деле в настоящее время достаточно широка и включает следующие основные направления:

- проектирование систем и их составных частей;

- планирование и анализ функционирования существующих систем;

- анализ и обработка информации;

- управление динамическими системами.

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

Как правило, размерность задач оптимизации достаточно велика, что требует выполнения громоздких расчетов и значительных затрат времени. Поэтому оптимизационные методы в основном ориентированы на реализацию с помощью ЭВМ.

В данном учебном пособии приведены некоторые из наиболее употребительных методов оптимизации.

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

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

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

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

Задача оптимизации, в которой критерий оптимальности задан функцией одной переменной, часто встречается в инженерной практике. Кроме того, одномерные методы оптимизации часто используются при решении подзадач многомерной оптимизации. Поэтому анализ задач такого типа занимает центральное место в оптимизационных исследованиях. Это обусловило разработку большого числа методов одномерной оптимизации. Ниже рассматриваются некоторые из этих методов. При этом приводятся алгоритмы поиска максимума целевой функции I(x), где x – параметр оптимизации. Учитывая, что минимуму функции I(x) соответствует максимум функции -I(x), т. е. то изменив знак y минимизируемой функции I(x) на обратный, алгоритмами поиска максимума можно пользоваться и для поиска минимума I(x).