Известия РАН. Теория и системы управления, 2022, № 3, стр. 3-20

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

Для сравнения сложности, как правило, конструируют измерительную шкалу (скалярную функцию), которая варианту структуры ставит в соответствие число, являющееся оценкой сложности. В линейной теории управления в качестве такой шкалы используют, например, порядок передаточной функции динамического регулятора [1–16], а также число ненулевых коэффициентов в матрице обратных связей статического регулятора [4, 17–20] синтезируемой системы.

Однако способ выбора предпочтительного варианта на основе минимизации оценки по заданной шкале не редко оказывается чрезмерно грубой формализацией механизма выбора, который реализует интуиция человека. На это обращали внимание авторы работ по теории выбора и принятия решений [21–24]. Например, содержательно менее сложным может быть признан не тот формально оптимальный вариант, в котором минимально число ненулевых элементов матрицы обратных связей, а вариант, выгодно отличающийся сочетанием более просто реализуемых обратных связей. Использование весовых коэффициентов, отражающих сложность реализации отдельных коэффициентов, не решает указанную проблему в полной мере из-за необязательной аддитивности оценочной функции. Оценка сложности по порядку динамического регулятора недостаточно полно учитывает информацию, заключенную в его математическом описании. Регуляторы одинакового порядка могут различаться характеристическим полиномом, набором сигналов обратных связей, а также сложностью операторов, преобразующих эти сигналы. В силу указанных обстоятельств применение шкалы с целью выбора предпочтительного варианта может приводить к нежелательному исключению вариантов, потенциально более предпочтительных при их содержательной оценке в сравнении с вариантами, которые выбраны в качестве формально оптимальных по заданной шкале.

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

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

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

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

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

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

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

Определение 1. Вектором решения задачи синтеза является конечномерный вектор x = = (x₁, …. x_i, …., x_n), значения компонент которого определяют количественные свойства синтезируемой системы, причем нулевое значение компоненты x_i  указывает на отсутствие i‑го элемента в максимальной структуре, заданной при математическом описании задачи.

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

Пример 1. Вектором решения задачи синтеза линейного регулятора может быть, например, вектор x = (x₁, x₂, …., x₆), компоненты которого – действительные числа, определяющие значения коэффициентов передаточной функции регулятора H(p) = (x₁p² + x₂p + x₃)/(x₄p² + x₅p + x₆), где p – комплексная переменная преобразования Лапласа. Указанная передаточная функция определяет максимальную структуру регулятора, которую можно редуцировать, если некоторые коэффициенты обнулить и рассматривать их как константы, равные нулю. Если принять x₄ = x₆ ≡ 0, то вектор x = (x₁, x₂, x₃, 0, x₅, 0) будет определять пропорционально-интегрально-дифференцирующий (ПИД) регулятор с передаточной функцией (x₁p² + x₂p + x₃)/(x₅p). Пропорционально-интегрирующий (ПИ) регулятор с передаточной функцией (x₂p + x₃)/(x₅p) описывается вектором решения, в котором x₁ = x₄ = x₆ ≡ 0, т.е. x = (0, x₂, x₃, 0, x₅, 0). Регулятор первого порядка с передаточной функцией (x₂p + x₃)/(x₅p + x₆) получается, если принять: x₁ = x₄ ≡ 0, т.е. если x = (0, x₂, x₃, 0, x₅, x₆).

Пример 2. Пусть регулятор, реализующий полиномиальную обратную связь по выходу системы управления, описывается уравнением

где u – величина управляющего воздействия, формируемого регулятором, величины y₁, …, y_n составляют вектор выхода системы, a_i, a_ij, a_ijk – постоянные коэффициенты. В качестве вектора решения задачи синтеза данного регулятора выступает вектор x, компонентами которого являются коэффициенты регулятора. Максимальная структура соответствует регулятору, в котором все компоненты вектора решения отличны от нуля. Обнуление некоторой компоненты вектора решения обеспечивает упрощение структуры регулятора.

Пример 3. Пусть при решении задачи идентификации требуется получить модель в виде линейной комбинации функций из заданного набора {f₁(t), …, f_n(t)}, т.е. искомой функцией будет функция x₁f₁(t) + x₂f₂(t) + …. + x_n f_n(t), которая достаточно близка функции φ(t), представляющей результаты наблюдений за объектом моделирования. Набор функций {f₁(t), …, f_n(t)} может содержать как линейные, так и нелинейные функции для аппроксимации нелинейных зависимостей φ(t), например, полиномы, гармонические функции, функцию знака переменной t и т.п. Равенство нулю некоторой компоненты x_i вектора решения x = (x₁, x₂, …., x_n) означает отсутствие соответствующей ей функции f_i(t) в искомой линейной комбинации и обеспечивает упрощение получаемой модели.

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

Определение 2. Компоненты вектора решения, значение которых отлично от нуля, назовем активными компонентами, а компоненты, значение которых равно нулю, – пассивными компонентами.

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

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

Определение 3. Структура есть набор S номеров активных компонент вектора решения.

Пример 4. В задаче примера 1 максимальной структуре соответствует набор {1, 2, 3, 4, 5, 6} номеров активных компонент вектора решения x. Структуре ПИД-регулятора соответствует набор S_ПИД = {1, 2, 3, 5}. Структура ПИ-регулятора задается набором S_ПИ = {2, 3, 5}, а структура регулятора первого порядка – набором S₁ = {2, 3, 5, 6}.

Множество ϒ всех вариантов структур совпадает с множеством всех подмножеств набора {$\overline {1,n} $}, где n – размерность вектора решения, т.е. ϒ есть степень (булеан) множества {$\overline {1,n} $}. Число элементов (мощность) множества ϒ равно 2ⁿ.

Элементом структуры, согласно определению 3, является элемент набора S номеров активных компонент вектора решения.

Пример 5. В примере 4 в качестве элементов структуры ПИД-регулятора выступают номера 1, 2, 3, 5 активных компонент вектора решения x.

Определение 4. Упрощением структуры является исключение из набора S активных компонент вектора решения некоторых его элементов.

Пример 6. Упрощение структуры ПИД-регулятора, указанного в примере 4, выражается в исключение из набора S_ПИД любого его элемента.

Определение 5. Правило сравнения сложности структур: структура S " сложнее, чем структура S  ', если структура S " содержит все элементы структуры S  ' и некоторые дополнительные. Структура S  ' проще, чем структура S ", если структура S  ' является подмножеством структуры S ". Структуры несравнимы по сложности (ни одна из них не может быть признана проще, либо сложнее другой), если одна из них не входит в другую в качестве подмножества. Рассматриваемое правило математически описывается бинарным отношением

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

Пример 7. В примере 4 структура ПИД-регулятора S_ПИД = {1, 2, 3, 5} сложнее, чем структура ПИ-регулятора S_ПИ = {2, 3, 5}, поскольку S_ПИ ⊂ S_ПИД. Структура ПИД-регулятора S_ПИД и структура регулятора первого порядка S₁ = {2, 3, 5, 6} несравнимы по сложности.

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

Множество приемлемых структур обозначим символом ζ.

Определение 7. Простой структурой будем называть приемлемую структуру S, для которой невозможно указать допустимую структуру S  ' более простую, чем S, т.е.

где Ω – множество простых структур.

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

Пример 8. Пусть в примере 4 любое упрощение структур S_ПИД и S₁ приводит к невозможности выполнить условия их приемлемости. Тогда структура ПИД-регулятора и структура регулятора первого порядка – простые структуры.

Определение 8. Простым решением назовем решение, имеющее простую структуру.

Пример 9. Пусть в примере 8 найдено значение вектора решения x = (x₁, x₂, x₃, 0, x₅, 0), соответствующего ПИД-регулятору с передаточной функцией (x₁p² + x₂p + x₃)/(x₅p). Такое решение является простым решением, поскольку структура S_ПИД этого решения – простая структура согласно условиям примера 8.

В качестве частного случая простого решения выступает решение, содержащее максимальное число нулевых компонент, называемое максимально разреженным решением (sparsest solution) [25]. В последующих разделах статьи проблема соотношения простых и максимально разреженных решений рассматривается более подробно.

Определение 9. Задача синтеза простых структур состоит в нахождении всех приемлемых структур, для каждой из которых нельзя указать менее сложную приемлемую структуру, т.е. требуется

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

где x – вектор решения, b – вектор, определяющий желаемые свойства синтезируемой системы, A – матрица, связывающая значение вектора решения x с значением вектора b.

Для заданного варианта структуры S, учитывая равенство нулю всех координат x_i вектора x, не включенных в S (т.е. учитывая, что x_i ≡ 0, ∀I ∉ S), систему (1.2) можно представить в виде

где матрица A_S и вектор x_S составлены соответственно из столбцов матрицы A и координат вектора x с номерами из S. В таком случае структура S является приемлемой, если для нее выполнимо условие (1.3), т.е.

Определение 10. Задачу (1.1), (1.4) синтеза простых структур решений системы линейных уравнений назовем строгой линейной задачей синтеза простых структур.

Требование приближенного выполнения равенства (1.2) опишем условием

где b^–, b⁺ – векторы, определяющие диапазон допустимых значений вектора b. Тогда с учетом (1.5) приемлемость структуры S задается формулой

Определение 11. Задачу (1.1), (1.6) синтеза простых структур решений системы линейных неравенств назовем приближенной линейной задачей синтеза простых структур.

Далее нас будет интересовать главным образом случай, когда системы (1.2) и (1.5) имеют неединственное решение.

Задачи, представленные в определениях 10, 11, мы назвали линейными, отличая их от задачи (1.1), которую будем называть задачей общего вида, поскольку в (1.1) описание условия S ∈ ζ может быть произвольным.

Формулы (1.4) и (1.6) определяют множество ζ приемлемых структур посредством указания свойства, отличающего приемлемую структуру S ∈ ζ от неприемлемой. Наряду с таким определением приемлемости будем допускать возможность задания списка ψ, явно указывающего некоторые неприемлемые структуры.

Пример 10. В задаче примера 1, формируя список ψ, можно учесть требование, состоящее в том, что порядок числителя передаточной функции регулятора не должен превышать порядок ее знаменателя. Это означает, что недопустимой является структура, указывающая активную компоненту x₁, но не указывающая активную компоненту x₄, а также всякая структура, указывающая активную компоненту x₂, но не указывающая в качестве активной компоненту x₄ или x₅. С целью учета данного требования все структуры с указанными недопустимыми сочетаниями их элементов включаются в набор ψ.

Линейную задачу (1.1), (1.6) можно доопределить, добавив к условиям (1.6) условие S ∉ ψ. В таком случае приемлемость структуры S описывается следующей формулой:

Определение 12. Задачу (1.1), (1.7) назовем линейной задачей с декларативными ограничениями.

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

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

2.1. Синтез динамического регулятора. Требуется синтезировать динамический регулятор с простой структурой в составе линейной стационарной системы со скалярным управлением и векторной обратной связью. Объект управления задан операторным уравнением

где y(t) – вектор выходов, используемых в регуляторе в качестве сигналов обратной связи. Его первая компонента y₁(t) – выход системы, a(p) – характеристический полином объекта управления, b_u (p), b_f (p) – векторы, компонентами которых являются полиномы числителей передаточных функций объекта управления соответственно по управляющему u и возмущающему f воздействиям, порядок полинома a(p) – не меньше порядка любого полинома в векторах b_u(p), b_f (p), p = d/dt – оператор дифференцирования по времени t.

Регулятор опишем уравнением

где g – скалярное задающее воздействие (вход синтезируемой системы), r(p), q_g(p), q_f (p) – полиномы, $\ell $(p) – полиномиальный вектор, r(p) – характеристический полином регулятора, q_g(p), $\ell $(p), q_f (p) – числители передаточных функций регулятора соответственно по задающему воздействию, по каналам обратных связей и по возмущающему воздействию.

Из уравнений (2.1), (2.2) следует уравнение, отражающее зависимость выхода синтезируемой системы от задающего и возмущающего воздействий:

В нем где h_s(p) – характеристический полином синтезируемой системы, h_g(p), h_f (p) – полиномы числителей передаточных функций синтезируемой системы соответственно по задающему и возмущающему воздействиям, c(p) – вектор, i-я компонента которого определяется выражением c_i(p) = (b_ui(p)b_f1(p) – b_fi(p)b_u1(p))/a(p), причем c_i(p) – полином, p – комплексная переменная преобразования Лапласа. Считаем заданными желаемые значения коэффициентов полиномов h_s(p), h_g(p), h_f (p), обеспечивающие соответствие характеристик системы назначенным требованиям.

Уравнения (2.4)–(2.6) линейны относительно искомых полиномов регулятора и сводятся к системе линейных уравнений (1.2) в результате приравнивания коэффициентов при одинаковых степенях оператора p.

Вектор решения рассматриваемой задачи – вектор неизвестных системы (1.2), составленный из искомых коэффициентов полиномов регулятора, т.е. x = (q_g, q_f, $\ell $, r)^Т, где q_g, q_f , $\ell $, r – векторы коэффициентов полиномов q_g(p), q_f (p), $\ell $(p), r(p).

Вектор правых частей системы (1.2) в данном случае составлен из желаемых значений коэффициентов полиномов синтезируемой системы h_s(p), h_g(p), h_f (p). Значения элементов матрицы A системы (1.2) определяются значениями коэффициентов полиномов a(p), b_u(p), b_f (p) объекта управления.

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

Структура регулятора определяется набором номеров ненулевых коэффициентов искомых полиномов регулятора q_g(p), q_f (p), $\ell $(p), r(p), выступающих в роли активных компонент вектора решения.

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

Искомыми являются простые структуры регулятора.

Таким образом, синтез регулятора сводится к задаче (1.1), (1.4) или (1.1), (1.6), соответственно – к строгой или приближенной линейной задаче синтеза простых структур.

При проверке приемлемости структуры можно учесть список ψ запрещенных структур. В него можно внести структуры, например, не соответствующие требованию физической реализуемости регулятора, т.е. структуры, в которых степень знаменателя (порядок r (p)) в передаточных функциях регулятора меньше, чем порядок числителя (порядок q_g(p), q_f (p), $\ell $(p)). В таком случае приходим к задаче (1.1), (1.7), т.е. к линейной задаче синтеза простых структур с декларативными ограничениями.

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

Объект управления включает в себя усилитель мощности, электродвигатель постоянного тока, механический редуктор и инерционную нагрузку. Он описывается системой дифференциальных уравнений [26, c. 10, 11], которую можно эквивалентно представить операторным уравнением (2.1). В нем вектор выходов  y = (y₁, y₂) = (φ, I_я), где φ – угловое положение выходного вала электропривода (выход синтезируемой системы), I_я – ток в якорной обмотке двигателя. Управляющим u и возмущающим  f воздействием являются соответственно напряжение на якорной обмотке и момент сопротивления движению, приведенный к выходному валу двигателя. Знаменатель передаточной функции (характеристический полином) объекта управления a(p) = (T ²p² + + 2ξTp + 1)p, где T ² = JL/(C_mC_e), ξ = JR/(2C_mC_eT); R, L – сопротивление и индуктивность обмотки двигателя; С_e, С_m – коэффициент противоЭДС и коэффициент момента двигателя; J – момент инерции подвижных частей, приведенный к валу двигателя. Числители b_u(p) и b_f (p) передаточных функций объекта управления по управляющему u и возмущающему f воздействиям представляют собой векторы b_u(p) = (1/(k_rC_e), J/(C_mC_e)p²) и b_f (p) = (–(R + Lp)/(k_rC_mC_e), p/C_m), где k_r – коэффициент передачи редуктора, φ = φ_д /k_r , φ_д – угловое положение вала двигателя.

Назначим максимальный допустимый порядок регулятора равный двум. Будем считать доступными для использования в регуляторе переменные y₁, y₂ и задающее воздействие g. Возмущающее воздействие в рассматриваемом примере считаем недоступным измерению и, как следствие, принимаем q_f(p) = 0. Порядок числителей в передаточных функциях регулятора не должен превышать порядок их знаменателя. В таком случае максимальная структура синтезируемого регулятора, согласно (2.2), описывается уравнением

Пусть в синтезируемой системе требуется обеспечить:

1) равенство характеристического полинома синтезируемой системы h_s(p) стандартному полиному Баттерворта [27] пятого порядка, т.е. требуется обеспечить равенство

в котором вектор левой части составлен из коэффициентов полинома h_s(p), номер коэффициента h_sk равен показателю степени его сомножителя p^k в полиноме h_s(p), вектор правой части составлен из коэффициентов полинома Баттерворта, ω₀ = 10π рад/с;

2) равенство единице коэффициента передачи системы по задающему воздействию, что эквивалентно условию одинаковости значений младших коэффициентов полиномов числителя и знаменателя передаточной функции системы по задающему воздействию, т.е. условию h_g0 = h_s0.

Из уравнения (2.5) и условия h_g0 = h_s0 находим q_g0 = h_g0/b_u1 = k_rC_e, q_g1 = q_g2 = 0. Уравнение (2.6) исключаем из рассмотрения, поскольку не назначены требования к полиному h_f (p). Таким образом, в системе (2.4)–(2.6) не решенным остается только уравнение (2.4).

Следуя известным правилам перехода от полиномиальных уравнений к алгебраическим [28], из (2.4) получим линейную систему алгебраических уравнений (1.2), в которой:

вектор неизвестных

где ${{\ell }_{{ik}}}$ – коэффициент при сомножителе p^k в полиноме ${{\ell }_{i}}$(p), являющимся i-й компонентой вектора $\ell $(p) в уравнении регулятора (2.2) (полином ${{\ell }_{i}}$(p) выступает в качестве коэффициента обратной связи по изображению переменной y_i), r₀, r₁, r₂ – коэффициенты полинома r(p),

вектор правой части

матрица системы где k_u1 = 1/(k_rC_e), k_u2 = J/(C_mC_e).

Таким образом, задача синтеза простых регуляторов электропривода сведена к задаче (1.1), (1.4), т.е. к строгой линейной задаче синтеза простых структур. В ней вектором решения является вектор (${{\ell }_{{10}}}$ ${{\ell }_{{11}}}$ ${{\ell }_{{12}}}$ ${{\ell }_{{20}}}$ ${{\ell }_{{21}}}$ ${{\ell }_{{22}}}$ r₀r₁r₂), составленный из искомых коэффициентов полинома регулятора в уравнении (2.2), описывающем, с учетом сказанного выше, его максимальную структуру. Вариант структуры регулятора определяется набором номеров активных компонент вектора решения. Число всех вариантов структур в данном случае равно 2⁹ = 512, поскольку размерность вектора решения равна 9. Требуется исключить все неприемлемые и избыточные структуры и, таким образом, найти все простые.

Воспользовавшись методом, изложенным в разд. 4.1, находим все простые структуры, обеспечивающие решение рассматриваемой задачи. Они представлены в табл. 1 наборами номеров активных координат вектора решения и в табл. 2 – их характеристическими векторами (характеристический вектор подмножества S ⊆ {$\overline {1,n} $} состоит из n компонент, его i-я компонента равна 1, если i ∈ S, и равна 0 в противном случае). В табл. 2 цифра 1 (0), стоящая на пересечении i-й строки и  j-го столбца, означает, что в структуре регулятора, кодируемой i-й строкой, присутствует (отсутствует) коэффициент, стоящий в заголовке j-го столбца. При вычислениях использовались следующие значения: T = 0.5 c, ξ = 200, k_u1 = 3 рад/В/с, k_u2 = 430 c · A · рад.

Выбор единственной структуры из найденного множества выполняется с учетом дополнительных требований, неучтенных при формализации рассматриваемой задачи. Например, если дополнительно учесть желательность упрощения измерительной системы, то привлекательным представляется регулятор, имеющий структуру S₅. Ей соответствует уравнение регулятора (r₂p² + + r₁p + r₀)u = q_g0g − (${{\ell }_{{12}}}$p² + ${{\ell }_{{11}}}$p + ${{\ell }_{{10}}}$)y₁. Такой регулятор позволяет решить рассматриваемую задачу на основе измерения и использования в обратной связи только величины y₁, являющейся выходом системы, поскольку в структуре S₅ коэффициенты ${{\ell }_{{20}}}$, ${{\ell }_{{21}}}$, ${{\ell }_{{22}}}$ в обратной связи по выходу y₂ (по току якоря) равны нулю.

Пример 12. Дополним условия примера 11 требованием обеспечить астатизм первого порядка (обеспечить нулевое значение первого коэффициента ошибки) по возмущающему воздействию, что эквивалентно требованию равенства нулю в полиноме h_f(p) младшего коэффициента h_f0. Из уравнения (2.6) находим h_f0 = ${{b}_{{u10}}}{{q}_{{f0}}}$ + ${{b}_{{f10}}}{{r}_{0}}$ + ${{\ell }_{{10}}}$c₁₀ + ${{\ell }_{{20}}}$c₂₀. Учтем, что в рассматриваемой задаче b_u1 = 1/(k_rC_e), b_f1 = –(R + Lp)/(k_rC_mC_e), q_f = 0, c₁₀ = 0; c₂₀ = 1/(k_rC_mC_e). Тогда h _f0 = –(${{\ell }_{{20}}}$ + + r₀R)/(k_rC_mC_e) и, следовательно, требование h_f0 = 0 эквивалентно условию ${{\ell }_{{20}}}$ + r₀R = 0. Обеспечим точное выполнение полученного равенства. С этой целью добавим в матрицу A системы (1.2) седьмую строку (0 0 0 1 0 0 R 0 0), описывающую левую часть полученного равенства. Правую часть равенства учтем, добавив в вектор b седьмую координату, равную нулю. В результате получаем задачу (1.1), (1.4), т.е. строгую линейную задачу синтеза простых структур с найденными для данного примера значением матрицы A и вектора b.

Применив метод, описанный в разд. 2.2, находим все простые структуры. Они представлены в табл. 3 их характеристическими векторами.

Число простых структур, соответствующих условиям задачи, в данном примере существенно меньше, чем в первом примере, что обусловлено расширением перечня учтенных требований. Структура S₅, которая в примере 11 была выбрана как предпочтительная, в рассматриваемом примере оказывается неприемлемой. Вместе с тем структуры S₁, S₂, S₄, S₁₂, найденные в примере 11, оказались способными выполнить дополнительное условие астатизма системы, назначенное в данном примере, без расширения перечня активных координат, т.е. без усложнения структуры регулятора. Порядок всех регуляторов, представленных в табл. 3, одинаков, но число элементов в найденных структурах различно. Структуры S₁, S₂, S₄, S₁₂, представленные в первом столбце табл. 3, указывают шесть активных координат вектора решения, а остальные – семь. Для структур S₁, S₂, S₄, S₁₂, соответствующих требованиям предыдущего примера, дополнительное требование ${{\ell }_{{20}}}$ + r₀R =0, введенное в данном примере для обеспечения астатизма, выполняется без использования дополнительных активных координат, поскольку в них координаты x₄ ≡ ${{\ell }_{{20}}}$, x₇ ≡ r₀ пассивны. Поэтому ${{\ell }_{{20}}}$ = r₀ = 0, что соответствует тривиальному решению уравнения ${{\ell }_{{20}}}$ + r₀R =0. В структурах S₂₂ – S₂₇ требование астатизма обеспечивается путем добавления в некоторую простую структуру примера 11 дополнительной активной координаты x₄ ≡ ${{\ell }_{{20}}}$ согласно условию ${{\ell }_{{20}}}$ + r₀R = 0, расширившего перечень требований примера 11. Например, структура S₂₂ – результат добавления в структуру S₃ активной координаты x₄ ≡ ${{\ell }_{{20}}}$.

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

Пример 13. Пусть в задаче примера 12 достаточно обеспечить равенство только пяти младших коэффициентов полинома h_s(p) соответствующим коэффициентам заданного полинома Баттерворта. При этом старший коэффициент полинома h_s(p) должен отвечать условию 0 ≤ h_s5 ≤ $\omega _{1}^{{ - 5}}$. Тогда требования к синтезируемой системе описываются системой неравенств (1.5). В ней вектор неизвестных x и матрица A остаются такими же, как в примере 12. Диапазон допустимых значений коэффициента h_s5 учтем, назначив шестой координате векторов b^–, b⁺ значение, равное соответственно 0 и $\omega _{1}^{{ - 5}}$, значения остальных координат векторов b^–, b⁺ совпадают с значениями координат вектора b из примера 12. Таким образом, задача сводится к задаче (1.1), (1.6), т.е. к приближенной линейной задаче синтеза простых структур. Воспользовавшись методом, изложенным в разд. 4.2, можно найти все простые решения указанной задачи. Однако у некоторых регуляторов, соответствующих найденным структурам, порядок полиномов ${{\ell }_{1}}$(p) или ${{\ell }_{2}}$(p) может превышать порядок полинома r(p), что противоречит условиям задачи. Чтобы исключить указанное противоречие, составим список ψ структур, нарушающих условие согласования порядков полиномов, и учтем наличие такого списка в постановке решаемой задачи. В список ψ включаем все подмножества наборов S, указывающих коэффициент r_i, i ∈ {0, 1, 2}, но при этом не указывающих коэффициенты ${{\ell }_{{1j}}}$, ${{\ell }_{{2k}}}$, такие, что  j ≤ i или k ≤ i. Следовательно, рассматриваемая задача сводится к линейной задаче с декларативными ограничениями, т.е. к задаче синтеза простых структур (1.1), (1.7). Воспользовавшись методом, изложенным в разд. 4.3, находим все простые структуры. Они представлены в табл. 4 их характеристическими векторами.

Из табл. 4 видно, что ослабление требований примера 12 привело к упрощению структур регуляторов. Приведенные в ней структуры S₂₈, S₂₉, S₃₀, S₃₁ есть результат исключения одной компоненты соответственно из структур S₂, S₂₂, S₂, S₂₅.

Пример 14. Пусть в задаче примера 12 требуется найти максимально разреженные решения системы (1.2), определяющие структуры регуляторов с минимальным числом настраиваемых коэффициентов. Согласно утверждению 5 (разд. 3), множество простых структур примера 12 содержит структуры всех максимально разреженных решений системы (1.2). Их можно выделить из табл. 3. Максимально разреженным решениям соответствуют структуры S₁, S₂, S₄, S₁₂. Они для настройки регулятора указывают шесть коэффициентов, а остальные структуры табл. 3 – семь коэффициентов.

Более подробно задача синтеза динамических регуляторов с простой структурой рассмотрена в [29, 30].

2.2. Синтез статического регулятора. Решим задачу синтеза статического регулятора с простой структурой в составе линейной динамической системы

где x(t), u(t) – векторы состояния и управления, r(t) – задающее воздействие; A(t), B(t) – числовые матрицы, Q, K – искомые матрицы коэффициентов регулятора. Желаемое поведение системы определено эталонной траекторией движения x*(t), t ∈ [t₀, T], соответствующей заданному воздействию r*(t) и начальным условиям x(t₀) = $x_{0}^{*}$.

Применив формулу Коши к системе (2.7), (2.8), получим уравнение:

где Ф(t, τ) – импульсная переходная матрица (матрица Коши) объекта управления (2.7).

Учитывая линейное вхождение искомых элементов матриц Q, K в уравнение (2.9), после перехода к дискретному времени имеем систему линейных алгебраических уравнений (1.2), в которой вектором неизвестных является вектор, составленный из искомых элементов матриц Q, K. При этом условие (1.2) соответствует требованию точной реализации назначенного движения x^*(t). Таким образом, рассматриваемая задача сводится к задаче (1.1), (1.4) синтеза простых структур решений системы линейных уравнений.

Приняв во внимание заданную погрешность реализации эталонной траектории, переходим от требования (1.2) к требованию (1.5). Следовательно, приемлемость структуры регулятора S определяется формулой (1.6). Структура S представляет собой набор номеров активных компонент вектора решения, составленного из искомых элементов матриц Q, K. Исключение из указанного набора любой компоненты приводит к упрощению структуры регулятора. Искомыми являются простые структуры. В результате рассматриваемая задача сводится к задаче (1.1), (1.6), т.е. к приближенной линейной задаче синтеза простых структур. Если указанные требования дополнить списком заведомо неприемлемых структур, то задача сводится к линейной задаче с декларативными ограничениями, т.е. к задаче синтеза простых структур (1.1), (1.7).

Пример 15. Решим задачу синтеза статического регулятора с простой структурой, предназначенного для стабилизации направления полета (курса) и угла крена самолета. Движение самолета по крену, рысканию (курсу) и скольжению называют боковым движением. Возмущенное боковое движение самолета относительно установившегося горизонтального полета описывается линейной системой дифференциальных уравнений пятого порядка [31, с. 208], которую можно представить в виде системы (2.7). В ней компонентами вектора состояния (β, ω_x, ω_y, γ, ψ) являются угол скольжения β, угловая скорость крена ω_x, угловая скорость рыскания ω_y, угол крена γ, угол рыскания ψ, компоненты вектора управления (δ_н, δ_э) – угол отклонения руля направления δ_н и угол отклонения элеронов δ_э. Для самолета массой 45 000 кг, летящего на высоте 9000 м со скоростью 800 км/ч, параметры модели бокового движения [31, с. 208] таковы, что матрицы системы (2.7) имеют значения

Эталонной траекторией движения системы (2.7), (2.8) назначим оптимальную траекторию, доставляющую минимум квадратичному функционалу:

при движении системы из состояния (β, ω_x, ω_y, γ, ψ) = (1, 1, 1, 1, 1) в состояние равновесия.

В данном примере регулятор решает задачу стабилизации, поэтому в (2.8) Qr(t) ≡ 0. Матрица K в (2.8), доставляющая минимум функционалу J и, следовательно, обеспечивающая реализацию оптимальной траектории, принимает значение

Максимальная структура регулятора описывается уравнением (2.8), в котором все элементы матрицы K = (k_ij), i = 1,2;  j = $\overline {1,5} $ , могут использоваться для настройки регулятора. Вариант структуры S определяется набором номеров активных компонент вектора решения (k₁₁…k₁₅, k₂₁…k₂₅), являющегося конкатенацией строк матрицы K .

Допустим отклонение траектории движения системы от оптимальной в переходном процессе в пределах ±1%. Учтем необходимость обязательного наличия в системе обратной связи по углу крена и углу рыскания. С этой целью составим список заведомо неприемлемых структур, в который включим все структуры, соответствующие матрицам K с нулевым четвертым или пятым столбцом, т.е. все структуры, относящие коэффициенты k₁₄ и k₂₄ или k₁₅ и k₂₅ к множеству пассивных координат вектора решения. В таком случае задача сводится к линейной задаче синтеза простых структур с декларативными ограничениями, т.е. к задаче (1.1), (1.7). Воспользовавшись методом, изложенным в разд. 4.3, находим решение указанной задачи. Единственной простой структурой, отвечающей требованиям данного примера, оказывается максимальная структура, которой соответствует уравнение регулятора

Пример 16. Пусть в задаче примера 15 допустимо отклонение траектории движения системы от оптимальной в переходном процессе в пределах ±5%. Воспользовавшись методом из разд. 4.3, находим множество простых структур. Оно содержит единственную простую структуру S₁ = {1, 3, 5, 7, 9, 10}, которой соответствует уравнение регулятора

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

Пример 17. Расширим указанный в примере 16 диапазон допустимых отклонений траектории движения системы от эталонной в переходном процессе до ±10%. В таком случае множество простых структур, найденное методом из разд. 4.3, содержит две структуры: структуру S₁, представленную в примере 16, и структуру S₂ = {1, 3, 5, 8, 9, 10}, которой соответствует уравнение регулятора:

Положительным отличием структуры S₂ от S₁ является отсутствие в ней обратной связи по скорости крена ω_x, что позволяет исключить необходимость измерения значений ω_x. При этом отклонение от эталонной траектории соответствует назначенным пределам.

2.3. Выбор управляющих воздействий. Пусть задан список возможных, но не обязательно необходимых управляющих воздействий. Вариант сочетания управляющих воздействий определяется набором S, который перечисляет номера воздействий, т.е. номера компонент u_j(t) вектора управления u, используемых для управления объектом. Все компоненты вектора u, не вошедшие в набор S, полагаются тождественно равными нулю. Требуется найти простые наборы S, т.е. наборы, указывающие воздействия, использование которых необходимо и достаточно для управления объектом с заданной точностью. Полагаем, что объект управления описывается уравнением (2.7) и назначена эталонная траектория x*(t, x₀), t ∈ [t₀,T], которую система управления должна осуществить с заданной точностью. Применив формулу Коши к уравнению (2.7), находим

Учитывая линейное вхождение вектора управления в уравнение (2.10), после перехода к дискретному времени получаем систему линейных алгебраических уравнений (1.2), в которой вектором неизвестных является вектор, составленный из компонент u_j(t) вектора управления. Приняв во внимание заданную погрешность реализации эталонной траектории, переходим от требования (1.2) к (1.5). Следовательно, приемлемость набора S определяется формулой (1.6). В результате рассматриваемая задача сводится к задаче (1.1), (1.6), т.е. к приближенной линейной задаче синтеза простых структур.

2.4. Синтез программного управления. Пусть объект управления описывается уравнением (2.7), где x – вектор состояния, u – скалярная импульсная функция управления, допускающая идеализированное представление:

где δ(t) – дельта-функция Дирака, u_j– амплитуда управления в  j-й момент времени. Набор S указывает номера моментов времени из заданного ряда {t₀, t₁,…, t_М}, в которые управление может быть отлично от нуля, т.е. S ⊆ {0,1, …, M}. Требуется найти программу управления u(t), обеспечивающую прохождение траектории движения через назначенное множество точек x*(t_k), k = $\overline {1,N} $. Структура программы управления определяется набором S. Исключение из него любого элемента является упрощением программы управления. Простая структура в данном случае определяет набор моментов времени, в которые подача управляющих импульсов есть необходимое и достаточное условие прохождения траектории движения через множество назначенных точек. Применительно к рассматриваемой задаче с учетом импульсного характера управляющих воздействий уравнение (2.10) принимает вид где Q(k) – множество номеров моментов времени {t₀, t₁, t₂ ,…, t_j ≤ t_k}, Δt – шаг по времени.

Система (2.11) является системой линейных алгебраических уравнений (1.2), в которой вектор неизвестных составлен из амплитуд u_j. Она соответствует требованию точного прохождения траектории движения через назначенные точки x*(t_k), k = $\overline {1,N} $. Задав допустимые отклонения траектории от назначенных точек, переходим от требования (1.2) к (1.5). В таком случае приемлемость набора S определяется формулой (1.6). В результате получаем приближенную линейную задачу синтеза простых структур (1.1), (1.6).

2.5. Идентификация. Решим задачу идентификации, в которой требуется получить модель в виде линейной комбинации функций из набора {f₁(t), …, f_n(t)}, которая на заданном множестве значений аргумента t достаточно хорошо воспроизводит результаты наблюдений, представленные набором {φ(t₁), φ(t₂), …, φ(t_m)}. Требование точного соответствия модели результатам наблюдений описывается уравнением

где x₁, x₂, …., x_n – искомые числа, составляющие вектор решения x = (x₁, x₂, …., x_n) рассматриваемой задачи. Равенство нулю компоненты x_i вектора решения означает отсутствие функции  f_i(t) в синтезируемой модели и таким образом приводит к упрощению модели. Структура модели определяется набором S номеров координат вектора решения, отличных от нуля. Система (2.12) в матричной форме записи имеет вид (1.2), в ней элементами a_ij матрицы системы A являются числа  f_j (t_i), i = $\overline {1,m} $, j = $\overline {1,n} $, а элементами b_j вектора b правых частей – числа φ(t_i), i = $\overline {1,m} $. Для заданного набора S она приобретает вид (1.3). Приемлемость набора S определяется формулой (1.4) или (1.6) соответственно в случае точного или приближенного решения рассматриваемой задачи. Требование получить модель с простой структурой приводит к задаче (1.1), (1.4) или (1.1), (1.6), т.е. к строгой или приближенной линейной задаче синтеза простых структур.

2.6. Синтез адаптивной системы. Пусть в процессе функционирования системы управления требуется парировать изменения ее параметров, приближая поведение располагаемой системы управления к поведению эталонной системы. Считаем, что располагаемая и эталонная системы описываются одинаковыми уравнениями, в которых можно выделить обобщенные параметры (постоянные времени, коэффициенты передачи и т.п.) Θ_i, i = $\overline {1,m} $, являющиеся функциями первичных параметров. Различие в поведении располагаемой и эталонной систем обусловлено различием только их обобщенных параметров. Значения некоторых первичных параметров α_j,  j = $\overline {1,n} $, можно корректировать. Набор S ⊆ $\overline {1,n} $ перечисляет корректируемые первичные параметры и тем самым определяет структуру закона адаптации. Требуется найти наборы S ⊆ $\overline {1,n} $, указывающие сочетания таких первичных параметров α_j, j ∈ S, изменение которых является необходимым и достаточным условием для адаптивного приближения располагаемой системы к эталонной с заданной точностью. Эти наборы соответствуют определению простого набора. Условие приемлемости набора S в данном случае описывается формулой

где α = (α₁, α₂, …., α_n) – вектор решения рассматриваемой задачи, $\Theta _{i}^{*}$ – эталонное значение обобщенного параметра Θ_i. Требование получить простую структуру закона адаптации приводит нас к задаче (1.1), (2.13), являющейся в рамках принятой терминологии задачей синтеза простых структур общего вида. В некоторых случаях представляется возможным линеаризовать зависимости Θ_i (α). Например, если обобщенные параметры – степенные комплексы первичных параметров, тогда в результате логарифмирования уравнений Θ_i (α) = $\Theta _{i}^{*}$ приходим к системе линейных уравнений где γ_ij, i = $\overline {1,m} $, j = $\overline {1,n} $ – показатели степеней в степенных комплексах Θ_i (α). Система (2.14) в матричной форме записи имеет вид (1.2), в ней элементами вектора неизвестных являются искомые значения lgα_j, j = $\overline {1,n} $, элементы матрицы системы A – числа γ_ij, i = $\overline {1,m} $, j = $\overline {1,n} $, а элементы вектора b правых частей – числа lg$\Theta _{i}^{*}$, i = $\overline {1,m} $. Для заданного набора S она приобретает вид (1.3). Приемлемость набора S определяется формулой (1.4) или (1.6) в случае точного или приближенного решения рассматриваемой задачи. В результате приходим к задаче (1.1), (1.4) или (1.1), (1.6), т.е. соответственно к строгой или приближенной линейной задаче синтеза простых структур.

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

3.1. Строгая линейная задача.

Утверждение 1. Структура S⁰ решения системы линейных уравнений (1.2) является простой тогда и только тогда, когда система (1.3) при S = S⁰ имеет единственное решение, все координаты которого отличны от нуля.

Доказательство. Пусть $x_{{{{S}^{0}}}}^{0}$ = ($x_{j}^{0}$),  j ∈ S⁰ – решение системы (1.3) при S = S⁰. Если $x_{{{{S}^{0}}}}^{0}$ содержит компоненты равные нулю, т.е. $x_{j}^{0}$ = 0,  j ∈ S " ⊆ S⁰, тогда вектор ($x_{j}^{'}$),  j ∈ S' = S⁰\S " является решением системы (1.3) для S = S'. Следовательно, набор S' является приемлемым. Тогда S⁰ ∉ Ω, поскольку S' ⊂ S⁰, т.е. структуру S⁰ можно упростить без нарушения условий приемлемости (1.3). Если система (1.3) не имеет решения при S = S⁰, то S⁰ ∉ Ω, поскольку S⁰ недопустимое множество. Если система (1.3) имеет неединственное решение для S = S⁰, то по крайней мере одна k-я компонента вектора x, k ∈ S⁰, может быть обнулена, и условие (1.3) может быть выполнено с помощью подходящего выбора значений компонент вектора x, номера которых принадлежат множеству S⁰\{k}. Теперь рассуждая, как в начале доказательства, получаем S⁰ ∉ Ω. Это завершает доказательство необходимости утверждения. Если для S⁰ выполнены условия утверждения, то множество S ⊂ S⁰ становится недопустимым при исключении набора координат вектора x_S из S⁰. Следовательно, не существует допустимого множества S, являющегося подмножеством множества S⁰. Это доказывает достаточность условий утверждения и завершает доказательство.

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

Утверждение 2. Если набору S соответствует единственное решение системы (1.3), в котором есть нулевые компоненты с номерами, составляющими множество S ", тогда набор S\S " является простым.

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

Утверждение 3. Число элементов, составляющих простой набор S⁰, не превышает ранг матрицы A системы (1.2), т.е. card(S⁰) ≤ rank(A), где card(S⁰) – кардинальное число (число элементов) множества S⁰.

Доказательство. Если набор S⁰ является простым, то, согласно утверждению 1, система (1.3) при S = S⁰ имеет единственное решение и, следовательно, ее матрица A_S0 имеет ранг rank(A_S0), равный числу неизвестных, т.е. равный card(S⁰). Поскольку ранг матрицы системы (1.3) не может быть больше, чем rank(A), приходим к выводу, что card(S⁰) ≤ rank(A).

Утверждение 4. Если набору S соответствует совместная система (1.3), имеющая неединственное решение, тогда среди подмножеств набора S присутствуют простые наборы.

Доказательство. Из условий утверждения следует, что вектор правой части системы (1.3) принадлежит линейной оболочке столбцов A_j, j ∈ S, матрицы A, среди которых присутствуют линейно зависимые. Исключив часть столбцов, можно получить как минимум один линейно независимый набор A_j, j ∈ S', содержащий вектор правой части системы (1.3) в своей линейной оболочке. В таком случае система (1.3), соответствующая набору S', будет иметь единственное решение. Исключив из S' номера нулевых компонент вектора решения, согласно утверждению 2, получим простой набор S⁰ ⊂ S.

Утверждение 5. Множество простых решений системы линейных уравнений содержит все максимально разреженные решения этой системы. Множество структур максимально разреженных решений

является подмножеством множества Ω простых структур.

Доказательство. Максимально разреженным решением (sparsest solution) [25] недоопределенной системы линейных уравнений является решение с максимальным количеством нулевых элементов. Каждое такое решение системы (1.2) удовлетворяет определению решения с простой структурой. Действительно, каждое максимально разреженное решение системы (1.2) имеет структуру, которую нельзя упростить, обнулив в векторе решения некоторую ненулевую (активную) компоненту, поскольку максимально разреженное решение – это решение с максимально возможным числом нулевых компонент. Таким образом, максимально разреженное решение является простым решением. Однако обратное утверждение не верно: в общем случае не каждое простое решение оказывается максимально разреженным. Следовательно, совокупность максимально разреженных решений есть подмножество набора простых решений.

3.2. Приближенная линейная задача. Для заданного варианта структуры S система неравенств (1.5) эквивалентна системе b^– ≤ A_Sx_S ≤ b⁺, которую запишем в следующем виде:

где z⁺ и z⁻ – векторы-столбцы дополнительных переменных, условие (3.2) означает что все компоненты векторов z⁺ и z⁻ должны быть неотрицательными.

Пусть множество Ω* составляют простые наборы S, для которых могут быть выполнены условия (3.1), (3.2), т.е.

Утверждение 6. Множество простых структур решений системы линейных неравенств (1.5) тождественно множеству Ω*.

Доказательство. Вектором решения системы (1.5) и эквивалентной ей системы (3.1), (3.2) является вектор x. Поскольку дополнительные переменные z⁺, z⁻ отсутствуют в системе (1.5), они не входят в вектор решения. По этой причине структура S вектора решения x в рамках принятой формализации – структура решения системы (3.1), (3.2). Предположим, что некоторый набор S из Ω* не является простой структурой решения системы неравенств (1.5). Это может выражаться либо нарушением условий (3.1), (3.2), либо наличием более простого приемлемого набора S ' ∈ ζ*, такого, что S' ⊂ S. Однако, и то и другое противоречит определению набора Ω* и, следовательно, условиям утверждения. В случае, если существует простая структура S" решения системы неравенств (1.5), не включенная в Ω*, приходим к выводу, что для S " либо невыполнимы условия (3.1), (3.2), либо существует более простой набор S ' ∈ ζ*, такой, что S ' ⊂ S ". Однако в таком случае, структура S" не соответствует определению простой структуры.

3.3. Линейная задача с декларативными ограничениями.

Утверждение 7. Множество Ω** решений линейной задачи с декларативными ограничениями (1.1), (1.7) тождественно множеству Ω* \ψ.

Доказательство. Каждый элемент множества Ω* \ψ соответствует условиям (1.1), (1.7) и, следовательно, входит в Ω**, поскольку он соответствует требованиям (1.6) и отсутствует в списке ψ. Таким образом, набор Ω* \ψ целиком входит в Ω**. Покажем, что в Ω** нет структур, отсутствующих в Ω* \ψ. Предположим обратное. Пусть существует структура S_a ∈ Ω**, отсутствующая в Ω* \ψ. Структуру S_a можно получить добавлением одного элемента к некоторой неприемлемой структуре S_b, поскольку структура S_a является простой. Пусть структура S_b неприемлема только потому, что она не соответствует условию (1.6), т.е. S_b ∉ ψ. Тогда получаемая добавлением к S_b единственного элемента допустимая структура S_a принадлежит Ω* \ψ, поскольку в этом случае структуре S_a соответствует простое решение системы (1.5) и S_a, как и S_b, не входит в ψ. Однако факт S_a ∈ Ω* \ψ противоречит предположению об отсутствии S_a в Ω* \ψ. Пусть структура S_b неприемлема только потому, что она есть в списке ψ, т.е. S_b ∈ Ω* ∩ ψ. Тогда допустимая структура S_a не является простой, либо потому что, сохранив в ней добавленный элемент, можно исключить один из элементов S_b, получив в результате приемлемую структуру, либо потому что добавленному элементу будет соответствовать нулевое значение координаты в векторе решения. Это формально означает, что S_a остается неприемлемой структурой после такого добавления. Этот вывод противоречит сделанному выше предположению. Теперь допустим, что структура S_b неприемлема потому, что она не соответствует условию (1.6) и присутствует в списке ψ. Тогда допустимая структура S_a принадлежит Ω* \ψ. Вновь получаем противоречие: факт S_a ∈ Ω* \ψ противоречит предположению об отсутствии S_a в Ω* \ψ.

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

Утверждение 8. Структура, полученная упрощением неприемлемой структуры, неприемлема.

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

Утверждение 9. Структура, полученная добавлением элементов в приемлемую структуру, приемлема.

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

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

4.1. Решение строгой линейной задачи синтеза простых структур. Метод решения рассматриваемой задачи (1.1), (1.4), т.е. метод поиска простых структур решений системы линейных уравнений (1.2), сводится к следующему.

Шаг 1. Проверяем совместность системы (1.2). Если она несовместна, то приемлемых и, следовательно, искомых простых структур не существует, иначе переходим к шагу 2.

Шаг 2. Анализируем наборы S с числом элементов, равным рангу матрицы A системы (1.2), т.е. наборы, для которых card(S) = rank(A). Наборы S с числом элементов, превышающим rank(A), исключаются из рассмотрения на основе утверждения 3. Если анализируемому набору S соответствует система (1.3), имеющая единственное решение, которое не содержит нулей, то, согласно утверждению 1, набор S включаем в искомое множество Ω простых структур. Если анализируемому набору S соответствует единственное решение системы (1.3), в котором есть нулевые компоненты с номерами, составляющими множество S', то, согласно утверждению 2, в Ω включаем набор S\S'. Если анализируемому набору S соответствует несовместная система (1.3), то набор S запоминаем как неприемлемый. Если анализируемому набору S соответствует система (1.3), имеющая неединственное решение, тогда, согласно утверждению 4, среди подмножеств набора S присутствуют искомые простые наборы. В данном случае по отношению к полученной системе (1.3) рекурсивно применяем приведенный метод поиска простых структур. При выполнении рекурсии систему (1.3) рассматриваем как исходную систему (1.2). Анализируем только те наборы, которые не являются подмножеством либо надмножеством некоторого набора из Ω, либо подмножеством набора, оказавшегося неприемлемым. Если все наборы S, для которых card(S) = rank(A) проанализированы, поиск закончен.

В результате выполнения шагов 1 и 2 находим искомое множество Ω простых структур.

Согласно утверждению 5, найденное множество Ω содержит структуры всех максимально разреженных решений системы (1.2). Их можно выделить из Ω в результате упорядочивания наборов S ∈ Ω по значению их кардинального числа card(S). В набор Ω^# структур максимально разреженных решений включают все структуры S^# ∈ Ω, которым соответствует минимальное значение кардинального числа, т.е. такие S^#, для которых

4.2. Решение приближенной линейной задачи синтеза простых структур. Рассмотрим метод решения задачи (1.1), (1.6), т.е. метод поиска простых структур решений системы линейных неравенств (1.5).

Согласно утверждению 6, поиск простых структур решений системы линейных неравенств (1.5) сводится к поиску множества Ω*, определяемого формулами (3.3), (3.4).

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

Шаг 1. Находим множество Ω** простых структур решений системы уравнений (3.1). Для этого воспользуемся методом из разд. 4.1. При его реализации в качестве матрицы, вектора неизвестных и вектора правой части системы (1.2) используются матрица, вектор неизвестных и вектор правой части системы (3.1).

Шаг 2. Исключаем из Ω** все множества, для которых система (3.1), (3.2) несовместна. Это можно сделать, исключив из Ω** все наборы, соответствующие решениям системы (3.1) с отрицательным значением хотя бы одной координаты векторов z⁺, z⁻.

Шаг 3. Исключаем из Ω** все множества, для которых в Ω** может быть указан более простой набор, если при сравнении сложности наборов S ∈ Ω** игнорировать векторы z⁺, z⁻.

Остающиеся в Ω** структуры составляют искомый набор Ω* простых структур. Таким образом, выполнив шаги 1–3, получаем набор Ω*, являющийся решением задачи (1.1), (1.6).

4.3. Решение линейной задачи с декларативными ограничениями. Решение задачи (1.1), (1.7), т.е. линейной задачи с декларативными ограничениями, согласно утверждению 7, сводится к исключению из множества Ω* решений линейной задачи (1.1), (1.6) всех структур, указанных в списке ψ. С целью снижения трудоемкости поиска решения необходимо совместить формирование множества Ω* с исключением из него структур, указанных в списке ψ. Это можно сделать при реализации метода из разд. 4.1, используемого при поиске множества Ω** в методе из разд. 4.2. Для этого шаг 2 в методе из разд. 4.1 дополняется условием отсутствия анализируемого набора S в списке ψ. В итоге выполнения метода из разд. 4.2 с учетом указанной его модификации получаем набор структур Ω* \ψ, являющийся решением задачи (1.1), (1.7).

4.4. Решение задачи общего вида. Рассмотрим метод решения задачи (1.1), применение которого целесообразно в случае, когда описание условий приемлемости структуры S не относится к выделенным нами типовым описаниям (1.4), (1.6), (1.7), (3.4). Предлагаемый метод сводится к следующему.

Шаг 1. Находим множество ζ всех приемлемых структур. С этой целью проверяем приемлемость всех наборов S ⊆ {1, 2, …, n}, где n – размерность вектора решения. При этом полагаем, что задана процедура P(S) проверки приемлемости. Структуры, оказавшиеся неприемлемыми, запоминаем как элементы множества ϑ, а оказавшиеся приемлемыми, запоминаем как элементы множества ζ. Процедуру P(S) не выполняем в следующих случаях:

если набор S – подмножество некоторого элемента из ϑ и, следовательно, заведомо неприемлем, согласно утверждению 8,

если набор S – надмножество некоторого элемента из ζ и, следовательно, очевидно приемлем, согласно утверждению 9.

Шаг 2. Выделяем из множества приемлемых структур ζ искомое множество Ω простых структур. Для этого каждую структуру S из ζ сравниваем с остальными структурами из ζ. Если в ζ нет структуры более простой, чем S, то S – простая структура. Учитывая это, включаем ее в искомое множество Ω.

В результате получаем множество Ω, являющееся решением задачи (1.1).

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