Решение транспортных задач методом потенциалов (стр. 5 из 8)

На первом этапе метода потенциалов вычисляются предварительные потенциалы

удовлетворяющие системе уравнений

для . (3.1)

(Здесь

- множество пар индексов векторов, составляющих базис плана .)

Переименуем векторы базиса

и обозначим l-й вектор через

Учитывая, что все компоненты вектора

, кроме двух, равных единице, равны нулю, можно переписать систему (3.1) в эквивалентном виде

.

Здесь

;

- стоимость единичной перевозки по коммуникации, соответствующей вектору .

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

,

То в соответствии с критерием оптимальности метода улучшения плана данный план

- решение задачи. Это же заключение следует из критерия оптимальности, используемого в методе потенциалов.

Предположим, что при некоторых i,j

.

Тогда в соответствии с методом последовательного улучшения плана выбирается такая пара индексов

, на которой величина

(оценка вектора условий

) достигает минимума, и осуществляется переход к новому базису путем замены одного из векторов системы вектором . Та же операция осуществляется и в методе потенциалов (этап 2). Переход к новому базису связан с разложением вводимого вектора (вектора ) по векторам базиса , что эквивалентно решению системы линейных уравнений. Благодаря простой структуре векторов решение этой системы существенно облегчается по сравнению с общим случаем.

Согласно методу улучшения плана после разложения вводимого вектора (вектора

) по векторам старого базиса разыскивается величина

. (3.2)

Здесь

- коэффициент при i-м векторе базиса в разложении вектора ограничений (вводимого вектора) по векторам старого базиса; минимум берется по тем индексам i, для которых . Если , то из базиса удаляется его r-й вектор.

Базисные компоненты нового плана определяются по формуле

(3.3)

Для транспортной задачи коэффициенты

равны нулю или . При этом в том и только в том случае, если i-й вектор базиса соответствует коммуникации, которая занимает нечетную (четную) позицию в построенном маршруте. Поэтому формула (3.2) в случае транспортной задачи может быть заменена правилом: - минимальная нечетная перевозка маршрута, связывающего пункты и . Это правило и используется в методе потенциалов. Формула (3.3) применительно к транспортной задаче превращается в правило изменения плана перевозок, употребляемое в методе потенциалов: перевозки, запланированные по нечетным (четным) коммуникациям, уменьшаются (увеличиваются) на величину , перевозка между и полагается равной , остальные перевозки сохраняют свои значения.

Итак, метод потенциалов является детализацией второго алгоритма метода улучшения плана, учитывающей специфику транспортной задачи. Отличие состоит только в том, что на каждом шаге метода потенциалов все параметры задачи (план, предварительные потенциалы, коэффициенты разложения вводимого вектора коммуникаций) вычисляются не по рекуррентным формулам, как в методе улучшения плана, а непосредственно. Это оказывается более выгодным из-за простоты условий задачи T, позволяющей легко решать соответствующие системы линейных уравнений.

4. Алгоритм метода потенциалов

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

задачи T и составляется матрица

,

где

и - предварительные потенциалы, отвечающие исходному плану .

На каждой итерации рассматриваются и преобразуются две матрицы

и .

Матрица

представляет собой опорный план задачи T, построенный в результате k-й итерации. Матрица составлена из оценок векторов относительно базиса плана , т.е.

где

и - предварительные потенциалы, отвечающие плану .

Вначале будем предполагать задачу T невырожденной. Необходимые замечания относительно вырожденного случая будут сделаны ниже.

Предварительный этап. С помощью метода северо-западного угла или метода минимального элемента определяется исходный опорный план

исследуемой задачи T. Далее, согласно правилам, изложенным при описании 1-го этапа метода потенциалов, вычисляем величины , , , и составляем матрицу

.

Если все элементы

неотрицательны, то - решение задачи T. В противном случае переходим ко второму этапу, описание которго приводится ниже. Процесс вычисления предварительных потенциалов формализуется следующим образом. Пусть - номера тех столбцов матрицы С, которые содержат -существенные элементы в 1-й строке; - номера строк матрицы С, которые содержат -существенные элементы в столбцах с номерами . Если множества и для уже определены, то объединяет номера тех столбцов матрицы С, не принадлежащих , которые содержат -существенные элементы в строках с номерами , а состоит из номеров строк этой матрицы, не включенных в и содержащих -существенные элементы в столбцах с номерами . Образование множеств и производится до тех пор, пока процесс не прерывается получением пустого множества. Если , то под будем понимать такой элемент множества , что - -существенный элемент С. Аналогично, для определим как элемент , при котором является -существенным элементом С. Из опорности плана следует, что множества , равно как и множества , не пересекаются. Невырожденность плана приводит к тому, что объединение всех множеств есть , а объединение всех множеств составляет .