![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Признак оптимальности
При перемещении q по циклу пересчета увеличиваются на эту величину значения переменных Xij в четных вершинах, а следовательно, увеличиваются и затраты на перевозку на q Cij. Одновременно уменьшаются на q переменные в нечетных вершинах и на q Cij соответствующие им затраты. Отсюда следует, что значение критерия в новом, (k+ 1)-м решении можно определить по критерию в исходном решении и изменениям в клетках цикла:
где Поставим в соответствие каждому пункту отправления сбалансированной задачи некоторую величину Ui, i =1, 2, …, m, а каждому пункту назначения – Vj, j =1, 2, …, n так, чтобы для базисных клеток выполнялись равенства Vj - Ui=Cij, i j Î б аз. (18) Система (18) содержит m+ n -1 уравнений с m+ n неизвестными. Зная Ui и Vj, можно вычислить относительную оценку для любого цикла в текущем плане перевозок. Для любой свободной клетки ij относительная оценка может быть вычислена без построения цикла пересчета по формуле Δ ij=Vj-Ui-Cij. (19) Для базисных клеток Δ ij=0. Ui и Vj - потенциалы пунктов отправления и назначения соответственно. Потенциалы можно интерпретировать как локальные цены. Если цена в пункте отправления i равна Ui и груз из него доставляется в пункт назначения j по коммуникации ij, то локальная цена в ПН возрастет по отношению к ПО на величину транспортных затрат: Vj=Ui+ Cij. (20) Рассмотрим конкретно преобразование матрицы D (k) в матрицу D (k+1) на основе нового решения X (k+1). Новое решение получено вводом небазисной переменной с максимальной оценкой в D (k). Пусть max Dij=Dkr . В матрице D (k) отмечаем элементы, соответствующие базисным в новом решении X (k+1) (символом *), максимальную оценку отмечаем особо. Далее строим цепочку выделения. Она строится с особо отмеченного элемента, который соединяют с отмеченными в этой строке. Затем отмеченные элементы, попавшие в цепочку, соединяют с отмеченными в их столбцах. Далее снова проводим соединение по строкам, и так до тех пор, пока не оборвутся все ветви.
Переменной Xkr будет соответствовать нулевая оценка, как и тем переменным из решения X (k), которые сохранили статус базисных. Таким образом, преобразованная матрица соответствует новому опорному плану. Провести выделение можно и иначе: сначала вычеркивать строку с максимальным элементом, затем вычеркивать столбцы, где есть элементы, отмеченные
|