Методы построения исходного опорного плана

Теорема 2.9. Ранг матрицы из коэффициентов при неизвестных системы ограничений транспортной задачи равен m+n-1, где m и n - количество поставщиков и потребителей соответственно.

Из теоремы следует, что опорное решение задачи должно содержать m+n-1 базисных и mn-(m+n-1) небазисных, равных нулю неизвестных.

Определение. Циклом, или замкнутым контуром, называется последовательность клеток (i, j) таблицы 2.31 транспортной задачи, в которой каждые две рядом стоящие клетки находятся в одной строке или в одном столбце, при этом первая и последняя клетки совпадают.

Например, μ=[(1,2),(1,4),(3,4),(3,2),(1,2)] есть цикл (таблица 2.32).

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

Таблица 2.32. Цикл транспортной задачи

j i	1	2	3	4
1
2
3

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

Если в опорном решении транспортной задачи число отличных от нуля неизвестных равно m+n-1, то решение называется невырожденным, а если их меньше, то вырожденным.

Дата добавления: 2015-05-26