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

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

740

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

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

Пусть , тогда

                     

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

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

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

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

740

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

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

Пусть , тогда

                     

Припишем значения потенциалов соответствующим строкам и столбцам. Вычисляем значения невязок для всех клеток без перевозок. Записываем их в правый верхний угол каждой клетки.

Все невязки неположительны, следовательно, оптимальное решение найдено.

Таким образом, минимальная стоимость перевозок:

740

             Соответствующие этой стоимости объемы перевозок:

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