ББК 32.97 К 70 УДК 681.31.00 K'ad^p"!3 ^Конструирование электронно-вычислительной аппараТур^ Ленинградского института точной механики и """"профессор, доктор техн. наук Е. Л. Глориозов (Московский институт электронного машиностроения) Корячко В. П. и др. К70 Теоретические основы САПР: Учебник для ву- зов/В. П. Корячко, В. М. Курейчик, И. П. Норен- ков.—М.: Энергоатомиздат, 1987.—400с.: ил. Изложены теоретические основы САПР, их технические и про граммные средства. Значительное внимание Улелшо о^ошъш cw^ нйям.об информационных потоках, структурах и •тex»mecv•^л'-pewsax САПР, об устройствах машинной графики, программном °бес"мении технических средств, системах управления банками данных, способах ^"дТя^Ту^тов, обучающихся по специальности «Конструирование и производство электронно-вычислительной аппаратуры». К 2405000000-319 ^_„ 051(01)—87 ББК 32,97 Энергоатомиздат, 1987 ПРЕДИСЛОВИЕ Стратегическая линия КПСС на ускорение социально- экономического развития—это выход в короткие сроки на самые передовые научно-технические позиции, на высший мировой уровень производительности общественного труда. Для реализации этой стратегии необходимо создание и бы- строе качественное внедрение высокоэффективных машин, оборудования, приборов и технологических процессов, обе- спечивающих 'высокие темпы научно-технического про- гресса. В решениях XXVII съезда КПСС по «Основным направ- лениям экономического и социального развития СССР на 1986—1990 годы и на период до 2000 года» сказано: «Внед- рять автоматизированные системы в различные сферы про- изводства, и в первую очередь в проектирование, управле- ние оборудованием и технологическими процессами». Современные задачи, возникающие перед наукой и тех- никой, вызывают необходимость проектирования все более сложных технических объектов в сжатые сроки. Удовлетво- рить противоречивые требования повышения сложности объектов, сокращения сроков и повышения качества про- ектирования с помощью простого увеличения численности проектировщиков нельзя, так как возможность параллель- ного проведения проектных работ ограничена и численность инженерно-технических работников в проектных организа- циях страны не может быть сколько-нибудь заметно увели- чена. Выходом из этого положения является широкое при- менение вычислительной техники для решения проектных задач (автоматизация проектирования). Цель автоматизации проектирования—обеспечить без- дефектное проектирование, снизить материальные затра- ты, сократить сроки проектирования и ликвидировать рост количества инженерно-технических работников, занятых проектированием. Знание математического аппарата, применяемого в ин- женерных исследованиях, умение пользоваться математи- ческими моделями при оптимальном проектировании реаль- ных объектов и систем, знание программных и технических средств САПР и умение пользоваться ими в качестве ин- I* я струмента проектировщика должны позволить современ- ным инженерам ставить и решать задачи автоматизации проектирования по отраслям техники. В связи с тем что существенно изменяются функции ин- женера в процессе автоматизированного проектирования и конструирования, возникла настоятельная необходимость подготовки специалистов в области создания и использо- вания САПР. В технических вузах страны открыта специ- альность «Системы автоматизированного проектирования». Кроме того, подготовка специалистов в области САПР проводится в рамках ряда специальностей, в том числе и специальности «Конструирование и производство электрон- но-вычислительной аппаратуры» (специализация 0648.02 «Конструирование и производство технических средств САПР»). Предметом курса являются теоретические основы САПР, их технические и информационные средства. Целью курса «Теоретические основы САПР» является систематическое изложение принципов организации, созда- ние и функционирование САПР. Содержание учебника полностью соответствует програм-' ме одноименного курса для студентов, обучающихся по спе- циальности 0648. Курс базируется на знаниях, полученных студентами при изучении марксистско-ленинской философии, общеоб- разовательных дисциплин (высшей математики, физики, инженерной графики, теоретической механики), курсов «Введение в специальность», «Лингвистическое и програм- мное обеспечение САПР», «Теоретические основы констру- ирования, технологии и надежности ЭВА», «Математичес- кое обеспечение конструкторского и технологического про- ектирования с применением САПР». В гл. 1 рассматриваются общие сведения о проектиро- вании технических средств объекта, классификация и ос- новные структуры САПР, виды обеспечения САПР, анали- зируется и обосновывается выбор критериев оптимально- сти. В гл. 2 разбираются вопросы организации технических средств САПР, технические средства машинной графики и систем передачи данных. Анализируется организация про- граммных и информационных средств САПР. В гл. 3 рассматриваются информационные потоки в САПР, классификация баз данных, организация системы управления базами данных, языки баз данных, описыва- ются логическая и физическая организация баз данных, ор- ганизация поиска данных. В гл. 4 анализируются особенности математического аппарата для математического моделирования на различ- ных иерархических уровнях проектирования БИС и ЭВА. В гл. 5 рассматриваются методы анализа процессов функционирования элементов интегральных схем, методы анализа статических режимов и переходных процессов в объектах на различных уровнях, методы анализа тепловых режимов, методы анализа логических и функциональных схем'ЭВА, методы многовариантного и статистического анализа. Глава 6 посвящена синтезу технических объектов в САПР. Рассматриваются задачи структурного синтеза и параметрической оптимизации. Описываются методы по- иска экстремума в задачах оптимального проектирования. В гл. 7 даются характеристики, позволяющие оценивать качество создаваемой САПР, рассматриваются методы имитационного моделирования аппаратных и программных средств САПР. Содержание книги построено на материале различных литературных источников, а также на оригинальных ре- зультатах работ по созданию подсистем САПР и на базе курсов лекций, прочитанных авторами в МВТУ им. Н. Э. Баумана, Рязанском и Таганрогском радиотехничес- ких институтах. Учебник предназначен для студентов высших учебных заведений, обучающихся по специальности 0648, и может быть рекомендован студентам смежных специальностей 0608, 0646, 0647, 0656, 0705 и др., а также аспирантам и ин- женерно-техническим работникам. Предисловие, гл. 6, 7 и § 1.3, 1.4 и 2.6 написаны В. П. Ко- рячко, гл. 2, 3 и § 1.1, 1.2, 1.5, 1.6 и 4.8—В. М. Курейчиком, гл. 4, 5, § 6.5, 7.4 и 7.7— И. П. Норенковым. Авторы благодарны рецензентам профессору, доктору техн. наук Е. Л. Глориозову, сотрудникам кафедры «Кон- струирование электронно-вычислительной аппаратуры» Ленинградского института точной механики и оптики, а также научному редактору В. Г. Одинокову за ценные замечания, улучшившие содержание книги. Замечания и пожелания следует направлять по адресу: 113114, Москва, М-114, Шлюзовая наб., 10, Энергоатомиз- дат, Авторы ГЛАВА 1 МЕТОДОЛОГИЯ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ 1.1. ОБЩИЕ СВЕДЕНИЯ О ПРОЕКТИРОВАНИИ При построении новых объектов техники по заданному описанию несуществующего объекта выполняется его ма- териализация в работоспособную надежную конструкцию. Проектирование—это процесс создания описания, необхо- димого для построения в заданных условиях еще не суще- ствующего объекта, на основе первичного описания этого объекта. Процесс создания описания нового объекта может выполняться различными способами. Выделим три основ- ных. Если весь процесс проектирования осуществляет чело- век, то проектирование называют неавтоматизированным. В настоящее время неавтоматизированное проектирование таких сложных объектов, как электронно-вычислительная аппаратура (ЭВА), практически не применяют. Наибольшее распространение получило проектирование, при котором происходит взаимодействие человека и ЭВМ. Такое проектирование называют автоматизированным. Ав- томатизированное проектирование, как правило, осущест- вляется в режиме диалога человека с ЭВМ на основе при- менения специальных языков общения с ЭВМ. Проектирование, при котором все преобразования опи- саний объекта и алгоритма его функционирования осуще- ствляются без участия человека, называют автоматичес- ким. Рассмотрим ряд понятий, которые используются, на- пример, при разработке ЭВА. Первичное описание ЭВА, представленное в заданной форме, называется заданием на проектирование. В задании на проектирование ЭВА должны быть сведения о назначении ЭВА, ее параметрах, способах функционирования, конструктивной реализации, изготовления и т. п. Проектным решением называется промежуточное или конечное описание объекта проектирования, не- обходимое и достаточное для рассмотрения и опреде- ления дальнейшего направления или окончания проек- тирования. Проектное решение или их совокупность, удовлетворя- ющие заданным требованиям, необходимые для создания объекта проектирования, будут являться результатом про- ектирования. В заданные требования должны быть обяза- тельно включены требования к форме представляемого проектного решения. Документ, выполненный по заданной форме, в котором представлено какое-либо проектное решение, полученное при проектировании, называется проектным. Совокупность проектных документов в соответствии с установленным перечнем, в котором представлен результат проектирования, называется проектом. Под проектной процедурой понимают формализованную совокупность действий, выполнение которых оканчивается проектным решением. Например, проектными процедурами являются оптимизация, контроль, поиск решения, коррек- тировка, компоновка, проверка правильности трассировки и т. п. Действие или формализованная совокупность действий, составляющих часть проектной процедуры, алгоритм ко- торых остается неизменным для ряда проектных процедур, называется проектной операцией. Примерами проектных операций являются составление таблиц с данными вычис- ления, вычерчивание топологии, ввод и вывод данных, на- бивка перфокарт и т. п. Соответственно проектная процеду- ра, алгоритм которой остается неизменным для различных объектов проектирования или различных стадий проекти- рования одного и того же объекта, называется унифициро- ванной проектной процедурой. Выполнение проектных работ можно распределить как во времени, так и по подразделениям проектной организа- ции. При временном распределении работ по созданию но- вых объектов процесс проектирования разделяется на ста- дии и этапы. Различают 8 стадий: предпроектные исследо- вания; техническое задание; техническое предложение; эс- кизный проект; технический проект; рабочий проект; изго- товление; отладка, испытание и ввод в действие. При создании новых объектов выделяют следующие этапы: этап научно-исследовательских работ (НИР). Объеди- няет стадии: предпроектные исследования, техническое за- дание и часть технического предложения. Здесь проводят исследования по поиску новых принципов функционирова- ния, новых структур, физических процессов, новой элемент- ной базы, технических средств и т. п.; этап опытно-конструкторских работ (ОКР). Объединя- ет стадии: часть технического предложения, эскизный про- ект, технический проект. Здесь отражаются вопросы де- тальной конструкторской проработки проекта; этап рабочего проектирования. Объединяет стадии: ра- бочий проект, изготовление, отладка и испытание, ввод в действие. Здесь прорабатывают схемные, конструкторские и технологические решения, проводят испытания, изготов- ление. Для этапа НИР в основном используют системы авто- матизации научных исследований и экспериментов. Распределение работ между подразделениями произво- дят с использованием блочно-иерархического подхода (БИП) к проектированию. Этот подход основан на струк- турировании описаний объекта с разделением описаний на ряд иерархических уровней по степени детальности отобра- жения в них свойств объекта и его частей. Каждому иерар- хическому уровню присущи свои формы документации, ма- тематический аппарат для построения моделей и алгорит- мов исследования. Совокупность языков, моделей, поста- новок задач, методов получения описаний некоторого иерархического уровня часто называют уровнем проекти- рования. Уровни проектирования можно выделять не только по степени подробности отражения свойств объекта, но и по характеру отражаемых свойств. Если в первом случае уровни называют горизонтальными, или иерархическими, то во втором—вертикальными, или аспектами. Методология БИП базируется на трех концепциях} разбиение и локальная оптимизация; абстрагирование; по- вторяемость. Концепция разбиения позволяет сложную задачу проек- тирования объекта свести к решению более простых задач с учетом взаимодействий между ними. Локальная оптими- зация подразумевает улучшение параметров внутри каж- дой простой задачи. Абстрагируемость заключается в по- строении формальных математических моделей, отражаю- щих только значимые в данных условиях свойства объек- тов. Повторяемость заключается в использовании сущест- вующего опыта проектирования. Основное достоинство БИП—это упрощение процесса проектирования и получение возможности решать задачи проектирования доступными средствами.. Использование БИП помогает: упростить решение про- блемы хранения данных, сократить размерность выполняе- мых программ и время проектирования, применять САПР один раз для объекта (его части) независимо от числа идентичных объектов (его частей). Весь процесс проектирования можно представить как последовательность этапов, связывающих концептуальное описание объекта и создание этого объекта. Указанную связь реализуют в одном из двух направлений: восходя- щем или нисходящем. Восходящее проектирование (ВП), т. е. проектирование снизу вверх, характеризуется решени- ем сначала задач низких иерархических уровней с последо- вательным переходом к решению задач более высоких уровней. Нисходящее проектирование (НП), т.е. проекти- рование сверху вниз, является противоположным по отно- шению к ВП. Отметим, например, что используемая в настоящее вре- мя концепция проектирования интегральных микросхем с большой степенью интеграции по модульному принципу— это концепция БИП. В системе БИП конструктор выполня- ет функциональные, интуитивные и интеллектуальные пре- образования на верхних уровнях, а ЭВМ выполняет про- ектирование на нижних уровнях. При выделении горизонтальных уровней проектирова- ния производится разделение объекта на блоки и рассмот- рение вместо объекта его отдельных блоков. Если на неко- тором уровне i'i имеем объект s, то на соседнем, более низком уровне t'z происходит разделение s на блоки Si, Ss, ..., Sj и рассмотрение каждого блока Si, S2, ..., s, на уровне t'a с большей степенью детализации, чем на уровне t'i. В общем случае при проектировании технических объ- ектов можно выделить несколько вертикальных уровней, основные из них — функциональный, конструкторский, тех- нологический. Описание каждого вертикального уровня в свою очередь делят на иерархические уровни. Ниже приве- ден пример структурирования описания ЭВМ; Вертикальные уровни 1 >,cu 3л ч сз (-оСП Ко.? Функциональ- Алгоритмический Конструктор- Технологический Системный Программирование системы Шкаф, стойка Принципиальная схема технологического процесса Логический Панель Программирование модулей Схемотехнический тэз Маршрутная технология Компонентный Проектирование микропрограмм Модуль Технологические операции Кристалл Ячейка Функциональное проектирование включает в себя анализ технического задания (ТЗ) и на его основе выбор с системных позиций методики построения и путей реализации вычислительного процесса в ЭВА; связано с анализом и синтезом блоков ЭВА; заключается в разра- ботке функциональных и принципиальных схем. Здесь оп- ределяют принципы функционирования и важнейшие па- раметры и характеристики ЭВА. Основные задачи функционального проектирования сле- дующие: разработка структурных схем, определение тре- бований к выходным параметрам; анализ и формирование ТЗ на разработку отдельных блоков ЭВА; синтез функцио- нальных и принципиальных схем полученных блоков; кон- троль и выработка диагностических тестов; проверка рабо- тоспособности синтезируемых блоков; расчеты параметров пассивных компонентов и определение требований к пара- метрам активных компонентов; формулировка ТЗ на проек- тирование компонентов; выбор физической структуры, то- пологии компонентов; расчеты параметров диффузионных профилей и полупроводниковых компонентов, электричес- ких параметров, параметров технологических процессов эпитаксии, диффузии, окисления и др.; вероятностные тре- бования к выходным параметрам компонентов. Алгоритмическое проектирование заклю- чается в разработке алгоритмов функционирования и соз- дании математического обеспечения ЭВА. Конструкторское проектирование заклю- 10 чается в реализации принципиальных схем в заданном конструктивном базисе. При этом решаются вопросы выбо- ра форм и материалов, выбора типоразмеров, компоновки, размещения элементов, трассировки соединений, контроля. Основные задачи конструкторского проектирования сле- дующие: покрытие функциональных схем, т. е. получение принципиальных электрических схем; конструкторский рас- чет геометрических размеров компонентов и площади раз- мещения; компоновка элементов; размещение элементов с учетом конструкторских схемотехнических и технологичес- ких ограничений; трассировка соединений; контроль топо- логии; проектирование фотошаблонов; выпуск конструктор- ско-технологической документации. Технологическое проектирование заклю- чается в решении задач технологической подготовки про- изводства — разработке принципиальной схемы, маршру- тов, операций и переходов технологических процессов изготовления деталей, сборки и монтажа узлов, включая вы- бор оснастки, инструмента, технологического оборудова- ния и т. п. Функциональное проектирование ЭВА состоит из четы- рех основных горизонтальных уровней: системного, логиче- ского, схемотехнического, компонентного. На системном уровне определяют общую структурную схему, структурные схемы основных блоков. На логическом уровне создают функциональные и прин- ципиальные схемы ЭВА. Здесь выделяют подуровни—ре- гистровый и вентильный. На регистровом подуровне про- ектируются устройства из модулей (функциональных уз- лов) типа регистров, счетчиков, сумматоров, интеграторов и т. п. На вентильном уровне проектируются устройства и модули из отдельных логических вентилей и триггеров. Алгоритмическое проектирование используется для раз- работки программного обеспечения ЭВА. Для больших программных систем обычно используют набор иерархиче- ских уровней, два из которых являются основными. На пер- вом планируют всю программную систему и разрабатыва- ют схемы алгоритмов на основе программных модулей. На втором производят программирование модулей на задан- ном алгоритмическом языке. Конструкторское проектирование состоит из иерархиче- ских уровней проектирования компонентов, БИС, типовых элементов замены, панелей, стоек, шкафов. Здесь в основ- ном используется восходящее проектирование. 11 Технологическое проектирование состоит из уровней проектирования принципиальной схемы технологического процесса, технологических маршрутов, технологических операций. 1.2. ЗАДАЧИ ПРИНЯТИЯ РЕШЕНИЙ В САПР Задачи проектирования делят на задачи синтеза и ана- лиза. Под синтезом понимается построение описания систе- мы по заданному функционированию. Анализ—это опре- деление функционирования по заданному описанию систе- мы. Задачи синтеза связаны с созданием проектных документов и самого проекта, а задачи анализа связаны с оценкой проектных документов. Различают синтез структурный и параметрический. Цель структурного синтеза — получение структурных схем объек- та, содержащих сведения о составе элементов и способах соединения их между собой. Цель параметрического синте- за—определение числовых значений параметров элемен- тов. Синтез называется оптимизацией, если определяются наилучшие в заданном смысле структуры и значения пара- метров. При расчетах оптимальных значений параметров при заданной структуре говорят о параметрической опти- мизации. Задачу выбора оптимальной структуры называют структурной оптимизацией. При проектировании на основе САПР имеется возмож- ность получать множество решений различных задач. Вы- деление некоторого подмножества решений задач относит- ся к проблемам выбора и принятия решений. Задачей при- нятия решений называют кортеж a==<^W, 6> (где W— множество вариантов решений задачи; 9—принцип опти- мальности, дающий представление о качестве вариантов, в простейшем случае правило предпочтения вариантов). Ре- шением задачи а называют множество Woa^W, получен- ное на основе принципа оптимальности. Задачи принятия решений классифицируют по наличию информации о множестве W и принципе оптимальности в. Задачу, где W и 0 могут быть неизвестными, называют общей задачей принятия решений. Данные для получения Won определяют в этой задаче в процессе решения. Задачу с неизвестным W называют задачей выбора, а задачу с из- вестными W и в называют задачей оптимизации. В САПР встречаются все три вида перечисленных задач. В задачах проектирования свойства элементов множе- 12 ства W помогают находить решение. Если произвольное свойство варианта w^ W 'выразить числом /<=={!, 2...}, т. е. предположить, что имеется отображение <р: W->K, то такое свойство называют критерием, а число (p(W,) —оцен- кой варианта Wi по критерию. Критериальным пространст- вом считают пространство Km, координаты точек которо- го — оценки по соответствующим критериям. Например, пусть надо определить трассу, соединяющую две БИС на подложке. Различные возможные пути, соединяющие БИС 1 и БИС 2, будут вариантами. Пользователь или ЭВМ в соответствии с алгорит- мом учитывает длину, стоимость, число изгибов, число пересечений и т. п. Значение длины трассы можно выразить числом, длину считать критерием. Задачу а решают следующим образом. Составляют мно- жество W, если это возможно, т. е. определяют варианты, а затем решают задачу выбора. Отметим, что задача построе- ния W в общем 'случае является задачей выбора. Следова- тельно, общую задачу принятия решений можно свести к решению последовательных задач выбора. В принятии ре- шений в общем случае участвуют ЭВМ, лицо, принимаю- щее решения (ЛПР), например проектировщик, эксперт, дающий оценки вариантам, и консультант. Частным случаем общей задачи принятия решений яв- ляется задача принятия решений в условиях неопределен- ности, возникающая, когда необходимо действовать в не полностью известной ситуации. Она часто формулируется как задача поиска одного наилучшего решения на заданном множестве допустимых решений. Неизбежной платой за попытку получить решение в ус- ловиях неполной информации об объекте проектирования и его поведении является возможность ошибочных решений. Поэтому в такой ситуации ЛПР должно вырабатывать та- кую стратегию в отношении принятия решений, которая хо- тя и не исключает возможность принятия неправильных решений, но сводит к минимуму связанные с этим нежела- тельные последствия. Для уменьшения неопределенности и возможных потерь ЛПР может провести эксперимент. Это позволит сделать знания об исследуемом объекте сколь угодно полными и действовать уже в условиях определен- ности. Однако этому мешают два обстоятельства: 1) на проведение эксперимента требуется время, тогда как реше- ние во многих случаях нужно принять быстро; 2) экспери- мент требует затраты средств и может стоить дороже того 13 выигрыша, который дают добавочные знания, полученные в результате эксперимента. Поэтому ЛПР должно принять решение о том, нужно ли проводить эксперимент, а если нужно, то на каком уров- не его закончить и какие действия предпринять после окон- чания эксперимента. Раздел математической теории принятия решений в ус- ловиях неполной определенности называют теорией стати- стических решений. 1.3. ВЫБОР КРИТЕРИЕВ ОПТИМАЛЬНОСТИ На разных этапах проектирования технических объектов перед разработчиками встает задача выбора наилучшего варианта из множества допустимых проектных решений, удовлетворяющих предъявляемым требованиям. Само по себе принятие решения есть компромисс. При- нимая решение, необходимо взвешивать суждения о ценно- сти, что включает рассмотрение многих факторов, в том чис- ле экономических, технических, научных, социальных и чи- сто человеческих. Принять «правильное» решение — значит выбрать такую альтернативу из числа возможных, в кото- рой с учетом всех разнообразных факторов будет оптими- зирована общая ценность. Задача оптимального проектиро- вания заключается в определении вектора X=(^i, ..., Xm) оптимальных конструктивных параметров проектируемого объекта исходя из технических и технико-экономических критериев оптимальности и поставленных ограничений. Пе- ременные проектирования Х являются внутренними пере- менными, допускающими варьирование. Использование ра- ционального комплекса критериев представляет собой ос- новной метод творческой технической деятельности при оптимальном проектировании. От того, как составлен комп- лекс критериев, зависит успех разработки. Процесс приня- тия решения при оптимальном проектировании характери- зуют следующие основные черты: наличие цели (критериев оптимальности) и альтернативных вариантов проектируе- мого объекта и учет существенных факторов при проекти- ровании. Понятие «оптимальное решение» при проектировании имеет вполне определенное толкование — лучшее в том или ином смысле проектное решение, допускаемое обстоятельст- вами. В подавляющем большинстве случаев одна и та же техническая задача может быть решена несколькими спо- 14 собами, приводящими не только к различным выходным характеристикам, схемам ^конструкциям, но даже и к фи- зическим принципам, положенным в основу построения объ- екта, При этом одно из решений может превосходить дру- гое по одним свойствам и уступать ему по другим. В этих условиях часто чрезвычайно трудно сказать не только ка- кая из систем оптимальна, но даже какая из них предпочти- тельнее. Если при проектировании технических объектов или си- стем можно выделить один параметр, которому отдается безусловное предпочтение и который наиболее полно харак- теризует свойства проектируемого объекта, то естественно этот параметр принять за целевую функцию. Такой выбор целевой функции лежит в основе критериев оптимальности, называемых частными критериями. При оптимизации по ча- стным критериям задача проектирования сводится к задаче оптимизации выбранной целевой функции при условии со- блюдения определенных ограничений. При этом одна часть параметров подпадает под категорию ограничений, а другая часть параметров, на которые не накладываются ограниче- ния, принимается такой, какой получилась при оптимизации целевой функции. Для решения однокритериальных задач создан и уже давно успешно применяется развитый .математический ап- парат, в том числе аппарат исследования операций. Альтернативы, перед которыми оказываются разработ- чики новых технических систем, в большинстве случаев не могут быть отнесены к однокритериальным задачам. Любая техническая система, особенно система сложная, характе- ризуется многими параметрами, определяющими ее качест- во и ценность. Среди этих параметров есть такие, значения которых желательно всемерно увеличивать, есть и такие, которые желательно минимизировать. Существующие взаимосвязи между параметрами любой технической системы и ограничения, накладываемые на па- раметры, не позволяют конструкторам системы увеличить, насколько это желательно, все те характеристики, возраста- ние которых повышает качество системы, и уменьшить до предела все те параметры, минимизация которых улучшает систему. Таким образом, ограничения и связи между отдельными параметрами технической системы приводят к необходимо- сти идти на компромисс и выбирать для каждой характери- стики не максимально возможное в принципе значение, а 15 меньшее, но такое, при котором и другие важные характе- ристики тоже будут иметь приемлемые значения. Поэтому при выборе варианта технической системы нельзя ограни- чиваться сравнением по одной какой-либо характеристике, а необходимо принимать во внимание всю их совокупность. Задачи проектирования, проводимые по нескольким крите- риям оптимизации, носят название многокритериальных, или задач векторной оптимизации. Все известные методы векторной оптимизации непосред- ственно или косвенно сводят решаемые задачи к задачам скалярной оптимизации. Иначе говоря, частные критерии Fi(X), г==1, п, тем или иным способом объединяются в со- ставной критерий F(X) =0(fi(X), ..., FnW), который за- тем максимизируется (или минимизируется). Если состав- ной критерий получается в результате проникновения в фи- зическую суть функционирования системы и вскрытия объек- тивно существующей взаимозависимости между частными критериями и составным критерием, то оптимальное реше- ние является объективным. Однако отыскание подобной взаимозависимости чрезвычайно сложно, а может быть, и не всегда возможно. Поэтому на практике составной крите- рий обычно образуют путем формального объединения част- ных критериев, что неизбежно ведет к субъективности по- лучаемого «оптимального» решения. Составной критерий иногда называют обобщенным или интегральным кри- терием. В зависимости от того, каким образом частные критерии объединяются в обобщенный критерий, различают крите- рии аддитивные, мультипликативные и минимаксные (мак- симинные). Если оптимизация ведется без учета статистического разброса характеристик, то соответствующий критерий оп- тимальности называют детерминированным критерием, ес- ли разброс параметров учитывается, то имеем критерий статистический. Статистические критерии оптимальности более полно отражают представление о качестве объектов проектирования, однако их использование, как правило, при автоматизированном проектировании ведет к значительному увеличению затрат машинного времени. Рассмотрим наиболее часто встречающиеся на практике способы выбора критериев оптимальности. Частные критерии. При проектировании по частным кри- териям в качестве целевой функции ^(Х) принимается наиболее важный выходной параметр проектируемого объ- 16 екта, все остальные параметры в виде соответствующих ус- ловий работоспособности относятся к ограничениям. В этом случае задача оптимального проектирования'является од- нокритериальной задачей математического программирова- ния: максимизировать (или минимизировать) значение це- левой функции F (X)-^-max (min) при наличии системы ограничений на параметры проекти- руемого объекта. Из постановки задачи математического программирова- ния вытекает, что параметры, для которых выполняются ограничения в виде строгих неравенств, имеют определен- ный запас по сравнению с заданными техническими требо- ваниями. Ряд параметров, для которых условия работоспо- собности имеют вид равенств, запасов вообще не имеет, и любые изменения технических требований для этих пара- метров приводят как к изменению характеристик и струк- туры проектируемого объекта, так и к изменению значения целевой функции. Частные критерии довольно широко используют при про- ектировании технических объектов различного назначения. Пример 1.1. Проектирование технологического оборудования. Пе- реносной автомат для забивания стальных дюбелей в бетонные стены состоит из корпуса с магазином, содержащим запас дюбелей, подающе- спускового механизма с зарядами и ствола (рис. 1.1). Требуется опре- Рис. 1.1. Технологический ав- томат Рис. 1.2. Область решения задачи оп- тимизации технологического автомата делить основной конструктивный параметр автомата—длину ствола L—при следующих исходных данных: число дюбелей, помещающих- ся в магазине, Л?>12, масса одного дюбеля с расходуемым на него за- рядом т=50 г, масса ствола 1,6 кг/м, масса корпуса 2 кг, критерий оп- тимальности — минимальная масса заряженного автомата. 2-785 17 При фиксированной величине заряда и заданной массе дюбеля скорость V выбрасывания дюбеля связана с длиной ствола L соотно- шением V^k^L, где fe=150 м^/с. Минимально допустимая скорость дюбеля определяется экспериментально: V'min^lOO м/с. Масса авто- мата при минимально допустимом числе дюбелей в магазине опреде- ляется как F(Z.)=1,6 L+0,05 yV+2=l,6L+2,6. Задача проектирования автомата сводится к минимизации целе- вой функции F(L)=l.6L+2.e при ограничении \wY~L> 100. Решение задачи оптимизации имеет вид: Л,=0,445м, F(L) =3,31 кг, График области компромисса для массы автомата 6 кг показан на рис. 1.2. Здесь точка А соответствует оптимальному решению данной задачи по критерию минимума массы автомата. Аддитивные критерии. В аддитивных критериях целевая функция образуется путем сложения нормированных значе- ний частных критериев. Частные критерии имеют различную физическую природу и в соответствии с этим — различную размерность. Поэтому при образовании обобщенного крите- рия следует оперировать не с «натуральными» критериями, а с их нормированными значениями. Нормированные кри- терии представляют собой отношение «натурального» част- ного критерия к некоторой нормирующей величине, измеряе- мой в тех же' единицах, что и сам критерий. При этом выбор нормирующего делителя должен быть логически обоснован. Возможны несколько подходов к выбору нормирующего де- лителя. Первый подход предлагает принимать в качестве нор- мирующего делителя директивные значения параметров, за- данные заказчиком. Логически слабым моментом такого подхода является негласное предположение того, что в ТЗ на проектируемый объект заданы оптимальные значения па- раметров объекта и что совокупность заданных значений критериев рассматривается как образцовая. Второй подход предполагает выбор в качестве нормиру- ющих делителей максимальных значений критериев, дости- гаемых в области существования проектных решений (в об- ласти компромисса). Возможен подход, при котором в ка- честве нормирующих делителей выбирают разность между максимальным и минимальным значениями критерия в об- ласти компромисса. 18 Выбор подхода к формированию безразмерной формы частных критериев в значительной степени носит субъектив- ный характер и должен обосновываться в каждом конкрет- ном случае. Пусть при проектировании некоторого объекта сущест- вует п частных критериев. Тогда целевая функция задачи оптимизации при применении аддитивного критерия имеет вид F(X) -v^^^-v ^ /f'(X) JJ i=l i=l CifiW. (1.1) Здесь Ci — весовой коэффициент t-го частного критерия; Л°) (X)—1-й нормирующий делитель; fi(X)—нормирован- ное значение i-го частного критерия. Функция (1.1) позволяет осуществлять компромисс, при котором улучшение значения одного нормированного част- ного критерия компенсирует ухудшение значений других. Введение весовых коэффициентов должно учитывать различную значимость частных критериев при формирова- нии аддитивного критерия. Определение весовых коэффи- циентов сталкивается с серьезными трудностями и обычно сводится либо к использованию формальных процедур, либо к применению экспертных оценок. С появлением обобщенного критерия исчезают логичес- кие проблемы, связанные с установлением взаимосвязей между частными критериями различной размерности и вы- бором наилучшего варианта проектируемого объекта, и ос- таются лишь вычислительные трудности. Но аддитивный критерий имеет ряд недостатков, главный из которых состо- ит в том, что он не вытекает из объективной роли частных критериев в функционировании объекта или системы и вы- ступает поэтому как формальный математический прием, придающий задаче удобный для решения вид. Другой не- достаток заключается в том, что в аддитивном критерии может происходить взаимная компенсация частных крите- риев. Это значит, что значительное уменьшение одного из критериев вплоть до нулевого значения может быть покрыто возрастанием другого критерия. Для ослабления этого не- достатка следует вводить ограничения на минимальные значения частных критериев и их весовых коэффициентов. Несмотря на слабые стороны обобщенный аддитивный кри- терий позволяет в ряде случаев успешно решать многокри- териальные задачи и получать полезные результаты. 2* 19 Пример 1.2. По исходным данным примера 1.1 определить конст- руктивные параметры L и N переносного автомата при условии, что масса заряженного автомата не должна превышать 6 кг, а частными критериями эффективности автомата являются скорость выбрасывания дюбеля V и число дюбелей N, помещающихся в магазине. Выбор этих критериев объясняется тем, что чем выше V, тем надежнее дюбеля про- никают в бетон любой марки, а чем больше N, тем удобнее работать с автоматом. По мнению экспертов оба критерия V и N в нормированном виде имеют одинаковую важность. Найдем оптимальное решение с помощью аддитивного критерия. Для нормирования найдем Nmax и Ртах. Величину Nmax определяют из условия, Vmin=100 м/с. Уравнение баланса масс имеет вид 1,6L+0,05,V+2=6. Из этого уравнения следует, что Л'тах=65. Для отыскания Vmax будем считать, что в автомате находится только один дюбель. Тогда Утах=150'}/'/-щах==236 м/с. Нормированные частные критерии будут иметь вид /I (V) = V/236; /-a (N) = AV65. Аддитивный критерий эффективности автомата F (V, N) = /I (V) + /2 W •= У/236 + N/65. Для определения максимального значения аддитивного критерия F(V, N) с учетом ограничения на массу автомата воспользуемся мето- дом неопределенных множителей Лагранжа. В результате решения за- дачи оптимизации получаем V^ =100 м/с, L^ =0,445 м, Л'д^ =65. На рис. 1.2 данному решению соответствует точка В. Мультипликативные критерии. Аддитивные критерии ос- нованы на использовании принципа справедливой компен- сации абсолютных значений нормированных частных крите- риев. Но в ряде задач проектирования более целесообраз- ным является оперирование не с абсолютными, а с относительными изменениями значений частных критериев. Принцип справедливой относительной компенсации фор- мулируется следующим образом: справедливым следует считать такой компромисс, когда суммарный уровень отно- сительного снижения значений одного или нескольких кри- териев не превышает суммарного уровня относительного увеличения значений других критериев. В математической форме условие оптимальности на основе прин- ципа справедливой относительной компенсации имеет вид 100 м/с, ^=0,445 м, Л'^=65. AF; (X) FiW (1.2) 20 где AF{{X)—приращение величины i-го. критерия; ^((Х)—первона- чальная величина i-го критерия. Полагая ДР,(Х) иногда носит название «прин- ципа гарантированного результата». Он заимствован из тео- рии игр, где, по существу, является основным принципом. Если частные критерии /г(Х) следует минимизировать, то самым «отстающим» критерием является тот, который принимает максимальное значение. В этом случае принцип равномерной компенсации формулируется в виде минимакс- ной задачи: ^(Х*0') ==minmax^(X)}, i i X l,n,X=--(^,...,xJ. (1.7) Для обоснования геометрической интерпретации принципа мини- макса приведем ряд определений из теории выпуклых множеств. Пусть Q — некоторое множество,' определенное в пространстве ?". Множество Q называют выпуклым, если отрезок, соединяющий любые две точки этого множества, целиком принадлежит этому множеству. Другими словами, Q — выпуклое множество, если для любых х0'), x<')eQ и любого 0<Л<1 справедливо x=^x(')+(l—?.)x(/)eQ. Величину х называют средневзвешенной по элементам х^' и х'3') свесами Х и (1—К). Пусть Л={А<1), ..., AW}—конечное множество точек в пространст- ве Е". Конечное множество точек (рис. 1.3, а) не является выпуклым, ^, Л О Рис. 1.3. Иллюстрация понятия выпуклой оболочки и области компро- мисса однако может быть заключено в выпуклую оболочку 5(Л) (рис. 1.3,6). Выпуклой оболочкой S(A) конечного точечного множества А называют пересечение всех выпуклых множеств Q„ подмножествами которых яв- ляется Л. В частности, если ЛсО; и AcQa, то S(A)cQinQ2. 23 Из данного определения следует, что выпуклая оболочка S(A) яв- ляется наименьшим выпуклым множеством, содержащим Л. Выпуклой оболочкой конечного точечного множества А на плоскости является выпуклый многоугольник, вершинами которого являются крайние точ- ки множества А, а выпуклой оболочкой конечного множества А в про- странстве ?" — выпуклый многогранник. Точку х* называют крайней точкой конечного множества Л, если ни для каких А0'), А^еЛ она не может быть представлена в виде х* = Ш') + (1 — К) W), 0 < К < 1. Заметим, что в этом определении К не может принимать значений О и 1. Это означает, что крайняя точка не может лежать внутри отрез- ка, соединяющего любые две точки множества Л, а может быть лишь концевой точкой этого отрезка. Выпуклая оболочка конечного множе- ства Л есть множество средневзвешенных по элементам множества Л. Геометрическая интерпретация принципа минимакса за- ключается в следующем. Пусть проектируется некоторый объект по п частным критериям ^г==Л-(Х), г==1, п. Каждый вариант объекта может быть представлен в пространстве En в виде точки А^ с координатами AC^^^i •••, 'б^^а множество вари- антов может быть отображено в конечное множество точек Л=={А°\ ..., А^)}, заключенное в выпуклую оболочку 5 (Л). Таким образом, область принятия решений при проек- тировании ограничена выпуклой оболочкой S(A) в прост- ранстве En. Пусть все частные критерии минимизируются. Тогда об- ластью компромисса является левая нижняя граница вы- пуклой оболочки S(A), а решение должно находиться в области компромисса (рис. 1.3, в). В общем случае при не- • равнозначных критериях •fl'i==/i(X) решение на основе принципа равномерной компенсации будет соответствовать такой точке А^, лежащей в области компромисса, для ко- торой будут удовлетворяться соотношения ^ ^ = ^, с, > 0,^^=1, i=~STn. (1.8) t=i Заметим, что направление, определяемое вектором С==? ==(ci, .... Сп), задается в первом ортанте в пространстве ?". Произвольный вектор весовых коэффициентов С, удов- летворяющий соотношениям (1.8), будем интерпретировать как предпочтение частных критериев <г;==/'г(Х) друг перед другом, выраженное в количественной шкале. 24 Остановимся на определении направления, порождаемого вектором С~в пространстве E•л. Это направление задается углами ?;, t=l, n, между осями координат и радиусом-вектором С. Тогда cos?, = У, е;) Iе; где е,=(0, ..., О, 1, 0, ..., 0)—орт оси 0,;Д*=(^* ..., О*)—точка, нахо- дящаяся на луче С. Исходя из отношений для различных пар углов р, и Р, (i, /=1, п), запишем систему линейно независимых уравнений, из которой могут быть найдены неизвестные направляющие косинусы: cos P^/cos р^ = ©;/&;, t, /• = T~h, ^ cos2?, == 1. (=i С другой стороны, в силу соотношений (1.8) для точки Q* спра- ведливо 0;/0;=с/./с„ i, j=T~n. i?-j. Учитывая эти соотношения, можно переписать (1.9) следующим Образом: cos P,/cos (3, = Cj/c^, i, j=]~n.i^j,^ cos2 P;= 1. (1.10) t'=i Решая (1.10), получим выражение для направляющих косинусов век- тора С: (1.11) Если все частные критерии равноценны, т. е. ci=l/M, г'=1, п, то cosp;=lV"Al, i=.T~n. При наличии двух частных критериев для равноценных критериев направляющие косинусы имеют вид cos Pi = cos pa= lfV~2, что соответствует биссектрисе координатного угла fl'i 0 •из (рис. 1.4, а), Если Ci>C2, что указывает на то, что частный критерий fl'i пред- почтительней второго, то cos|3i] i=l, ft, /==1, т, множества S={S\, „., Sm} альтернативных вариантов. В матрице @ вектор-строка ©.^(д^, .... 0^ )) описывает вариант S^eS проектируемого объекта. Для перехода от •&,* к f^ W=ff При фиксированном векторе переменных проектирования X», введем совокупность директивных значений параметров ©о= (^\ )>••• ..., 'в"), устанавливаемых в ТЗ на проектирование. Тогда нормирован- ные (относительные) значения параметров определяются как fW = О,"»/^, I = \~п, J = 1~от. (1.14) Определим в матрице Э величины 0^ —экстремальные (наилуч- шие) значения всех параметров. Очевидно, что идеальный вариант объ- екта 5и должен описываться всеми б,*, t'==l, п. Для оценки степени важности каждого параметра Ог (или каждо- го нормированного значения параметра fi) вводится система весов С= =(Ci, .... Сп), которая должна отражать усилия, необходимые для дос- тижения экстремальных значений параметров (увеличить значения та- ких параметров, как производительность, надежность и другие, или уменьшить значения массогабаритных, стоимостных и энергетических па- раметров). Правильный выбор системы весов открывает возможность целенаправленно воздействовать на улучшение тех или иных парамет- ров объекта путем увеличения соответствующих весов ci. Конечно, для осуществления этой возможности система весов не должна быть за- стывшей, а должна быть гибкой и должна меняться в зависимости от назначения объекта и состояния развития данной отрасли техники в настоящий момент времени. В основу выбора системы весов положим принцип ограниченности общих затрат, необходимых для создания объ- екта. Это означает, что увеличение затрат на улучшение одних парамет- ров неизбежно вызывает уменьшение затрат на улучшение других па- раметров. Методика формального определения весовых коэффициентов бази- руется на выполнении последовательности процедур выработки пред- почтения среди каждой пары показателей fi и fh- 30 Обозначим через fi/i значение показателя /г в варианте объекта, в котором максимальные затраты сосредоточены на-увеличении показа- теля fh, а через ^. — наилучшее значение показателя fi во множестве альтернативных вариантов S, т. е. ^=ext{^' };/„=/,|/,=^, где /it=/i[/t=^ —значение показателя fi в варианте S, для которо- го ^=?;. При этом ^=ln|/:-^'[=lnl7:-l (1.15) определяет близость директивного значения показателя f^^-of1'1/^^ == == 1 к наилучшему- ^ . Чем большее значение придается показателю fi, тем меньше должно быть Д/J. Следовательно, 'вес, придаваемый пока- зателю fi, должен быть обратно пропорционален величине А/*, что по- зволяет записать с,»1/Д/;. Величина ^fik=^\f"i-fik\ (1.16) определяет ухудшение показателя fi в варианте объекта, в котором мак- симальные затраты сосредоточиваются на улучшении показателя ft. Если величина Д/;д мала, то это означает, что сосредоточение затрат на увеличении f/г не ухудшает существенно ^ и что, следовательно, поддержание f, на высоком уровне не требует больших затрат и ве- личина d должна быть взята малой, и наоборот. Следовательно, вес показателя fi должен увеличиваться с увеличением &fi/,. Это утвержде- ние справедливо для любого йе{1, .„, п], откуда следует, что ^л^- 4=1 (1.17) С учетом (1.16) и (1.17) можно записать ^•-i^/^-i^' (1-!8) *==! ' t=l где ?i»=Afik/AL будут тем больше, чем большее значение придается показателю /; и чем сильнее сказывается на снижении этого показате- ля сосредоточение усилий на показателе fk. Следовательно, величины 1ц, могут рассматриваться как относи- тельные веса, показывающие относительное превосходство (доминиро- вание) показателя /, над fk. Однако использование (1.18) для определения весов наталкивает- 31 ся на ряд трудностей. Во-первых, описанная методика определения ?«, оказывается неприемлемой при k=i, т. е. величины 1ц, г=1, п, остают- ся неопределенными. Ими, правда, можно было задаться произвольно, однако это вносит произвол в определение весов с,. Во-вторых, величи- ны l,k, отражающие, как отмечалось, превосходство показателя fs над показателем f/г и дающие соответствующие вклады в суммарный вес ci, входят в (1.18) с коэффициентами, равными единице, т. е. не учитываются веса показателя fh- В то же время превосходство 1цг па- раметра fi над fk. может быть превосходством «сильного» над «слабым», поэтому значительность этого превосходства должна быть пропорцио- нальна весу параметра fh. Исходя из этого, следует заменить в (1.18) величины lii, на сЛъ- Такой подход приводит к необходимости использования для оп- ределения весов метода итерации. В нулевом приближении веса всех показателей принимаются одинаковыми и равными с\ ^\. Далее, ес- ли определены веса г-го порядка, то переход к весам г+1-го порядка будем осуществлять по формуле „(г+1) _ Vc<^/ ^ —^cй 4k' fc=l согласно которой веса первого, второго и т. д. порядков будут „(I) _ у ^ -Zi г(0), _ VI / ck 4k — ZJ ' ,.(2) _ V,(1), -I ~ ZJ ck l K=1 Данный процесс довольно быстро приводит к установившейся си- стеме весов, не зависящих от последующих итераций и от величин 1ц. В связи с этим значения 1ц можно выбирать произвольно, например равными 0,5 или 1. Нормированные веса всех показателей после прове- дения t итераций определяются как ... / " W. <=l е,=(^/)^ ..., ^)=о;), Если подмножество параметров 9,св^ описывающее вариант объ- екта 5,eS, является подмножеством наилучших значений параметров ©,= (О^^О^, ..., в^^О*), то возникает неопределенность при нахождении относительных весов с, по формуле (1.18). Для разрешения этой неопределенности перейдем от матрицы па- раметроа е^НО^Ц к матрице относительных показателей А^^0'], <='!, ", /=1, т, элементы Л1'1 которой образуются согласно (1.14^. 32 Множество строк Л={Л), „., Лп} матрицы А расщепим на два под- множества А, и A'.(A=A,[jA.)i причем подмножество Aj (мощностью q) является порождением множества в^ = (О^ , ..., О^) посредством преобразования (1.14), а Л' (мощностью п—q)—порождением множе- ства ever^-H,-,^). Сформируем q матриц А'*) относительных параметров размерности (п—<7+1)т таким образом, что множество строк Л1'11 матрицы А'"'об- разуется из одного элемента Л»еЛ, и всех элементов множества Л._ Для каждой матрицы AW, <г=1, q, определяют значения весовых коэффициентов 'Cfe=(^ft, Ck+i, ..., Сп) согласно описанной выше итера- ционной процедуре. Поскольку значения весовых коэффициентов Ck па- раметра fh в матрицах AW, й==1, q определены относительно одного итого же подмножества параметров А,, то это позволяет найти доми- нирование параметра fi над параметром fk(fi, fii^A:) как lih=cu'Cii, а затем все полученные lih., i, йе{1, ..., q) использовать для определе- ния весовых коэффициентов ci более высоких порядков. Проиллюстрируем формальную методику определения весовых ко- эффициентов на примере. Пример 1.5. Выбор наилучшего варианта системы автоматического регулирования. При проектировании системы автоматического регули- рования представлено три конкурирующих варианта, эквивалентных по функциональному назначению системы, Si, 5э и 5з, параметры которых приведены в табл. 1.1. Отметим, что все О^О^.01, t'=l, 3 и все параметры целесообразно минимизировать. Таблица 1.1 Параметры Относительные показатели Тип системы ^ 4с i^, Вт 4 tt f '1 h/2 Л'3 усл. ед. Si 0,1 10 15 0,17 0.5 1,0 ^2 0,3 13 5 0,5 0,65 0,33 sl 0,6 7 10 1,0 0,35 0,67 Требования 0,6 20 15 1,0 1,0 1,0 технического задания ^0) Примечание. Здесь ^'i — время регулирования; '0'г — энергопотребление; ^з — сложность аппаратурной реализации; 0^ — директивные значения пара- метров. 3—785 33 В связи с тем что все требования ТЗ для всех систем выполнены и не требуется применять определеных усилий для достижения заданных директивных значений переменных, оказывается возможным вместо со- отношений (1.15) и (1.16), необходимых для определения весовых коэф. фициентов параметров, использовать выражения вида Д/М^-^Н^.-Ч^Ч^-Ы- Из табл. 1.1 следует, что min [f^]"^ =0,17; min {^^^О.Зб; min {^"Й =0,33. k В табл. 1.2 приведены результаты расчетов величин fih, c^ и ci на 1-й итерации. Величины 1ц взяты равными 0,5. Таблица 1.2 /, h f, /, ^ с! /i h 0,5 0,231 1,0 0,5 0,397 0,461 1,897 1,192 0,372 0,234 h 1,0 0,507 0,5 2,007 0,394 Рассмотрим формирование элементов первой строки табл. 1.2: г„ = о,5; i^ - ^f^|^f\ = (f\ -/„ | •i | /;-11 = =|0,17-l|/[0,17-l|=l,0; 3 'i3=l 0,17-0,5 1/1 0,17-11=0,397; с{1» ^ ^ = 1,897; k==i I 3 Ci ^i/^c^ =1,897/5,096=0,372. / * ч k=\ п По формуле с^"" '= ^ ^(r) /a рассчитывают весовые коэффици- k=l енты более высоких порядков. Результаты расчетов сведены в табл. 1.3. Из таблицы видно, что значения весовых коэффициентов парамет- ров стабилизировались к четвертой итерации. Согласно выражению (1.13) определим значение аддитивного кри" терпя для всех вариантов систем: FW (X) = 0,590; FW (X) = 0,466; FW (X) = 0,710. Поскольку стремимся минимизировать значение аддитивного кри- терия, наиболее предпочтительным оказывается вариант 82. 34 Таблица 1.3 № итерации Ci "2 с» 1 0,372 0,234 0,394 2 0,349 0,234 0,417 3 0,350 0,238 0,412 4 0,351 0,237 0,412 5 0,351 0,237 0,412 В настоящее время получили распространение интерак- тивные методы решения многокритериальных задач, когда информация о важности и предпочтениях приходит как от инженера-разработчика, так и от ЭВМ. Уточнение обоб- щенных критериев и упорядочивание критериев по важно- сти производится на основе диалога конструктора с ЭВМ. Часто для определения наилучшего решения конструктору приходится решать задачи структурной и параметрической оптимизации. При этом модель принятия решения описы- вается как задача многокритериальной оптимизации. В этом случае используют интерактивный режим оптими- зации или диалоговой оптимизации. Разработчик может изменить процесс решения задачи на любом этапе, пара- метры, метод решения, математическое описание задачи. Проблемами здесь являются разработка эффективных па- кетов прикладных программ, сценариев диалога, эвристи- ческих и точных алгоритмов проектирования с учетом рас- плывчатости и неопределенности интеллектуальной дея- тельности инженера-разработчика. 1.5. ВИДЫ ОБЕСПЕЧЕНИЯ И КЛАССИФИКАЦИЯ САПР Все определения, приведенные ниже, даны в соответст- вии с существующими ГОСТ и стандартами по автомати- зации проектирования. Система автоматизированного проектирования (САПР)— организационно-техническая система, состоящая из комп- лекса средств автоматизации проектирования (КСАП), взаимосвязанного с необходимыми подразделениями про- ектной организации П\, Пч, ...,/7„ или коллективом специа- листов (пользователей системы) и выполняющая автома- тизированное проектирование (рис. 1.5, а). Соответственно система автоматического проектирования выполняет авто- матическое проектирование без участия человека. У 35 Виды обеспечения САПР. Комплекс средств автомати- зации проектирования (К.САП) — это совокупность раз- личных видов обеспечения автоматизированного (автома- тического) проектирования (АП), необходимых для выпол- нения АП (рис. 1.5,6). Математическое обеспечение (МО) АП — это совокуп- ность математических методов (ММет), математических моделей (ММ) и алгоритмов проектирования (АлП), необ- ходимых для выполнения АП, представленных в заданной форме (рис. 1.6, а). Техническое обеспечение (ТО) АП — это совокупность взаимосвязанных и взаимодействующих технических средств, предназначенных для выполнения АП. Пример ТО АП ЭВА показан на рис. 1.6,6. Технические средства (ТС) Рис. 1.5. Система автоматизированного (автоматического) проектиро- вания (а) и комплекс средств автоматизированного (автоматического) проектирования (б) 36 выполняют определенную функцию в САПР и представля- ют собой компоненты ТО. Вообще говоря, компонент САПР—это элемент средства обеспечения, выполняющий определенную функцию. К ТС относятся устройства вычис- лительной и организационной техники, средства передачи данных, измерительные и другие устройства. Различают следующие группы ТС: подготовка и ввод данных. Группа предна- значена для автоматизации подготовки и редактирования данных при вводе в ЭВМ алфавитно-цифровой и графиче- ской информации. Группа дает возможность кодирования информации, нанесения данных на машинные носители, ввода данных в ЭВМ, визуального контроля и редактиро- вания данных при вводе информации; передача данных. Группа предназначена для обеспечения дистанционной связи технических средств по телефонным, телеграфным и специальным каналам связи; программная обработка данных. Группа включает в себя универсальные или специализированные ЭВМ, обеспечивающие прием цифровых данных с устрой- ства ввода или каналов связи, их программной обработки, накопления и вывода на машинные носители, устройства отображения и каналы связи. Позволяет изменить произ- водительность путем наращивания ЭВМ, использовать мультипрограммный и диалоговый режимы работы; отображение и документирование дан- н ы х. Группа предназначена для оперативного представ- ления и документирования проектных решений. Здесь ис- пользуют печатающие устройства и графопостроители, микрофильмы, микрофиши и устройства отображения ви- зуальной информации; архив проектных решений. Группа предна- значена для обеспечения хранения, контроля, восстановле- ния и размножения данных о проектных решениях и спра- вочных данных. Компоненты ТО создаются на базе серийных средств вычислительной техники общего назначения и специализи- рованных технических средств. В настоящее время преиму- щественно используют двухуровневую иерархическую структуру комплекса ТС САПР. Структура включает в се- бя компоненты центрального вычислительного комплекса (ЦВК) и компоненты терминального комплекса (ТК). Центральный ВК строят на основе ЭВМ, вычислительных систем и сетей ЭВМ коллективного пользования. Терми- 37 программ. Задержки ts могут быть различными для разных путей прохождения сигналов от входов к выходам и в об- щем случае функционального узла с п входами и т выхо- дами задаются в виде матрицы [т;/], l•=s•\, п, /==1, т, где •ч, — задержка распространения сигнала от t'-ro входа к f-му выходу. В отдельных случаях модель функционального узла мо- жет быть представлена в виде алгоритма, в котором дейст- вия выполняются над переменными U и Y вещественного типа. В таком виде удобно представлять сложные устройст- ва, например арифметико-логические, выполняющие дейст- вия над числами с плавающей запятой. Пример модели функционального узла Y:=X1 . Х2, где Y — идентификатор выхода; XI и Х2 — идентификаторы входов; :i! — символ выполняемой в функциональном узле операции (алгоритма) над операндами XI и Х2. Перемен- ные Y, XI и Х2 могут быть скалярами или векторами буле- вого или вещественного типа. Подобным образом описыва- ются шифраторы, сумматоры, схемы контроля четности и т. п. 4.8. МАТЕМА-1ИЧЕСКИЕ МОДЕЛИ ДЛЯ ЗАДАЧ КОНСТРУИРОВАНИЯ РЭА При автоматизированном конструировании пользовате- лю приходится принимать решения в условиях неопределен- ности, которые не имеют ни случайного, ни игрового харак- тера. Эта неопределенность лежит в самом существе про- цесса принятия решения и происходит от неопределенности условий, в которых необходимо принимать решение. Интенсивно развивающаяся в настоящее время теория расплывчатых (нечетких) множеств является попыткой со- здать более естественный и широкий математический аппз- рат для описания существующих неопределенностей мно- жеств решений. На практике, особенно при проектировании, приходится иметь дело с множествами, в которых нельзя указать рез- кую границу, отделяющую элементы, принадлежащие к дан- ному множеству и не принадлежащие к нему. Следует от- личать понятия случайности и расплывчатости. Случайность связана с неопределенностью, относящейся к принадлеж- ности или непринадлежности элемента к множеству. Рас- 196 плывчатое множество—это такое множество, в котором могут иметься различные степени принадлежности элемен- тов к данному множеству. Пусть задано множество X==[xi, хч, .... Хп}. Тогда рас- плывчатое множество АеХ есть совокупность кортежей А == « ^л (^,), л-,>}, л, 6Х, t == 1, п, где ^A{Xi) — степень принадлежности элемента Xi к А; ^д — функция, отображающая х,: в пространство принадлежно- сти М. Предполагается, что М — это интервал [О, I], при- чем 1 и 0 представляют высшую и низшую степени принад- лежности. Основное положение теории расплывчатых множеств со- стоит в том, что А несмотря на «размытость» границ зада- ется точно путем сопоставления каждому элементу л:еХ числа, лежащего между 0 и 1. Например, пусть Х=={2, 4, 6 ...}—множество неотрица- тельных четных чисел. Тогда расплывчатое множество А можно, например, определить как набор кортежей вида А-{<0,6;2>, <0,2;4>, <0,7;6>...}. Основой расплывчатого множества А называют множе- ство элементов X, для которых ^д (х) положительно. Носитель А есть множество элементов л-еХ, для которых I^A (х) положительно. Точкой перехода А называют элемент х, для которого ^д(х)==0,5. Одноточечным расплывчатым множеством (иногда используют термины «нечеткий», «раз- мытый») называют множество, носитель которого состоит из единственной точки. Тогда если А — одноточечное рас- плывчатое множество, то его обозначают А==ц/^, где ц— степень принадлежности л: к А. Тогда обыкновенное-мно- жество можно обозначить А==1/х. Расплывчатое множество рассматривают в виде объеди- нения входящих в него одноточечных множеств, Если А состоит из конечного числа элементов, то А = ^iLW^U- UlV^n - U И А-. Очевидно, что тогда конечное множество Х=={л:,, xi,... 197 ..., Хп} можно записать в виде X == 1/Л-1 U 1/^2 U-U l/^n = U Ух,. Пример 4.9. Пусть Х= {кристалл, плата, панель}; А—расплывчатое множество, определяемое признаком степень интеграции (СИ) элемен- тов. Тогда, например, можно записать: А=СИ большая/кристалл U СИ средняя/плата U Си малая/ па- нель. Степени принадлежности большая, средняя, малая также являют- ся расплывчатыми подмножествами множества W=OUO, 1UO, 2U, ... , UO, 9(J1. А эти подмножества можно определить, например, так: малая средняя . большая 0,5/0,1 1/0,2 0,8/0,3 0,6/0,4 1/0,5 0,9/0,6 0,7/0,7 0,8/0,8 1/1 Такая запись означает, что малая степень принадлежно- сти соответствует элементу 0,2, средняя степень принадлеж- ности — элементу 0,5, а большая степень принадлежно- сти — элементу 1. В практических задачах конструирования функция при- надлежности цл определяется исходя из конкретных усло- вий проектирования. При проектировании конструкций пользователю удобнее иметь дело с моделями, которые легко образуются, если элементы конструкций принять за точки, а связи между ни- ми — за линии. Такое представление объекта отличается высокой наглядностью, позволяет сосредоточить внимание на наиболее существенных связях, находить оптимальное решение задач проектирования. Использование аппарата теории графов для разработки алгоритмов конструкторского проектирования приводит нас к введению лишь некоторых определений, правил, теорем и положений из общей теории графов, которые будут представлять интерес в дальнейшем изложении. Объект, состоящий из двух множеств (множества точек и множества линий), которые находятся между собой в не- котором отношении, называют графом. Множество точек графа обозначают X={xi, Хч, ..., Хп}, |Х| =п и называют множеством вершин. Множество линий, соединяющих пары вершин (xs,x,)^X, называют множест- вом ребер или дуги обозначают U ={щ, и^,..., и.т}, |U|===w. Тогда графом можно считать объект, который обозначается 198 как G===(X,U) и состоит из множества вершин Х и множе- ства ребер или дуг U, находящихся между собой в некото- ром отношении. В общем случае множество U можно представить в виде lJ==U[JU|Jl3, где U —подмножество неориентированных ли- ний, для которых не существенно направление соединения вершин. Такое подмножество называют подмножеством ре- бер. Каждое ребро «(SD определяется неупорядоченной па- рой вершин Xi, Xj, которые оно соединяет, и записывается u/,=(Xi, х,) или iik==(x„ Xi). U—подмножество ориенти- рованных линий, для которых существенно направление соединения вершин. Подмножество U называют подмноже- ством дуг, причем каждая дуга «ге1Г определяется упоря- доченной парой (кортежем длины два) вершин xi, х,, кото- рые Uk соединяет, и записывается Uh==<.xi, Xj>. Подмно- жество U — подмножество линий, каждая из которых выходит и входит в одну и ту же соответствующую этой ли- нии вершину, и называется подмножеством петель. Каждая петля Ui-sL) может определяться упорядоченной или неупо- рядоченной парой, например,вида ". == (^, ^) или щ = <^, х,,>. Граф G=(X, U) (рис. 4.17), у которого О, I), U^0, называют смешанным. Рис. 4.17. Смешанный граф Рис. 4.18. Мультиграф Здесь |Х|==5, |U|=13,U=UUOUU; L = {MS, "4, "S> "7, "8, "8, "11 Ь О == {«i, Us, Ми}. U === {«г, Mm, «12}. 199 Граф G==(X, U), у которого U==U, a U, U==0, называ- ют ориентированным или орграфом. Граф G=(X, U), у которого U==U, называют неориен- тированным или неорграфом. Заметим, что подмножество петель можно рассматри- вать как ориентированные, так и неориентированные под- множества ребер. Обычно графы с петлями оговаривают особо. Рассмотрим неорграфы с петлями и без петель, которые будем называть просто графами. Граф G, у которого суще- ствует хотя бы одна пара вершин, соединяемых m ребрами «iSU, называют мультиграфом, а максимальное m—муль- тичислом графа G (ms{2, 3...}). Ребра, соединяющие одну и ту же пару вершин, называются кратными. На рис. 4.18 показан пример мультиграфа, у которого т==5. Если ребро UfcSU графа Q=(X, U) соединяет вершины Xi, Xj sX, т.е. Uk=={Xj, Xi), то говорят, что ребро Ui, инци- дентно вершинам Xi и х/. Аналогично и обратное: вершины Xi и х, инцидентны ребру и/г. Любые две вершины х,, х,^\ графа G называют смеж- ными, если существует соединяющее эти вершины ребро Mft<=U, т. е. Uh== (Xi, x,}. Если два ребра iik, UieU инцидент- ны одной и той же вершине, то их называют смежными. Следовательно, отношения инцидентности и смежности могут иметь место как на множестве X, так и на мно- жестве L). Граф G==(X,U) можно задать в различных формах. Основными из них являются геометрическая и мат- ричная. Основой геометрической формы задания графа является рисунок. Изображение графа в виде рисунка обладает на- глядностью, раскрывает содержательный смысл представ- ляемого объекта. Граф называют помеченным, если его вершины отлича- ются одна от другой различными метками, например х\, л"2, •••, Хп. Для конструирования необходима нумерация эле- ментов, поэтому в дальнейшем будем рассматривать поме- ченные графы. Большинство задач автоматизации конструирования удобно решать при использовании матричной формы зада- ния графа. Квадратную таблицу Р=\\гц\\пХп называют матрицей смежности, если ее элементы образуются по пра- вилу 200 (1, если вершина Xi соединена с х, ребром, т. е. Xi п, == | смежна Xj; I 0 в противном случае. Для мультиграфа | m, если вершина Xi соединена с x, m ребрами; r^ = j 0 в противном случае. Очевидно, что для рассматриваемых графовг,;==г,1Идля задания графа достаточно использовать половину матрицы R. Граф G (рис. 4.19) имеет следующую матрицу смеж- ности: Xl 1 R = =^2 1 Xs 1 Xi 1 •^1 Xt х» х* Л-, 1 1 1 1 Строки и столбцы матрицы R соответствуют вершинам графа G. На пересечении х, строки и х, столбца находится элемент Гц, соответствующий числу ребер, соединяющих Рис. 4.19. Пример графа вершины Xi и Xj. Заметим, что строки и столбцы матрицы R также можно нумеровать числами натурального ряда, со- ответствующими индексам помеченных вершин графа. Пет- ли в графе изображаются элементами гц=г,,, расположен- ными по главной диагонали матрицы R. Преимущество использования матриц смежности—это простота и фор- мальность преобразований над графами. Основной недоста- ток применения матрицы смежности заключается в том, что они занимают большой объем памяти в ЭВМ даже тогда, когда граф содержит только 0(Х) ребер. Если [U|^|X2!, то этот недостаток устраняется, если представить матрицу в виде списка. Такое представление графа требует памяти ЭВМ порядка 0(|X|+|U|). Прямоугольную таблицу вида 1==||Ы1-пхт 'называют матрицей инцидентности, если ее элементы образуются по правилу 201 д= fl, если вершина Xis инцидентна ребру «,; [ 0 в противном случае. Матрица инцидентности для графа G (рис. 4.19) имеет вид "1 "2 Us "1 "3 1 0 1 1 0 1 1 о 0 1 0 1 1 1 0 0 0 о 0 1 Строки матрицы I соответствуют вершинам графа, столб- цы — ребрам, а элемент iki указывает на инцидентность вершины Xk и ребра ui. В каждом столбце матрицы I рас- положено по две единицы, так как каждое ребро соединяет ровно две вершины. При наличии в графе петель соответ- ствующие им столбцы в матрице I будут иметь по одной единице, так как петля соединяет только одну вершину графа. Матрицы R и I задают однозначно информацию о графе. Граф G называется конечным, если множество его вер- шин и ребер — конечные множества. Далее будем рас- сматривать конечные графы, так как объекты проектиро- вания, представляемые графами, состоят из конечного чис- ла элементов. Граф G, у которого X=7^0, a U==0, называют нуль- графом, а его вершины — изолированными. Обозначают его Go. Граф G=(X, U)|X|=n называют полным, если между любой парой вершин Xi, y,sX имеется ребро «feSLI. Обоз- начают его Kn. Число ребер, инцидентных вершине A'(SX графа G, называется локальной степенью этой вершины и обозначается p[xi}. Тогда для графа G==(X, U), |X]==fl, 11) [ ==m, число ребер 1=1 Если в графе имеются петли, то каждую из них счита- ют дважды. Так как для полного графа на п вершин p(xi) =pte) ==...=р(л-„), то m=n (ra—l)/2. Подграфом графа G называют граф, у которого все вершины и ребра принадлежат G, т. е. G'= (Х^ И') — под- граф графа G==(X, U), если X'sX, U'sU и ребра U' соединяют только вершины X', 202 Суграфом G' = (X7, V) графа G == (X, И) называют граф, для которого Х'==Х, U'sU. Граф G называют дополнением графа G до полного, если он состоит из всех ребер полного графа Кп, не принад- лежащих G, т. е. G - KAG. На рис. 4.20, а показан суграф графа, изображенного на рис. 4.19. На рис. 4.20, б приведено дополнение его до полного. Маршрутом в графе G=(X, U) называют некоторую конечную последовательность ребер вида S==(xo, х\), (х\, Рис. 4.20. Суграф графа G (и) и дополнение графа G до полного (б) хг), ..., (^i-i, Xi), где Хо, x-i — начальная и конечная верши- ны соответственно. В конечном графе G можно выделить только конечное число маршрутов. Число рёбер в, маршру- те S называют его длиной. Маршрут, в котором нет повторяющихся ребер, назы- вают цепью. Замкнутую цепь, в которой XQ=X{, называют циклом. Соответственно цепи и циклы называют простыми, если они не содержат повторяющихся вершин, кроме, разу- меется, первой и последней в случае цикла. На рис. 4.21, а изображен неэйлеров граф. Здесь Si == (x^), (x^Xy), (ХуХ^), (х^х^), (х^, Xi), (х^, х^ — маршрут, Sg == (^1 х^, (х^ Д-д), (Ху х^), (х^ х^ — цепь, 53 == (Xs х^), (х-г, Ху), (Ху х^), (Ху х^) — цикл, 54 = (^1^2). (^г^з)> (-^s). (•^e) — простая цепь, Sg = (л-2 Ху), (Хд-^), (л-;,.^) ~ простой цикл. Матрица циклов графа G {рис. 4.21, и) имеет вид М, Xi ^ Хз ^ ^ ^0 I 1 1 0 1 1 о II 0 1 1 о 1 о III 0 1 1 о 1 1 203 Две произвольные вершины xi, лс^еХ графа называют связными, если существует маршрут S, в котором конце- выми будут вершины xi, Ху. Граф О называют связным, если любые две его вершины связаны. В противном случае G несвязан, а каждый из соответствующих его подграфов а) Рис. 4.21. Неэйлеров (а) и эйлеров (б) графы Gi, О;,..., Gi называют компонентой связности. При реше- нии задач конструирования важное значение имеют графы специального вида — эйлеровы и гамильтоновы. Связный граф G=(X, U) называется эйлеровым, если существует замкнутая цепь, проходящая через каждое его ребро только один раз. В эйлеровом графе все локальные степени четны. На- пример, граф О (рис. 4.21, а) не является эйлеровым, так как степени хг и хз нечетны. Говорят, что граф имеет эйле- ров цикл, если связан и все его локальные степени четны. Эйлеров цикл (ЭЦ) обозначается через Сэ. Для графа G (рис. 4.21, б) Сэ = (A-I х^) (л-з Ху) (Ху х^ (х^ х^) (х^ Ху) (х^ х^ (^ JV„) (Xg Ху) (Ху Xi). Цикл, проходящий по всем вершинам графа G один раз, называют гамильтоновым, а G называют гамильтоновым графом. Например, граф G (рис. 4.20, а) не имеет гамиль- тонова цикла (ГЦ), а граф G (рис. 4.21, б) имеетСщ =={xi, х<г, хз, л-4, xs, Хб). В отличие от ЭЦ для ГЦ неизвестен об- щий критерий существования. В основном известны только теоремы, дающие достаточные условия существования ГЦ. Теорема. Если в графе Gen вершинами для любой па- ры вершин Xi, Xj имеем Р (А',) + р (х^) > п, то G имеет ГЦ. Из теоремы следует результат Дирака, что граф имеет ГЦ, если для каждой его вершины p(.v,)^n/2. 204 Очевидно, что полный граф всегда содержит гамильто- нов цикл. Связный граф без циклов называют деревом я обозначают Т= (X, U), |Х|=п. Любое дерево Т имеет п—1 ребро. Начальную вершину называют корнем, из которого выходят ребра, называемые ветвями дерева. Оче- видно, что в дереве любые две вершины Xi, х, дерева свя- заны единственной цепью. В любом связном графе G можно выделить произвольное дерево Т, Для задач конст- руирования РЭА Наибольший интерес представляют де- ревья, у которых число вершин равно числу вершин гра- фа, из которого выделено это дерево. Такие деревья назы- вают покрывающими. Для одного и того же связного гра- фа можно выделить некоторое множество покрывающих деревьев. Теорема. Число покрывающих деревьев t графа Кл, со- держащего п вершин, составляет t^n"-2. Множество деревьев графа называют лесом. Задачи выделения эйлеровых и гамильтоновых циклов и покрыва- ющих деревьев связаны с задачами о лабиринте, комми- вояжере и с построением путей минимальной стоимости. Задача о лабиринте в терминах теории графов форму- лируется как задача отыскания в связном графе G== (X, U) такого маршрута, который начинается в заданной вершине л'1-sX и приводит в искомую Jf/sX, причем маршрут дол- жен содержать наименьшее число ребер. Пусть необходимо проложить сеть проводов, связываю- щих п терминалов вычислительной аппаратуры, причем так, чтобы из одного терминала можно было связаться с любым другим. Если из экономических соображений тре- буется, чтобы количество затраченного провода было ми- нимально, то граф, вершины которого соответствуют тер- миналам, а ребра — соединяющим их проводам, должен быть деревом. Задача состоит в определении одного из дп-2 возможных деревьев, соединяющих терминалы. Эту задачу можно усилить. Пусть G=(X, U)—связ- ный граф и каждому ребру Ui-eU ставится в соответствие некоторое неотрицательное число v(u), называемое его мерой. Необходимо найти покрывающее дерево Т, у кото- рого сумма мер, взятая по всем ребрам, m ^v(Ui)--mn. 1=1 205 Приведем алгоритм решения данной задачи. 1. В связном графе G == (X, U), |Х| == п определяется ребро с наименьшей мерой и\. 2. Строят по индукции последовательность ребер и<г, из,„.,ип-1, выбирая на каждом шаге ребро, не совпадаю- щее с предыдущим, с наименьшей мерой и не образующее циклов с предыдущими ребрами Ui. 3. Получается подграф Т графа G с ребрами «i, ...,Un-i, который и является искомым деревом с наименьшей сум- мой мер. Расстоянием di,, между вершинами xi, Jf/sX гра- фа G=(X, U) называют длину кратчайшей цепи, соеди- няющей эти вершины. Под длиной цепи понимают число входящих Б нее ребер. Функцию расстояний для графа G удобно задавать мат- рицей расстояний D=\\di, или ее списком. ',/11 пХп ' 0, если Xi = Xj; . di,„ если Xi i= Xj. Элемент матрицы D определяется следующим образом: di.i- Для графа G (рис. 4.21, б) матрица расстояний имеет вид D = 123456 1012221 2101121 3210122 4211011 5l2 2 2 1 0 1 6|l 1 2 1 1 0 Для задач конструирования представляет интерес на- хождение функции расстояний для графов Gr частного вида, называемых координатной решеткой. В графе Gr== = (Хг, Ur) множество вершин Хг соответствует узлам ре- шетки, а множество Ur ребер — горизонтальным и верти- кальным отрезкам, соединяющим узлы решетки. Пример графа Gr—координатной решетки—показан на рис. 4.22. Расстояние между двумя смежными вершинами в ре- шетке Gr, называемое шагом решетки, принимают равным единице. Между двумя произвольными вершинами в ре- шетке Gr расстояние ^>/= |Si—S^|+ \ti—t,\, где si, s, и ti, t, — координаты вершин xi, x,G.G.r. 206 Обычно задаются размеры решетки pXq, где р — число узлов решетки по оси s, a q — по оси t. Например, для графа Gr (рис. 4.22) расстояние ^(<Ч1) =c\s,— sJ + i/e —^i i = 14 — О I + (1 — 2) == 5. Если произвольный граф G отображается в Gr так, что любые вершины G размещаются в узлах решетки, то рас- стояние между вершинами G определяется как расстояние между соответствующими узлами решетки Gr. Любой граф G может быть отображен в решетку Gr. Для подсчета суммарной длины L(G) ребер графа G, ото- Рис. 4.22. Граф Gr — коорди- натная решетка Рис. '4.23. Граф G браженного в решетку Gr, введем понятие матрицы гео- метрии Dy, представляющей собой часть матрицы расстоя- ний D, в которой исключены элементы d;,„ если вершины Xi, Jc/sX не смежны в графе G. Для построения матрицы геометрии Dy графа G необ- ходимо каждый элемент матрицы D умножить на соответ- ствующий элемент матрицы смежности R, т. е. Dy ==s ==\\ri,jdij\\ny.n- Сумма элементов матрицы Dy определяет удвоенную суммарную длину L(G) ребер графа G при данном отображении его в решетку Gr. С задачей определения гамильтоновых циклов и крат- чайших расстояний тесно связана задача о коммивояжере, суть которой в следующем: имеется N городов (вершин графа) и заданы расстояния между городами. Коммивоя- жер находится в городе х\. Ему необходимо посетить толь- ко по одному разу все остальные N—1 городов и вернуть- ся в х\, чтобы общее пройденное расстояние было мини- мальным. 207 Рассмотрим описание алгоритма. Сначала строят все кратчайшие пути, соединяющие х\ с любой вершиной / (;==2, 3,...,N). Длина любого из этих путей равна рассто- янию di,/ от х\ до Xi. Далее определяют путь минимальной длины, соединяющий х\ с Xi и проходящий через одну про- межуточную вершину Хгл. Зная длину минимального пути из Xi в Xi с одной промежуточной вершиной, можно опре- делить длину пути минимальной длины между х\ и Xi, про- ходящего через две промежуточные вершины, три и т.д. При увеличении числа промежуточных вершин обяза- тельно будет построен путь минимальной длины из х\ в лю- бую вершину, проходящий через все остальные вершины. Тогда можно определить минимальный путь с учетом воз- вращения в Xi. Пример 4.10. Пусть для графа G (рис. 4.23) задана матрица рас стояний D=3 1234 О 37 47 27 7 0 27 2 20 15 0 45 • 31 25 35 0 Согласно алгоритму определяют кратчайшие пути, ведущие из к\ в Xi (1=2, 3, 4). Получают di,^37, di,3=47, di,4=27. Далее находят пути минимальной длины, соединяющие х\ с Хг и проходящие через не- которую промежуточную вершину. Пусть /=2, тогда длина пути из Xt В Хч 42=^1,3+^=47+15=62; ^,2 = ^1,4 + ^4,2 = 27 + 25 = 52. Аналогичные вычисления выполняют для Хз и х^. Результаты све- дены в таблицу: г=2 1=3 /=4 Xi di,2=37 di, з=47 di, 4=27 Ч df 2 =62 <2 -52 <з =64 <3 =62 4,4 =39 ^,4 ==92 х» d^=120, п. Многие задачи контроля схем сводят к различным тож- дественным преобразованиям заданных графов этих уст- ройств. Тождественные преобразования графов, сводимые только к переобозначению вершин и ребер, приводят к по- лучению изоморфных графов. Два графа G=(X, L)) и G'== (X7, V) называют изо- морфными, если можно установить взаимно однозначное соответствие Х--" X', U^U' такое, что если (л"„ A'/)?X4-" •"•(л;;, л-^^Х7, то ребро и=(х„ Xj)e=V^ 1]'={х'^ A^GIT. Изоморфные графы могут быть получены один из дру- гого путем перенумерации их вершин. Очевидно, что изо- морфизм есть отношение эквивалентности на графах. Если изоморфные преобразования проводятся с графом, задан- ным матрицей смежности, то они сводятся к перестановке местами соответствующих строк и столбцов. Известно, что в общем случае для определения изоморфизма графов не- обходимо сделать п\ сравнений или перестановок строк и столбцов матрицы, что для графов с тг>30 не под силу даже современной ЭВМ. Поэтому необходимо применить тот или иной эвристический алгоритм поиска по дереву ре- шений. При конструировании схем к их топологическому чер- тежу предъявляется требование получения, либо плоского изображения схем, либо плоского изображения частей схем. В этой связи возникает задача определения планарности графа. Граф G=(X, U) называют плоским, если его множест- во ребер расположено на плоскости таким образом, что ребра имеют общие точки лишь в вершинах. Граф, изо- морфный плоскому и расположенный на плоскости с пе- ресечением ребер, называют планарным. Область плоскости, огр-аниченная ребрами плоского графа, внутри которой нет вершин ребер, называют гранью. Ребра грани образуют простой цикл. Заметим, что плос- кий граф имеет всегда одну бесконечную грань, не ограни- ченную ребрами. Существует формула Эйлера, позволяю- щая установить связь между числом граней, числом вер- шин и числом ребер плоского графа: 14* 211 где / — число граней плоского графа. Определять планарность графа можно с помощью раз- личных критериев. Рассмотрим основной из них. Пусть задан граф 0==(Х, U). Подразбиением ребра и>!==(х,, Xj) называют замену его двумя ребрами Upi== == (Xi, Хр) и Up2= (Xp, Xj) с введением новой вершины л-р. Два графа называют гомеоморфными, если они обладают изоморфными подразбиениями. Теорема Понтрягина — Куратовского. Граф планарен тогда и только тогда, когда не содержит подграфов, гомеоморфных полному графу Ks (рис. 4.24, и) и полному двудольному графу Кз,з (РИС. 4.24,6). Рис. 4.24. Полный граф /<5 (а) и полный двудольный граф Яз.з (б) Очевидно, что граф планарен тогда и только тогда, ког- да планарны все его связные компоненты. Поэтому для определения планарности рассматривают связные графы. Распространенная методика определения планарности за- ключается в нахождении в графе G максимального цикла С (лучше всего гамильтонова) и размещении его на плос- кости в виде замкнутой самопересекающейся кривой. Да- лее в оставшейся части определяют пересекающиеся по ребрам пути и предпринимают попытки разместить каж- дый из этих путей либо полностью внутри С, либо полно- стью вне С. Если таким "образом размещается весь граф, то он планарен, в обратном случае не планарен. Основная проблема — иметь возможность генерирования множества путей, выбора областей для пленарного размещения и пе- рестановки путей. Сложность алгоритма—О (га). Число попарных пересечений ребер (иногда называется числом скрещиваний) на плоскости обозначается P(G) и для полного графа определяется выражением ^ I 1/64 (га — I)2 (га •— З)2, если га нечетно; i 1/64и (га — 2)2 (га — 4), если га четно. 212 Зная, что Р(К5)==1, можно определить минимальное число пересечений для полного графа с любым числом вершин. Часто при описании элементов системы связи необхо- димо учитывать направление. Орграф G==(X, U) будем обозначать D=(X, U). В графе D маршрутом считается чередующаяся последо- вательность вершин и дуг: (XQ, щ, Xi,...,Un, Хп), в которой каждая дуга м/== (А',-Ь Xi). Путь — это маршрут, в котором все вершины различны. Контур—это простой замкнутый маршрут, у которого все вершины различны за исключени- ем первой и последней. Если существует путь из Xi в х,, то говорят, что Xj достижима из Xi. Граф D называют сильно связным, если любые две его вершины взаимно достижимы. Матрицей смежности графа D называют матрицу R(D)==||/-,/||„xn, причем _ f 1, если — дуга графа D; [ 0 в противном случае. Так как ri,, =7^ г/;, то матрица несимметрична относи- тельно главной диагонали. Заметим, что в графе D дуга и, есть кортеж, т.е. упоря- доченное множество из двух вершин. Дуга и;=<х„ х,-> считается положительно инцидентной ее конечной верши- не Xj. Число дуг, положительно инцидентных вершине х„ называют полустепенью захода и обозначают р+(^;). От- рицательную степень х/ определяют аналогично, называют полустепенью исхода и обозначают р~(х/). Очевидно, что р{х,) ==p+{X|}-sf-p~{Xj). Так как дуга по- ложительно инцидентна только одной вершине х, и отри- цательно инцидентна той же самой вершине Хц то 2 p4-^)- 2 P-(^)=|U|, ^6Х ^(ЕХ Элементы матрицы инцидентности 1(D) графа D при- нимают значения 0, +1,—1. Элемент равен нулю, если вер- шина не инцидентна дуге, -J-1, если дуга ориентирована от вершины, и —1 в противном случае. Заметим, что любой неорграф G можно перевести в ор- граф D путем замены каждого ребра двумя противополож- но направленными дугами. Поэтому многие результаты для неорграфов справедливы и для орграфов. 213 Рис. 4.26. Граф Кенига К(Н) <- Рис. 4.25. Гиперграф Н= (X, Е) В описанных выше графах использовались бинарные отношения на множестве вершин. Заметим, что в общем случае на множестве вершин можно задать й-местные от- ношения. Такое обобщение графа позволяет строить объ- екты, в которых каждое ребро может соединять не только две вершины, но и любое подмножество множества вершин. Объект Н = (X, Е) будем считать гиперграфом, если он состоит из множества вершин Х и множества ребер Е, •причем каждое ребро /,sE представляет собой некоторое подмножество вершин, т.е. /,?X. Если у /»sE( | Е| ==2), то гиперграф Н преобразуется в граф G без изолирован- ных вершин. На рис. 4.25 показан пример гиперграфа Н==(Х, Е), |Х|==6, |Е|=4; ребро 1з с J^|==1 есть петля. Ребрами являются: li={xi, Xi, Хз}, ls=[xi, Xs, х^ Xs}, /3= ={Хб}, 1^=={х\, Хц, хз, Xi, хц, хв}. В гиперграфе Н=(Х, Е) две вершины считаются смежными, если существует ребро li, содержащее эти вершины. Соответственно два ребра яв- ляются смежными, если их пересечение — непустое под- множество. Матрицей инцидентности гиперграфа называют матри- цу l(H)=\\ai,j\\mXn, причем а,- ' 1, если Xj^li; .0, если х^ I,. Для гиперграфа Н (рис. 4.25) матрица инцидентности примет вид •^1 •^2 ^3 ^4 ^5 '^9 I, 1 11000 0110 1 (Н) = k \ \ /з о о о о о i I, I I 1 1 1 1 214 При решении некоторых задач конструирования возни- кает необходимость в установлении соответствия между гнперграфом Н==(Х, Е) и графом К(Н)=(Х, Е, V), ко- торый называют графом Кенига. Граф К(Н) является дву- дольным, причем Х — это одно подмножество его вершин (X—множество вершин соответствующего гиперграфа); Е—это второе подмножество его вершин, т.е. множество ребер соответствующего гиперграфа. При этом вершины Xi^\ и //еЕ в К(Н) смежны тогда и только тогда, когда в гиперграфе Н вершина л"; принадлежит ребру /,. На рис. 4.26 приведен граф Кенига для гиперграфа Н (см. рис. 4.25). В некоторых случаях для построения схем используют расплывчатые графы и гиперграфы. Граф G==(X, U) называют расплывчатым, если для каждой вершины х,еХ множество U является расплывча- тым. Множество U характеризуется функцией принадлеж- ности р1и{х), принимающей значения из отрезка [0,1]. Оче- видно, что если [iu(x} для любых х, ysX принимает зна- чения 0 или 1, то расплывчатый граф G становится обыкновенным графом. Для расплывчатого гиперграфа функция принадлежности определяется так же, как и для расплывчатого графа. При решении задач автоматизации основные свойства и характеристики объектов описывают с помощью фор- мальных математических объектов, обеспечивающих аде- кватность и сохраняющих наглядность и необходимую со- держательность. При решении задач с помощью САПР и при разработке компонентов КСАП возникает необходи- мость построения различных ММ и выбора из них наибо- лее приемлемой. Сформулируем основные требования, предъявляемые к ММ: адекватность и простота представления исходного объекта; информационная сложность, т. е. возможность пе- рехода от одной ММ к другой, от объекта к модели и об- ратно; разумный объем памяти ЭВМ, отводимый для хра- нения информации о модели; степень разработанности математического аппарата для оперирования с ММ; прос- тота обработки. Очевидно, что самой лучшей моделью является сам объ- ект. Построение его ММ вызвано попытками формализо- вать и алгоритмизовать процесс проектирования, а также необходимостью минимизации объема памяти ЭВМ для 215 представления модели. В этой связи рассматриваемые мо- дели не могут полностью отвечать всем требованиям опи- сания объекта, а могут лишь описывать его части. Для этой цели используют теоретико-множественные подходы. Для правильного моделирования объекта необходимо определить все свойства объекта и каждый раз подбирать абстрактную формальную модель, чтобы между объектом и его моделью можно было устанавливать различные виды изоморфизма. В конструкторском проектировании выделяют ММ схем (структурных, функциональных, электрических), монтаж- ного пространства, самих конструкций. Использование графотеоретических моделей объектов сохраняет всю наглядность и содержательность описыва- емых объектов и позволяет строить формальные алгоритмы конструирования, которые легко обрабатываются на ЭВМ. Любая функциональная или принципиальная схема объекта состоит из набора элементов, соединенных меж- ду собой заданным образом. Тогда схему ЭВА можно рассматривать как некоторое множество элементов х^ Хч, .... Хп, соединенных между собой цепями из мно- жества Е. Такое представление схемы обычно называют схемой соединений или коммутационной схемой. На рис. 4.27 по- казан условный фрагмент схемы. Каждый элемент схемы имеет некоторое множество соединительных выводов, ко- торые будем называть множеством контактов и обозначать C=={ci, C2,...,Cp}. Кроме элементов и контактов в схеме имеются внешние контакты Со, которые осуществляют связь рассматриваемой схемы с другими. Два контакта считаются связанными, если объединяют- ся одной электрической цепью. Под электрической цепью &г Coi е-i с,г 1 ^2 2 Саз—о о— coг с е+ "1 \Cis с и сгз ГУ е? —о ^ е! Уг - ^2 г о— CJI\ ^з Cifi с^г Сд^ Рис. 4.27. Условный фрагмент схемы 216 понимается некоторое множество эквипотенциальных кон- тактов. Рассмотрим несколько способов задания схем РЭА и ЭВА графами, гиперграфами и их матричными и списко- выми эквивалентами. Зададим схему в виде графа G==(XUE|JC, U), где Х— вершины графа, соответствующие элементам схемы; Е—• вершины, соответствующие цепям схемы; С—вершины, соответствующие контактам элементов. Множество ребер U состоит из элементных F и сигнальных W ребер, причем U=F|JW. Ребра-подмножества F определяют принадлеж- ность контактов из С элементам Х и задаются парами {х:, Рис. 4.28. Граф G=(XUEUC, V) фрагмента схемы с/с). Ребра-подмножества W задают вхождение контактов из С в цепи Е и описываются парами (с/г, I;). На рис. 4.28 показан граф схемы рис. 4.27. Обычно граф, С задается в виде двух матриц и а\. fl, если контакт с; 6/,; |С1 [О в противном случае; 1, если с,6Х,; А, и а2., |Х|.|С| '^ О в противном случае. Граф также задают в виде матрицы цепей Г== [/,/lnXfe, строки которой соответствуют элементам схемы, а столб- цы — контактам. Если элементы 'имеют различное число выводов, то в качестве k принимается max/Ci, f=0,l... Эле- 217 мент in — номер цепи, связанный с контактом с, элемен- та Xi. Заметим, что если в матрице Т элементы fii=tpy=... ..."fctp.TO это означает, что контакты /',