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

.

При использовании матрицы Х критерий проверки линейной независимости формулируется так: для линейной независимости системы векторов

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

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

Введем теперь в систему

вектор

, отметив его знаком '+'. Чтобы разложить

по векторам системы R, составим цепочку из выделенных элементов, которая замыкается на элементе

:

.

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

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

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

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

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

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

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

5 6 11 7 81 19 112 110 1 1 13 14 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. Определяют верхний левый элемент матрицы Х:

.

Возможные три случая: а) если

то

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

, то

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

то

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

Находим