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

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_сток