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

Полагаем

и вычисляем

для .

Далее определяем

для .

Аналогично вычисляются

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

Каждая итерация алгоритмов состоит из двух этапов. Предположим, что уже приведено k итераций, в результате которых получен план

и матрица

.

Целью

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

Этап 1. На этапе 1 вычисляется матрица

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