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

2019-10-11

335

Обсуждений (0)

0.00 из 5.00 0 оценок

⇐ Предыдущая 1 234 Следующая ⇒

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

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

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

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

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

Таблица. 3.

A_i \ B_j	1	2	3	4	B_j / a_i
1	7⁽¹⁰⁾	8⁽¹¹⁾	5⁽⁷⁾	3⁽⁵⁾	11
2	2⁽³⁾	4⁽⁴⁾	5⁽⁸⁾	9⁽¹²⁾	11
3	6⁽⁹⁾	3⁽⁴⁾	1⁽¹⁾	2⁽²⁾	8
A_i / b_j	5	9	9	7	b_j \ a_i

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

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

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

Таблица 4

Х₀
	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

C =	a_ib_j	4	6	8	6
	6	2⁽⁵⁾	2⁽⁴⁾	3⁽⁶⁾	4⁽¹¹⁾
	8	6⁽¹²⁾	4⁽¹⁰⁾	3⁽⁹⁾	1⁽³⁾
	10	1⁽¹⁾	2⁽⁶⁾	2⁽⁷⁾	1⁽²⁾

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

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

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

Рис. 6.

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

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

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

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


	^*	6^*	0	0				6	0	0
X₀=	0^*	^*	8	0⁺		X₁ =	0	0	6	
	4	0	0	6^*	₁ = 		4	0	0	6

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