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

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

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

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

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

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

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