автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.12, диссертация на тему:Разработка среды непрерывно-дискретной оптимизации для конструирования специального алгоритмического обеспечения САПР

< од

' 2 ДЕК

На правах рукописи

ПИТО ЛИП Михаил Владимирович

РАЗРАБОТКА СРЕДЫ НЕПРЕРЬШНО-ДИСКРЕШОЙ ОПТИМИЗАЦИИ ДЛЯ КОНСТРУИРОВАНИЯ СПЕЦИАЛЬНОГО АЛГОРИТМИЧЕСКОГО ОБЕСПЕЧЕНИЯ САПР

Специальность 05.13.12 - Системы автоматизации проектирования

/ АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Воронеж - 1997

у Работа выполнена в Воронежском государственном техническом 7 университете

Научный руководитель - канд. техн. наук,

профессор Кашшнский А.И.

Официальные оппоненты: д-р техн. наук.,

профессор Шишкин В.М. канд. техн. наук, доцент Каляпина О.И.

Ведущая организация - Научно-исследовательский центр

электронно-вычислительной техники (г. Москва)

Защита диссертации состоится

ч декабря 1997г. в часов п конференц-зале на заседании диссертационного совета Д 063.81.02 при Воронежском государственном техническом университете по адресу: 394026, г. Воронеж, Московский пр., ¡4.

С диссертацией можно ознакомиться в библиотеке Воронежского государственного технического университета.

¡/Тг

Автореферат разослан •* г' ноября 1997 г.

Ученый секретарь диссертационного совета

Львович Я.Е,

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

1) неадаптивность к различным классам объектов проектирования; ■2) отсутствие обучающих элементов, которые позволили бы проектировщику использовать эти средства для решения прикладных задач.

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

Диссертационная работа выполнена в соответствии с межвузовской научно-технической программой 12.11 "Перспективные информационные технологии в образовании", г/б НИР 5/97 "Разработка среды поисковой и непрерывно-дискретной оптимизации для создания специализированного алгоритмического обеспечения в САПР" в рамках одного из основных направлений Воронежского государственного технического университета "Разработка САПР, роботов и ГЛП".

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

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

формирование библиотеки базовых и проблемно-ориентированных модулей непрерывно-дискретной оптимизации;

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

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

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

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

Научим новизна. Основные результаты диссертации, выносимые на защиту и имеющие научную новизну:

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

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

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

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

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

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

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

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

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

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

Апробация рг.боты. Основные положения диссертации докладывались и обсуждались на следующих конференциях, семинарах и совещаниях: Всероссийском совещании-семинаре "Математическое обеспечение высоких технологий в технике, образовании и медицине" (Воронеж, 1994 1995.); Всероссийском совещании-семинаре "Математическое обеспечение информационных технологий в технике, образовании и медицине" (Воронеж, 1996-1997); Международной научно-технической конференции "Методы и средства оценки и повышения приборов, уст-

ройсгв и систсм'Ч Пенза, 1995); Международной научно-техническом конференции "Актуальные проблемы анализа и обеспечения надежности и качества прибором, устройств и систем'ЧПенза, 1996-1997); ежегодных научных конференциях профессорско-преподавательского состава Воронежского государстпенпого технического униисрситста.

Публикации._Основные результаты работы опубликованы в 12

печатных работах, перечень которых приведен в конце автореферата.

Структура и объем работы. Диссертация состоит из введения, четырех глав с выводами и заключения иа 146 е., списка литературы (85 наименований) на 8 е., трех приложений на 25 е., содержит 16 рисунков, 4 таблицы.

СОДЕРЖАНИЕ РАБОТЫ

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

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

Отмечено, что многообразие экстремальных задач и методов их решения вызывает потребность в развитых программных средствах (ПС) оптимизации.

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

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

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

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

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

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

Во многих задачах структурного синтеза в САПР к координатам вектора X предъявляется требование булевости, т.е.

Построение процедур поиска оптимальных вариантов во множестве булевых случайных величин осуществляется по следующей схеме:

1. Переход к рандомизированной эквивалентной переформулировке А/[/(,Г)]-> тт.

2.Формирование процедур поиска оптимальных вариантов во множестве случайных булевых величин;

Х,ып 12,.,«,

I)" - булева случайная величина,

м\и1 ] = г(и? 1) = р^, V, = 1 - у;, ¡'¡и", = |) = 1 - = ^ .

3.Выбор случайных величин X ри, ~ условие локального улучшения (УЛУ) вариационного типа:

4.Выделение отдельной координаты при выполнении УЛУ - раз- 7 биение допустимого множества на два подмножества:

= г^'гг^*,,....*, .....л-;)-*

....JT^) t „r„",l)J

W- булева случайная величина, параметр ветвления: /'(W = ])/;„.,

При И/','*' = 1- спуск по дереву вариантов. При - возврат в

исходную вершину дерева вариантов. При этом варьирование вектора , _ происходит с учетом накопленной информации.

5.Определение параметров процедуры поиска W,U,V,Y на пси one выполнения УЛУ.

Таким образом, УЛУ позволяет указать план проведения экспериментов и их анализ с делыо выбора перспективного направления поиска оптимальных вариантов.

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

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

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

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

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

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

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

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

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

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

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

Базовая подсистема представляет собой пакет инвариантных алгоритмических и программных модулей по непрерывно-дискретной оптимизации. Рабочая подсистема включает в себя прикладные программные модули и процедуры. В соответствии с перечисленными выше требованиями и принципами организации процедур непрерывно-дискретной оптимизации разработана структура базовой библиотеки модулей (рисунок).

Разработанная среда работает под управлением графической оболочки Windows 3.11. Данный выбор сделан с учетом широкой распространенности и популярности этой среды, что обусловлено дополнительными возможностями, которые предоставляет Windows по срашеншо с DOS: удобный интерфейс, выполненный в графическом режиме; многозадачность; аппаратная независимость программ, обеспечиваемая использованием драйверов устройств; использование для работы защищенного режима процессора, что позволяет более полно использовать аппаратные ресурсы.

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

Базовая библиотека модулей обеспечивает решение задач линейного и целочисленного программирования, булева целочисленного программирования и состоит из следующих компонентов:

1) модули линейного программирования;

2) модуля, реализующие метод Гомори (построение дополнительных ограничений);

3) модули, реализующие метод ветвей и вероятностных границ;

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

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

ISKL_ALL KANON DATE 4—-

модуль приведе- модуль при- модуль

ния СЛУ к виду ведения ввода

с искл. перемен- ЗЛП ....... данных « —

ными во всех к КФ

строках

DROBJLIN модуль решения задачи дробио-лнисйиого программирования

POISK

модуль поиска иеотр. базис, решения СЛУ

IS_BAS модуль решения ЗЛ11 методом искусственного базиса

JL

SOVMEST

модуль проверки совместности СЛУ_

REZULT 2 модуль решения одиокрите-рлальнои ЗЛП

REZULT1 модуль решения многокритериальной ЗЛП

TL

рсиюнис СЛУ ;

1 решгндо задачи дробно-линейного программирования; ,11т решение одиокрнтсриальиой ЗЛП симплскс-нстодои; —решение ЗЛП методой искусственного базиса; "решение многокритериальной ЗЛП

DOP_OGR

модуль ввода дополнительного ограничения

1

модуль BUILD PGR

Простое отсечение Гомори

Отсечение, получаемое в результате max пропой часгн добавляемого ограниченна

СЙГщсе отсечение на основании вектора АЛ ЬФА

Структура базовой библиотеки модулей

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

Рассмотрены вопросы применения двойственной задачи для решения задачи о покрытии, к которой сводится большой класс прикладных задач. Большую группу алгоритмов решения задачи составляют алгоритмы неявного перебора, основанные па идеях метода ветвей и границ. В этих алгоритмах часто условие целочисленности переменных ослабляется до условия 0 < x¡ < 1, что позволяет использовать для вычисления нижней границы решения симплексный метод или метод множителей Лагранжа.

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

Кроме того верхняя граница решения может определяться как симплекс-методом, так и более простым, но в то же время достаточно эффективным, градиентным способом.

В качестве примера рассмотрена задача выбора параметров для контроля работоспособности системы.

Математически задача оптимизации объема проверки систем может быть сформулирована следующим образом. Требуется определить параметры контроля Xj = 1,..., п), обеспечивающие максимум выражения

п

О = 2 qjXj при ограничениях

х^Т, XI е {0; 1 }; } = 1.....п.

') => 1

где qj - вероятность отказа элементов, контролируемых ^-м параметром; ^ - время контроля .¡-го параметра; Т - допустимое время контроля системы.

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

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

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

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

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

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

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

Идея излагаемого подхода состоит в сведении исходной проблемы к решению последовательности более простых задач.

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

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

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

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

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

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

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

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

5.Создан программно-методический комплекс оптимального проектирования, направленный на решение определенного класса задач непрерывно-дискретной оптимизации, отличающийся сочетанием автоматизм-

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

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

7. Создана автоматизированная обучающая подсистема по методам непрерывно-дискретного программирования, предусматривающая ведение обучения как с элементами(инсгрументарием) проектирования, так и обучения пользователя технологии, этапам проектирования конкретного объекта (алгоритма).

8. Разработанный программно-методический комплекс по методам непрерыпно-дискретной оптимизации для конструирования специализированного алгоритмического обеспечения в САПР внедрен в учебный процесс :ia кафедрах "Системы автоматизированного проектирования и информационные системы" Воронежского государственного технического университета и "Техническая кибернетика и автоматическое регулирование" Воронежского государственного университета и используется при проведении курсовых и лабораторных работ по курсам: "Конструирование алгоритмов н САПР", "Оптимизация в САПР", "Модели п алгоритмы оптимального выбора", "Модели и алгоритмы обработки финансовой информации".

Основное содержание -диссертации опубликовано в следующих работах:

1. Дискретно-непрерывные модели оптимального проектирования: Учеб. пособие / Я.Е. Львович, А.И. Каплинский, С.Ю. Белецкая, A.B. Питолин, М.В. Питолин. - Воронеж: ВГТУ, 1997,- 109 с.

2. Львович Я.Е., Питолин A.B., Питолин М.В. Компоненты обучающей подсистемы по оптимизации в САПР // Математическое обеспечение высоких технологий в технике, образовании и медицине: Тез. докл. Всероссийского совещания-семинара. - Воронеж, 1994 - С. 106.

3. Львович Я.Е., Питолин A.B., ПиТолин М.В. Методология построения обучающей подсистемы по оптимизации в САПР // Методы и средства оценки и повышения надежности приборов,устройств и систем: Тез. докл. Всероссийской науч.- техн. копф. - Пенза, 1994. - С. 27.

4. Питолин A.B., Питолин М.В., Медведь H.A. Организация обучающих процедур в автоматизированной обучающей системе по оптимизации ц САПР // Математическое обеспечение высоких технологий в

технике, образовании и медицине: Тез. докл. Всероссийского совещания-семинара. -Воронеж, 1994. - С. 105 .

5. Кандинский А.И., Питолин A.B., Питолип М.В. Алгоритмизация решения некоторых нестандартных задач оптимизации // Методы и средства оценки и повышения надежности приборов, устройств и систем: Тез. докл. Международной науч.-техн. конф. - Пенза, 1995. - С. 127-129.

6. Львович Я.Е., Питолин A.B., Питолин М.В. Алгоритмизация функционирования обучающих процедур по методам оптимизации .// Методы и средства оценки и повышения надежности приборов,устройств и систем: Тез. докл. Международной науч.- техн. коиф. - Пенза, 1995.-С. 91.

7. Питолин М.В. Формирование алгоритмических модулей по непрерывно-дискретной оптимизации в САПР для линейных моделей // Математическое обеспечение высоких технологий в технике, образовании и медицине: Тез. докл. Всероссийского совещания-семинара. - Воронеж,

1995. - С. 146-147.

8. Питолин М.В., Питолин A.B. Базовая библиотека алгоритмических модулей обучающей подсистемы по непрерывно-дискретной оптимизации в САПР для линейных моделей // Оптимизация и моделирование в автоматизированных системах: Межвуз. сб. науч. тр - Воронеж, 1995. - С. 76-80.

9. Питолин М.В. Адаптация стандартных программных средств оптимального проектирования для решения задач математического программирования // Актуальные проблемы анализа и обеспечения надежности и качества приборов, устройств и систем: Тез. докл. Международной науч.-техн. конф. - Пенза, 1996. - С. 148.

10. Питолин М.В., Садчиков A.A. Разработка интегрированной среды для конструирования программного и алгоритмического обеспечения задач дискретной оптимизации / / Математическое обеспечение информационных технологий в технике, образовании и медицине: Тез. докл. Всероссийского совещания-семинара. - Воронеж,

1996. - 4.1. - С. 39-40.

11. Питолин М.В. Алгоритмизация нестандартных вариантов методов ветвей и вероятностных границ // Актуальные проблемы анализа и обеспечения надежности и качества приборов, устройств и систем: Тез. докл. Международной науч.-техн. конф. - Пенза, 1997. - С. 52.

12. Питолип М.В. Организация вычислительных процедур дискретной оптимизации// Математическое обеспечение информационных технологий в технике, образовании и медицине: Тез. докл. Всероссийского совещания-семинара. - Воронеж, 1997. - С. 77.