Методы решения задачи оптимального закрепления операций за станками

Проверим возможность уменьшения суммарных затрат времени на проведение операций. С этой целью для каждой свободной от операции клетки определяется величина Δ ij, характеризующая изменение суммарных затрат, при условии включения в план операции Хij=1 от поставщика Аi к потребителю Вj.

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

Величина Δ ij называется оценкой свободной клетки (или характеристика).

В исходном решении задачи имеются клетки свободные от операций.

Необходимо вычислить значение оценок Δij для этих свободных от операций клеток. С этой целью для каждой свободной клетки составляется означенный цикл перерасчета (или замкнутая цепь, круг, кольцо, контур и т.д.). Причем одна из вершин находится в свободной от операции клетке, в той, для которой определяется оценка Δij . Все другие вершины находятся в базисных клетках, т.е. клетках, занятых операциями.

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

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

Следующий этап решения задачи заключается в улучшении опорного плана.

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

Практическая реализация задачи оптимального закрепления операций за станками