автореферат диссертации по электротехнике, 05.09.05, диссертация на тему:Комбинаторные методы исследования минимальных структур математических моделей электрических цепей и систем

Введение.

Глава 1. Минимальные структуры матроидных моделей электрических цепей и систем.

1. Матроиды, субмодулярные функции, дистрибутивные решетки - комбинаторный аппарат описания минимальных структур математических моделей электрических цепей и систем.

2. Критерий минимальности смешанной системы уравнений электрической цепи.

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

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

5. Выводы.

Глава 2. Дистрибутивная решетка минимальных разрезов графов электрических цепей и систем.

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

2. Анализ теоретико-решетчатых свойств множества минимальных разрезов графа электрической цепи.

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

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

5. Выводы.

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

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

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

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

4. Применение разработанных методов для определения разрезов графов схем электроэнергетических систем.

5. Выводы.

Глава 4. Разработка комбинаторного алгоритма определения показателей структурной надежности электрических цепей и систем.

1. Определение сечения электрической системы (цепи).

2. Разработка классификации сечений электрических систем (цепей).

3. Выбор приближений для оценки показателей надежности электрических систем (цепей).

4. Разработка классификации одно-, двух- и трехэлементных сечений электрических систем (цепей).

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

6. Разработка комбинаторного алгоритма формирования классов одно-, двух- и трехэлементных сечений электрических систем (цепей).

7. Анализ и перечисление состояний отказа по графу электрической системы (цепи).

8. Выводы.

Глава 5. Разработка комбинаторного алгоритма диагностики ^^ структуры электрической цепи.

1. Разработка комбинаторной модели задачи диагностики структуры электрической цепи.

2. Разработка комбинаторного алгоритма решения задачи диагностики структуры электрической цепи.

3. Выводы.

Выводы.

Методика анализа электрических цепей начала развиваться в XIX веке в связи с практическими потребностями электротехники.

Г. Р. Кирхгоф [214] предложил при описании и исследовании электрических цепей использовать специальную комбинаторную конструкцию - граф. Им же была разработана теория деревьев применительно к исследованию электрических цепей. Первый и второй законы Кирхгофа связаны с комбинаторными конструкциями разреза и цикла. Предложенные для расчета определителей топологические формулы [214, 220] основывались на экстремальных комбинаторных конфигурациях - деревьях и кодеревьях (дополнениях деревьев) графа. При этом расчет заключается в перечислении подобных конструкций, т.е. носит комбинаторный характер.

Число деревьев графа цепи (в случае когда все вершины соединены между собой, т.е. граф полный) п11~2 [197], где п - число вершин графа, экспоненциально растет с ростом п; и при п = 10 достигао ет 10 . Отыскание и хранение такого числа деревьев проблематично даже для мощных ЭВМ [123]. Даже при впечатляющем росте производительности компьютеров, эта фраза не устарела и в 2002 г. Графы схем электрических цепей обычно разрежены (число ветвей меньше числа ветвей полного графа п(п -1)/2, где п - число вершин). Число деревьев полного графа представляет верхнюю оценку числа деревьев графа с п вершинами. Для неполных графов число деревьев (найдено в неявной форме Кирхгофом [180]) меньше, но тоже весьма велико. В таблице В.1 приводятся данные о числе деревьев для схем замещения электрических цепей различной сложности [188].

Таблица B.l.

Число узлов ветвей деревьев узлов ветвей деревьев

10 22 36 768 14 29 1 029 504

12 26 294 144 16 30 882 432

13 27 441 216 22 32 1 398 837

14 28 588 288

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

Стремление довести решение задачи до аналитических выражений (для выяснения общих свойств решаемой задачи помимо получения численных результатов) при вычислении определителя матрицы и ее алгебраических дополнений неминуемо потребует обработки всего множества деревьев. Упрощения обработки растущего количества объектов можно достичь лишь за счет одновременной обработки некоторых объектов, например, получения вложенных выражений схемных символьных функций. Таким образом, нужна некоторая классификация получаемых объектов для одновременной их обработки. Целью проводимых преобразований является получение минимальных или близких к минимальным моделей. Важность получения именно минимальных моделей следует, например, из сравнения количества операций (таблица В.2), используемых в различных выражениях для определителей [164].

Таблица В.2

Схема (8 узлов) Вложенные выражения Без свертки

Число "х" Число "+" Число "-" Число "х" тт " 1 55 " " Число + , test 1 15 559 26 381 686 10 080 000 1 439 999 test 2 18 164 44 442 63 5 173 245 739 034 test 3 15 775 27 480 595 10 920 000 1 559 999 test 4 20 537 33 942 773 11 289 600 1 612 799

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

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

Применение средств вычислительной техники существенно изменило положение, сделав возможным решать задачи большей размерности за счет проведения большего числа операций. При этом усовершенствование алгоритма может давать существенный выигрыш или во времени работы алгоритма, или в используемой памяти. Улучшение алгоритма основано на использовании свойств и закономерностей, не учтенных или не известных ранее. К настоящему времени разработано значительное количество комбинаторных методов и эффективных алгоритмов [101, 103, 9, 127, 112].

Широкое развитие методов (анализа и синтеза) исследования электрических цепей (систем), использующих самые различные комбинаторные свойства схем электрических цепей, в частности, специфику разреженности, началось лишь после 1950 г. В это время, с одной стороны, потребности практики поставили задачу расчета более сложных цепей, а с другой стороны, расчет стали производить с помощью электрических цифровых машин и начались поиски простейших способов программирования таких расчетов [11]. Таким образом, при разработке оптимальных алгоритмов в электротехнике возникла необходимость совершенствования классических методов анализа и синтеза цепей, и разработки новых, более приспособленных к нуждам автоматизации вычислений с помощью ЭВМ. Дело в том, что начали проявляться комбинаторные аспекты, которые раньше по указанным выше причинам были не существенны, и на которые обычно не обращали внимания. Проводимые исследования при формировании математических моделей электрических цепей и систем начали носить, в частности, и комбинаторный характер [148, 143]. (Многие важные открытия в теории цепей имеют главным образом теоретико-графовую природу, и усилия, ведущие к таким открытиям, приводят к значительному вкладу в теорию графов [143], являющуюся частью единой теории дискретных множеств - комбинаторного анализа [140]).

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

В. Фойснером [203, 204] предложено проводить разложение определителей исходной схемы и производных от нее схем, что позволяет представить определитель с вынесенными за скобки общими множителями. Указанное, в частности, использует деление схемы на подсхемы, т.е. требует поиска и использования минимальных комбинаторных конструкций - разрезов. К. Т. Wang [241] предложил новый метод расчета токов и напряжений в электрических цепях, основанный на применении алгебры, в которой а + а = 0 и а»а = 0. Оба метода были направлены на эффективное вычисление определителей разреженных матриц (порождение только отличных от нуля слагаемых приводило к усложнению, связанному с отказом от полного перебора), и оба метода, предвосхитив свое время, широкого распространения не получили (были формальны и ощутимых преимуществ на исследуемых классах цепей не давали). Первый метод исходил из геометрических представлений графа схемы, второй - из формальных алгебраических представлений. Однако во время появления ЭВМ методы оказались востребованными, поскольку позволяли уменьшить объем вычислений и моделировали «логику работы компьютера»

Представление системы линейных уравнений графом [219, 198] позволяет наглядно представить процесс решения, и соответственно выбрать наименее трудоемкий. При этом направленность перебора не скрывается за формальными алгебраическими действиями. Можно совместить граф схемы электрической цепи с графическим изображением системы - в этом случае отпадает необходимость в формальном составлении системы уравнений. Таким образом, удалось снизить до приемлемого уровня трудоемкость расчета более сложных электрических цепей. В этом направлении следует отметить работы [119, 135, 2, 149, 153, 80, 5, 155, 126, 117]. При помощи этих методов человеку удобно прослеживать и выявлять закономерности исследуемых объектов, планировать стратегию перебора и разрабатывать алгоритм. Эти методы удобны при обучении [81, 154]. Однако удобство операций перебора для человека и для компьютера - вещи разные. Дальнейшее усложнение электрических схем и развитие компьютерной техники привели к развитию алгебраических методов. В основу метода "структурных чисел" [11] были положены соответствия между преобразованиями цепей и алгебраическими преобразованиями со структурными числами, дающими информацию о деревьях и дополнениях деревьев электрической цепи. Метод обобщенных структурных чисел (которые образуются частично упорядоченным множеством элементов, состоящих из цифровых индексов, а в некоторых случаях и буквенного кода) [157] "дает возможность формализовать расчет линейных систем, уменьшить количество символов, используемых при промежуточных операциях по составлению расчетных формул, и отличается строгой последовательностью операций над цифрами, что значительно уменьшает объем выкладок при расчете сложных схем и делает возможным решение задач на ЦВМ как в численном, так и в общем виде". Операции алгебры структурно-режимных схем [129] "позволяют решить задачи эквивалентного преобразования без составления уравнений, отличаются от известных алгебр полнотой системы операций и высокой степенью формализации." Идеи, заложенные В. Фойснером, были развиты и программно реализован на современном уровне В. В. Филаретовым [163]. Попытки эффективно организовать перебор все более увеличивающихся по объему множеств приводят к все большему усложнению и формализации этого процесса, усложнению результата, и, как следствие, потере наглядности. Например, формула, в текстовом формате занимающая полную дискету, а то и не одну (более 1000 стр. текста). В связи с этим первоочередной становится задача получения не просто решения, а лучшего (минимального) решения. Результаты, полученные различными программами, сравниваются именно по этому критерию [163].

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

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

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

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

Применение комбинаторных методов в теории цепей и систем восходит к основополагающим работам Г.Р.Кирхгофа и Д.К.Максвелла. В дальнейшем комбинаторные методы использовали в своих исследованиях В.И.Анисимов, Т.С.Беллерт, Г.Возняцки, Н.Г.Максимович, С.Мэзон, А.Г.Остапенко, М.Б.Рид, М.Свами, С.Сешу, В.П.Сигорский, А.М.Сучилин, Ю.В.Тимкин, Я.К.Трохи-менко, К.Тхуласираман, В.Фойснер, П.Ф.Хасанов, К.Е.Шеннон, M.Iri, A.Recski, K.T.Wang и др. авторы.

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

Достижение цели исследования предполагает решение следующих основных задач:

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

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

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

Научная новизна основных результатов диссертационной работы.

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

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

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

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

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

6. Сформулирована задача диагностики структуры электрической цепи (системы) и разработана ее формальная математическая модель в форме оптимизационной комбинаторной задачи.

5. Разработаны и исследованы алгоритмы:

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

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

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

- формирования классов одно-, двух- и трехэлементных сечений электрической системы (цепи);

- решения задачи диагностики структуры электрической цепи.

Конкретное личное участие автора в получении результатов, изложенных в диссертации.

Все результаты диссертационной работы получены лично автором диссертации. П. А. Бутырину, в соавторстве с которым опубликовано 9 работ, принадлежат идея и поддержка проведения исследований, связанных с применением средств и методов комбинаторной математики в теории электрических цепей и систем.

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

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

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

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

- при декомпозиции сложных электрических цепей и систем;

- при решении задач диагностики электрических цепей;

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

Реализация результатов работы. Работа выполнялась в соответствии с планом научно-исследовательских работ по теме № ГР 01830001716 (инв. № отчетов во ВНТИЦ: 02840069712 [131], 02860043621 [132]). Работа поддержана грантами РФФИГУрал" 01-0196401 и губернаторского конкурса Челябинской области р2001урчел-01-04.

Разработанные в диссертационной работе методы и алгоритмы оценки надежности сложных цепей и систем реализованы в виде комплекса программ на ЭВМ, зарегистрированы в РОСПАТЕНТе (свидетельства об официальной регистрации программ для ЭВМ № 2002610643 [145], 2002611217 [144]), включены в Информационно-библиотечный фонд Российской Федерации (№ ОФАП - 2023; № госрегистрации - 50200200340) [75], и внедрены в практику проектирования Челябинского филиала ВНИПИ «Тяжпромэлектропроект», а также на предприятии ЗАО «Фосфохим» (г. Тольятти), что подтверждается соответствующими актами. Результаты диссертационной работы также использовались в учебном процессе Южно-Уральского государственного университета [72] и Тольяттинского государственного университета.

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на:

• Всесоюзном семинаре по проблеме "Автоматизация проектирования электротехнических устройств и систем" (Истра, 1984);

• IV Всесоюзной школе-семинаре молодых ученых и специалистов "Проблемы совершенствования устройств и методов приема, передачи и обработки информации" (Звенигород, 1985);

• научной конференции Московского энергетического института (Москва, 1985);

• VI Московской городской конференции ученых и специалистов по повышению надежности, экономичности и мощности энергетического, электротехнического и радиоэлектронного оборудования (Москва, 1985);

• III Международном симпозиуме по теоретической электротехнике (Москва, МЭИ, 1985) [23];

• Всесоюзном семинаре "Методы синтеза и планирования развития структур крупномасштабных систем" (Звенигород, ИПУ, 1985 [22],

1990 [76]);

• Всесоюзной научной конференции "Декомпозиция и координация в сложных системах" (Челябинск, ЧПИ, 1986) [25];

• Всесоюзном семинаре "Кибернетика электроэнергетических систем" (Челябинск, ЧПИ, 1990) [56];

• конференции "Надежность и высоконадежность" (Симферополь, Симферопольский государственный университет, 1991);

• второй научно-технической сессии с Международным участием (Болгария, София, военно-транспортное училище Теодора Каб-лешкова, 1991);

• Всероссийской конференции "Математическое программирование и приложения" (Свердловск, Екатеринбург, ИММ УрО РАН, 1991 [62], 1993 [37], 1995 [64], 1997 [61], 1999 [70], 2003 [58]);

• Международной конференции "Распределенные системы: оптимизация и приложения в экономике и науках об окружающей среде" (Екатеринбург, УрО РАН, 2000) [60];

• Международной конференции "Дискретный анализ и исследование операций" (Новосибирск, ИМ СО РАН, 2000) [43];

• Всероссийской научной конференции "Алгоритмический анализ неустойчивых задач" (Екатеринбург, ИММ УрО РАН, УрГУ, 2001) [73];

• VII Международном семинаре "Дискретная математика и ее приложения" (Москва, механико-математический факультет МГУ, 2001) [74];

• Международной конференции "Континуальные логико-алгебраические исчисления и нейроматематика в науке, технике и экономике — КЛИН-2001" (Ульяновск, УлГТУ, 2001) [67];

• Международной школе-семинаре "Дискретная математика и математическая кибернетика" (Ратмино, каф. Математической кибернетики факультета ВМиК МГУ, 2001);

• Российском национальном симпозиуме по энергетике, семинар "Методические вопросы исследования надежности больших систем энергетики" (Казань, КГЭУ, 2001) [19, 53];

• XIII Международной школе-семинаре "Синтез и сложность управляющих систем" (Пенза, МГУ, ПГУ, 2002) [42];

• 5-й Международной конференции «Цифровая обработка сигналов и ее применение» (Москва, ИПУ РАН, 2003)[48];

• на кафедре Теоретических основ электротехники Московского энергетического института, на кафедре Электроэнергетических систем Московского энергетического института и на кафедре Математического анализа (Высшей математики № 2) Южно-Уральского государственного университета (Челябинского государственного технического университета, Челябинского политехнического института) (1984-2002 г.г.).

Настоящая работа является продолжением работ автора [68].

выводы

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

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

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

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

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

6. Получено информационно-компактное аналитическое описание всего множества минимальных разрезов графа электрической цепи (системы) через посредство только подмножества неприводимых разрезов этого графа.

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

8. Получена оценка временной сложности

0{ сг(| V |, \U\) + l\U\+d(VF)\T\ ) арифметических операций для разработанной алгоритмической процедуры, и на основе этой оценки показано, что предлагаемый алгоритм может быть эффективнее всех известных алгоритмов за счет сокращения поиска на графе.

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

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

11. Разработан алгоритм определения множества одно- и двухэлементных разрезов графа электрической цепи (системы), и получена оценка его временной сложности

0{ шах {\Ы\, \М2\] ) арифметических операций.

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

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

0( max {\U\, | М31} ) арифметических операций. На основе этого алгоритма предложен эффективный подход для поиска трехэлементных разрезов, не являющихся минимальными.

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

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

16. Введено понятие сечения электрической системы (цепи), которое дает компактное представление множества состояний отказа системы (цепи).

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

18. Выделено только пятнадцать различных классов сечений во множестве одно-, двух- и трехэлементных сечений электрических систем (цепей).

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

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

21. Сформулирована задача диагностики структуры электрической цепи (системы).

22. Разработана формальная математическая постановка задачи диагностики структуры электрической цепи (системы) как оптимизационной комбинаторной задачи.

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

1. Абраменкова Н. А., Воропай Н. И., Заславская Т. Б. Структурный анализ электроэнергетических систем: В задачах моделирования и синтеза. Новосибирск: Наука, 1990. - 224 с.

2. Абрахаме Дж., Каверли Дж. Анализ электрических цепей методом графов. М.: Мир, 1967. - с.

3. Айгнер М. Комбинаторная теория: Пер. с англ. М.: Мир, 1982. -558 с.

4. Анисимов В. И. Матричный метод анализа схем с многополюсными элементами в смешанном координатном базисе // Известия ВУЗов. Энергетика. 1969. - № 8. - С. 27-33.

5. Анисимов В. И. Топологический расчет электронных схем. JL: Энергия, 1977.-240 с.

6. Анищенко В. А. Выявление ошибок сигнализации положения коммутирующей аппаратуры при помощи ЭВМ // Известия ВУЗов. Энергетика. 1982. - № 9. - С. 24-28.

7. Арзамасцев Д. А., Обоскалов В. П. Расчет показателей структурной надежности энергосистем: Учебное пособие. Свердловск: Изд-во УПИ им. С. М. Кирова, 1986. - 80 с.

8. Асанов М. О., Баранский В. А., Расин В. В. Дискретная математика: графы, матроиды, алгоритмы. Ижевск: НИЦ "Регулярная и хаотическая динамика", 2001. - 288 с.

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

10. Барлоу Р., Прошан Ф. Математическая теория надежности: Пер.с англ. М.: Сов. радио, 1969. - 488 с.

11. Беллерт Т. С., Возняцки Г. Анализ и синтез электрических цепей методом структурных чисел: Пер. с англ. М.: Мир, 1972. - 332 с.

12. Биллинтон Р., Аллан Р. Оценка надежности электроэнергетических систем: Пер. с англ. М.: Энергоатомиздат, 1988. - 288 с.

13. Биркгоф Р. Теория решеток: Пер. с англ. М.: Наука, 1984. -568 с.

14. Богданов В. А., Волков Р. П. Анализ топологии электрической сети по данным телеметрии в автоматизированной системе диспетчерского управления // Электричество. 1975. - № 5. - С. 24-29.

15. Бутырин П. А. Диагностика линейных многополюсников // Изгвестия АН СССР. Энергетика и транспорт. 1983. -№ 6. - С. 81-85.

16. Бутырин П. А., Васьковская Т. А. Восстановление матрицы узловых проводимостей Y по отдельным элементам ее обратной матрицы Z=Y 4 в задачах диагностики // Электричество. 2000. - № 3. -С. 60-62.

17. Бутырин П. А., Васьковская Т. А. Принципы декомпозиции сложных электрических цепей при их диагностике по частям // Электричество. 2001. - № 6. - С. 41-47.

18. Бутырин П. А., Гришкевич А. А. Гейтингова алгебра минимальных разрезов // Проблемы теоретической кибернетики: Тез. докл. VII Всесоюзной конференции. Иркутск, 1985. -Ч. 1. - С. 38-39.

19. Бутырин П. А., Гришкевич А. А. Дистрибутивные решетки в задачах оценки структурной надежности схем электрических систем // Вестник ЮУрГУ (Серия «Энергетика», выпуск 1). 2001 - № 4. -С. 9-14.

20. Бутырин П. А., Гришкевич А. А. Использование дистрибутивных решеток при оценке топологии сетевых систем // Одиннадцатый Всесоюзный семинар по вычислительным сетям: Тез. докл. М., 1986. -Ч. 1.-С. 33-38.

21. Бутырин П. А., Гришкевич А. А. Комбинаторный метод анализа и синтеза структур сложных систем // Методы синтеза и планирования развития структур крупномасштабных систем: Тез. докл. и сообщений III Всесоюзного семинара. М., 1985. - С. 89.

22. Бутырин П. А., Гришкевич А. А. Минимальные структуры математических моделей электрических цепей // III Международный симпозиум по теоретической электротехнике: Тез. докл. М., 1985. - Ч. 2. -С. 23-24.

23. Бутырин П. А., Гришкевич А. А. О множестве минимальных разрезов графа // Декомпозиция и координация в сложных системах: Тез. докл. Всесоюзной конференции. Челябинск, ЧПИ, 1986. - Ч. 1. -С. 56.

24. Бутырин П. А., Гришкевич А. А. Применение дистрибутивных решеток для оценки связности сложных систем // Методы проектирования и анализа вычислительных систем, сетей и сред: Межвузовский сборник. М.: МЭИ, 1985. - № 81. - С. 47-51.

25. Бутырин П. А., Кукайнис О. А., Шестаков А. А. Восстановление разреженной матрицы по соответствующим элементам ее обратной матрицы // Известия АН Латвийской ССР. Сер. Физических и технических наук, 1986.-№ 2.-С. 116-118.

26. Бэндлер У., Салама А. Э. Диагностика неисправностей в аналоговых цепях // ТИИЭР,- 1985.-Т. 73. -№ 8. С. 35-104.

27. Волгин Л. И. Логические основы математической теории надежности. Ульяновск: Изд-во УлГТУ, 1997. - 44 с.

28. Волгин Л. И. Определение сопротивлений и проводимостей двухполюсников логико-алгебраическим методом // Электричество. -1998,-№7.-С. 64-69.

29. Волгин Л. И. Субдистрибутивный и супрадистрибутивный законы логики исчисления иммитансов электрических двухполюсников // Электричество. 2001. - № 2. - С. 66-67.

30. Воропай Н. И. Теория систем для электроэнергетиков: Учебное пособие. Новосибирск: Издательская фирма РАН, 2000. - 273 с.

31. Вычислительные методы выбора оптимальных проектных решений / Михалевич В. С., Шор Н. 3., Галустова Л. А. и др. Киев: Наук. Думка, 1977,- 178 с.

32. Гамм А. 3. Статистические методы оценивания состояний электроэнергетических систем. М.: Наука, 1976. - 220 с.

33. Гловер Ф., Клингман Д. Последние достижения в технике реализации сетевых алгоритмов // Экономические оптимизационные задачибольшой размерности: Труды сов.-амер. семинара (США, 1980). М.: ЦЭМИ, 1983.-С. 180-209.

34. Гретцер Г. Общая теория решеток: Пер. с англ. М.: Мир, 1982. -456 с.

35. Еришкевич А. А. Алгоритм нахождения трехэлементных разрезов графа // Обозрение прикладной и промышленной математики. -2001. Том 8.-Вып. 1.-С. 153-154.

36. Гришкевич А. А. Дважды брауэрова алгебра разрезов графа // Проблемы теоретической кибернетики: Тез. докл. XIII Международной конференции. Ч. I. М.: Изд-во центра прикладных исследований при механико-математическом факультете МГУ, 2002. - С. 49.

37. Гришкевич А. А. Дистрибутивная решетка минимальных разрезов неориентированного графа // Международная конференция "Дискретный анализ и исследование операций": Материалы конференции. -Новосибирск: Изд-во Института математики СО РАН, 2000. С. 95.

38. Гришкевич А. А. Дистрибутивная решетка минимальных разрезов ориентированного графа // Труды XII Байкальской международной конференции (24 июня 1 июля 2001 г.). - Иркутск: Иркутский государственный ун-т, 2001. - Том. 5. - С. 43-48.

39. Гришкевич А. А. Классификация и перечисление состояний отказа при оценке надежности электрических систем // Известия АН. Энергетика. 2001. - № 5. - С. 128-134.

40. Гришкевич А. А. Классификация сечений сложных систем на основе МС-состояний // Обозрение прикладной и промышленной математики. 2000. - Том 7. - Вып. 2. - С. 337.

41. Гришкевич А.А. Кодирование дистрибутивной решетки минимальных разрезов графа // Доклады 5-й Международной конференции «Цифровая обработка сигналов и ее применение». М., 2003. - Том 2. -С. 347-349.

42. Гришкевич А. А. Комбинаторная модель надежности сложной системы // Обозрение прикладной и промышленной математики. -2000. Том 7. - Вып. 2. - С. 337-338.

43. Гришкевич А. А. Комбинаторный алгоритм диагностики структуры электрической цепи // Методы и программы решения оптимизационных задач на графах и сетях: Тез. докл. IV Всесоюзного совещания. Новосибирск: ВЦ СО АН СССР, 1989. - Ч. 1. - С. 48.

44. Гришкевич А. А. Комбинаторный алгоритм формирования классов сечений // Международная Сибирская конференция по исследованию операций. Материалы конференции. Новосибирск: Изд-во Института математики СО РАН, 1998. - С. 74.

45. Гришкевич А. А. Комбинаторный метод оценки надежности сложных сетевых систем // Известия Челябинского научного центра. -2000.-Вып. 4(9).-С. 6-10.http://www.sci.urc.ac.ru:8002/news/20004/20004l2.pdf)

46. Гришкевич А. А. Комбинаторный метод оценки надежности сложных электроэнергетических систем // Методы оптимизации и их приложения: Тез. докл. 10-ой Байкальской школы-семинара. Иркутск: Ротапринт СЭИ СО РАН, 1995. - С. 287-289.

47. Гришкевич А. А. Комбинаторный метод оценки надежности сложных электрических цепей // Электричество. 2000. - № 8. -С. 53-61.

48. Гришкевич А. А. Комбинаторный метод формирования классов сечений // Управление и автоматизация проектирования в электроэнергетических системах: Тез. докл. Всесоюзного семинара "Кибернетика электроэнергетических систем". Челябинск: ЧПИ, 1990. - С. 86.

49. Гришкевич А. А. Комбинаторный подход к определению вероятностных характеристик электрических цепей // Сложные электромагнитные поля и электрические цепи: Межвузовский научный сборник. Уфа: Уфимский авиационный институт, 1985. - № 13. -С. 74-78.

50. Гришкевич А. А. Критерии минимальности смешанного порождающего подмножества // Информационный бюллетень Ассоциации математического программирования № 10. Екатеринбург: УрО РАН, 2003.-С. 88.

51. Гришкевич А. А. Нахождение дистрибутивной решетки по подмножеству неприводимых элементов // Проблемы оптимизации и экономические приложения: Тез. докл. Международной конференции. -Омск: Омский государственный ун-т, 1997. С. 53.

52. Гришкевич А. А. Нахождение минимальных трехэлементных разрезов графа // Распределенные системы: оптимизация и приложения в экономике и науках об окружающей среде. Сборник докладов к Международной конференции. Екатеринбург: УрО РАН, 2000. -С. 123-126.

53. Гришкевич А. А. Об одной задаче диагностики электрической цепи // Российская конференция "Дискретный анализ и исследование операций": Материалы конференции. Новосибирск: Изд-во Института математики СО РАН, 2002. - С. 143.

54. Гришкевич А. А. Пересечение матроидов и задача размещения измерительных приборов // Обозрение прикладной и промышленной математики. 2002. - Том 9. - Вып. 1. - С. 184-185.

55. Гришкевич А. А. Представление дистрибутивной решетки подмножеством неприводимых элементов // Вычислительные технологии 2000: Тез. докл. Новосибирск, Академгородок: ИВТ СО РАН. -http://www.ict.nsc.ru.

56. Гришкевич А. А. Разработка и исследование комбинаторных методов и алгоритмов оценки надежности и диагностики электрических цепей. Автореф. дис. . к-та техн. наук. - М., 1987. - 20 с.

57. Гришкевич А. А. Синтез дистрибутивной решетки по подмножеству неприводимых элементов // Обозрение прикладной и промышленной математики. 2001. - Том 8. - Вып. 2. - С. 578-579.

58. Гришкевич А. А. Управление топологической структурой сети // Шестая Всесоюзная конференция по проблемам управления развитием систем: Тез. докл. Киев: 1991. - Ч. 2. - С. 22.

59. Гришкевич А. А. Учебный CD ROM «Комбинаторика. Теория графов» // Проблемы вузовского учебника: Труды научно-методической конференции (29-30 апреля 2002 г.). Челябинск: Изд-во ЮУрГУ, 2002.-С. 8-12.

60. Гришкевич А. А. Формирование классов сечений из элементов с тремя состояниями // Алгоритмический анализ неустойчивых задач: Тез. докл. Всероссийской научной конференции. Екатеринбург: Изд-во Уральского ун-та, 2001. - С. 205-206.

61. Гришкевич А. А., Гришкевич М. В. Теоретико-решетчатый подход к описанию структурных взаимосвязей // Методы синтеза и планирования развития структур крупномасштабных систем: Тез. докл. V Всесоюзного семинара. М.: ИПУ, 1990. - С. 17.

62. Гришкевич А. А., Духовный И. Р., Пельцвергер Б. В. Оценка алгоритмов решения задачи построения магистрального хода автомобильной дороги между двумя пунктами // Известия ВУЗов. Строительство и архитектура. 1982. - № 9. - С. 124-126.

63. Гришухин В. П., Папернов Б. А. Субмодулярные задачи, алгоритмы их решения и смежные вопросы // Препринт. М.: ЦЭМИ, 1982.

64. Гук Ю. Б. Анализ надежности электро-энергетических установок. Л.: Энергоатомиздат. Ленингр. отделение, 1988. -224 с.

65. Гуревич И. В. Основы расчетов радиотехнических цепей. М.: Связь, 1975.-368 с.

66. Гуревич И. В., Заездный А. М. Основы теории сигнальных графов в приложении к радиотехнике: Учебное пособие. JL: 1967. - 86 с.

67. Гурский С. К. Алгоритмизация задач управления режимами сложных систем в электроэнергетике. Минск: Наука и техника, 1977. -368 с.

68. Демирчян К. С. Проблемы диагностики электрических цепей // Диагностика и специальные методы анализа электрических цепей: Труды ДВПИ. Владивосток: ДВПИ, 1975. - Т. 105. - С. 3-6.

69. Демирчян К. С., Бутырин П. А. Алгебраические проблемы расчета цепей переменной структуры // Автоматизированное проектирование электротехнических устройств и систем: Труды Всесоюзного семинара. -М., 1985.-С. 3-5.

70. Демирчян К. С., Бутырин П. А. Моделирование и машинный расчет электрических цепей. М.: Высшая школа, 1988. - 335 с.

71. Демирчян К. С., Бутырин П. А. Решение одного класса некорректных задач теории электрических цепей // Электронное моделирование. 1981. -№ 1.-С. 3-10.

72. Демирчян К. С., Ракитский Ю. В., Бутырин П. А., Карташев Е. Н., Коровкин Н. В. Проблемы численного моделирования процессов в электрических цепях // Известия АН СССР. Энергетика и транспорт. -1982.-№2.-С. 94-114.

73. Диагностика линейных электрических цепей : Учебное пособие / Н. В. Киншт, М. А. Кац, П. Г. Рагулин, П. М. Вайнман; Под общей редакцией М. А. Каца. Владивосток: Изд-во Дальневосточного университета, 1987. - 232 с.

74. Диллон Б., Сингх Ч. Инженерные методы обеспечения надежности систем: Пер. с англ. -М.: Мир, 1984. 318 с.

75. Диниц Е. А., Карзанов А. В., Ломоносов М. В. О структуре системы минимальных реберных разрезов графа // Исследования по дискретной оптимизации. М.: Наука, 1976. - С. 290-306.

76. Дискретная математика для программистов / Ф. А. Новиков. -СПб: Питер, 2001.-304 с.

77. Драгалин Г. Д. Математический интуиционизм. Введение в теорию доказательств. М.: Наука, 1979. - 256 с.

78. Дэвис Д., Барбер Д. Сети связи для вычислительных машин: Пер. с англ. М.: Мир, 1976. - 680 с.

79. Емеличев В. А., Ковалев М. М., Кравцов М. К. Многогранники, графы, оптимизация (комбинаторная теория многогранников). М.: Наука, 1981.-344 с.

80. Змыслёный М. Гибридная (вероятностно-статистическая) методика машинного анализа стабильности частотно-селективных LRC-цепей. Автореферат дис. . к-та техн. наук; 05.14.07 - Теоретическая электротехника. - М.: МЭИ, 1976. - 20 с.

81. Зорин В. В., Недин И. В. Определение и использование минимальных сечений при оценке надежности систем электроснабжения // Известия ВУЗов. Энергетика. 1974. -№ 4. - С. 31-36.

82. Иваницкий А. М., Игошин А. А. Расширение гибридного метода анализа цепей // Известия ВУЗов. Электромеханика. 1985. - № 2. -С. 109-116.

83. Кестен X. Теория просачивания для математиков. М.: Мир, 1986.-392 с.

84. Киншт Н. В., Герасимова Г. Н., Кац М. А. Диагностика электрических цепей. М.: Энергоатомиздат, 1983. - 192 с.

85. Киту шин В. Г. Надежность энергетических систем: Учебное пособие для электроэнергетических специальностей ВУЗов. М.: Высшая школа, 1984. - 256 с.

86. Кнут Д. Искусство программирования для ЭВМ. Т. 3. Сортировка и поиск. М.: Мир, 1978. - 846 с.

87. Ковалев М. М. Матроиды в дискретной оптимизации. Минск: Университетское, 1987. - 220 с.

88. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2000. - 960 с.

89. Короткое Б. А., Попков Е. Н. Алгоритмы имитационного моделирования переходных процессов в электрических системах: Учебное пособие / Под. ред. И. А. Груздева. Л.: Изд-во Ленинградского ун-та, 1987.-279 с.

90. Кофман А. Введение в прикладную комбинаторику. М.: Наука, 1975.-480 с.

91. Крон Г. Исследование сложных систем по частям диакоптика. -М.: Наука, 1972.-478 с.

92. Крон Г. Применение тензорного анализа в электротехнике // М.-Л.: Государственное энергетическое изд-во, 1955. 275 с.

93. Крых Я. Исследование устойчивости и чувствительности активных фильтров PC. Автореферат дис. . к-та техн. наук; 05.09.05 -Теоретическая электротехника. - М.: МЭИ, 1980. - 20 с.

94. Крых Я., Ханусик К. Алгоритм вычисления некоторой матрицы сопротивлений многополюсника, описанного ориентированным мат-роидом // III Международный симпозиум по теоретической электротехнике: Тез. докл. М., 1985. -Ч. 2.- С. 11-12.

95. Кудрин Б. И., Лосев Э. А. О необходимой точности методов расчета электрических нагрузок и оценки надежности систем электроснабжения промышленных предприятий // Известия ВУЗов. Электромеханика. 1982. - № 12.-С. 1448-1451.

96. Лекции по теории графов / Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. М.: Наука, 1990. - 384 с.

97. Липский В. Комбинаторика для программистов: Пер. с польск. -М.: Мир, 1988.-213 с.

98. Ловас Д., Пламмер М. Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии: Пер. с англ. М.: Мир, 1998.-653 с.

99. Логика и компьютер. Вып. 4 (серия «Кибернетика: неограниченные возможности и возможные ограничения»), Карпенко А. А. Многозначные логики. М.: Наука, 1997. - 223 с.

100. Максимович Н. Г. Линейные электрические цепи и их преобразования. М.-Л.: Госэнергоиздат, 1961. - 264 с.

101. Максимович Н. Г. Методы топологического анализа электрических цепей. Львов: Изд-во Львовского ун-та, 1970. - 259 с.

102. Максимович Н. Г. Теория графов и электрические цепи. Львов: Вища школа. Изд-во при Львовском ун-те, 1987. - 216 с.

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

104. Мэзон С., Циммерман Г. Электронные цепи, сигналы и системы. -М.: ИЛ, 1963.-620 с.

105. Надежность систем электроснабжения / Зорин В. В., Тисленко В. В., Клеппель Ф., Адлер Г. Киев: Вища школа, 1984. - 192 с.

106. Надежность технических систем: Справочник / Ю. К. Беляев, В. А. Богатырев, В. В. Болотин и др.; Под. ред. И. А. Ушакова. М.: Радио и связь, 1985. - 608 с.

107. Нгуен Динь Хао. Повышение эффективности алгоритма определения опасных по вероятности отказов сечений и элементов в системах электроснабжения // Известия АН СССР. Энергетика и транспорт. -1986. -№3.- С. 55-61.

108. Нейман JI. Р., Демирчян К. С. Теоретические основы электротехники. Том 1. JL: Энергоатомиздат, 1981. - 536 с.

109. Оре 0. Теория графов. М.: Наука, 1980. - 336 с.

110. Остапенко А. Г. Анализ и синтез линейных радиоэлектронных цепей с помощью графов: Аналоговые и цифровые фильтры. М.: Радио и связь, 1985. - 280 с.

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

112. Попков В. И., Демирчян К. С. Проблемы диагностики и прогнозирования надежности энергетического оборудования // Известия АН СССР. Энергетика и транспорт. 1979. -№ 6. - С. 3-11.

113. Преобразования схем электрических и электронных цепей / П. Ф. Хасанов, С. X. Ирматов, Ю. Р. Рашидов, А. А. Кадыров. Ташкент: Фан, 1978.- 83 с.

114. Прусс В. Л., Тисленко В. В. Повышение надежности сельских электрических сетей. Л.: Энергоатомиздат. Ленинградское отделение, 1989.-208 с.

115. Райншке К., Ушаков И. А. Оценка надежности систем с использованием графов. М.: Радио и связь, 1988. - 208 с.

116. Робишо Л., Буавер М., Робер Ж. Направленные графы и их приложение к электрическим цепям и машинам. М.: Энергия, 1964. -248 с.

117. Розанов М. Н. Надежность электроэнергетических систем. М.: Энергоатомиздат, 1984. - 200 с.

118. Розанов М. Н. Обзор существующих методов расчета надежности электрических сетей // Вопросы надежности энергосистем: Труды ВНИИЭ. М.: ВНИИЭ, 1978. - Вып. 55. - С. 38-55.

119. Ройтмэн Л., Свами М. Метод диагностики цепей // ТИИЭР. -1981.-Т. 69. -№ 5. С. 194-195.

120. Руденко Ю. Н., Ушаков И. А. Надежность систем энергетики. -М.: Наука, 1986.-251 с.

121. Рыбников К. А. Введение в комбинаторный анализ. М.: Изд-во Московского ун-та, 1985. - 308 с.

122. Рябинин И. А. Основы теории и расчета надежности судовых электроэнергетических систем. Л.: Судостроение, 1967. -363 с.

123. Рябинин И. А., Черкесов Г. Н. Логико-вероятностные методы исследования надежности структурно-сложных систем. М.: Радио и связь, 1981.-264 с.

124. Свами М., Тхуласираман К. Графы, сети, алгоритмы. М.: Мир, 1984.-455 с.

125. Сергиенко И. В. Математические модели и методы решения задач дискретной оптимизации. Киев: Наук. Думка, 1985. - 384 с.

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

127. Сешу С., Рид М. Б. Линейные графы и электрические цепи: Пер. с англ. М.: Высшая школа, 1971. - 448 с.

128. Сигорский В. П. Матрицы и графы в электронике. М.: Энергия, 1968.- 175 с.

129. Сигорский В. П., Петренко А. И. Алгоритмы анализа электронных схем. М.: Сов. радио, 1976. - 608 с.

130. Силламаа X. В. Основы синтеза схемных структур соединения многополюсных цепей. Таллин: Валгус, 1983.

131. Синьчугов Ф. И. Расчет надежности схем электрических соединений. М.: Энергия, 1971. - 176 с.

132. Сучилин А. М. Применение направленных графов к задачам электротехники. -М.-Л.: Энергия, 1971. 104 с.

133. Теоретические основы электротехники. Т. 1. Основы теории линейных цепей / Ионкин П. А., Даревский А. И., Кухаркин Е. С., Миронов В. Г., Мельников Н. А; Под ред. проф. П. А. Ионкина. М.: Высшая школа, 1976. - 544 с.

134. Тимкин Ю. В. Анализ электронных схем методом двунаправленных графов. М.: Энергоатомиздат, 1985. - 256 с.

135. Тисленко В. В. Оценка надежности сложных структур систем энергетики//Электричество. 1978.-№6.-С. 81-83.

136. Трохименко Я. К. Метод обобщенных чисел и анализ линейных цепей. М.: Сов. радио, 1972. - 311 с.

137. Уилсон Р. Введение в теорию графов: Пер. с англ. М.: Мир, 1977.-208 с.

138. Ушаков И. А., Литвак Е. И. Верхняя и нижняя оценки параметров двухполюсных сетей. Известия АН СССР. Техническая кибернетика. - 1977. - № 1.-С. 34-38.

139. Ушаков И. А., Литвак Е. И. Оценка параметров сетей со сложной структурой. М.: ВЦ АН СССР, 1986. - 66 с.

140. Филаретов В. В. Метод двоичных векторов для топологического анализа электронных схем по частям // Электричество. 2001. - № 8. -С. 33-42.

141. Филаретов В. В. Синтез оптимальных формул схемных функций электрических цепей // Электричество. 1995. - № 4. - С. 36-43.

142. Филаретов В. В. Топологический анализ электрических цепей на основе схемного подхода. Автореферат дис. . д-ра техн. наук; 05.09.05 - Теоретическая электротехника. - М., 2002. - 40 с.

143. Филаретов В. В. Формирование символьных функций для активных электрических цепей методом стягивания и удаления ветвей // Электричество. 2001. - № 4. - С. 43-51.

144. Филин Б. П. Методы анализа структурной надежности сетей связи. М.: Радио и связь, 1988. - 208 с.

145. Фокин Ю. А. Вероятностно-статистические методы в расчетах систем электроснабжения. М.: Энергоатомиздат, 1985. - 240 с.

146. Фокин Ю. А. Вероятностные методы в расчетах надежности электрических систем: Учебное пособие для вузов. М.: МЭИ, 1983. -216с.

147. Фокин Ю. А. Расчет надежности систем электроснабжения // Электротехнический справочник. М.: Энергоатомиздат, 1988. - Т. 3. - Кн. 1, разд. 39.8. - С. 320-336.

148. Фокин Ю. А. Расчет показателей надежности в системах электроснабжения // Электричество. 1982. - № 6. - С. 1-6.

149. Фокин Ю. А., Алиев Р. С., Туманин А. Н., Файницкий О. В. Методы оценки структурной надежности сложных схем электроэнергетических систем при меняющихся коммутационных состояниях // Известия АН. Энергетика. 1997,-№. 5. - С. 111-118.

150. Фокин Ю. А., Курилко М. В., Павликов В. С. Декомпозиция в расчетах надежности сложных электроэнергетических систем // Электричество. 1999. - №. 12.-С. 2-9.

151. Фокин Ю. А., Пономаренко И. О. Метод определения минимальных сечений относительно узлов нагрузки в расчетах надежности сверхсложных схем систем электроснабжения // Известия ВУЗов СССР. Энергетика, 1982. -№ 8.-С. 11-15.

152. Фокин Ю. А., Туфанов В. А. Оценка надежности систем электроснабжения. М.: Энергоатомиздат, 1981. - 224 с.

153. Фокин Ю. А., Харченко А. М. Определение минимальных сечений для оценки надежности электрических систем // Известия АН СССР. Энергетика и транспорт,- 1982.-№ 1.-С. 17-24.

154. Фокин Ю. А., Харченко А. М. Расчет показателей надежности систем электроснабжения // Электричество. 1982. - № 8. - С. 5-10.

155. Фокин Ю. А., Чан Динь Лонг. Метод оценки пропускной способности сложных систем электроснабжения и определения ожидаемого дефицита мощности у потребителей // Электричество. 1978. -№8.-С. 21-27.

156. Фокин Ю. А., Чан Динь Лонг. Оценка надежности электроснабжения узлов нагрузки сложных схем // Электричество. 1976. - № 8. -С. 13-18.

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

158. Фрэнк Г., Фриш И. Сети, связь и потоки: Пер. с англ. М.: Связь, 1978.-448 с.

159. Харари Ф., Палмер Э. Перечисление графов: Пер. с англ. М.: Мир, 1977.-326 с.

160. Ху Т. Целочисленное программировдние и потоки в сетях: Пер. с f англ. М.: Мир, 1974. - 520 с.

161. Хусаинов Ш. Н. Метод обобщенных главных величин // Теоретическая электротехника: Республ. межвед. научн.-техн. сборник. -Вып. 46. Львов: Вища школа, изд-во при Львовском ун-те, 1989. -С. 79-88.

162. Хусаинов Ш. Н. Современные методы анализа электрических цепей: Учебное пособие. Челябинск: Изд-во ЮУрГУ, 1998. - 71с.

163. Хусаинов Ш. Н. Улучшенный вариант метода главных контурных токов // Электричество. 1990. - № 2. - С. 81-83.

164. Хусаинов Ш. Н. Формирование уравнений электрической цепи по обобщенному контурно-узловому методу // Электричество. 1998. -№ 10.-С. 57-61.

165. Чан Динь Лонг, Нгуен Динь Хао. Определение группы узких по пропускной способности сечений в сложных ЭЭС // Известия ВУЗов. Электроэнергетика. 1982. -№ 1. - С. 3-7.

166. Червинская Л. А. О полиномиальной эквивалентности задач поиска разрезов, минимальных по величине и минимальных по включению // Техническая кибернетика. 1987. -№ 2. - С. 182-187

167. Чуловский В. И. Разработка алгоритмов анализа электрических цепей с использованием булевых множеств и их применение в задачах диагностики. Автореф. дис. . к-та техн. наук; 05.09.05 - Теоретическая электротехника. - Киев, 1990. - 20 с.

168. Шакиров М. А. Преобразования и диакоптика электрических цепей. Л.: Изд-во Ленинградского государственного ун-та, 1980. -196 с.

169. Шиханович Ю. А. Введение в современную математику. М.: Наука, 1965.-376 с.

170. Эндрени Дж. Моделирование при расчетах надежности в электроэнергетических системах: Пер. с англ. М.: Энергоатомиздат, 1983. -336 с.

171. Allan R. N., Billinton R., De Oliveira M. F. An Efficient Algorithm for Deducing the Minimal Cuts and Reliability Indices of a General Network Configuration // IEEE Trans. 1976. - Vol. R-25. - № 4. - P. 226233.

172. Billinton R., Grover M. S. A Computerized Approach to Substation and Switching Station Reliability Evalution // IEEE Transactions. 1974. -Vol. PAS-93. - № 5. - P. 1488-1497.

173. Bruno J. Matroids, graphs and resistance networks. Ph. D. Thesis. -City College ofN.Y.- 1969.

174. Bruno J., Weinberg L. Generalized networks: networks embedded on a matroid. Part I, II // Networks. 1976. - Vol. 6. - P. 53-94, 231-272.

175. Bruno J., Weinberg L. The principal minors of a matroid // Lin. Alg. and Appl. 1971. - № 4. - P. 17-54.

176. Cayley A. A theorem on trees // Quart. J. Math. Oxford Ser. 1889. -Vol. 23. - P. 376-378.

177. Coates С. L. Flow-graph solutions of linear algebraic equations // IRE Trans. Circuit Theory. 1959. - Vol. CT-6. - P. 170-187.

178. Cunningham W. Minimum cuts, modular functions and matroid poly-hedra//Networks. 1985.-Vol. 15.-P. 205-215.

179. Dulmage A. L., Mendelson N. S. Covering of bipartite graphs // Can. J. Math. 1958.-№ 10.-P. 517-534.

180. Edmonds J. R. Matroid partition // Lectures in Appl. Math. Part I. (Mathenmatics of the Decision Sciences.) 1968. - Vol. 11. - P. 335-346.

181. Endrenyi J., Maenhaut P., Payne L. Reliability evaluation of transmission systems with switching after fauits approximation and a computer program // IEEE Transactions on power apparatus and systems. - 1973. -Vol. PAS-92. - № 6. - P. 1863-1875.

182. Feussner W. Uber stromverzweigung in netzformigen leitern // Ann. Phus. 1902. - Vol. 9. - P. 1304-1329.

183. Feussner W. Zur berechnung der stromstarke in netzformigen leitern //Ann. Phus. 1904,- Vol. 15.-P. 385-394.

184. Galil Z. On the theoretical efficiency of various network flow algorithms // Theoretical Computer Science. 1981. - Vol. 14. - № 1. -P. 103-111.

185. Hanusik K., Krych J. Algorytm wyznaczania macierzy rezystancyjnej rozwarciowej wielowrotnika opisanego matroidem zorientowanym // VIII -SPETO GLIWICE 85. - 1985. - P. 131-135.

186. Iri M. A revive of recent work in japan on principal partitions of ma-troids and their applications // Ann. N.Y. Acad. Sci. 1979. - Vol. 319. -P. 306-319.

187. Iri M. Application of matroid theory // Mathematical Programming: The State of the Art. 11th Int. Symp. Springer: Berlin, 1983. - P. 158-201.

188. Iri M. Application of matroid theory to engineering systems problems // Proceedings of the 6-th Conf. On Probability Theory. Bucuresti, 1981. -P. 107-127.

189. Iri M. Comparison of matroid theory with algebraic topology with special reference to applications to network theory // Research Notes.f University of Tokio, 1964. Vol. 83.

190. Iri M., Fujishige S. Use of matroid theory in operations research, circuits and systems theory // Int. J. Systems Sci. 1981. - Vol. 12. - № 1. -P. 27-54.

191. Iri M., Tomizawa N. A unifying approach to fundamental problems in network theory by means of matroids (in Japanese) // Transactions of the Institute of Electronics and Communication Engineers of Japan. 1975. -Vol. 58A.-P. 33-40.

192. Kishi G., Kajitani Y. Maximally distant trees and principal partition of a linear graphs // IEEE Trans. Circuit Theory. 1969. - Vol. CT-16. -P. 323-330.

193. Kishi G., Kajitani Y. Maximally distant trees in a linear graph (in Japanese) // Transactions of the Institute of Electronics and Communication Engineers of Japan. 1968. - Vol. 51A. - P. 196-203.

194. Krych J., Zmyslony M. Hybrydowe rownanie opisujace wielowrotnik sis о strukturze wewnetrznej opisanej matroidem zorientowanym // Zeszyty naukowe wyzszej szkoly inzynierskiej w opolu. Seria: Elektryka z. 21. -1983.-Nr kol. 86.-P. 55-61.

195. Lawler E. L. Combinatorial optimization: networks and matroids. -New York: Holt, Rinehart and Winston, 1976. 374 p.

196. Mason S. J. Feedback theory: some properties of signal flow graphs // Proc. IRE. 1953. -Vol. 41. -P. 1144-1156.

197. Maxwell J. C. Electricity and magnetism. Т. 1. Oxford: Clarendon Press, 1892. - В кн.: Максвелл Д. К. Трактат об электричестве и магнетизме. (В 2-х т.) Т. 1.-М.: Наука, 1989.-416 с.

198. Minty G. On the axiomatic foundations of the teories of directed linear graphs, electrical networks and network-programming // Journal of Mathematics and Mechanics. 1966. - Vol. 15. - № 3. - P. 485-520.

199. Nakamura M. Boolean sublattices connected with minimization problems on matroids // Math. Programming. -1982. Vol. 22. - P. 117-120.

200. Nakamura M. Principal partition of polymatroids and its applications to electric network theory. Master's thesis. University of Tokyo, 1979.

201. Nakamura M., Iri M. Fine structures of matroids intersections and their applications // Proceedings of the International Symposium on Circuits and Systems. Tokyo, 1979. - P. 996-999.

202. Nakazawa H. Equivalence of nonoriented line and a pair of oriented lines in a network // IEEE Trans. Relial. 1979. - Vol. 28. - № 5. -P. 364-367.

203. Narayanan J. Theory of matroids and networks analysis. Ph. D. Thesis in Elect. Engin. Bombay, India: Indian Institute of Technology, 1974.

204. Ohtsuki Т., Ishizaki Y., Watanable H. Network analysis and topological degrees of freedom (in Japanese) // Transactions of the Institute of Electronics and Communication Engineers of Japan. 1968. - Vol. 51 A. -P. 238-245.

205. Ohtsuki Т., Ishizaki Y., Watanable H. Topological degrees of freedom and mixed analysis of electrical networks // IEEE Trans. Circuit Theory. 1970. - Vol. CT-17. - P. 491-499.

206. Ozawa Т., Kajitani Y. Diadnosability of linear active networks // Proceedings of the International Symposium on Circuits and Systems. Tokyo, 1979.-P. 866-869.

207. Papic M. Ocjena funkcionalne pouzdanosti distributivne mreze // Elektrotehnika. 1983,- Vol. 26.-№3.-P. 153-157.

208. Petersen B. Electrical networks and matroids. Ph. D. Dissertation. -Lyngby : Technical University of Denemark, 1976.

209. Petersen B. Investigating solvability and complexity of linear active networks by means of matroid // IEEE Trans, on Circuit and Systems. -1979. Vol. CAS-26. - № 5. - P. 330-342.

210. Picard J. C., Queyranne M. On the structure of all minimum cuts in a network and applications // Mathematical Programming Study. 1980. -Vol. 13.-P. 8-16.

211. Picard J. C., Queyranne M. Selected applications of minimum cuts in networks // INFOR. Can. J. Oper. Res. and Inf. Process. 1982. - Vol. 20. - № 4. - P. 394-422.

212. Recski A. Combinatorics in electrical engineering and statics // Handbook of Combinatorics. Vol. 2. Elsevier, 1995. - P. 1912-1924.

213. Recski A. Matroid theory and its applications in electric network theory and statics. Budapest: Academiai Kiado, 1989. - 531 p.

214. Recski A. On the sum of matroids with applications in electric network theory. Doctoral Dissertation. Budapest, 1972.

215. Tomizawa N., Fujishige S. Historial survey of extensions of the concept of principal partition and their unifying generalization to hypermatroids // Int. Symp. On Circuits and Systems. Rome, 1982. - P. 142-145.

216. Tutte W. T. Intriduction to the theory of matroids. New York: Elsevier, 1970.

217. Tutte W. T. Matroid and graphs // Trans. Amer. Math. Soc. 1959. -Vol. 90.-P. 527-552.

218. Wang К. T. On a new method for the analysis of electrical networks // Nath. Res. Ins. For Engineering, Academia Sinia Memor. 1934. - № 2.

219. Weinberg L. Matroids, generalized networks, and electric network synthesis // Journal of Combinatorial Theory. Ser. B. 1977. - Vol. 23. -P. 106-126.

220. Weinberg L. Matroids, oriented matroids, and polymatroids: theory and applications // Proc. Eur. Conf. Circuit Theory and Design. Amsterdam, 1981.-P. 164-175.

221. Welsh D. J. A. Matroid theory. London, New York: Academic press, 1976.-433 p.

222. Whitney H. On the abstract properties of linear dependence // American Journal of Mathematics. 1935. - Vol. 57. - P. 509-533.

223. Zmyslony M. Orientierte matroide und ihre anwendung in der netz-werktheorie // 27 Int. Wiss. Kolloq. Ilmenau, DDR, 1982. - Heft 6. -P.65-68.