Дискретно-непрерывная математика (стр. 107 )

3) уменьшением границы на величину левой части ограничений в миноре. Таким образом,

(4.61)

Теорема 4.11. Произвольный ЛО (4.51) можно разложить по любой совокупности столбцов представив его в виде дизъюнкции БЛ сумм всех миноров, образованных на базе множества Вr, и их логи­ческих дополнений:

(4.62)

Доказательство. В определении (4.51) q-ю сумму ЛО можно разбить на две:

Здесь р и s - номера частичных сумм правой части, соответствующие номе­ру q полной суммы левой части. Учитывая эти разбиения, распишем ЛО ввиде

Вынеся за знак не зависящее от s первое слагаемое, получим

Первое слагаемое в скобке есть, согласно (4.60), минор а вто-

рое, согласно (4.61), - логическое дополнение этого минора Таким образом. полученное соотношение есть развернутая запись разложения (4.62).

В частном случае при формула (4.62) переходит в (4.59). Раз-

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

(4.63)

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

Оценим сложность представления М × Р-ЛО, полученного последователь­ным разложением по столбцу (4.59). Полагая, что в процессе разложения не появляются фиктивные ЛО (это завышает оцениваемую сложность), получим из (4.59) уравнение для числа N(P) элементарных операций в представлении ЛО в виде (4.36) с начальным условием N(1) = 2М — 1, вытекающим из (4.63). Решение этого уравнения

(4.64)

Оценим еще сложность представления М × Р-ЛО, полученного последова­тельным разложением по совокупности r столбцов (4.62). При фиксирован­ном множестве Вr этих столбцов имеется Мr различных миноров с r столбцами (в представлении каждого содержится 2r элементарных опера­ций +) и столько же соответствующих им логических дополнений с Р - r столбцами. Отсюда получаем уравнение для искомой сложности

(4.65)

Пусть аналогично уравнению (4.47):

1) r фиксировано и не зависит от Р;

2) Р имеет вид

3) N(r) задано. Тогда из (4.65) последовательно найдем

(4.66) Заменив в (4.66) kr на Р, после упрощений получим

Сравнив оценки (4.64) и (4.66), заключаем, что разложение по совокуп­ности r столбцов приводит к гораздо более простому представлению ЛО, чем разложение по столбцу. Оба дают существенно более простое выраже­ние ЛО, чем непосредственное его выражение по определению (4.51).

4.11. Вычисление логических определителей

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

определенному ограничению. Поэтому понятие вычисления ЛО с ограни­чениями может включать отыскание номера q (поэлементного состава) максимальной или минимальной суммы которой равен наш ЛО; эту сумму назовем определяющей.

Методически проще всего вычислять ЛО по их определениям (4.2), (4.3), (4.24), (4.25), (4.38), (4.39), (4.51), (4.52), рассматривая последние как формулы раскрытия ЛО. Однако сложность такого вычисления с увеличе­нием размеров ЛО растет слишком быстро. Поэтому будем вычислять ЛО с помощью их разложения.

Дизъюнктивный ЛО первого рода вычисляется по разложению (4.20), а конъюнктивный ЛО — по двойственному к (4.20) разложению (заменяется на). Отсюда следует, что

(4.67)

где а*j—экстремальный элемент j-го столбца: максимальный для ЛО и минимальный для ЛО Сложность такого способа вычисления ЛО равна выражению (4.21). Из него следует возможность вычисления ЛО практи­чески неограниченных размеров M× P.

Дизъюнктивный ЛО второго рода можно вычислить последователь­ным разложением по столбцу (4.30), а конъюнктивный — по двойствен­ному разложению. При этом для отыскания определяющей суммы ЛО следует запоминать элементы , по которым идет разложение. Такой способ вычисления ЛО, как видно из оценки его сложности (4.37), приго­ден для ЛО большой высоты М, но ограниченной ширины Р.

Пример 4.2. Вычислим ЛО

Шаг 1. Разлагаем по первому столбцу:

Шаг 2. Разлагаем логические дополнения по первому столбцу:

Новые логические дополнения — ЛО-столбцы, вычисляемые непосредствен­но по определению ЛО (4.24), (4.35):

Шаг 3. Подставив последующие выражения в предыдущие, найдем

Для получения численного значения ЛО остается подставить числен­ные значения его элементов и выполнить операции Например, для

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

Разлагать ЛО можно не аналитически (как в примере 4.2), а с помощью

дерева. Корнем этого дерева служит сам ЛО а последовательно удаляю­щимися от него вершинами — элементы получаемые в результате после­довательных шагов разложения. Найдя ветвь дерева с максимальной сум­мой элементов, тем самым получим определяющую сумму ЛО. Численное значение этой суммы и есть численное значение ЛО.

Пример 4.3. Для ЛО из примера 4.2 дерево разложения имеет вид

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

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