Теорема о существовании решения транспортной задачи

Теорема о существовании решения транспортной задачи

Рассмотрим транспортную задачу.
(1)   F(X ) = ^mΣ_i = 1 ⁿΣ_j = 1 c_ij x_ij  → min
(2)   ⁿΣ_j = 1 x_ij  = a_i ,  (i = 1 ÷ m )
(3)   ^mΣ_i = 1 x_ij  = b_j ,  (j = 1 ÷ n )
(4)   x_ij  ≥ 0 ,
(5)   a_i  > 0,  b_j  > 0  (i = 1 ÷ m,  j = 1 ÷ n ) .
Для того чтобы существовало решение транспортной задачи (1) – (5), необходимо и достаточно, чтобы
сумма запасов поставщиков равнялась сумме потребностей потребителей:
(6)   ^mΣ_i = 1 a_i  = ⁿΣ_j = 1 b_j .

Доказательство необходимости

Пусть транспортная задача (1) – (5) имеет решение. Это означает, что существуют m × n неотрицательных величин x_ij , которые удовлетворяют системе ограничений (2), (3).

Покажем, что тогда сумма мощностей поставщиков ^mΣ_i = 1 a_i равна сумме мощностей потребителей ⁿΣ_j = 1 b_j . Для этого применим (2) и (3), и изменим порядок суммирования:
^mΣ_i = 1 a_i  = ^mΣ_i = 1 ⁿΣ_j = 1 x_ij  = ⁿΣ_j = 1 ^mΣ_i = 1 x_ij  = ⁿΣ_j = 1 b_j .

Необходимость доказана.

Доказательство достаточности

Пусть сумма мощностей поставщиков равна сумме мощностей потребителей, то есть выполняется (6).
Обозначим суммарные мощности буквой M :
M = ^mΣ_i = 1 a_i  = ⁿΣ_j = 1 b_j .

1) Сначала покажем, что существует любое допустимое решение. То есть нам нужно показать, что существуют такие m × n величин x_ij , для которых выполняются условия системы ограничений (2), (3), (4).

Возьмем x_ij  = a_i b_jM . Покажем, что при этом выполняется (2):
ⁿΣ_j = 1 x_ij  = ⁿΣ_j = 1 a_i b_jM = a_iM ⁿΣ_j = 1 b_j  = a_iM M = a_i .
Покажем, что выполняется (3):
^mΣ_i = 1 x_ij  = ^mΣ_i = 1 a_i b_jM = b_jM ^mΣ_i = 1 a_i  = b_jM M = b_j .

Покажем, что выполняется (4). То есть покажем, что величины x_ij неотрицательные.
Действительно, согласно (5), a_i  > 0,  b_j  > 0 . Тогда и M > 0 :
M = ^mΣ_i = 1 a_i  = ⁿΣ_j = 1 b_j  > 0 .
Поэтому
x_ij  = a_i b_jM > 0 .

Существование допустимого решения доказано.

Заметим, что доказать существование допустимого решения (плана) можно и другими способами. Например, можно воспользоваться тем, что для любой транспортной задачи, при выполнении условия (6), всегда можно составить опорный план методом северо-западного угла.

2) Покажем, что существует оптимальное решение. Для этого нужно показать, что каким бы не было допустимое решение x_ij , целевая функция F является ограничена снизу. То есть существует такое число m , так что для любых x_ij , удовлетворяющих условиям (2) – (4),
F(X ) ≥ m .

Для этого заметим, что коэффициенты c_ij в целевой функции (1) являются конечными числами. Поэтому они ограничены снизу некоторым числом C :
c_ij  ≥ C .
Поскольку x_ij  ≥ 0 , то c_ij x_ij  ≥ Cx_ij . Тогда
F(X ) = ^mΣ_i = 1 ⁿΣ_j = 1 c_ij x_ij  ≥ ^mΣ_i = 1 ⁿΣ_j = 1 Cx_ij  = C ^mΣ_i = 1 ⁿΣ_j = 1 x_ij  = C ^mΣ_i = 1 a_j  = CM .

То есть мы нашли, что целевая функция F(X ) ограничена снизу числом m = CM :
F(X ) ≥ CM . Перебирая возможные допустимые решения транспортной задачи, мы построим множество значений функции F(X ) . Поскольку это множество не пустое и ограничено снизу, то оно имеет конечную точную нижнюю грань, которая и является решением транспортной задачи.

Теорема доказана.