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

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

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

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

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

Циклом называется такая последовательность клеток таблицы транспортной задачи (i₁,j₁), (i₁,j₂), (i₂,j₂), …, (i_k,j₁), в которой две и только две соседние клетки расположены в одной клетке или столбце, причем первая и последняя клетки также находятся в одной строке или столбце.

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

* * * * * *

* * * *

* * * * * *

рис1.

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

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

. (10)

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

В выбранной подобным образом последовательности векторов должен найтись вектор , у которого второй индекс совпадает со вторым индексом первого вектора. Данной последовательности векторов соответствует совокупность клеток таблицы транспортной задачи (i₁,j₁), (i₁,j₂), (i₂,j₂), …, (i_k,j₁), которая образует цикл.

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

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

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