§ 2. Задачи транспортного типа

Теоремы 1.1 и 1.2 из § 1 дают необходимые и достаточные условия целочисленности для некоторых классов многогранных множеств. К сожалению, в общем случае эти условия весьма трудно проверяемы, так как матрица размером (здесь содержит миноров порядка (весьма большое число при близком к и достаточно большом Еще больше число миноров любого порядка данной матрицы — их будет

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

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

2.1. Рассмотрим (несколько обобщенную) систему условий транспортной задачи

Здесь может обозначать каждое из отношений Эти задачи отличаются от обычной транспортной задачи только наличием отношений вместо знаков равенства в (2.1) — (2.2).

Если перейти от двухиндексной к обычной нумерации переменных и занумеровать некоторым образом ограничения (2.1) и (2.2) (всего их будет то получим запись условий (2.1) — (2.3) в более стандартной для задач линейного программирования форме

Здесь любое из отношений

Замечание 2.1. При любой нумерации переменных и ограничений матрица условий транспортной задачи обладает следующими свойствами:

1) равно или

2) В каждом столбце матрицы А содержится ровно две единицы.

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

Определение 2.1. Матрицу

назовем -матрицей, если:

2) в каждом столбце матрицы А содержится не более двух ненулевых элементов.

Задачу линейного программирования с ограничениями назовем задачей транспортного типа, если матрица А является -матрицей. Здесь — любое из отношений

2.3. Чтобы перейти непосредственно к исследованию многогранников задач транспортного типа, введем еще некоторые определения.

Определение 2.2, Две строки -матрицы А назовем согласованными, если для каждого столбца для которого имеем:

Определение -матрицу назовем согласованной, если любые две строки ее согласованы.

Определение 2.4. Две матрицы (А и А) с одинаковым числом строк и столбцов назовем эквивалентными, если равна А, либо может быть получена из А изменением знака некоторых строк (обозначение

Замечание 2.2. Из приведенных определений следует, что если две матрицы эквивалентны, то:

1) они обе одновременно являются или не являются -матрицами,

2) они обе одновременно унимодулярны или не унимодулярны.

2.4. В § 1 (теорема 1.2) было показано, что целочисленность многогранников эквивалентна унимодулярности матрицы А. В начале этого параграфа было отмечено, что проверка на унимодулярность в общем случае весьма трудна. Однако для -матриц проверка на унимодулярность может быть, как показывает следующая теорема, сильно облегчена.

Теорема 2.1. Для того чтобы -матрица пбыла унимодулярной, необходимо

и достаточно, чтобы нашлась согласованная матрица эквивалентная А.

Переходив к доказательству теоремы 2.1.

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

Для проведем то же рассуждение и т. д. В конечном счете могут возникнуть три случая:

в) в каждом столбце матрицы

ровно два ненулевых элемента,

г) матрица является подматрицей матрицы А и, следовательно, согласованной -матрицей. В случаях 1) и 2) теорема верна. Остается разобрать случай 3). Введем обозначения

Ясно, что В — согласованная -матрица, в каждом столбце которой содержится ровно два ненулевых элемента. Очевидно, что

Так как В — согласованная -матрица, в каждом столбце которой содержится ровно два ненулевых элемента, то для любого

Из (2.6) и (2.7) получаем

Достаточность доказана.

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

какова бы ни была матрица найдется такая последовательность пар индексов

что:

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

Таким образом, после некоторой перенумерации строк и столбцов матрица будет иметь вид

где

(см. скан)

Из (2.9) вытекает, что матрица А не является униодулярной. Следовательно, не является унимодулярной и матрица что противоречит условию. Необходимость доказана.

2.7. Обычно условие унимодулярности -матриц формулируют следующим образом.

Теорема Для того чтобы -матрица была унимодулярной, необходимо и достаточно, чтобы строки матрицы А можно было разбить на два класса обладающих следующими свойствами:

а) Если строки принадлежат одному и тому же классу и для некоторого имеем то

б) Если строки принадлежат разным классам, и для некоторого имеем

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

Теперь выведем условия теоремы 2.1 из условий теоремы Пусть существует разбиение на классы удовлетворяющее условиям а) и б) теоремы Образуем матрицу эквивалентную матрице следующим образом: строка матрицы равна соответствующей строке матрицы если последняя входит в строка матрицы А получена изменением знака соответствующей строки матрицы если последняя попадает в класс Очевидно, что матрица согласована.

2.8. Из теоремы непосредственно следует унимодулярность матрицы транспортной задачи (при любой нумерации переменных и ограничении).

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

Отсюда и из теорем 1.1, 1.2 получается

Следствие 2.1. Многогранник планов (2.1)-(2.3) транспортной задачи является целочисленным при любых целых

2.9. Изложим алгоритм проверки -матрицы А на унимодулярность, основанный на теореме Нам понадобится понятие согласованности (см. определение 2.2), а также некоторые новые понятия.

Определение 2.5. Две строки матрицы А назовем строго согласованными, если эти строки согласованы (см. определение 2.2) и существует такой столбец что

Определение 2.6. Две разные строки назовем строго несогласованными, если строки и строго согласованы.

Определение 2.7. Две строки назовем несогласуемыми, если существуют такие столбцы что

Определение 2.8. Две разные строки назовем связанными, если найдется такой столбец что

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

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

Разобьем множество строк матрицы на непересекающиеся множества обладающие

следующим свойством: если то Это разбиение осуществляется следующим образом: полагаем где произвольная строка из Строим до тех пор, пока не получим первый раз пустое множество 1). Тогда полагаем

Если то и процесс разбиения завершен. Если то заменяем на и аналогичным образом продолжаем процесс разбиения.

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

2.11. Переходим непосредственно к изложению алгоритма.

0-й шаг. Задана -матрица

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

а) Имеются Каждая строка зачислена в один из классов: (1) или Этот класс обозначаем через

Находим

Если пусто, то матрица унимодулярна. Если не пусто, то для каждого находим (это, очевидно, непустое множество).

(кликните для просмотра скана)

б) Для каждого и каждого полагаем

в) Если найдется хотя бы одна строка такая, что среди чисел имеются разные, то матрица не унимодулярна.

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

д) Если среди строк зачисленных в один и тот же класс, найдутся две строго несогласованные строки, то матрица не унимодулярна. Если таких строк нет, то переходим к .

е) Если среди строк найдутся две строго согласованные строки, зачисленные в разные классы, то матрица не унимодулярна. Если таких строк нет, то переходим к шагу. Блок-схема алгоритма приведена на рис. 17.2.1.

2.12. Приведем численный пример.

Требуется проверить на унимодулярность матрицу, помещенную на стр. 339 (в пустых клетках стоят нули).

Здесь

т. е. матрица состоит ровно из одного блока.

2) Проверкой убеждаемся, что среди строк нет несогласуемых.

3) Воспользуемся множествами , построенными в п. 1).

(см. скан)

Выписываем Полагаем

Выписываем Так как каждая из строк 8, 3, 2 строго несогласована со строкой 1, полагаем Проверяем строки 8, 3, 2 — среди них нет строго несогласованных строк.

Выписываем Строим функцию связаны).

(см. скан)

Так как для каждого фиксированного принимает лишь одно значение то полагаем

Строки 6 и 7 не связаны, так что отнесение их к классам и (1) соответственно не создает противоречия.

Выписываем Строим функцию связаны).

(см. скан)

Так как для каждого фиксированного принимает лишь одно значение то полагаем

Строки 4 и 5 не связаны, так что отнесение их к классам (1) и соответственно не создает противоречия.

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