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

б) если

- опорное решение задачи , то - оптимальный опорный план задачи .

Здесь под

понимается матрица, составленная из нулей и коэффициентов разложения вектора

по базису плана

. Матрица строится аналогичным образом, исходя из вектора

.

Доказывать эти утверждения мы не будем.

Допустим теперь, что нам необходимо найти решение некоторой транспортной задачи T (быть может вырожденной!). Отмеченные свойства транспортных задач

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

Будем считать число

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

В соответствии с утверждением

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

, где

не зависят от

. Это обстоятельство позволяет опускать при вычислении оптимального плана задачи величину и оперировать лишь с составляющими плана :

и .

Введем предварительно несколько определений. Пару матриц

,

назовем обобщенным планом задачи T, если при всех достаточно малых

является планом задачи

. Обобщенный план удобно записывать в виде одной матрицы

.

Элементы матрицы

будем называть обобщенными перевозками.

Между двумя обобщенными перевозками введем соотношение «больше, меньше», полагая

, если либо , либо , но . Очевидно, что условие эквивалентно равенствам

, .

В частности, обобщенная перевозка

считается положительной, если либо , либо , однако .

Пусть

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

,

либо

,

но

.

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

3.Метод потенциалов и метод последовательного улучшения плана

Пусть

- некоторый опорный план задачи T. Обозначим через совокупность векторов , отвечающих основным коммуникациям плана . Наши рассуждения будут вестись в предположении невырожденности задачи T. Поэтому состоит из m+n-1 векторов и является базисом опорного плана .