Лабораторная работа 13. Решение транспортной задачи в матричной постановке

Рассмотрим пример, в котором требуется решить транспортную задачу методом потенциалов , что значения a[i], b[j],c[i,j] (iÎ[1..4], jÎ[1..3]), заданы в таблице 1.

Таблица 1.

	j
I	Bj Ai
1
3
4

Решение.

Транспортная задача имеет решение тогда и только тогда, когда выполняется соотношение :

В данном случае, , поэтому необходимо ввести в рассмотрение фиктивного (внешнего) потребителя (№4) :

b[4]= =12-11=1

Положим для всех iÎ[1..4] с[i,4]=100

Определим исходное базисное решение методом северо-западного угла.

Таблица 2.

	j	1		2		3		4
i	Bj Ai	1	7	3	1	Ui
1		1	1	2	1	2		100		0
		0	-	0	+	-4		-3
2		2		3	4	1		100		-1
		0		0		-2		-2
3		1		4	1	3		100		-2
		2	+	0	-	-3		-1
4		3		5	1	1	3	100	1	-3
		1		0		0		0
	Vj	1	2	-2	97	Ui Vj

Стоимость перевозок составит: L(x)= 127

По критерию оптимальности определим, является ли найденное решение наилучшим. d[3,1] =max{ d[i,j]| iÎ[1..4], jÎ[1..4] }=2 ³ 0, значит полученное базисное решение не является оптимальным и необходимо перейти к новому базису.

Строим цикл П, который будет состоять из клеток x[3,1], x[1,1], x[1,2], x[3,2], в позициях q которых записываются соответственно ‘+’, ‘-’, ‘+’ ,‘-’. Среди значений x[i,j], в клетках которых записаны ,‘-’ находим минимальное Q=min x[i,j]. Оно равно 1, и достигается на клетке [1,1]. Т.о. клетку [3,1] вводим в базис, а клетку [1,1] выводим из базиса.

Пересчитаем значения x[i,j] для нового базиса.

Таблица 3.

	j	1	2	3	4
I	Bj Ai	1	7	3	1	Ui
1	2	1		2	1	2		100		0
		-2		0		-4		-3
2	4	2		3	4	1		100		-1
		-2		0		-2		-2
3	1	1	1	4	0	3		100		-2
		0		0		-3		-1
4	5	3		5	1	1	3	100	1	-3
		-1		0		0		0
	Vj	-1	2	-2	97	Ui Vj

Стоимость перевозок составит: L(x)=125. По критерию оптимальности определим, является ли найденное решение наилучшим. max{ d[i,j]| iÎ[1..4], jÎ[1..4] }£ 0, значит полученное базисное решение является оптимальным Стоимость перевозок без учета фиктивного потребителя составит L(x)=25

Задание. Решить транспортную задачу методом потенциалов, значения a[i] (iÎ[1..4]) и b[j] (jÎ[1..3]) заданы в таблице 4, значения c[i,j] задать произвольным образом.

Таблица 4