Построение цикла и определение величины перераспределения груза. Выбор клетки, в которую необходимо поместить перевозку

Выбор клетки, в которую необходимо поместить перевозку

Проверка выполнения условия оптимальности для незанятых клеток

Просматриваем строки и для каждой незанятой клетки проверяем выполнения условия (6.13), т.е. суммируем потенциалы тех строк и столбцов, на пересечении которых стоит незанятая клетка. Если для всех незанятых клеток U_i + V_j ≤ C_ij, то по теореме (6.3) проверяемый план является оптимальным. Если для некоторых клеток U_i + V_j > C_ij, то план является неоптимальным. Тогда для каждой клетки, в которой не выполняется условие оптимальности, находим величину (U_i + V_j) – C_ij > 0.

Загрузке подлежит в первую очередь клетка, которой соответствует

max((U_i + V_j) – C_ij).

Для определения количества единиц груза, подлежащих перераспределению, отмечаем знаком «+» незанятую клетку, которую надо загрузить. Это означает, что клетка присоединяется к занятым клеткам. Занятых клеток стало m + n, поэтому появляется цикл, все вершины которого за исключением клетки, отмеченной знаком «+», находятся в занятых клетках, причем этот цикл единственный. Отыскиваем цикл и, начиная движение от клетки, отмеченной знаком «+», поочередно проставляем знаки «–» и «+». Затем находим = min X_ij, где X_ij – перевозки, стоящие в вершинах цикла, отмеченных знаком «–». Величина определяет, сколько единиц груза можно перераспределить по найденному циклу. Значение записываем в незанятую клетку, отмеченную знаком «+». Двигаясь по циклу, вычитаем из объемов перевозок, расположенных в клетках, которые отмечены знаком «–», и прибавляем к объемам перевозок, находящихся в клетках, отмеченных знаком «+». Если соответствует несколько минимальных перевозок, то при вычитании оставляем в соответствующих клетках нулевые перевозки в таком количестве, чтобы во вновь полученном опорном плане занятых клеток было m + n – 1.

Дата добавления: 2014-12-29