Транспортная задача

Тра́нспортная зада́ча

Задача о наиболее рациональном плане перевозок однородного продукта из пунктов производства в пункты потребления. Пусть имеется m пунктов производства некоего однородного продукта A₁, …, A_i, …, A_m и n пунктов его потребления B₁, …, B_j, …, B_n. В пункте A_i (i = 1, …, m) производится a_i единиц, а в пункте B_j (j = 1, …, n) потребляется b_j единиц продукта. Предполагается, что . Транспортные издержки, связанные с перевозкой единицы продукта из пункта A_i в пункт B_j, равны c_ij. Суть Т. з. состоит в составлении оптимального плана перевозок, минимизирующего суммарные транспортные издержки, при реализации которого запросы всех пунктов потребления B_j, j = 1, …, n, были бы удовлетворены за счёт производства продукта в пунктах A_i, i = 1, …, m. Пусть x_ij — количество продукта, перевозимого из пункта A_i в пункт B_j. Тогда Т. з. формулируется так: определить значения переменных x_ij, i = 1, …, m; j = 1, …, n, минимизирующих суммарные транспортные издержки.

при условиях

, i=1, ..., m; (1)

, j = 1, ..., n; (2)

, i=1, ..., m; j = 1, ..., n; (3)

Набор чисел x_ij, i = 1, …, m; j = 1, …, n, удовлетворяющий этим условиям, называется планом перевозок, а его элементы — перевозками.

Т. з. решают специальными методами линейного программирования (См. Линейное программирование).

Лит.: Гольштейн Е. Г., Юдин Д. Б., Задачи линейного программирования транспортного типа, М., 1969.