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

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

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

Date: 2015-09-24; view: 663; Нарушение авторских прав