Транспортная задача
Рассмотрим простейшую постановку транспортной задачи. В m пунктах отправления А1, А2, ..., Ат находится однородный груз, в количествах a1, a2, ..., aт единиц (ед.) (например, тонн) соответственно. Потребность в этом грузе в п пунктах назначения В1, В2, ..., Вт составляет соответственно b1, b2, ..., bт ед. груза. Стоимость перевозки ед. груза (удельная стоимость) из пункта Аi в пункт Вj (короче, из Аi в Bj) равна cij, 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, вводят фиктивный пункт назначения Bn+1, полагая
bn+1 = a-b, ci,n+1 = 0, i=1, 2, ..., m.
Если, наоборот, а < b, то вводят фиктивный пункт отправления Am+1, полагая
am+1 = b-a, cm+1,j = 0, j=1, 2, ..., n.
Пусть xij — неизвестный пока объем груза, который по плану перевозок следует доставить из Аi в Bj, i = 1, 2, ..., т, j = 1, 2, ..., n. Занесем неизвестные xij в табл. 1 и приступим к составлению ограничений. Возьмем какой-нибудь пункт отправления, например Аi. Весь груз из него должен быть вывезен (это следствие того, что модель закрытая), поэтому сумма неизвестных в i-ой строке табл. 1 должна равняться ai, т.е.
xi1 + xi2 + ... + xin = ai, i = 1, 2, ..., m.
Таким образом, получим систему линейных уравнении (2) для пунктов отправления. Аналогично, сумма неизвестных, стоящих в j-ом столбце табл. 1, должна равняться bj, т.е.
x1j + x2j + ... + xmj = bj, j = 1, 2, ..., n.
В результате получим систему линейных уравнении (3) для пунктов назначения. Естественно, неизвестные в этих системах должны быть неотрицательны.
x11 + x12 + ... + x1n = a1,
x21 + x22 + ... + x2n = a2, (2)
…
xm1 + xm2 + ... + xmn = am;
x11 + x21 + ... + xm1 = b1,
x12 + x22 + ... + xm2 = b2, (3)
…
x1n + x2n + ... + xmn = bn.
Предполагая, что стоимость перевозок пропорциональна количеству перевозимого груза, общую стоимость перевозок можно выразить формулой
. (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 неизвестных.
Непосредственное применение симплекс-метода к решению сформулированной задачи ЛП затруднительно из-за большого числа переменных. Поэтому разработаны его модификации, учитывающие специфику транспортной задачи. Ниже будет рассмотрен распределительный метод решения транспортной задачи. Все необходимые вычисления по этому методу можно оформить с помощью матрицы перевозок.
Решение транспортной задачи начинается с нахождения какого-либо допустимого базисного решения.