Признак оптимальностиПри перемещении q по циклу пересчета увеличиваются на эту величину значения переменных Xij в четных вершинах, увеличиваются и затраты на перевозку на q Cij. Одновременно уменьшаются на q переменные в нечетных вершинах и на q Cij соответствующие им затраты. Значение критерия в новом, (k+ 1)-м решении можно определить по критерию в исходном решении и изменениям в клетках цикла: или , где Δij – относительная оценка переменной Xij, на которой построен цикл. Для базисных переменных оценка всегда равна нулю. Δij показывает, как изменится критерий (в какую сторону и насколько) при перемещении по циклу 1 груза (q =1). Если Δij>0, то введение Xij в число базисных приведет к уменьшению суммарных затрат. Если же Δij<0, критерий возрастет, что противоречит цели. Решение нельзя улучшить, когда среди оценок нет положительных, Признак оптимальности - "Δij£0. Если признак не выполняется, то новое решение целесообразно строить на основе клетки с максимальной оценкой. Поставим в соответствие каждому пункту отправления сбалансированной задачи некоторую величину Ui, i =1, 2,…, m, а каждому пункту назначения – Vj, j =1, 2,…, n так, чтобы для базисных клеток выполнялись равенства Vj -Ui=Cij, i j Îб аз. Система содержит m+n -1 уравнений с m+ n неизвестными. Присвоив одной из неизвестных некоторое произвольное значение, например, 0, м найти значения остальных. Зная Ui и Vj, можно вычислить относительную оценку для любого цикла в текущем плане перевозок. Пример на произвольно взятом цикле: В скобках указаны индексы клеток (переменных), в которых расположены вершины цикла. Вычисляем относительную оценку свободной клетки i0j0: Δ iоjо=Ciоj1 - Ci1j1+ Ci1j2 - Ci2j2+ Ci2jо - Ciоjо. или Δ iоjо = Vj1 -U iо -Vj1+Ui1+Vj2 -Ui1 -Vj2+Ui2+Vjо -Ui2 -Ciоjо = Vjo-Uio-Ciojo. Δ ij=Vj-Ui-Cij. Новые переменные Ui и Vj - потенциалы ПО и ПН соответственно. Потенциалы можно интерпретировать как локальные цены. Если цена в пункте отправления i равна Ui и груз из него доставляется в пункт назначения j по коммуникации ij, то локальная цена в ПН возрастет по отношению к ПО на величину транспортных затрат: Vj=Ui+ Cij. Из этого соотношения также следует, что в оптимальном решении не может иметь место неравенство Vj >Ui+ Cij, так как оно означает, что локальная цена в пункте j выше, чем в случае прямой доставки из i в j. Приведенный способ определения оценок через потенциалы пригоден для любого опорного плана перевозок. Однако учитывая структуру матрицы оценок (нули в базисных клетках), можно оценки нового плана получить минуя вычисления потенциалов простым преобразованием матрицы оценок предшествующего плана. Рассмотрим преобразование матрицы D (k) в матрицу D (k+1) на основе нового решения X (k+1). Новое решение получено вводом небазисной переменной с максимальной оценкой в D (k). Пусть max Dij=Dkr. В матрице D (k) отмечаем элементы, соответствующие базисным в новом решении X (k+1) (на рис. помечены символом *), максимальную оценку отмечаем особо. Далее строим цепочку выделения. Она строится с особо отмеченного элемента, который соединяют с отмеченными в этой строке. Затем отмеченные элементы, попавшие в цепочку, соединяют с отмеченными в их столбцах. Далее снова проводим соединение по строкам, и так до тех пор, пока не оборвутся все ветви. Элементы, попавшие в цепочку выделения, выделяют строку и столбец за исключением особо отмеченного элемента, который выделяет только строку. К выделенным столбцам прибавляем, а из выделенной строки вычитаем . Переменной Xkr и тем переменным из решения X (k), которые сохранили статус базисных будет соответствовать нулевая оценка. Преобразованная матрица соответствует новому опорному плану.
|