ыфсы. Конспект лекций Санкт Петербург
 Скачать 1.77 Mb.
|
|
Эффективность оптимизационных методов, позволяющих осуществить выбор наилучшего варианта без непосредственной проверки всех возможных вариантов, тесно связана с широким использованием достижений в области математики: теории матриц, элементов линейной и не- линейной алгебры и дифференциального исчисления, а также положений математического ана- лиза. Задачи оптимизации с точки зрения математической постановки относятся к задачам математи- ческого программирования и части науки, называемой исследованием операций. Системный анализ и принятие решений Макаров Л.М. 57 Важным этапом изучения явлений, предметов, процессов является их систематизация. Резуль- татом строгой систематизации является классификация. Классификация осуществляется по не- скольким признакам: область применения, содержание задачи, класс математической модели. Приложение методов оптимизации достаточно широкое: – проектирование структурных элементов систем и процессов; – планирование стратегий капитальных вложений; – определение оптимальных маршрутов движения грузового транспорта; – дислокация вооруженных сил; – проектирование составных частей машин и сооружений; – планирование и анализ функционирования существующих систем; – инженерный анализ и обработка информации; – управление динамическими системами. В настоящем пособии из всего обширного круга задач, решаемых методами оптимизации, рас- сматриваются только задачи оптимизации технических решений, связанных с обеспечением производственной, деятельности промышленных предприятий. Обеспечение производства включает организацию и управление, проектирование изделий, разработку технологических процессов (в табл. 4.1). Таблица 4.1 Области применения задач оптимизации Задачи организации и управления включают в себя оптимизацию объема и характера выпускае- мой продукции, снабжения и сбыта, маркетинга, распределения и использования станочного парка, распределения людей по рабочим местам и т.п. Все эти задачи можно отнести к ресурс- ным, к классу задач распределения ресурсов. Объекты проектирования характеризуются устройством и действием. Устройство определяется структурой и параметрами. Действие характеризуется процессом функционирования. Необходимость оптимизации возникает при решении всех трех типов во- просов. Технологический процесс определяется последовательностью работ, которые обеспечивают превращение сырья в готовую продукцию. Такую последовательность работ называют маршру- том. Каждая операция, входящая в маршрут, характеризуется режимом обработки. Задачи, тре- бующие оптимизационного решения, могут быть и при выборе маршрута и при определении параметров операции. Для решения рассмотренных задач используются различные математические модели, которые классифицируются по следующим элементам: Системный анализ и принятие решений Макаров Л.М. 58 исходным данным, искомым переменным, зависимостям, описывающим целевую функцию и ограничения. Исходные данные, которые заданы определенными величинами, называют детер- минированными. Исходные данные, например амплитуды колебаний вращающегося ротора бумагоделательной машины, зависят от ряда случайных факторов. Такие исходные данные называют случайными величинами. Переменные могут быть непрерыв- ными и дискретными. Непрерывными называются такие величины, которые в заданном интер- вале могут принимать любые значения, например, масса 1 м2 бумаги, скорость бумагоделатель- ной машины и т.д. Дискретными, или целочисленными, называют такие величины, которые мо- гут принимать только целые значения, например количество тракторов. Зависимости между переменными могут быть линейными и нелинейными. В линейные зависи- мости переменные входят в первой степени, в них нет произведений переменных. В нелиней- ных зависимостях переменные имеют разные степени, могут быть трансцендентными или вхо- дят в виде произведений. Структура элементов модели представлена на рис. 4.1. Рис. 4.1. Структура элементов математических моделей оптимизации Сочетание различных элементов модели требует различных методов решения оптимиза- ционных задач. Классы задач оптимизации приведены в табл. 4.2. Задачи оптимизации подраз- деляются также по форме, по наличию ограничений, по виду переменных и по другим призна- кам (рис. 4.2). Таблица 4.2. Классы задач оптимизации Системный анализ и принятие решений Макаров Л.М. 59 По форме целевой функции оптимизация связана с определением максимума или минимума функции. По наличию ограничений могут быть задачи условной и безусловной оптимизации. Задача условной оптимизации – задача с ограничениями. Задача, в которой нет ограничений, называется задачей безусловной оптимизации. Рис. 4.2. Классификация задач оптимизации Задачи с нелинейной целевой функцией называются задачами нелинейного программирования. Эти задачи можно классифицировать на основе структурных особенностей нелинейных целе- вых функций. Если f(x) – квадратическая функция, то присутствует задача квадратического программирования; если f(x) – отношение линейных функций, то имеется задача дробно-линей- ного программирования и т. д. 4.2. Методология оптимизации Постановка задачи оптимизации Первым и наиболее важным этапом оптимизации технических решений является постановка задачи оптимизации. Корректная постановка задачи служит ключом к успеху оптимизацион- ного исследования и ассоциируется в большей степени с искусством, нежели с точной наукой. Искусство постановки задачи постигается в практической деятельности на примерах успешно реализованных разработок и основывается на четком представлении преимуществ, недостатков и специфических особенностей различных методов оптимизации. Считается, что на постановку задачи оптимизации специалист затрачивает 60 % времени, а на решение задачи только 40 %. Следует также заметить, что далеко не все решения задач оптимизируются. Последовательность процесса постановки задачи инженерной оптимизации: 1) установление границ подлежащей оптимизации инженерной системы; 2) определение количественного критерия, на основе которого можно провести анализ вариан- тов с целью выявления наилучшего; 3) выбор внутрисистемных переменных для определения характеристик и идентификации вари- антов; Системный анализ и принятие решений Макаров Л.М. 60 4) определение ограничений (зависимостей между переменными); 5) определение граничных условий, показывающих предельно допустимые значения искомых переменных; 6) построение оптимизационной модели, отражающей взаимосвязи между переменными и представляющей собой некоторый набор уравнений и неравенств. Эта последовательность действий и составляет содержание процесса постановки задачи инже- нерной оптимизации. Установление границ системы Прежде, чем приступить к оптимизационному исследованию, важно четко определить границы изучаемой системы. Система предстает как некоторая изолированная часть реального мира. При проведении анализа обычно предполагается, что взаимосвязи между системой и внешней средой зафиксированы на некотором выбранном уровне представления. Границы системы задаются пределами, отделяющими систему от внешней среды. Поскольку между системой и внешней средой или над системой имеются определенные связи, установле- ние границ системы является первым шагом в процессе приближенного описания реальной си- стемы. Расширение границ системы повышает разрядность и сложность многокомпонентной системы и, следовательно, в значительной мере затрудняет ее анализ. Очевидно, что в инженер- ной практике следует, насколько это возможно, стремиться к разбиению больших сложных си- стем на относительно небольшие подсистемы, которые можно изучать по отдельности. Однако при этом необходимо иметь уверенность в том, что такая декомпозиция не приведет к излишнему упрощению реальной ситуации. Следует иметь в виду, что ошибка в выборе границ системы может привести к суб оптимизации, при которой оптимальное решение для одной со- ставной части системы приводит к неоптимальному решению всей системы. Для примера рассмотрим задачу проектирования спираль- ной пружины минимальной массы, входящей в состав виброизолятора машинного агрегата и работающей на сжатие под действием осевой нагрузки (рис. 4.3.). Рис. 4.3 Макет системы исследования В данном случае границы системы определяются пружи- ной и приложенной к ней нагрузкой. Можно расширить границы, например, до вибро изолятора, в состав которого входит эта пружина, или до всего машинного агрегата, учитывая таким образом действие на пружину еще ряда дополнительных факторов. Определение первичного количественного критерия Принимающий решение должен абсолютно точно представлять, в чем заключается оптималь- ность принимаемого решения, т.е. по какому критерию (от греч. criterion – мерило, оценка) при- нимаемое решение должно быть оптимально. Критерий часто называют целевой функцией, а в математических работах - функционалом. Системный анализ и принятие решений Макаров Л.М. 61 В качестве критерия, на основе которого можно оценить техническое решение, могут быть эко- номические, технологические или иные факторы, например капитальные затраты, издержки в единицу времени, чистая прибыль в единицу времени, продолжительность процесса производ- ства изделия, минимизация потребляемой энергии, минимизация массы изделия и др. Важно отметить, что только один критерий может использоваться при определении оптимума, так как невозможно получить решение, которое одновременно обеспечивает оптимум по не- скольким критериям, например невозможно обеспечить одновременно минимум затрат на изго- товление, максимум надежности, минимум потребляемой энергии и минимум массы изделия. При определении оптимума обычно принимают один из критериев, который считается первич- ным, остальные критерии являются вторичными. Первичный критерий используется при опти- мизации как характеристическая мера, а вторичные критерии порождают ограничения оптими- зационной задачи, устанавливающие диапазоны изменения соответствующих показателей от минимальных до максимальных приемлемых значений. Так, в рассматриваемом примере в ка- честве целевой функции берется по заданию масса пружины, которая должна быть минимальна. Хотя за целевую функцию могли быть приняты критерии прочности, предотвращение резо- нанса Целевая функция записывается в виде: f(x) = P n (t) Переменные должны адекватно описывать допустимые проекты или условия функционирова- ния системы. Переменные выбираются таким образом, чтобы все важнейшие технико-экономи- ческие решения нашли отражение в формулировке задачи. Очень важно ввести в рассмотрение все основные переменные, но не менее важно «не перегружать» задачу большим количеством мелких, несущественных переменных, т. е. при выборе независимых переменных следует рас- сматривать только те переменные, которые оказывают существенное влияние на характеристи- ческий критерий, выбранный для анализа сложной системы. При выборе независимых переменных учитывают различие между переменными, значения ко- торых могут изменяться в достаточно широком диапазоне, и переменными, значения которых фиксированы и определяются внешними факторами. Последние могут предполагаться постоян- ными и подверженными флуктуациям вследствие воздействия внешних или неконтролируемых факто- ров. Исключение возможных альтернатив может привести к получению суб оптимальных решений. Например, при проектировании аппарата можно рассматривать его высоту, диаметр, толщину стенки как независимые переменные, но если исключить возможность использования в аппа- рате, например, компрессора для повышения рабочего давления, то получится решение весьма низкого качества, так как не учтена стоимость компрессора. Определение ограничений и граничных условий Как уже отмечалось, вторичные критерии при определении оптимума представляются в виде ограничений. В рассматриваемом примере кри- териями, представленными в виде ограничений, являются: 1) предотвращение разрушения материала τ ≤ [τ], где τ – касательные напряжения (напряжения сдвига) в проволоке; [τ ] – допустимое касательное напряжение; 2) предотвращение резонанса в пружине ω – ω 0 > 0, где ω – частота динамических воздействий на пружину; ω0 – собственная частота колебаний пружины. То есть пружина должна работать в до резонансном режиме. Системный анализ и принятие решений Макаров Л.М. 62 Граничные условия показывают предельно допустимые значения искомых переменных. В об- щем случае граничные условия могут быть двух сторонними: a i ≤ x i ≤ b i Возможны частные случаи. В технических расчетах искомые величины бывают положитель- ными или равными нулю, т.е. накладывается требование неотрицательных перемещений, xi ≥ 0. Итак, граничные условия показывают предельно допустимые значения искомых переменных. Ограничения – это зависимости между переменными, которые могут быть детерминирован- ными и статистическими. Значения переменных, удовлетворяющих граничным условиям и ограничениям, называют до- пустимым решением задачи. Построение модели На завершающем этапе постановки задачи строится модель, описывающая взаимосвязи между переменными задачи и отражающая влияние независимых переменных на степень до- стижения цели, определяемой целевой функцией. Моделью называется упрощенное математическое представление системы. Модель пред- ставляет некоторый набор уравнений и неравенств, которые определяют взаимосвязь между пе- ременными системы и ограничивают область допустимых значений этих переменных. Элементы модели содержат всю информацию, которая используется при расчете проекта или прогнозировании характеристик инженерной системы. Очевидно, что процесс построения мо- дели является весьма трудоемким и требует четкого понимания специфических особенностей рассматриваемой системы. Существует даже такое мнение, что составление модели – это искус- ство, творчество. До какого-то уровня научить этому можно, но не более того. Там, где творче- ство, там важны личные качества, знания, способности. Такие качества всегда ценились очень высоко. Ведь, если двое смотрят на одно и то же, это не значит, что оба видят одно и то же. И утверждение древних греков «Если двое делают одно и то же, это не значит, что получится одно и то же», в полной мере относится к составлению математических моделей. Заметим, что в задачу могут включаться требования, которые оказываются противоречи- выми, невыполнимыми. Такие задачи называются несовместимыми, несбалансированными, и их необходимо выявлять на стадии постановки задачи оптимизации. Математическая постановка задачи оптимизации в общем случае включает три составляющие: целевую функцию (ц.ф.), ограничения (огр.) и граничные условия (гр.у.). Математическая модель оптимизационной задачи выглядит в общем случае в виде: Таким образом, оптимизационная задача включает целевую функцию и сложную систему нера- венств. 4.3. Метод безусловной оптимизации В этом случае рассматриваем имеет место свойства функции одной переменной Пусть f(x) – целевая функция, S – область допустимых значений. f(x) = x 3 +2x 2 − x+3 для всех x 𝝐 S = {-5 ≤ x ≤ 5}. Системный анализ и принятие решений Макаров Л.М. 63 Непрерывная функция – функция, обладающая свойством непрерывности в каждой точке х, принадлежащей области допустимых значений. Виды функций даны на рис. 4.5. Функция f(x) является монотонной, если для двух произвольных точек х1 и х2 при х1 ≤ х2 вы- полняется одно из следующих неравенств: f(x1) ≤ f(x2) – монотонно возрастающая функция; f(x1) ≥ f(x2) – монотонно убывающая функция. Функция f(x) является унимодальной на отрезке a < x < b в том случае, если она монотонная по обе стороны от единственной на интервале оптимальной точки х*. Функция f(x), определенная на множестве S, достигает своего глобального минимума в точке х Г в том и только в том случае, если f(x Г ) ≤ f(x) для всех х 𝝐 S. Если функция унимодальна, то локальный оптимум автоматически является глобальным. Если функция не является унимодальной, то возможно наличие нескольких оптимумов. Глобальные оптимумы можно определить путем нахождения всех локальных оптимумов и выбора наимень- шего (минимум) или наибольшего (максимум) из них (рис. 4.6). Для оптимизации функции одной переменной используется множество алгоритмов наиболее часто применяемых методов: правило исключения интервалов, методы полиноминальной Системный анализ и принятие решений Макаров Л.М. 64 аппроксимации и методы с использованием анализа производных. Все методы одномерной оп- тимизации основаны на предположении, что исследуемая целевая функция в допустимой обла- сти обладает свойством унимодальности, так как для унимодальной функции f(x) сравнение значений f(t) в двух различных точках интервала поиска позволяет определить, в какой из за- данных двумя указанными точками под интервалов точки оптимума отсутствуют. Рис. 4.6. Локальные и глобальные оптимумы 95 Сущность метода полиноминальной аппроксимации заключается в том, что непрерывную функцию в некотором интервале можно аппроксимировать полиномом достаточно высокого порядка. Следовательно, если функция унимодальна и найден полином, который достаточно точно ее аппроксимирует, то координаты точки оптимума функции можно оценить путем вы- числения координаты точки оптимума полинома. Методы с использованием анализа производных заключаются в следующем: необходимыми условиями того, что точка х* является точкой локального минимума (максимума) дважды диф- ференцируемой функции f(x) на интервале (a, b), являются следующие отношения: Системный анализ и принятие решений Макаров Л.М. 65 Условия являются необходимыми, но недостаточными, так как они характерны не только для точек оптимума, но и для то- чек перегиба (рис. 4.7). Несмотря на то, что безусловная оптимизация функ- ции одной переменной – это наиболее простой тип оп- тимизационных задач, она занимает центральное ме- сто в теории оптимизации как с теоретической, так и с практической точек зрения. Это связано с тем, что задачи однопараметрической оптимизации достаточно часто встречаются в инженер- ной практике и, кроме того, находят свое применение при реализации более сложных итератив- ных процедур многопараметрической оптимизации. Безусловная многопараметрическая оптимизация Методы безусловной оптимизации функции многих переменных отличаются относительно высоким уровнем развития по сравнению с дру- гими методами нелинейного программирования. К ним относятся методы прямого поиска, ос- нованные на вычислении только значений целевой функции, методы, в которых используются значения первых и вторых производных. Методы прямого поиска приемлемы лишь для исследования непрерывных циклоидальных функций. Применяются следующие методы прямого поиска: − эвристические, построенные на интуитивных геометрических представлениях; − поиск по комплексу; − по методу Хука−Дживса; − теоретические, основанные на математических направлениях; − метод сопряжения направлений Пауэлля. Особенности методов прямого поиска: − относительная простота соответствующих вычислительных процедур, которые быстро реали- зуются и легко корректируются; − не требуют явного выражения целевой функции в аналитическом виде; − могут требовать более значительных затрат времени по сравнению с методами, основанными на производных. 4.4. Линейное программирование Задачами линейного программирования называются оптимизационные задачи, в которых огра- ничения представляются в виде равенств или неравенств и целевая функция линейна. Это наиболее часто применяемый метод решения оптимизационных задач, особенно в экономике и управлении. Имеется целый ряд различных методов линейного программирования; одни являются специали- зированными, другие носят общий характер. В пособии рассматривается два метода общего назначения: метод графического линейного про- граммирования и симплексный метод. Метод графического линейного программирования нагляден и прост, но ограничен только задачами с двумя переменными. Симплексный метод не |