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

Определение "Транспортная задача" в Большой Советской Энциклопедии

Транспортная задача, задача о наиболее рациональном плане перевозок однородного продукта из пунктов производства в пункты потребления. Пусть имеется 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, минимизирующих суммарные транспортные издержки.

при условиях
, ; (1)
, ; (2)
, ; ; (3)
Набор чисел x_ij, i = 1, ¼, m; j = 1, ¼, n, удовлетворяющий этим условиям, называется планом перевозок, а его элементы — перевозками.
Транспортная задача решают специальными методами линейного программирования.
 
Лит.: Гольштейн Е. Г., Юдин Д. Б., Задачи линейного программирования транспортного типа, М., 1969.