Консалтология Общая теория консалтинга (стр. 30 )

Поэтому при реальном консультировании (при п>100) получить ре­шение задачи компоновки путем перебора всех вариантов разбиения даже с использованием современных ЭВМ практически невозможно. Для уменьшения перебора задачу компоновки можно сформулировать в терминах целочисленного программирования.

Пусть требуется распре­делить п компонентов электронной схемы между N блоками таким образом, чтобы суммарное число связей между блоками было мини­мально. Введем вектор X переменных консультирования, компоненты xik (i=1,2,…,n, k=1,2,…,N) которого указывают на включение или невключе­ние элемента di D в подмножество Dk, т, е.

Содержательно функция качества F(X) может характеризовать число связей между подмножествами Di (при заданном числе N под­множеств), число подмножеств N, число типов подмножеств Di, опре­деляемых данным разбиением. Очевидно, все перечисленные функции качества F(X) следует минимизировать.

Пусть F(X) характеризует общее число связей между подмноже-стиами Dk, k=1,2,…,N. Тогда задача компоновки формулируется следую­щим образом: минимизировать целевую функцию

(9.14)

при ограничениях

(9.15)

(9.16)

Здесь πij— число связей между элементами di и dj; υ(S)i—значе­ние параметра S для элемента di; V(k)S—ограничение по параметру S, накладываемое на подмножество Dk, причем под параметром υ(S)i эле­мента di может подразумеваться любой показатель, подчиняющийся свойству аддитивности (объем, масса, стоимость, энергоемкость и т. д.),

Целевая функция (9.14) является квадратичной, поэтому задача компоновки, сформулированная в виде задачи (9.14) — (9.16), являет­ся квадратичной задачей дискретного программирования.

Пример 9.3. Задача размещения. После того как решена задача ком­поновки, требуется определенным образом расположить компоненты, входящие в один блок. От того, как будут размещены микросхемы на определенной печатной плате (или любые элементы на плоскости), зависит длина соединительных провод­ников (связей), от которой в свою очередь зависят уровень помех и время рас­пространения сигналов. Подобные задачи получили название задач размещения. В общем случае требуется найти такое размещение компо­нентов d1,d2,...,dn на множестве q1, q2,...,qm (m>n) позиций монтаж­ного пространства, при котором суммарная длина электрических со­единений между компонентами была бы минимальной. Введем псевдо­булевы переменные

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

(9.17)

при ограничениях

(9.18)

Здесь lks — расстояние между позициями qk и qs; тij — число свя­зей между компонентами di и dj.

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

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

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

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

Рассмотрим формальную постановку одной из разновидностей консультационной за­дачи трассировки, а именно — задачи построения связывающих се­тей минимальной длины для цепей αk. Соединяемые по цепи αk точки образуют множество Uk мощностью |Uk|=пk, в котором каждому элементу ukUk в пространстве соответствует одна точка. Введем псевдобулевы переменные

Задача построения минимальной связывающей сети имеет вид: ми­нимизировать целевую функцию

(9.19)

при ограничениях

(9.20)

(9.21)

(9.22)

Здесь К0 — максимально допустимое число соединений, инцидентных одной точке цепи; y(s)ij—вспомогательные переменные.

Условия (9.21), (9.22) гарантируют связность определяемой сети.

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

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

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

Для пояснения сущности задач параметрического синте­за будем использовать геометрическую интерпретацию, связанную с введением m-мерного пространства Ет пространства пара­метров консультирования (управляемых параметров) и k-мерного пространства Ek выходных параметров. Каждой точке пространства Ет и Еk соответствуют векторы X и Y значений переменных консультирования и выходных па­раметров соответствующего варианта КП.

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

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

F(X)→min (9.23)

при ограничениях

g(X)=0 и h(X)≤0, (9.24)

где g(X) и h(X) —векторные функции от X, описывающие систему ограничений на параметры консультирования X.

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

(9.25)

и среднеквадратичная целевая функция

(9.26)

где yj(0) — заданное значение параметра yj; yj(р) — реальное значение этого параметра.

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

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