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


 

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

42949. Расчет коленчатого вала двигателя ЗМЗ - 53 376.33 KB
  ПЗ РАЗРАБОТКА МАРШРУТНОГО ТЕХНОЛОГИЧЕСКОГО ПРОЦЕССА Коленчатый вал двигателя ЗМЗ 53 рисунок 1 поступающие в ремонт может иметь следующие дефекты: обломы и трещины любого характера и расположения 1 изгиб вала 2 увеличение длины передней коренной шейки 3 износ шатунных шеек по длине 4 износ шатунных 5 и коренных 6 шеек износ шпоночной канавки под шпонки шестерни 7 и ступицы шкива коленчатого вала 8 биение шейки под шестерню коленчатого вала 9 износ шейки по шестерню коленчатого вала 10 износ шейки под ступицу шкива...
42950. Исследование QR метода на основе преобразований вращения и отражения 194.67 KB
  Рассмотрим два метода исключение обладающих в отличие от метода Гаусса гарантированной хорошей обусловленностью метод вращений и метод отражений. Оба эти метода позволяют получить представление исходной матрицы в вид произведения ортогональной матрицы Q на верхнюю треугольную матрицу R: =QR. 1 Теория метода вращения Пусть дана система линейных алгебраических уравнений содержащая n уравнений с n неизвестными. Идея метода заключается в том что матрицу А приводим к верхней треугольной умножая ее на коэффициенты c и s а потом с помощью...
42952. Організації передачі повідомлень на базі нових мережевих технологій 54.45 KB
  Завантаження однієї абонентської лінії телефонною розмовою складає в середньому 002 Ерланга в годину у годину пік у 5 разів більше. Для спрощення розрахунків думаємо що динаміка росту кількості абонентів описується лінійним законом; завантаження однієї абонентської лінії телефонною розмовою складає в середньому 002 Ерланга в годину у годину пік у 5 разів більше; середній трафик мови визначаємо по формулі: Тм сер = 002 Nб Тм сер = 002 13=026 Тм сер = 002 15=030 Тм сер = 002 16=032 Тм сер = 002 17=034 Тм сер = 002...
42953. Физические основы рентгеноспектрального и рентгенофлуоресцентного методов анализа 1.05 MB
  Свойства тонкоплёночных твёрдотельных объектов (электрические, магнитные, оптические и др.) зависят от их химического состава и толщины. Поэтому определение химического состава, толщины и других физико-химических характеристик твёрдотельных плёнок и покрытий для получения материалов с уникальными физическими свойствами является важной задачей
42954. Технологический процесс на изготовление детали – ступенчатый вал 252.63 KB
  Деталь изготавливается в условиях единичного производства из стали 45 ГОСТ 1050-88 твердостью НВ 280, термообработка - нормализация. Она представляет собой 5-ти ступенчатый вал длиной 360 мм. Относится к группе цилиндрических изделий. Внутри - сплошной. Основное предназначение вала – передавать крутящий момент в редукторе тихоходной ступени.
42956. КОМПЛЕКТУВАННЯ ОПТИМАЛЬНОГО СКЛАДУ МТП БРИГАДИ С ТОВ ім. КІРОВА З РОЗРОБКОЮ ОПЕРАЦІЙНО-ТЕХНІЧНОЇ КАРТИ ПОСІВУ ЦУКРОВОГО БУРЯКА 324.5 KB
  В процесі курсового проектування студенти повинні закріпити, поглибити і узагальнити знання з загально-технічних спеціальних предметів, розвити навички самостійної роботи, навчитися використовувати отримані знання при вирішенні питань виробничо-технічного характеру.
42957. Разработка устройства защиты коллиматора для твердотельного лазера на неодимовом стекле 87.78 KB
  Проверил преподаватель Москва 2012 Цель работы: разработка устройства защиты коллиматора для твердотельного лазера на неодимовом стекле. Схема лабораторной установки 3Dмодель устройства защиты коллиматора от попадания лазерных лучей при измерении.