автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Методы и алгоритмы оптимизации решения комплексной задачи проектирования РЭА

ВВЕДЕНИЕ.

ГЛАВА I. ЗАДАЧИ КОНСТРУКТОРСКОГО ЭТАПА ПРОЕКТИРОВАНИЯ РЭА

И ЭВА И ИХ ОБЩАЯ МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА

§1.1. Неформальная постановка комплексной задачи проектирования

§1.2. Математическая модель элементов схем РЭА и отношения между ними.

§1.3. Математические модели конструкций узлов РЭА и условия размещения в них элементов.

§1.4. Математическая постановка комплексной задачи проектирования РЭА

§1.5. Основные особенности комплексной задачи

§1.6. Математическая постановка задач проектирования цифровых узлов.

ВЫВОДЫ ПО ГЛАВЕ

ГЛАВА II ОБЩАЯ СХЕМА РЕИЕНИЯ КОМПЛЕКСНОЙ ЗАДАЧИ

ПРОЕКТИРОВАНИЯ РЭА

§2.1. Выбор критерия оптимальности задачи и задание отношения предпочтения на множестве ее решений

§2.2. Построение приближенных моделей задач формирования наборов узлов и назначения в них элементов

§2.3. Общая схема получения приближенных решений комплексной задачи проектирования РЭА

ГЛАВА III СПОСОБЫ ЗАДАНИЯ ВАРИАНТОВ FEIfEHM ЗАДАЧ КСНСТЕУКТОРСКОГО ЭТАПА ПРОЕКТИРОВАНИЯ РЭА НА ПЕРЕСТАНОВКАХ

§3.1. Использование принципа прямого отображения для задания вариантов решения.

§3.2. Общая схема метода последовательно-группового размещения

§3.3. Алгоритмы решения задач, реализующие метод последовательно-группового размещения

3.3. [[.Построение вариантов решения задач назначения элементов.

3.3.2 .Построение вариантов решения задач проектирования цифровых узлов. вывода ПО ГЛАВЕ.

ГЛАВА 1У СТАТИСТИЧЕСКАЯ ОПТИМИЗАЦИЯ ФУНКЩОНАЛСВ НА

ПЕРЕСТАНОВКАХ

§4.1. Рандомизация задачи и анализ некоторых схем последовательной статистической оптимизации

§4.2. Непараметрический подход.10?

§4.3. Основные параметры метода.

ВЫВОда ПО ГЛАВЕ

ГЛАВА У РЕ ПЕНИЕ НЕКОТОРЫХ ПРАКТИЧЕСКИХ, МОДАЛЬНЫХ И

ТЕСТОВЫХ ЗАДАЧ ПРОЕКТИРОВАНИЯ РЭА И ЭВА

§5.1. Решение задач конструкторского этапа проектирования

5.1.1.Решение известных и практических задач назначения элементов в узлы ЭВА.

5.2.2.Решение тестовых и практических задач размещения элементов ЭВА

§5.2. Решение некоторых задач конструкторского этапа проектирования РЭА.

ВЫВОда ПО ГЛАВЕ.

Автоматизированное проектирование радиоэлектронной (РЭА) и электронно-вычислительной аппаратуры (ЗВА) в настоящее время представляет не только теоретический, но и практический и производственный интересы. Как отмечается в предисловии к работе / I /, численность инженерно-технических работников, занятых конструированием и технологической подготовкой производства достигает 50-60$ и более от общей численности рабочих, занятых на производстве. Именно поэтому в решениях

XX7I съезда КПСС предусматривается "расширять автоматизацию проектно-конструкторских и научно-исследовательских работ с применением электронно-вычислительной техники" /2/.

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

Для синтеза конструкции РЭА и ЭВА в связи с трудностью построения общей формальной модели задачи конструкторского проектирования в настоящее время, как правило, используются методы и алгоритмы решения отдельных задач: выбора набора узлов для реализации устройства, компоновки узлов, размещения элементов в узлах и трассировки соединений /4, 5, 6, 7/. Такая декомпозиция позволяет уменьшить размерность решаемой задачи, но, естественно, вызьюает ухудшение качественных показателей конструкции проектируемого устройства в целом. В первую очередь это ухудшение вызывается взаимосвязью решаемых задач и, как следствие, существенной зависимостью результатов решения каждой последующей задачи от результатов, полученных при решении предшествующих задач. Так, выбор набора узлов в значительной степени влияет на результат решения задачи компоновки, а решение задачи компоновки, в свою очередь - на качество последующего размещения элементов и т.д.

С математической точки зрения задачи конструкторского этапа проектирования РЭА и ЭВА относятся к классу, так называемых, np - полных задач. В настоящее время не известны алгоритмы их решения, обладающие полиномиальной сложностью. Более того, существует гипотеза, что такие алгоритмы для np - полных задач разработать невозможно /8, 9/. Вследствие указанной причины для решения задач конструкторского этапа проектирования наиболее широкое применение получили эвристические методы и алгоритмы.

Первые работы, затрагивающие в той или иной степени вопросы решения задач конструкторского этапа проектирования РЭА и ЭВА, появились в начале 50-х годов. В частности, пионерский характер носит статья С.Крея и С.Киша /10/, в которой рассматривается задача компоновки структуры проектируемой ими ЭВМ по конструктивным узлам. В дальнейшем количество публикаций, связанных с решением задач конструкторского этапа проектирования РЭА и ЭВА, возрастало чрезвычайно быстро и продолжает нарастать в настоящее время. Вследствие этого рассмотрение всех работ, связанных с вопросом автоматизированного проектирования РЭА и ЭВА, в кратком обзоре является весьма проблеме-тичным. Достаточно полное описание существующих методов и алгоритмов решения задач конструкторского этапа проектирования приведено в работах /4-7, 11-28/. Рассмотрим некоторые подходы, получившие широкое применение в практике проектирования РЭА и ЭВА или отличающиеся оригинальностью и новизной, непосредственно связанные с решением рассматриваемых в настоящей диссертационной работе задач.

Прежде всего остановимся на задаче выбора рационального набора узлов. Математическая постановка этой задачи может быть осуществлена с использованием результатов, приведенных в /29/, однако, практическое использование такой постановки затрудняется необходимостью учета ряда факторов, зависящих от специфики конкретного производства /3, 31/. Непосредственно связанные с задачей выбора наборов узлов вопросы построения размерно - параметрических рядов конструкций РЭА рассматриваются в работах /3, 31, с£/.

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

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

Для решения задач разбиения в настоящее время широко используются последовательные методы и алгоритмы (метод максимальной конъюнкции-минимальной дизъюнкции /34/ и его многочисленные модификации /4, 36, 37/). Основу этих методов составляет последовательная процедура выделения из исходной схемы связанных групп элементов. Последовательные методы являются особенно эффективными при разбиении схем с повышенной связностью между элементами.

Широкое применение для решения задачи назначения элементов схемы в узлы получили алгоритмы итерационного типа /4/. Характерным для алгоритмов этого типа является требование начального варианта и наличие некоторого рационального варианта назначения элементов на каждом шаге (итерации) их работы. Начальные.варианты, как правило, получают алгоритмами последовательного типа или вручную. Основой алгоритмов итерационного типа является процесс обмена местами элементов, или групп элементов, с целью минимизации критерия качества. Наиболее распространенным алгоритмом этого типа является алгоритм парных перестановок /20/, заключающийся в последовательной минимизации связей между узлами путем парных замен элементов в разных узлах.

Среди других алгоритмов итерационного типа выделим алгоритмы последовательного разделения /37/ и последовательного выделения /4, 38/. Эти алгоритмы особенно эффективны для разбиения схем, содержащих сильно связанные группы элементов, в случае, когда размеры этих групп приблизительно равны.

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

Для решения задач размещения элементов РЭА и ЭВА в дискретном монтажно-коммутационном пространстве (МКП) (наборе фиксированных позиций) используются методы и алгоритмы, схожие с используемыми для задач назначения элементов в узлы. Поэтому рассматривать их не будем, а остановимся только на вопросах, связанных с размещением элементов в нерегулярных МКП. Решение этих задач производится, как правило, с использованием двух подходов. Первый подход заключается в наложении на непрерывные МКП дискретной сетки, в узлы которой и размещаются элементы. Некоторые алгоритмы, реализующие указанный подход, рассматриваются в работах /4, 6, 28/.

Существенно более трудным, но более эффективным, является второй подход, при котором размещение элементов производится непосредственно в непрерывном МИЛ. Задача размещения в этом случае сводится к задаче размещения геометрических объектов /24, 42, 43, 41/ в заданной области.

Известны некоторые работы, посвященные совместному решению задач конструкторского этапа проектирования РЭА и ЭВА /44, 45, 46, 47, 48, 49, 50/. Эффективность решения при этом существенно определяется построением математической модели задачи и используемыми для ее решения методами. Основные затруднения, возникающие при совместном решении задач проектирования, в основном,вызваны необходимостью учета отношений, порождаемых реальной геометрической формой элементов схемы. Эти отношения, в первую очередь, определяются условиями взаимного непересечения элементов схемы при их размещении в узлах и условиями взаимного непересечения элементов и границ МКЯ узла. Совместное решение задач конструкторского этапа проектирования в общем случае сводится к решению задач векторной оптимизации /51/. Методы и различные подходы к решению задач векторной оптимизации рассмотрены в работах /5£, 53, 54, 55, 56, 57, 58, 59, 60/.

Для решения ряда задач конструкторского этапа проектирования могут быть использованы и некоторые более общие математические методы, разработанные для решения задач целочисленного программирования. Здесь отметим метод последовательного анализа и отсева вариантов /61,62/, метод ветвей и границ /63,64/, метод отсечения /65/, метод вектора спада /66/ и метод сужающихся окрестностей /67/. Б этих методах полный перебор всех возможных вариантов решения задачи заменяется сокращенным (направленным) перебором, обеспечивающим отбрасывание неперспективных вариантов и тем самым увеличивающим эффективность поиска.

Диссертация является продолжением исследований, проводимых в Харьковском ордена Трудового Красного Знамени институте радиоэлектроники им.- акад. М.К.Янгеля и Институте пробV лем машиностроения Ж УССР под руководством профессора Ю.Г.Стояна, направленных на разработку способов формализа- \ ции задач геометрического проектирования, задач САПР ,; методов и алгоритмов решения оптимизационных задач. В частности, метод последовательно-одиночного размещения, используемый при разработке метода последовательно-группового размещения, предлагаемого в настоящей работе, рассмотрен в работе /42/. Идея, лежащая в основе упоминавшегося ранее метода сужающихся окрестностей, использована при разработке предлагаемого в работе непараметрического статистического метода последовательной оптимизации. Дальнейшее развитие она получила в работах /43,68/. В них основной акцент делается на использование параметрических законов, а вопросы построения непараметрических методов адаптивного случайного перебора не рассматриваются. В настоящей диссертационной работе основное внимание уделено именно непараметрическому подходу, т.к. он становится более логичным, обоснованным и,что наиболее важно, эффективным при решении задач конструкторского этапа проектирования РЭА большой размерности.

Диссертация состоит из пяти глав.

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

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

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

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

В пятой главе описываются результаты применения предлагав мых методов и алгоритмов для решения практических задач конструкторского этапа проектирования РЭА. Рассмотрены задачи покрытия, назначения элементов в узлы и размещения элементов в узлах для случаев непрерывного и дискретного монтажно-коммутационных пространств. Приводятся результаты решения практической комплексной задачи проектирования и тест-задачи Штейнберра. Иллюстрируется процесс решения указанных задач при помощи предлагаемых методов. Осуществляется сравнение полученных результатов с решениями, полученными конструктором, а также с известными из литературы решениями.

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

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

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

- предложены алгоритмы, построенные по общей схеме метода последовательного анализа и отсева вариантов, позволяющие находить оптимальные решения рассматриваемой комплексной задачи проектирования РЭА с учетом введенных предпочтений;

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

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

- исследована сравнительная эффективность предлагавмых методов при решении тестовых и практических задач конструкторского этапа проектирования РЭА.

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

Диссертационная работа выполнена в Харьковском ордена Трудового Красного Знамени институте радиоэлектроники им. акад. М.К.Янгеля в период с 1978г. по 1984г. в соответствии с планом аспирантской подготовки и планами научно-исследовательских и госбюджетных работ:

- "Разработка комплекса программ оптимального раскроя промышленных материалов для подключения их в состав математического обеспечения автоматизированной системы технологической подготовки производства (IP гос. per. 78023102);

- "Разработка математического обеспечения ИШ АСУ цехом" (Р гос. per. 79079'095);

- "Разработка комплекса программ математического обеспечения автоматизированной системы проектирования радиоэлектронной аппаратуры" (Р гос. per. 80000478);

- "Исследование возможностей создания микроэлектронной аппаратуры методом установки ИС в кремниевую подложку эвтектической пайкой (№ гос. per. 01820086378);

-"Система автоматизированного проектирования плат с неоднотипными элементами под комбинированный монтаж" (№ гос. per. 01829010998);

-"Разработка математического обеспечения для проектирования двухслойных печатных плат" (Р гос. per. 01840062175);

- теме У.9.3.7 "Разработка методического обеспечения для решения задач проектирования радиоэлектронной аппаратуры и использование результатов в учебном процессе" проблемы

У.9."Повышение эффективности и качества учебного процесса на основе широкого использования ЭВМ и видеотерминальных устройств";

- договором о научно-техническом сотрудничестве с Институтом проблем машиностроения АН УССР.

Основные результаты диссертационной работы докладывались и обсуждались на I Всесоюзном симпозиуме "Статистический и дискретный анализ нечисловой информации, экспертные оценки и дискретная оптимизация" (Алма-Ата, 1981г.), УН Всесоюзном симпозиуме "Системы программного обеспечения решения задач оптимального планирования"(Нарва-Йыэссу, 1982г.)f II Всесоюзном симпозиуме "Планирование эксперимента, оптимизация и практические приложения" (Харьков, 1984г.), II Всесоюзном сове

- 15 щании "Методы и программы решения оптимизационных задач на графах и сетях" (Улан-Удэ, 1982г.), Всесоюзном совещании "Случайный поиск в угольной промышленности" (Кемерово, 1984г.), Всесоюзной конференции "Теоретические и прикладные вопросы разработки, внедрения и эксплуатации систем автоматизированного проектирования радиоэлектронной аппаратуры" (Цахкадзор, 1983г.), Всесоюзной конференции "Вероятностные методы и средства" (Новгород, 1983г.), научно-технической конференции "Контроль и автоматизированное проектирование монтажа узлов и устройств цифровой аппаратуры" (Каунас, 1981г.), научно-технической конференции "Автоматизированное техническое проектирование электронной аппаратуры" (Каунас, 1982г.), 10-й Юбилейной научно-технической конференции "Автоматизация конструкторского проектирования РЭА и ЭВА" (Пенза, 1983г.), научно-технической конференции "Применение систем автоматизации проектирования в машиностроении" (Свердловск, 1983г.), II Республиканской научно-технической конференции "Моделирование и автоматизация процессов проектирования, изготовления и эксплуатации сложных систем" (Одесса, 1983г.), деловой встрече ученых "Случайный поиск в задачах дискретной оптимизации" (Харьков, 1983г.), школе-семинаре "Дискретная оптимизация: методы и приложения" (Севастополь, 1984г.), Республиканской конференции молодых ученых (Харьков, 1983г.), ХУТ-ХУТП научно-технических конференциях профессорско-преподавательского состава Харьковского института радиоэлектроники (Харьков, 19781983г.), а также на семинарах Научного совета АН УССР по проблеме "Кибернетика" в Киеве, Харькове в 1979-1983 годах и научно-технических конференциях молодых ученых Института проблем машиностроения АН УССР (Харьков, 1979-1983г.).

Основные результаты диссертации опубликованы в /69-78/.

Основные результаты диссертационной работы следующие.

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

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

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

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

6. Для минимизации функционалов на перестановках предложен непараметрический статистический метод последовательной оптимизации.

7. Описаны результаты решения известных, тестовых и практических задач проектирования РЭА.

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

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

заключении;

1. Автоматизация в проектировании / Пер. с англ. под ред. Д.Калахана, пред.М.А.Таврилова.- М.: Мир, 1972. - 162 с.

2. Материалы ХХУ1 съезда КПСС.- М.: Политиздат, 1981. 223 с.

3. Справочник конструктора РЭА: Общие принципы конструирования / Под ред. Р.Г.Варламова.- М.: Сов.радио,1980. 480 с.

4. Селютин В.А. Машинное конструирование электронных устройств.-М.: Сов. радио, 1977. 384 с.

5. Петренко А.И. Основы автоматизации проектирования. Киев: Техника, 1982. - 295 с.

6. Деньдобренко Б.Н.,Малика А.С. Автоматизация конструирования РЭА.- М.2 Высш.школа, 1980.- 384 с.

7. Петренко А.И.,Тетельбаум А.Я. Автоматизация проектирования электронной аппаратуры. Топологический подход.- Киев.: Вища школа, 1980.- 173 с.

8. Ахо А.,Хопкрофт Д.,Ульман Д. Построение и анализ вычислительных алгоритмов.- М.: Мир, 1979.- 536 с.

9. Карп P.M. Сводимость комбинаторных проблем.- Кибернетический сборник, 1975, вып. 12, с. 16-38.ю. Ухяу J/.L, Кик (I. fl.

10. X Рчл^чМА/ on, Contftuiw, (ZppficaJUotL in CowpwUt CLpp^-taiiotU/ Lit Сотри, t^vtof-. iW WJCC, №6p p.p. Ms*.

11. Петренко А.И.,Тетельбаум А.Я. Формальное конструирование ЭВА.- М.: Сов. радио, 1979.- 256 с.

12. Абрайтис Л.Б.,Шейнаускас Р.И.,Жилевичус В.А. Автоматизация проектирования ЭВМ.- М.: Сов. радио, 1978.- 272 с.

13. Базилевич Р.П. Декомпозиционные и топологические методы автоматизированного конструирования электронных устройств.

14. Львов: Вища школа. Изд-.во при Ль во в. ун-те, 1981.- 168 с.

15. Мелихов А.Н.,Бернштейн Л.С.,Курейчик В.М. Применение графов для проектирования дискретных устройств,- М.: Наука, 1974.303 с.

16. Петренко А.И.,Саватьев В.А. Автоматизированное проектирование больших интегральных схем,- Киев: Знания, 1979,- 27 с.

17. Рубцов В.П.,Хахаров В.П.,Жижко В.А. Автоматизация проектирования больших интегральных схем.- Киев: Техника, 1980,- 231 с.

18. Штейн М.Е.,Штейн Б.Е. Методы машинного проектирования цифровой аппаратуры.- М.: Сов. радио, 1973.- 294 с.

19. Бершадский A.M. Автоматизация конструкторского проектирования электронно-вычислительной и радиоэлектронной аппаратуры.-Пенза, 1977,- 81 с.

20. Брейер М. Последние достижения в области автоматизации проектирования и анализа цифровых систем.- В кн.: Автоматизацияв проектировании.- М.: Мир, 1972, с. 19-48.

21. Теория и методы автоматизации проектирования вычислительных систем / Под ред. М.Брейера.- М.: Мир, 1977.- 282 с.

22. Автоматизация проектирования цифровых устройств / Баранов С.И. Майоров С.А.,Сахаров Ю.П.,Селютин В.А.- Л.: Судостроение, 1979.- 261 с.

23. Норенков И.П.,Маничев В.Б. Системы автоматизированного цро-ектирования электронной и вычислительной аппаратуры.

24. М.: Высш.школа, 1983. 272 с.

25. Деньдобренко Б.Н.,Селютин В.А. Опыт использования ЭВМ при конструировании радиоэлектронной аппаратуры.- Л.: Судостроение , 1977.- 32 с.

26. Автоматизация конструирования больших интегральных микросхем / Петренко А.И. ,Сыпчук П.П. ,Тетельбаум А.Я.,Иваненков А.,1

27. Саватьев В.А,- Киев: Вища школа, 1983,- 312 с.

28. Ландау И.Я. Применение ЦВМ для проектирования ЦВМ,- М.: Энергия, 1974.- 152 с.

29. Применение вычислительных машин для проектирования цифровых устройств / Под ред. Н.Я.Матюхина.- М.: Сов.радио, 1968.256 с.

30. Петренко А.И.,Курейчик В.Й.,Тетельбаум А.Я. и др. Автоматизация проектирования больших и сверхбольших интегральных схем.- Зарубежная радиоэлектроника, 1981, № 6, с. 47-66.

31. Герасименко Е.П.,Кот В.И.,Ландау И.Я.,Сомкин В.М. Автоматизация проектирования печатных блоков с мо,дулями произвольной формы.- М.: Машиностроение, 1979.- 168 с.

32. Чуев Ю.В.,Спехова Г.П. Технические задачи исследования one-раций.- М.: Наука, 1971.- 256 с.

33. Варламов Р.Г. Компоновка радиоэлектронной аппаратуры.- 2-е изд.,перераб. и доп.- М.: Сов. радио, 1975.- 351 с.

34. Анисимов Б.В.,Савельев А.Я. Основы конструирования и производства ЭВМ.- М.: Высшая школа, 1972.- 278 с.

35. Базовый принцип конструирования РЭА/ Е.М. Парфенов, В.Ф. Ананасенко, В.И.Владимиров, Е.В.Саушкин; Под ред. Е.М.Парфенов а. -М. : Радио и связь, 1981.- 120с.

36. Базилевич Р.П. Основные принципы и обобщения алгоритмических методов гибкой трассировки межсоединений.- Управляющие системы и машины, 1977, № 6, с. 99-112.

37. UcwnjMui X, ^dtofa 771.OLuutovtodcc расшля ojf rrurUcbtuxiitQ tiiuuU,„ CU^utci^tu£ (HvolllU (Pazlia^Ltt^vAlnymtiw" МбЯ^.Я, Я/?

38. Крыжановский Ю.М. Компоновка конструкторских элементов цифровых устройств,- В кн.: Применение вычислительных машин дляпроектирования цифровых устройств. Под ред. Н.Я.Матюхина.-М.: Сов. радио, 1968.- 256 с.

39. Абрайтис Л.Б.,Шимайтис А.П. Алгоритмы компоновки узлов и исследование их эффективности.- В кн.: Вычислительная техника, т. II, Каунас, политехн. ин-т, 1971, с. 66-76.37. 74<*лрЛ С. %. Ш ахМпш^и, Pacha^if

40. Сот-риЛы Cuutuli^, (9GSf J6££ dnhbkatioria^ Coruy.^flec.? V. (Part 3; p.p.

41. Мелихов A.H.,Бернштейн JI.С.,Селянкин В.В.,Хиль М.И. Применение гиперграфов длякомпоновки схем в ячейках.- Изв. АН СССР. Техническая кибернетика, 1974, № 3, с. 202-207.

42. Методы разбиения схем РЭА на конструктивно законченные части / К.К.Морозов, А.Н.Мелихов,Л.С.Бернштейн и др.: Под ред. К.К.Морозова.- М.: Сов. радио, 1978.- 134 с.

43. Морозов К.К.,0диноков В.Г. Использование ЭЦВМ при конструировании некоторых узлов РЭА.- М.: Сов. радио, 1972.- 104 с.

44. Стоян Ю.Г. Размещение геометрических объектов.- Киев: Наук, думка, 1975.- 239 с.

45. Стоян Ю.Г.,Гиль Н.И. Методы и алгоритмы размещения плоских геометрических объектов.- Киев: Наук, думка, 1976.- 247 с.

46. Стоян Ю.Г.,Соколовский В.З. Решение некоторых многоэкстремалЬ' ных задач методом сужающихся окрестностей.- Киев: Наук, думка, 1980.- 205 с.

47. Медведев А.С.,Ревенко В.Н.,Штейн М.Е. О решении задач оптимизации, предшествующих трассировке печатных соединений.

48. В кн.: Вычислительная техника, Каунас, 1976, т.8, с.91-94.

49. Юеим Г.В.,Таганов А.И.,Пимахин В.М. Реализация совместного решения задач, предшествующих трассировки.- В кн.: Вычислительная техника, Вильнюс, 1979, т.10, с. 93-95.

50. УоЖиу L У., Сттм Um ej Uw ^rit-шЛц fwfcdnt Aurdt Owi&id job ^uiQriacj Ни (ZbhimA fa (Pxinham&itorii Am",4, V. 31, № p. {15- i49. § . ± л /

51. Z^bi a A. d J^dmv p*- му^ ouX ишиЬВиbLUtiJ <г Лиь^е Xo^ei of йп^&ммгсЬшгй,. buff. СотриЛ. did. /№2. ^otu/oz, p. гг-зо.

52. Тетельбаум А.Я.,Шрамченко Б.JI. Методы машинного проектирования электронных устройств,- Зарубежная радиоэлектроника, 1977, № 2, с. 24-50.

53. OljfcMtl. t PurdzjJ- idibt&f боаги/-Xou/mt 4ц Ccrn-puitt. „ &tlttwrut&, ouid Pou-et." Oct. ml, u. /?, p. Ъ19.50. tkaMrdkutL /? а ГША cfp-toac/t -Lo nun-cut pta&mad.

54. Jhbl*on culJ TehMnbuurbucaiLorUu. (S/tg. ttgl, V. Zf, HH, p.p. 5ZG-532.

55. Гермейер Ю.Б. Введение в теорию исследования операций.-М.: Наука, 1971.- 384 с.

56. Батищев Д.И. Задачи и методы векторной оптимизации.- Горький: изд-во Горьк. ун-та, 1979.- 92 с.

57. Батищев Д.И. Поисковые методы оптимального проектирования.-М.: Сов. радио, 1975.- 216 с.

58. Вермишев Ю.Х. Методы автоматического- поиска решений при проектировании сложных технических систем.- М.: Радиои связь, 1984.- 152с.

59. Брахман Т.Р. Многокритериальность и выбор альтернативы в технике. М.: Радио и связь, 1984,288с.

60. Моисеев Н.Н. Неформальные процедуры и автоматизация проектирования.- М.: Знание, 1979.- 64 с.

61. Карлин С. Математические методы в теории игр, программировании и экономике.- М.: Мир, 1964,- 838 с.

62. Эйрес Р. Научно-техническое прогнозирование и долгосрочное планирование.- М.: Мир, 1971.- 292 с.

63. Михалевич B.C.,Волкович В.Л. Вычислительные методы исследования и проектирования сложных систем.- М.: Наука, 1982.286 с.

64. Fya Б. Проблемы и методы применения решений в задачах с многими целевыми функциями. Вопросы анализа и процедуры принятия решений.- М.: Мир, 1976.- 273 с.

65. Михалевич B.C. Последовательные алгоритмы оптимизации и их применение.- Кибернетика, 1965, № I, с. 45-56.

66. Mo mo t^ /2.(5. ОиМщл ofy cut aJt^xiiknt fobftt to lintdt pvy6uM. OLmzi.fyioJJb. Aoc., /958, N5, p.ZM-Zl*.

67. Сергиенко И.В. 0 применении метода вектора спада для решения задач оптимизации комбинаторного типа.- Управляющие системы и машины, 1975, № 2, с. 86-94.

68. Стоян Ю.Г. Об одном способе поиска наилучшего решения для одного класса многоэкстремальных задач.- Управляющие системы, 1969, вып. 3, с. 81-88.

69. Стоян Ю.Г.,Соколовский В.З. Метод сужающихся окрестностей для минимизации функционалов, заданных на перекрестках.-Автоматика и вычисл. техника, 1979, № 3, с. 44-48.

70. Кухаренок М.А. Совместное решение задач размещения элементов и внешних контактных площадок при проектировании ЦВА.- в кн.:

71. Прикладные методы кибернетики.- Киев, 1984, с. 72-78.

72. Стоян Ю.Г., Кухаренок М.А. Обобщенный подход к задачам компоновки и размещения при проектировании РЭА.- В кн.: Вычислительная техника.- Каунас, 1982, с. 54-55.

73. Кухаренок М.А.,Соколовский В.З. 0 применение метода последовательно-одиночного размещения при решении задач квадратичного назначения.- Харьков, 1982.- 10 е.- Рукопись деп. в ВИНИТИ, № 4783-82 Деп.

74. Кухаренок М.А.,Соколовский В.З. Новая стратегия поиска по методу сужающихся окрестностей.- Харьков, 1982.- 9 е.- рукопись деп. в ВИНИТИ № 4784-82 Дер.

75. Кухаренок М.А. Об одном методе решения геометрических оптимизационных задач САПР.- Тез.науч.-техн. конференции"Проблемы автоматизации проектирования1.1- Свердловск, 1983, с. 41-42.

76. Стоян Ю.Г.,Кухаренок М.А. Один подход к решению задачи разрезания гиперграфа и его приложение.- Тез. докл. П Всесоюзного совещания "Методы и программы решения оптимизационных задач на графах и сетях".- Новосибирск, 1982, с. 142-143.

77. Стоян Ю.Г.,Кухаренок М.А. Комбинаторный подход к совместному решению задач покрытия и размещения.- Тез .докл. науч.-техн. конференции "Автоматизация конструкторского проектирования РЭА и ЭВА".- Пенза, 1983, с. 49-50.

78. Кухаренок М.А. Использование случайного поиска для разбиения гиперграфов.- Тез. докл. Всесоюзн. конференции "Случайныйпоиск в угольной промышленности",- Кемерово, 1984, с.42.44,

79. Стоян Ю.Г., Яковлев С.В., Кухаренок М.А, Дискретная оптимизация в задачах большой размерности.- Тез. докл. I Всесоюзн. симпозиума "Статистический анализ нечисловой информации, экспертные оценки и дискретная оптимизация".-М., 1981, с. 214-215.

80. Гель ПЛ., Иванов-Есипович Н.К. Конструирование радиоэлектронной аппаратуры.- Л,: Энергия, 1972,- 257с.

81. Парфенов Е.М,, Афанасенко В.®., Владимиров В,И,, Саушкин Е.В, Базовый принцип конструирования РЭА / Под ред.

82. Парфенова Е.М,- М,: Радио и связь, 1981,- 120с.

83. Пестряков В.Б. Конструирование радиоэлектронной аппаратуры,- М.: Сов. радио, IS69.- 208с.

84. Конструирование микроэлектронной аппаратуры / Под ред. Высоцкого Б.®. М.: Сов. радио, 1975,- 120с,

85. Основы проектирования микроэлектронной аппаратуры / Под ред. Высоцкого B.Q.- М.: Сов. радио, 1978.- 162с.

86. Фролов В.А. Механические воздействия и защита электронной аппаратуры.- Киев: Вища школа, 1979.- 128с.

87. Токарев М.Ф., Талицкий Е,Н., Фролов В.А. Механические воздействия и защита радиоэлектронной аппаратуры./ Под ред.

88. В.А.Фролова.- М.: Радио и связь, IS84.- 224с.

89. Дульнев Г.Н., Тарновский Н.Н. Тепловые режимыэлектронной аппаратуры.- М.: Энергия, 1971, 248с.

90. Ненашев А.П., Коледов Л.А. Основы конструирования микроэлектронной аппаратуры.- М.: Радио и связь, 1981.- 304с.

91. Конструирование и расчет больших гибридных интегральных схем, микросборок и аппаратуры на их основе. / Алексеев Г.В., .Борисов, Воробьева Т.Л. и др.: Под ред. Б.&. Высоцкого.- М.: Радио и связь, 1981.- 216с.

92. Мелихов А.Н., Берштейк JT.C. Гиперграфы в автоматизации проектирования дискретных устройств.- Изд-во Ростовского университета, 198I.- IKс.

93. Петренко А.Й., Твтельбаум А.Я. Модели электронных уст. ройств при решении конструкторских задач.- Кибернетика,1978, №2, с.47-54.

94. Зыков А.А. Гиперграфы.- В кн.: Успехи математических наук. Ы.: 19 74, т. 19, вып. 6, с. 89-154.

95. Мелихов А.Н., Берштейн Л.С. Операции над гиперграфами и их свойства.- Изв. АН СССР. Техническая кибернетика, 1977, 114, с.43-48.

96. Стоян Ю.Г. Основная задача геометрического проектирования, Харьков, 1983.- 36с.- (Препринт /Ж УССР. Ин-т пробл. машиностроения; №181).

97. Александров П.С. Введение в теорию множеств и общую топологию.- М.: Наука, 1977,- 367с.

98. Стоян Ю.Г. Об одном обобщении функции плотного размещения. Докл. АН УССР. Сер. А, 1980, № 8, с. 70-74.

99. Стоян Ю.Г.,Винарский В.Я. Алгебро-топологические свойства объектов.- Харьков, 1981.- 34 с. (Препринт АН УССР, йн-т п пробл. машиностроения; № 166).

100. Рвачев В.Л. Геометрические приложения алгебры логики.-Киев: Техника, 1967.- 210 с.

101. Стоян Ю.Г.,Панасенко А.А. Периодическое размещение геометрических объектов.- Киев: Наук, думка, 1978.- 176 с.

102. Форд А.,Фалкерсон Д. Потоки в сетях.- М.: Мир, 1966.- 276 с

103. Стоян Ю.Г.,Пономаренко Л.Д.,Литвинов В.Н. Размещение телв техмерном пространстве.- Харьков, 1976.- 73 с. (Препринт АН УССР. Ин-т пробл. машиностроения; № 19).

104. Бусленко Н.П.,Калашников В.В.,Коваленко И.Н. Лекции по теории сложных систем.- М.: Сов. радио, 1973.- 439 с.

105. Акоф Р.,Сасиеени М. Основы исследования операций.- М.: Мир, 1971.- 584 с.

106. Блауберг И.В.,Юдин Э.Г. Становление и сущность системного подхода.- М.: Наука, 1973.- 270 с.

107. Блауберг И.В., Садовский В.Н. Системные исследованияи общая теория систем.- В кн.: Системные исследования.

108. М.- Наука, 1969, с. 123-167.

109. Бахтин Б.И. Автоматизация в проектировании и производстве печатных плат радиоэлектронной аппаратуры.- Л.: Энергия, 1979.- 120 с.

110. Холл М. Комбинаторика.- М.: Мир, 1970.- 424 с.

111. Сергиенко й.В.,Лебедева Т.Т.,Рощин В.А. Приближенные методы решения дискретных задач оптимизации.- Киев: Наук.думка, 1980.- 276 с.

112. Михалевич В.С.,Шор Н.Э. Численные решения многовариантных задач по методу последовательного анализа вариантов,- Научно-методические материалы экономико-математического семинара.- М.: ЛЭММ АН СССР, 1962, вып. I, с.

113. Голыптейн Е.Г.,Юдин Д.Б. Новые направления в линейном программировании.- М.: Сов. радио, 1966.- 524 с.

114. НО. Вильяме И.Н. Параметрическое программирование в экономике.-М.: Статистика, 1976.- 96 с.

115. Моцкус И.Б. Многоэкстремальные задачи в проектировании. Статистические решения. Усиление локальных методов. Эвристические способности человека).- М.: Наука, 1967.- 215 с.

116. Растригин Л.А. Системы экстремального управления.- М.: Наука, 1974.- 630 с.

117. Ермаков С.М. Метод Монте-Карло и смежные вопросы.- Изд. 2-е,

118. Доп.- М.: Наука, 1975.- 471 с.

119. ЛЫбхХ Ь. О. a ^иЫМ, mjJllwd jMntf thzфоМ тлхишьт, a, fdwiion,. dfK1. J>ht . mt, 9, />. W-ш.

120. Юдин Д.Б. Решающие правила в экстремальных задачах.- Изв.вузов. Сер. Радиофизика, 1972, т. 15, № 7, с. 957-966.

121. Юл^-ь d. AjUfiUtn-UobZ rtdlbLMAJZL AbCLUdba, m&occmunt. (Pua. ССтгь. /ТУ1ос1к. Jwc.;if, /V3, p. бог-50&.

122. Стронгин Р.Г. Минимизация многоэкстремальных функций нескольких переменных.- Изв. АН СССР. Техн.кибернетика, 1971, № 6, с. 39-46.не. Циикм-ъ & пШг ryudkod о^ ^осд^Соп-maX'ityuuK' point ofc от axJiitOL^ ти£1ьреал. cwtuc in tiu. рчжь&гпля гшл&. Тъоииь.

123. Sc. В&лйс. 1961 м, АЧ, р. М-{06.

124. Растригин Л.А.,Рипа К.К.,Тарасенко Г.С. Адаптация случайного поиска.- Рига: Зинатне, 1978.- 243 с.

125. Невельсон М.Б. Дасьминский Р.З. Стохастическая аппроксимация и рекуррентное оценивание.- М.: Наука, 1972.- 304 с.

126. Колмогоров А.Н. Основные понятия теории вероятностей.- М.: Наука, 1974.- 119 с.

127. Гнеденко Б.В. Курс теории вероятностей.- М.: Наука, 1969.400 с.

128. Крамер Г. Математические методы статистики.- М.: Мир, 1975.648с.

129. Феллер В. Введение в теорию вероятностей и ее приложения.-М.: Мир, т.1, 1964; т. 2, 1967.- 498 с.

130. HoSwU, 1С. ^С. Gc A&axcfi rnooLe£ <Ци)пг wjl-j(yLLCl£ut£ сопъбUbOLto vt LoMt£ tTp<(j04Uv& pwiitrvU,.- Opib. 4Щ 19, e, p. 390-jot.126. Pdiuat it.? UfeJet 1С. %

131. MaptoilbOnjUri Abodjtcuii^che^ AuchvetftaJiu/i fob duJw-ie, QpiMmuwMMwS&rrit. fYlaik., Opttoubioru, Jfobik, 11. AiaAtit. 4Щ, 5, N*> p. 551 -511.

132. Рунион P. Справочник по непораметрической статистике.- M.: Финансы и статистика, 1982.- 199 с.

133. Яковлев С.В. Стохастический алгоритм оптимизации для решения одного класса многоэкстремальных задач.- В сб.: Теория оптимальных решений,- Вильнюс, 1981, вып. 7, с. 49-58,

134. Стоян Ю.Г.,Яковлев С.В. Исследование сходимости и эффективности метода сужающихся окрестностей,- Харьков, 1981.43 с. (Препринт АН УССР. Ин-т пробл. машиностроения; № 168).

135. Пытьев Ю.П.,Шишмарев И.А. Курс теории вероятностей и математической статистики для физиков.- М.: Изд-во М.ун-та, 1983.- 256 с.

136. Моисеев Н.Н.,Иванилов Ю.П.,Столярова Е.М. Методы оптимизации.- М.: Наука, 1978.- 352 с.

137. Козерацкая Л.Н.,Лебедева Т.Т.,Сергиенко И.В. Вопросы устойчивости, параметрический и постоптимальный анализ задач дискретной оптимизации.- Кибернетика, 1983, № 4, с. 71-80.

138. Леоньтьев В.К. Устойчивость в комбинаторных задачах выбора.-Докл. АН СССР, 1976, 228, № I, с. 23-25.

139. Прикладная статистика: Основы моделирования и первичная обработка данных. Справочное пособие./ С.А.Айвазян, И.П.Еников, Л.Д.Мешалкин.- М.: Финансы и статистика, 1983.- 471с.

140. Каспшицкая М.Ф.,Сергиенко И.В. К вопросу о построении эффективных методов решения некоторых задач организации вычислительного процесса на ЭВМ.- Кибернетика, 1969, № 4, с. 67-74.

141. Голенко Д.И.Дарнопольский Ю.Я. Оптимизация календарных планов методами направленного поиска.- Киев, Кибернетика, 1970, № б, с. 139-144.

142. Сергиенко И.В.,Каспшицкая М.Ф. Модели и методы решения на ЭВМ комбинаторных задач оптимизации.- Киев, Наук, думка, 1981.- 288 с.

143. Ш.7У1. Modh^todital тосСг&ьfit ike cUcuLti fa^otjut pw^tinc. J? £ £ £

144. Jy. W.y VlfkuiUo/L d, 6. drL (dfoic. (MAi^n/nwdt ръоЕ-Олт. ~ IYLCL -пл^тлЬ 4tiert,ci7 я Mo. p. H53-W.

145. У Мм- X. A. Qtcoudative tooll jo>c pCasit layout алаЛи^. Xhz fyoutal 0jtU)LMJi>UrUf} 1<?6Ъу у. tJo, 1, p. ЪЪ-JfO.147# Uilwuz (pt с. OpicmaZ алс! Auiopiimaipt iU fyuadzcdcc ouLU^nmtttt ръоб&лг. a AMm, mi, D.w, hio.z?p.зог-зп.