Сравнительный анализ методов оптимизации (стр. 1 из 7). Анализ оптимизации
Методы анализа и оптимизации бизнес-процессов
Ковалев Сергей Михайлович, Ковалев Валерий Михайлович, (Журнал "Консультант директора", № 7 (234), Апрель 2005 г.)
Текст статьи, разбитый на части представлен в следующих разделах:
| | Часть 1 "Разработка целей и показателей оптимизации бизнес-процессов" |
| | Часть 2 "Методы анализа и оптимизации бизнес-процессов" |
| | Часть 3 "Метод пяти вопросов" |
Часть 1.
"Разработка целей и показателей оптимизации бизнес-процессов"
Анализ и оптимизация бизнес-процессов
В предыдущих публикациях был рассмотрен первый этап построения и оптимизации деятельности предприятия "Разработка модели "как есть". В публикации "Выбор бизнес-процессов для оптимизации" были рассмотрены вопросы выбора приоритетных бизнес-процессов для оптимизации. В этой статье и последующих будет продолжено рассмотрение второго и третьего этапов: "Анализ модели "как есть" и "Разработка модели "как надо", но только применительно к бизнес-процессам. Анализ существующей и разработка новой оптимальной организационной структуры согласно классике построения организации является следующим шагом и будет рассмотрен в дальнейшем (см. рис.1).
Рисунок 1. Главная формула и классика построения и оптимизации организации
Технологии анализа и оптимизации бизнес-процессов Определение целей и критериев оптимизации бизнес-процессов
После определения приоритетных бизнес-процессов нужно приступить к их детальному описанию, анализу и оптимизации. Практика реализации подобных проектов показала, что перед проведением детального описания бизнес-процессов необходимо сформулировать основные цели и критерии их оптимизации. На данном этапе это возможно сделать, используя результаты экспресс-диагностики деятельности компании, проведенной при определении степени проблемности бизнес-процессов.
Первоочередное планирование целей и критериев оптимизации необходимо для повышения эффективности проекта по улучшению процессов. У любого проекта на начальной стадии должна быть четко сформулированная и реальная цель.
Многие компании, реализующие проекты по улучшению бизнес-процессов, допускают типичную ошибку: они начинают бесцельно описывать бизнес-процессы в надежде, на что после разработки детальных процессных схем будут обнаружены проблемы, сформулированы пути их решения и соответственно цели и критерии оптимизации. Практика реализации подобных проектов показала, что данный подход неэффективен, так как бесцельное описание бизнес-процессов часто не дает никаких результатов и отнимает много времени и сил, что приводит в дальнейшем к отказу от проведения подобных работ.
Более того, не сформулировав изначально цели и критерии оптимизации процесса, невозможно выбрать нужный подход и методологию описания, а также инструмент анализа и улучшения. При этом нельзя построить компактную схему бизнес-процесса, дающую ответы на нужные вопросы.
Базовые показатели, цели и критерии оптимизации бизнес-процессов
Итак, перед проведением описания, анализа и оптимизации бизнес-процессов нужно сформулировать цели и критерии их оптимизации. Цели и критерии оптимизации бизнес-процессов базируются на ключевых показателях процессов, определяющих эффективность и конкурентоспособность организации. В нашей книге эти показатели сгруппированы и представлены в виде пяти групп:
показатели Результативности бизнес-процесса – R$
показатели Стоимости бизнес-процесса - C$
показатели Времени бизнес-процесса – t
показатели Качества бизнес-процесса – Q
показатели Фрагментации бизнес-процесса – FRAG
studfiles.net
Оптимизация
Оптимальный — наилучший в заданных условиях. Качество оценивается с помощью критерия оптимальности, а условия задаются в виде ограничений на дополнительные критерии.
Оптимизация — в математике, информатике и исследовании операций задача нахождения экстремума (минимума или максимума) целевой функции в некоторой области конечномерного векторного пространства, ограниченной набором линейных и/или нелинейных равенств и/или неравенств.
Оптимизационные модели
Оптимизационные модели предназначены для определения оптимальных (наилучших) с точки зрения некоторого критерия параметров моделируемого объекта или же для поиска оптимального (наилучшего) режима управления некоторым процессом. Часть параметров модели относят к параметрам управления, изменяя которые можно получать различные варианты наборов значений выходных параметров. Как правило, данные модели строятся с использованием одной или нескольких дескриптивных моделей и включают некоторый критерий, позволяющий сравнивать различные варианты наборов значений выходных параметров между собой с целью выбора наилучшего. На область значений входных параметров могут быть наложены ограничения в виде равенств и неравенств, связанные с особенностями рассматриваемого объекта или процесса. Целью оптимизационных моделей является поиск таких допустимых параметров управления, при которых критерий выбора достигает своего «наилучшего значения».
Оптимизационные модели исследования операций
Задача формулируется в виде математической модели. Типовая математическая модель исследования операций представлена в следующей формулировке:
Максимизация или минимизация целевой функции, при условии выполнения ограничений
Оптимальными называются решения которые по тем или другим признакам предпочтительнее других. Каждый выбор лучшего варианта конкретен, поскольку основан на соответствии установленным критериям. Говоря об оптимальном варианте, указывают эти критерии («оптимальный по…»). То, что оптимально при одном критерии, не обязательно будет таковым при другом.
Допустимое решение — если оно удовлетворяет всем ограничениям модели. Допустимых решений в отдельных случаях может быть бесконечное множество.
Оптимальное решение — если кроме того, что оно допустимо, целевая функция в этом решении достигает максимального или минимального значения.
Оптимизация — максимизация или минимизация целевой функции.
Оптимизационная модель — это модель принятия решения, содержащая показатель эффективности (целевую функцию), который необходимо оптимизировать при условии соблюдения набора заданных ограничений.
Оптимальное решение — допустимый набор значений переменных решения, оптимизирующий целевую функцию оптимизационной модели.
Модель оптимального выбора
Большое число встречающихся на практике задач выбора сводится к нахождению лучших или наиболее предпочтительных для человека вариантов, а нередко — к поиску единственно лучшего варианта. При этом у каждого лица принимающего решение (ЛПР) есть собственные субъективные представления о том, что для него является предпочтительным в конкретной ситуации выбора.
Имеется достаточно много задач, для которых можно построить математическую модель выбора, где понятие лучшего варианта формализуется путем задания одного или нескольких числовых показателей эффективности или критериев качества решения. Эти показатели, хотя и задаются ЛПР, носят объективный характер, определяемый содержанием решаемой задачи, и выражаются какими-либо функциями, зависящими от переменных, которыми измеряются свойства вариантов. В таких случаях наиболее предпочтительным для ЛПР вариантом решения задачи выбора принято считать так называемый оптимальный вариант, который соответствует экстремальному значению одного или нескольких показателей эффективности решения при существующих условиях.
Принципиальным моментом для формулировки задачи оптимального выбора является возможность описания проблемной ситуации и предпочтений ЛПР в количественной форме. Это означает, что, во-первых, возможные варианты решения (альтернативы, объекты, способы действия) определяются количественными признаками (переменными, параметрами, атрибутами), измеряемыми с помощью числовых шкал. Во-вторых, должны быть заданы количественные же показатели (критерии оптимальности, показатели эффективности, целевые функции, функции ценности), по величине которых оценивается качество выбранного варианта. Такого рода ситуации характерны для хорошо структурируемых проблем и повторяющихся ситуаций выбора, типичных для исследования операций и оптимального управления.
Для анализа возможных вариантов решения проблемы (способов достижения цели) и выбора среди них одного или нескольких лучших вариантов строятся формальные модели оптимального выбора. Модель дает упрощенное представление реальной проблемы и должна отражать наиболее важные и объективно существующие зависимости и связи между вариантами, описывающими их признаками и ограничениями, которые задаются управляемыми и неуправляемыми факторами. Построение такой модели — задача консультантов-аналитиков и экспертов при участии ЛПР. При построении модели выбора нужно соизмерять адекватность и детальность модели с точностью требуемого решения реальной задачи выбора, а также с объемом необходимой для поиска решения информации — как имеющейся в наличии, так и получаемой дополнительно.
Ограничения оптимизационного подхода
Оптимизационные проблемы являются строго формальными математическими задачами. Практическое значение решений таких задач прямо зависит от того, насколько хороша исходная математическая модель. В сложных системах математическое моделирование является затруднительным, приблизительным, неточным. Чем сложнее система, тем осторожнее следует относиться к ее оптимизации.
С позиций системного анализа отношение к оптимизации можно сформулировать следующим образом: это мощное средство повышения эффективности, но использовать его следует все более осторожно по мере возрастания сложности проблемы.
При всей очевидной полезности идеи оптимизации практика требует необходимости осторожного обращения с ней. Для такого заключения имеются достаточно веские основания.
- Оптимальное решение часто оказывается неустойчивым: незначительные на первый взгляд изменения в условиях задачи могут привести к выбору существенно отличающихся альтернатив.
- Рассматриваемая система является частью некоторой большей системы, и тогда локальная оптимизация совсем не обязательно приведет к тому же результату, который потребуется от подсистемы при оптимизации системы в целом. Это приводит к необходимости увязывать критерии подсистем с критериями системы, часто делая ненужной локальную оптимизацию.
- Критерии характеризуют цель лишь косвенно, иногда лучше, иногда хуже, но всегда приближенно. Максимизация критерия оптимальности часто отождествляется с целью, а на самом деле это разные вещи. Фактически критерий и цель относятся друг к другу как модель и оригинал, со всеми вытекающими отсюда особенностями. Многие цели трудно или даже невозможно количественно описать.
- Не задав всех необходимых ограничений, мы можем одновременно с максимизацией основного критерия получить непредвиденные и нежелательные сопутствуюшие эффекты.
Моделирование
Системный анализ
Исследование операций
Методология исследования операций
systems-analysis.ru
Методы анализа и оптимизации (реинжиниринга) бизнес-процессов
Перечислим полный перечень методов анализа и оптимизации (реинжиниринга) бизнес-процессов.- SWOT-анализ (анализ слабых и сильных сторон бизнес-процесса)
- Метод причин-следствий (диаграмма Исикавы – Cause and Effect Diagram)
- Бенчмаркинг
- Анализ и оптимизация бизнес-процессов на основе показателей (KPI)
- Мозговой штурм
- Методики Lean, «6 Сигма»
- Расчёт и изменение фрагментарности процесса
- Анализ бизнес-логики процесса
- Метод функционально-стоимостного анализа (ФСА-анализ)
- Метод имитационного (динамического) моделирования БП
- Расчёт и анализ трудоёмкости и длительности бизнес-процесса
- Анализ матрицы распределения ответственности
- Анализ автоматизированности процесса
Рассмотрим более подробно отдельные методы.
1. Анализ бизнес-логики процесса Бизнес-логика – это ход выполнения бизнес-процесса, взаимосвязь и очередность выполнения его подпроцессов и элементарных функций. Для анализа бизнес-логики целесообразно привлекать отраслевого эксперта, который может дать консультацию о том, как наиболее правильно и эффективность организовать выполнение бизнес-процесса. Необходимо ответить на следующие вопросы. 1. Какие подпроцессы / функции детализировать. 2. Какие подпроцессы / функции удалить, заменить, либо перевести в другие бизнес-процессы. 3. Выполнение каких подпроцессов / функций сделать параллельным. 4. Для каких подпроцессов / функций разработать несколько вариантов выполнения в зависимости от входных данных и условий внешней / внутренней среды. 5. Как изменить последовательность (очередность) выполнения подпроцессов / функций. 6. Каких подпроцессов / функций не хватает в бизнес-процессе. 7. Как перераспределить исполнителей внутри бизнес-процесса.2. Анализ автоматизированности бизнес-процесса Для реализации данного метода необходимо выполнить следующие этапы. 1. Разработать модель информационных систем банка с детализацией до модулей и их ИТ-функций. 2. Разработать проекции бизнес-процессов / функций на ИТ-функции, которые их автоматизируют. 3. Проанализировать уровень автоматизации бизнес-процессов. Собрать от владельцев и исполнителей бизнес-процессов предложения по автоматизации. Выявить наиболее проблемные участки в бизнес-процессах, требующие автоматизации. Также следует определить какие бумажные информации потоки в бизнес-процессах можно и целесообразно сделать электронными. 4. Разработать план автоматизации бизнес-процессов и технические задания по каждому бизнес-процессу.
3. Функционально-стоимостной анализ (ФСА) бизнес-процесса ФСА-анализ применяется для расчета и оптимизации стоимости бизнес-процессов. ФСА-анализу посвящены отдельные объёмные методики и материалы, поэтому рассмотрим только вкратце основные этапы метода. 1. Разработать модель операционных ресурсов, которые используются в бизнес-процессах. Установить для ресурсов параметры: стоимость, единица измерения и т.д. Если ресурс материальный, то единицей измерения, как правило, являются штуки. Если ресурс условно «нематериальный» (например, компьютер или сотрудник банка), то единицей измерения являются часы работы. 2. Разработать проекции ресурсов на бизнес-процессы (процедуры и функции). Т.е. какие ресурсы и сколько потребляет каждый бизнес-процесс. Например, 4 листа бумаги, 10 минут работы компьютера, 20 минут работы операциониста. 3. Выполнить расчет стоимости бизнес-процесса. Расчет рекомендуется выполнять с помощью программных продуктов бизнес-моделирования, которые имеют соответствующую функциональность. Также перед ФСА-анализом рекомендуется рассчитать имитационную модель бизнес-процесса, т.е. какая длительность бизнес-процесса и каждой его процедуры / функции, сколько раз он выполняется в течение определенного промежутка времени.
4. Анализ длительности и трудоемкости бизнес-процесса Данный метод будет подробно рассмотрен далее в разделе «Оптимизация оргструктуры и численности персонала банка на основе расчета трудоемкости бизнес-процессов».5. Анализ бизнес-процесса на основе диаграмм причин-следствий Диаграмма причин-следствий (Cause-and-Effect Diagram или диаграмма Исикавы) используется как вспомогательный инструмент анализа проблемных областей в бизнес-процессе и выявления причин. Данную диаграмму можно использовать также как инструмент разработки решений проблемы и планов оптимизации. Пример данной диаграммы.
6. Анализ фрагментарности бизнес-процесса Во всех бизнес-процессах есть функциональные переходы, которые обозначают переход от одного подпроцесса / функции к другому (следующему). Если в бизнес-процессе более 1-го исполнителя, то имеет место такое понятие, как организационный разрыв.
Организационный разрыв – это функциональный переход в бизнес-процессе, где при переходе от одной функции к другой меняются исполнители этих функций (см. Рисунок далее.)
На основе числа организационных разрывов и функциональных переходов определяется показатель «Фрагментарность процесса (FRAG)».www.bankiram.pro
Анализ оптимизация - Справочник химика 21
Этот процесс логически состоит из итерационного последовательного взаимного чередования этапов синтеза, анализа, оптимизации и модификации некоторого первоначально заданного технологического решения ИЗС. [c.178]Этот внушительный перечень этапов совершенно не обязателен для подавляющего большинства задач, возникающих в инженерной практике. Как правило, решается очень много идентичных задач (регрессионный анализ, оптимизация и др.), для которых в вычислительном центре имеются стандартные программы. Таким образом, обязательными остаются лишь этапы 1 (т. е. специалист, безусловно, должен понимать, чего он хочет) [c.18]
Приведенные соображения применимы к анализу оптимизации любой технологической схемы. Таким [c.27]Выбрав систему разделительных колонок, можно повысить разрешение, уменьшая скорость элюции (см. рис. IV.2), а также подобрать чувствительность детектирования так, чтобы максимальная высота пика составляла 50—70% шкалы регистрирующего прибора. При скоростной хроматографии с использованием л-стирогелЯ или микросферических силикагелей время ГПХ-анализа полимера, включая пробный анализ, оптимизацию и окончательный анализ, занимает не более 1,5 ч. Очевидно, что для быстрого проведения анализа необходимо располагать калибровочными зависимостями для всех используемых в анализе хроматографических колонок и систем колонок. [c.149]
СинтеЗ) анализ, оптимизация [c.41]
Основой решения задач проектирования являются синтез, анализ, оптимизация [6]. Это очень емкие понятия. Их сущность в обычном широком смысле заключается в следующем. [c.41]
Сх е ма ПЬЗ. Взаимодействие синтез — анализ — оптимизация в процессе проектирования [c.43]
Лроцесс принятия решения в проектировании включает формулировку целей, определение ограничений и критерия, выбор метода решения, которое осуществляется на всех этапах (синтез, анализ, оптимизация). В общем виде процесс принятия решения приведен на схеме 111-4. [c.46]
Основными понятиями в проектировании ХТС, как и в других системах, являются синтез, анализ, оптимизация. [c.60]
Таким образом, при синхронной интенсификации возникает проблема оптимизации соотношений и т] для достижения наибольших значений т . Детальный анализ оптимизации при синхронной интенсификации с использованием формулы (4.47) проведен в работе [4.27]. Показано, что существуют оптимальные значения синхронно изменяющихся величин и обеспечивающие максимальное значение теплового КПД Т1 = Эти величины находятся в области Лп Лр 0,5- 0,55. [c.291]
В настоящее время мощным средством повышения эффективности научных исследований при решении задач расчета, анализа, -оптимизации и прогнозирования химико-технологических процессов стал метод математического моделирования [1]. При наличии полной информации о механизме процесса (термодинамике, кинетике, гидродинамике) составляют детерминированную математическую модель, представляющую собой систему дифференциальных уравнений обыкновенных или в частных производных. Для определения неизвестных констант, входящих в систему дифференциальных уравнений и проверки адекватности математической модели процесса, проводится эксперимент. [c.5]
Основные трудности, возникающие при математическом моделировании, анализе, оптимизации и синтезе сложных ХТС, обусловлены многомерностью решаемых задач, связанной с ней проблемой декомпозиции, а также способом представления математического описания отдельных процессов. [c.375]
К функциям обработки данных следует отнести учет, контроль, анализ, оптимизацию, прогнозирование, планирование. [c.26]
Автоматизированная система анализа и синтеза ХТС (АСАС ХТС SYNSYS), разработанная на кафедре кибернетики химико-технологических процессов МХТИ им. Д. И. Менделеева, предназначена для решения широкого круга задач, связанных с цифровым моделированием, анализом, оптимизацией и синтезом оптимальных химико-технологических систем [1, 2]. Она содержит три основных уровня уровень автоматизированного моделирования уровень синтеза ХТС уровень анализа ХТС (рис. 11.1). [c.588]
Совместно с Л.С.Гордеевым и А.Ю.Винаровым сформулированы научные принципы анализа, оптимизации, масштабирования и проектирования биотехнологических процессов. С позиций системного подхода последовательно проведен анализ эффектов и явлений, происходящих в биохимическом реакторе на микро- и макроуровне. Разработаны математические модели, учитывающие кинетику роста микробных популяций, транспорт питательного субстрата к клеткам и гидродинамическую обстановку в реакторе, характеризуемую эффектами се1регации ферментациогшой среды и неидеальностью структуры потоков в реакторе большого объема. Предложена методика решения задачи масштабного перехода от лабораторных установок к промышленным биореакторам на основе вычислительных экспериментов. Показаны направления оптимизащш конструктивных и режимных параметров биотехнологических процессов. [c.13]
Создать методы анализа, оптимизации и проектирования нетрадиционных биотехнологий на основе квалиметрических методов интегральной оценки качества биотехнических систем вида сырье — процесс — устройство — продукт в мясоперерабатывающей промышленности [c.1350]
Общий анализ оптимизации процессов за цикл, проведенный А.З.Федото- [c.12]
Ситуация в анализе с программируемым элюированием аналогична изократическому элюирова1шю в том плане, что удер-л ивание и селективность можно оптимизировать более или менее независимо. Однако, если элюирование ведется в постоянных условиях, оптимизация только удерживания заключается в том, что проводится адаптация основных параметров, в результате которой все коэффициенты емкости должны соответствовать оптимальному диапазону их значений (1анализе оптимизация одного только удерживания заключается в оптимизации характеристик программы (начальные и конечные условия, наклон и форма градиента) во взаимосвязи с физическими параметрами (т. е. скоростью потока и размерами колонки, см. разд. 3.6). [c.328]
При решении задач анализа, оптимизации и синтеза ХТС можно использовать следующие три класса топол огических моделей в виде графов. [c.378]
chem21.info
Оптимизация - анализ - Большая Энциклопедия Нефти и Газа, статья, страница 1
Оптимизация - анализ
Cтраница 1
Оптимизация анализа необходима, поскольку в противном случае продолжительность анализа будет неоправданно велика. Помните о том, что основным достоинством кварцевых капиллярных колонок является возможность их разрезания на отрезки любой длины. [1]
При оптимизации анализа необходимо находить компромисс между воспризводимостью и эффективностью. Если требуется количественно проанализировать пробу, то для получения надежных результатов следует работать с коцентрациями, превышающими границу обнаружения по крайней мере от 10 до 20 раз. [2]
Для оптимизации анализа существуют сложные теоретические выкладки, в которые, однако, включены также субъективные оценки, так что в результате можно получить различные данные. С другой стороны, на практике всегда проводят оптимизацию по методу проб и ошибок. Поэтому в лабораториях, где проводят анализ следовых количеств элементов, обычно получают средние значения из большого числа определений при соблюдении всех требований. Реальная ситуация в лабораториях часто такова, что приобретенные однажды приборы и разработанные методы из соображений экономии и просто по инерции применяют и тогда, когда они уже устарели. Нужно только, чтобы это отставание от современного уровня развития не превышало 10 лет. [3]
Однако при оптимизации анализа с программированием в газовой хроматографии это требование может и не привести к непреодолимым проблемам, так как: 1) процесс оптимизации может быть выполнен применительно к ограниченному числу компонентов образца ( главных компонентов) [14]; 2) изменения в порядке элюирования компонентов маловероятны. [4]
Другой метод оптимизации анализа [58] предполагает использование в качестве критерия для изменения скорости и эффективной высоты теоретической тарелки ВЭТТ. Оптимальное значение температуры находится по величине разности во временах удерживания в анализируемой смеси до появления существенного перекрытия, что фиксируется изменением в площадях пиков. [5]
Усилия, затрачиваемые на разработку и оптимизацию многоколоночного анализа, оказываются оправданными в тем большей степени, чем большее число анализов придется выполнять. [6]
Общий недостаток симплекс-оптимизации, заключающийся в необходимости выполнения большого числа экспериментов, еще более усугубляется при оптимизации анализа с программированием, так как здесь длительность единичного эксперимента больше, чем в изократических условиях ( см. разд. Кроме того, поверхности отклика, получаемые при оптимизации селективности в ЖХ с программированием элюента, изогнуты не меньше, чем получаемые при оптимизации изократического элюирования [27], поэтому и в этом случае вероятность обнаружения локального ( а не глобального) оптимума велика, если применяется симплекс-алгоритм. [7]
Работа в реальном масштабе времени позволяет осуществлять и последнюю ступень автоматизации: управление анализатором с целью оптимизации анализа. [8]
Для изократического анализа справедливо следующее утверждение: чем больше анализируется образцов какого-либо одного типа, тем более оправданы усилия, затрачиваемые на оптимизацию анализа. В анализе с программированием действует обратное правило. [9]
Включение в систему устройств, позволяющих программировать условия разделения ( температуру в ГХ, элюент в ЖХ), может оказаться полезным не только при оптимизации анализа с программированием ( гл. [11]
Если же исследуются образцы неизвестного состава или такие образцы, компоненты которых недоступны в чистом виде, а также если мы не готовы к выполнению большого числа экспериментов ( как это обычно бывает при оптимизации анализа с программированием), приходится полагаться на то что нам удастся идентифицировать все компоненты на каждой из хроматограмм ( см. разд. [13]
Оптимизация анализа необходима, поскольку в противном случае продолжительность анализа будет неоправданно велика. Помните о том, что основным достоинством кварцевых капиллярных колонок является возможность их разрезания на отрезки любой длины. [15]
Страницы: 1 2
www.ngpedia.ru
Сравнительный анализ методов оптимизации
Министерство образования и науки Республики Казахстан
Карагандинский Государственный Технический Университет
Кафедра САПР
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
к курсовой работе
по дисциплине "Теория принятия решений"
Тема: "Сравнительный анализ методов оптимизации"
Руководитель:
(подпись) (дата)
Студент:
(группа)
_____________________
(подпись) (дата)
Караганда 2009
СодержаниеВведение
1. Формулировка математической задачи оптимизации. Основные понятия
1.1 Формулировка математической задачи оптимизации
1.2 Минимум функции одной переменной
1.3 Минимум функции многих переменных
1.4 Унимодальные функции
1.5 Выпуклые функции
2. Прямые методы безусловной оптимизации
2.1 Прямые методы одномерной безусловной оптимизации
2.1.1 Метод деления отрезка пополам (дихотомии)
2.1.2 Метод золотого сечения
2.1.3 Практическое применение прямых методов одномерной безусловной оптимизации
2.2 Методы безусловной минимизации функций многих переменных
2.2.1 Метод циклического покоординатного спуска
2.2.2 Алгоритм Хука-Дживса
2.2.3 Практическое применение прямых методов безусловной многомерной оптимизации
2.2.4 Минимизация по правильному симплексу
2.2.5 Поиск точки минимума по деформируемому симплексу
2.2.6 Практическая реализация симплексных методов
3. Условная оптимизация
4. Линейное программирование
Заключение
Список использованной литературы
Задача оптимизации всегда была весьма актуальной, а в последнее время, с ускоренным развитием различных областей науки и техники, она приобрела еще более весомое значение.
Так как поведение любого физического объекта можно описать уравнением или системой уравнений (т.е. создать математическую модель реального объекта), то задачей инженера является подбор функции с заданной точностью при данных граничных условиях, которая бы могла "показать" оптимальное решение.
В данном курсовом проекте рассмотрены базовые методы оптимизации, которые дают основное представление о теории принятия решений и широко применяются в самых различных сферах.
В достаточно общем виде математическую задачу оптимизации можно сформулировать следующим образом; минимизировать (максимизировать) целевую функцию с учетом ограничений на управляемые переменные.
Под минимизацией (максимизацией) функции n переменных f (x) = (x1 ,.., xn ) на заданном множестве U n-мерного векторного пространства Еn понимается определение хотя бы одной из точек минимума (максимума) этой функции на множестве U, а также, если это необходимо, и минимального (максимального) на множестве U значения f (x). При записи математических задач оптимизации в общем виде обычно используется следующая символика:
f (x) ®min (max),
хÎU
где f (x) - целевая функция, а U - допустимое множество, заданное ограничениямина управляемые переменные.
Если функция f (x) - скалярная, то задача ее оптимизации носит название задачи математического программирования. В этом случае критерий оптимизации один, и, следовательно, речь идет об однокритериальной (одномерной) оптимизации. Если же критериев несколько, то такая задача называется многокритериальной (задачей векторного программирования).
Если область допустимых значений исходной функции задана, то оптимизация называется условной, т.е. имеются ограничения.
Если же ограничений нет, т.е. областью определения является область существования функции f (x), то такая оптимизация называется безусловной.
1.2 М инимум функции одной переменной
Пусть функция f (x) определена на множестве U вещественной оси R.
1. Число х* ÎU называется точкой глобального (абсолютного) минимума или просто точкой минимума функции f (x) на множестве U, если f (x*) £f (x) для всех хÎU.
Значение f* = f (x*) =
называют глобальным (абсолютным) минимумом или просто минимумом функции f (x) на множестве U.Множество всех точек минимума f (x) на U в дальнейшем будет обозначено через U*.
2. Число
ÎU называется точкой локального минимума функции f (x),если для всех xÎU, достаточно близких к , т.е. если существует e > 0 такое, что это неравенство выполняется для любого.Глобальный минимум f (x) является и локальным минимумом, а обратное неверно.
Будем рассматривать функции многих переменных f=f (x1 , …, xn ) как функции, заданные в точках х n-мерного евклидова пространства Е n : f=f (х).
1. Точка х* ÎЕ n , называется точкой глобального минимума функции f (х), если для всех х* ÎЕ n выполняется неравенство f (x* ) £f (х). Значение f (x* ) = =
называется минимумом функции. Множество всех точек глобального минимума функции f (х) будем обозначать через U * .2. Точка
называется точкой локального минимума функции f (х), если существует e-окрестность точки : U n () ={x | r (x, ) * ÎU n () выполняется неравенство f () £f (х).3. Если допустимое множество U в задаче минимизации (максимизации) функции n переменных совпадает со всем пространством E n , то говорят о задаче безусловной оптимизации
, xÎE n .1.4 Унимодальные функции
Если функция f (x) на множестве U имеет, кроме глобального, локальные минимумы, отличные от него, то минимизация f (x), как правило, сильно затрудняется. В частности, многие методы поиска точки минимума f (x) приспособлены только для функций, у которых каждый локальный минимум является одновременно и глобальным. Этим свойством обладают унимодальные функции.
Функция f (x) называется унимодальной на отрезке [а; b], если она непрерывна на [а; b] и существуют числа a и b,
, такие, что:1) если а < a, то на отрезке [a; a] функция f (x) монотонно убывает;
2) если b < b, то на отрезке [b; b] функция f (x) монотонно возрастает;
3) при х Î [a; b] f (x) =f* =
.Множество унимодальных на отрезке [а; b] функций мы будем обозначать через Q [а; b]. Отметим, что возможно вырождение в точку одного или двух отрезков из [a; a], [a; b] и [b; b]. Некоторые варианты расположения и вырождения в точку отрезков монотонности и постоянства унимодальной функции показаны на рисунке 1.
Рисунок 1 - Некоторые варианты расположения и вырождения в точку отрезков монотонности и постоянства унимодальной функции
Основные свойства унимодальных функций:
1. Любая из точек локального минимума унимодальной функции является и точкой ее глобального минимума на отрезке [а; b].
2. Функция, унимодальная на отрезке [а; b], является унимодальной и на любом меньшем отрезке [с; d]
[а; b].3. Пусть f (x)
Q [а; b] и . Тогда:если
, то x* [a; x2 ] ;если
, то x* [x1 ; b],где х* - одна из точек минимума f (x) на отрезке [a; b].
1.5 В ыпуклые функции
Функция f (x), заданная на отрезке [a; b], называется выпуклой на этом отрезке, если для всех х', х"
[а; b] и произвольного числа [0; 1] выполняется неравенствоf [ax'+ (1- a) x"] £af (x') + (l - a) f (x"). (1)
Перечислим основные свойства выпуклых функций.
Если функция f (x) выпукла на [a; b], то на любом отрезке [х'; х"] Ì [a; b] ее график расположен не выше хорды, проведенной через точки графика с абсциссами х' и х" (рисунок 2).
Рисунок 2 - Взаимное расположение
mirznanii.com
Сравнительный анализ методов оптимизации
Министерство образования и науки Республики Казахстан
Карагандинский Государственный Технический Университет
Кафедра САПР
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
к курсовой работе
по дисциплине «Теория принятия решений»
Тема: «Сравнительный анализ методов оптимизации»
Караганда 2009
Введение
Необходимо выполнить оптимизацию заданных целевых функций. Определить параметры заданного геометрического тела методом многопараметрической оптимизации. В процессе решения задач оптимизации должны быть найдены такие значения проектных параметров, при которых целевая функция имеет минимум (или максимум).
Актуальность математического моделирования процессов и явлений заключается в том, что функции и методы их оптимизации, которые исследуется в данном курсовом проекте, довольно часто применяется на практике в различных сферах жизнедеятельности, и их исследование позволило бы сократить временные и материальные затраты предприятий, использующих в производстве данные математические модели.
1. Основы теории оптимизации
Оптимизация – это выбор наилучшего решения. Математическая теория оптимизации включает в себя фундаментальные результаты и численные методы, позволяющие находить наилучший вариант из множества возможных альтернатив без их полного перебора и сравнения.
Для того чтобы использовать результаты и вычислительные процедуры теории оптимизации на практике, необходимо, прежде всего, сформулировать рассматриваемую задачу на математическом языке, т.е. построить математическую модель объекта оптимизации.
Построение математических моделей оптимизации можно условно разбить на следующие основные этапы.
1. Определение границ объекта оптимизации . Необходимость этого этапа диктуется невозможностью учета и исчерпывающего описания всех сторон большинства реальных систем. Выделив главные переменные, параметры и ограничения, следует приближенно представить систему как некоторую изолированную часть реального мира и упростить ее внутреннюю структуру. Может оказаться, что первоначальные границы объекта оптимизации выбраны неудачно. Тогда в одних случаях границы системы следует расширить, а в других – сузить.
2. Выбор управляемых переменных . На этом этапе математического моделирования необходимо провести различие между теми величинами, значения которых можно варьировать и выбирать с целью достижения наилучшего результата (управляемыми переменными), и величинами, которые фиксированы или определяются внешними факторами. Определение тех значений управляемых переменных, которым соответствует наилучшая (оптимальная) ситуация, и представляет собой задачу оптимизации.
3. Формулировка математической задачи оптимизации . Объединяя результаты предыдущих этапов построения математической модели, ее записывают в виде математической задачи оптимизации, включающей построенную целевую функцию и найденные ограничения на управляемые переменные. При записи математических задач оптимизации в общем виде обычно используется следующая символика:
f(xi ) ®min (max), хi Î U
где f(xi ) – целевая функция, а U – допустимое множество, заданное ограничениями на управляемые переменные. Значение параметров f(xi ) ®min (max) при которых достигается min (max), называется оптимальным решением.
2. Численные методы одномерной безусловной оптимизации
Число х* Î U называется точкой глобального (абсолютного) минимума функции f (x) на множестве U, если f (x*) £ f (x) для всех хÎ U.
Значение f * = f (x*) =
называют глобальным (абсолютным) минимумом или просто минимумом функции f (x) на множестве U.Множество всех точек минимума f (x) на U будем в дальнейшем обозначать через U*.
Число
ÎU называется точкой локального минимума функции f (x), если для всех xÎU, достаточно близких к , т.е. если существует e > 0 такое, что это неравенство выполняется для любого.Глобальный минимум f (x) является и локальным минимумом, а обратное, неверно.
Если функция f ( x ) на множестве U имеет, кроме глобального, локальные минимумы, отличные от него, то минимизацияf ( x ) ,как правило, сильно затрудняется. В частности, многие методы поиска точки минимума f ( x ) приспособлены только для функций, у которых каждый локальный минимум является одновременно и глобальным. Этим свойством обладают унимодальные функции.
Функция f ( x ) называется унимодальной на отрезке [а ; b ], если она непрерывна на [а ; b ] и существуют числа a и b,
, такие, что:1) если а < a, то на отрезке [a ; a] функция f ( x ) монотонно убывает;
2) если b < b , то на отрезке [b; b ] функция f ( x ) монотонно возрастает;
3) при х Î [a; b] f ( x ) =f * =
.Возможно вырождение в точку одного или двух отрезков из [a; a], [a; b] и [b; b]. Некоторые варианты расположения и вырождения в точку отрезков монотонности и постоянства унимодальной функции показаны на.
Основные свойства унимодальных функций:
1. Любая из точек локального минимума унимодальной функции является и точкой ее глобального минимума на отрезке [а; b].
2. Функция, унимодальная на отрезке [а; b], является унимодальной и на любом меньшем отрезке [с; d]
[а; b].3. Пусть f (x)
Q [а; b] и . Тогда:если
, то x* [a; x2];если
, то x* [x1; b],где х* – одна из точек минимума f (x) на отрезке [a; b].
Из численных методов одномерной безусловной оптимизации рассмотрим два:
1. метод дихотомии
2. метод золотого сечения
2.1 Метод дихотомии
В этом методе точки x 1 и х 2 располагаются близко к середине очередного отрезка [а ; b ], т.е:
,
где d > 0 – малое число. При этом отношение длин нового и исходного отрезков
близко к 1/2, этим и объясняется название метода.Отметим, что для любых точек x 1 и х 2 величина t > 1/2, поэтому указанный выбор пробных точек объясняется стремлением обеспечить максимально возможное относительное уменьшение отрезка на каждой итерации поиска х*.
В конце вычислений по методу дихотомии в качестве приближенного значения х* берут середину последнего из найденных отрезков [а ; b ], убедившись предварительно, что достигнуто неравенство
.Опишем алгоритм метода деления отрезка пополам.
Шаг 1. Определить x 1 и х 2 по формулам (2.11). Вычислить f (x 1 ) и f (x 2 ).
Шаг 2. Сравнить f (x 1 ) и f (x 2 ). Если
, то перейти к отрезку [а; x 2 ], положив b = x 2 , иначе – к отрезку [x 1 ; b ], положив а = x 1 .Шаг 3. Найти достигнутую точность
Если , то перейти к следующей итерации, вернувшись к шагу 1. Если , то завершить поиск х *2.2 Метод золотого сечения
Рассмотрим такое симметричное расположение точек x 1 и х 2 на отрезке [а ; b ], при котором одна из них становится пробной точкой и на новом отрезке, полученном после исключения части исходного отрезка. Использование таких точек позволяет на каждой итерации метода исключения отрезков, кроме первой, ограничиться определением только одного значения f (x ),так как другое значение уже найдено на одной из предыдущих итераций.
Рассмотрим сначала отрезок [0; 1] и для определенности предположим, что при его уменьшении исключается правая часть этого отрезка. Пусть х 2 = t, тогда симметрично расположенная точка х 1 = 1–t (рис.2.2).
Рис. 2.2.-Определение пробных точек в методе золотого сечения
Пробная точка х 1 отрезка [0; 1] перейдет в пробную точку х 2 ¢= 1–t нового отрезка [0; т]. Чтобы точки х 2 = t, и х 2 ¢= 1–t делили отрезки [0; 1] и [0; t] в одном и том же отношении, должно выполняться равенство
или , откуда находим положительное значение … Таким образом, х 1 = 1–t = , .mirznanii.com
