Идея метода потенциалов, применяемого для решения транспортной задачи линейного программирования

Идея метода потенциалов заключается в том, что отличия затрат на перевозку по разным транспортным связям можно представить какразность потенциалов, причем эта разность потенциалов бу­дет тем больше, чем сильнее различаются величины затрат. На­личие разности потенциалов, как известно, приводит к возникнове­нию потока в системах различной природы. В данном случае раз­ность потенциалов поставщиков и потребителей в транспортной системе приводит к возникновению потоков, которые можно пред­ставить как потоки перераспределения объемов перевозок между транспортными связями, соединяющих этих поставщиков и потре­бителей. То есть объемы перевозок переносятся с транспортных связей, не обладающих разностью потенциалов, на транспортные связи с максимальной разностью потенциалов.

Для определения величины разности потенциалов каждому по­ставщику и потребителю приписывается потенциал. Совокупность потенциалов образует систему потенциалов. Потенциал потребите­ля определяется как сумма потенциала поставщика и оценки транс-

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