18

18) Транспортная задача. Постановка задачи и ее матем формулировка.

В m пунктах-поставщиках сосредоточен однородный груз в количестве а₁, a _2,..,a _n. Этот груз надо перевести n потребителям в количестве в_1, в_{2, …,}в_n. Известно, что c_ij-стоимость перевозки ед груза от i поставщика к j потребителю. С_ij-тариф. А₁+а₂+…+a_n=b₁+b₂+…+b_n (задача с правильным балансом). Обозначим x_ij количество груза от i поставщика к j потребителю.

	В1	B2	…	bn
a1	C11 X11	C12 X12		C1n X1n
a2	C21 X21	C22 X22		C2n X2n
…
am	Cm1 Xm1	Cm2 Xm2		Cmn xmn

X=(x₁₁, x₁₂,..,x₂₁,x₂₂,…x_2n,…,x_m1,x_m2,…,x_mn)

X-план перевозок.

План перевозок должен удовлетворять след условиям:

1.От каждого поставщика груз должен быть вывезен полностью

(1)

2.Каждый потребитель должен получить груз в полном объеме.

(2)

3.Все перевозки должны быть неотрицательными. x_ij ≥0 i=1,m j=1,n(3)

План должен быть таким, чтобы f(X)→min

F(X)= i=1,m j=1,n (4)

Математическая формулировка:

Найти такой план Х, удовлетворяющий системам ограничений (1) и (2), условию неотрицательности (3) и обеспечивающий min значение целевой функции (4).