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

Рассмотрим простейшую постановку транспортной задачи. В m пунктах отправления А₁, А₂, ..., А_т находится однородный груз, в количествах a₁, a₂, ..., a_т единиц (ед.) (например, тонн) соответственно. Потребность в этом грузе в п пунктах назначения В₁, В₂, ..., В_т составляет соответственно b₁, b₂, ..., b_т ед. груза. Стоимость перевозки ед. груза (удельная стоимость) из пункта А_i в пункт В_j (короче, из А_i в B_j) равна c_ij, i = 1, 2, ..., т, j = 1, 2, ..., n. Все эти данные можно свести в табл. 1, называемую матрицей перевозок, разграфив ее для удобства на клетки.

Таблица 1

ai / bj	b1	b2	…	bn
a1	c11	c12	…	c1n
a2	c21	c22	…	c2n
…	…	…	…	…
am	cm1	cm2	…	cmn

Можно считать, что сумма a запасов в пунктах отправления равна суммарным потребностям b в пунктах назначения, т.е.

. (1)

Такая модель транспортной задачи называется закрытой. Если условие (1) не выполняется, т.е. модель открытая, то в случае, когда а > b, вводят фиктивный пункт назначения B_n+1, полагая

b_n+1 = a-b, c_i,n+1 = 0, i=1, 2, ..., m.

Если, наоборот, а < b, то вводят фиктивный пункт отправления A_m+1, полагая

a_m+1 = b-a, c_m+1,j = 0, j=1, 2, ..., n.

Пусть x_ij — неизвестный пока объем груза, который по плану перевозок следует доставить из А_i в B_j, i = 1, 2, ..., т, j = 1, 2, ..., n. Зане­сем неизвестные x_ij в табл. 1 и приступим к составлению ограничений. Возьмем какой-нибудь пункт отправления, например А_i. Весь груз из него должен быть вывезен (это следствие того, что модель закрытая), поэтому сумма неизвестных в i-ой строке табл. 1 должна равняться a_i, т.е.

x_i1 + x_i2 + ... + x_in = a_i, i = 1, 2, ..., m.

Таким образом, получим систему линейных уравнении (2) для пунктов отправления. Аналогично, сумма неизвестных, стоящих в j-ом столбце табл. 1, должна равняться b_j, т.е.

x_1j + x_2j + ... + x_mj = b_j, j = 1, 2, ..., n.

В результате получим систему линейных уравнении (3) для пунктов назначения. Естественно, неизвестные в этих системах должны быть неотрицательны.

x₁₁ + x₁₂ + ... + x_1n = a₁,

x₂₁ + x₂₂ + ... + x_2n = a₂, (2)

…

x_m1 + x_m2 + ... + x_mn = a_m;

x₁₁ + x₂₁ + ... + x_m1 = b₁,

x₁₂ + x₂₂ + ... + x_m2 = b₂, (3)

…

x_1n + x_2n + ... + x_mn = b_n.

Предполагая, что стоимость перевозок пропорциональна количеству перевозимого груза, общую стоимость перевозок можно выразить формулой

. (4)

Итак, для решения поставленной задачи требуется среди неотрица­тельных решений системы линейных уравнений (2)-(3) найти реше­ние, дающее минимум форме z (4).

Система линейных уравнений (2)-(3), состоит из (т + n) уравнений с т • n неизвестными, причем эта система линейно зависима, так как в силу условия (1) сумма первых m уравнений (подсистема (2)) совпа­дает с суммой остальных n уравнений (подсистема (3)). Это означает, что ранг системы (2)-(3) меньше, чем (m+n). Можно показать, что он равен m+n-1, следовательно, базис системы уравнений (2)-(3) содержит m + n -1 неизвестных.

Непосредственное применение симплекс-метода к решению сформули­рованной задачи ЛП затруднительно из-за большого числа переменных. Поэтому разработаны его модификации, учитывающие специфику транспортной задачи. Ниже будет рассмотрен распределительный метод решения транспортной задачи. Все необходимые вычисления по этому методу можно оформить с помощью матрицы перевозок.

Решение транспортной задачи начинается с нахождения какого-либо допустимого базисного решения.