Вырожденные матрицы и способы борьбы

Выше отмечалось, что число занятых мест в таблице должно быть равно m+n-1. Однако на практике встречаются случаи, ког­да в процессе решения оно сокращается. Это явление называется вы­рождением. Рассмотрим это на примере, в табл. 3.8 имеется свободное место 12. Воспользуемся им для улучшения решениям.

Таблица 3.8

ПО	ПН
I	30 1	à - â + à â 1	0 1.2	3
II	0.8	â à + 3 â - à 50	90 1.3	20 0.9
III	4	2.6	1.8	30 1.3

При вычитании 50 из клеток П.2 и 1.3 значения их превращаются в 0. В результате сокращается число занятых клеток и невозмож­но воспользоваться методом потенциалов.

Для преодоления этого в одну из освободившихся клеток поста­вим 0 и будем считать эту клетку занятой (табл. 3.9). Число занятых мест в таблице равно 6 (т.е. m+n-1).

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

Транспортная задача может использоваться в различных сферах хозяйства связи. Ниже приведены два примера.

Таблица 3.8

ПО	ПН
I	â + à - à â 30 1	à + â àààààààààààà 50 1 â à -	0 1.2	3
II	0.8	àààààààààààà 3	90 1.3	20 0.9
III	4	2.6	1.8	30 1.3

Пример 1. Газеты поступают на четыре вокзала города в количествах a₁, a₂, a₃, a₄. Нужно развести их по 4 отделениям связи в количествах b₁, b₂, b₃, b₄:

a₁=120, a₂=144, a₃=168, a₄=192,

b₁= 96, b₂=168, b₃=120, b₄=192.

Расстояние от вокзалов до отделений связи приведены в таблице. Оставшиеся Газеты реализуют на вокзале. Составить оптимальный план перевозок.

Таблица 3.10

bj ai	b1	b2	b3	b4
a1	7.2	11.7	10.8	17.1
a2	9.9	6.3	5.4	12.6
a3	8.1	11.7	3.6	9.9
a4	14.4	15.3	16.2	2.7

Пример 2. Распределить емкость трех АТС (5000, 7000, 10000) между четырьмя районами с потребностями 7000, 7000, 6000, 5000 так, чтобы обеспечить минимальный расход кабеля. Расстояние между районами и АТС приведены в таблице.

Таблица 3.11