Постановка транспортной задачи.

В каждом из пунктов P_i, i=1...,m, производится a_i единиц некоторого однородного продукта, а в каждом из пунктов Q_j, j=1...,n, потребляется b_j единиц того же продукта. Возможная транспортировка продукта из каждого пункта производства Pi в каждый пункт потребления Qj. Стоимость перевозки единицы продукта из пункта Pi в пункт Qj известна и составляет с_іj единиц. Считая, что суммарный объем производства равняется суммарному объему потребления, нужно составить план перевозок продукта, что минимизирует суммарные транспортные расходы.

Математическая модель транспортной задачи имеет вид:

L(x)= c₁₁ x₁₁ +...+ c_1n x_1n +...+ c_m1 x_m1 +...+ c_mn x_mn ® min

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

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

x_ij³0, i=1...,m, j=1...,n

a₁ +...+ a_m = b₁ +...+ b_n.

Последнее условие определяет сбалансированную транспортную задачу.

В предложенной модели назовем вектор x=(x₁₁...,x_1n,...,x_m1,...,xmn) вектором перевозок, вектор b=(a₁...,am,b₁,...,bn) т — вектором запасов-потребностей, вектор A_ij=(0...,0,1,0...,0,0,...,0,1,0,...,0) т— вектором коммуникации PiQj (вектор A_ij имеет размерность m+n, причем первая единица стоит на і-у месте, а вторая — на m+j-у) и, наконец, вектор c=(c₁₁...,c1n,...,cm1,...,cmn) - вектором транспортных расходов.