Задачи линейного программирования транспортного типа. Горячев Л.В. - 7 стр.

                                                                                                               7

   Из приведенного выше примера Т.З. для m = 2 и n = 3 видна зависимость между условиями-
равенствами. Действительно, сложив первые два условия и вычтя из полученного результата сле-
дующие два условия, мы получим последнее уравнение. Таким образом, каждое условие-равенство
является следствием остальных условий.
   Теперь убедимся, что число независимых условий-равенств Т.З. равно m + n − 1. Для это-
го достаточно найти в матрице A квадратную подматрицу порядка m + n − 1 с определите-
лем, не равным нулю. Такую подматрицу нетрудно найти в матрице, составленной из векторов
A1n , A2n , . . . , Amn , A11 , A12 , . . . , Ai n−1 . Первые m + n − 1 строк такой матрицы образуют верхнюю
треугольную подматрицу с диагональными элементами, равными 1, и определителем, отличным от
нуля. Таким образом, в системе условий-равенств Т.З. одно условие излишнее и его можно отбро-
сить. Однако это обычно не делают, чтобы не нарушать симметричность форм задачи.
   Ранг матрицы условий A определяет число линейно-независимых векторов, составляющих базис
Т.З. Таким образом, базис Т.З. состоит из m + n − 1 вектора, а невырожденный опорный план
содержит m + n − 1 положительных компонент. Сказанное позволяет сформулировать:
   Утверждение. Если все ai и bi — неотрицательные целые числа, то любой опорный план является
целочисленным.
   Доказательство. Оно вытекает из того, что ранг матрицы A условий Т.З. равен m + n − 1,
а система базисных векторов содержит треугольную подматрицу m + n − 1 – го порядка. Данное
утверждение сформулируем в несколько иной форме, имеющей многочисленные теоретические при-
ложения.
   Теорема. Любой минор матрицы A равен 0 либо ±1.
   Доказательство. Применим метод математической индукции. Для миноров первого порядка
утверждение очевидно, так как элементы A — нули и единицы. Допустим, что теорема верна для
миноров матрицы A порядка k − 1, и докажем ее справедливость для миноров порядка k. Разделим
обе строки матрицы A на две группы: первые m строк отнесем к 1 – ой группе, а следующие n —
ко 2 – ой. Каждый столбец A содержит одну единицу среди строк 1 – ой группы. Пусть k — про-
извольный минор порядка k. Каждый столбец k содержит либо две единицы, либо одну единицу,
либо будет нулевым. В последнем случае, очевидно, k = 0. В случае, если хотя бы в одном столбце
k содержится ровно одна единица, разлагая минор по этому столбцу, получаем, что k = ±k−1 ,
где k−1 — некоторый минор матрицы A порядка k − 1. Если же во всех столбцах k — по две еди-
ницы, то среди строк k имеются представители как первой, так и второй групп строк матрицы A.
Выбирая любую строку k из первой группы, прибавляем к ней остальные строки из этой группы.
Получаем строку, состоящую из единиц. Аналогично поступаем с одной из строк второй группы и
получаем еще одну строку из единиц. Проведенные преобразования не меняют величину k . Итак,
k совпадает с определителем, обладающим двумя одинаковыми строками, и, следовательно, равен
нулю.
   Анализ Т.З., как и любой части ЛП, существенно опирается на результаты теории двойствен-
ности. Введем вектор W (v1 , v2 , . . . , vn , −u1 , −u2 , . . . , −um )T , где vj — двойственные переменные, от-
вечающие условиям (8), −ui — отвечают условиям (7), i = 1, 2, . . . , m, j = 1, 2, . . . , n. Знак минус
перед ui принят ради удобства интерпретации задачи. Переменные vj и −ui называют потенциалами
столбцов и строк соответственно.
   Согласно общему правилу построения двойственных задач ЛП, задача, двойственная к Т.З.,
имеет вид
                                                     
 n         m
                                                                 

                                                         bj vj −   ai ui − max                               (10)
                                          j=1            i=1
при условии
                               vj − ui ≤ cij ,     i = 1, 2, . . . , m, j = 1, 2, . . . , n                 (11)
Ограничения на знаки двойственных переменных отсутствуют, поскольку условия (7)–(8) прямой
задачи имеют вид равенств. Согласно общим свойствам пар двойственных задал ЛП, для любых
планов X = xij mn и W (v1 , v2 , . . . , vn , −u1 , −u2 , . . . , −um )T прямой и двойственной задач, соответ-
ственно, справедливо неравенство
                                     m 

                                     
 n                    n
                                                            
               n
                                                                            

                                                cij xij ≥         bj vj −         ai ui
                                      i=1 j=1               j=1             i=1