Методы оптимальных решений (стр. 12 )

При описанном выше способе распределения продукции план Х1 будет содержать не больше, чем m + n — 1 положительных перевозок или занятых клеток, где m — число поставщиков, n — число потребителей. Остальные компоненты плана Х1 соответствующие нулевым перевозкам, будем называть свободными клетками. Если число занятых клеток k = m + n — 1, то план перевозок называется невырожденным, если k < m+ n — 1, то — вырожденным. Для плана Х1 имеем: k = 6, m + n —1 = 6 и, значит, k = m + n—1. Следовательно, план Х1 является невырожденным. Заметим что, если план перевозок окажется вырожденным, то следует часть свободных клеток условно считать занятыми, записан в них нули, так чтобы общее число занятых

клеток было равно m + n — 1. В дальнейшем с этими нулями следует “обращаться” так же, как и с положительными перевозками.

Подсчитаем суммарную стоимость перевозок по плану Х

¦(Х1) = 9 ´ 20 + 4 ´ 5 + 3 ´ 5 + 6 ´ 10 + 8 ´ 20 + 0 ´ 15 = 180 + 20 + +15 + 60 + +160 = 435.

Проверим план Х1 на оптимальность. Найдем потенциалы u1, u2, u3 поставщиков и потенциалы n1, n2, n3,n4 потребителей, так чтобы выполнялись условия 10 и 20 критерия оптимальности плана перевозок. По условию 20 для занятых клеток:

u1 + v1 = 9, u2 + v2 = 3, u3 + v3 = 8,

u1 + v2 = 4, u3 + v3 = 6, u3 +v4 =

Один из потенциалов всегда задается произвольно, например, за дадим u1 = 0. Тогда из системы (69) получим v1 = 9, v2 = 4, u2 = -1, n3 = 7,u3 = 1, n4 = —1. Эти потенциалы полезно записать справа и снизу от плана Х1. По условию 10 для свободных клеток:

u1 + v3 £ 7, u2 + v1 £ 5, u3 + v1 £ 6,

u1 + v4 £ 0, u2 + v4 £ 0, u3 +v1 £

Подставив потенциалы, найденные из уравнений (69), в неравенства (70), получим

0 + 7 = 7 = 7, -1 + 9 = 8 > 5, 1 + 9 = 10 > 6,

0 - 1 = -1 < 0,= -2 < 0, 1 + 4 = 5 =

Мы видим, что не выполняются два неравенства системы (70), причем

D21 = с21 - (u2 + n1) = 5 - 8 = -3, D31 = с31 - (u3 + n1) = = -4.

Следовательно, план Х1 можно улучшить, введя в план перевозку х31= q, для которой разность D31 оказалась меньше разности D21. С этой целью составим так называемый цикл, имеющий начало в свободной клетке (3, 1), а остальные вершины — в занятых клетках последовательно увеличивая и уменьшая перевозки, попавшие в цикл, на величину q. В результате получим план Х2(q).

	9		4	7	0
20 - q		5 + q
5		3		6	0
5 - q		10 + q
	6	5		8		0
+q		20-q		15

Х2(q) =

Важно отметить, что при составлении цикла следует двигаться только по горизонтали или вертикали, так чтобы в каждую строку и каждый столбец плана перевозок, охваченных циклом, попали только две перевозки. Выберем q = min(20, 5, 20) = 5, то есть в качестве q выбирается наименьшая из перевозок, из которых q вычитается. При включении в план Х1 перевозки q = 5 суммарная стоимость перевозок изменится на D¦(Х1) = D31 ´ q = -4 ´ 5 = -20, то есть уменьшится на 20 ед. и для нового плана Х2 составит

¦(Х2) = ¦(Х1) + D¦(Х1) = = 415.

	9	4	7	0	u1 = 0
15
5	3		6	0	u2 = -5
15
	6	5		8		0	u3 = -3
6		15		15
n1 = 9	n2 = 4	n3 = 11	n4 = 3

Пересчитав перевозки, вошедшие в цикл плана Х2(q) при q = 5, получим новый план перевозок Х2.