Реферат: Сетевое моделирование при планировании. Задача о коммивояжере...

S₁₂ = 4

S₁₃ = 7

S₁₄ = 8

S₂₃ = 3

S₂₅ = 5

S₃₄ = 8

S₃₅ = 9

S₄₅ = 9

Математическая модель

Обозначим за х_{1, 2, …, 8} перевозки по маршрутам 12, 13, 14, 23, 25, 34, 35, 45 соответственно, а за х₉ – пропускную способность конечного узла сети.

Сумма входящих в каждый узел потоков равна сумме выходящих, причем интенсивность каждого потока не может превышать пропускную способность своего участка сети. Поэтому система условий-ограничений выглядит следующим образом.

х₉ - х₁ – х₂ – х₃ = 0 ⁽¹⁾

х₁ – х₄ – х₅ = 0 ⁽²⁾

х₂ + х₄ – х₆ – х₇ = 0 ⁽³⁾

х₃ + х₆ – х₈ = 0 ⁽⁴⁾

х₅ + х₇ + х₈ – х₉ = 0 ⁽⁵⁾

х₁ £ 4 ⁽⁶⁾

х₂ £ 7 ⁽⁷⁾

х₃ £ 8 ⁽⁸⁾

х₄ £ 3 ⁽⁹⁾

х₅ £ 5 ⁽¹⁰⁾

х₆ £ 8 ⁽¹¹⁾

х₇ £ 9 ⁽¹²⁾

х₈ £ 9 ⁽¹³⁾

Функция цели: х₉ max

Таблица 3.1

Исходная матрица

№	х1	х2	х3	х4	х5	х6	х7	х8	х9	Знак	Св.чл.
1	-1	-1	-1	0	0	0	0	0	1	=	0
2	1	0	0	-1	-1	0	0	0	0	=	0
3	0	1	0	1	0	-1	-1	0	0	=	0
4	0	0	1	0	0	1	0	-1	0	=	0
5	0	0	0	0	1	0	1	1	-1	=	0
6	1	0	0	0	0	0	0	0	0	£	4
7	0	1	0	0	0	0	0	0	0	£	7
8	0	0	1	0	0	0	0	0	0	£	8
9	0	0	0	1	0	0	0	0	0	£	3
10	0	0	0	0	1	0	0	0	0	£	5
11	0	0	0	0	0	1	0	0	0	£	8
12	0	0	0	0	0	0	1	0	0	£	9
13	0	0	0	0	0	0	0	1	0	£	9
Ф. ц.	0	0	0	0	0	0	0	0	1	max

Решение

х₁ = 4

х₂ = 7

х₃ = 8

х₅ = 4