Лабораторная работа № 4

Вариант №9

Студента ИТ 14-1 Красовского Абхая

Транспортные сети

Цель работы – Построение максимального потока в транспортной сети. Упрощение (оптимизация) транспортной сети

Задание

t = ] N/ 10[ = [ 9 / 10 ] = 9.

Решение

Определение максимального потока в сети:

1. Установим нулевой поток в каждой дуге сети.

2.Построим первую прибавляющую цепь(цепь, в которой все прямые дуги имеют поток, меньший за ее пропускную способность, а у обратных дуг поток больше нуля)

Прибавим ко всем потокам дуг 8(минимальная пропускная способность дуг), т.к. все дуги прямые(направлены в сторону t и их поток меньше проп. способн.)

S 12(0) a 8(0) d 13(0) m 16(0) t

12(8) 8(8) 13(8) 16(8)

Дуга ad – насыщенная(т.к. ее поток равен пропускной способности ), значит, удаляем ее из этой цепи.

3.Построим вторую прибавляющую цепь

Прибавим ко всем потокам дуг 4, т.к. все дуги прямые.

S 12(8) a 4(0) b 6(0) d 13(8) m 16(8) t

12(12) 4(4) 6(4) 13(12) 16(12)

Дуга Sa и ab – насыщенные, значит, удаляем их из этой цепи.

4.Построим третью прибавляющую цепь

Прибавим ко всем потокам дуг 1, т.к. все дуги прямые.

S 14(0) b 6(4) d 13(12) m 16(12) t

14(1) 6(5) 13(13) 16(13)

Дуга dm – насыщенная, значит, удаляем ее из этой цепи.

5.Построим четвертую прибавляющую цепь

Прибавим ко всем потокам дуг 1, т.к. все дуги прямые.

S 14(1) b 6(5) d 9(0) f 6(0) m 16(13) t

14(2) 6(6) 9(1) 6(1) 16(14)

Дуга bd – насыщенная, значит, удаляем ее из этой цепи.

6.Построим пятую прибавляющую цепь

Прибавим ко всем потокам дуг 2, т.к. все дуги прямые.

S 14(2) b 17(0) f 6(1) m 16(14) t

14(4) 17(2) 6(3) 16(16)

Дуга mt – насыщенная, значит, удаляем ее из этой цепи.

7.Построим шестую прибавляющую цепь

Прибавим ко всем потокам дуг 8, т.к. все дуги прямые.

S 14(4) b 17(2) f 8(0) t

14(12) 17(10) 8(8)

Дуга ft – насыщенная, значит, удаляем ее из этой цепи.

Больше представляющих цепей построить нельзя

8. Определим максимальный поток транспортной сети

Для этого проведем разрез и посчитаем его пропускную способность.

= 10 + 1 - 3 + 16 = 24

Проверим полученный результат, проведя и вычислив проп. способн. других разрезов

B

C(A-A) = 16 + 8 = 24

C(B-B) = 13 + 1 + 10 = 24

C(C-C) = 12 - 4 + 6 + 10 = 24

С(D-D) = 12 + 12 = 24

C(E-E) = 8 + 6 + 10 = 24

…

Модернизация сети

Найдем прибавляющие цепи, в которых есть только одна насыщенная дуга

S 14(12) b 17(10) f 8(8) t

S 14(12) b 17(10) f 6(3) m 16(16) t

---

Смотрите также файлы

• Lab5.docx

• Lab6.docx

• Lab1.docx

• Lab2.docx

• Lab3.docx