Содержание к диссертации
Введение
Глава I. Основы структурно-функционального подхода к моделирова нию разработок на начальных этапах проектирования
I. I. Описание объекта разработки / ?
1.2. Структурно-функциональная модель класса технических систем «23
1.3. Описание процесса разработки 32.
1.4. Структурно-функциональная модель проектируемой ТС W
1.5. Концептуальное описание понятия "степень новизны" ТС и ее блоков 50
1.6. Структура комплекса моделей разработок бо
Глава II. Формализация понятия "степень новизны технической системы" 67
2.1. Основные понятия 67 2.2. Формализация понятия "степень новизны по значению признака" 70
2.3. Модель оценки новизны 3
2.2.4. Понятие цены блока 8&
Глава III. Задачи анализа и синтеза при проектировании с учетом степени новизны 32
3.1. Частные задачи проектирования /задачи анализа/ 92
3.2. Общие задачи проектирования /задачи синтеза/ 93
3.3. Свойства оценок общих задач ...НО
Глава ІV. Алгоритма решения задач проектирования 113
4.1. Дерево решений общих задач проектирования 115
4.2. Алгоритм решения задачи о коробках, как генератор макетов 430
4.3. МВГ - генератор макетов 1SG
4.4. Алгоритм с поглощением для решения задачи о коробках...439
4.5. Эвристические приемы сокращения перебора М&
4.6. Экспериментальное исследование эффективности алгоритмов ' решения задачи о коробках t№
4.7. Анализ чувствительности алгоритмов решения общих задач проектирования ^{
4.8. Эвристический алгоритм генерации макетов J?J
Глава V. Построение подсистемы АСУ на основе методов и алгоритмов моделирования разработок
5.1. Информационное обеспечение подсистемы моделирования разработок 118
5.2. Программное обеспечение блока автоматизированного построения сети І20
5.3. Использование алгоритма решения задачи о коробках в подсистеме оперативного планирования АСУП /52
Заключение 0S"
Литература 192
- Структурно-функциональная модель класса технических систем
- 2.2. Формализация понятия "степень новизны по значению признака"
- Частные задачи проектирования /задачи анализа/
- Дерево решений общих задач проектирования
Введение к работе
ХХУІ съезд КПСС определил как одну из основных задач одиннадцатой пятилетки задачу повышения эффективности и качества во всех областях народного хозяйства [I ] . Решение этой задачи в сфере научных исследований и опытно-конструкторских разработок предъявляет новые, все более высокие требования к управлению процессом создания новой техники. Для эффективного управления процессами проектирования применяются совершенные методы и средства, позволяющие сокращать время и затраты на создание новой техники, обеспечить высокое качество технических систем. Важную роль среди этих методов играют методы моделирования научных исследований и разработок.
Целью настоящей работы является разработка комплекса методов моделирования разработки технических систем, на начальных этапах проектирования.
В [2] дается следующее определение термина "проектирование" - "...весь комплекс работ по изысканиям, исследованиям, расчетам и конструированию, связанный с разработкой удовлетворяющих ряду заданных требований вновь создаваемых, а также реконструируемых, либо модернизируемых объектов, которые были бы наилучшими в экономическом или других специально предусмотренных отношениях".
Большая трудоемкость и неоднозначность проектирования систем неизбежно приводит к появлению в процессе проектирования как ошибок при планировании, так и ошибок в конструкциях технических систем (ТС). Сократить сроки разработки ТС, снизить трудоемкость их проектирования, существенно повысить объективность планов разработки ТС, улучшить качество проекта при снижении стоимости разработки можно только при использовании средств и методов автома- -s-- тизированного проектирования и управления, систем автоматизации проектирования (САПР) и управления (АСУ).
В.Гаспарский [3] определяет "проектирование" как: а) совокупность действий выполняемых проектировщиками; б) продукт этих действий, т.е. проект.
Таким образом, всякая разработка должна быть рассмотрена в двух аспектах: как технические изделие со сложной структурой, формирующееся в процессе НИОКР - объект разработки; как процесс разработки, т.е. комплекс операций или действий, выполняемых отдельными подразделениями предприятия в определенной последовательности и приводящих к созданию ТС-объек-тов разработки.
При функционировании САПР учет второго аспекта не является определяющим (существенным), тогда как функционирование АСУ разрабатывающим предприятием невозможно без совместного рассмотрения обоих аспектов. Как указывалось в [4 ] , система планирования и управления проектной организацией призвана, в числе прочих, решать следующие экономические, организационные и технические задачи: разработку реальных научно-обоснованных планов; правильное распределение работ между подразделениями исполнителями; обеспечение автоматизации разработки всех видов планов проектной организации.
В настоящее время широко разработаны методы автоматизированного составления плана предприятия и распределение работ с учетом загрузки на основе сетевых графиков или технических программ разработки отдельных темГ5-Ю].
Однако, собственно составление объективных сетевых графиков разработки ТС и является в настоящее время наиболее узким местом, снижающим эффективность планирования и управления разработками в условиях АСУ fll] . Это происходит по нескольким причинам, среди которых: большая трудоемкость построения вручную сетевого графика, включающего до нескольких тысяч работ и, как следствие, невозможность разработки нескольких вариантов плана проектирования ТС, невозможность (при отсутствии методов организации проектирования) построения объективного сетевого графика еще до начала проектирования ТС, что необходимо для составления тематического плана, назначения сроков разработки системы и распределения ресурсов.
Как следствие, часто план разработки ТС вида сетевого графика появляется слишком поздно, когда проектирование системы уже идет полным ходом, либо построенный заранее сетевой график не является объективным и требует постоянных значительных коррекций, опять же выполняемых вручную.
Таким образом, возникает актуальная проблема разработки формализованных моделей и методов планирования и управления разработкой на начальных этапах проектирования системы, учитывающих две стороны разработки - как объект и разработку как процесс.
Объективное планирование отдельной разработки требует знания структуры ТС в виде совокупности его частей (блоков, узлов, элементов) и связей между ними на всех уровнях, что возможно лишь после выполнения всех работ. Вместе с тем уже на начальном этапе планирования и организации проектирования необходимо иметь предварительное представление о контурах будущей разработки, как с точки зрения самого изделия, его основных особенностей и характеристик, так и - совокупности операций, которые необходимо запланировать, чтобы получить конечный результат.
Таким образом, как отмечалось в [12] , "необходима такая постановка задачи проектирования и такой выбор решения, которые позволяют получить оптимальный вариант организации будущих действий, причем проблема рационального выбора будет смещаться к все более ранним фазам проектирования".
Рассматриваемую в диссертационной работе проблему можно сформулировать следующим образом: - на основе вектора технических требований на разработку (запроса) определить образ объекта разработки, т.е. предполагаемый блочный состав технической системы и степени новизны отдельных блоков, позволяющий получить оптимальную по выбранному критерию сетевую модель процесса разработки.
Данная проблема может быть интерпретирована двояко: - на основе технических требований на разработку построить сетевую модель процесса проектирования, отражающую истиную сте- v пень новизны разработки относительно имеющего место научно-технического уровня разработок систем данного класса. - определить такой предполагаемый состав технической систе мы, задаваемой запросом на разработку, на основе допустимого пе рераспределения функций между отдельными модулями - блоками сис темы, с учетом неполноты фактических прототипов этих блоков, ко торый бы обеспечивал экстремум критериальному функционалу сетевой модели проектирования ("цене" разработки).
Каждая из трактовок данной проблемы акцентирует внимание лишь на одном из двух взаимосвязанных аспектов разработки: степени новизны объекта разработки (в первом случае) или оптимальности сетевой модели плана процесса разработки.
На настоящем уровне научного знания эта проблема относится к числу слабоструктурированных, важнейшая особенность которых "...заключается в том, что их модель может быть построена только на основании дополнительной информации, получаемой от человека, участвующего в решении проблемы" [13J .
Предложенное в работе понятие "образа разработки" перекли- кается с понятием "облик технической системы", введенным В.С.Кра-снощековым [ 14*16 ] , и отличается в следующих существенных моментах.
Автором ставится не задача оптимального проектирования объекта х." є Atq max F(cc) , а задача синтеза плана разработки ТС с учетом степени новизны, относительно самого "близкого", в некотором смысле прототипа системы. При этом вектор параметров считается заданным. Критериальной функцией считается "цена процесса разработки, а не эффективность функционирования проектируемой системы FM . Процедура построения образа разработки соответствует сужению прещендентного множества прототипов до од- '. ного или нескольких (эквивалентных по значению критерия) прототи- ' пов, задающих образ (образы) разработки. Тогда как формирование облика технической системы есть процедура сужения множества прототипов Х~[х} до облика П(Л) путем нахождения множества оптимальных по Парето векторов U(x)=fum(x)J- наборов отдельных качеств системы.
Учитывая данные моменты, можно указать место проблемы, рассматриваемой в диссертационной работе, как лежащей в пределах "внешнего" (по терминологии Н.П.Еіусленко [Т?] проектирования системы.
Совокупность требований, налагаемых в процессе анализа проблемы на математический аппарат формализации понятия "степень новизны", предопределяет выбор аппарата нечетких множеств Л.Заде f18*21] . Анализировались другие возможные подходы к формализации понятия "степень новизны", например: - введение функции полезности [22] , вероятностные модели, использующие законы распределения и часто применяемые в задачах распознования образов [23-24], - методы квалиметрии Г.Г.Азгальдова [25І . Все они оказались неприменимы для формализации понятия "степень новизны": либо вслед- ствие невыполнения аксиом, лежащих в их основе (методы теории полезности и кваяиметрии), либо вследствие невозможности получения на практике требуемой информации (о законах распределения - для методов распознования образов, о весовых коэффициентах и значениях оценок - для методов квалиметрии).
Проблема автоматизированного построения претендентного множества прототипов и выбора из них оптимального тесно смыкается с задачей автоматизированного синтеза структуры, структурной оптимизацией [26*28 ] , а также проблемой поиска новых технических решений (ТР) с помощью ЭВМ [29-30]
Связь с проблемой синтеза новых ТР осуществляется в следующих двух аспектах: - построение новых ТР на базе прототипов является одним из путей синтеза технических решений, не являющихся пионерскими (что совпадает с крутом проектируемых технических систем, рассматрива емых в диссертационной работе) [31] ; в общности некоторых методологических предпосылок и подходов, положенных в основу как процедуры построения образа, так и отдельных методов синтеза решений [32+34] .
В частности, для синтеза ТР используется процедура, называемая "качественная экстраполяция" - перенос какого-либо свойства одних элементов объекта на другие [33] . Так, например, в ^34\ выделяются следующие схемы синтеза ТР: а) создание новых типов ТР на базе прототипа путем: включения в него нового признака (функции), заимстванно-го из предыдущего опыта; замена того или иного свойства прототипа новым; исключение из прототипа признака, о) создание новых ТР на базе прототипов, путем дополнения прототипа качественно новым признаком. - /о -
Подход, основанный на качественной экстраполяции в процедуре построения образа разработки нашел свое отражение в следующих моментах: учете факта появления в запросе на разработку качественно новых функций и признаков системы, не зафиксированных на множестве ранее выполненных разработок, имеющего место в реальных ситуациях проектирования; принятии ряда предложений, допускающих сужение и расширение функциональных и призначных описаний отдельных блоков ТС в виде предписаний прототипа.
Предлагаемая процедура построения образа разработки, основанная на построении множества альтернативных вариантов прототипов с последующим выбором оптимального из них по критерию минимума степени новизны, методологически базируется на морфологическом подходе к синтезу систем, часто используемом при синтезе структур и поиске новых ТР. Основу данного подхода составляет метод "морфологического ящика" Ф.Цвикки Г35] . Дальнейшее развитие идеи морфологического подхода получили в нашей стране в работах В.М.Одрина и С.С.Картаво-ва [36*38]
В [38] выделяются две группы методов: методы, сводящие морфологический синтез к дискретному программированию, в частности работы А.И.Половинкина [29J и В.Л.Волковича Г39 J , методы, основанные на последовательном переборе возможных вариантов, в частности работы В.С.Михалевича [28,40] , А.Г.Шигина [41,42] , А.Г.Мамиконова [43] , И.С.Потемкина [44.45J .
В работах И.О.Потемкина предлагается вариантный метод синтеза, суть которого заключается в автоматическом комбинировании конструктивных признаков из их набора, описывающего объект проектирования f44] или фрагментов tэлементов состава) объекта [45] .
Предлагаемый в диссертационной работе подход к построению претендентного множества прототипов можно рассматиривать как развитие вариантного метода синтеза, когда комбинирование проводится на нескольких уровнях описания: - рассматриваются различные комбинации блоков системы К элементов состава), покрывающие требуемое множество функций и признаков разрабатываемой системы; рассматриваются различные комбинации функций и признаков на множестве допустимых предписаний для каждого из блоков состава для всех комбинаций блоков.
В диссертационной работе рассматривается возможность сведения задачи нахождения оптимального прототипа к задаче линейного целочисленного программирования К1Щ1) с булевыми переменными. Проведенный в работе анализ существующих методов решения задач такого типа показал неэффективность их применения вследствие значительного увеличения размерности задачи при сведении ее к задаче ЦЛП.
Это потребовало разработки новой модификации метода ветвей и границ - генератора макетов. Макетный алгоритм позволил поставить задачу нахождения оптимального программирования в виде дискретной минимаксной задачи.
В абстрактной постановке такая задача была названа автором задачей "о коробках" и представляет собой новый класс дискретных минимаксных задач комбинаторного типа.
Рассмотренные в Г4б] алгоритмы решения дискретных задач, близких по структуре к задаче о коробках оказались неприменимы в чистом виде для ее решения. B диссертационной работе предложены новые алгоритмы для решения задачи о коробках, являющиеся модификацией общей схемы метода ветвей и границ применительно к специфике задачи.
Научная новизна работы складывается из следующих компонентов:
I. Предложен подход к формализации ранее неформализованной проблемы построения плана (сетевого графика; процесса разработки технической системы (.ТСJ по запросу (техническим требованиям) на ее разработку, основанный на "сшивании" сетевой модели из типовых сетевых модулей (ТОМ), в соответствии с образом разработки, отражающим блочный состав системы и степень новизны 1С и ее блоков; г. Предложены принципы построения системы иерархически вложенных типо#сетевых модулей.
Предложен комплекс моделей разработки на начальных этапах проектирования, позволяющий реализовать процедуру построения образа разработки.
Разработана методика построения отдельных моделей процесса, классифицируемых на : модели объекта разработки и модели процесса разработки, модели класса технических систем и модели проектируемой системы.
Данная методика базируется на следующих предложенных в диссертации концепциях: обобщении и формализации опыта проектирования технических систем некоторого класса в виде струЕстурно-фз^нкциональной модели объекта, отражающей: блочный состав ТС, выполняемые ею функции и характеризующие ее параметры (признаки); обобщенного описания элементной базы систем (блоков) с помощью введенного понятия "обобщенный представитель"; обобщении и формализации опыта сетевого планирования разработки систем данного класса в виде структурной модели процесса проектирования, задающей правила назначения стадий и этапов цроек- тирования в зависимости от степени новизны разработки; рассмотрения новизны технической системы относительно прототипов, как их неполноты относительно запроса на разработку по функциям, наименованиям признаков и их значениям; формализации понятия "степень новизны технической системы" с использованием математического аппарата нечетких множеств и лингвистической переменной; при этом предложена отличная от традиционной трактовка операции объединения нечетких множеств и доказана ее необходимость при оценке степени новизны; определении образа разработки, как такой допустимой комбинации блоков соответствующей степени новизны, которая обеспечивает минимум критериальной функции на всем множестве реальных и гипотетических прототипов системы; постановка задачи формирования образа разработки, как дискретной минимаксной задачи, принадлежащей к новому, не рассмотренному в литературе, классу комбинаторных задач и названной автором задачей "о коробках".
Предложенные концепции построения моделей разработки реализуются с помощью разработанных в диссертации: процедуры построения структурно-футшциональной модели объекта проектирования; процедуры построения структурной модели разработки; - процедуры построения образа разраоотки, в виде методов решения задачи о коробках, представляющих собой точную и приближенную модификацию метода ветвей и границ, учитывающие специфический вид целевой функции задачи; - процедуры динамического управления моделью в процессе по строения образа разраоотки по правилам, полученным в результате анализа чувствительности алгоритмов к неточности исходных моделей процесса и объекта разраоотки для класса технических систем.
Практическое использование предложенных в диссертационной работе подходов и системы моделей разраоотки на начальных этапах проектирования основывается на их реализации в виде комплекса программ решения отдельных задач, входящего в состав функциональной подсистемы комплексного оперативного управления разработками АСУ разраоатывающим предприятием. Показана возможность использования математической модели задачи "о корооках" и алгоритмов ее решения в другой предметной области - маршрутизации партий деталей в рамках автоматизированной подсистемы оперативного планирования и управления производством.
Практическая результативность работы подтверждена актами о внедрении. диссертация состоит из пяти глав и приложения. J3 первой главе рассматриваются основные положения предлагаемого подхода к моделированию разработок на начальных этапах проектирования. Предлагается комплекс моделей разработки и формулируются методики построения некоторых из них. приводится концептуальное описание понятий образ разработки и степень новизны, формируются требования к математическому аппарату для их формализации.
Вс второй главе осуществляется математическая формализация понятия степень новизны технической системы и ее блоков, формулируется математическая модель оценки новизны С МОИ). Вводится понятие "цены" блока и доказывается ряд утверждений о свойствах новизны и цены блоков при различных предписаниях функций.
В третьей главе дается математическая формулировка частных и общих задач проектирования (задач анализа и синтеза прототипов), вытекающих из предложенного подхода, в виде комбинаторных оптимизационных задач. Сравнивается ряд методов дискретной оптимизации с точки зрения их применимости к решению этих задач и предлагает- ся, как наиболее эффективный метод, метод ветвей и границ. Осуществляется формальная постановка задачи в терминах "цен", доказывается ряд утверждений о свойствах оценок отдельных частных и общих задач при различных подходах к оценке степени новизны, предлагаются алгоритмические схемы для решения этих задач. а четвертой главе рассматриваются различные подходы к представлению комбинаторных дискретных задач в виде дерева перебора. Предлагается, как наиболее эффективный, метод, реализующий эвристику сведения задачи к подзадачам. Б качестве оператора сведения предлагается использовать макетный генератор. На основании доказанных в главе 3 утверждений об оценках задач предлагается процедура направленного перебора в пространстве макетных подзадач. Процедура генерации макетов формулируется как дискретная минимаксная задача о коробках и предлагается ряд алгоритмов ее решения, основанных на введенных понятиях пути в матрице цен, префикса пути и поглощаемой вершины, а также доказанных утверждениях об их оценках. Предлагается совокупность эвристических алгоритмов дополнительного сокращения перебора за счет переупорядочивания макетного дерева. Рассматривается динамическое управление переборным алгоритмом построения образа разработки с учетом систематической и случайной погрешности моделирования, как следствия неточности исходных моделей объекта и процесса разработки класса технических систем. Рассматривается приближенный эвристический алгоритм решения задачи о коробках.
В пятой главе представлен материал, иллюстрирующий реализацию системы моделей разраоотки в виде комплекса программ, входящих в функциональную подсистему комплексного оперативного управления разработками AU-У РП. Приводится организационная схема моделирования разработки на начальных этапах проектирования в рамках ФЇЇ КОУР.
Апробация работы. Основные положения и результаты диссертационной работы докладывались: на московской городской конференции молодых ученых и специалистов по повышению надежности, экономичности и мощности энергетического и электротехнического ооорудования, Москва, май 1У76г. на семинаре "Измерение эффективности и качества в больших системах", Москва,МДНТЇЇ, март 1У7Уг. на II Всесоюзном научно-техническом семинаре "Оптимизация технических систем", Винница, апрель 1У7Уг. на конференции "Оовершенствование планирования и управления промышленным предприятием", овердловск, ІУ7УГ. на III Всесоюзной школе молодых ученых и специалистов "Теория систем и ее приложения", Ереван, іУЬиг. на совещании-семинаре "Теоретические и прикладные вопросы разраоотки, внедрения и эксплуатации ОАШ? радиоэлектронной аппаратуры", Алушта, 1981г.
Но основным положениям диссертации опубликованы ь печатных работ.
Автор выражает свою олагодарность д.т.н.,проф.темникову Ф.Е. и к.т.н.,доц.Орлову В.А. за постановку задачи диссертации и оказанную помощь в решении возникавших вопросов.
Структурно-функциональная модель класса технических систем
Представление объекта разработки технической системы в виде совокупности функции, признаки, состав позволяет единообразно описать все существенные (в рамках рассматриваемой проблемы) особенности как уже выполненных разработок, так и будущего изделия.
Целесообразно обобщить такое описание ТО на целый класс, в некотором смысле, схожих объектов. Предпосылкой разбиения всех разработок на классы является относительная традиционность разработок на предприятии, возможность их типизации по структурным схемам и назначению.
Определение 1.3.
Структурно-функциональной моделью класса ТС (СШК) называется обобщенное описание совокупности однородных технических систем и входящих в них блоков, отражающее структурно-функциональные особенности всех систем (как разработанных ранее, так и проектируемой), существенные в рамках проблемы построения образа разработки.
СШК представляется в виде пятерки множеств: в, S, р, Л, М где В = 1 } » І -множество, отражающее блочный состав ТС данного класса, элементная база ТС; Ф, X - множество,соответственно, функций и признаков, описывающих ТС данного класса; М - множество, отражающее взаимосвязи элементов В , Ф и X описания ТС; $ - множество, отражающее структурные связи блоков в системах данного класса.
Предложение 2
Все множество разработок может быть разбито на конечное число классов, определяемых общностью СШЕ для всех ТС, соотносимых с данным классом.
Разбиение всех выполненных разработок на К классов осуществляется на следующих основаниях сходства ТС одного класса:
1. Все изделия одного класса имеют одинаковое назначение.
2. Все изделия одного класса имеют общий набор основных функций - функциональное описание і -го класса ТС, задаваемый кортежем Л, где - число функций для изделий к -го класса. При этом выполняются соотношения: где / = г..; - номер изделия в і-ом классе; /J - мощность і -го класса (число входящих в него изделий); 9%. - функциональное описание / -ой ТС -і -го класса.
Таким образом функциональное описание А -го класса покрывает все функциональные описания технических систем данного класса.
3. Все изделия одного класса имеют общий набор наименований признаков - призначное описание і -го класса ТС, задаваемый кор тежем: Л І А%} , і--J. 2, ..., / , где Rk - общее число признаков в призначном описании класса. При этом: V к, / = Л S и =, / где Л - призначное описание / -го изделия і -го класса.
Таким образом призначное описание Х 6 -го класса изделий покрывает все значимые признаки технических систем данного класса.
4. Все изделия одного класса имеют общий набор компонент со става - блочное описание -го класса ТС, где 1к- общее число различных наименований компонент состава ТС к -го класса. Конфигурация каждого изделия k -го класса может содержать не все 1± возможных блоков: V к, j = Bk е S ; ,f однако &, =y / 5. Каждому компоненту состава SA с наименованием соот ветствует одна и только одна версия структурной модели процесса проектирования (СШШ) при разработке системы ё-го класса.
В дальнейшем, для упрощения записи, индекс класса -И будет, где это возможно, опускаться. При этом подразумевается, что описываемые действия выполняются для изделий того из і = і, 2,..., к классов, к которому принадлежит данная разработка.
Определение 1.4.
Структурно-функциональной моделью блока вида В- (СФМ (6-) ) называется обобщенное описание совокупности блоков 4 . (" є наименования 4 : Зс- , Ф f Х, М- где B L - {&;„ J - множество реализаций Sift блока (- ; Фіг л{ - множества функций и признаков, описывающих блоки Siku ; = U ін ; XL- U Xt„ ; ( /V. - индексное множество для бдо-ков вида - , 9J„ ,Д;„ - их функциональное и признанное описание) Мс - множество,отражающее взаимосвязи элементов в(- , 9= ; , Х Определение 1,5;
Обобщенным представителем I- блоков ,-м называется фиктивный блок t функциональное и призначное описание которого Ф %6 являются отражением СШ (;) .
Для каждой реализации 6i/t обобщенного представителя SL справедливо: ,- - , Л/» s V
Тогда описание класса ТС в виде тройки Р (в, в), (л, X) можно трактовать как описание обобщенного представителя ТС оис-темТС 4 -гокяасоа.
Компонент " , данного описания включает в себя, как обобщенные представители всех блоков, вошедших в состав хотя бн одной системы ТСІ/ , так и вновь спроектированных блоков (например, в рамках НИР) пригодных для использования в системах к -го класса.
Формализация понятия "степень новизны по значению признака"
Для формализации отображения 7 . (я, я) - tfax) = 7 примем следующее достаточно естественное предложение. Предложение 18
Степень новизны блока 4- относительно прототипа ? по значению признака с наименованием хг є Х есть некоторая функция близости значений аг и х признака ос± в блоке 4 и его прототипе #f . В качестве меры "близости" примем нормированное по & зна чение признака хг : Хх =fx(x,x ) » гДе / функция нормировки. Тогда, 7Z : х . - 4($ъ) = є т Предложение 19 Для любого признака Sc & X структурно-функциональной мо дели класса ТС может быть построена такая функция нормировки / , что любые две пары (х 1, х?) и (хь, ) признака «z , для которых г{х?\ ) = Л (я?1, ? ) , сообщают объектам 4 и 4 z ОДИУ и ту же степень новизны по значению признака относительно прототипов 4 и 42 соответственно, т.е. У ( ъ, х?), Ґх , х . ) » если set = дг/ , то
Данное предложение позволяет построить функцию t;( .) инвариантную относительно конкретных значений и -г/ в запросе на разработку и прототипе, т.е. общую для всех блоков вида . . Тогда, при функции нормировки у , допустим, вида: . .. „ „/
МК, ) =± (то єсть t={/+Jx! ), любое требуемое в запросе на разработку изменение х в ( %) раз, например на 1($, будет инициировать для блока е;ґгєX;) одну и ту же степень новизны, допустим "модификация". В дальнейшем для упрощения записей будут использоваться следующие обозначения: t - степень новизны блока 4? относительно прототипа 4 ; с ; - то же самое, если нет необходимости выделять индекс р прототипа, а надо выделить номер реализации блока 4 используемой в /з-м прототипе; t - степень новизны относительно обобщенного представителя «г.
Из предложений П4, Ш8 и ПІ9 вытекает возможность представить отображение 7Z : Д -» і( = еє Т в виде системы функций: \f Єє/ } ji/ : Д -» S - отображающих нормированное значение признака в некоторое числовое значение S , характеризующее совместимость величины со значением 4е степени новизны. Щс і si7 J -= +е е Т - отобра жающей совокупность значений $ по всем -6еТ в значение степени новизны по значению признака
Совокупность вышеописанных требований, налагаемых на математический аппарат формализации понятия "степень новизны", практически однозначно предопределяет выбор аппарата нечётких множеств и лингвистической переменной Л . Заде f18-21J . Необходимые сведе ния об этом аппарате сведены в определение 2.1 и представлены в Приложении.
Для лингвистической переменной Л ="степень новизны" терм - множество ТС Л") её значений порождается контекстно свободной грамматикой [71 J G = ( V? , У#, , Р ) , где VT = ( &, Р, ff " W "е; и и ) - множество терминальных символов; y =-(S,A,B,C,8,tFt// ) - множество нетерминальных символов; Р - система подстановок (продукций) вида 1. S- A 5. Л-»# 9. С - а 2. S - S u/iu А Ь.А- Е Ю.З- 3.8- //eS 1.A- F II. Е -«?/ 4. А С 8. А-+Н 12. /=- // 13. //- /- Семантическое правило для переменной "степени новизны" индуцируется синтаксическим правилом, то есть смысл М(-ЬЛ) терма Ь є ТҐЛ) определяется его синтаксическим деревом.
В диссертационной работе, как в 72, 737 , элемент отражает конкретную ситуацию (яА, р) проектирования блока, которая может быть соотнесена с каждым из значений степени новизны. Предложение 20 Для каждого признака х є X , для каждого из значений t 6 Т = /У / z,..., t ) степени новизны 7"= / , -&/&?, -г , м, /?/»/J , существует йункция совместимости (ФС) // : Х — L &,ll , ста вящая в соответствие каждому нормированному значению х: є лt признака . число 3 0, Л - совместимость значения с понятием і = Т
В зависимости от типа признака - и функции нормировки /z универсальное множество лк базовой переменной «, будет бесконечным Хх-{- , ) или конечным Хх {г } множеством. Например, для признака sc - "число каналов", область значений - Лг = ( , 2, 3, 4, б) . Тогда при функции нормировки /t = С г - zx) имеем: % = (-S, -4, -3, -2. -1, О, 4, 2, 3, 4 , S) Для упрощения дальнейшего изложения будем временно считать имеющим место
Частные задачи проектирования /задачи анализа/
Отличие наблюдается в способах оценки макета при различных подходах: - при подходе 2 или 3 оценка {&J ) осуществляется путем решения задачи 2 (см. 3.1); - при подходе I оценка Cfef ) определяется решением задачи 3-І, которая (см. 3.1) сводится к генерации реальных прототипов 8 /в" , инициируемых макетом 3 с последующей оценкой каждого с помощью задачи I и выбору в качестве оценки макета лучшей из оценок прототипов
Очевидно из описания постановок задач 8 - 1,2,3, что алгоритм их решения внешне будет совпадать с алгоритмом решения задачи 7-І (рис. 3.5а), так как задачи 7-І и 8-І абсолютно идентичны, а в задачах 8-2 и 8-3 будет иметь место только отличие в способах оценки реальных прототипов макета по задачам 3-2 и 3-3, соответственно, а не по задаче 3-І, как это имеет место в блок-схеме, рис. 3.5а.
Значения О- . и с-- определяются видом массива M6v s (рис. 3.1 и 3.4) и способом нахождения jt (у-) и t-(fc) при различных подходах.
Вид массива C/SC?os { ?;„;} U i cty} представлен на рис. 3.6 а),б) для массивов Ma90g при подходе I (рис. 3.1) и 2,3 (рис. 3.4). Так как при подходе I не определена степень новиз-да clfj) обобщенного представителя /, по функции - (см. предложение 24) и цена ,у обобщенного представителя « (см. определение 2.12), при подходе I не определена матрица цен Се9„ .
Таким образом для всех задач 1-8 существует следующая общая процедура построения матрицы цен л л :
Шаг I YZi& Х0 , где Х0 - элемент зацроса на разра ботку tp0/ (Хо, Хо) ; V-%;3 , где в - элементная база СФМО; ІЇ4іиє&; » где 3; - совокупность реализаций бло-ка вида 4 В , на основе ВДР и МОН определить степени новизны tih(x) Утведодение 17. Для задачи 8 при различных подходах справед шво Є(2-з)4СС#-л) ССї-Л)
Совокупность утверждений 8-17 позволяет, используя свойства щенок макетов, наборов реальных прототипов и задач, отказаться в ілгоритмах от полного перебора прототипов /задача 7-І, 8-І, 2-3/ рис. 3.5а/ или макетов /задача 7-2 рис. 3.56/. Вопросам разработки ілгоритмов рационального перебора будет посвящена глава 4.
Выводы по главе 3
1. Положения структурно-функционального подхода к моделирова-ию разработок и введение понятия "цена блока" позволяют сформулиро-ать отдельные частные задачи проектирования /задачи анализа/ в виде адач дискретной оптимизации с булевыми переменными.
2. Взаимно-вложенные частные задачи проектирования алгоритми-ески могут быть сведены к конечному числу шагов поиска элемента ножества прототипов, имеющего минимальную цену.
3. Общие задачи проектирования /задачи синтеза/ являются зада-эми целочисленного линейного программирования с булевыми переменны-и.
4. Большая размерность задач делает не эффективным использова-ле известных методов решения задач бивалентного программирования, эедлагается разработать модификацию метода ветвей и границ, учиты-шцую особенности конкретных задач.
5. Для нахождения оптимальных решений общах задач проектирова-ш могут быть использованы процедуры, основанные на переборе возмож-IX прототипов.
6. Анализ процедур нахождений оптимальных решений позволяет ;елать вывод о существенной похожести алгоритмов решения общих дач 7 и 8 проектирования при различных подходах, как комбинаций горитмов соответствующих частных задач.
7. Представление общих и частных задач проектирования в терминах "цен" позволяет свести общие задачи 7 и 8 к комбинаторным задачам нелинейной оптимизации с минимаксной целевой функцией.
8. Совокупность утверждений 8-17 позволяет, используя свойства оценок макетов и задач, отказаться при решении задач 7 и 8 от полного перебора прототипов или макетов и организовать рациональную процедуру направленного перебора по схеме ветвей и границ.
Дерево решений общих задач проектирования
Сформулированные в 3.3 задачи оптимизации 7.и 8 представляют собой комбинаторные.задачи вариантного выбора. Задача 7-І, 8-1.2.3. Найти вектор / „ ) такой, что Таким образом постановка задач в данном параграфе ив 2.3 эквивалентны.
Решение комбинаторных задач удобно представить в виде дерева вариантов f94] . Основные сведения о графах типа дерева сведены в одно определение,4.1. Определение 4.1. а) Деревом 3(Х, ) называется ориентированный граф в каждую вершину которого входит не более одной дуги. б) Вершина дерева, в которую не входит ни одна дуга называет ся начальной или корнем дерева. в) Вершина, из.которой не выходит ни одной дуги называется конечной или висячей. г) Число дуг, соединяющих две вершины Xа и X называется расстоянием effx . X ), между этими вершинами. .. . д) Расстояние между вершиной X и корнем дерева называется ярусом ЯX . .... е) КУСТОМ дерева КXа называется поддерево инициируемое какой-либо вершиной X .
Для комбинаторных задач с булевыми переменными традиционным является представление вариантов в виде.бинарного дерева в пространстве состояний - дерева (рис. 4.1).
С каждой вершиной Xа отождествляется некоторое состояние, представляющее собой кортеж булевых переменных.
На ярусе Я в каждом из кортежей этого яруса значимы только Я булевых переменных, задающих частичное решение задачи.
В каждой вершине яруса Я переход к ярусу д х осуществляется ветвлением по правилу: частичное решение яруса ./I дополняется значениями I или 0 еще одной булевой переменной. Такое прави ло ветвления определяет название дерева как бинарного.
Для задачи (4.1) каждое состояние характеризуется на ярусе булевым вектором Х(Я ) = ( , ,,..., Xfi., Х,ч ,..., Xd) где Ч х., ё X (Я ) сся = і у о _ Вектор Х(#) , определенный на Я Я называется частич ным решением. Вектор Х(Я) , соответствующий висячей вершине, называется решением задачи и удовлетворяет ограничению (4.4). Очевидно Я 1 /\/ 3 , где Я - индексное множество для последовательно перенумерованных значений { & ;„ j . При выполнении.условий (4.2) и (4.3) вектор Х(Я) будет допустимым решением. Очевидно, что задача 4-І на -дереве рис. 4.1 имеет 2я =21Л//А3 решений, из которых только ничтожная часть является допустимыми. Таким образом оценка объема перебора при представле нии задачи (4.1) в виде -дерева О = 0(2 ) При рассмотрении задачи (4.5) на S -дереве оценка перебора 0S - 0(2z 7Jm
.Предлагается другой способ представления решения задач (4.1) и (4.5) в виде дерева, более удобный для рассматриваемых комбинаторных задач вариантного синтеза. Такое ЕМ В -дерево для задачи (4.1) представлено на рис. 4.2. Здесь используются три стратегии ветвления, соответствующие трем ярусам ЕМ В- дерева.
Ветвления согласно стратегии Е начинаются из корневой вер шины Л . Каждой.дуге, исходящей из вершины J1 соответствует в задаче 4.1 определенная этикетка ВА , удовлетворяющая ограни чению: Vj ZL Z. ос.. 7,1 , то есть ослабленному ограничению (4.2) задачи (4.1).
Из вершин , полученных применением стратегии / , ветвления продолжаются о использованием стратегии М . При этом каждой ду -ге исходящей из вершины 8 е соответствует один и только один макет в"/ef , инициируемый этикеткой 8J вершины еєЕ При этом,каждый макет удовлетворяет ограничениям релаксированной задачи 4.1 (без ограничения 4,3). При использовании третьей стратегии 3 каждой дуге исходящей из вершины 8" / sf соответствует один и только один прототип 3 / Ё"
Очевидно, что для задачи (4,5) может быть использовано сокращенное представление в виде двухярусного ЕМ -дерева.
Представление решения задач 4.1 и 4.5 в виде ЕМ В- и ЕМ-деревьев адекватно процедурам нахождения образа разработки и цены плана, представленным в виде блок-схемы рис. 3.5 а) б).
Для перебора на ЕМВ- и Ш-деревьях справедливы оценки, полученные в І.Б : Р =M=Z Ме ; Р- Z. fl L П л/ Єе Є Є S»6Me рал /пеннее "
Здесь Е - индексное множество этикеток, /% - индексное множество макетов одной этикетки, ве - индексное множество блоков в этикетке, л/ - число реализаций блока 4р этикетки, М - общее индексное множество макетов, Р„ - общее число макетов, Р - общее число прототипов.
