Транспортная задача с ограниченными пропускными способностями.

Важной в практическом отношении является Т_d - задача, в которой существуют ограничения на пропускные способности коммуникаций.

Пусть - пропускная способность коммуникации A_i B_j.

 

Тогда  (1.9)

 

Т-задача состоит в минимизации Ц.Ф. (1.3) при условиях (1.1), (1.2), (1.9). Даже в случае разрешимости Т-задачи, Т_d – задача может оказаться неразрешимой, поскольку величины пропускных способностей будут недостаточны для полного вывоза продукта из п. А_і, и полного ввоза продукта в п. В_j. Поэтому для Т_d – задачи вводят еще два условия:

 

 (1.10)

 (1.11)

 

Но и при добавочных условиях (1.10), (1.11) Т_d – задача не всегда разрешима. Для установления совместимости всех условий делают попытку построить любой план Т-задачи. Если удается, то система уравнений (1.1), (1.2), (1.9) – (1.11) совместна. В противном случае Т_d – задача неразрешима.

Теорема 3. Для оптимальности плана Х₀ Т_d – задачи необходимо и достаточно существование таких чисел v₁, v₂., v_n, – u₁, – u₂., – u_m, при которых

 

если , (1.12)

если 0 < , (1.13)

если . (1.14)

 

Смысл условий оптимальности (1.12) – (1.14) состоит в следующем:

если приращение стоимости продукта v_j – u_j меньше транспортных расходов c_ij, то такая перевозка убыточна, а потому . Если же приращение стоимости продукта v_j – u_j больше транспортных расходов c_ij (3.1.14), то эта перевозка прибыльна, а потому ее величина должна быть максимальной, т.е. .

Таким образом, теорема 3.3 по существу выражает принцип рентабельности для T_d – задачи.

Открытые транспортные модели. Существует ряд практических задач, в которых условие баланса не выполняется. Такие модели называются открытыми. Возможные два случая:

 

1)

2)

 

В первом случае полное удовлетворение спроса невозможно.

Такую задачу можно привести к обычной транспортной задаче следующим образом. Обозначим через величину штрафа из-за неудовлетворения запросов на единицу продукта в пункте B_j.

Тогда требуется минимизировать

 

 (1.15)

 

при условиях

 

где - неудовлетворенный спрос.

Задачу (3.1.15) приводят к обычной Т-задаче введением фиктивного пункта производства А_m+1, с объемом производства и транспортными издержками В таком случае Т-задача будет иметь вид

минимизировать

при условиях

 

 

В найденном решении х_опт полагаем все перевозки из фиктивного пункта А_m+1 равными нулю, т.е. .

Рассмотрим теперь второй случай. Введем фиктивный пункт B_n+1 с объемом спроса . Пусть - это убытки (штраф) в пункте А_і за единицу невывезенного продукта. Обозначим через сии_,n+1 = удельные транспортные издержки на перевозку единицы продукта с А_і в В_n+1. Тогда соответствующая Т-задача запишется так:

 

минимизировать  (1.16)

 

при условиях

 

 (1.17) – (1.18)

В найденном решении все перевозки в фиктивный пункт В_n+1 считают равными нулю.

Опорные планы Т-задачи

Опорным (базисным) планом Т-задачи называют любое ее допустимое, базисное решение. Понятие опорного плана имеет наглядную геометрическую интерпретацию.

Последовательность коммуникаций

 

 (1.19)

 

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

 

     …

    .  

Рис. 2

 

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

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

 

 

Во втором случае процесс переноса продолжается, и поскольку , среди векторов Р_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:

 

.

 

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

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

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

 

.

 

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

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

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

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

В первом случае из элементов множества S составить цикл невозможно. Следовательно, соответствующий план Х является опорным.

Во втором случае множество S содержит цикл (циклы) и соответствующий план Х не является опорным (базисным). На рис. 4 показаны два плана Т-задачи: небазисный (рис. 4, а) и базисный (рис. 4, б). Номера линий указывают порядок вычеркивания. Звездочками отмечены элементы, которые вычеркнуть нельзя. Они образуют цикл.

 

1* *1 1* 1* 1 1 *1 *1 Рис. 4. а)

5 6 11 7 8 1 1 9 1 1 2 1 10 1 1 1 3 1 4 1 Рис. 4. б)

Нахождение начальных опорных планов

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

Метод северо-западного угла. Основную идею метода рассмотрим на конкретном примере.

Пусть дана Т-задача с четырьмя пунктами производства А₁, А₂, А₃, А₄ с объемами производства и пунктами потребления с объемами потребления соответственно .

Построим матрицу Х размером 4х4, причем для удобства вычислений снизу от нее оставим строку b_j, справа столбец a_i. Кроме того, снизу от b_j образуем строки , где будем записывать неудовлетворенные потребности, а справа от a_i – столбцы , где будем записывать остатки невывезенного продукта (табл. 2).

Заполнение таблицы начинают с левого верхнего элемента таблицы X – x₁₁, что и обусловило название метода. Сравнив с и выбрав меньшее из них, получим x₁₁=1. Записываем это значение в матрицу Х₀. Так как первый выбор произведен по строке, то остальная часть первой строки должна быть заполнена нулями. Во вспомогательном столбце записываем остатки невывезенного продукта, , а в строке – неудовлетворенные потребности после одного шага заполнения.

Переходим к второй строке и начинаем заполнение с элемента (новый северо-западный угол незаполненной части таблицы 2). Сравнивая выбираем меньшее из них, и потому . Остальную часть второй строки заполняем нулями. Далее заполняем таблицу аналогично. После окончания процесса заполнения будем иметь начальный план Х₀. Полученный план является базисным (опорным), так как из его ненулевых элементов нельзя составить цикл. Кроме того, он удовлетворяет условиям задачи, так как

 

.

Таблица 2

Х
	1	0	0	0	1	0	0	0	0	0	0
	2	0	0	0	2	2	0	0	0	0	0
	2	1	0	0	3	3	3	1	0	0	0
	0	0	2	2	4	4	4	4	4	2	0
	5	1	2	2
	4	1	2	2
	0	1	2	2
	0	0	2	2
	0	0	0	2
	0	0	0	0

 

Формальное описание алгоритма. I. Определяют верхний левый элемент матрицы Х:

 

.

 

Возможные три случая: а) если то и всю первую строку, начиная со второго элемента, заполняют нулями; б) если , то , а все оставшиеся элементы первого столбца заполняют нулями; в) если

 

то

 

и все оставшиеся элементы первых столбцов и строки заполняют нулями.

Находим

 

 

на этом один шаг метода заканчивается.

2. Пусть уже проделано k шагов. (k+1) – й шаг состоит в следующем. Определяют верхний левый элемент незаполненной части матрицы Х. Пусть это будет элемент

 

причем

 

, (1.27)

 

где

 

 (1.28)

 

Если , то заполняем нулями строку , начиная с ( +1) – го элемента. В противном случае заполняем нулями столбец , начиная с элемента ( +1). Если , то заполняем нулями остаток строки и столбца . Далее вычисляем . На этом (k+1) – й шаг заканчивается. Описанный процесс повторяется до тех пор, пока матрица Х не будет заполнена полностью.