Вырожденность

Решение называется вырожденным, если число перевозок в транспортной таблице меньше, чем (т.+ п - 1). Данную проблему можно разрешить, проставив в независимые клетки очень маленькие, по сути равные нулю объемы перевозок. Число перевозок увеличивается таким образом до (т + а. - 1). Выявить клетки, которые следует использовать для этой цели, поможет алгоритм метода МОДИ проверки решения на оптимальность.

□ Пример 13.6. Три торговых склада (X, Y и Z) могут осуществлять постав­ки 6, 3 и 4 единиц продукта в три магазина (L, М и N), спрос которых равен 4, 5 и 1 единицам соответственно. Значения единичной стоимости транспортировки указаны в приведенной ниже таблице.

Таблица 13.24. Исходная информация

Торговый склад	Магазин, ф. ст./ед.	Общее предложение
L М N
X Y Z	6 4 9 5 3 2 2 3 6	6 3 4
Общая потребность	4 5 1

482 Ч. 4. Моделирование в бизнесе

Как следует распределить перевозки, чтобы общая стоимость транспортировки была минимальной?

Решение.

Общее предложение составляет 13 единиц, что превышает общую потребность в 10 единиц, поэтому в задачу вводится фиктивный магазин, потребность которого в продукции балансирует излишек предложения торговых складов. Чтобы найти начальное распределение перевозок, применим метод Вогеля:

Таблица 13.25. Начальное распределение перевозок, полученное методом Вогеля

Торговый склад		Розничный магазин		Общее предло­жение	Штрафная стоимость
L	М	N	Фиктивный
X Y Z										4, 2 2
		:	J				,
								■а 1 п	2 12
		:	>
								+G-	2 1 1
	л	. ■
Общая потребность	4 0	5 3 0	1 0
1-й штраф 2-й штраф 3-й штраф	3 3	0 0 0	4г

Значение стоимости транспортировки составит:

4x3 + 0x3 + 3x2 + 2x1+2x4 = 28 ф. ст.

Для того, чтобы решение являлось базисным, оно должно включать (3 + 4 — 0 = 6 переменных, тогда как в нашей задаче число перевозок равно лишь 5. Найденное решение является вырожденным. Поступая в соответствии с алгоритмом метода МОДИ, мы должны ввести нулевую перевозку, чтобы использовать в качестве запол­ненной одну из пустых клеток. Этот прием позволяет получить требуемое число перевозок, равное 6. Затем можно будет рассчитать значения всех компонент и и v, a следовательно, и теневые цены.

Реализацию алгоритма метода МОДИ мы начнем, используя 5 заполненных клеток, соответствующих начальному распределению перевозок. Дополнительная

Гл. 13. Транспортная задана и задача о назначениях 483

нулевая перевозка будет введена только тогда, когда без нее продолжение алгоритма будет невозможно. Обратимся к данным табл. 13.26.

Таблица 13.26. Проверка вырожденного решения на оптимальность — метод МОДИ

Торговый склад	Розничный магазин	06u<ee предложение
L	М	N	Фиктивный
X Y Z	С		.	4 5	©	.	0 J	u, =0 6
£		:	>			©	u2 = -l 3
<		Q		D	D	©	u3 = 3 4
Общая потребность			l
	v, = -l	v2 = 4	v3 = 3	y4 = 0

Заполненные клетки используются для расчета соответствующих компонент по строкам и по столбцам из соотношения: с,. = u, + v. при условии, что и₍ = 0. Значения v₂, v₄, u₂ и v₃ можно найти, не испытывая никаких затруднений, однако, значения и₃ и v₍ рассчитать нельзя. Для этого необходимо иметь дополнительную заполненную клетку.

Нулевую перевозку можно поместить в пустую клетку столбца v₍ или строки и^. Какая из этих клеток будет выбрана, значения не имеет. Пусть выбрана клетка (Z, N). Теперь можно завершить алгоритм и найти значения теневых цен для пустых клеток из соотношения Sy ■ Сц - (uj + V:). Соответствующие величины приведены в табл 13.26. Как видно из таблицы, в двух клетках теневые цены принимают отрицательные значения. Следовательно, полученное распределение перевозок является неоптимальным, и необходимо осуществить их перераспределение, используя при этом клетки (Z,M) или (Z, фиктивный). Начнем с клетки (Z,M), поскольку ей соответствует большее по абсолютной величине значение теневой цены. Ступенчатый цикл для клетки (Z,M) и движение объемов перевозок по входящим в него клеткам можно представить в виде табл. 13.27.

Чтобы определить число единиц, которые следует перемещать вдоль построенного цикла, обратимся к клеткам (Y,M) и (Z,N), помеченным знаком "-", количество перевозок в которых равно 2 и 0 единицам.

484 Ч. 4. Моделирование в бизнесе

Таблица 13.27. Ступенчатый цикл для клетки (Z.M)

М N

Y

Z

Заполненная 2	Заполненная + 1
Проверяемая +		Нулевая перевозка

Это означает, что по циклу следует осуществлять перемещение нулевой пере­возки таким образом, чтобы клетка (Z, N) снова стала пустой, а клетку (Z, М) предполагается использовать при распределении перевозок, поскольку в нее поме­шается нулевая перевозка. Остальные перевозки остаются без изменений. При дальнейшей проверке данного распределения на оптимальность выясняется, что значения всех теневых цен положительны. Данное распределение перевозок опти­мальное. Это предполагает, что начальное решение, включающее 5 переменных, также оптимально. Обратимся к данным табл. 13.28.

Таблица 13.28. Проверка оптимального решения — метод МОДИ

С торгово­го склада		В магазин		Общее предложение
L	М	N	фиктивный
X Y Z	G	з)	.		d		.	i	и, = 0 6
								u, = -l 3
©	:	г		©
								u, = -l 4
	Ь	и	©	©
Общая потребность
	v, = 3	vj-4	v,-3	vt = 0

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

Гл. 13. Транспортная задача и задача о назначениях ____ 485

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

МАКСИМИЗАЦИЯ

Алгоритм решения транспортной задачи предполагает, что ее целевая функция стремится к минимуму, Однако если некоторая проблема требует максимизации целевой функции перед тем, как применять для решения этой задачи стандартный алгоритм, его необходимо немного модифицировать. Например, мы намерены по условиям примера 13.5 осуществить перевозку товаров таким образом, чтобы максимизировать общий доход. В этом случае нам необходима информация о единичных доходах от транспортировки товаров между всеми пунктами производства и назначения. Модификация заключается в умножении всех значений единичного дохода на (- 1), а затем поступают обычным образом.