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

Числа аi и bj; называются потенциалами.

Сформулированная теорема позволяет построить алгоритм нахождения решения задачи закрепления операций за станками. Он состоит в следующем. Пусть одним из рассмотренных выше методов найден опорный план задачи. Для каждого из станков и операций определяют потенциалы аi и bj . Эти числа находят из системы уравнений

(10)

где сij - производительность, стоящая в заполненных клетках таблицы условий задачи.

Так как число заполненных клеток равно п+m-1, то система (10) с п + m неизвестными содержит n + m-1 уравнений. Поскольку число неизвестных превышает на единицу число уравнений, одно из неизвестных можно положить равным произвольному числу, например a1 = 0, и найти последовательно из уравнений (10) значения остальных неизвестных. После того как все потенциалы найдены, для каждой из свободных клеток определяют числа

.

Если среди чисел аij нет отрицательных, то найденный опорный план является оптимальным. Если же для некоторой свободной клетки аij > 0, то исходный опорный план не является оптимальным и необходимо перейти к новому опорному плану. Для этого рассматривают все свободные клетки, для которых aij > О, и среди данных чисел выбирают максимальное. Клетку, которой это число соответствует, следует заполнить.

Заполняя выбранную клетку, необходимо изменить объемы поставок, записанных в ряде других занятых клеток и связанных с заполненной так называемым циклом. Циклом в таблице условий транспортной задачи называется ломаная линия, вершины которой расположены в занятых клетках таблицы, а звенья-вдоль строк и столбцов, причем в каждой вершине цикла встречается ровно два звена, одно из которых находится в строке, а другое - в столбце, где линия совершает поворот на 90°. Примеры некоторых циклов показаны на рис.1.

1) 2) 3)

Рис.1. Возможные циклы

Если ломаная линия, образующая цикл, пересекается, то точки самопересечения не являются вершинами.

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

1. Каждой из клеток, связанных циклом с данной свободной клеткой, приписывают определенный знак, причем свободной клетке - знак плюс, а всем остальным клеткам - поочередно знаки минус и плюс (будем называть эти клетки минусовыми и плюсовыми);

2. В данную свободную клетку переносят меньшее из чисел xij , стоящих в минусовых клетках. Одновременно это число прибавляют к соответствующим числам, стоящим в плюсовых клетках, и вычитают из чисел, стоящих в минусовых клетках. Клетка, которая ранее была свободной, становится занятой, а минусовая клетка, в которой стояло минимальное из чисел xij считается свободной.

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

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