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

Тема 1. ВВЕДЕНИЕ. ОСНОВНЫЕ ПОНЯТИЯ ОПТИМАЛЬНОГО ПРОЕКТИРОВАНИЯ.

1.1 Общие положения

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

ММ ИТП по назначению и способам реализации делятся на две части:

1) ММ и построенные на их основе математические модели, описывающие объекты проектирования (их части) или вычисляющие необходимые свойства и параметры объектов;

2) ММ, представляющие формализованное описание информационных технологий проектирования.

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

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

Для совершенствования ММ выделяют два направления работ:

1) развитие методов получения оптимальных проектных решений, в том числе ориентированных на ИТП;

2) совершенствование и типизацию самих процессов ИТП.

Анализ существующих методов решения оптимизационных задач ИТП показал следующее:

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

2) теоретически наиболее эффективными при поиске оптимальных проектных решений являются методы нелинейного математического программирования;

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

1.2 Задачи синтеза и оптимизации в процессе проектирования

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

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

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

Синтез подразделяют на структурный и параметрический.

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

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

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

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

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

http://www.viktoriastar.ru/konstruirovanie/289-opredelenie-optimalnogo-proektirovaniya.html

«Оптимальным проектным решением называется такой допустимый проект, реализация которого приводит к созданию объекта, настолько хорошего в отношении некоторой количественной меры его эффективности и полезности, насколько это возможно в заданных условиях.» http://allmehanika.ru/print:page,1,286-optimalnoe_proektirovanie.html

В этих определениях выделяются такие ключевые положения:

· наличие различных вариантов решения;

· наличие количественной меры для оценки этих вариантов, достижение экстремального значения которой является целью работ;

· наличие некоторых ограничений в виде технических требований.

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

Пример 1 [Дитрих Я. Проектирование и конструирование. Системный подход. 1981]: На рисунке показаны возможные пути, соединяющие рыбацкий поселок с лодочным причалом. Точка А – начало пути из поселка, точка B – место расположения причала. Дорога до причала фактически соответствует не прямой, проходящей через точку C’, а ломаной, проходящей через точку C. Этот путь представляет собой результат инстинктивного стремления к минимизации усилий по преодолению пути из A в B. Такая минимизация учитывает различные сопротивления движению по лугу и по песчаному пляжу.

Аналитически эта ситуация может быть описана так:

E = αa + βb ® E_min,

где a – длина участка дороги по лугу, b – длина участка дороги по пляжу, α – коэффициент затрат энергии на лугу, β – коэффициент затрат энергии на пляже, E – затраты энергии на преодоление дороги ACB.

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

(β/α ® 1) Þ (C ® C’),

(β/α ® ¥) Þ (C ® C”),

В этом примере существует задача оптимизации, поскольку:

· существует много вариантов пути из A в B, выбор пути не очевиден и не однозначен;

· существует критерий в виде затрат энергии на прохождение этого пути.

Пример 2 [ Задачі оптимізації / Л.М. Вивальнюк та ін., 1991]:

Очевидно, что h² = d² – b². Прочность бруса можно выразить как P = k×b×(d² – b²), где k – коэффициент пропорциональности.

Производная этой функции равна P¢ = k× (d² – 3b²). Единственным решением уравнения (d² – 3b²) = 0 является число b = d/Ö3. Отсюда h = Ö(2d/3).

Пример 3 [ Задачі оптимізації / Л.М. Вивальнюк та ін., 1991]: Стоимость топлива, потребного для движения теплохода со скоростью b узлов (миль в час), пропорциональна кубу его скорости и составляет a грн/час. Прочие затраты составляют c грн/час. Найти наиболее экономичную скорость движения теплохода v_opt.

Стоимость топлива при скорости 1 узел составляет a/b³ грн/час, а при скорости v узлов – av³/b³ грн/час. С учетом прочих расходов общая стоимость часовой эксплуатации составит (av³/b³ + c) грн.

За время t часов теплоход пройдет путь в S морских миль. Тогда t = S/v, а суммарная стоимость эксплуатации теплохода за это время составит (в грн.)

R = (av³/b³ + c)×S/v = S×(av²/b³ + c/v).

Производная этой функции R¢ = S×(2av/b³ – c/v²) приобретает нулевое значение в точке v = (cb³/2a)^⅓, что и соответствует искомой наивыгоднейшей скорости.

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

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

Однако такой простой путь – дифференцирование целевой функции – возможен далеко не всегда. Как отмечено в работе [Вентцель Е.С. Исследование операций: задачи, принципы, методология. 1988], во-первых, при большом числе аргументов задача решения системы уравнений может оказаться не проще, а сложнее, чем непосредственный поиск экстремума. Во-вторых, когда на значения аргументов наложены ограничения, экстремум может достигаться не в той точке, где производные равны нулю, а где-то на границе допустимой области, причем чаще всего в углу области, где дифференцирование вообще невозможно. В-третьих, в некоторых задачах функция цели может вообще не иметь производной, например, может быть определена только для целочисленных значений аргументов. Все эти причины привели к необходимости разработки специальных методов для решения задач оптимизации.

Пример 4 [Егер и др. Основы автоматизированного проектирования самолетов, 1986. Гл. 4. Методы оптимизации проектных решений]:

… Предположим, проектировщик стоит перед проблемой выбора параметров крыла, максимизирующих аэродинамическое качество. Иными словами, ему необходимо найти максимум функции F(x₁, x₂), где x₁ и x₂ – проектные переменные, например, удлинение крыла и удельная нагрузка на крыло, а F – аэродинамическое качество. Графическая интерпретация этой задачи показана на рисунке, где проектные переменные представлены в нормализованном (безразмерном) виде.

Очевидно, что максимум критерия F достигается в точке A (вершине «холма») при значениях параметров x1opt и x2opt. Точка A соответствует строгому математическому оптимуму. Однако этот оптимум может находиться за пределами допустимой области изменения проектных параметров, определяемой ограничениями на их величины. Например, максимально допустимое удлинение крыла может быть ограничено условиями хранения самолета в ангаре, а удельная нагрузка на крыло – скоростью захода на посадку. На рисунке ограничения показаны штриховкой. При наличии ограничений оптимальное значение критерия достигается в точке A’, лежащей на границе допустимой области и соответствующей значениям параметров x’1opt и x’2opt. Точку A’ называют условным оптимумом функции F.

Однако это не единственная сложность при решении практических задач оптимального проектирования. Целевая функция может иметь несколько экстремальных значений. Это создает опасность нахождения локального оптимума (точка B) вместо глобального (точка A). Топография целевой функции часто характеризуется рядом особенностей, затрудняющих нахождение экстремума. К таким особенностям относятся «гребни», «овраги», седловые точки и др. …

[ САПР-1986, кн. 5 «Автоматизация функционального проектирования», гл. 3 «Процедуры параметрической оптимизации»]

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

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

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

Пример 5. (Определение оптимального плана выпуска продукции).

Имеется m видов резервов в количестве, определяемом вектором

, которые могут использоваться для производства n видов продукции.

, ; - норма расхода i -го ресурса на производство одной единицы j -й продукции.

, . - удельный доход, характеризующий эффективность выпуска единицы j -й продукции.

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

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

.

Учитывая имеющееся количество ресурсов, запишем ограничения, которые определяют допустимую область решений:

, .

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

На практике часто приходится сталкиваться с ситуацией, когда операция не может быть оценена с помощью единственного критерия эффективности. Тогда операция описывается с помощью вектора Ф=(Ф₁, Ф₂,..., Ф_n) критериев эффективности, причем, как правило, одни показатели необходимо обратить в максимум, а другие — в минимум. Задачи такого типа называются задачами векторной или многокритериальной оптимизации.

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

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

Требуемые соотношения между выходными параметрами и техническими требованиями (ТТ) называют условиями работоспособности и записывают в виде

y_i < TT_i, i Î [1:k];

y_j > TT_j, j Î [k+1:l]; (1.1)

y_r = TT_r ± Dy_r; r Î [l+1:m],

где Dy_r – допустимое отклонение r -го выходного параметра от указанного в ТЗ значения TT_r.

Пример: Тактико-технические требования к самолету [Основы общего проектирования самолетов с ГТД, ч.1, с.175]

Тактические требования:

· диапазон скоростей (V_min, V_max);

· диапазон высот (H_min, H_max);

· диапазон дальностей (с максимальной нагрузкой, с максимальным запасом топлива и др.);

· скороподъемность Vy_max;

· минимальный радиус виража r_min;

· масса целевой нагрузки (коммерческой или боевой);

· состав оборудования и вооружения;

· взлетно-посадочные характеристики (V_взл, V_пос, L_разб, L_проб);

· уровень заметности (для военных самолетов) и др.

Технические требования

· требования аэродинамики (запасы продольной статической устойчивости, ограничения на нагрев конструкции и др.);

· требования прочности и жесткости;

· требования надежности (ресурс, число посадок и др.);

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

· требования эксплуатационной технологичности (трудоемкость и себестоимость технического обслуживания);

· способность к модификации.

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

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

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

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

В зависимости от количества управляемых параметров различают методы одномерного и многомерного поиска. Если размерность вектора X равна 1 (n =1), то задача называется однопараметрической задачей оптимизации (одномерной задачей оптимизации). Если размерность вектора X больше 1 (n >1), то задача называется многопараметрической задачей оптимизации (многомерной задачей оптимизации). Одномерный поиск может рассматриваться как самостоятельная задача или как часть процедуры многомерного поиска. Рассмотрим методы решения задач одномерной оптимизации.

Дата добавления: 2014-12-16