Оптимизация структуры объектов проектирования на основе эквивалентных преобразований задачи о минимальном покрытии тема диссертации и автореферата по ВАК РФ 05.13.12, кандидат технических наук Каширина, Ирина Леонидовна

• Каширина, Ирина Леонидовна
• кандидат технических наук
• 1999

Оглавление диссертации кандидат технических наук Каширина, Ирина Леонидовна

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

ГЛАВА 1. ПУТИ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ ПРО- 9 ЦЕДУР ПРИНЯТИЯ РЕШЕНИЙ НА ЭТАПЕ СТРУКТУРНОГО СИНТЕЗА ОБЪЕКТОВ ПРОЕКТИРОВАНИЯ

1.1. Анализ оптимизационных моделей этапа структурного син- 9 теза объектов проектирования

1.2. Требования к эффективности алгоритмических процедур

1.3. Цель и задачи исследования 44 ГЛАВА 2. ФОРМИРОВАНИЕ ЭКВИВАЛЕНТНЫХ ПОСТАНО- 48 ВОК ЗАДАЧИ О МИНИМАЛЬНОМ ПОКРЫТИИ ПРИ ОПТИМИЗАЦИИ СТРУКТУРЫ ОБЪЕКТОВ ПРОЕКТИРОВАНИЯ

2.1. Принципы формирования эквивалентных постановок

2.2. Детерминированные постановки

2.3. Вероятностные постановки, использующие рандомизацию 57 переменных

Выводы 2-й главы

ГЛАВА 3. РАЗРАБОТКА ВЕРОЯТНОСТНЫХ АЛГОРИТ- 64 МИЧЕСКИХ СХЕМ РЕШЕНИЯ ЗАДАЧИ О МИНИМАЛЬНОМ ПОКРЫТИИ

3.1. Методы конструирования точных и приближенных адаптив- 64 ных алгоритмов решения задачи о покрытии

3.2. Модификация "жадных" эвристических алгоритмов за счет 69 перехода к вероятностной постановке задачи

3.3. Вероятностная модификация двойственных субградиентных 89 алгоритмов

3.4. Алгоритм решения задачи о покрытии с дополнительными 101 ограничениями

3.5. Тестирование разработанных алгоритмов Выводы 3-й главы

116

ГЛАВА 4. ВНЕДРЕНИЕ АЛГОРИТМОВ И ПРОГРАММНЫХ 118 СРЕДСТВ В ЗАДАЧАХ ОПТИМАЛЬНОГО ПРОЕКТИРОВАНИЯ

4.1. Организация программного обеспечения для этапа структур- 118 ного синтеза объектов проектирования

4.2. Проектирование структуры производительной радиосети пе- 122 редачи информации

4.3. Структурная оптимизация базы знаний 125 Выводы 4-й главы

Введение диссертации (часть автореферата) на тему «Оптимизация структуры объектов проектирования на основе эквивалентных преобразований задачи о минимальном покрытии»

ВВЕДЕНИЕ

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

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

Из множества формализуемых задач структурного синтеза различ-

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

, Для ее решения разработано большое количество точных методов решения, которые, в частности, приведены в работах [2, 21, 51, 66, 78, 81]. Но все точные алгоритмы связаны с перебором на некотором конечном множестве, задаваемом исходными данными. По объему этого перебора как функции количества исходных данных существующие точные алгоритмы решения задачи о минимальном покрытии относятся к экспонециальным, что делает невозможным их использование для практических задач больших размерностей. Таким образом, возникает необходимость в разработке точных методов решения задачи о покрытии, отличающихся более высоким порогом применимости по сравнению с известными алгоритмами.

Основным недостатком существующих приближенных алгоритмов [11, 21, 49, 51, 62, 66, 81] является то, что основываясь на тех или иных разумных соображениях, они предлагаются , к сожалению, без надлежащего теоретического обоснования, поэтому в общем неизвестно, насколько далеко полученное решение от оптимального. Кроме того, для каждого из приближенных алгоритмов желательно знать специфические особенности задач, для которых его использование наиболее целесообразно. В связи с универсальным характером задачи о минимальном покрытии, есть смысл разрабатывать алгоритмы, не привязанные к конкретной предметной интерпретации. Тогда ведущее значение приобретает не смысловая трактовка, а характеристики набора исходных

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

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

Работа выполнена в соответствии с межвузовской комплексной научно- технической программой 12.11 "Перспективные информационные технологии в высшей школе" и в рамках одного из основных направлений Воронежского государственного технического университета "САПР и системы автоматизации производства"

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

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

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

• разработка точных и приближенных алгоритмов решения задачи о

покрытии, учитавающих специфические особенности задач, возникающих на этапе структурного синтеза объектов пректирования;

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

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

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

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

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

числом переменных и ограничений, наличие малосущественных огра-

ничений) с целью повышения точности получаемого результата.

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

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

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

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

в мелкосерийном машиностроительном производстве".

Результаты диссертационной работы используются в учебном процессе кафедры ММИО в Воронежском государственном университете для студентов специальности "Прикладная математика".

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

Апробация работы . Основные результаты работы докладывались и обсуждались: на семинарах в Воронежском государственном университете, Воронежском государственном техническом университете; на V Международной конференции женщин - математиков ( 1997 г.), III Международной конференции из серии "Нелинейный мир" (1997 г.), Всероссийском совещании - семинаре "Математическое обеспечение информационных технологий в технике, образовании и медицине" (1997 г.), 20-й Конференции молодых ученых (1998 г.), 20-й Международной научной школе-семинаре "Системное моделирование социально - экономических процессов" (1998 г.), конференции "Математическое моделирование систем" (1998 г.).

Публикации. По теме диссертационной работы опубликовано 12 печатных работ.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав и списка литературы и содержит без списка литературы 131 страницу печатного текста. Список цитируемой литературы включает 81 наименование. Диссертация включает в себя 14 рисунков и 3 таблицы.

Заключение диссертации по теме «Системы автоматизации проектирования (по отраслям)», Каширина, Ирина Леонидовна

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

2. Получены эквивалентные постановки задачи о минимальном покрытии. Показана связь между алгоритмом решения задачи и ее исходной постановкой.

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

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

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

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

7. Созданные программные средства нашли практическое применение в составе программного комплекса по организации сетей радиодоступа, разрабатываемом в ВНИИС, и в "Экспертной системе контроля качества инноваций в мелкосерийном машиностроительном производстве", разрабатываемой РАУ "Агентство информационных систем и технологий".

Теоретические и практические результаты работы используются в учебном процессе кафедры ММИО в Воронежском государственном университете для студентов специальности "Прикладная математика" в курсах "Адаптивные алгоритмы" и "Практическая реализация алгоритмов дискретной оптимизации".

Список литературы диссертационного исследования кандидат технических наук Каширина, Ирина Леонидовна, 1999 год

ЛИТЕРАТУРА

[1] Адельсон- Вельский Г. М., Кузнецов О П. Дискретная математика для инженеров.- М.: Энергия, 1980.- 344 с.

[2] Алексеев О.Г. Комплексное применение методов дискретной оптимизации. - М: Наука, 1987. -279 с.

[3] Антамошкин А.Н. Регулярная оптимизация псевдобулевых функций. - Красноярск: Изд-во Краснояр. ун-та, 1989.- 209 с.

[4] Аоки М. Введение в методы оптимизации: Пер. с англ.- М.: Мир, 1977,- 344 с.

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

[6] Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы.- М: Мир, 1982. -584 с.

[7] Батищев Д. И., Львович Я. Е., Фролов В. Н. Оптимизация в САПР.-Воронеж: Изд-во ВГУ, 1997.- 416 с.

[8] Батищев Д.И. Методы оптимального проектирования .- М.: Радио и связь, 1984.-247 с.

[9] Батищев Д. И., Старостин Н. В. Применение генетических алгоритмов к решению задачи дихотомического разбиения графа // Оптимизация и моделирование в автоматизированных системах: Межвуз. сб. науч. трудов.- Воронеж, 1998. - С. 4-11.

[10] Береснев В.Л. Алгоритм минимизации полиномов от булевых переменных// Проблемы кибернетики.- М.: Наука, 1979.- Вып. 36.-С. 225-246.

[11] Береснев B.JI., Гимади Э.Х., Дементьев В.Т. Экстремальные задачи стандартизации.- Новосибирск: Наука, 1978. - 335 с.

[12] Бибило П. Н. , Енин C.B. Синтез комбинационных схем методами функциональной декомпозиции.- Минск: Наука и техника, 1987. -189 с.

[13] Бертсекас Д. Условная оптимизация и методы множителей Лагранжа.- М: Радио и связь, 1987.- 400 с.

[14] Бибило П.Н. Использование заданных функций при синтезе схем в базисе программируемых логических интегральных схем // Автоматика и вычислительная техника. - 1998. - N 2. - С.58-96.

[15] Бутов A.A. Реализация систем не полностью определенных булевых функций в базисе схем малого и среднего уровней интеграции // УСИМ.- 1979.- N 6,- С. 97-104.

[16] Ворожеева C.B.,Черных О.И., Чернышова Г. Д. Построение вероятностных алгоритмов оптимизации с использованием модифицированной функции Лагранжа для задач САПР// Оптимизация и моделирование в автоматизированных системах: Межвуз. сб. науч. трудов.- Воронеж, 1988. - С. 87 - 91.

[17] Ворожеева C.B., Чернышова Г. Д. Вероятностные алгоритмы формирования поисковых функций при решении задач условной оптимизации/ / Алгоритмы моделирования оптимизации автоматизированных систем: Межвуз. сб. науч. трудов. - Воронеж, 1990.- С.115 -122.

[18] Вычислительные методы выбора оптимальных проектных решений/ B.C. Михалевич, Н.З. Шор, Л.А. Галустова и др.; Под ред. В. С.Михалевича.- Киев: Наукова Думка, 1977.- 178 с.

[19] Вязгин В.А., Федоров В.В. Математические методы автоматизированного проектирования.- М.: Наука, 1988.- С. 552.

[20] Герман О.В. Ефремов О.В. Принципы обучения экспертной системы/ / Автоматика и вычислительная техника.- 1997. - N б. -С. 10 - 19.

[21] Герман О.В. Разрешающий принцип для задачи о минимальном покрытии// Кибернетика и системный анализ. -1996. - N 1.- С. 135 -146.

[22] Гилл У., Мюррей А., Райт К. Практическая оптимизация: Пер. с англ.- М.: Мир, 1989. - 460 с.

[23] Дарахвелидзе П.Г., Марков Е.П. Delphi- среда визуального программирования.- СПб.: BHV- Санкт- Петербург, 1996.-352 с.

[24] Деннис Д., Шнабель Р. Численные методы безусловной оптимизации и решения нелинейных уравнений.- М.: Мир, 1988. - 440 с.

[25] Дискретная математика и математические вопросы кибернетики/ Под ред. С. В. Яблонского и О. Б. Ляпунова. Т.1.- М.: Наука, 1974.311 с.

[26] Долин Г. Системы автоматизированного проектирования радиоэлектронной аппаратуры// Компьютер пресс.- 1998.- N 7.- С. 286 -293.

[27] Закревский А. Д. Комбинаторика логического проектирования. // Автоматика и вычислительная техника.- 1990.- N 2.- С.68-79.

[28] Закревский А. Д. Логический синтез каскадных схем. - М.: Наука, 1981. - 416 с.

[29] Иоффе М.И. Диагностирование логических схем.- М.: Наука, 1989. - 241 с.

[30] Итоги науки и техники. Серия Радиотехника / Под ред. Э.М. Квертиркина,- М: ВИНИТИ, 1990,- Т.40. -108 с.

[31] Карп P.M. Сводимость комбинаторных проблем// Кибернетический сборник.-М., 1975. - Вып.12. - С.16-38.

[32] Каплинский А.И.,Лимарев А.Е.,Чернышова Г.Д. Построение рандомизированных алгоритмов оптимизации // Проблемы случайного поиска, 1980.- Вып.8.- С. 63-91.

[33] Каплинский А.И., Чернышова Г. Д., Хлявич O.A. Вероятностная алгоритмизация задач с булевыми переменными на основе адаптивного варианта метода ветвей и границ. - Воронеж, 1984. -59 с. -Деп. в ВИНИТИ 18.07.84. N 5164.

[34] Каплинский А.И., Чернышова Г. Д., Черных О.И. Адаптивный выбор ограничений при алгоритмизации булевой задачи математического программирования на основе вероятностного варианта метода ветвей и границ // Моделирование и оптимизация слож- ных систем: Межвуз. сб. науч. трудов.- Воронеж, 1986.- С.16-22.

[35] Каширина И.Л. Об одном алгоритме приближенного решения задачи коммивояжера // Сборник работ студентов и аспирантов. -Воронеж, 1997.- Вып. 1. - С. 30-34.

[36] Каширина И.Л., Чернышова Г.Д. Алгоритмы решения задачи о покрытии, использующие переход к вероятностной постановке задачи // Известия РАЕН, серия МММИУ.- 1997.- N 1.- С. 119-127.

[37] Каширина И.Л., Чернышова Г.Д. Использование Лагранжиана в приближенной алгоритмизации задачи о минимальном покрытии // Оптимизация и моделирование в автоматизированных системах: Межвуз. сб. науч. трудов.- Воронеж, 1997. - С. 129-135.

[38] Каширина И.Л., Чернышова Г.Д. Об одном подходе к построению приближенных алгоритмов решения задачи о минимальном покрытии // Известия Вузов. Радиофизика.- 1998.- Т 5.- Вып 1. - С. 119 -126.

[39] Каширина И.Л., Чернышова Г.Д. О вероятностной модификации одного "жадного" алгоритма решения задачи коммивояжера // Оптимизация и моделирование в автоматизированных системах: Межвуз. сб. науч. трудов.- Воронеж, 1996. - С. 37-45.

[40] Каширина И.Л., Чернышова Г.Д. О выборе алгоритмических схем решения задачи о минимальном покрытии // Оптимизация и моделирование в автоматизированных системах: Межвуз. сб. науч. трудов.- Воронеж, 1998. - С. 83-88.

[41] Каширина И.Л. Об одном алгоритме нахождения минимальной ДНФ комбинационной функции // Математическое моделирование систем: Тез. докл. науч. конф., 12-16 октября 1998 г. - Воронеж, 1998. - С. 20-21.

[42] Каширина И.Л., Чернышова Г.Д. Алгоритмизация задачи о минимальном покрытии // Тезисы научных докладов 20-й междунар. конференции "Системное моделирование социально-экономических процессов" , Воронеж, 11-14 мая 1998 г. - Воронеж, 1998. - Ч. 2 - С. 205-207.

[44] Каширина И.Л. Конструирование алгоритмов решения задачи о минимальном покрытии на основе ее эквивалентной перезаписи// Труды 20 Конф. молодых ученых мех.-мат. ф-та МГУ (12-16 мая 1998 г.).- Москва, 1998.- С. 25-29.

[45] Каширина И.Л., Чернышова Г.Д. Об одном подходе к построению алгоритмов решения задачи о минимальном покрытии // Математика. Экономика: Тез. докл. V Междунар. науч. конф. женщин -математиков, 26 мая - 1 июня 1997 г. - Ростов - на - Дону, 1997. -С.121.

[46] Каширина И.Л., Чернышова Г.Д. Применение в САПР алгоритмов решения задачи о покрытии // Тезисы Всероссийского совещания -семинара "Математическое обеспечение информационных технологий в технике, образовании и медицине" Воронеж, 28-31 мая 1997 г. - С. 48- 51.

[47] Квайн У. Упрощение функций истинности// Вопросы теории математических машин.- М.: Машиностроение,1964.

[48] Ковалев М.М. Дискретная оптимизация.- Минск: Изд-во БГУ, 1977.- 192 с.

[49] Корбут A.A., Финкелынтейн Ю. Ю. Дискретное программирование : Пер. с англ.- М.: Наука, 1969. - 368 с.

[50] Корячко В.П., Курейчик В.М., Норенков И.П. Теоритические основы САПР. -М: Энергоатомиздат, 1987.- 400 с.

[51] Кузюрин H.H. Задача линейного булева программирования и некоторые комбинаторные проблемы //Компьютер и задачи выбора.-М.: Наука, 1989.- С. 44-60.

[52] Левин Г.М. , Танаев B.C. Декомпозиционные методы оптимизации проектных решений.- Минск: Наука и техника, 1978.- 240 с.

[53] Логическое проектирование СБИС / Под ред. Мищенко В.А.- М.: Радио и связь, 1984.- 312 с.

[54] Львович Я.Е., Каплинский А.И., Чернышова Г.Д. Черных О.И. Конструирование адаптивных схем перебора для решения дискретных задач оптимизации// Актуальные проблемы фундаментальных наук.- М.: Изд-во МГТУ, 1991,- С.44 - 46.

[55] Львович Я.Е., Каширина И.Л., Чернышова Г.Д., Головнев A.M. Об одном алгоритме построения производительной радиосети передачи информации// Высокие технологии в технике и медицине: Межвуз. сб. науч. трудов.- Воронеж, 1998. - С. 51-56.

[56] Львович Я.Е. Комбинаторный выбор на основе вариационного моделирования. // Оптимизация и моделирование в автоматизированных системах: Межвуз. сб. науч. трудов. - Воронеж, 1996. - С. 175181.

[57] Львович Я.Е., Фролов В.Н. Теоритические основы конструирования, технологии и надежности PEA.- М.: Радио и связь, 1986.- 192 с.

[58] Мину М. Математическое программирование. - М.: Мир, 1987. -426 с.

[59] МурогаС. Системное проектирование сверхбольших интегральных схем: Пер. с англ.- М.: Мир, 1985.- Т.2. - 291 с.

[60] Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность: Пер. с англ.- М.: Мир, 1985. - 510 с.

[61] Поляк Б.Т. Введение в оптимизацию. -М.: Наука, 1983.- 258 с.

[62] Рейнгольд Э., Ю. Нивергельт, Н. Део. Комбинаторные алгоритмы. Теория и практика: Пер. с англ.- М.: Мир, 1980. - 162 с.

[63] Реклейтис Г., Рейвиндран А., Регедел К. Оптимизация в технике: В 2 т./ Пер. с англ.- М.: Мир, 1986. - 2 т.

[64] Рот Д. Алгебро-топологические методы синтеза переключательных схем. - В кн.¡Вопросы теории математических машин.- М.: Машиностроение,1964.

[65] Саати Т. Целочисленные методы оптимизации и связанные с ними экстремальные проблемы: Пер. с англ.- М.: Мир, 1973. - 300 с.

[66] Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации.- Киев: Наукова думка, 1988.- 320 с.

[67] Системы автоматизированного проектирования: В 9 кн. Кн. 1. Но-ренков И. П. Принципы построения и структура.- М.: Высш. шк., 1986.- 127 с.

[68] Современное состояние теории исследования операций / Под ред. Н. Н. Моисеева.- М.: Наука, 1979.- 464 с.

[69] Сысоев В.В. Структурные и алгоритмические модели автоматизированного проектирования производства изделий электронной техники.- Воронеж: Изд-во Воронеж, технол. ин-та, 1993.- 208 с.

[70] Фаронов В.В. Delphi 3. Учебный курс.- М.: "Нолидж", 1998.- 400 с.

[71] Феллер В. Введение в теорию вероятностей и ее приложения: В 2-х т. - М.: Мир, 1984. - Т. 1. - 527 с.

[72] Фихтенгольц Г. М. Основы математического анализа: В 2-х т. -М.: Наука, 1968. - Т. 1. - 440 с.

[73] Фридман Ф., Менон П. Теория и проектирование переключательных схем : Пер. с англ.- М.: Мир, 1978. - 580 с.

[74] Фролов А.Б. Модели и методы технической диагностики.- М: Знание, 1990.- 48 с.

[75] Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем. - М.: Мир, 1983. - 310 с.

[76] Чернышова Г.Д. Вероятностная модификация "жадных" алгоритмов комбинаторной оптимизации// Высокие технологии в технике и медицине: Межвуз. сб. науч. трудов.- Воронеж, 1994. - С. 51-56.

[77] Хант Э. Искусственный интеллект.- М.: Мир, 1978.- 420 с.

[78] Brayton R.K., Hachtel G.D., McMullen С.Т. Logic minimization algorithm for VLSI synthesis - Boston: Kluwer Academic Publishers, 1984. - 231 p.

[79] Krarup J., Pruzan P.M. The simple plant location problem: syrvey and synthesis// European J. Oper. Res. - 1983.- V. 12, N 2.- P. 233-261.

[80] McCluskey E. J. Minimization of Boolean function// Bell System Techn., 1956, v. 35.

[81] Young M. H. The minimal covering problem and automated design of two-level AND/OR optimal networks, Ph. S. dissertation, Dept. of Computer Science, University of Illinois, 1978.-186 p.

ЖуУ, УТВЕРЖДАЮ

щр''; ? директора ВНИИС по научной работе " кандидат технических наук

и . < ' 1-Г 1 ___ ^ / / /I

Николаев В.И.

Щп ноября 1998 г.

АКТ

о внедрении пакета прикладных программ "Минимальное покрытие"

Настоящий акт составлен в том, что в результате внедрения пакета прикладных программ " Минимальное покрытие" в состав специального программного обеспечения "Автоматизированной навигационной системы определения местоположения объектов и обмена данными между ними", разрабатываемого в рамках НИОКР ВНИИС, получены следующие результаты:

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

2. Использование пакета "Минимальное покрытие" в программном комплексе по организации сетей радиодоступа позволило за счет выбора оптимальной структуры сети обмена данными увеличить производительность сетей и сократить среднее время транспортировки информации между абонентами сети.

Начальник отдела

Начальник сектора

Разработчик

Клоков Ю. М.

Головнёв А. М.

Каширина И. Л.

& 4 JU ^ «к X Л J ' » ~ ✓ >«. - V X t _ ,

Агентство информационных систем и технологий

394000, г.Воронеж, Главпочтамт, а/я 518, тел./fax [phone], e-mail: [e-mail] ИНН 3666073198 р/с 40703810508000000015 в Воронежском ф-ле КБ «Эталонбанк» к/с 30101810900000000815 БИК 042007815

№_

«_» 199_г

АКТ

О внедрении пакета прикладных программ "Минимальное покрытие"

Воронеж «01» октября 1998 г.

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

1. Решена проблема реализации модуля обратной связи в разрабатываемой "Экспертной системе контроля качества инноваций в мелкосерийном машиностроительном производстве" ;

2. Разработанный с использованием пакета "Минимальное покрытие" программный комплекс успешно используется РАУ "Агентство информационных систем и технологий" при построении систем автоматизации управления и поддержки принятия решений своих заказчиков.

Исполнитель

Директор РАУ «Агентство информационных систем и технологий»

И.Л.Каширина

^ У/^ "" и А.И.Пастухов