Алгоритм решения транспортной задачи методом потенциалов. Пусть дана транспортная задача с правильным балансом

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

I. Начальный шаг

1. Используя метод северо-западного угла или метод наименьшей стоимости, находим первоначальный план перевозок, содержащий занятую клетку.

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

II. Общий шаг

1. Построение нового плана:

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

б) Строим цикл, начиная с отмеченной клетки. И последовательно обходим его клетки, проставляя в них поочередно и .

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

2. Проверяем построенный план на оптимальность. Если этот план не оптимален, то снова повторяем общий шаг данного алгоритма.

Пример. Решить задачу: , , , , , , , .

Решение. Сначала, используя метод наименьшей стоимости, находим первоначальный план данной задачи.

	+ –			–
–3	–	–	–	+
–2	–		–	–

Для нахождения потенциалов составляем систему уравнений

Полагая , находим значения потенциалов. Вычисляем для каждой свободной клетки величину : , , , , , .

Так как среди найденных значений имеются положительные, то построенный план перевозок не является оптимальным и нужно перейти к новому плану. Наибольшим среди положительных значений является , поэтому помечаем клетку (1, 1) знаком . Строим цикл. Отмечаем клетки выбранного цикла знаками и и находим величину . Вычитая величину из объемов перевозок, расположенных в отмеченных знаком клетках, и прибавляя к объемам перевозок в клетках со знаком , получаем новый план перевозок, записанный в следующей таблице.

				–
–1		–	–
–2	–		–	–

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

Дата добавления: 2015-06-30; просмотров: 167; Нарушение авторских прав

Мы поможем в написании ваших работ!