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 одиниць.


 

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

81759. Развитие лицейской темы в лирике А.С.Пушкина. (на примере 3 – 4 стихотворений). Разбор одного стихотворения 32.7 KB
  Творческая жизнь Пушкина начинается в годы национальнопатриотического подъема вызванного войной 1812г. Другим явлением определившим духовное и нравственное развитие Пушкина было начавшееся еще в годы его пребывания в Лицее освободительное движение в среде дворянской молодежи в дальнейшем движение декабристов. Уже в Лицее Пушкин приобщается к вольнолюбивым идеям которые находили благодатную почву среди лицеистов. На развитие Пушкина большое влияние оказали произведения Радищева сочинения французских просветителей ХУШ века.
81760. Проблема добра и зла в прозе Л. Андреева ( на примере одного произведения 30.42 KB
  Образы и мотивы Нового завета проблему отношений идеала и действительности героя и толпы истинной и неистинной любви Андреев разработал и в рассказе Иуда Искариот 1907. Иуда верит Христу но сознает что он как идеал не будет понят человечеством. Предатель предстает у Андреева фигурой глубоко трагической: Иуда хочет чтобы люди уверовали в Христа но для этого толпе нужно чудо воскресение после мученической смерти. В трактовке Андреева предавая и принимая на себя навеки имя предателя Иуда спасает дело Христа.
81761. Мотив дуэли в произведениях отечественной классики 19 века 32.05 KB
  Пушкин Евгений Онегин В деревне куда едет О. Пушкин дал О. которого Пушкин таким родством снижает. Пушкин не раз подчеркивает этот мотив в истории дуэли.
81762. Вечные вопросы и их осмысление в лирике А.С.Пушкина (на примере 3 – 4 стихотворений). Разбор одного стихотворения 45.14 KB
  В петербургский период лирика Пушкина особенно вбирает в себя свободолюбивые политические идеи и настроения. Первым значительным произведением после выхода из лицея была написанная Пушкиным в самом конце 1817 г. Лирике лицейских лет Пушкин лротивопоставляет поэзию вольности и обличения порока у свободы он ищет вдохновения. Недаром Пушкин в одном из вариантов своего Памятника в конце жизни прямо указывает что вслед Радищеву восславил он свободу.
81763. Тема отцов и детей в произведениях отечественной классики 19 века 32.44 KB
  Отцов или детей обличает Т. дети не должны убивать отцов а отцы заставлять детей думать так же как они думают. потому что смешно и бессмысленно полагать что можно силой заставить молодое поколение думать так же как и поколение отцов.
81764. М.Е. Салтыков-Щедрин «Господа Головлевы» (1880) 31.48 KB
  Нет любви в доме госпожи Головлевой. В ее доме все подчинено процессу припасания. Все в доме Головлевых дышит ненавистью. Из бесконтрольной обладательницы головлевских имений Арина Петровна сделалась скромной приживалкой в доме младшего сына.
81765. Своеобразие композиции романа А.С.Пушкина «Евгений Онегин» 33.37 KB
  Чтение наизусть отрывка из романа Евгений Онегин . В годы создания романа Пушкину пришлось пережить ссылку потерять многих друзей испытать горечь от гибели лучших людей России того времени. Ее духовный и нравственный облик представлен в героях романа Евгении Онегине и Ленском.
81766. Социальная и философская проблематика пьесы М. Горького «На дне» 32.62 KB
  изображением дна являющегося изнанкой современного буржуазного строя Горький утверждал мысль о необходимости решительного обновления этого строя во имя освобождения человека. Горький поновому показал босяка дав строго реалистический анализ бродяжного люда ни разу не отрываясь от трезвого взгляда на босячество как на явление в основе своей антисоциальное. Горький усилил и художественно обобщил одну черту босяка его презрение к мещанским предрассудкам к мещанской морали к мещанскому фетишизму вещей и понятий. Горький использовал эту...
81767. Роль пейзажа в произведениях отечественной литературы 31.46 KB
  В рассказе Хорь и Калиныч Калиныча более трогали природа горы водопад. чутко воспринял тему человек и природа В рассказе того же цикла Бежин луг описание природы начинает повествование. Это рассказ о том что природа сильнее человека и поэтому надо с уважением к ней относиться. Главный герой романа Евгений Базаров так выражает свои отношения с природой: Природа пустяки Природа не храм а мастерская и человек в ней работник Но далее читаем: Солнце жгло изза тонкой завесы сплошных беловатых облаков.