Таким чином, течія в проміжних вершинах нічого не лишає і приносить на вихід стільки одиниць товару (інформації), скільки вийшло з входу. Ця кількість і є величина течії.

Величина течії в одній і тій же мережі може бути різною.

Наприклад, розглянемо орієнтований граф

1) f₁₂ = 5

Таким чином, через даний граф пройшла течія, що дорівнює 5 одиниць продукту: f = 5.

2) f₁₂ = 5

f₁₄ = 2 .

Таким чином, через даний граф пройшла течія, що дорівнює f = 3 + 2 + 2 = 7 одиниць продукту.

3) f₁₃ = 3 ,

f₁₂ = 5 ,

f₁₄ = 2 .

Таким чином, через даний граф пройшла течія, що дорівнює

f = 3 + 5 + 2=10 одиниць продукту.

Задача про максимальну течію складається з того, щоб знайти течію найбільшої величини, яку можна пропустити через задану мережу.

Теорема Форда – Фалкерсона.

Для кожної мережі величина максимальної течії дорівнює пропускній спроможності мінімального розрізу.

Введемо в розгляд деякі поняття.

Дуги графа можна віднести до двох категорій:

- дуги, в яких течію можна збільшити, − це ненасичені дуги, їх об’єднаємо в множину І – множина ненасичених дуг;

- дуги, в яких течію можна зменшити, − це невільні дуги, їх об’єднаємо

в множину R – множина обернених дуг.

Дуга, в якій течія дорівнює нулю, називається вільною. В такій дузі течію зменшити не можна.

Дуга може належати і множині І, і множині R одночасно.

Введемо в розгляд величини:

1) і(х,у) =с_ху - f_xy − це максимальна величина, на яку можна збільшити течію в дузі.

На рисунку маємо ланцюг, що збільшує, він містить прямі дуги (1,2), (2,3), (3,4). Течію з вершини 1 в вершину 4 можна збільшити на min(i(1,2), i(2,3), i(3,4)) = min (3;2;1) = 1;

2) r(x,y) − максимальна величина, на яку можна зменшити течію в дузі

На рисунку маємо ланцюг, що збільшує, який містить обернені дуги. Зменшення течії з вершини 4 до вершини 1 приводить до збільшення течії з вершини 1 до вершини 4. У мережі на рисунку течія з вершини 4 у вершину 1 може бути зменшена на min(r (2,1), r (3,2), r (4,3)) = min (1;2;1) = 1, і тим самим течію з вершини 1 у вершину 4 збільшимо на 1.

Сформулюємо алгоритм пошуку ланцюга, що збільшує.

Крок І Визначимо склад множин І і R. Зафарбуємо початкову вершину.

Крок ІІ Будемо зафарбовувати дуги і вершини відповідно до наведених нижче правил доти, поки або не буде зафарбована кінцева вершина, або

фарбування нових вершин стане неможливим.

Правило фарбування.

Якщо вершина х зафарбована, тоді фарбування вершини у і дуги (х,у) відбувається таким чином:

а) якщо дуга (х,у) І, то зафарбовується вершина у і дуга (х,у)

(х,у)

І;

б) якщо дуга (у,х) R, тоді зафарбовується вершина у і дуга (у,х)

в) інших випадках вершина у і дуга (х,у) не фарбуються.

Можна довести, що, якщо кінцева вершина зафарбована, тоді в мережі знаходиться єдиний ланцюг з початкової вершини у кінцеву, який включає зафарбовані дуги (це ланцюг, що збільшує). Якщо кінцева вершина не зафарбована, тоді в мережі відсутні ланцюги з початкової до кінцевої вершини, що збільшують.

Зауваження.

Дуга фарбується лише тоді, коли одна з її вершин зафарбована, а інша ні. Отже не може бути зафарбована дуга, обидві вершини якої були раніше зафарбовані. Тому зафарбовані дуги не можуть утворювати цикл. Зафарбовані дуги утворюють дерево. Якщо зафарбовується кінцева вершина, то існує ланцюг з початкової вершини в кінцеву. Це і буде ланцюг, що збільшує, оскільки процедура фарбування гарантує, що прямі дуги цього ланцюга збільшують, а обернені – зменшують течію в мережі.

Далі розглянемо алгоритм пошуку максимальної течії у графі.

Ідея, що лежить в основі цього алгоритму Форда – Фалкерсона така: беремо деяку початкову течію з початкової в кінцеву вершину і за допомогою алгоритму пошуку ланцюга, що збільшує, виконуємо пошук такого ланцюга. Якщо він виявляється успішним, то течія вздовж знайденого ланцюга збільшується до максимально можливого значення. Потім знаходять новий ланцюг, що збільшує. Якщо на якомусь етапі цієї процедури ланцюг, що збільшує, знайти не вдається, виконання алгоритму закінчується, тобто знайдена течія з початкової до кінцевої вершини є максимальною.

Крок І Беремо будь-яку початкову течію з початкової до кінцевої вершини, наприклад, нульову.

Крок ІІ Сформуємо множини дуг І і R. На цих множинах застосуємо алгоритм пошуку ланцюга, що збільшує.

Якщо ланцюг, що збільшує, знайти не вдається, закінчуємо процедуру алгоритму. У протилежному випадку здійснюємо максимально можливе збільшення течії вздовж цього ланцюга і повертаємось до кроку ІІ.

Приклад.Знайти максимальну течіюу графі при даних пропускних спроможностях дуг в мережі.

1Пропустимо через всі дуги мережі нульову течію.

2Всі дуги мережі відносяться до множини І. Розглянемо ланцюг, що збільшує

(1,2), (2,3), (3,5)

і(1,2) = 2 – 0 = 2 і(2,3) = 3 – 0 = 3 і(3,5) = 2 - 0 =2.

Через цей ланцюг можна пропустити течію, що дорівнює min( 2;3;2) = 2.

Течія в дугах даного ланцюга збільшується на дві одиниці.

Повертаємось до кроку ІІ.

3Знову шукаємо ланцюг, що збільшує. Зауважимо, що дуги (1,2) і (3,5) належать до множини R. Розглянемо ланцюг

(1,3), (2,3), (2,4), (4,5)

І R І І

і(1,3) = 3 – 0 = 3 r(2,3) = 2 і(2,4) = 4 - 0 = 4 і(4,5) = 1 - 0 = 1.

Тепер течія через мережу буде дорівнювати 2 + 1 = 3.

Це максимальна течія, тому що ланцюг, що збільшує, побудувати вже не можна, бо у кінцеву вершину ведуть дуги, що належать до множини R, у яких течію можна лише зменшувати.

Далі розглянемо метод знаходження максимальної течії в неорієнтованому графі.

Маємо неорієнтований граф.

1 По Av₁v₂B можна пропустити течію, що дорівнює min(5,2,6) = 2. Ребро з мінімальною спроможністю (v₁,v₂) вилучається, із решти пропускних спроможностей віднімаємо число 2.

2 По Av₃v₄B можна пропустити течію, що дорівнює min(2,3,2) = 2. Повторюємо процедуру пункту 1.

3 По Av₄v₂B можна пропустити течію, що дорівнює min(3,4,4) = 3. Тоді одержуємо:

Шляхів із А в В немає. Течія із А в В дорівнює 2 + 2 + 3 = 7.

Питання для самоперевірки

1 Сформулюйте означення графа.

2 Сформулюйте означення орієнтованого та неорієнтованого графа.

3 Сформулюйте означення маршруту у графі.

4 Сформулюйте означення ланцюга, ланцюга простого, цикла, простого цикла, шляха, контура у графі.

5 Який граф називається ейлеровим, гамільтоновим?

6 Що таке матриця суміжності вершин графа?

7 Що таке матриця суміжності ребер (дуг графа)?

8 Що таке матриця інцидентності графа?

9 Дайте означення остовного дерева графа.

10 Як підрахувати число остовних дерев графа?

11 Сформулюйте алгоритм побудови остовного дерева графа, остовного дерева максимальної та мінімальної довжини.

12 Сформулюйте алгоритм Дейкстри побудови найкоротшого шляху в графі.

13 Сформулюйте метод поміток побудови найкоротшого та найдовшого шляху в графі.

14 Дайте означення мережевого графа.

15 Сформулюйте правила, яких необхідно дотримуватись при побудові мережевого графа.

16 Як на мережевому графі відображаються роботи (операції проекта)?

17 Що таке найбільш ранній і найбільш пізній термін настання події?

18 Як їх обчислити?

19 Що таке повний, вільний та незалежний резерв часу операції? Чи є зв’язок між ними?

20 Що таке критична операція?

21 Що таке критичний шлях у мережевому графі?

22 Дайте означення розбивальної множини графа та розрізу графа.

23 Що таке пропускна спроможність розрізу? Що таке мінімальний розріз?

24 Дайте означення течії по дузі.

25 Яка дуга називається насиченою, ненасиченою, вільною?

26 Сформулюйте задачу про максимальну течію в графі.

27 Сформулюйте теорему Форда-Фалкерсона.

28 Сформулюйте алгоритм пошуку ланцюга, що збільшує.

29 Сформулюйте алгоритм пошуку максимальної течії у графі.

Задачі для самостійної роботи

1 Маємо граф

Побудувати матриці суміжності вершин графа, дуг графа і матрицю інцидентності орграфа.

2Маємо граф

Побудувати матриці суміжності вершин і ребер не орграфа.

3За матрицею інцидентності відновити граф.

4Маємо граф

Для цього графа:

а) обчислити кількість остовних дерев графа;

б) побудувати остовне дерево графа, мінімальне остовне дерево і максимальне остовне дерево;

5Маємо граф

Для цього графа обчислити:

а) найкоротший шлях методом Дейкстри;

б) найкоротший та найдовший шлях методом поміток;

в) максимальну течію в графі.

6Маємо проект будівництва спортивної споруди (за нижеподаною таблицею).

Етап	Робота, що виконується	Попередній етап	Потрібний час (тиж)
А	Підготовка будмайданчика	-
Б	Побудова фундаменту	А
В	Підводка магістральних ліній електро- і водопостачання	А
Г	Монтаж вертикальних стін	Б
Д	Монтаж стріха	Г
Е	Укладання дерев’яних перекриттів	Г
Ж	Установка дверей та вікон	Г
З*	Монтаж електрообладнання	Д
І	Монтаж системи опалення	В, Г
К	Установка сантехніки	В, Г
Л	Оздоблювальні роботи	З*, І, К

За даними проекту побудувати мережевий граф, для кожної роботи (операції) розрахувати повний вільний та незалежний резерви часу, побудувати критичний шлях у графі.

Глава 3 МЕТОД ГІЛОК ТА МЕЖ

Основні поняття

Цей метод буде застосовано для розв’язання задачі про рюкзак та задачі комівояжера.

Сформулюємо основні ідеї метода гілок та меж.

Деяка функція має бути мінімізована f(x)→min, де Х складається з дискретних точок (наприклад, цілочисельних). Це задача нелінійного програмування, навіть якщо f(x) – лінійна функція.

Якщо множина Х складається з невеликої кількості елементів, то можливий перебір всіх елементів, якщо кількість елементів множини Х є великою, то потрібен метод спрямованого перебору. Одним з таких методів є метод гілок та меж . В цьому методі треба вказати дві речі:

1)алгоритм розбиття множини Х;

2)деяку систему оцінок будь-якої підмножини Х.

Множину Х розбиваємо на дві – три частини

Х_11,Х_12, Х₁₃– кінцеві множини 1-го кроку.

На другому кроці за деякою ознакою вибираємо одну з множин 1-го кроку і розбиваємо її. Одержані множини разом з нерОзгалуженими множинами другого кроку називаються кінцевими множинами другого кроку.

Для системи оцінок множин запроваджується функція ρ(Х^*), Ця функція повинна задовольняти наступним вимогам:

1)оцінка будь-якої підмножини ρ(Х^*) при розбиті повинна бути меншою, ніж min f(x), ;

2)оцінка будь-якої підмножини повинна бути меншою за оцінку тієї множини, з якої ця підмножина одержана, тобто ρ(Х^*) ≥ ρ(Х), ;

з цього випливає, що при розбитті оцінка ρ(Х) не може спадати;

3)оцінка множини, що складається з однієї точки, дорівнює значенню цільової функції f(x) в цій точці.

Ми розглянемо реалізацію метода гілок та меж, яка називається повне галуження.

Для цього на першому кроці обчисляємо оцінку множини Х − ρ(Х) за означеним правилом. Після цього обчислюється оцінка ρ для підмножин Х₁₁, Х₁₂. Зі знайдених оцінок ρ(Х₁₁), ρ(Х₁₂) обирається найменша, і далі галузиться та множина, для якої оцінка ρ найменша. Після цього процедура повторюється.

Далі галузимо ρ(Х₁₂):

З трьох множин Х_11,Х_21, Х₂₂вибираємо ту, для якої оцінка є найменшою. Галузимо доти, поки не доберемося до множини, що складається з однієї

точки, оцінок кінцевих множин останнього кроку.

Задача про рюкзак

Є n предметів. Відомі вага p кожного i вартість c , i = .Потрібно покласти у рюкзак сукупність предметів з мінімальноюсумарною вагою за умови, що вартість вантажу не менша за С. Введемо в розгляд змінну :

Тоді одержуємо задачу:

Це повна постановка задачі про рюкзак. Опишемо алгоритм галуження i зв'язану з ним систему оцінок. Для того, щоб обчислити оцінку ρ(х), треба розв’язати задачу лінійного програмування (неперервну), тобто розв’язуємо свою задачу, але умову замінимо на 0 ≤ х_і≤ 1. Таким чином

ρ(х) =min f(x) за умови 0 ≤ х_і≤ 1. За умови 0 ≤ х_і≤ 1 min f(x) може тільки зменшитися, тобто ρ(x) ≤ minf (x), і вимога на ρ(х) виконана.

Складаємо відношення – це відносна вага предмета на одиницю вартості. В першу чергу будемо класти в рюкзак ті предмети, що мають min . Умова 0 ≤ х_і≤ 1 означає, що маємо право дробити предмети. При цьому множина припустимих значень збільшується, a min функції може лише зменшуватися.

Приклад. Маємо п’ять предметів, які треба покласти в рюкзак за умови, що вартість предметів у рюкзаку

С=30

с_і

вартість

р_і

Вага

Математична модельзадачі така: ми шукаємо min ваги

f(x) = 6х₁ + 2х₂+ 5x₃+ 8х₄+4х₅→ min

за умови, що вартість вантажу

10х₁+ 5x₂+ l 6x₃ + 4x₄ + 6x₅≥ 30. (1)

Коли задача буде розв'язана, ми одержимо такий граф-дерево:

Зробимо оцінку планів задачі (1), тобто будуємо оцінку ρ.

(2)

Це задача (2) лінійного програмування. Розв'яжемо її.

Розташовуємо предмети в порядку зростання i відповідно перенумеруємо предмети.

і
поперед. ном.
с_і
р_і

Задача (2) тоді має вигляд (з новою нумерацією предметів):

Якщо візьмемо перший предмет, тоді його вартість 16<30; якщо перший і другий, то їх вартість 16+5=21<30. Якщо візьмемо перший, другий і третій предмети, то їх вартість буде 16 + 5 + 10=31, 31 > 30 на одиницю. Яку частину третього предмета треба взяти? Одиниця – це вартості третього предмета, тобто треба взяти предмета. Тоді опорний план задачі (2): (1; 1; 0,9; 0; 0); ρ(х) = 5 + 2 + б*0,9 = 12,4.

Будемо галузити множину опорних планів по третій координаті, оскільки вона не ціла. Розбиваємо множину Х, тобто сукупність планів задачі (2),на дві підмножини.

З’являються задачі (3) і (4):

(3)

(4)

Для задачі (3) третього предмета немає.

1пр. + 2пр. + 4пр. 16 + 5 + 6 = 27 < 30,

1пр. + 2пр. + 4пр.+ 5пр. 16 + 5 + 6 + 4 = 31 > 30.

П’ятий предмет перевищує вартість на одиницю, тобто на 1/4 його вартості, тоді потрібно взяти 3/4 п’ятого предмета. Опорний план для задачі (3) наступний: (1; 1; 0; 1; 3/4),

ρ(х₁₁) = 5 + 2 + 4 + 8*(3/4) = 17.

Розв’язуємо задачу (4):

1 пр. + 2 пр. 16 + 5 = 21>20.

Вже другий предмет перевищує вартість на одиницю, тобто на 1/5 його вартості; треба взяти 4/5 другого предмета. Опорний план (1;4/5, 1; 0; 0),

ρ(х₁₂)= 5 + 2*(4/5)+6+0=12,6.

Із ρ(х₁₁) i ρ(х₁₂) вибираємо min, це ρ(х₁₂),і далі галузимо х₁₂ за другою координатою:

З'являються задачі (5) i (6):

(5)

(6)

Розв’язуємо задачу (5).

1 пр.+ 4 пр. 16 + 6 = 22 > 20. Четвертий предмет перевищує вартість на 2 одиниці або на його вартості, тобто потрібно взяти четвертого предмету. Опорний план такий: (1; 0; 1; ;0),

ρ (х₂₁) = 5+6+4* =13 .

Розв’язуємо задачу (6).

1 пр. 16 > 15. Перший предмет перевищує вартість на 1 одиницю, тобто на своєї вартості треба взяти від першого предмету. Опорний план (6) задачі ( ; 1; 1; 0: 0), ρ(х_2,2) =5* + 2 + 6 = 8 + = 12 .

Кінцеві множини цього кроку X₁₁, Х₂₁, Х₂₂

min ρ = ρ(X₂₂) = l2 .

Далі треба галузити Х₂₂ за першою координатою:

Задачі (7) i (8):

(7)

(8)

Розв’яжемо задачу (7).

4пр.+5 пр. с=10<15 множина планів порожня. Тоді відповідну оцінку вважаємо рівною ∞, тобто ρ(X₃₁) = ∞. Така множина галуженню не підлягає.

Розв’язуємо задачу (8). Розв'язок цієї задачі (1;1; 1; 0; 0), ρ(X₃₂) = 13.

Кінцеві множини третього кроку Х₁₁, X₂₁, X₃₁, X₃₂; min ρ = ρ(X_3,2) = l3.

План задачі (8) цілочисельний, тому множина Х_3,2 розбивається таким чином: одноелементна підмножина Х_4,1= {1,1,1,0,0} – одна точка, i X_4,2=X_3,2\X_4,1. Вважаємо при цьому ρ(Х_4,1) = ρ(Х_4,2) =ρ(Х_3,2) =13. Елемент Х_4,1 є розв'язком задачі.

Оптимальне значення цільової функції 13. Якщо перейти до старої

нумерації, тоді в рюкзак треба покласти 3,2 і 1 предмети.

Задача комівояжера

Далі розглянемо іншу задачу, яку можна розв’язати за допомогою методугілок та меж.

Постановка задачі. Маємо n міст, комівояжер повинен відвідати кожне з міст тільки один раз і повернутися в перше. Його маршрут повинен мінімізувати сумарну довжину ( або вартість) пройденого шляху. В теорії графів такий шлях називається гамільтоновим контуром. Тобто задача комівояжера – це знаходження гамільтонового контуру мінімальної довжини.

Мінімізується функція де Х – множина всіх припустимих маршрутів, тобто гамільтонових контурів, c_ij – вага дуги (i,j) (довжина або вартість шляху). Будемо вважати крім того, що c_i_i= ∞,

c_i_j= ∞, якщо немає шляху з пункту і в пункт j.

Сформулюємо загальну схему розв’язання задачі.

Маємо матрицю С = (c_ij), де c_ij – вага дуги( i,j). Віднімаємо з усіх елементів кожного рядка матриці С мінімальний елемент цього рядка, далі в матриці, що одержана, від усіх елементів кожного стовпця віднімаємо мінімальний елемент цього стовпця. Матриця, що виникає, називається зведеною, позначимо її , крім того позначимо через – мінімум в рядку і; – мінімум у стовпці j; – назвемо константами зведення, i,j=1,2,…,n.

Для будь-якого гамільтонового контуру виконується наступне:

У якості ρ(х) вибираємо , і тоді виконуються вимоги, які накладаються на оцінку ρ(х), ρ(х) ≤ f(x).

Після операції зведення довжина всіх гамільтонових шляхів зменшуються на одну й ту ж величину, тому оптимальний гамільтонів контур, знайдений з використанням зведеної матриці, буде оптимальним і для початкової матриці.

Множину X ми повинні галузити. Множина Х₁₁складається з уcіx гамільтонових контурів із X, що не містять деякої дуги (r,s). Множила Х₁₂ складається з ycix гамільтонових контурів з X, що містять дугу (r,s).

Правило вибору дуги (r,s) полягає в наступному: оцінку ρ(Х₁₂) прагнуть зробити меншою, оцінку ρ(Х₁₁) – більшою з метою збільшити ймовірність подальшого галуження множини Х₁₂. Бажання зменшити оцінку ρ(Х₁₂) означає, що кандидатами на вибір дуги (r,s) можуть бути лише ті дуги, яким у зведеній матриці відповідають нульові елементи. Їх може бути декілька. Тоді знайдемо суму констант зведення кожного з нульових елементів матриці . Позначимо цю суму для елемента (i,j) через Θ(і, j). Як дугу (r,s) вибираємо таку, для якої оцінка знизу максимальна, тобто Θ(r,s) =max Θ (i,j).

Наступний етап – побудова зведених матриць i обчислення оцінок знизу.

Замінимо в матриці нульовий елемент, що відповіднє дузі (г,s), на ∞. Нову матрицю позначимо С₁. Зведена матриця відстаней для гамільтонових контурів із Х₁₁, що не містять дуги (r,s), одержується зведенням матриці C₁. Сума констант зведення для матриці С₁ дорівнює Θ(r,s).

Оцінка знизу для функції f(x) на множині Х₁₁ така: ρ(Х₁₁) = ρ(Х) + Θ(r,s).

Гамільтонові контури з Х₁₂ містять дугу (r,s). Викреслимо в матриці рядок i стовпець, що відповідають дузі (рядок відповідає місту r і стовпець відповідає місту s), Елемент, що відповідає дузі (s,r), замінюємо на ∞ (назад із s в r їхати не можна).

Отриману матрицю позначимо С₂ (її розмір менше, ніж у попередньої). Зведена матриця відстаней для контурів з X₁₂ одержується зведенням матриці С₂. При цьому оцінка знизу ρ(Х₁₂) = ρ(Х) + τ(r,s), де τ(r,s) – сума констант зведення матриці С₂.

Якщо в кожному рядку і стовпцю матриці С₁ або С₂ виявилося лише по одному елементу, відмінному від ∞, тоді множина X₁₁(або Х₁₂) містить єдиний маршрут, довжина якого дорівнює ρ(Х₁₁) (або ρ(Х₁₂)).

Приклад. ( Задача комівояжера).

Є 5 міст. Дана матриця відстаней (вартості):