Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Признак оптимальности
При перемещении q по циклу пересчета увеличиваются на эту величину значения переменных Xij в четных вершинах, а следовательно, увеличиваются и затраты на перевозку на q Cij. Одновременно уменьшаются на q переменные в нечетных вершинах и на q Cij соответствующие им затраты. Отсюда следует, что значение критерия в новом, (k+ 1)-м решении можно определить по критерию в исходном решении и изменениям в клетках цикла: или , (15) где (16) Δ ij – относительная оценка переменной Xij, на которой построен цикл. Для базисных переменных оценка всегда равна нулю. Δ ij показывает, как изменится критерий (в какую сторону и насколько) при перемещении по циклу единицы груза ( q =1). Если Δ ij> 0, то введение Xij в число базисных приведет к уменьшению суммарных затрат. Если же Δ ij< 0, критерий возрастет, что противоречит цели. Решение нельзя улучшить, когда среди оценок нет положительных, и поэтому признак оптимальности имеет вид " Δ ij£ 0. (17) Если признак не выполняется, то новое решение целесообразно строить на основе клетки с максимальной оценкой. Поставим в соответствие каждому пункту отправления сбалансированной задачи некоторую величину 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), которые сохранили статус базисных. Таким образом, преобразованная матрица соответствует новому опорному плану. Провести выделение можно и иначе: сначала вычеркивать строку с максимальным элементом, затем вычеркивать столбцы, где есть элементы, отмеченные в этой строке, и т.д. Вычеркнутые строки и столбцы являются выделенными.
|