Переход от одного опорного решения к другому

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

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

Доказательство. Опорное решение занимает N=m+n-1 клеток таблицы, которым соответствуют линейно независимые векторы-условия. Если же к занятым клеткам присоединить одну свободную, то соответствующие им m+n векторов линейно зависимы, и по той же теореме существует цикл, содержащий эту клетку. Предположим, что таких циклов два (i₁,j₁), (i₁,j₂), (i₂,j₂), …, (i_k,j₁) и (i₁,j₁), (i₂,j₁), …, (i₁,j_i). Тогда, объединив клетки обоих циклов без свободной клетки (i₁,j₁), получим последовательность клеток (i₁,j₂), …, (i_k,j₁), (i₂,j₁), …, (i₁,j_i), которые образуют цикл. Это противоречит линейной независимости векторов-условий, образующих базис опорного решения. Следовательно, такой цикл единственный.