• Главная
• Биология и химия
• Иностранные языки и языкознание
• История и исторические личности
• Коммуникации связь цифровые приборы и радиоэлектроника
• Краеведение и этнография
• Кулинария и продукты питания
• Маркетинг реклама и торговля
• Мировая экономика МЭО
• Не Российское законодательство
• Немецкий
• Неопределено
• Нотариат
• Общениеэтика семья брак
• Основы права
• Охрана окружающей среды экология
• Философия
• Финансовое право
• Финансовый менеджмент финансовая математика
• Финансы деньги кредит
• Французский
• Хозяйственное право
• Цифровые устройства
• Этика эстетика
• Блог
• Карта сайта

Сетевое моделирование при планировании. Задача о коммивояжере...
	1	0	0	0	1	=
Фц.	8	8	6	4	6	12	10	12	18	8	10	4	min

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

Решение

x3 = 1

x5 = 1

x7 = 1

x8 = 0

x11 = 1

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

Задание №3

Тема: Графы

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

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

aисток                                                                                                                                              aсток

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

S12 = 4

S13 = 7

S14 = 8

S23 = 3

S25 = 5

S34 = 8

S35 = 9

S45 = 9

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

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

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

х9 - х1 – х2 – х3 = 0 (1)

х1 – х4 – х5 = 0 (2)

х2 + х4 – х6 – х7 = 0 (3)

х3 + х6 – х8 = 0 (4)

х5 + х7 + х8 – х9 = 0 (5)

х1 £ 4 (6)

х2 £ 7 (7)

х3 £ 8 (8)

х4 £ 3 (9)

х5 £ 5 (10)

х6 £ 8 (11)

х7 £ 9 (12)

х8 £ 9 (13)

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

Таблица 3.1

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

№

х1

х2

х3

х4

х5

х6

х7

х8

х9

Знак

Св.чл.

1

-1

-1

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23