Теоретическое обоснование метода потенциалов

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

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

Далее рассуждения повторяются до тех пор, пока перевозки не будут полностью перераспределены. Отметим две особенности этого перераспределения:

1) клетки, участвующие в перераспределении, являются вершинами некоторого замкнутого контура, стороны которого вертикальны и горизонтальны;

2) количество клеток, в которые добавлена единица загрузки (условно пометим их знаком «+»), совпадает с количеством клеток, в которых загрузка уменьшена на единицу (пометим их знаком «–»).

Нетрудно видеть, что изменение транспортных расходов, вызванное рассмотренным перераспределением перевозок, может быть вычислено как разность между суммой тарифов клеток, помеченных знаком «+», и суммой тарифов клеток, помеченных знаком «–». Таким образом, если эта разность окажется положительной, транспортные расходы возрастут, если отрицательной, то уменьшатся, если же указанная разность окажется равной нулю, транспортные расходы не изменятся.

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

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

Оказывается, такого упрощения можно достичь, введя в рассмотрение для каждого поставщика и каждого потребителя их потенциалы и соответственно. Чтобы уяснить экономический смысл этих потенциалов, достаточно предположить, что все поставщики и потребители оплачивают перевозки в складчину, тогда их потенциалы и подбираются так, чтобы для каждой загруженной клетки выполнялось равенство . Таким образом, числа и являются решением системы уравнений , составленных для каждой загруженной клетки . Отметим, что таких уравнений столько, сколько загруженных клеток, т. е. ,
а неизвестных и – ровно . Следовательно, неизвестных в данной системе на одну больше, чем уравнений. Как известно из курса высшей математики, это означает, что данная система уравнений имеет бесконечное множество решений. Нас устроит любое из них, поэтому выберем, например, то, для которого . Другими словами, мы будем находить потенциалы и , предполагая, что поставщик ничего не платит за перевозки.

Нетрудно понять, что для каждой незагруженной клетки искомая разность между суммой тарифов клеток, помеченных знаком «+», и суммой тарифов клеток, помеченных знаком «–», равна разности . Действительно, величина – это та сумма, которую поставщик и потребитель заплатят вместе за перевозку одной единицы груза из пункта в пункт при данном плане перевозок, в то время как – это реальный тариф такой перевозки. Следовательно, разность показывает, на сколько изменятся транспортные расходы, если из рассматриваемого пункта отправления в рассматриваемый пункт потребления будет перевезена одна единица груза. Напомним, что именно этот экономический смысл скрывался и за разностью между суммами загрузок клеток со знаком «+» и загрузок клеток со знаком «–».

Учитывая все отмеченное нами, получим алгоритм метода потенциалов, который приведем в следующем параграфе.