Контрольная работа: Постановка и основные свойства транспортной задачи

В процессе этого движения коммуникации, стоящие на четных местах в (1.19), будут пройдены в противоположном направлении.

Маршрут (1.19), к которому добавлена коммуникация называется замкнутым маршрутом или циклом.

Способ проверки произвольного плана Т-задачи на опорность, основан на следующих двух теоремах (прямой и обратной).

Теорема 4. Система, составленная из векторов Т-задачи, является линейно независимой тогда и только тогда, когда из коммуникаций, соответствующих этим векторам, нельзя составить замкнутый маршрут.

Доказательство. Необходимость . Пусть векторы линейно независимы. Если бы существовал замкнутый маршрут из коммуникаций и , то, очевидно, начиная движение из пункта и последовательно проходя все пункты по последней коммуникации мы вернемся в начальный пункт . Тогда справедливое равенство

(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) можно образовать замкнутый маршрут. Таким маршрутом является