1-й тип 2-й тип 3-й типРис. 2.1-Первинний і вторинний потоки
Потоки не є однорідними: на графі може існувати
видів повторного потоку і типів первинного потоку. При цьому повторний потік може протікати від джерел до стоків будь-якими припустимими шляхами, тоді як кожний тип первинного потоку може існувати лише на визначеному підграфі (відповідно до цого всі типи первинного потоку 1,..., розділені на групи , М = невзаємозамінює типів).Принциповою особливістю задачі, що відрізняє її від класичних задач про багатопродуктові потоки, є наявність взаємозв'язку між потоками: для підтримки повторного потоку по дузі (i, j), переміщення якого приносить «корисний ефект» («прибуток»), необхідно, щоб по ній протікав також первинний, що несе потік, переміщення якого пов'язано з визначеними «витратами».
Первинний потік
m-го типу по дузі (i, j) , М = , складається з потоків «активної» і «пасивної» складових:
Розмір активної складового
первинного потоку визначає розмір повторного потоку по цій дузі, наявність пасивної складової обумовлена вимогою зберігання первинного потоку m-го виду.Активна і пасивна складові подають, наприклад, кількість ресурсів, використовуваних при виконанні робіт, і кількість вільних ресурсів, що переміщаються з однієї роботи на іншу (зокрема, кількості навантажених і порожних транспортних засобів).
Залежність між первинним і повторним потоками виражається в тому. що розмір повторного потоку
по якийсь дузі (i, j) пропорційна активним складових різноманітних типів первинного потоку, що протікають по дузі:Залежність між первинним і повторним потоками не є взаємно однозначної:
1) той самий повторний потік може підтримуватися різноманітними комбінаціями активних складових різноманітних типів первинного потоку;
2) повторний потік може протікати від джерел до стоків будь-якими шляхами, тоді як кожний тип первинного потоку може існувати лише на визначеному підграфі;
3) у процесі свого переміщення від джерела до стоку повторний потік може підтримуватися різноманітними типами первинного потоку, що переміняють один одного в проміжних вершинах (наприклад, на - дузі (7, 2) (див. мал. 3.4) повторний потік підтримується активної складового первинного потоку першого типу, а на дузі (2, 3) - активної складового первинного потоку другого типу);
4) первинний потік може існувати й у тих дугах, у яких повторний потік відсутніх (як, наприклад, у дузі (4, 5) на мал. 2.1).
На відміну від задачі (5) - (11) припускається лише часткове перетворення потоків різноманітних типів продуктів і без їхнього посилення або ослаблення: відмінні від нуля і рівні одиниці лише ті з коефіцієнтів перетворення, що зв'язують активну і пасивну складові того самого типу первинного потоку. Ці складові можуть переходити друг у друга у вершинах
, наприклад на початку і по закінченні робіт (зокрема, при навантаженні і розвантаженні потік порожніх транспортних засобів перетворюється в потік навантажених і навпаки) або при зміні одних ресурсів на інші (зокрема, при перевалюванні вантажів із транспортних засобів одного типу на транспортні засоби іншого типу).Задача полягає в перебуванні такої комбінації первинного і повторного потоків по дугах графа, що забезпечує одержання максимальної «прибули».
У [19] розглядалася більш загальна задача про взаємозалежні потоки на мережі, у якій поряд із не взамозамінює і цілком взаємозамінними типами первинного потоку, що існують на підграфі, що не перетинаються, розглядалися і частково взаємозамінні типи потоку, що існують на підграфах, що мають загальні дуги.
Незважаючи на свою специфічність, задача такого роду мають цілий ряд різноманітних і важливих практичних додатків. Вони виникають у сітковому плануванні і керуванні (коли поряд із послідовністю виконуваних робіт враховуються і переміщення ресурсів), керуванні виробництвом (коли оптимізується потік деталей або напівпродуктів, що проходять послідовне опрацювання, так і потік ресурсів, необхідних для цього опрацювання), керуванні потоками інформації (коли розглядається як потік інформації, так і потік носіїв) і, як уже відзначалося, у плануванні роботи транспорту (коли поряд із розподілом потоку вантажів по транспортній мережі оптимізуються переміщення транспортних засобів, що перевозять ці вантажі).
Для того щоб більш наочно уявити особливості структури даної задачі, роздивимося її окремий випадок, коли є лише один вид повторного потоку, а всі типи первинного потоку цілком взаємозамінні. При цих умовах задача про двох взаємозалежні потоки формулюється в такий спосіб.
Максимізувати
(3) (де - корисний ефект від переміщення одиниці повторного потоку і витрати на переміщення одиниці первинного потоку m-ого типу по дугах (i, j) A графа) при виконанні звичайних умов зберігання кожного з потоків, що проходять через вершину i графа: (6)де
, - попит і пропозиції для первинного і повторного потоків Ks+I, Ks-I, Ks+II і Ks-II- джерела і стоки для первинного і повторного потоків відповідно, а також обмежень на пропускну спроможність дуг (8)і особливих обмежень, що відбивають розподіл первинного потоку на активну і пасивну складові
(9)і залежність повторного потоку від активних складових різноманітних типів первинного потоку
(10)Крім того, повинні виконуватися умови невід’ємності
. (11)Як неважко бачити, основною особливістю, що відрізняє дану задачу від звичайних задач про багатопродуктові потоки мінімальної вартості [24], є наявність специфічних обмежень (9), (10).
Розглянута задача може бути зведена до традиційних задач про потоки в мережах лише в деяких окремих випадках. Одним із найбільше істотних умов для цього є виконання вимоги, щоб перетворення активної складової в пасивну й обернено відбувалося тільки в джерелах і стоках
для повторного потоку і не припускалася передача повторного потоку від ресурсів одного типу до ресурсів іншого типу, тобто щоб розмір активної складового первинного потоку (потоку ресурсів), що підтримує повторний потік від джерела до стоку, оставалась постоянной