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

 (1.19)

называют маршрутом, соединяющим пункты  (рис. 2).

   …

  .  

Рис. 2

Используя маршрут, составленный из коммуникаций, можно осуществить перевозку продукта из пункта  в пункт , проходя через пункты .

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

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

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

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

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

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

.

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

Так как из выделенных единицами позиций на рис. 3 нельзя составить замкнутый маршрут, то данная система линейно независима и образует базис.

Введем теперь в систему  вектор , отметив его знаком '+'. Чтобы разложить  по векторам системы R, составим цепочку из выделенных элементов, которая замыкается на элементе :

.

При небольших размерах матрицы Х визуальное отыскание замкнутых цепочек в ней представляет значительные трудности. В таком случае прибегают к формализованному методу вычеркивания. Метод вычеркивания позволяет выделить в произвольном плане Х Т-задачи замкнутую цепочку, если она существует.

Этот метод состоит в следующем. Выделив в плане Х множество ненулевых элементов, обозначаемое через S, выясним, существуют ли во множестве элементов S циклы. Для этого просматриваем одну за другой строки плана Х и вычеркиваем строки, не содержащие элементов S, и строки, которые содержат не более одного элемента S (ненулевой элемент). Просмотрев все строки плана Х, переходим к столбцам и вычеркиваем те из них, которые содержат не более одного элемента S.

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

Страницы: 1, 2, 3, 4, 5