Математическая постановка задачи. В исследовании операций под транспортной задачей обычно понимают задачу выбора плана перевозок некоторого товара (изделий

В исследовании операций под транспортной задачей обычно понимают задачу выбора плана перевозок некоторого товара (изделий, груза) от m поставщиков (пунктов производства, поставщиков) к n потребителям (станциям назначения, пунктам сбыта), обеспечивающего минимальные транспортные затраты. При этом предполагают, что:

а) мощность i-го поставщика (объем поставок товара от i -го поставщика) равна S_i > 0, i =1,..., m;

б) мощность j-го потребителя (объем поставок товара к j -му потребителю) равна D_j > 0, j =1,..., n;

в) стоимость перевозки единицы товара (в условных денежных единицах) от i -го поставщика к j -му потребителю равна с_ij;

Для математического описания транспортной задачи вводят переменные x_ij, обозначающие объемы поставок товара от i -го поставщика к j -му потребителю. В этом случае x_i1+x_i2+...+x_in — общий объем поставок товара от i -го поставщика, т.е. мощность этого поставщика; x_1j+x_2j+...+x_mj — общий объем поставок товара к j-му потребителю, т.е. мощность этого потребителя; c₁₁x₁₁+c₁₂x₁₂+...+c_mnx_mn — суммарная стоимость перевозок товара от потребителей к поставщикам. С учетом этого рассматриваемая задача может быть представлена в следующем виде:

	(2а)
	(2б)
	(2д)

На рис.2 показано представление транспортной задачи в виде сети с m пунктами отправления и n пунктами назначения, которые показаны в виде узлов сети. Дуги, соединяющие узлы сети, соответствуют маршрутам, связывающим пункты отправления и назначения. С дугой (i, j), соединяющей пункт отправления i с пунктом назначения j, соотносятся два вида данных: стоимость c_ij перевозки единицы груза из пункта i в пункт j и количество перевозимого груза x_ij. Объем грузов в пункте отправления i равен S_i, а объем грузов в пункте назначения j равен D_j. Задача состоит в определении неизвестных величин x_ij, минимизирующих суммарные транспортные расходы и удовлетворяющих ограничениям, накладываемым на объемы грузов в пунктах отправления (предложение) и пунктах назначения (спрос).

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