Быстрый поиск

Контрольная работа: Постановка и основные свойства транспортной задачи

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

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

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

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

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

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

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

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

Таблица 5

C =	ai bj	4	6	8	6
	6	2(5)	2(4)	3(6)	4(11)
	8	6(12)	4(10)	3(9)	1(3)
	10	1(1)	2(6)	2(7)	1(2)

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

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

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

Рис. 6.

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

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

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

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


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

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