Циклы как метод перехода к лучшей вершине

Циклом называется замкнутая ломанная, соединяющая несколько выбранных клеток(перевозок x_ij), которая в каждой выбранной клетке поворачивает на 90°. Вершины цикла (выбранные клетки) помечаются знаками «+» и «–», причем знаки всегда строго чередуются, т.е. всегда соседние по ходу цикла вершины помечены разными знаками. Перенести k единиц груза по циклу означает в положительных вершинах увеличить x_ij на k единиц, а в отрицательных вершинах уменьшить x_ij на k единиц. Поскольку цикл помечен таким образом, что в каждой строке и каждом столбце количество плюсов и минусов одинаково, переброска груза по циклу не нарушает условий баланса. Цена цикла равна сумме цен помеченных ячеек (с учетом знака) на величину переброски k.

Цикл всегда строится таким образом, что он начинается в пустой ячейке, которая помечается знаком «+» а все остальные вершины цикла находятся в заполненных ячейках (базисные переменные). Если реализация цикла приводит к уменьшению цены перевозок, то нам выгодно переместить по циклу максимально большое количество груза, чтобы достичь максимального эффекта. Ограничением на эту величину является самая малая из тех базисных переменных, которые помечены знаком «–». Если попытаться переместить больше, то в этой ячейке x_ij станет отрицательным, но если переместить ровно столько, сколько есть в самой «малой» ячейке, помеченной минусом, то в итоге в этой ячейке x_ij станет нулем. Т.е. мы одну небазисную переменную сделали базисной (положительной) а одну базисную небазисной (нулевой). Количество базисных ячеек не изменилось – значит мы из одной вершины перешли в другую вершину