Лыткина Л.И.

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

в системе MATHCAD

Печатается по решению

Редакционно-издательского совета академии

в качестве учебного пособия

Красноярск 2001

УДК22.18я7

ББК 519.68(07)

Л 88

Рецензенты:

профессор кафедры ИВТ САА В. В. Вдовенко;

доцент кафедры. высшей математики КГАЦМиЗ Н. А. Братухина

Лыткина Л. И.

Л 88 Методы оптимизации с программами в системе MATHCAD: Учеб. пособие/ САА. – Красноярск, 2001. – с. 88.

ISBN 5-86433-131-7

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

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

УДК 22.18я7

ББК 519.68(07)

© Сибирская аэрокосмическая академия ISBN5-86433-131-7 имени академика М. Ф. Решетнева, 2001

Предисловие

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

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

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

В учебном пособии рассматриваются две основные темы: безусловная оптимизация и условная оптимизация. В первой теме знакомятся с классическими и численными методами безусловной оптимизации. Материал излагается поглавно. Главы сопровождаются программами изложенных методов, выполненных в системе MATHCAD, которые позволяют получить “живые” картинки работы алгоритмов, помогают проанализировать методы с целью выбора подходящего при решении различных практических задач. Во второй теме показываются классические и численные методы решения задач условной оптимизации.

Автор выражает сердечную благодарность Семенкину Е.С. за помощь, оказанную при формировании структуры курса. Также признателен студентам группы ИУ-71 за оказанную помощь в технических вопросах.

ГЛАВА 1. БЕЗУСЛОВНАЯ ОПТИМИЗАЦИЯ

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

1.1. Постановка и классификация задач

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

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

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

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

• инженерный анализ и обработка информации;

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

Рассмотрим один пример, относящийся к третьей из перечисленных областей.

Предположим, что функционирование некоторого объекта (системы) описывается уравнением , гдеx - вход, независимая переменная, y - выход, зависимая переменная, - два параметра, влияющие на значение выходаy (и- неизвестны). Для того чтобы определить соответствующие параметры, необходимо провести серию экспериментов, в каждом из которых задается значениеx и измеряется значение y. Результатом серии из N экспериментов является множество пар чисел . На основе полученной информации делается попытка подобратьитаким образом, чтобы обеспечить хорошую точность описания экспериментальных данных с помощью функцииf. Наиболее часто на практике используется критерий наименьших квадратов, т. е. требуется минимизировать функцию

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

Эта задача может быть решена изложенными ниже методами.

Общая задача математического программирования формулируется следующим образом: требуется оптимизировать (минимизировать или максимизировать) целевую функцию

(1)

при наличии ограничений типа равенства

, , (2)

и ограничений типа неравенства

, . (3)

Функции f, заданы. Чаще рассматривается задача минимизации, чем максимизации, но это не ограничивает общности, так как .

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

Задача, удовлетворяющая условиям (1)-(3) называется задачей условной оптимизации. Если ограничения (2),(3) отсутствуют (допустимая область совпадает с ), то задача называется безусловной.

Если в задаче (1)-(3) целевая функция линейная и допустимая область задается линейными равенствами и (или) неравенствами, то задача (1)-(3) называется задачей линейного программирования.