Метод двойного предпочтения

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

В каждом столбце отмечают знаком * клетку с наименьшей стоимостью. Затем то же проделывают в каждой строке. В результате некоторые клетки будут иметь отметку **. В них находится минимальная стоимость как по строке, так и по столбцу. Тогда в них помещают максимально возможные объемы перевозок, каждый раз исключая из рассмотрения соответствующие столбцы или строки. Затем распределяют перевозки по клеткам, отмеченным знаком *. В оставшейся части таблицы перевозки распределяют по наименьшей стоимости.

Полученный таким образом план может оказаться неоптимальным, то есть значение целевой функции, получаемое в соответствии с ним, может быть уменьшено за счет некоторых эквивалентных преобразований системы ограничений и перехода к другим смежным решениям Т-задачи, как задачи ЛП. В основе таких переходов лежит так называемый метод потенциалов, идея которого состоит в улучшении начального опорного плана до тех пор, пока не будет удовлетворяться некий признак оптимальности.

Алгоритм метода потенциалов решения Т-задачи состоит из предварительного этапа и конечного числа итераций.

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

где потенциалы пунктов отправления и пунктов назначения соответственно.

Предварительные потенциалы выбирают таким образом, чтобы для связанных коммуникациями пар пунктов, для которых в плане , сумма потенциалов была равна :

Если матрица не содержит отрицательных элементов, то - оптимальный план. В противном случае, план можно улучшить.

Поиск по сайту: