Циклы таблицы перевозок и их свойства.

Определение. Циклом таблицы перевозок называется замкнутая ломаная линия, вершины которой находятся в клетках таблицы перевозок, а звенья расположены вдоль строк и столбцов таблицы. Причём в каждой вершине встречаются ровно два звена, одно из которых расположено по строке, другое – по столбцу таблицы (рис. 13, 14, 15).

Замечание. Цикл может иметь точки самопересечения, которые не являются вершинами (рис. 15).

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

Определение. Цикл назовём означенным, если каждой его вершине приписан знак «+» или «-», причём так, что знаки чередуются (рис. 16).

Свойства циклов таблицы перевозок:

1) Никакие три последовательные вершины цикла таблицы перевозок не могут находиться в одной строке (столбце).

2) Число вершин цикла перевозок чётно.

3) В каждой строке (столбце) таблицы перевозок число положительных вершин означенного цикла равно числу отрицательных вершин.

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

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

Теорема (о сдвиге по циклу). Сдвиг по циклу в таблице перевозок преобразует любуе решения системы ограницений транспортной задачи (23), (24) также в решение этой системы.

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

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

Теорема. Для любой свободной клетки в таблице перевозок существует, и притом единственный, цикл пересчёта.

Замечание. В дальнейшем цикл пересчёта свободной клетки будем считать означенным, причём свободной клетке будем приписывать знак «+».