3. Теорема о разрешимости транспортной задачи

Рассмотрим сбалансированную транспортную задачу.

найти минимальное значение линейной функции

; (4.1)

при ограничениях

= , I = 1,…,m; (4.2)

(4.3)

x_ij ³ 0, i = 1,…, m; j = 1,…, n. (4.4)

. (4.5)

Транспортная задача имеет n + m уравнений с mn неизвестными.

Определение 4.1. Матрицу Х = (х_ij)_m,n, удовлетворяющую условиям (4.2) – (4.4), называют планом перевозок транспортной задачи (х_ij - перевозками).

Определение 4.2. План Х*, при котором целевая функция (4.1) обращается в минимум, называется оптимальным.

Теорема 4.1. Для разрешимости транспортной задачи необходимо и достаточно выполнение условия баланса (4.5):

.

Доказательство:

1.Необходимость

Пусть ТЗ - разрешима;

а) Суммируем ограничения «4.2» по i:

б) Суммируем ограничения «4.3» по j:

Т.к левые части выражений а) и б) равны, то равны и правые части,

следовательно,

2. Достаточность. Пусть выполнено условие (4.5), т.е.

Построим матрицу Х = (х_ij)_m,n, где

(4.6)

Подставляя (4.6) в (4.2)получаем:

Аналогично подставляя (4.6) в (4.3), получим

Кроме того очевидно, что , следовательно матрица X является планом ТЗ, т.е. множество планов ТЗ не пусто.

Для установления разрешимости ТЗ осталось показать, что линейная функция (4.1) ограничена снизу на множестве планов ТЗ. Условия (4.2)-(4.3). обеспечивают выполнение неравенств

С ледовательно, для любого плана Х линейная функция (4.1) ограничена снизу на множестве планов ТЗ.

Достаточность условий теоремы можно было доказать по-другому, т.к. множество планов ТЗ – ограниченное множество и, следовательно, любая непрерывная функция достигает своей нижней грани.

4.4. Опорный план тз. Алгоритмы нахождения исходного плана.

4.4.1. Определения опорного плана тз.

Определение 4.3. План транспортной задачи называется опорным, если положительным перевозкам соответствует система линейно независимых векторов где - векторы при переменных в матрице системы ограничений (4.2.)-(4.3.)

Теорема 4.2. Существует план, содержащий не более (m + n – 1) положительных перевозок, при этом система векторов , соответствующая таким перевозкам (х_ij > 0), линейно независима.

В силу (4.5) система (4.2)-(4.3) содержит не более чем (m + n – 1) независимых уравнений, т.е. ранг системы меньше или равен (m + n – 1). В матрице ограничений (4.2)-(4.3) не трудно обнаружить квадратную матрицу порядка (m + n – 1), с определителем не равным нулю, следовательно ранг системы уравнений равен (m + n – 1).

Таким образом, опорный план транспортной задачи содержит (m + n – 1) положительных перевозок. Если положительных перевозок в плане меньше чем (m + n – 1), то он называется вырожденным.

Дадим другое определение опорного плана.

Определение 4.4. План транспортной задачи называется опорным, если из его основных коммуникаций (ij) невозможно составить замкнутый маршрут.