Лекция 6. Оптимизация проектных решений

 

План лекции

Будут рассмотрены следующие вопросы:

- примеры оптимизационных задач и постановка задачи оптими­зации;

- критерий оптимальности;

- обзор методов оптимизации.

Литература: Л.1, Л.2, Л.3, Л.5,

 

6.1. Примеры оптимизационных задач и постановка задачи оптимизации

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

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

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

Максимизируемые характеристики: скорость, производитель­ность, надежность, пропускная способность, прочность (балки, фун­да­менты) и т.д.

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

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

·  - задачи на нахождение экстремумов;

·  - вариационные задачи;

· - теория игр;

· - теория графов;

· -линейное, нелинейное и динамическое программирование.

 

Примеры проектных оптимизационных задач.

1. Проектируется контроллер для применения в автомати­чес­ких системах управления. Возможные характеристики при реше­нии оптимизационных задач: а) надежность контроллера – должна максимизироваться; б) потребляемая мощность – должна миними­зи­роваться; в) вес (масса) контроллера – должен минимизи­ро­ваваться.

 

2. Проектируется магистральный нефтепровод (рис.6.1). Рас­смотрим постановку задачи в упрощенном виде.

       Рис.6.1. Схема магистрального нефтепровода

 

Задана необходимая пропускная способность нефтепровода

/час – на участке 1 и /час – на участке 2.

Известны: длины  км,  км;  

                С_т1, С_т2, … С_{т n} - стоимость 1 км труб различного       

   диа­­­­­­метра, руб./км (включая затраты на прокладку);

                С_ДНС - затраты  на сооружение одной дожимной  

насос­ной станции.

Необходимо определить число дожимных насосных станций, мес­та их размещения и диаметр труб. При увеличении числа ДНС диа­метр труб может быть уменьшен.

Необходимо минимизировать затраты на строительство магис­трального нефтепровода, т.е. С ® min.

Если учитывать не только капитальные затраты, но и эксплуата­ционные (электроэнергия на питание электродвигателей, отопление зданий ДНС, зарплата персонала и др.) задача усложняется.

 

3. Проектируется магистральный газопровод (рис.6.2):

               Рис.6.2. Схема магистрального газопровода

 

Рассмотрим постановку задачи в упрощенном виде.

Задана необходимая пропускная способность газопровода:

/час - на участке  1 и /час – на участке 2.

Известны: длины км и км;
     С_т1, С_т2, … С_{т n} - стоимость 1 км труб различного диаметра, руб./км (включая затраты на прокладку);

- затраты на сооружение одной компрессорной станции.

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

Если учитывать не только капитальные затраты, но и эксплу­атационные (топливо на газотурбинные установки, отопление зданий КС, зарплата персонала и др.), задача усложняется.

 

4. Проектируется высоковольтная ЛЭП (35, 110, 220 кВ и т.д.).

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

Математические модели оптимизируемых объектов можно харак­теризовать конечной совокупностью числовых параметров, которые можно разделить на три группы:

- внутренние;

- внешние;

- выходные.

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

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

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

Введём следующие обозначения.

Вектор внутренних параметров:         
                                 или  .                      (6.1)

Вектор внешних параметров:

           или  .                    (6.2)

Вектор выходных параметров:

            или  .                      (6.3)

Компоненты векторов  и  являются независимыми перемен­ными, определяющими значения выходных параметров.

Таким образом, существует функциональная связь

                                    .                                        (6.4)

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

              или  .                (6.5)

Следовательно, .

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

                   или  .               (6.6)

Естественно, что  .                                                 (6.7)

Для того, чтобы судить о качестве проектных решений и срав­нивать получаемые решения между собой, нужно иметь некоторый численный критерий оптимальности (показатель оптимальности ре­­ше­­ния) – W.

Конкретный вид критерия W зависит от проектируемого объек­та, от этапа проектирования, от того, какая часть объекта проек­тируется. Простейшая оптимизационная задача – это определение экс­тремума функции одной переменной величины (рис.6.3).

Рис.6.3. Экстремум функции

 

Решение опирается на теорему Ферма: Если функция W = f(z), имеющая производную, при  z = z ₀ принимает минимум или максимум, то производная от этой функции при z=z₀ обращается в ноль.

При разработке САПР объектов определённого класса должна быть найдена зависимость

           ,           (6.8)

где  - внешние параметры;

    - внутренние параметры, которые не могут быть изменены;

    - элементы решения оптимизационной задачи (результаты решения).

Выражение (6.8) означает, что при заданных значениях парамет­ров ;   необходимо найти такие значения элементов решения , которые в зависимости от характера критерия W обращали бы его в максимум или в минимум, то есть

                  W ® max или W ® min.

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

Функциональные ограничения включают в себя условия работо­способности объекта, имеющие принципиальное значение при оценке правильности его функционирования. Эти ограничения задаются в виде системы равенств и неравенств:

                          x_s £ a_s; x_q ³ a_q; x_d = a_d ,                         (6.9)

где a_s, a_q, a_d – заданные числовые значения выходных парамет­ров,

 ;  ;  .

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

Вторая группа ограничений называется критериальными ограни­чениями:

                        x_s ³ a_s; x_q £ a_q; x_d = a_d,                      (6.10)

где a_s, a_q, a_d - заданные числовые значения выходных параметров, .

Примеры критериальных ограничений: ограничения на стои­мость объекта, на быстродействие, время срабатывания, габариты объ­екта и т.д.

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

                                   ;   ,                            (6.11)

где b_j – заданные значения внешних параметров, .

 

 

6.2. Критерий оптимальности

 

Качество проектируемого объекта характеризуется некоторым числовым показателем W, который в результате процедур оптими­зации требуется обратить в экстремум – в максимум, а в неко­торых случаях – в минимум.

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

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

Пусть задан ряд показателей качества проектируемого объекта w_i, , где, например, w ₁- стоимость разработки, w ₂ –коли­че­ствен­ная ха­рак­теристика надёжности, w ₃ – потребляемая мощность; w ₄ – мас­са объекта и т. д.

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

Оптимизационные задачи с несколькими критериями называются многокритериальными.

При нескольких критериях оптимальности w ₁, w ₂, …, w_i, …, w_n мо­гут использоваться различные методы решения поставленной задачи.

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

Предположим, выбран критерий w ₂. Обозначим выбранный кри­те­рий как w _гк = w ₂ (индекс ГК – главный критерий). При проек­ти­ро­вании или конструировании стремятся максимизировать или мини­ми­зи­ровать (в зависимости от того, какая характеристика объекта вы­бра­­на для оптимизации) значение критерия w _гк. На все остальные кри­­те­рии накладываются ограничения вида

                           w ₁ ³ A; w ₃ £ B и т.д.                              (6.12)

Предположим, проектируется электронное устройство и в ка­че­стве w _гк выбрана надёжность. При этом быстродействие w ₁ не должно быть меньше А, а стоимость w ₃ не должна превышать неко­торого зна­че­ния В.

Другой подход состоит в том, что осуществляют объединение различных критериев в один многокомпонентный. Могут исполь­зо­ваться различные способы такого объединения.

1. Строится обобщённый критерий в аддитивной форме

                                 ,                                          (6.13)

где w_i – i-ый частный критерий;

  a_i – весовой коэффициент i-го частного критерия;

  n – количество критериев.

При этом a_i> 0 при тех показателях, которые надо максими­зи­ро­вать, и a_i< 0 при тех показателях, которые необходимо минимизи­ро­вать.

Абсолютные значения весовых коэффициентов a_i соответствуют степени важности соответствующих критериев. Для получения значе­ний весовых коэффициентов используют методы экспертных оценок. Может быть использован метод ранжирования.

В (6.13) все слагаемые должны быть в безразмерной форме, так как нельзя суммировать рубли, тонны, м³ и т.д. Поэтому норми­рую­щие коэффициенты a_i должны иметь такую размерность, что­бы пре­об­разовать соответствующее слагаемое в (6.13) в без­раз­мерную фор­му. Предположим, критерий w ₂ имеет размерность |кг|. Тогда коэф­фи­циент a_i должен иметь размерность 1/кг.

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

                                       .                                 (6.14)

6.2. Обзор методов оптимизации

В процессе автоматизированного проектирования, например, не­ко­торого объекта, требуется определить его параметры  таким образом, чтобы максимизировать надёжность, быстродействие, скорость, точность, производительность и др., мини­ми­зировать стои­мость, габариты, массу и др. Решение задачи обеспе­чивается варьи­рованием параметров Х в некоторой допустимой обла­сти D, которая формируется системой ограничений типа равенств и нера­венств и определяется требованиями технологии.

Основными методами оптимизации в САПР являются поисковые методы, которые основаны на пошаговом изменении тех параметров, которые могут быть изменены в процессе выполнения проектных про­­це­­дур, т.е.

                             ,                                     (6.15)

где приращение Δ Х _k вектора варьируемых параметров вычисляется по формуле

                               .                                     (6.16)

Здесь X_k – значение вектора варьируемых параметров на k-м ша­ге; h – номер шага; g(X_k) – направление поиска. Если выполняется условие сходимости, то реализуется пошаговое (итерационное) при­бли­жение к экстремуму.

Методы оптимизации классифицируются по ряду признаков. В зависимости от числа критериев оптимальности различают методы од­­но­­мерной и многомерной оптимизации. В первых из них критерий – единственный, во вторых – размер вектора W не менее двух. Реаль­ные задачи в САПР – многомерны, методы одномерной оптими­зации играют вспомогательную роль на отдельных этапах многомер­ного поиска.

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

Методы решения оптимизационных проектных задач, в которых критерий оптимизации является функцией n переменных, называют методами математического программирования. (Термин «программи­ро­ва­ние» в данном случае обусловлен тем, что в задачах ищется неко­то­рая программа действий).

В математическом программировании выделяют следующие разделы:

- линейное программирование;

- нелинейное программирование;

- динамическое программирование.

Для случаев, когда критерий W зависит от элементов решения x ₁, x ₂, …, x_n линейно, и ограничения, наложенные на x ₁, x ₂, …, x_n, также имеют вид линейных равенств (или неравенств), максимум (или ми­ни­мум), функция W находится с помощью математических методов линейного программирования.

Задачу линейного программирования можно записать следую­щим образом:

найти x_j³ 0 (j=1, 2, …, n) при ограничениях типа

 , (i=1, 2, …, m₁);

 , (i=m₁₊₁, m₁₊₂, …, m₂);                                 (6.17)

 , (i=m₂₊₁, m₂₊₂, …, m),

которые минимизируют (или максимизируют) линейную функ­цию

                                .                                        (6.18)

В (6.17) и (6.18)  - это параметры проектируемого или конструируемого объекта.

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

Итак, задача линейного программирования состоит в миними­за­ции или максимизации линейной функции при линейных ограниче­ниях. Однако во многих оптимизационных задачах автоматизи­рованного проектирования целевая функция или функции, задающие ограничения, не являются линейными. Такие задачи называются задачами нелинейного программирования.

Оптимизационная задача нелинейного программирования – это задача максимизации или минимизации целевой функции (критерия оптимизации)

                                                                                (6.19)

при условиях   ;

                        ;                                                            (6.20)

                         .

 В (6.19) и (6.20)  - это параметры проектируемого или конструируемого объекта. Условия (6.20) являются ограничениями за­­дачи. Ограничения могут отсутствовать. В этом случае мы имеем задачу безусловной оптимизации.

Для решения задач нелинейного программирования применяется несколько методов.  

Основная идея градиентного метода состоит в замене максими­зируемой (минимизируемой) функции в окрестности конкретной точки её линейным приближением.

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

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

Динамическое программирование представляет собой метод оп­ти­мизации решений, специально приспособленный к многоша­го­вым или многоэтапным операциям.

Поставим задачу динамического программирования в общем виде. Пусть имеется операция Q с аддитивным критерием оптималь­ности, распадающаяся (естественно или искусственно) на m шагов. На каждом шаге принимается какое-то решение w_i. Требуется найти оптимальное решение

                              W =( w ₁, w ₂, …, w_m ),

при котором критерий оптимальности (показатель эффективности)

                                     

обращается в максимум.

Поставленную задачу можно решать по-разному: или искать сра­зу оптимальное решение W, или же находить его постепенно, шаг за шагом, на каждом этапе расчёта оптимизируя только один шаг.

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

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

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

Предположим, что эта процедура выполнена и для каждого исхо­да (m-1)-го шага. Теперь мы можем оптимизировать решения на пред­последнем (m-1) шаге. Сделаем все возможные предположения о том, чем может закончиться (m-2)-й шаг, и для каждого из этих пред­по­ло­жений найдем такое решение на (m-1)-м шаге, чтобы вы­игрыш за два последних шага (из которых последний уже оптими­зи­ро­ван) был мак­симизирован. Далее оптимизируется решение на (m-2)-м шаге и т. д.

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

Действительно, пусть нам известно начальное состояние процесса, обозначим его S₀. На первом шаге надо применить усло­в­ное оптимальное решение, выработанное для первого шага, относя­щееся к состоянию S₀. В результате этого решения после первого ша­га система перейдёт в другое состояние S₁, но для этого состояния мы снова знаем условное оптимальное решение на втором шаге w₂ и так да­лее. Таким образом, будет найдено оптимальное решение , приводящее к максимально возможному значению критерия W_max.

Таким образом, при оптимизации методом динамического программирования многошаговый процесс проходится дважды:

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

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

Заключение

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

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

 

Вопросы для самоконтроля

1. С какой целью при автоматизированном проектировании применяются методы оптимизации?

2. Назовите некоторые максимизируемые и минимизируемые характе­рис­тики проектируемых объектов?

3. Приведите примеры проектных оптимизационных задач?

4. В моделях оптимизируемых объектов какие параметры являются внут­ренними, внешними и выходными?

5. Какие параметры называют параметрами оптимизации?

6. Что собой представляет критерий оптимальности?

7. С какой целью в оптимизационных задачах используются ограничения?

8. Какие задачи оптимизации называются однокритериальными?

9. Какие задачи оптимизации называются многокритериальными?

10. Как на базе частных критериев осуществляется создание обобщённых критериев оптимальности?

11. Как формулируется задача линейного программирования?

12. Как формулируется задача нелинейного программирования?

13. Как формулируется задача динамического программирования?

 

 

⇐ Предыдущая123456789Следующая ⇒

Поделиться: