Метод минимального элемента

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

Формальное описание алгоритма. Элементы матрицы нумеруют, начиная от минимального в порядке возрастания, а затем в этом же порядке заполняют матрицу Х₀.

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

Дале этот процесс повторяют с незаполненной частью матрицы Х₁.

Пример 1. Найти начальный базисный план методом минимального элемента для Табл. 3. следующей задачи.

Таблица. 3.

Цифры в скобках указывают порядок заполнения элементов в матрице Х₀ (табл. 3.4).

Соответствующее значение целевой функции равно

3*8 + 1*5 + 3*7 + 5*2 + 6*4 + 8*1 = 92

Таблица 4

Х0
	0	3	1	7	11	4	3	0
	5	6	0	0	11	6	0
	0	0	8	0	8	0
	5	9	9	7
	0	3	1	0
		0	0

Решение транспортной задачи при вырожденном опорном плане

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

Рассмотрим два случая.

1. Вырожденный план является начальным Х₀. Тогда выбирают некоторые нулевые элементы матрицы Х₀ в качестве базисных так, чтобы при этом не нарушалось условие базисного плана. Число этих элементов равняется . Далее данные элементы заменяют на (где – произвольное, бесконечно малое число) и рассматривают их как обычные базисные элементы плана. Задачу решают как невырожденную, а в последнем оптимальном плане Х_k вместо пишут нули.

2. Вырожденный план получается при построении плана Х_k+1 на базе Х_k, если цепочка в плане Х_k содержит не менее двух минимальных нечетных элементов. В таком случае в матрице Х_k+1 полагают равным нулю только один из этих элементов, а остальные заменяют на , и далее решают задачу как невырожденную. Если на k-м шаге , то при переходе от Х_k к Х_k+1 значение целевой функции не изменяется, а в базис вводится элемент , для которого перевозка станет равной .

Пример 2. Решим Т-задачу со следующими условиями (см. Табл.6)

Проверим условие баланса

Предварительный этап. Методом минимального элемента строим начальный базисный план Х₀ (Табл. 5)

Таблица 5

Так как m + n – 1 = 6; k = 4, то план х₀ – вырожденный; l = m+ n -1 – k = 2.

Два нулевых элемента Х₀ делаем базисными так, чтобы не нарушить условие опорности. Выберем в качестве базисных элементов , и положим их равными .

Схема перевозок для плана Х₀ показана на рис. 6.

Рис. 6.

Для вычисления предварительных потенциалов выберем начальный пункт А₁ и допустим, что . Потенциалы всех остальных пунктов вычисляем по формулам

,

Для проверки оптимальности плана х₀ строим матрицу С₁, элементы которой вычисляем по соотношению

Так как в матрице С₁ элемент С₂₃ = – 3 < 0, то план Х₀ – неоптимальный.

Первая итерация. Второй этап.

		*	6*	0	0						6	0	0
X0 =		0*	*	8	0+			X1 =		0	0	6	
		4	0	0	6*		1 = 			4	0	0	6

В результате построения Х₁ в базис вводим . План Х₁ является вырожденным (в цепочке есть два минимальных элемента). Поэтому один из этих элементов, например , в плане Х₁ заменяем на .

Вторая итерация. Первый этап

			0	2	2					0	0	-1	2
С1 =		2	0		-3		+3	С2 =		5	3	0	0
		0	1	2	0					0	1	-1	0
				-3

Второй этап.

			6	0	0						6	0	0
X1 =		0	0	8*	*			X2 =		0	0	2	6
		4	0	0+	6*		3 =min {8, 6}= 6			4	0	6	0

Третья итерация. Первый этап.

				-1	2		+1			0	0	0	3
С2 =		5	3					С2 =		4	2	0	0
			1	-1	0		+1			0	1	0	1
		-1	-1

Так как в матрице С₃ нет отрицательных элементов, план Х₂ – оптимальный.