Сетевое моделирование при планировании. Задача о коммивояжере... (стр. 2 из 5)

Из-за сокращения критического пути проект будет введен в эксплуатацию на 5,4 недели раньше. Т. к. прибыль за неделю составляет 100 тыс. $, то за этот срок она составит 100 тыс. $ * 5,4 = 540 тыс. $.

В результате дополнительная прибыль с учетом возрастания затрат на проведение работ составит 540 тыс. $ - 124,8 тыс. $ = 415,2 тыс. $

Задание №2

Тема: Графы

Задача о коммивояжере

Имеется 4 пункта. Время переезда из пункта I в пункт j представлено в таблице 2.1.

Таблица 2.1

Исходные данные

Из пункта i	В пункт j
	1	2	3	4
1	0	8	8	6
2	4	0	6	12
3	10	12	0	18
4	8	10	4	0

График представлен на рисунке.

Требуется найти оптимальный маршрут, вычеркнув из таблицы отсутствующие маршруты.

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

Обозначим за x маршруты, приведенные в таблице 2.2.

Таблица 2.2

Обозначения

xi	Пункт отправления	Пункт назначения	Время переезда
x1	1	2	8
x2	1	3	8
Продолжение
x3	1	4	6
x4	2	1	4
x5	2	3	6
x6	2	4	12
x7	3	1	10
x8	3	2	12
x9	3	4	18
x10	4	1	8
x11	4	2	10
x12	4	3	4

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

x₁ + x₂ + x₃ = 1 ⁽¹⁾

x₄ + x₅ + x₆ = 1 ⁽²⁾

x₇ + x₈ + x₉ = 1 ⁽³⁾

x₁₀ + x₁₁ + x₁₂ = 1 ⁽⁴⁾

x₄ + x₇ + x₁₀ = 1 ⁽⁵⁾

x₁ + x₈ + x₁₁ = 1 ⁽⁶⁾

x₂ + x₅ + x₁₂ = 1 ⁽⁷⁾

x₃ + x₆ + x₉ = 1 ⁽⁸⁾

Функция цели: 8x₁ + 8x₂ + 6x₃ + 4x₄ + 6x₅ + 12x₆ + 10x₇ + 12x₈ + 18x₉ + 8x₁₀ + 10x₁₁ + 4x₁₂ min

Исходная матрица условий задачи представлена в таблице 2.3.

Таблица 2.3

№	x1	x2	x3	x4	x5	x6	x7	x8	x9	х10	x11	x12	Св.чл.	Зн
1	1	1	1	0	0	0	0	0	0	0	0	0	1	=
2	0	0	0	1	1	1	0	0	0	0	0	0	1	=
3	0	0	0	0	0	0	1	1	1	0	0	0	1	=
4	0	0	0	0	0	0	0	0	0	1	1	1	1	=
5	0	0	0	1	0	0	1	0	0	1	0	0	1	=
6	1	0	0	0	0	0	0	1	0	0	1	0	1	=
7	0	1	0	0	1	0	0	0	0	0	0	1	1	=
8	0	0	1	0	0	1	0	0	1	0	0	0	1	=
Фц.	8	8	6	4	6	12	10	12	18	8	10	4	min

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

Решение

x₃ = 1

x₅ = 1

x₇ = 1

x₈ = 0

x₁₁ = 1

Это означает, что на графике остаются только пути, соответствующие переменным х₃, х₅, х₇, х₁₁ (1 4, 2 3, 3 1, 4 2). Функционал равен 12, т. е. время пути будет равно 12 единицам. График при этом выглядит следующим образом.

Задание №3

Тема: Графы

Задача о максимальном потоке

Имеется трубопроводная сеть с заданной S_ij пропускной способностью каждого участка из i-го узла в j-й узел и мощностью насосной станции, расположенной в узле. Необходимо рассчитать максимальную пропускную способность сети из начального узла в конечный узел.

a

_исток a _сток

Пропускная способность S_ij , тыс. тонн

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