Лабораторная работа 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

№ варианта	А[I]	В[j]