Оптимальное распределение ресурсов, страница 10

Поставщик	Потребители								Запасы	Ui
	1		2		3		4
1	0	-2	120			-3		-3	120	-1
		2		1		3		2
2	80		0	-2	60			-2	140	-2
	6	1		4	5	1		2
3	170		60		0	-3		-3	230	-2
	7	1	8	2		4		3
4		-1		-1	140		60		200	-3
		3		4	4	2	3	1
5		1		2		1	90		90	-2
		0	1	0		0	2	0
Потребность	250		180		200		150
Vj	-1		0		-1		-2

890

, что соответствует теории:

Рассчитаем новую систему потенциалов. Имеем систему уравнений:

Пусть , тогда

                     

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

. В нечетных вершинах значения увеличатся на q, в четных уменьшатся на q.

Получим новое опорное решение:

Поставщик	Потребители								Запасы	Ui
	1		2		3		4
1	0	0	120			-1		-1	120	-2
		2		1		3		2
2	20		0	-4	120			-2	140	-1
		1		4		1		2
3	230		0	-2	0	-3		-3	230	-1
		1		2		4		3
4		-1		-3	80		120		200	-2
		3		4	2	2	3	1
5		1	60			1	30		90	-1
		0		0	1	0	4	0
Потребность	250		180		200		150
Vj	0		-1		0		-1

770

, что соответствует теории:

Рассчитаем новую систему потенциалов. Имеем систему уравнений:

Пусть , тогда

                     

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

. В нечетных вершинах значения увеличатся на q, в четных уменьшатся на q.

Получим новое опорное решение: