II этап. Определение вводимой в базис переменной (“ме- тод потенциалов”).

Отметим, что “метод потенциалов” эквивалентен принци- пу решения задачи линейного программирования и исполь- зованию условия оптимальности в симплекс-методе. Сначала находят опорный план транспортной задачи, а затем его улуч- шают до получения “оптимального плана”. Содержание “мето- да потенциалов” заключается в следующем:

1. Каждой строке i и столбцу j транспортной таблицы ста- вится в соответствие числа ui и νj, называемые потенциалами. Они должны для каждой базисной переменной xij текущего ре- шения удовлетворять условию ui + νj = cij. Эти условия приво- дят к системе, состоящей из m + n − 1 уравнений (так как име- ется всего m + n − 1 базис-переменных), в которых фигурируют m + n неизвестных. Значение потенциалов определяют из этой системы уравнений, придавая одному из них произвольное значение (например, u1= 0).

2. Определяются оценки  для небазисныx переменных в

соответствии с соотношением:

.

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

4. Вводимой в базис переменной является небазисная пе- ременная, имеющая самую большую положительную оцен- ку .

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

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

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

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

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

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

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

После конечного числа описанных выше итераций нерас- пределенный остаток становится равным нулю. В результате получают оптимальный план данной транспортной задачи.

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

задач с использованием электронно-вычислительных машин (ЭВМ) применяется метод дифференциальных рент.