Улучшение плана поставок

Среди положительных величин выбирается максимальная. В нашем случае величины и являются максимальными. Выбирается какая-нибудь одна из них, например, величина . Клетка (1, 5) помечается знаком «+» в левом верхнем углу.

Смотрим, с какой занятой клеткой первой строки или пятого столбца можно соединить клетку (1, 5). Построим цикл, двигаясь от клетки (1, 5), например, по часовой стрелке.

В пятом столбце имеется единственная занятая клетка (4, 5), с которой можно соединить клетку (1, 5). Следующее звено ломаной должно находиться в четвертой строке. Так как в этой строке тоже единственная занятая клетка (4, 4), то ее следует соединить с клеткой (4, 5). Очередное звено ломаной должно находиться в четвертом столбце таблицы – это будет звено, соединяющее клетки (4, 4) и (3, 4).Следующее звено должно находиться в третьей строке, а в ней две занятые клетки. Для отыскания нужной клетки применяется метод проб и ошибок. Попробуем соединить клетки (3, 4) и (3, 3). Так как в одной строке таблицы не может быть более одного звена ломаной, то следующее звено должно быть расположено после такого соединения в третьем столбце таблицы. Однако в третьем столбце нет больше занятых клеток, поэтому таким путем нельзя замкнуть ломаную. Клетка (3, 3), следовательно, является тупиковой и ее не следует соединять с клеткой (3, 4). Остается единственная возможность – соединить клетку (3, 4) с занятой клеткой (3, 2). Далее процесс построения цикла пойдет однозначно.

Следующее звено должно находиться во втором столбце, поэтому соединяем клетки (3, 2) и (2, 2). Затем в цикл войдут клетки (2, 1) и (1, 1). Соединяя клетки (1, 1) и (1, 5), ломаная линия замыкается.

Начиная с клетки (1, 5) обойдем клетки цикла по часовой стрелке, отмечая их попеременно знаками плюс и минус.

В нашем примере четыре минусовых клетки в цикле – это клетки (4, 5), (3, 4), (2, 2) и (1, 1). Минимальная поставка находится в двух клетках: (2, 2) и (3, 4), т.е.

Переходим к новому плану поставок

	bj	58		22		18		22		33		ui
ai
30		–	5		8		6		2	+	0	10
		8								22
50			2		7		5		3		0	13
		50
40		+	1		4		3	–	5		0	7
				22		18		0
33			6		5		5	+	2	–	0	11
								22		11
vj		15		11		10		12		10		326

Перейдем ко второй итерации. Проверяем план на оптимальность. Находим потенциалы, согласованные с полученным планом. Пусть тогда

,

Считаем величины для свободных клеток.

, ,

, ,

, ,

, ,

, ,

,

План не оптимален, так как среди величин _ij имеются положительные. Находим max_ij = ₃₁ = 7.

	bj	58		22		18		22		33		ui
ai
30		–	5		8		6		2	+	0	15
		8								22
50			2		7		5		3		0	18
		50
40		+	1	–	4		3	–	5		0	19
		0		22		18
33			6	+	5		5		2	–	0	15
								22		11
vj		20		23		22		17		15		326

Клетку (3, 1) отмечаем знаком плюс и находим цикл. Минимальная поставка в минусовых клетках цикла равна Клетка (3, 1) при переходе к новой табл.5 занимается в данном случае нулевой поставкой, а клетка (3, 4), соответствующая минимальной поставке, освобождается. Так как , то новый план поставок совпадает со старым. Транспортные расходы по новому плану также останутся прежними, т.е. Однако потенциалы изменятся.

Выполним третью итерацию. Вычислим потенциалы, полагая Находим величины для свободных клеток табл.5.

Так как max_ij = ₄₂ = 3 > 0, то план неоптимален. Отмечаем клетку (4, 2) знаком плюс и строим цикл, который в данном случае образуют клетки (4, 2), (3, 2), (3, 1), (1, 1), (1, 5) и (4, 5).

	bj	58		22		18		22		33		ui
ai
30			5		8		6		2		0	9
		8								30
50			2		7		5		3		0	9
		50
40			1		4		3		5		0	10
		8		14		18
33			6		5		5		2		0	9
				8				22		3
vj		11		14		13		11		9		302

Выполним четвертую итерацию. Находим новую систему потенциалов, согласованную с полученным планом, полагая Проверяем план на оптимальность:

Все Следовательно, получен оптимальный план. При этом