73180

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

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

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

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

Украинкский

2014-12-05

454.8 KB

0 чел.

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

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


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

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


Лабораторна робота №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 одиниць.


 

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

26859. Анатомический состав и морфофункциональная хар-ка органов размножения самцов и самок 2.9 KB
  В целом морфология органов половой системы самца и самки паренхиматозного и трубчатого строения обеспечивает два вида процессов: 1 трофику развитие гонады и плода и 2 проведение половых клеток введение половых органов самца в половые пути самки и выведение по ним развившегося плода.Половой аппарат самца и самки имеет общие принципы строения и состоит из нескольких отделов: а половые железы парные: у самцов семенники у самок яичники вырабатывающие половые клеткиб половые протоки про водящие половые клетки семяпроводы у...
26860. Семенниковый мешок 1.88 KB
  Состоит семенниковый мешок из мошонки и влагалищных оболочек. Кожа мошонки cutis scroti покрыта мелкими волосами содержит потовые и сальные железы. По средней сагитталь'ной линии на ней выделяется шов мошонки. Она очень прочно сращена с кожей мошонки образуя одну оболочку.
26861. Семенники и придатки 4.39 KB
  Семенник подвешен на семенном канатике в семенниковом мешке; по форме он напоминает эллипсоид; с ним тесно связан придаток семенника . Головчатый конец extremitas capitata характеризуется наличием на нем головки придатка семенника которая бывает то плоская то толстая почти такая же как и хвост придатка . На придаточном крае семенника margo epididymidis прикрепляется брыжейка семенника и располагается тело придатка. Край семенника противоположный придатковому называется свободным краем .
26862. Семенной канатик и семяпровод 3.07 KB
  Семенной канатик и семяпровод. Семяпровод ductus deferens представляет собой семя проводящую трубку из слизистой мышечной и серозной оболочек; он служит продолжением канала придатка и выходит из его хвоста В составе семенного канатика с его медиальной стороны семяпровод направляется через. паховый канал в брюшную полость и затем идет в семяпроводной складке plica ductus deferentis в тазовую полость. Позади шейки последнего семяпровод соединяется с выводным протоком пузырьковидной железы в семяизвергающий проток ductus...
26863. Мочеполовой канал и придаточные половые железы 4.84 KB
  Мочеполовой канал начинается внутренним отверстием уретры ostium urethrae internum : из шейки мочевого пузыря и оканчивается наружным отверстием уретры ostium urethrae externum на головке полоеого члена. Губчатая часть pars spongiosa начинается от перешейка уретры и заканчивается на переднем конце головки полового члена образуя здесь отросток уретры processus urethrae. Кавернозный слой мужской уретры stratum cavernosum в своей основе имеет соединительнотканный остов. bulbourethral парная; размещается в каудальной части...
26864. Половой член и препуций 3.74 KB
  Половой член penis состоит из пещеристого тела полового члена и удовой части мочеполового канала. Пещеристое тело полового члена corpus cavernosum penis в области седалищной дуги прикрепляется к седалищным костям двумя ножками crus penis. Ножки формируют непарное тело corpus penis. Корень полового члена radix penis образован ножками кавернозного тела и началом удовой части мужской уретры.
26865. Яичники и яйцеводы домашних животных 3.89 KB
  Передний конец яйцепровода формирует воронкообразное расширение. В глубине воронки находится брюшное отверстие яйцепровода ostium abdominale tubae uterinae. Брюшное отверстие ведет в краниальную часть яйцепровода ампулу ampulla tubae uterinae.
26866. Матка домашних животных 3.21 KB
  Рога и тело матки содержат полость матки cavum uteri которая переходит в канал шейки. Рога матки истончаясь продолжаются краниально и без видимой границы переходят в яйцепроводы. Шейка матки открывается во влагалище. Слизистая оболочка матки endometrium выстлана цилиндрическим эпителием.
26867. Характеристика органов кроветворения и иммуногенеза 5.01 KB
  кроветворения относят красный костный мозг селезёнку и лимф. К органам кроветворения и иммуногенеза относят: красный костный мозг тимус лимфатические узлы селезенку миндалины а также лимфоидные образования слизистой оболочки пищеварительной половой дыхательной и выделительной систем. Центральные органы включают в себя красный костный мозг и тимус . Костный мозг.