8.3.2. Знаходження максимального потоку на транспортній сітці і мінімального розрізу

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

1) існує єдина вершина тільки з додатно інцидентними дугами ( – вхід сітки);

2) існує єдина вершина тільки з від’ємно інцидентними дугами ( – вихід сітки);

3) кожній дузі поставлено у відповідність ціле невід’ємне число , назване пропускною спроможністю дуги.

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

[v,mf] = grMaxFlows(E,s,t) − для орграфа-сети E (або ) із джерелом s ( або ) і стоком t (або ) знаходить потоки у всіх дугах v, що забезпечують максимальний сумарний потік mf.

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

Вхідний параметр s − номер вершини-джерела.

Вхідний параметр t − номер вершини-стоку.

Вихідний параметр v(m,1) − вектор-стовпець потоків у дугах.

Вихідний параметр mf − сумарний максимальний потік (скаляр).

Для рішення задачі використовується її зведення до задачі лінійного програмування, тому для роботи цієї функції необхідний інструментарій Optimization Toolbox, тому що використовується функція linprog, що вирішує задачу лінійного програмування.

Приклад звертання (скопіюйте цей фрагмент у командне вікно або редактор MATLAB):

clear all % очистили пам'ять

V=[0 0;1 1;1 0;1 -1;2 1;2 0;2 -1;3 1;...

3 0;3 -1;4 0]; % координати вершин

E=[1 2 5;1 3 5;1 4 5;2 3 2;3 4 2;2 5 3;...

2 6 2;3 6 5;3 7 2;4 7 3;5 6 1;6 7 1;...

5 8 5;6 8 2;6 9 3;7 9 2;7 10 3;8 9 2;...

9 10 2;8 11 5;9 11 4;10 11 4];%список дуг орграфа і їхні ваги

s=1; % джерело мережі

t=11; % стік мережі

fprintf('Джерело мережі s=%d\n сток мережі t=%d\n',s,t)

grPlot(V,E,'d','','%d'); % малюємо орграф

set(get(gcf,'CurrentAxes'),...

'FontName','Times New Roman Cyr','FontSize',10) % встановили шрифт

title('\bfорграф мережі')

[v,mf]=grMaxFlows(E,s,t); % вирішуємо задачу

disp('Рішення задачі про максимальний потік')

disp(' N дуги потік')

fprintf(' %2.0f %12.8f\n',[[1:length(v)];v'])

fprintf('Максимальний потік =%12.8f\n',mf)

grPlot(V,[E(:,1:2),v],'d','','%6.4f'); % орграф з потоками по дугах

set(get(gcf,'CurrentAxes'),...

'FontName','Times New Roman Cyr','FontSize',10) % встановили шрифт

title('\bfПотоки по дугах')

Джерело мережі s=1

Стік мережі t=11

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

N дуги потік

1 5.00000000

2 5.00000000

3 2.99999999

4 0.77083005

5 0.00000000

6 3.00000000

7 1.22916995

8 4.23415718

9 1.53667287

10 2.99999999

11 0.00000000

12 0.46332713

13 3.00000000

14 2.00000000

15 3.00000000

16 2.00000000

17 3.00000000

18 0.00000000

19 1.00000000

20 5.00000000

21 4.00000000

22 4.00000000

Максимальний потік = 12.99999999

Отримані в ході рішення орграф і максимальні потоки в дугах представлені на рисунках 8.4 і 8.5.

Рис. 8.4. Орграф мережі

Рис. 8.5. Максимальний потік по дугах