73180

Оптимізація на мережах

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

Информатика, кибернетика и программирование

Потоком у мережі S називається пара (f, w), де w - деяка орієнтація всіх неорієнтованих ребер мережі, а f(u) - задана на множині всіх ребер функція з невід’ємними значеннями, що не перевершують пропускних спроможностей, і така, що в кожній внутрішній вершині виконується закон Кірхгофа...

Украинкский

2014-12-05

454.8 KB

1 чел.

МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ
ТА СПОРТУ УКРАЇНИ

ДЕРЖАВНИЙ ВЫЩИЙ НАВЧАЛЬНИЙ ЗАКЛАД
“НАЦІОНАЛЬНИЙ ГІРНИЧИЙ УНІВЕРСИТЕТ”


Кафедра: програмного забезпечення

комп’ютерних систем


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

        по курсу дискретної математики
на тему: “Оптимізація на мережах


Виконав: студент 1-шого

курсу факультету ФІТ

групи КНіт-14-2
Задорожній О.А.

Перевірив: Мінеев О. С.




Дніпропетровськ

2014 р.

Варіант 6

Мета роботи: ознайомлення з методами оптимізації мереж.

1. Короткі теоретичні відомості.

1.  Короткі  теоретичні відомості

Пошук максимального потоку.

Нехай S є довільна, частково орієнтована мережа, кожному ребру u якої приписане невід'ємне число c(u) - пропускна спроможність. Потоком у мережі S  називається пара (f, w), де w - деяка орієнтація всіх неорієнтованих ребер мережі, а f(u) - задана на множині всіх ребер функція з невід'ємними значеннями, що не перевершують пропускних спроможностей, і така, що в кожній внутрішній вершині  виконується закон Кірхгофа, відповідно до якого сума значень потоку по ребрах, що входить у вершину, дорівнює сумі потоків по ребрах, що виходить із вершини. Іншими словами, для  f(u) виконуються умови:

0   f(u)  c(u) для усіх вершин мережі;

R() = 0 для усіх внутрішніх вершин, де

а () (відповідно '()) - множина всіх ребер, що виходять із   (відповідно вхідних у ) при орієнтації w.

Оскільки сума значень R() по усіх вершинах мережі, включаючи полюси, дорівнює нулю (кожне ребро є вихідним для однієї вершини і вхідним для іншої), то R(s)  = - R(s). Значення R = R(s) називається величиною потоку.  

 Розглянемо задачу визначення максимального значення Rmax потоку через мережу S при  заданих значеннях пропускних спроможностей. Відповідь може бути отримана у термінах перетинів мережі.

 Перетином мережі називається множина ребер, при видаленні яких мережа стає незв'язною, причому полюса потрапляють у різні компоненти зв'язності. У мережі на рис. 1 прикладами перетинів є {d, e, f}, {b, c, e, g, h},      {d, g, h, i}.  

Перетин називається простим, якщо при видаленні будь-якого його ребра, він перестає бути перетином. Так, перетини {d, e, f} і {b, c, e, g, h} - прості, а перетин {d, g, h, i} не є таким. Очевидно, що для кожного ребра простого перетину можна зазначити ланцюг, що проходить через це ребро, але не проходить через інші ребра даного перетину.  


                             5

  7   a        d        h            2

        S  2    c        4     e    3    g         S

         3       b               4        i

       1

       f

                  Рис.1. Задача максимального потоку

Якщо у зв'язній мережі віддалиться простий перетин, то мережа розпадеться рівно на дві частини: ліву і праву, що містить S і S відповідно. Кожне ребро простого перетину зв'язує вершини з різних частин. Будемо називати ребро перетину прямим, якщо воно в мережі не орієнтоване або орієнтоване зліва праворуч, і оберненим у противному випадку. Буде орієнтоване ребро прямим або оберненим, залежить від вибору перетину. Так, у прикладі ребро е  в перетинах {d, e, f} і {b, c, e, g, h} - обернене, а в перетині {a, c, e, g, i}- пряме.

Кожному простому перетину W припишемо пропускну спроможність c(W), рівну сумі пропускних спроможностей усіх його прямих ребер. У прикладі на рис.2.12 перетин {d, e, f} має пропускну спроможність 5+1=6, а перетин {b, c, e, g, h} - 3+2+3+2=10.

Теорема про максимальну пропускну спроможність мережі сформульована Фордом і Фалкерсоном так: максимальний розмір потоку Rmax через мережу S дорівнює мінімальній пропускній спроможності cmin її простих перетинів. Ця теорема покладена в основу задачі визначення максимальної пропускної спроможності мережі.

 Розглянемо  алгоритм  Форда - Фалкерсона для розв'язання цієї задачі.

         Крок 0. Нехай джерела  позначені,  але  не  переглянуті, а всі  інші  вузли  не  позначені.

         Крок  1. Вибрати  довільний  позначений,  але  не  переглянутий  вузол  i.

         Крок  2.   Переглянути  всі  дуги  e (i, j)  із  пропускною   спроможністю      е  0, що  з'єднують  вузол  i  з  ще  не  позначеними  вузлами j. Приписати позначки вузлам  j  і відзначити  дуги  e j =  e  = (i, j). Тепер  вузол  i  позначений  та  переглянутий,  вузли  j  позначені,  але  не  переглянуті. Якщо  при  цьому  стік  виявився  позначеним, то  необхідний  ланцюг  знайдений. У противному  випадку після  перегляду  по  всіх  дугах  (i, j)  перейти  до  кроку  

Крок  3. Нехай вузол i позначений і переглянутий. Перейти до кроку 1 і повторювати кроки алгоритму доти, поки не залишиться позначених і не переглянутих вузлів. На цьому пошук максимального потоку закінчується.

Пошук найкоротшого шляху.

Якщо для мережі кожне ребро характеризується деяким числом, що є відстанню між вузлами мережі, то виникає задача визначення найкоротшої відстані між заданими вузлами, тобто початку і стоку. 

       Розглянемо  алгоритм  Дейкстри  для  визначення  найкоротшого  шляху  (ланцюга) з  початку  в  стік.

Крок 0. Вибрати як перспективну  множину  вузлів  множину  S c = S 0 і  покласти  d i = 0  для  i S 0  та  d i =   для  i  S 0 .

Крок 1. Вибрати  вузол  i   S c,  якому  відповідає  найменше  значення   di ( i  S0 ) . Знайдений  в  такий спосіб розмір  d i  відповідає  найкоротшому  шляху  з  деякого  джерела  у  вузол  i (довжиною  дуги  є  c e), а  дуга  e i ( визначена  для  усіх  вузлів  i  S c  ,  крім  джерел ) є остання  дуга  шляху . Якщо    i    -  стік ,  то  процедура  пошуку  найкоротшого  шляху  закінчується .

Крок  2. Переглянути дуги  e  = ( i , j )  і  замінити  оцінку d j на  min {d j , d i + c e}.    Якщо   d j була   дорівнена   ,  увести  вузол  j у  S c. Якщо  d j  зменшилася,  увести  позначення  e j = e = (i*,  j).

Крок  3. Видалити  i* із  S c  і  перейти  до  кроку  1 ,  якщо  множина  S c  не  порожня. На цьому пошук найкоротшого шляху закінчується.

2. Індивідуально побудована мережа з варіантом вхідних даних.

Вершина№1: початок
Вершина№2: cтік

3. Повні розрахунки на мережі з пошуку максимального потоку та

найкоротшого шляху.

3.1 Пошук максимального потоку:

fmax(1:9) = 14

p(1) = (1:2:3:9) = min {5; 3; 7} = 3;  p() = 3;

p(2) = (1:2:9) = min {2; 3} = 2;  p() = 5;

p(3) = (1:6:7:8:5:9) = min {9; 2; 4; 3; 2} = 2;  p() = 7;

p(4) = (1:6:9) = min {7; 8} = 7;  p() = 14

p(1-2) = 2 -> R

p(2-3) = R

p(5-9) = R
p(6-7) = R

p(1-6) = 7 -> R

R = ресурси вичерпані.

3.2 Пошук найкоротшого шляху

1.) d(1) = 0; d(2..9) = ;

2.)  y = (1) = 0;

d(2) = 5 (<) - min

d(6) = 9  (<)

3.) y = (2) = 5;

d(9) = 5 + 3 = 8 ✓ (<); - min  [Стік]

d(3) = 5 + 3 = 8 ✓ (<); - min 

4. Висновки з лабораторної роботи.

Таким  чином,  максимальний  потік  становить  14  одиниць. Найкоротший шлях з початку (1) у стік (9) складається з дуг (1, 2) і (2, 9) та дорівнює 14.2 одиниць.


 

А также другие работы, которые могут Вас заинтересовать

26393. Вспомогательные приспособления мышц 21 KB
  Каждая мышца упакована глубокой фасцией которая имеет футлярное строение. Она препятствует распространению инфекции экономит силу мышечного сокращения имеет собственные сосуды и нервы поэтому интегрирует функционирование костей связок и мышц. Могут находиться под кожей под мышцей под связкой под фасцией под сухожилием.
26394. Головная кишка 21 KB
  ответ и глотки. Глотка pharynx полостной орган в котором перекрещиваются дыхательный и пищеварительный пути: воздух из хоан через глотку проходит в гортань расположенную в вентральной части ее мощная мускулатура передвигает корм из глотки в пищевод расположенный над гортанью. Стенки глотки состоят из 3 слоев: а слизистая оболочка; 6 мышечный слой состоит из парных правых и левых поперечно исчерченных мышц заканчивающихся на дорсальном сухожильном шве глотки raphe pharyngis.
26395. Головной мозг (encephalon) и черепные нервы 22.5 KB
  Ромбовидный мозг представлен продолговатым отходят с 6 по 12 пары черепных нервов и задним мозгом а задний cocтоит из мозжечка и мозгового моста отходит 5 пара черепных нервов. Большой мозг представлен средним отходят 3 и 4 пары нервов промежуточным 2 пара нервов и концевым 1 пара черепных нервов В ромбовидном мозге расположен 4й мозговой желудочек в среднеммозговой водопровод в промежуточном 3й а в концевом 1й и 2й мозговые желудочки.
26396. Гортань larynx 25 KB
  Остов гортани образован 5 хрящами на которых прикрепляются мышца гортани и глотки: кольцевидный хрящ cartilagо cricoidea гиалиновый состоит из пластинки и дужки. На переднем крае пластинки заметны фасетки для сочленения с черпаловидными хрящами. Черпаловидные хрящи соединяются суставами с пластинкой кольцевидного хряща. Основание хряща соединено связкой с телом щитовидного хряща вершина отогнута вперед.
26397. Грудная клетка и полость 23.5 KB
  Мышечный аппарат грудной клетки представлен дыхательными мышцами которые образуют 2 функциональные группы: вдыхатели инспираторы и выдыхатели экспираторы. Грудная клетка замыкает грудную полость cavum thoracis при этом форма грудной клетки определяет объём грудной полости и как следствие функциональные возможности органов грудной полости прежде всего лёгких и сердца При этом важное значение имеет форма диафрагмы которая отделяет грудную и брюшную полости друг от друга и образует купол вершина которого расположена в плоскости 67...
26398. Дыхательный аппарат apparatus respiratorius 20 KB
  Состав у млекопитающих: носоглотка гортань трахея лёгкие. У птиц: носовая полость носоглотка верхняя гортань состоит из 3 хрящей отсутствуют щитовидный и надгортанник трахея длинная тесно связана с пищеводом у бифуркации трахеи нижняя певчая гортань макроскорически прозрачна несколько расширена пузыревидно является резонатором звуков лёгкие очень компактные и врастают в грудной отдел позвоночника.
26399. Закономерности строения и ветвления сосудов. Круги кровообращения 21.5 KB
  Отработанная венозная кровь собирается в посткапилляры венулы вены. Вены снабжены клапанами складками эндотелия. Все вены объединяются в 2 крупные краниальную и каудальную полые у которых отсутствуют клапаны впадают в правое предсердие.
26400. Законы биологического развития. Онтогенез и филогенез 21 KB
  Закон взаимосвязи организма и внешней среды закон целостности и неделимости организма: целостность биологических систем поддерживается в процессе развития за счёт интеграции систем закон экономии биоматериала и места основной биогенетический закон Геккель филогенез определяет онтогенез. Филогенез phylon род племя исторический путь развития вида. дифференциации: в процессе развития организма органа ткани или клетки однородные структуры разделяются на обособленные отличающиеся друг от друга части благодаря чему меняются формы...
26401. Застенные железы тонкой кишки 24 KB
  Выводной проток ductus pancreaticus открывается в 12перстную кку: лошадь: объединяется вместе с печёночным протоком в фатеров дивертикул; свинья КРС: расстояние между печёночным и панкреатическим протоками 35 см; собака: может быть несколько добавочных протоков. и вегетативное печёночное нервное сплетение и выходит общий печёночный проток и лимфатические сосуды в воротах лимфоузел. Пузырный проток соединяется с печёночным образуя желчный проток который идёт в 12перстную кишку. Отток лимфы в поясничную истерну грудной лимфатический...