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

.

Кроме того, все ее

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

После l – 1 шагов все ненулевые

- существенные элементы оказываются принадлежащими . Пусть l – нечетное (четное) число. Поскольку - пустое множество, все - существенные элементы матрицы, полученной после вычитания (прибавления) величины из строк (к столбцам) элементов , равны нулю. Итак, величины , удовлетворяют системе (1.3), соответствующей плану .

Следовательно,

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

.

Как нетрудно заметить, описанное правило отыскания предварительных потенциалов

, или, что то же самое, матрицы , базируется на определении разностей

.

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

, можно вычислять и непосредственно, решая систему (1.3). Формализация процесса решения этой системы была приведена при описании предварительно этапа (применительно к исходному плану ).

Если все элементы матрицы

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

Этап 2. На этапе 2 производится улучшение плана

. Основой этапа является процесс составления цепочки из положительных элементов этого плана. Выберем наименьший элемент матрицы , расположенный, скажем, на пересечении - й строки и - го столбца, и обозначим его через . По условию . Переходим к поиску цепочки из положительных элементов матрицы , замыкающейся на элементе (очевидно, =0). Соединим стрелками со всеми положительными элементами его строки, совокупность которых обозначим через . Затем каждый из элементов соединим стрелками со всеми положительными элементами, расположенными в его столбце. Совокупность всех таких элементов обозначим через . Процесс образования множеств продолжается до тех пор, пока при некотором p (p – нечетное число) среди столбцов, содержащих элементы , обнаружится столбец с номером . Заметим, что в силу опорности плана множества , не пересекаются, ибо в противном случае существовала бы замкнутая цепочка из ненулевых перевозок плана . Это обстоятельство, а также то, что любые два пункта невырожденной задачи T могут быть соединены коммуникациями с ненулевыми перевозками, служит доказательством существования введенного выше числа . Теперь уже нетрудно образовать искомую цепочку. От элемента перейдем по столбцу к элементу . От по строке перейдем к соединенному с ним стрелкой элементу и т.д. Двигаясь таким образом вдоль намеченных стрелок по строкам и столбцам матрицы , получим в конце концов последовательность положительных элементов этой матрицы вида

, (4.1)

образующую цепочку, которая замыкается на элементе

.

Построение цепочки (4.1) можно осуществить также с помощью метода вычеркивания строк. Для этого вводится множество Г, состоящее из положительных элементов матрицы

и ее элемента .

Из матрицы

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

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

, оставшиеся после процесса вычеркивания, составляют искомую цепочку. Построив цепочку (4.1), легко сформировать новый план .

Обозначим совокупность пар индексов

, через , а множество пар индексов вида , через . Положим