Студопедия — Признак оптимальности
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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






При перемещении 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о=Ciоj1 - Ci1j1+ Ci1j2 - Ci2j2+ Ci2- Ciо. или

Δ iо = Vj1 -U -Vj1+Ui1+Vj2 -Ui1 -Vj2+Ui2+Vjо -Ui2 -Ciо = 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), которые сохранили статус базисных будет соответствовать нулевая оценка. Преобразованная матрица соответствует новому опорному плану.








Дата добавления: 2015-04-19; просмотров: 552. Нарушение авторских прав; Мы поможем в написании вашей работы!



Композиция из абстрактных геометрических фигур Данная композиция состоит из линий, штриховки, абстрактных геометрических форм...

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

ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Статика является частью теоретической механики, изучающей условия, при ко­торых тело находится под действием заданной системы сил...

Теория усилителей. Схема Основная масса современных аналоговых и аналого-цифровых электронных устройств выполняется на специализированных микросхемах...

Искусство подбора персонала. Как оценить человека за час Искусство подбора персонала. Как оценить человека за час...

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

Тема 5. Анализ количественного и качественного состава персонала Персонал является одним из важнейших факторов в организации. Его состояние и эффективное использование прямо влияет на конечные результаты хозяйственной деятельности организации.

Интуитивное мышление Мышление — это пси­хический процесс, обеспечивающий познание сущности предме­тов и явлений и самого субъекта...

Объект, субъект, предмет, цели и задачи управления персоналом Социальная система организации делится на две основные подсистемы: управляющую и управляемую...

Законы Генри, Дальтона, Сеченова. Применение этих законов при лечении кессонной болезни, лечении в барокамере и исследовании электролитного состава крови Закон Генри: Количество газа, растворенного при данной температуре в определенном объеме жидкости, при равновесии прямо пропорциональны давлению газа...

Studopedia.info - Студопедия - 2014-2024 год . (0.011 сек.) русская версия | украинская версия