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


 

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

66567. Работа с графической средой ОС UNIX и Windows 44 KB
  Цель работы – изучить архитектуру системы X Window, базовых механизмов отображения графической информации и способов управления графическими окнами в UNIX, основные компоненты оконного интерфейса в Windows.
66568. РАБОТА С ГРАФИЧЕСКОЙ СРЕДОЙ ОС UNIX И WINDOWS 118.91 KB
  Цель работы – изучить архитектуру системы X Window, базовых механизмов отображения графической информации и способов управления графическими окнами в UNIX, основные компоненты оконного интерфейса в Windows.
66569. Исследование схемы автоматического управления электроприводом в функции изменения частоты вращения 112.5 KB
  Целью работы является изучение схем управления электроприводом и исследование режимов работы экспериментальной установки Автоматизированное управление электроприводом в функции изменения частоты вращения. Схемы управления электроприводом...
66570. Построение сети типа «hot-spot» на основе шлюза DSA-3100 42 KB
  Цель работы: получить практические навыки в построение сетей типа «hot-spot». I. Конфигурирование точек доступа Настраиваем первую точку доступа DWL-2100AP публичной подсети: а) заходим на web-интерфейс первой точки доступа.
66571. ВИМІРЮВАННЯ ПОТУЖНОСТІ В ТРИФАЗНИХ КОЛАХ 1.03 MB
  Електричні схеми трифазного електричного кола при з’єднанні споживачів зіркою а трикутником б для вимірювання активної потужності фази одним ватметром Ватметром PW вимірюють активну потужність тільки в одній фазі: PФ = UФIФcos φФ де PФ UФ IФ відповідно фазні потужність...
66573. Створення завантажувальних дискет, CD/DVD-дисків, флеш-накопичувачів 112.5 KB
  Діючи в рамках закону про авторські права, корпорація MicroSoft не може включити в аварійний комплект програми сторонніх розробників. Тому, завантажувальна дискета, автоматично створюється Windows, задовольняє лише тих, хто не розбирається ні в системі команд MS-DOS...
66574. Освоєння технології структурного та модульного програмування при розробці й створенні програми мовою Турбо Паскаль при реалізації на ПЕОМ задач з використанням процедур 118 KB
  Дослідити роботу операторів процедур мови Паскаль; знати призначення, форму запису та особливості вживання процедур. Освоїти методику складання, відладки та розв’язання Паскаль-програм (ПП) з використанням процедур на ПЕОМ.
66575. Преддипломная практика на предприятии Красноярский информационно-вычислительный центр структурное подразделение Главного вычислительного центра - филиала ОАО «РЖД» 293 KB
  Проведение преддипломной практики ставит следующие цели: приобретение профессиональных навыков работы менеджера; сбор, систематизация и обработка исходных практических материалов для дипломного проекта. Для достижения целей практики ставятся следующие задачи: ознакомиться с организационной структурой предприятия...