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

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

Рассмотрим транспортную задачу.
(1)  
(2)  
(3)  
(4)   ,
(5)   .
Для того чтобы существовало решение транспортной задачи (1) – (5), необходимо и достаточно, чтобы
сумма запасов поставщиков равнялась сумме потребностей потребителей:
(6)   .

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

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

Покажем, что тогда сумма мощностей поставщиков равна сумме мощностей потребителей . Для этого применим (2) и (3), и изменим порядок суммирования:
.

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

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

Пусть сумма мощностей поставщиков равна сумме мощностей потребителей, то есть выполняется (6).
Обозначим суммарные мощности буквой M:
.

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

Возьмем . Покажем, что при этом выполняется (2):
.
Покажем, что выполняется (3):
.

Покажем, что выполняется (4). То есть покажем, что величины неотрицательные.
Действительно, согласно (5), . Тогда и :
.
Поэтому
.

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

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

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

Для этого заметим, что коэффициенты в целевой функции (1) являются конечными числами. Поэтому они ограничены снизу некоторым числом C:
.
Поскольку , то . Тогда
.

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

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