Нехай заданий орієнтований граф G= , в якому напрямок кожної дуги vÎVозначає напрямок руху потоку (наприклад потік автомобілів), пропускна здатність кожної дуги дорівнює d(v).На безлічі вершин Eвиділено дві вершини tі s. Вершина tє джерелом потоку, s- Стоком. Потрібно визначити максимальний потік, який може бути пропущений з вершини tв s .

Позначимо через x(v)величину потоку, що рухається дугою v. Очевидно, що

0£ x(v) £ d(v) , vÎV . (6. 1)

У кожній вершині iÎE(t,s)обсяг потоку вхідного дорівнює обсягу потоку, що виходить, тобто. справедлива рівність

(x(v)| i V + (i)) = (x (v) | i V - (i))

(x(v)|iÎV + (i)) - (x(v)|iÎV - (i))=0.(6.2)

Для вершини t

(x(v)|iÎV + (i)) -(x(v)|iÎV - (i))=-Q,(6.3)

для вершини s

(x(v)|i V + (i)) -(x(v)| i Î V - (i)) = Q.(6.4)

Величина Qє величиною потоку, що виходить із вершини tі входить у вершину s.

Потрібно визначити

Q ® max(6.5)

за обмежень (6.1-6.4).

Величини Q, x(v) , vÎV,що задовольняють обмеженням (6.1-6.4) називатимемо потоком у мережі, і якщо вони максимізують величину Q, то максимальним потоком. Неважко бачити, що значення Q=0, x(v)=0, vVє потоком в мережі.

Завдання (6.1-6.5) є завданням лінійного програмування і його можна вирішити алгоритмами симплекс-метода.

Розіб'ємо безліч вершини Е на дві частини, що не перетинаються, Е1 і Е2 таким чином, щоб tÎE1, sÎE2. Розрізом V(E1,E2), що розділяє tі sбудемо називати безліч V(E1,E2)ÌVтаке, що для кожної дуги v V (E1, E2)або h1(v)ÎE1і h2(v)ÎE2, або h1(v)ÎE2і h2(v)ÎE1.

Розіб'ємо безліч V(E1,E2)на дві частини V(E1,E2,+),V(E1,E2,-)наступним чином:

V(E1,E2,+)=(vÎV(E1,E2)| h1(v)ÎE1і h2(v)ÎE2)

V(E1,E2,-)= ( vÎV(E1,E2)| h2(v)ÎE1і h1(v)ÎE2)

Пропускною здатністю розрізу називатимемо

Q(E1,E2) = (x(v)| vV(E1,E2,+))-(x(v)| vV(E1,E2,-))

Справедлива наступна

Теорема 1. (Про максимальний потік та мінімальний розріз).

У будь-якій мережі величина максимального потоку із джерела tу стік sдорівнює мінімальній пропускній здатності Q(E1,E2)серед усіх розрізів V(E1,E2), що розділяють вершини tі s.

Зауважимо, що у максимальному потоці

x(v)=d(v) , vÎV(E1,E2,+),

x(v)=0 , vÎV(E1,E2,-).

Нехай Q, x(v), vV, -деякий потік у мережі, послідовність

t=i(0),v(1),i(1),v(2),i(2),...,v(k),i(k)=s,

є ланцюгом, що з'єднують вершини tі s. Задамо на цьому ланцюгу напрямок руху від вершини tдо s. Дуга v(j)з цього ланцюга називається прямий, якщо його напрямок збігається з напрямком руху від tдо s, і зворотної інакше. Цей ланцюг називатимемо шляхом збільшення потокуякщо для прямих дуг vланцюги x(v)< d(v) і для зворотних x(v) > 0. По цьому ланцюзі можна пропустити додатковий потік qз tдо sвеличиною q = min (q1, q2),де q1=min (d(v) -x(v)), мінімум береться за всіма прямими дугами ланцюга, q1=min (x(v))мінімум береться по всіх зворотних дугах ланцюга.

Теорема 2.

Потік Q, x(v) , vÎV, максимальний тоді і тільки тоді, коли немає шляху збільшення потоку.

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

вершина iпозначена позначкою q(i)>0, а також відома дуга пряма дуга v(i)через яку надійшов цей потік, або позначена позначкою якщо до неї дійшов деякий додатковий потік величиною q(i)>0, а також відома зворотна дуга v(i), якою надійшов цей потік;

вершина i переглянута, якщо позначено усі сусідні з нею вершини.

Якщо позначено вершину s, то знайдено шлях збільшення потоку величиною q, що пропускається цим шляхом. Для опису алгоритму нам знадобиться також масив SPW, в якому розміщуються номери помічених вершин у порядку їх позначки. З 1- номер у масиві SPWпроглядається вершини, С2- Номер останньої поміченої вершини в цьому масиві.

Алгоритм розрахунку максимального потоку в мережах

І ітерація. КРОК 2. Вибір незалежних маршрутів у мережі та визначення потоків у них.В якості М 1 візьмемо маршрут( v і =V 1 , V 2 , V 5 , v с = V 7), розглянутий у прикладі 1. Для нього А(М 1) = 10.

Також нескладно виділити незалежний від М 1 маршрут М 2 = (v і =V 1 , V 3 , V 6 , v с = V 7). Виконаємо для нього розрахунок максимальної пропускної здатності та скоригуємо пропускну здатність дуг: А(М 2)= min{d 13 , d 36 , d 67 } = min{45, 40, 30} = 30. d 13 ¢ = d 13 - 30 = 15, d 36 ¢ = d 36 - 30 = 10, d 67 ¢ = d 67 - 30 = 0.

ІІ ітерація. КРОК 2.Як єдиний незалежний маршрут приймемо М 3 = (v і =V 1 , V 4 , V 2 , V 5 , v с = V 7). Для нього:

А(М 3)= min{d 14 , d 42 , d 25 , d 57 } = min{15, 10, 10, 15} = 10.

d 14 ¢ = d 14 - 10 = 5, d 42 ¢ = d 42 - 10 = 0, d 25 ¢ = d 25 - 10 = 0, d 57 ¢ = d 57 - 10 = 5.

КРОК 4. Корекція мережі.Максимальний потік А(М 3) віднімаємо з дуг маршруту М 13 . Результат дано на рис.1.16 б.

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

Мережеве планування

Будь-яке завдання з проектування чи побудові досить складного об'єкта ( проект) можна розбити на ряд дрібніших складових кроків. Від правильного виборупослідовності виконання цих кроків залежить терміни виконання всього проекту.

Весь комплекс дій щодо виконання проекту подають у вигляді сукупності подійі робіт. Подіями називають окремі етапи проекту. Роботами називають процес виконання. Весь комплекс подій та робіт, необхідних для виконання проекту, може бути представлений у вигляді двополюсної мережі Г =({v і, v з} , V, X), в якій:

а все подіїпозначені безліччю вершин V,серед них виділено вихідна подія v та(початок робіт) та завершальна подія v з(завершення виконання всього проекту), внутрішні вершини мережі задають проміжні події- етапи, які необхідно виконати у процесі реалізації проекту,

б) усі роботипозначені дугами, що з'єднують між собою пари подій - вершин.

Графічне зображенняданої мережі називають мережевим графіком.Для позначення послідовності дій у мережевий графік вводять також фіктивні роботи, які пов'язані з виконанням будь-яких дій. Відповідні роботи позначають штриховими дугами.

Як приклад розглянемо організацію деякого виробництва. Проект вимагає виконання наступних робіт:

I) маркетингові дослідження; II) передпроектні дослідження з обладнання; III) організація мережі збуту; IV) проведення рекламної кампанії; V) розробка технічного завдання на виробниче обладнання; VI) розробка технічної документації на виробничі приміщення та комунікації; VII) закупівля стандартного обладнання VIII) проектування та виготовлення нестандартного обладнання, IX) будівництво виробничих приміщень та монтаж комунікацій, X) монтаж стандартного обладнання, XI) монтаж нестандартного обладнання, XII) пусконалагоджувальні роботи.

Дані роботи позначимо у мережевому графіку дугами із відповідними номерами.

Подіями у цьому проекті будуть наступні:

1) початок робіт (вихідна подія); 2) завершення маркетингових досліджень; 3) завершення передпроектних досліджень; 4) організація мережі збуту; 5) організація рекламної кампанії; 6) підготовка технічного завдання на виробниче обладнання; приміщення та комунікації, 8) завершення закупівлі стандартного обладнання, 9) завершення проектування та виготовлення нестандартного обладнання, 10) завершення будівництва виробничих приміщень та монтажу комунікацій, 11) завершення встановлення обладнання та пусконалагоджувальних робіт,

12) завершення проекту (завершальна подія).

Події зіставляємо вершини з відповідними номерами. Мережевий графіквиконання проекту дано на рис. 1.17:

Рис.1.17. Мережевий графік виконання проекту

Потоки у мережах

Завдання про максимальний потік

Нехай задана мережа, що складається з безлічі вершин Е і безлічі дуг, що з'єднують деякі впорядковані пари вершин, взятих з Е. Припускатимемо, що вона є симетричним графом, тобто якщо дуга () входить в мережу, то в неї входить і симетрична Дуга (), хоча реально такої дуги може і не бути. Для визначеності привласним вершин мережі такі номери: . Кожна вершина характеризується інтенсивністю. Вершини, котрим , назвемо джерелами, вершини, котрим , - стоками, інші - проміжними. Шляхами мережі прямують деякі потоки - однорідна речовина (газ, рідина) або транспорт - із джерел у стоки. Кожній дузі () мережі поставлено у відповідність число, зване пропускною здатністю дуги. Під пропускною спроможністю дуги розуміється максимальний потік, який може пропустити за одиницю часу. Нехай і для інших вершин, тоді - єдине джерело, - єдиний стік, а - проміжні вершини мережі.

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

(3.9)

при обмеженнях:

(3.11)

Умова (3.9) відображає величину максимального потоку, що дорівнює кількості речовини, що витікає з джерела, або припливає в стік. Умови (3.10) означають, що потік за кожною дугою повинен бути невід'ємним і не перевищувати її пропускну здатність; з умови (3.11) випливає, що кількість речовини, що притікає до будь-якої проміжної вершини, дорівнює кількості речовини, що випливає з неї.

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

Проілюструємо це з прикладу.

Розглянемо мережу, що складається з трьох джерел та двох стоків (Рис. 3.10). Нехай, для певності, дана мережаописує таке завдання.

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

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

Рис. 3.10. Введення фіктивного джерела та стоку

приклад 3.

Наведемо приклад розв'язання задачі про максимальний потік в Excel. Розглянемо деяку транспортну мережу (Рис. 3.11). Припустимо також, що транспортні потоки можуть йти в обох напрямках деяких дуг (очевидно, цей випадок є більш загальним та складним для вирішення, ніж випадок односторонніх транспортних потоків). На малюнку позначені максимальні пропускні здібності в обох напрямках: наприклад з пункту 3 пункт 6 може бути транспортований потік інтенсивністю 4 одиниці, і такий же потік - з пункту 6 пункт 3 (нулі у закінчень деяких дуг означають неможливість транспортування у відповідному напрямку). Потрібно визначити максимальну пропускну спроможність мережі загалом, тобто. максимальне значення потоку.

Рис. 3.11. Мережевий графік прикладу 3.

Рішення.

Так як передбачається, що для кожного проміжного вузла мережі повний вхідний потік повинен дорівнювати повному вихідному потоку, то завдання може бути сформульована наступним чином:

Максимізувати за обмежень:

Введемо дані на робочий лист відповідно до Мал. 3.12.

Рис. 3.12. Дані для вирішення задачі про максимальний потік

Діапазон осередків A6: Q6 відведемо під розрахункові значення змінних. У комірки A8:A14, а також у цільову комірку F13 введемо такі формули

Після запуску Пошуку рішення введемо такі обмеження:

У вікні діалогу Пошуку рішення для діапазону змінних осередків вкажемо A6:Q6.

В результаті рішення отримаємо відповідь: ; потоки в дугах представлені нижче

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