Содержание к диссертации
Введение
Глава I. Обзор методов решения задач нелинейного дискретного программирования и их применение в задачах оптимизации надежности сложных систем 13
1.1. Методы решения задач нелинейного дискретного программирования 13
1.2. Методы решения задач оптимального резервирования при проектировании сложных систем 22
Глава II Метод послвдователшого анализа вариантов в задачах дискретной оптимизации 37
2.1. Общая схема решения задач дискретной оптимизации 37
2.2. Метод решения двухуровневой задачи дискретного программирования 54
2.3. Метод решения задачи дискретного монотонного программирования 70
Глава III. Математические модем и алгоритмы решения задач оптимизации надежности непоследовательных систем 76
3.1. Постановка общей задачи оптимизации надежности непоследовательной системы 76
3.2. Алгоритм решения задачи оптимизации надежности непоследовательной системы с явно заданными множествами возможных вариантов подсистем. Пример синтеза системы 82
3.3. Алгоритм решения задачи оптимизациинадежности непоследовательной системы с использованием разнотипного резервирования 92
3.4. Сведение задачи оптимизации надеж ности непоследовательной системы к задачам дискретного сепарабельного программирования 116
Глава ІV. Программная ремизация алгоритмов оптимизаций надежіости непосщоватешьных систем и их ис пользование для решения задач оптимального проектирования 126
4.1. Программная реализация алгоритмов оптимизации надежности непоследова тельных систем 126
4.2. Диалоговая система автоматизированного проектирования структур сложных систем по критерию надежности 129
4.3. Экспериментальное исследование алгоритмов оптимизации надежности непоследовательных систем 141
Заключение 151
Список основной использованной литературы
- Методы решения задач оптимального резервирования при проектировании сложных систем
- Метод решения двухуровневой задачи дискретного программирования
- Алгоритм решения задачи оптимизации надежности непоследовательной системы с явно заданными множествами возможных вариантов подсистем. Пример синтеза системы
- Диалоговая система автоматизированного проектирования структур сложных систем по критерию надежности
Введение к работе
Высокий уровень надежности - одно из основных требований, предъявляемых при проектировании технических систем. Одним из ме-тодов повышения надежности сложных систем, широко применяемым в практике проектирования, является резервирование. Однако, повышение надежности систем за счет резервирования связано с увеличением значений их технико-экономических характеристик таких как вес, стоимость, габариты и т.п. Поэтому возникает задача оптимального резервирования /оптимизации надежности/, которая заключается в определении оптимального /максимального/ по надежности варианта структуры системы с учетом заданных ограничений на технико-экономические характеристики. Решение задач оптимального резервирования тесно связано с использованием моделей и методов дискретного программирования.
В настоящее время при решении задач оптимального резервирования наиболее широко используются модели последовательных систем, то есть систем, которые отказывают при отказе хотя бы одной подсистемы, причем отказы подсистем независимы. В математической постановке эти задачи с аддитивными ограничениями по технико-экономическим характеристикам представляются как задачи дискретного се-парабельного программирования, для решения которых предложены разнообразные алгоритмы.
Вместе с тем, на практике возникают более сложные задачи оптимизации надежности, поскольку появление отказов отдельных подсистем в реальных системах не приводит, вообще говоря, к полному отказу всей системы в целом, а лишь ухудшает надежность ее функ х/ Здесь и ниже под надежностью понимается вероятность безотказной работы системы /подсистемы/ на заданном интервале времени ционирования. Примерами систем, в которых отказы отдельных подсистем не приводят к отказу всей системы в целом, являются монотонные структуры [ 7 ] /когерентные системы [ 122-124, 128 ] / или непоследовательные системы/ поп series- рагаве sysiem /[і7б], системы с произвольной структурой [97J . •
В настоящее время область прикладной теории надежности по оптимизации сложных систем интенсивно развивается: рассматриваются модели систем, обладающих промежуточным уровнем надежности, отличным от уровня, соответствующего полной работоспособности или отказу системы, конкретные примеры прикладных задач, разрабатываются и исследуются оптимизационные алгоритмы /см.обзор, помещенный в § 1.2 работы/.
Однако гсуществующие модели и алгоритмы оптимизации надежности сложных систем не удовлетворяют в полной мере растущим потребностям практики. Поэтому рассмотрение новых моделей и методов решения задач оптимального резервирования сложных систем представляет как теоретический, так и практический интерес. Задачи оптимального резервирования непоследовательных систем ввиду нелинейного критерия /функции надежности/ сводятся к задачам нелинейного дискретного программирования, разработка методов решения которых представляет самостоятельное теоретическое и прикладное значение.
Накопленный к настоящему времени опыт решения задач нелинейного дискретного программирования, а также проводимые теоретические исследования свидетельствуют о том, что решение этих задач затруднительно без выявления свойств функций ограничений и критерия /монотонность, выпуклость, дифференцируемость и т.п./, специфики структуры множества ограничений, учета структуры множеств возможных значений переменных. Специфику задач необходимо учитывать как при разработке новых подходов и применении известных ме - б тодов дискретного программирования для решения задач из прикладных областей, так и при решении отдельных практических задач.
Среди прикладных задач оптимизации надежности последовательных и непоследовательных систем большое значение, как отмечалось в [80J , имеет задача оптимального резервирования, в которой резервирование осуществляется за счет использования в подсистемах разнотипных резервных элементов. В математической постановке указанная задача является двухуровневой задачей дискретного программирования: построение подсистем на основе разнотипных элементов и определение их надежности и технико-экономических характеристик - второй /нижний/ уровень; построение варианта системы в целом из отдельных подсистем - первый /верхний/ уровень.
Непосредственное сведение указанной задачи оптимального резервирования к "одноуровневой" задаче /с явно заданными множествами возможных вариантов подсистем/ на практике не представляется возможным ввиду ее огромной размерности даже при сравнительно небольшом числе подсистем, числе типов элементов и небольших значениях кратностей резервирования элементов.
Актуальность, теоретический интерес и практическая значимость двухуровневых задач дискретной оптимизации обусловливают необходимость их дальнейшего исследования и разработки методов решения.
В прикладном отношении разрабатываемые методы решения задач нелинейного дискретного программирования должны быть ориентированы на нахождение точных и приближенных решений, учитывать особенности решаемых задач, что наиболее актуально при решении задач большой размерности, к которым относятся и двухуровневые задачи дискретной оптимизации.
Как показывает опыт, использование разработанных моделей и алгоритмов особенно эффективно при создании на их основе пакетов прикладных программ и диалоговых систем с развитым математическим, системным и информационным обеспечением. Создание подобного рода систем актуально для решения задач оптимального проектирования, где они являются инструментарием в работе проектировщиков.
Одним из универсальных подходов к решению задач математического программирования является методология последовательного анализа вариантов, общий формализм которой разработан в начале 60-х годов В.С.Михалевичем [б9, 75 J .
В работе этот подход является основой для разработки методов и алгоритмов решения указанных выше классов задач дискретной оптимизации и прикладных задач теории надежности.
Диссертационная работа выполнялась в рамках госбюджетной темы "Разработка методов моделирования, идентификации и оптимизации сложных динамических объектов и создание на их основе комплекса программ для автоматизации обработки натурных испытаний, структурного проектирования систем управления летательными аппаратами и линейных ускорителей", которая входит в Целевую комплексную научно техническую программу ГКНТ СССР 0.Ц.027 /Постановление ПШТ, Госплана СССР, АН СССР № 474/250/132 от 12.12.80. Приказ Минвуза УССР № 189 от 28.04.1981 г., номер государственной регистрации 81005X06/, на базе следующих хоздоговорных работ:
"Разработка моделей, методов и алгоритмов оптимизации структур сложных систем по критерию надежности", выполняемой по Постановлению ЦК КПСС и СМ СССР совместно с ИК АН УССР /номер государственной регистрации 78035429/.
"Разработка прикладного математического и системного обеспечения САПР динамических систем по критерию надежности", выполняемой совместно с ИК АН УССР им.В.М.Глушкова в рамках ЦК НТП ГКНТ СССР 0.Ц.027 "САПР" и "АСНИ" /задание 03.22, номер государственной регистрации 81003080/ и в рамках ЦК НТП Минвуза УССР М072 "Автоматизация проектирования сложных динамических систем" /"АПРОДОС"/.
Основной целью работы является следующее.
Разработка и исследование методов и алгоритмов поиска решений /точных и приближенных/двухуровневых и монотонных задач дискретного программирования и их применение для решения задач оптимизации надежности непоследовательных систем с явно заданными множествами возможных вариантов подсистем и задач оптимального резервирования с использованием в подсистемах разнотипных резервных элементов.
Реализация на ЭВМ алгоритмов решения задач оптимизации надежности непоследовательных систем и создание программного комплекса, позволяющего повысить эффективность работы алгоритмов в рамках диалоговой системы автоматизированного проектирования структур сложных технических систем по критерию надежности.
Научная новизна работы заключается в следующем.
Разработаны и исследованы методы поиска точных и приближенных решений двухуровневых и монотонных задач дискретного программирования в общей постановке.
На основе методов решения рассматриваемых классов задач дискретного программирования разработаны и обоснованы новые алгоритмы решения задач оптимизации надежности непоследовательных систем с явно заданными множествами возможных вариантов реализаций подсистем и задач оптимального резервирования с использованием в подсистемах разнотипных резервных элементов.
Исследованы вопросы сведения задачи оптимизации надежности непоследовательной системы к задачам дискретного сепарабельного программирования. Для высоконадежных непоследовательных систем при таком сведении получены оценки погрешности значений функции надежности.
Разработанные алгоритмы решения задач оптимизации надежности непоследовательных систем реализованы на ЭВМ в виде программного комплекса, который включен в состав математического обеспечения диалоговой системы автоматизированного проектирования структур сложных систем по критерию надежности.
Практическая ценность работы состоит в следующем.
Разработанные методы и алгоритмы могут быть использованы при решении задач дискретной оптимизации, возникающих в проектировании, планировании и т.п., а также использоваться при решении специальных задач дискретного программирования.
Результаты, полученные в диссертационной работе, внедрены в производство.
Система автоматизированного проектирования, в состав математического обеспечения которой входят разработанные модели и алгоритмы оптимизации надежности непоследовательных систем, внедрена в производство в одном научно-производственном объединении Министерства авиационной промышленности СССР и используется для решения практических задач оптимального проектирования структур сложных систем. Получен экономический эффект.
Диссертационная работа состоит из 4-х глав, заключения, списка основной использованной литературы и двух приложений.
В первой главе приведен обзор литературы по моделям и методам решения задач нелинейного дискретного программирования /§ I.I/, по постановкам задач оптимизации надежности сложных систем и алгоритмам их решения /§ 1.2/. Обосновывается необходимость исследования двухуровневых задач дискретного программирования.
Во второй главе приводится описание общей алгоритмической схемы решения задач дискретной оптимизации, основанной на методологии последовательного анализа и отсеивания вариантов, в рамках которой описываются предлагаемые методы решения двухуровневых и монотонных задач дискретного программирования.
В § 2.1 описывается схема решения задач дискретной оптимизации. Вводится определение подварианта, родового множества, допуска для множества подвариантов. Рассмотрены операторы анализа и отсеивания множеств подвариантов по допускам, конструирования агрегированной задачи. Сформулированы принцип оптимальности и критерии оптимальности.
Схема может быть эффективно реализована при решении задач дискретной оптимизации, для которых удается построить процедуры вычисления допусков и реализовать операторы анализа подвариантов по допускам.
В § 2.2 предлагается и исследуется метод решения задачи двухуровневого дискретного программирования в общей постановке, базирующийся на общей схеме. Вводятся допуски первого и второго уровней, конкретизируются операторы схемы и агрегированная задача. Для двухуровневой задачи с монотонно неубывающей целевой функцией и сепарабельными ограничениями доказаны теоремы, в которых определяются способы вычисления допусков первого и второго уровней.
В § 2.3 на основе схемы предлагается метод решения задачи дискретного монотонного программирования.
В третьей главе рассматривается и исследуется постановка задачи оптимизации надежности непоследовательной системы и предлагаются решающие алгоритмы, базирующиеся на разработанных в главе 2 методах.
В § 3.1 рассматривается и исследуется постановка общей задачи оптимизации надежности непоследовательной системы.
В § 3.2 предлагается алгоритм решения задачи оптимизации надежности непоследовательной системы с явно заданными множествами возможных вариантов подсистем. Приводится пример синтеза варианта структуры непоследовательной системы.
В § 3.3 приводится постановка и предлагается алгоритм решения задачи оптимального резервирования непоследовательной системы с использованием в подсистемах разнотипных резервных элементов, который основывается на методе решения двухуровневых задач дискретной оптимизации. Определяются способы вычисления допусков первого и второго уровня, описываются процедуры уточнения допусков, являющиеся основой алгоритма.
В § 3.4 предлагаются способы сведения /сепарализации/ задачи оптимизации надежности непоследовательной системы к задачам дискретного сепарабельного программирования путем введения дополнительных переменных и ограничений. Для высоконадежных непоследовательных систем при таком сведении получены оценки погрешности значений функции надежности.
В § 4.1 главы 4 приводится краткое описание программного обеспечения по формированию моделей и алгоритмов решения задач оптимизации надежности, предложенных в главе 3.
В § 4.2. описывается диалоговая система автоматизированного проектирования структур сложных систем по критерию надежности, в состав математического обеспечения которой входят разработанные модели и алгоритмы оптимизации надежности. Рассматриваются возможности системы, описывается ее функциональный состав, приводится фрагмент сценария работы. Основное внимание при описании диалоговой системы уделено проблемной части,ее математическому обеспече - 12 нию, в разработке и реализации на ЭВМ которого автор принимал непосредственное участие.
В § 4.3 приводятся и обсуждаются результаты вычислительных экспериментов на ЭВМ по решению задач оптимизации надежности непоследовательных систем с помощью разработанных алгоритмов.
В заключении отмечаются основные результаты работы.
В приложении I приводится пример решения задачи синтеза варианта структуры непоследовательной системы с использованием разнотипного резервирования. В приложении 2 дано описание программной реализации алгоритмов оптимизации надежности и описание основных программных модулей математического обеспечения диалоговой системы, приводятся тексты графов тем диалога и основных программ, материалы внедрения.
Основные результаты диссертационной работы докладывались и обсуждались на П Всесоюзном совещании "Автоматизация проектирования и конструирования" /Ленинград, 1983/, на УІ Всесоюзной конференции "Проблемы теоретической кибернетики" /Саратов, 1983/, IX Всесоюзном совещании "Проблемы управления, 83" /Ереван, 1983/, на I Крымской весенней школе по дискретной оптимизации /Судак, 1982/, на П Всесоюзной школе "Дискретная оптимизация и ее приложения, в том числе экономические" /Кишинев, 1983/, на семинаре "Стандартизация пакетов прикладных программ оптимизации" /Йошкар-Ола, 1982/, на Ш-ей республиканской конференции "Вычислительная математика в современном научно-техническом прогрессе" /Канев, 1982/, на республиканских семинарах Научного совета АН УССР по проблеме "Кибернетика" в ЙК АН УССР им.В.М.Глушкова и Киевском госуниверситете им.Т.Г.Шевченко.
По теме диссертации опубликовано 7 печатных работ.
Методы решения задач оптимального резервирования при проектировании сложных систем
Высокий уровень надежности - одно из основных требований при проектировании сложных систем [7, 42, 80 ] . Одним из методов повышения надежности сложных систем, широко применяемым в практике проектирования, является резервирование /нагруженное резервирование/ [ 7 J . Однако, повышение надежности систем за счет резервирования связано с увеличением значений их технико-экономических параметров таких как вес, стоимость, габариты и т.п. Поэтому возникает задача оптимального резервирования, которая заключается в определении оптимального /максимального/ по надежности варианта структуры системы при заданных ограничениях на технико-экономические характеристики.
Интенсивные исследования и разработки моделей и методов оптимизации надежности сложных систем ведутся в течение трех последних десятилетий. Задача оптимального резервирования, понимаемая как задача оптимального распределения ресурсов, была четко сформулирована в 1956 г. в работе [ібО] , одна из первых отечественных работ [ 90 ] появилась в 1959 году.
Существенный вклад в разработку теоретических и прикладных вопросов оптимизации надежности сложных систем внесли работы советских ученых О.Г.Алексеева, Б.В.Гнеденко, А.Д.Епифанова, О.А.За-горуйко, Б.А.Козлова, Н.Н.Кулакова, А.Л.Райкина, Х.Л.Смолицкого, А.Д.Соловьева, И.А.Ушакова, Н.А.Шишонка и других, а также зарубежных авторов К.Аггарвала, Р.Барлоу, Р.Беллмана, Л.Бодина, Г.Брея, Дж.Кеттеля, Ф.Прошана, і.Тиллмана, К.Хванга, Дж.Эзари и других.
Основные результаты исследований освещены и подытожены в монографиях [7,25,31,42,58,64,67,80,84,95,110,150 ] и обзорах [II,12,83,93,154,159,172,176 ] . Важный этап в развитии прикладных исследований теории оптимизации надежности связан с разработкой диалоговых систем автоматизированного проектирования структур сложных систем по критерию надежности [ 16 ] и по критерию эффективности /без учета ограничений на ресурсы/ [ 127 ] .
На основании анализа литературы по проблеме оптимизации надежности можно отметить, что большинство работ посвящено оптимизации надежности последовательных систем [7 J , т.е. таких систем, в которых отказ любой подсистемы вызывает отказ всей системы, причем отказы подсистем происходят независимо друг от друга.
Наиболее часто в работах рассматривается математическая модель задачи оптимизации надежности последовательных систем в следующей постановке [7, 95 J : максимизировать при ограничениях n где 11 і (І 17П.)— конечные множества вариантов Si і и подсистемы, которые определяются типами элементов, используемых для построения вариантов подсистем, кратностями их резервирования и способом соединения /при резервировании могут учитываться один тип отказа - "обрыв", либо два типа отказов - "обрыв" и "короткое замыкание"/; pj Ф/), Qn (Sj) - соответственно надежность и С -я технико-экономическая характеристика варианта Sj ; r(S) и СІ (S) - соответственно надежность и расход -го ресурса при выборе варианта S системы; л1 U 11 ї - множество возможных ва-риантов реализации системы; б с Сі=19яі)- заданное ограничение по С -му ресурсу на всю систему в целом. Обычно вместо /І.2.І/ рассматривается сепарабельная функция r(S) = 2-, rj j гДе FCS) - & P(S)у jfy (Sj) = &fpj(sj) (j ЬН)ч полученная путем логарифмического преобразования.
При оптимизации высоконадежных последовательных систем [95 ] /когда ненадежности Qf ($/)=1 Pj(Sj) (J = -) подсистем удовлетворяют условию д.- (Sj) . 1 /П, / максимизация критерия /I.2.I/ при ограничениях /1.2.2/, /1.2.3/ заменяется минимизацией функции ненадежности системы [7,52,80,95,II4]:US) = Q.(Sj)
при ограничениях /1.2.2/, /1.2.3/. В частности, если функции Q i($) (i 1ylU) линейные и варианты 5!/ є fir (і=ірг) подсистем строятся из элементов одного типа, то получаем "классическую" задачу оптимального резервирования [7 ] . Рассмотренные выше модели задач оптимизации надежности последовательных систем сводятся к задачам дискретного сепарабельного программирования [ 60 J .
Для решения задачи /I.2.I/ - /1.2.3/ были предложены различные алгоритмы, ориентированные на поиск как точных, так и приближенных решений, которые основываются на методах, изложенных в 1.1. Так, в [і, 7, 112, 125] рассмотрены способы нахождения решений задачи /І.2.І/ - /1.2.3/, основанные на методе динамического программирования, в [7, 80, 95 используется метод неопределенных множителей Лагранжа, в [7, 95 ] приводятся вычислительные алгоритмы, которые опираются на метод наискорейшего спуска, в [б, 20 ] рассмотрены возможности сведения задач оптимального резервирования к целочисленным задачам линейного программирования, а в LI58 J - к задачам булевого программирования.
В последнее десятилетие интенсивно разрабатываются алгоритмы, базирующиеся на методе ветвей и границ [157, 163 ] , целочисленном методе Гомори [174 ] , модификациях метода динамического программирования и метода ветвей и границ [2, 4 J , комбинированном методе, основанном на динамическом программировании и множителях Лагранжа [3 J, последовательностных схемах [38 J , декомпозиционном подходе [іб, 71 ] , эвристических методах [95, 154, 161 ]
Метод решения двухуровневой задачи дискретного программирования
В данном параграфе в рамках общей схемы решения задач дискретной оптимизации предлагается и исследуется метод решения двухуровневой задачи дискретного программирования в следующей постановке /Задача В / максимизировать F({ ( ), -, /j (Xj), , /л(хп)) /2.2.1/ при ограничениях QL (р (X,), ,ftj(Xj), -,$tn(Zn))i (L=Vh), /2-2.2/ xjeXj Q=iTn) . /2.2.3/
Здесь A/ ={ Xf? Xj 9 ", Cj J (l = i,fl) - конечные множества подвариантов /элементов первого, верхнего,уровня/ OCj , которые конструируются из элементов "базовых" множеств /элементов второ-го, нижнего, уровня/ X/ ІХІ1 ,"\Xj » Xje І (Ґ=1 nj в частности, множества J П Xj Q n) /j о С (С= ) заданные числа; н и йц - действительные функции дискретного аргумента; F и Grt - действительные функции, определенные соответственно на множествах области изменения функций fj у Qn на множестве
На актуальность, практические приложения и трудности решения задачи /2.2.1/ - /2.2.3/ указывалось в обзоре / 1.2/.
Необходимо определить такие подварианты Х-і є Xj (J = 1,n), т.е. указать элементы jeh базовых множеств Xj , используемые для их построения, чтобы вариант (Xf, ",xJ," ,Xn) удовлетворял условиям /2.2.2/, /2.2.3/ и максимизировал функцию г
Вариант который удовлетворяет уеловиям /2.2.2/, /2.2.3/, будем называть допустимым. Подварианты #i , образующие допустимые варианты, будем называть допустимыми. Множество допустимых вариантов обозначим D , а множества допустимых под-вариантов - Dj (І=19ІІ). Допустимый вариант ( %1, ", XJ, " , п\ максимизирующий функцию /2.2.1/, назовем оптимальным.
Метод решения задачи /2.2.1/ - /2.2.3/ базируется на общей схеме, рассмотренной в 2.1, и заключается в сокращении размерности модели за счет отсева элементов на каждом уровне с одновременной ее оптимизацией. Одним из главных вопросов в методе является вопрос определения допусков для элементов каждого уровня и способов их вычисления.
Пусть Rf (jjf) и Ri (З-j) соответственно родовое и до пустимое родовое множество первого уровня подварианта ОС і Xj . Выберем во множестве PCX) в качестве семейства мно жеств подвариантов / / первого уровня множество Х-П X; /т.е. положим PiJ - Xj (І-1,И) /. При таком задании «А вы полняготся условия
Пусть dii - допуск первого уровня для множества подвариан тов Xj относительно множества D по С -му ограничению ви да /2.2.2/, то есть для всякого подварианта %ч At такого, что Я-LjC -j 1} следует, что множество R1 (ocj) = 0. Анализ множества подвариантов Xj (1=13Л) по допускам dii ( t = 1,trL j. = 1,n ) для каждого из ограничений /2.2.2/ осуществляется на основе следующей подсистемы ограничений: %L}(xj) d-Cj, (L = i7ri), /2.2.4/ Xje Xj . /2.2.5/ Обозначим через систему допусков пер вого уровня, где множество допусков Q1 (Xi) = {d[iL=1tto j
Вычисление и улучшение системы допусков Q1 (X) осуществляет ся оператором аппроксимации CZ , определенным на множестве X /назовем его оператором аппроксимации первого уровня и обозначим Очевидно, что чем лучше в указанном выше смысле /см. 2.1/ определена система допусков 66/ (X) , тем точнее описываются множества
Используя подсистемы ограничений /2.2.4/, /2.2.5/, определим допуски второго уровня, на основании которых исключаются элементы из множеств Xf ( =1,17-/ ,JГ—1,ҐІ) . Сужение множеств элементов
At (ґ=1, у;/-1 п) второго уровня приводит к сужению множеств подвариантов Xj (J =1, ) первого уровня. Построение системы допусков второго уровня рассмотрим на примере 1-й подсистемы ограничений вида /2.2.4/, /2.2.5/.
Алгоритм решения задачи оптимизации надежности непоследовательной системы с явно заданными множествами возможных вариантов подсистем. Пример синтеза системы
Если на практике то максимальный вариант во множестве проверяем на оптимальность по критерию оптимальности I. Если критерий оптимальности I выполняется, то получен оптимальный вариант системы; заканчиваем выполнение алгоритма. В противном случае на множестве 12 прямым перебором вариантов решается агрегированная задача вида /2.3.5/ - /2.3.7/. Если агрегированная задача не имеет решения, то переходим к п.2.2. В противном случае вариант 5 , максимальный по надежности среди допустимых вариантов задачи, проверяем на оптимальность по критериям оптимальности 2,3. Если критерии оптимальности не выполняются, то S - приближенный вариант реализации системы. Если надежность системы на варианте S является удовлетворительной, то заканчиваем выполнение алгоритма. В противном случае продолжаем поиск оптимального варианта: полагаем Pmin = P(S ) и переходим к шагу 6.
Если 12 0 и М А/ /т.е. число вариантов во множестве велико для решения задачи прямым перебором ва риантов/, то максимальный вариант во множестве проверяем на оптимальность по критерию оптимальности I. Если вариант оптимален, то заканчиваем вычисления. В противном случае переходим к шагу 4.
Пояснения к алгоритму: І/ параметр /\/ - число вариантов множества,среди которых путем прямого перебора отыскивается максимальный вариант для проверки на оптимальность, в каждом случае задается, исходя из практических соображений, например, времени, выделенного для решения задачи, быстродействия ЭВМ, необходимости поиска оптимального варианта и т.п.; 2/ если на шаге 4 возникает ситуация, в которой выполняется условие Нпасс # C-g и /к /v , то решение агрегированной задачи в п.2.3 шага 2 прямым перебором вариантов связано с большими вычислительными трудностями. Вместе с тем, рассматриваемый случай означает, что множество содержит большое число эквивалентных /близких по надежности и ограничениям/ вариантов. Поэтому представляется целесообразным перейти на поиск субоптимальных / - приближенных, - оптимальных/ вариантов [24J , удовлетворяющих системе неравенств
Определим надежность и технико-экономические характеристики варианта sJKe/{n) ,/ и подсистемы через показатели входящих в /7 здесь декартово произведение. него разнотипных элементов. Рассмотрим поэлементное резервирование в подсистемах в случае отказа элементов типа "обрыв" и предположим, что технико-экономические характеристики вариантов подсистем аддитивно выражаются через характеристики элементов.
Тогда надежность варианта SjKejCrn Длины rJ. реализации -й подсистемы определяется по формуле а его технико-экономические характеристики равны где Pj(U-iKi?) и 9ij ujKb ) соответственно надежность и С -я технико-экономическая характеристика элемента UjnJ kJ-vo типа; Ajtip кратность резервирования элемента Щ Нр
Задача /3.I.I/ - /3.1.3/ при построении вариантов подсистем из разнотипных резервных элементов представляет собой двухуровневую задачу дискретного монотонного программирования, которая с учетом введенных обозначений имеет вид /задача R /: максимизировать
Согласно методу конкретизируем операторы анализа ULj и (Х% , операторы конструирования и отсеивания вариантов Зъ и » процедуры аппроксимации и определим способы вычис ления допусков.
Семейство множеств подвариантов rii перво го уровня выберем совпадающим с множеством SI = П Slf /т.е. положим P-jj =_і2І (J = 1,n)/. Допуски первого уровня по технико-экономическим характеристикам для множества возможных вариантов подсистемы Si І (J-Ь -) определяются согласно теореме 2.4 следующим образом:
Диалоговая система автоматизированного проектирования структур сложных систем по критерию надежности
Для оптимизации моделей с использованием в качестве критериев линейных приближений разработан комплекс программ с управляющей программой UN PR. Пересчет коэффициентов в сепарабельном критерии /3.4.3/ осуществляется в подпрограмме FORМI//?, решение задачи дискретного сепарабельного программирования осуществляется алгоритмом ALGMW , реализующим метод
Для решения задач оптимизации надежности с использованием квадратичных приближений разработан модифицированный вариант алгоритма ALGMAXt комплекс программ с основным модулем NhLGMN, Процедуры вычисления и уточнения допусков, реализованные модулем /VOTSEVi являются модификацией процедур 1// и 1 [23 J , учитывают специфику модели и позволяют усиливать отсев заведомо бесперспективных значений дополнительных переменных во множествах их изменения. Формирование математической модели задачи /3.1.1/, /3.1.2/, /3.4.14/, /3.4.15/ осуществляется с помощью подпрограммFORMVRn BLOK, Решающий алгоритм и программы формирования модели объединены управляющей программой К VPR IB В ней осуществляется пересчет границ информационных массивов, ведение диалога по выбору оптимизационной модели и изменению параметров алгоритмов при решении задач.
При реализации алгоритмов использовался принцип модульности, в соответствии с которым в различных алгоритмах использованы общие программные единицы, имеющие независимое функциональное назначение .
Все программные модули хранятся в двух библиотеках: в библиотеке текстов /в виде программ, написанных на соответствующих языках программирования/ и в библиотеке загрузочных модулей, которые организованы на пакете дисков. Подобная организация позволяет,как уже отмечалось, использовать одни и те же модули в различных программных комплексах для формирования алгоритмов, а также оперативно корректировать имеющиеся в них программы, дополнять библиотеку программ новыми модулями.
Реализованные алгоритмы, программы формирования моделей и управляющие программы стали основой для создания математического обеспечения диалоговой системы автоматизированного проектирования структур сложных систем по критерию надежности, которая описывается в следующем параграфе.
Более подробное описание программ, реализующих алгоритмы решения задач оптимизации надежности, описание основных функциональных частей, структуры входных и выходных данных приведены в приложении 2. В приложении 2 приводятся также тексты основных программных модулей.
В настоящем параграфе описывается диалоговая система /ДС/ автоматизированного проектирования структур сложных систем по критерию надежности с учетом ограничений на технико-экономические характеристики /вес, стоимость и т.п./. I. Назначение и возможности системы. Проектировщику при работе с системой предоставляются следующие возможности.
1. Выбирать тип модели проектируемого объекта и его параметры. Проектируемый объект может рассматриваться как последовательная или непоследовательная система. Варианты подсистем могут быть построены на основе однотипных или разнотипных элементов, с резервированием или без резервирования.
2. Автоматически сводить задачу оптимизации структуры объекта к одной из канонических моделей задач дискретной оптимизации. Для решения задач оптимизации надежности последовательных систем в математическое обеспечение включены алгоритмы [22,70,71] При оптимизации непоследовательных систем используются алгоритмы, изложенные в 3-й главе работы. Решение задач может вестись как в автоматическом, так и в интерактивном режиме. Для обеспечения работы алгоритмов в интерактивном режиме разработан диалог.
3. Выдавать на устройства вывода /дисплей, АЦПУ/ результат решения задачи в терминах проектируемого объекта /имен подсистем и имен типов элементов/, схем соединения элементов с указанием типов элементов и кратностей их резервирования, значения надежности варианта структуры объекта и надежностей вариантов подсистем.
4. Формировать в интерактивном режиме информацию по проектируемому объекту в файлах системы. Информационным наполнением файлов являются значения технико-экономических характеристик элементов, значения кратностей резервирования элементов различных типов, данные о дереве неотказов объекта /для непоследовательных систем/, значения ограничений по ресурсам на проектируемую систему в целом, имена ресурсов, подсистем, типов элементов. На каждом из этапов проектирования имеется возможность корректировать информацию, для чего разработана подсистема коррекции данных /ІЩ/.
5. Осуществлять оптимизацию моделей с исходными и текущими /изменяемыми/ данными. Предусмотрены возможности переходов от одной оптимизационной модели к другой, например, от последовательной к непоследовательной и обратно.
