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

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

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

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

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