Опорное решение транспортной задачи

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

Ввиду того, что ранг системы векторов-условий транспортной задачи равен m + n - 1, опорное решение не может иметь отличных от нуля координат более m + n - 1. Число отличных от нуля координат невырожденного опорного решения равняется m + n - 1, а для вырожденного опорного решения – меньше m + n - 1.

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

Любое допустимое решение транспортной задачи можно записать в ту же таблицу, что и исходные данные. Клетки таблицы транспортной задачи, в которых находятся отличные от нуля или базисные нулевые перевозки, называются занятыми, остальные – незанятыми или свободными. Клетки таблицы нумеруются так, что клетка, содержащая перевозку , т. е. стоящая в i-й строке, j-м столбце, имеет номер (i, j). Каждой клетке с номером (i, j) соответствует переменная , а этой переменной соответствует вектор-условий .

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

Цикл изображают в таблице транспортной задачи в виде замкнутой ломаной линии. В цикле любая клетка является угловой, в которой происходит поворот звена ломаной линии на 90°. Простейшие циклы изображены на рис. 6.1, где звездочкой отмечены клетки таблицы, включенные в состав цикла.

Рис 6.1

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

Доказательство. Необходимость. Пусть система, состоящая из n векторов

линейно зависима. Тогда существует такой ненулевой набор чисел , что справедливо равенство

. (6.10)

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

В выбранной таким образом последовательности векторов должен найтись вектор , у которого второй индекс совпадает со вторым индексом первого вектора. Данной последовательности векторов соответствует совокупность клеток таблицы транспортной задачи

( ), ( ), ( ), …, ( ),

которая образует цикл.

Достаточность. Пусть из соответствующих векторам клеток (i, j) выбрана последовательность клеток, образующих цикл ( ), ( ), ( ), ..., ( ). Нетрудно видеть, что

.

Отсюда следует линейная зависимость рассматриваемой системы векторов.

Следствие. Допустимое решение транспортной задачи i = 1, 2, ... , m; j = 1, 2, ..., n является опорным тогда и только тогда, когда из занятых им клеток таблицы нельзя образовать ни одного цикла.

Метод вычеркивания

Метод вычеркивания позволяет проверить, является ли данное решение транспортной задачи опорным.

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

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

Ниже приведены примеры "вычеркиваемого" (опорного) и "невычеркиваемого" (неопорного) решений:

вычеркиваемое невычеркиваемое