Главная » Справочник » Основы организации и управления транспортными системами » Постановка транспортной задачи линейного программирования

Постановка транспортной задачи линейного программирования

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

Оптимальный план перевозок в системе – это совокупность объемов перевозок между каждым поставщиком и потребителем по наиболее коротким или дешевым транспортным связям. План перевозок характеризуется затратами на перевозку всего объема.

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

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

Необходимым условием решения ТЗЛП является закрытость или замкнутость моделируемой транспортной системы. В замкнутой задаче объемы спроса равны объемам потребления. Если это условие нарушается, то транспортная задача называется «открытой» и приводится к задаче закрытого типа путем введения в транспортную систему дополнительного (фиктивного) поставщика или потребителя. Этому фиктивному поставщику или потребителю приписываются соответственно недостающий объем предложения или спроса, в результате чего система становится закрытой. Кроме того, естественным ограничением в ТЗЛП является условие неотрицательности объемов перевозок.

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

Интересно

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

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

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

Если ни у одной транспортной связи в системе нет положительной разности потенциалов, то это означает, что получен оптимальный план перевозок. В противном случае объемы перевозок по определенному правилу переносятся на транспортные связи с максимальной величиной разности потенциалов, что означает изменение плана перевозок.

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

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

Предыдущая статья Постановка задачи определения оптимального варианта плана формирования поездов Следующая статья Причины недостачи грузов

Статьи по теме