17

ЛЕКЦИЯ N 10 -11

§ 5 Основы синтеза и теории оптимизации технических объектов

§ 5.1 Основные понятия.

П остановка задачи синтеза. Понятие “синтез” технического объекта (ТО) в широком смысле слова близко по содержанию к понятию “проектирование”. Задача синтеза ТО состоит в том, чтобы по заданному функциональному назначению объекта или закону его функционирования получить проектное решение в виде некоторого описание проектируемого объекта.

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

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

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

Для этой модели необходимо обосновать критерий оптимальности проектируемого объекта и определить множество показателей

Θ = (q₁, …, q_n), на которые наложено ограничение V = (V₁ , …, V_n). Кроме того, формализуя задачу синтеза, необходимо выделить некоторую совокупность независимых переменных Х =( х₁ , …, х_m), фиксация значений которых (то есть некая структура переменных) определяет один из вариантов объекта и его количественные характеристики, в том числе значение критерия оптимальности, а также показателей, принятых в качестве ограничений.

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

Критерий оптимальности F(Х) = F (х₁ , …, х_m) и показатели

Θ(Х) = (q₁, …, q_n), на значения которых наложены ограничения, являются функциями независимых переменных х₁ , …, х_m .

В формализованном виде задача синтеза технических объектов заключается в определении значений независимых переменных

(х₁ , …, х_m), при которых критерий оптимальности

F(Х) = F (х₁ , …, х_m) (10.1)

принимает экстремальное (минимальное или максимальное) значение при условиях

θ_i (х₁ , …, х_m)≤ 0, i = 1, n;

а_j ≤ x_j ≤ b_j j = 1, m. (10.2)

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

θ_i (х₁ , …, х_m, х_m+i) = 0 (10.3)

путем введения дополнительных переменных х_m+i , причем для неравенств вида (10.3) х_m+i≥ 0.

В задачах оптимизации, в которых ограничения имеют вид уравнений, количество ограничений n не может быть больше числа переменных m, т.е. n ≤ m. Разность (n – m) определяет число степеней свободы в данной задаче. Только (n – m) переменных берутся произвольными, значения же остальных переменных определяются из системы ограничений. Если n = m, то число степеней свободы равно нулю и задача в этом случае является чисто алгебраической, то есть оптимизация целевой функции не требуется,- решение получается аналитически и однозначно.

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

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

Рассмотрим в качестве конкретного примера решение упрощенной задачи нелинейного программирования:

минимизировать целевую функцию вида F(Х) = х₁ – х₂

при нелинейных ограничениях на независимые переменные в виде:

Введем дополнительные переменные х₃ , х₄ , х₅ и превратим последние неравенства в систему уравнений, которую разрешим относительно этих введенных переменных

В
идно, что число переменных m = 5, число уравнений n = 3, тогда

(m-n) = 2 –число степеней свободы. Следовательно, имеется возможность геометрической интерпретации задачи в пространстве Е², т.е. на плоскости.

По условию (10.1–10.3) все переменные должны быть положительными, то есть: x_j › 0, j = 1, 5.

Каждое из уравнений(10.4) и неравенств (10.5) определяет некоторую допустимую область в пространстве Е². Так, неравенство х₁ › 0 определяет верхнюю полуплоскость; неравенство х₄ › 0 – полуплоскость, лежащую по одну сторону от прямой 2х₁ – х₂ + 1 = 0, а именно ту, которая содержит начало координат. Область х₄ ‹ 0 является запрещенной (отмечена штриховкой).

Подобные построения для всех х_j показаны на рис. 10.1.Областью существования целевой функции F(Х) является область ОАВСD. Целевая функция принимает минимальное значение на границе области в

точке В.

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

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

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

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

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

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

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

В качестве примера рассмотрим типовую задачу размещения электронных компонентов, входящих в один электронный блок (печатную плату). Аналог лабораторной работы : “Оптимизация … .” От того, как будут размещены микросхемы на определенной печатной плате, зависит длина соединительных проводников, от которых, в свою очередь, зависят время распространения сигналов и уровень помех.

Требуется найти такое размещение компонентов d₁ , d₂ …, d_n на множестве p₁ , p₂ , …, p_m (m › n) монтажного пространства, при котором суммарная длина электрических соединений между компонентами была бы минимальной.

В
ведем псевдобулевы переменные

Т
огда задача размещения может быть сформулирована в виде: минимизировать целевую функцию

где l_ks - расстояние между позициями p_k и p_s; m_ji –число связей между компонентами d_i и d_j .

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

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

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

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

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

x={x} - вектор управляемых параметров, часть множества внутренних (внешних) параметров объекта, изменение которых приводит к улучшению функционирования объекта проектирования;

x^* - оптимальное значение вектора управляемых параметров: такое значение вектора управляемых параметров, при котором функция качества принимает экстремальное значение

F(x) - целевая функция (функция качества): правило предпочтения одних вариантов решения задачи другим.

XD - область допустимых значений вектора управляемых параметров: такое множество векторов управляемых параметров, которые удовлетворяют ограничениям на значения параметров. Ограничения бывают типа равенств  и типа неравенств 

В такой формулировке к задаче параметрической оптимизации ТО могут быть применимы математические методы теории оптимизации.

§5.2 Свойства и методы получения целевой функции

Пусть Y={y_i} - вектор частных критериев. Применяют несколько способов сведения частных критериев к одному общему:

1. Выбор частного критерия в качестве целевой функции

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

1. Аддитивный критерий

,  - весовые коэффициенты, отражающие важность каждого критерия.

1. Мультипликативный критерий

1. Минимаксный критерий (максиминный)

Пусть s_i - количественная оценка степени выполнения критерия y_i . Например s_i =( y_i - Tt_i) / TT_i В качестве целевой функции на каждом шаге оптимизации принимают тот частный критерий, оценка которого в данный момент является наилучшим (минимальным). На следующем шаге критерий может смениться.

, а постановка задачи оптимизации

критерий может быть максиминный, если требуется максимизировать минимальную оценку.

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

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