Признак оптимальности

При перемещении q по циклу пересчета увеличиваются на эту величину значения переменных X_ij в четных вершинах, а следовательно, увеличиваются и затраты на перевозку на q C_ij. Одновременно уменьшаются на q переменные в нечетных вершинах и на q C_ij соответствующие им затраты. Отсюда следует, что значение критерия в новом, (k+ 1)-м решении можно определить по критерию в исходном решении и изменениям в клетках цикла:

или , (15)

где (16) Δ _ij – относительная оценка переменной X_ij, на которой построен цикл. Для базисных переменных оценка всегда равна нулю. Δ _ij показывает, как изменится критерий (в какую сторону и насколько) при перемещении по циклу единицы груза ( q =1). Если Δ _ij> 0, то введение X_ij в число базисных приведет к уменьшению суммарных затрат. Если же Δ _ij< 0, критерий возрастет, что противоречит цели. Решение нельзя улучшить, когда среди оценок нет положительных, и поэтому признак оптимальности имеет вид " Δ _ij£ 0. (17) Если признак не выполняется, то новое решение целесообразно строить на основе клетки с максимальной оценкой.

Поставим в соответствие каждому пункту отправления сбалансированной задачи некоторую величину U_i, i =1, 2, …, m, а каждому пункту назначения – V_j, j =1, 2, …, n так, чтобы для базисных клеток выполнялись равенства V_j - U_i=C_ij, i j Î б аз. (18)

Система (18) содержит m+ n -1 уравнений с m+ n неизвестными.

Зная U_i и V_j, можно вычислить относительную оценку для любого цикла в текущем плане перевозок. Для любой свободной клетки ij относительная оценка может быть вычислена без построения цикла пересчета по формуле Δ _ij=V_j-U_i-C_ij. (19)

Для базисных клеток Δ _ij=0.

U_i и V_j - потенциалы пунктов отправления и назначения соответственно.

Потенциалы можно интерпретировать как локальные цены. Если цена в пункте отправления i равна U_i и груз из него доставляется в пункт назначения j по коммуникации ij, то локальная цена в ПН возрастет по отношению к ПО на величину транспортных затрат: V_j=U_i+ C_ij. (20)

Рассмотрим конкретно преобразование матрицы D ^(k) в матрицу D ^(k+1) на основе нового решения X ^(k+1). Новое решение получено вводом небазисной переменной с максимальной оценкой в D ^(k). Пусть max D_ij=D_{kr .} В матрице D ^(k) отмечаем элементы, соответствующие базисным в новом решении X ^(k+1) (символом *), максимальную оценку отмечаем особо. Далее строим цепочку выделения. Она строится с особо отмеченного элемента, который соединяют с отмеченными в этой строке. Затем отмеченные элементы, попавшие в цепочку, соединяют с отмеченными в их столбцах. Далее снова проводим соединение по строкам, и так до тех пор, пока не оборвутся все ветви.

Переменной X_kr будет соответствовать нулевая оценка, как и тем переменным из решения X ^(k), которые сохранили статус базисных. Таким образом, преобразованная матрица соответствует новому опорному плану. Провести выделение можно и иначе: сначала вычеркивать строку с максимальным элементом, затем вычеркивать столбцы, где есть элементы, отмеченные в этой строке, и т.д. Вычеркнутые строки и столбцы являются выделенными.