Операция 3.1. Построение цепи (контура, цикла) перераспределения поставок

Улучшение плана осуществляется по одной из небазисных клеток, для которой условие оптимальности оказалось невыполненным. В нашем плане имеется четыре такие клетки. Выбираем одну из них, для которой условие оптимальности не выполняется в наибольшей степени. В нашем плане это клетка А₂В₄. Для нее условие оптимальности не выполнено на 4 единицы (10 – 0 – 6 = 4). Для этой клетки строим цепь перераспределения поставок. Цепь перераспределения поставок – это такая замкнутая ломаная линия, которая проходит по клеткам матрицы ходом шахматной ладьи. В вершинах контура обязательно лежит одна небазисная клетка (несоответствующая условию оптимальности, найденная ранее), а остальные соответствуют только базисным клеткам. Линии контура могут пересекаться. Для небазисной клетки А₂В₄ цепь будет проходить по клеткам А₁В₄, А₁В₃, А₂В₃ (табл. 3.7).

Таблица 3.7 - Возможные варианты построения цикла перераспределения

В нашем случае форма цепи простая. Однако цепь может иметь любую форму, в том числе и причудливую (см. табл. 3.7). Её нужно научиться отыскивать, используя эвристические подходы. При этом необходимо учитывать, что каждая небазисная клетка транспортной матрицы обязательно имеет одну цепь перераспределения поставок.