Означенный цикл

Цикл называется означенным, если его угловые клетки пронумерованы по порядку и нечетным клеткам приписан знак «+», а четным – знак «-» (рис 2.) 1 2

+ -

- 5 +

+ -

3 4

рис 2.

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

Теорема7. Е сли таблица транспортной задачи содержит опорное решение, то при сдвиге по любому циклу, содержащему одну свободную клетку, на величину = получится опорное решение.

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

В каждой строке и в каждом столбце таблицы, входящих в цикл, две и только две клетки, одна из которых отмечена знаком «+», а другая - знаком «-». Поэтому в одной клетке объем перевозки увеличивается на , а в другой уменьшается на , при этом сумма всех перевозок в строке (или столбце) таблицы остается неизменной. Следовательно, после сдвига по циклу по-прежнему и запасы всех поставщиков вывозятся полностью, и запросы всех потребителей удовлетворяются полностью. Так как сдвиг по циклу осуществляется на величину = , то все объемы перевозок будут неотрицательными. Следовательно, новое решение является допустимым.

Если оставить свободной одну из клеток с нулевым объемом перевозки, соответствующих , то число занятых клеток будет равно N=m+n-1. Так как цикл единственный, то удаление из него одной клетки разрывает его. Цикл из оставшихся занятых клеток образовать нельзя, соответствующие векторы-условия линейно независимы, а решение является опорным.