Постановка и основные свойства транспортной задачи (стр. 3 из 7)

Доказательство. Необходимость. Пусть векторы

линейно независимы. Если бы существовал замкнутый маршрут из коммуникаций

и

, то, очевидно, начиная движение из пункта

и последовательно проходя все пункты

по последней коммуникации

мы вернемся в начальный пункт

. Тогда справедливое равенство

(1.20)

которое указывает на линейную зависимость векторов

.

Полученное противоречие доказывает необходимость условий теоремы 4.

Достаточность. Допустим, что из коммуникаций, отвечающих векторам

системы R, нельзя составить замкнутый маршрут. Докажем, что в таком случае R – линейно независимая система. Если предположить противное, т.е. линейную зависимость векторов системы R, то существуют такие числа

, среди которых не все нули, для которых выполняется условие

. (1.21)

Пусть, например

. Перенесем тогда соответствующий вектор вправо и получим

, (1.22)

где Е₁ образуется вычеркиванием в Е пары индексов (

). Компонента с номером

в правой части (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 тогда и только тогда, когда из векторов этой системы можно составить маршрут, соединяющий пункты A_k и

. Если этот маршрут имеет вид

то

. (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: