Алгоритм метода потенциалов. 2. Дальше метод потенциалов состоит из однотипных шагов, на каждом из которых:

1. Строится выходной ДБР.

2. Дальше метод потенциалов состоит из однотипных шагов, на каждом из которых:

i) Вычисляются потенциалы u_i, i=1...,m, и v_j, j=1...,n;

ii) Вычисляются оценки D ij переменных x_ij, i=1...,m, j=1...,n;

iii) Анализируются найденные оценки D ij. Если D ij ³ 0 для x_ij = 0 та D ij £ 0 для x_ij = r_ij, то текущий ДБР оптимальный. В другом случае переходят к улучшению текущего ДБР (п. п. iv) и v)).

iv) Строится цикл.

v) Находится новый ДБР.

Шаг закончен. Переход к пункту и).

Программное обеспечение.

Обучающий модуль, с помощью которого транспортная задача с ограниченными пропускными способностями коммуникаций Решается в диалоге с пользователем за выложенным алгоритмом, вызывается из раздела «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПО–МО.

Задание.

Решить методом потенциалов транспортные задачи, условия которых задаются модулем с помощью команды «Данные» главного меню (задачи №1 – №9), а также следующие задачи:

1)		6	2	5	3			16	34	15	19
	C =	3	6	9	7	,	R =	13	17	12	4	,
		7	1	6	5			17	19	2	4

а = (74, 33, 19), b = (28, 70, 15, 13);

2)		2	1	5	5			13	10	31	15
	C =	2	3	7	4	,	R =	20	28	7	22	,
		9	5	7	1			19	6	15	8

а = (63, 72, 17), b = (33, 40, 43, 36);

3)		3	6	6	4			5	8	6	4
	C =	3	2	2	6	,	R =	29	24	15	17	,
		1	4	10	7			20	5	10	6

а = (13, 79, 34), b = (49, 30, 22, 25);

4)		5	1	2	7			4	12	5	5
	C =	6	1	8	7	,	R =	20	10	37	10	,
		2	9	4	10			25	10	10	15

а = (20, 76, 54), b = (40, 30, 52, 28);

5)		9	6	6	1			15	10	34	7
	C =	8	10	9	2	,	R =	31	23	20	11	,
		5	9	2	6			11	15	4	10

а = (64, 75, 21), b = (57, 33, 44, 26);

6)		6	4	8	5			20	5	15	12
	C =	2	8	3	2	,	R =	45	20	21	19	,
		1	7	2	8			8	20	12	4

а = (42, 99, 27), b = (68, 40, 30, 30);

7)		5	6	10	3			37	20	7	21
	C =	6	4	7	2	,	R =	5	26	7	11	,
		8	8	3	7			5	20	25	10

а = (78, 37, 53), b = (38, 60, 30, 40);

8)		6	1	9	3			16	30	21	30
	C =	9	2	9	7	,	R =	18	4	5	11	,
		3	2	10	6			30	4	29	15

а = (77, 24, 70), b = (56, 30, 40, 45);

9)		8	4	6	8			12	20	30	20
	C =	8	9	9	6	,	R =	25	4	3	2	,
		9	10	4	7			33	10	30	10

а = (72, 29, 68), b = (65, 24, 50, 30);

10)		1	3	8	7			10	26	23	8
	C =	9	4	5	10	,	R =	6	18	30	5	,
		9	7	2	8			9	2	25	3

а = (53, 45, 38), b = (21, 30, 75, 10).

Ответы:

1) L (x*)= 444. 2) L (x*)= 538. 3) L (x*)= 413. 4) L (x*)= 837. 5) L (x*)= 1091.

6) L (x*)= 700. 7) L (x*)= 800. 8) L (x*)= 885. 9) L (x*)= 1134. 10) L (x*)= 649.

Лабораторная работа 7.