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

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

5. Логические определители с ограничениями на область

5.1. Вводные замечания

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

5.2. Понятие логического определителя с ограничениями на область

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

(т, п). Эти пути можно представить в виде

Пусть М - общее число таких путей. Обозначим через сумму элементов матрицы А, расположенных вдоль q-го пути и через — сумму ее элементов, расположенных вне q- го пути. Будем назы­вать их ступенчатыми суммами первого и второго рода.

Определение 5.1. Выражения вида

(5.1)

(5.2)

т. е. дизъюнкцию (конъюнкцию) БЛ всех ступенчатых сумм первого (вто­рого) рода матрицы А назовем соответственно ЛО первого (второго) рода с ограничениями для матрицы А. Будем также называть их дизъюнк­тивным ЛО и конъюнктивным ЛО.

Определение 5.2. Выражение вида

(5.3)

т. е. сумму всех элементов матрицы А назовем суммирующим ЛО матри­цы А. Каждая матрица А всегда имеет непустые множества сумм и а отсюда и ЛО Очевидно и существование у любой матрицы AЛОА+.

5.3. Свойства логических определителей

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

Лемма 5.1. Общее для всех элементов слагаемое можно вынести за знак ЛО с соответствующим коэффициентом:

(5.4) (5.5)

Доказательство. Имея в виду, что каждая суммасодержит

m + п — 1 слагаемыхи учитывая распределительный закон (1.37),

найдем соотношение

совпадающее с (5,4). Соотношение (5.5) для конъюнктивного ЛО дока­зывается аналогично с учетом того, что каждая сумма содержит mп — m — п + 1 слагаемых и учитывая распределительный закон (1.38). Аналогично доказывается соотношение (5.5) для суммирующего ЛО.

Лемма 5.2. Общий для всех элементов положительный сомножитель можно вынести за знак ЛО

(5.6) Доказательство. Имеем, учитывая распределительный закон (1.45)

что совпадает с первым соотношением (5.6). Доказательство второго и третьего соотношений аналогично (используется закон (1.46)).

Лемма 5.3. Общий для всех элементов отрицательный сомножитель можно вынести за знак ЛО в виде

(5.7)

где ∆ — размах ступенчатых сумм первого рода, равный

(5.8)

Доказательство. С учетом распределительного закона (1.48) и формулы (5.8) имеем

Аналогично, учитывая закон (1.47), формулу (5.8) и равенство размахов ступенчатых сумм первого и второго рода, найдем

В частном случае при с = -1 соотношения (5.7) принимают вид

(5.9)

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

Лемма 5.4. Слагаемые угловых элементов а11 и атп ЛО можно вынес­ти за знак ЛО

(5.10)

Доказательство. Угловые элементы, стоящие в (1,1) - й и (т, n)-й клетках левого ЛО, входят в каждую сумму вида Отсюда, учитывая распределительный закон (1.37), получаем выражение левой части (5.10)

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

Частным случаем формулы (5.10) являются формулы

(5.11)

показывающие, что угловые элементы а11 и атп можно вынести за знак дизъюнктивного ЛО.

Лемма 5.5. Слагаемые угловых элементов а11 и атп конъюнктивного ЛО можно вычеркнуть, не изменив величины ЛО

(5.12)

Доказательство. Угловые элементы, стоящие в клетках (1,1) и (m, п) левого ЛО, не входят ни в одну сумму вида Поэтому по

определению (5.2) конъюнктивного ЛО любое изменение величин этих элементов не влияет на величину ЛО.

Частным случаем соотношения (5.12) являются соотношения

(5.13)

показывающее, что угловые элементы а11 и атп ЛО можно вычеркнуть, не изменив величины ЛО. Лемма 5.6. Соотношение дизъюнктивного, конъюнктивного и сумми­рующего ЛО одной и той же матрицы А дается формулой

(5.14)

Доказательство. Учитывая очевидное равенство

и распределительные законы (1.37), (1.48), найдем

что совпадает с (5.14).

Лемма 5.7. Пусть ai, аj - есть пара строк m × п-матрицы А, симметричных относительно середины А, т. е. и аi, аj — пара симметричных столбцов матрицы А (для них i+j=n+ 1). Тогда перестановка местами каждой пары симметричных строк и каждой пары симметричных столбцов не меняет величин ЛО Величина ЛО А+ не меняется при любой перестановке строк или столбцов.

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

преобразуется в равную ей ступенчатую сумму матрицы В