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


 

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

54953. Становление парламентаризма в России 58.5 KB
  Оборудование: Оформление помещения для проведения Парламентского урока государственными символами Российской Федерации Технические средства: мультимедиа-проектор. Мы живём с вами в одной из прекраснейших республик...
54954. Строчная буква в. Написание строчной буквы в 1.9 MB
  Задачи: Закреплять графические навыки письма изученных букв и гигиенические навыки при письме; Развивать внимание, речевые умения, умение анализировать и обобщать; Воспитывать чувство взаимопомощи, умение радоваться не только за себя, но и за своих товарищей.
54955. Описание действий (развитие речи) 30.5 KB
  Сегодня мы с вами познакомимся с новым видом сочинения-описания действий. Слов какой части речи больше в тексте описания действий глаголов. В каких случаях мы с вами чаще всего сталкиваемся с описанием действий рецепты инструкции по применению разных товаров.
54956. Инфляция: сущность, причины, виды. Методы измерения инфляции 20.97 KB
  Инфляция представляет собой увеличение денежной массы по сравнению с ее товарным покрытием и проявляется в обесценивании денег и росте общего уровня цен.
54957. Гуситское движение в Чехии 62.5 KB
  Вооруженная борьба гуситов. Крестовые походы против гуситов. Вооружение и способы борьбы гуситов. Вооруженная борьба гуситов.
54958. Причины и социально-экономические последствия инфляции. Антиинфляционная политика государства 18.02 KB
  Как свидетельствует опыт, остановить инфляцию с помощью одних организационных мер весьма трудно, если не сказать невозможно. Для этого необходима структурная реформа, направленная на преодоление возникших в экономике диспропорций.
54959. Пусть всегда будет солнце 62.5 KB
  Вид урока Комбинированный Тип урока Комплексный урок Государственный социальный заказ Во исполнение Закона Российской Федерации Об образовании; Закона О развитии образования в городе Москве; Конвенции о правах ребенка;...
54960. ВЫРЕЗАНИЕ ИЗ БУМАГИ 69 KB
  Цели: Обучающая: Способствовать формированию представления о таком виде декоративно прикладного искусства как вырезание из бумаги. Слайды 18 Сейчас вы можете назвать мне тему нашего урока ответы детей Правильно вырезание из бумаги слайд 9 Но давайте нашему уроку придумаем красивое название...
54961. Материки и океаны 65.5 KB
  План урока Этапы урока Задачи этапов Деятельность учителя Деятельность учащихся Методы и приемы Формы работы Средства обучения Самоопределение в деятельности Настрой учащихся на работу активизация познавательных мотивов учащихся создание психологического комфорта в классе...