double arrow

Корректировка плана перевозок

Использование потенциалов каждый раз переводит ТЗ к новой задаче с другой матрицей стоимостей. На каждом шаге идет проверка плана на оптимальность по выражениям (1.37), (1.38) до тех пор, пока план не окажется оптимальным. Если в матрице стоимостей среди незагруженных клеток (ij) имеются отрицательные (9), то перераспределение грузопотоков может быть выполнено с помощью цикла пересчета или просто цикла.

Циклом в таблице стоимостей в ТЗ называют ломаную линию, вершины которой располагаются в загруженных клетках таблицы, а звенья - вдоль строк и столбцов таблицы, причем в каждой вершине цикла встречаются ровно два звена, одно из которых находится в строке, а другое в столбце. Число вершин в цикле четно. Если ломаная линия, образующая цикл, пересекается, то точки самопересечения не являются вершинами (рис. 1.10).

Цикл образуется из загруженных и одной незагруженной клетки. Для построения цикла выбирают отрицательную стоимость максимальную по модулю Cij* = - max . Используя эту и другие загруженные клетки преобразованной матрицы, строят цикл, пользуясь вышеописанными правилами.

Затем, начиная с отрицательного элемента (Cij* = - max ), нумеруют вершины цикла по порядку по часовой или против часовой стрелки. Вид цикла может быть самым разным. Примеры некоторых циклов показаны на рис. 1.10.

Цикл обладает свойством не нарушать ограничивающих условий ТЗ. Итак если из всех клеток с четными номерами вершин перенести какую-нибудь поставку, то сумма грузопотоков во всех строках и столбцах не изменится: в клетке с четной вершиной уменьшится, а в нечетной увеличится на то же самое значение. Следовательно, цикл используется для построения нового плана перевозок в ТЗ.

Рис. 1.10.


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: