Что значит "транспортная задача"

задача о наиболее рациональном плане перевозок однородного продукта из пунктов производства в пункты потребления. Пусть имеется m пунктов производства некоего однородного продукта A1, ¼, Ai, ¼, Am и n пунктов его потребления B1, ¼, Bj, ¼, Bn. В пункте Ai (i = 1, ¼, m) производится ai единиц, а в пункте Bj (j = 1, ¼, n) потребляется bjединиц продукта. Предполагается, что . Транспортные издержки, связанные с перевозкой единицы продукта из пункта Ai в пункт Bj, равны cij. Суть Т. з. состоит в составлении оптимального плана перевозок, минимизирующего суммарные транспортные издержки, при реализации которого запросы всех пунктов потребления Bj,j = 1, ¼, n, были бы удовлетворены за счёт производства продукта в пунктах Ai, i = 1, ¼, m. Пусть xij ≈ количество продукта, перевозимого из пункта Ai в пункт Bj. Тогда Т. з. формулируется так: определить значения переменных xij, i = 1, ¼, m; j = 1, ¼, n, минимизирующих суммарные транспортные издержки. при условиях , ; (

1. ; (

2. ; ; (

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

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

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

Транспортная задача (задача Монжа — Канторовича) — математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение. Для простоты понимания рассматривается как задача об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления, с минимальными затратами на перевозки. Транспортная задача по теории сложности вычислений входит в класс сложности P . Когда суммарный объём предложений , запрашиваемые пунктами потребления, транспортная задача называется несбалансированной (открытой).