Постановка и основные свойства транспортной задачи (стр. 3 из 7)
Доказательство. Необходимость. Пусть векторы 
линейно независимы. Если бы существовал замкнутый маршрут из коммуникаций 
и 
, то, очевидно, начиная движение из пункта 
и последовательно проходя все пункты 
по последней коммуникации 
мы вернемся в начальный пункт . Тогда справедливое равенство 
(1.20)
которое указывает на линейную зависимость векторов
.
Полученное противоречие доказывает необходимость условий теоремы 4.
Достаточность. Допустим, что из коммуникаций, отвечающих векторам 
системы R, нельзя составить замкнутый маршрут. Докажем, что в таком случае R – линейно независимая система. Если предположить противное, т.е. линейную зависимость векторов системы R, то существуют такие числа 
, среди которых не все нули, для которых выполняется условие
. (1.21)
Пусть, например 
. Перенесем тогда соответствующий вектор вправо и получим
, (1.22)
где Е1 образуется вычеркиванием в Е пары индексов ( 
). Компонента с номером 
в правой части (3.1.22) не равна нулю.
Следовательно, это же относится и к левой части этого равенства, т.е. среди
векторов 
найдется хотя бы один вектор вида 
с
коэффициентом 
. Перенеся его в правую чатсть равенства (1.22), получим
, (1.23)
где 
. Но поскольку 
, компонента с номером 
правой части (1.23) отлична от нуля. Поэтому среди векторов левой части (1.23) найдется хотя бы один вектор вида 
, для которого 
. Перенося его в правую часть (1.23), находим
(1.24)
где 
Этот процесс переноса векторов в правую часть можно продолжить аналогичным образом и дальше. Допустим, что уже проведено (2k-1) шагов. Тогда имеет место соотношение
(1.25)
где 
Возможные два случая:
1) 
при некотором 
2) 
.
В первом случае процесс переноса заканчивается, причем из векторов в правой части (1.25) можно образовать замкнутый маршрут. Таким маршрутом является
Во втором случае процесс переноса продолжается, и поскольку 
, среди векторов Рij, где (i, j) 
обязательно найдется вектор 
с коэффициентом 
.
Описанный процесс переноса не может длится бесконечно, так как все вектора, переносимые вправо, различны. Поэтому через конечное число шагов мы обязательно столкнемся со случаем 1, который, как показано выше, ведет к образованию замкнутого маршрута.
Итак, допустив, что система векторов 
линейно зависима, мы пришли к противоречию с условием теоремы, согласно которому из коммуникаций системы R нельзя составить замкнутый маршрут. Остается принять, что система R состоит из линейно независимых векторов.
Достаточность условий теоремы доказана.
Назовем коммуникацию 
Т-задачи основной коммуникацией плана Х, если 
Тогда, используя теорему 3.4, можно сформулировать следующий признак проверки произвольного плана на опорность.
План 
Т-задачи является опорным (базисным), если из его основных коммуникаций нельзя составить замкнутый маршрут.
Теорема 5. Вектор 
является линейной комбинацией векторов системы R тогда и только тогда, когда из векторов этой системы можно составить маршрут, соединяющий пункты Ak и 
. Если этот маршрут имеет вид
то
. (1.26)
Доказательство этой теоремы основано на теореме 3.4. Пусть выражен в виде линейной комбинации векторов системы R. Добавив к ней вектор , получим систему линейно зависимых векторов. Тогда в силу теоремы 3.4 появляется замкнутый маршрут 
. Этот замкнутый маршрут должен содержать коммуникацию 
и, следовательно, все остальные коммуникации должны соединить 
и .
Тогда
.
Перенеся 
в правую часть, получим выражение (1.26), что и требовалось доказать.
| 1 | 2 | 3 | 4 | 5 | 6 | i /j |
 | 1 |  |  + | 1 | ||
  1 | 1 | 2 | ||||
| X = |   1 |  1 | 3 | |||
 1 | 1 | 4 | ||||
 1 | 1 | 1 | 5 | |||
| Рис. 3.3. | ||||||
Рассмотрим произвольную матрицу 
. Между позициями матрицы Х и векторами 
можно установить следующее соответствие. Вектор соответствует элементу 
матрицы Х. Тогда можно задать систему из векторов 
, выделив единицами соответствующие элементы матрицы Х. Рассмотрим матрицу на рис3. Здесь единицами отмечена система векторов R: