Оптимизация функций одной переменной

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

Рубрика Производство и технологии
Вид курсовая работа
Язык русский
Дата добавления 20.05.2018
Размер файла 158,3 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

Федеральное государственное образовательное учреждение высшего образования

«Казанский национальный исследовательский технологический университет»

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

КУРСОВАЯ РАБОТА

по дисциплине

“Оптимизация композитных систем и технологических процессов”

«Оптимизация функций одной переменной»

Выполнил студент гр. 1143-82 Стрелков Р.

Проверил доцент кафедры ТИПКМ Е.Г. Белов

г. Казань

СОДЕРЖАНИЕ

Введение

1. Методологические основы оптимизации

1.1 Необходимые условия для применения оптимизационных методов

1.2 Определение границ системы

1.3 Характеристический критерий

1.4 Независимые переменные

1.5 Модель системы

2. Применение методов оптимизации в инженерной практике

3. Оптимизация функции одной переменной

3.1 Оптимизация функции одной переменной методом золотого сечения

3.1.1 Этап установления границ интервала

3.1.2 Этап уменьшения интервала

ВВЕДЕНИЕ

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

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

В работе решались следующие задачи в рамках дисциплины «Методы оптимизации композитных систем»:

1) Обучающие задачи:

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

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

в) изучение основ теории оптимизации при решении технических задач;

г) освоение методов оптимизации КС (состава КС, проектирования, конструирования и технологии изготовления изделий из КС);

д) получение практических навыков при постановке оптимизационных задач и путей их решения.

2) Разработка обучающих и контролирующих программ оптимизации функций одной переменной.

Пояснительная записка оформлена на примере оптимизации функций одной переменной методом деления отрезка пополам.

1. МЕТОДОЛОГИЧЕСКИЕ ОСНОВЫ ОПТИМИЗАЦИИ

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

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

По размерности решаемой задачи: одномерные и многомерные.

По способу формирования шага многомерные методы делятся на следующие виды:

2.1. Градиентные.

*по способу вычисления градиента: с парной пробой и с центральной пробой;

* по алгоритму коррекции шага;

*по алгоритму вычисления новой точки: одношаговые и многошаговые.

Безградиентные: с поочередным изменением переменных и с одновременным изменением переменных.

Случайного поиска: с чисто случайной стратегией и со смешанной стратегией.

3. По наличию активных ограничений.

3.1. Без ограничений (безусловные).

3.2. С ограничениями (условные):

с ограничениями типа равенств;

с ограничениями типа неравенств;

смешанные.

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

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

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

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

1.1 Необходимые условия для применения оптимизационных методов

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

1.2 Определение границ системы

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

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

1.3 Характеристический критерий

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

Важно отметить, что независимо от содержания оптимизационных методов, рассматриваемых в настоящей книге, только один критерий (и, следовательно, характеристическая мера) может использоваться при определении оптимума, так как невозможно получить решение, которое, например, одновременно обеспечивает минимум затрат, максимум надежности и минимум потребляемой энергии. Здесь мы опять сталкиваемся с существенным упрощением реальной ситуации, поскольку в ряде практических случаев было бы весьма желательным найти решение, которое бы являлось «наилучшим» с позиций нескольких различных критериев.

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

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

1.4 Независимые переменные

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

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

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

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

1.5 Модель системы

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

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

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

2. ПРИМЕНЕНИЕ МЕТОДОВ ОПТИМИЗАЦИИ В ИНЖЕНЕРНОЙ ПРАКТИКЕ

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

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

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

систем;

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

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

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

Рисунок 2.1 - Этапы процесса инженерного проектирования

3. ОПТИМИЗАЦИЯ ФУНКЦИИ ОДНОЙ ПЕРЕМЕННОЙ

3.1 Оптимизация функции одной переменной методом золотого сечения

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

Задача оптимизации, в которой характеристическая мера задана функцией одной переменной, относится к наиболее простому типу оптимизационных задач. Тем не менее анализ задач такого типа занимает центральное место в оптимизационных исследованиях как теоретической, так и практической направленности. Это связано не только с тем, что именно такие задачи обычно решаются в инженерной практике, но и с тем, что одномерные методы оптимизации часто используются для анализа подзадач, которые возникают при реализации итеративных процедур, ориентированных на решение многомерных задач оптимизации. Важность теоретических и прикладных оптимизационных задач с одной управляемой переменной обусловила разработку большого числа алгоритмов их решения. Классификация методов решения одномерных задач по существу основывается на различных предположениях и допущениях относительно природы и свойств функции f{x).

Методы исключения интервалов

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

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

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

- этап установления границ интервала, на котором реализуется процедура поиска границ достаточно широкого интервала, содержащего точку оптимума;

- этап уменьшения интервала, на котором реализуется конечная последовательность преобразований исходного интервала с тем, чтобы уменьшить его длину до заранее установленной величины,

3.1.1 Этап установления границ интервала

На этом этапе сначала выбирается исходная точка, а затем на основе правила исключения строится относительно широкий интервал, содержащий точку оптимума. Обычно поиск граничных точек такого интервала проводится с помощью эвристических методов поиска, хотя в ряде случаев можно также использовать методы, экстраполяции. В соответствии с одним из эвристических методов, который был предложен Свенном [1], (+1)-я пробная точка определяется по рекуррентной формуле

где х0-- произвольно выбранная начальная точка, Д -- подбираемая некоторым способом величина шага. Знак Д определяется путем сравнения значений f(x0), f(x0+|Д|) и f(x0-- |Д|). Если

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

то точка минимума лежит между х0--|Д| и х0+|Д| и поиск граничных точек завершен. Случай, когда

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

3.1.2 Этап уменьшения интервала

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

Методы с использованием производных

Все рассмотренные в предыдущих разделах методы поиска основываются на предположениях об унимодальности и в ряде случаев о непрерывности исследуемой целевой функции. Целесообразно предположить, что если в дополнение к условию непрерывности ввести требование дифференцируемости функции, то эффективность поисковых процедур можно существенно повысить. Напомним, что в разд. 2.2 установлено необходимое условие существования локального минимума функции в некоторой точке z, согласно которому первая производная функции в точке z должна обращаться в нуль, т. е. f '(z)=df/dx|x=2=0.

Если функция f(x) содержит члены, включающие х в третьей и более высоких степенях, то непосредственное получение аналитического решения уравнения f'(x)=0 может оказаться затруднительным. В таких случаях используются приближенные методы последовательного поиска стационарной точки функции f. Прежде всего опишем классическую поисковую схему, ориентированную на нахождение корня нелинейного уравнения. Эта схема была разработана Ньютоном и позднее уточнена Рафсоном [5].

Метод средней точки

Если функция f(x) унимодальна в заданном интервале поиска, то точкой оптимума является точка, в которой f '(х)=0. Если при этом имеется возможность вычислять как значения функции, так и ее производной, то для нахождения корня уравнения f '(х)=0 можно воспользоваться эффективным алгоритмом исключения интервалов, на каждой итерации которого рассматривается лишь одна пробная точка. Например, если в точке z выполняется неравенство f '(z)<0, то с учетом предположения об унимодальности естественно утверждать, что точка минимума не может находиться левее точки z. Другими словами, интервал х?z подлежит исключению. С другой стороны, если f '(z)>0, то точка минимума не может находиться правее z и интервал x?z можно исключить. Приведенные рассуждения лежат в основе логической структуры метода средней точки, который иногда называют поиском Больцано.

Определим две точки L и R таким образом, что f '(L)<0 и f '(R)>0. Стационарная точка расположена между L и R. Вычислим значение производной функции в средней точке рассматриваемого интервала z=(L+R)/2. Если f '(z)>0, то интервал (z, R)-можно исключить из интервала поиска. С другой стороны, если f '(z)<0, то можно исключить интервал (L, z). Ниже дается формализованное описание шагов алгоритма.

Пусть имеется ограниченный интервал а? х? b и задан параметр сходимости .

Шаг 1. Положить R=b, L=a; при этом f '(а)<0 и f '(b)>0.

Ш а г 2. Вычислить z=(R+L)/2 и f '(z).

Ш а г 3. Если |f '(z)|?, закончить поиск. В противном случае, если f '(z)<0, положить L=z и перейти к шагу 2. Если f '(z)>0, положить R=z и перейти к шагу 2.

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

Размещено на Allbest.ru

...

Подобные документы

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.