Нелінійні задачі розподілу потоків у мережах з фіксованими та вільними вузловими параметрами

The problem of flows distribution in networks presented as a connected flat graph is considered. This problem is formulated as an extremal one with nonlinear objective function and bilateral capacity bounds. In some continuity equations the right sides are presented as unknowns, i.e. optimization is...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2019
Автор:	Kirik, O. E.
Формат:	Стаття
Мова:	Українська
Опубліковано:	The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2019
Онлайн доступ:	https://journal.iasa.kpi.ua/article/view/176059
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	System research and information technologies
Завантажити файл:

Репозитарії

System research and information technologies

_version_	1867334390236839936
author	Kirik, O. E.
author_facet	Kirik, O. E.
author_institution_txt_mv	[ { "author": "O. E. Kirik", "institution": null } ]
author_sort	Kirik, O. E.
baseUrl_str	http://journal.iasa.kpi.ua/oai
collection	OJS
datestamp_date	2019-08-15T19:35:31Z
description	The problem of flows distribution in networks presented as a connected flat graph is considered. This problem is formulated as an extremal one with nonlinear objective function and bilateral capacity bounds. In some continuity equations the right sides are presented as unknowns, i.e. optimization is realized not only over arc but over node variables as well. Solution algorithms based on nonlinear programming methods are proposed.
first_indexed	2025-07-17T10:26:08Z
format	Article
fulltext	© О.Є. Кірік, 2002 106 ISSN 1681–6048 System Research & Information Technologies, 2002, 4 TIДC МЕТОДИ ОПТИМІЗАЦІЇ, ОПТИМАЛЬНЕ УПРАВЛІННЯ І ТЕОРІЯ ІГОР УДК 519.8 НЕЛІНІЙНІ ЗАДАЧІ РОЗПОДІЛУ ПОТОКІВ У МЕРЕЖАХ З ФІКСОВАНИМИ ТА ВІЛЬНИМИ ВУЗЛОВИМИ ПАРАМЕТРАМИ О.Є. КІРІК Розглядається задача розподілу потоків у мережах, що представляються у ви- гляді зв’язних плоских графів. Проблема формулюється як екстремальна задача з нелінійною цільовою функцією та двосторонніми технологічними обме- женнями на змінні. В деяких рівняннях неперервності праві частини представ- лені як невідомі, тобто оптимізація відбувається не тільки за дуговими, але й вузловими змінними. Пропонуються алгоритми розрахунків, що базуються на методах нелінійного програмування. ВСТУП Відгалуження теорії лінійного програмування, пов’язане із знаходженням найвигіднішого розподілу потоків, розвивається вже багато років. Перелік постановок задач з цієї тематики наведений, наприклад у [1]. Аналогічні за- дачі з різноманітними нелінійними цільовими функціями створили розма- їття алгоритмів, частина з яких так чи інакше зводиться до добре розроблених процедур лінійного програмування. Між тим спільність харак- теристик широкого кола розподілюючих мереж дозволяє сформулювати мо- дель потокової задачі з нелінійною функцією цілі загального вигляду [2], яка як частковий випадок охоплює і лінійні задачі. Застосування такої інтег- ральної нелінійної моделі привабливе, по-перше, з тієї точки зору, що до- зволяє розвинути єдину теорію аналізу для широкого кола різних за призначенням, але близьких за структурою мереж. По-друге, дозволяє побудувати цілком конкретні ефективні обчислювальні процедури на основі добре відомих методів нелінійного програмування. Класична задача розподілу потоків формулюється таким чином. Ме- режа задається у вигляді скінченного графа, причому кожній дузі графа ста- виться у відповідність функція вартості протікання потоку та пара чисел, що характеризують верхню та нижню пропускну спроможність. У кожному ву- злі графа задана функція споживання. Потрібно визначити такий план роз- поділу потоків вздовж мережі, що за рахунок всіх джерел задовільнить споживачів з найменшими загальними витратами. У поняття найкращого розподілу потоків надалі вкладатимемо не тіль- ки знаходження оптимальної величини, але й бажаного напрямку проті- Нелінійні задачі розподілу потоків у мережах з фіксованими та вільними вузловими параметрами Системні дослідження та інформаційні технології, 2002, 4 107 кання потоку, що або збігається (значення потоку зі знаком «+»), або проти- лежний (значення потоку зі знаком «–») попередньо заданій орієнтації дуг графа. У разі необхідності можемо легко зафіксувати бажаний напрямок протікання потоку вздовж певних ділянок мережі за допомогою простих двосторонніх обмежень. Деякі достатньо прозорі результати наводяться нижче з доведеннями, якщо ці факти є важливими надалі при побудові алгоритмів. 1. ФОРМУЛЮВАННЯ ПРОБЛЕМИ Мережа топологічно представляє собою зв’язний граф ( )VNG ,= , де N і V - пара скінченних множин. Елементи i множини N називаються вершинами графа G , елементи k множини V — дугами, причому кожному Vk∈ співставлена упорядкована пара вершин ( )ji, , Nji ∈, , що є відповідно по- чатком і кінцем дуги ( )jik ,= . Для графа ( )VNG ,= поставимо оптимізаційну задачу. Потрібно мінімі- зувати функцію ( ) ( ) ∑ ∫ ∈ = Vji x ij ij dttfF , 0 (1) при обмеженнях ( )( ) Nidxx Vjij Vijj ijiij ∈=−∑ ∑ ∈ ∈ , ,: ,: , (2) ( ) Vjirxr ijijij ∈≤≤ +− ,, . (3) Тут ijx — це величина потоку від вершини i у вершину j вздовж дуги ( ) Vji ∈, . Величина id означає кількість речовини, що споживається ( 0<id ) чи подається у мережу ( 0≥id ) у вершині i . Останні нерівності випливають із рівнянь неперервності (2), що служать основною системою обмежень для задач розподілу потоків. Числа + ijr і − ijr визначають верхнє та нижнє техно- логічні обмеження на потік вздовж дуги ( )ji, . Необхідною умовою сумісності системи (2), тобто існування допус- тимого розв’язку задачі розподілу потоків, є виконання співвідношення 0=∑ ∈Ni id , (4) що одержується шляхом додавання рівнянь (2) за всіма Ni∈ . Іншими сло- вами, сумарне споживання повинно в точності дорівнювати сумарній кіль- кості речовини, що подається в мережу. Будемо вважати, що виділена деяка підмножина вершин NN ⊆0 , в яких величина id не фіксована. Це надалі дасть можливість оптимізувати не О.Є. Кірік ISSN 1681–6048 System Research & Information Technologies, 2002, 4 108 тільки розподіл потоків вздовж ділянок мережі, але й подачу речовини у ме- режу в деяких вузлах. Таким чином, мінімізація відбуватиметься за всіма ( ) ,,, Vjixij ∈ 0, Nidi ∈ , зв’язаними обмеженнями (2), (3), за умов, що виконується (4). Що стосується цільової функції, будемо вважати, що кожному ребру ( )ji, поставлена у відповідність неперервна функція ( )ijij xf , причому • вона є строго монотонно зростаючою; • існує таке ijx , що ( ) 0=ijij xf . Як показано в [3], якщо задача є сумісною, такі цілком природні припущення гарантують існування мінімуму. Якщо функція ( )ijij xf відображає умовну вартість проходження потоку вздовж дуги ( )ji, , то розв’язання задачі (1)–(4) дає найвигідніший розподіл потоків вздовж мережі. 2. ПОБУДОВА ДВОЇСТОЇ ЗАДАЧІ Випишемо для сформульованої задачі (1)–(4) необхідні умови екстремуму. Поставимо у відповідність кожному i -му співвідношенню (2) множник Ла- гранжа iλ , Ni∈ , а співвідношенню (4) — 0λ . Запишемо для цієї задачі фу- нкцію Лагранжа ( ) ( )( )( ) + ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ −−+= ∑ ∫ ∑ ∑ ∑ ∈ ∈ ∈ ∈Vji x Ni Vjij Vijj ijiijiij ij dxxdttfL , 0 ,: ,: λ ( ) [ ] [ ] ( ) ∑ ∑∫∑ ∈ ∈∈ −+ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ −−=+ Vji Ni ii x ijijij Ni i dxdttfd ij , 0 0 0 λλλλλ . (5) Згідно з теоремою Куна – Таккера [4], для того аби величини ijx , ( ) Vji ∈, та id , 0Ni∈ , були розв’язком задачі (1)–(4), необхідно та достатньо, щоб знайшлися такі числа iλ , Ni∈ , та 0λ , що відповідні значення ijx та id , 0Ni∈ , доставляли б мінімум функції Лагранжа при обмеженнях +− ≤≤ ijijij rxr , ( ) Vji ∈, . Звідси випливає: 1. Оскільки id , 0Ni∈ , є вільними, то 0λλ =i , 0Ni∈ , тобто в тих вер- шинах, де id не задані, всі iλ є однаковими. 2. Для оптимальних потоків ( )ijijij xx λλ −= . Точка ijx є точкою мінімуму функції ( ) [ ]∫ −− x ijij xdttf 0 λλ (6) Нелінійні задачі розподілу потоків у мережах з фіксованими та вільними вузловими параметрами Системні дослідження та інформаційні технології, 2002, 4 109 при обмеженні +− ≤≤ ijij rxr . Позначимо ( ) ( ) xydttfyx x −= ∫ 0 ,ϕ . (7) Якщо функція f задовольняє наведеним у розділі 1 умовам на функцію вартості протікання потоку, то функція ( )yx,ϕ є опуклою при довільному y , оскільки її похідна ( ) yxfx −=′ϕ є монотонно зростаючою функцією [4]. Таким чином, у задачі ( )yx rxr ,min ϕ +− ≤≤ похідна цільової функції є монотонно зростаючою функцією. Можливі такі варіанти: Якщо ( ) 0≥−− yrf , то функція ϕ зростає і мінімальне значення дося- гається на нижній границі допустимого інтервалу ( ) −= ryq . При ( ) 0≤−+ yrf , зважаючи на від’ємність похідної, функція ϕ є спа- даючою і ( ) += ryx . У випадку, коли ( ) 0<−− yrf , ( ) 0>−+ yrf існує єдиний корінь всере- дині інтервалу ( )+−∈ rrx , і він знаходиться з умови ( ) yxf = . Таким чином, функція ϕ досягає мінімуму в єдиній точці, тому існує одне певне значення ( )yx , яке є точкою мінімуму функції (7) за фіксованого y . Для одновимірної задачі мінімізації функції (6) можемо записати необ- хідні та достатні умови екстремуму. Вони є такими. Якщо −= ijij rx , то похідна функції (6) повинна бути невід’ємною: ( ) ijijij xf λλ −≥ . (8) Якщо += ijij rx , то похідна функції (6) повинна бути недодатною: ( ) ijijij xf λλ −≤ . (9) Якщо +− << ijijij rxr , то похідна повинна дорівнювати нулю: ( ) ijijij xf λλ −= . (10) Теорема 1. Для того аби потоки ijx , ( ) Vji ∈, були оптимальними, не- обхідно і достатньо, щоб знайшлися такі iλ , 0\ NNi∈ , за яких виконува- лися б співвідношення (8)–(10) і 0λλ =i , 0Ni∈ . Величина 0λ може бути вибрана довільно. О.Є. Кірік ISSN 1681–6048 System Research & Information Technologies, 2002, 4 110 Перейдемо тепер до двоїстої задачі. Враховуючи (7), можемо записати: ( ) [ ] ( ) ∑ ∑ ∈ ∈ −+−= Vji Ni iiijijij dxL , 0, λλλλϕ . Оскільки, як зазначено вище, 0λλ =i , 0Ni∈ , то ( ) [ ] ( ) ∑ ∑ ∈ ∈ −+−= Vji NNi iiijijij dxL , \ 0, 0 λλλλϕ . Знайдемо мінімум функції Лагранжа L по ijx . Якщо позначити мі- німальне значення функції ( )yx,ϕ при +− ≤≤ rxr через ( )xϕ̂ , то отримає- мо вираз ( ) [ ] ( ) ∑ ∑ ∈ ∈ −+−=Φ Vji NNi iiijij d , \ 0 0 ˆ λλλλϕ . Із теорії двоїстості, двоїста задача полягає в максимізації вогнутої фун- кції Φ за змінними iλ , 0\ NNi∈ . Згідно з теоремою про похідну від функції мінімуму [4], функція ( )yijϕ̂ є диференційовною по y і її похідна дорівнює значенню похідної від ( )yxijij ,ϕ по y , взятій у точці мінімуму ( )yxij : ( ) ( )yx dy yd ij ij −= ϕ̂ . Звідси ( ) ( )ijij i ijij x d d λλ λ λλϕ −= −ˆ . Похідна цільової функції двоїстої задачі i Ni jiji Ni ijij i dxx d d −−−−= Φ ∑∑ ∈∈ )()( λλλλ λ . (11) Таким чином, двоїста задача зводиться до задачі безумовної оптимізації Φmax , (12) причому її цільова функція має неперервні похідні (11), які можна обчислити. Для розв’язання задачі (12) маємо можливість застосувати довільний метод безумовної оптимізації. 3. ОБЧИСЛЮВАЛЬНІ ПРОЦЕДУРИ Сформулюємо алгоритм для розв’язання задачі оптимального розподілу по- токів у мережі. Нелінійні задачі розподілу потоків у мережах з фіксованими та вільними вузловими параметрами Системні дослідження та інформаційні технології, 2002, 4 111 Алгоритм 1. 1. Надамо невідомим величинам id , 0Ni∈ , довільних значень, що за- довольняють умовам (4). Знайдемо деякий допустимий розподіл потоків ijx , ( ) Vji ∈, , вздовж дуг графа G . Одна з можливих процедур знаходження по- чаткового розподілу потоків буде наведена нижче. 2. Виберемо довільне початкове значення 0λ і знайдемо решту вели- чин iλ , Ni∈ , за формулами ( ) ( ) Vjixf ijijij ∈+= ,,λλ , використовуючи значення потоків, отримані на кроці 1. Ці значення двоїстих змінних приймемо за початкове наближення до розв’язання задачі (12). 3. Максимізуємо функцію Φ , варіюючи тільки змінні iλ , 0\ NNi∈ і покладаючи 0λλ =i , 0Ni∈ . 4. Знаючи оптимальні значення * iλ , Ni∈ , і використовуючи формули (8)–(10), повертаємося до вихідних змінних * ijx , ( ) Vji ∈, , що дає розподіл потоків, який є розв’язком задачі (1)–(4). Тепер обгрунтуємо процедуру знаходження розподілу потоків, що за- довольняє системі (2), вважаючи, що величини Nidi ∈, , є фіксованими в усіх вершинах. Як зазначено вище, вважаємо, що досліджувана нами мережа пред- ставляється у вигляді зв’язного графа. Якщо дуга ( ) Vuw ∈, є розділяючою, то після її видалення з множини V граф ( )( )uwVNG ,\,=′ стає незв’язним. Нехай видалення дуги ( )uw, з графа призводить до розпаду графа на дві ча- стини: ( )www VNG ,= і ( )uuu VNG ,= , що містять, відповідно, вершини w і u . Теорема 2. Якщо в зв’язному графі дуга ( )uw, є розділяючою, то сис- тема (2) однозначно визначає потік по цій дузі: ∑∑ ∈∈ −== uw Ni i Ni iwu ddx . (13) Доведення. В системі (2) перенесемо додаток wux у праву частину. Оскільки він входить у два рівняння цієї системи, позначимо wuww xdd −=′ , wuuu xdd +=′ . Покладемо ii dd =′ для всіх uwi ,≠ . Система (2) розпалася на дві незале- жні підсистеми ( )( ) w Vjij Vijj iijij Nidxx w w ∈′=−∑ ∑ ∈ ∈ , ,: ,: , О.Є. Кірік ISSN 1681–6048 System Research & Information Technologies, 2002, 4 112 ( )( ) u Vjij Vijj iijij Nidxx u u ∈′=−∑ ∑ ∈ ∈ , ,: ,: . Згідно з умовою розв’язності цих систем 0=−=′ ∑∑ ∈∈ wu Ni i Ni i xdd ww , 0=+=′ ∑∑ ∈∈ wu Ni i Ni i xdd uu , що й потрібно було довести. Якщо довільна дуга зв’язного графа є розділяючою, то граф називається деревом. Наслідок. Якщо граф G є деревом, то при виконанні умови (4) система (2) має єдиний розв’язок. Якщо розв’язок існує, то він задається формулою (13), тобто є єдиним. Існування ж розв’язку доводиться індукцією по числу вершин дерева. Таким чином, для графа типу дерева розподіл потоків визначається од- нозначно. На довільному зв’язному графі можна виділити так зване макси- мальне дерево, тобто дерево, що містить всі вершини цього графа. Для цього використовується процедура позначок [3]. Спочатку позначається довільна вершина i . Далі, якщо ( ) Vji ∈, , то по- значається вершина j і дуга ( )ji, . На кожному кроці позначається одна ве- ршина і одна дуга. Оскільки граф G є зв’язним, то процес закінчиться позначкою всіх N вершин і 1−N дуг. Позначені елементи графа і утво- рюють дерево. Довільне максимальне дерево можна отримати, якщо провес- ти процес позначок відповідним чином. Якщо позначити ( )VNG ′=′ , , VV ⊆′ — виділене на графі G дерево, то систему (2) можна перетворити до вигляду ( )( ) Nidxx Vjij Vijj ijiij ∈′=−∑ ∑ ′∈ ′∈ , ,: ,: , де ( )( ) ∑ ∑ ′∈ ′∈ +−=′ VVjij VVijj jiijii xxdd \,: \,: , тобто невідомі, які відповідають дугам, що не входять у максимальне дере- во, переносяться у праву частину. Якщо задати на них потоки довільним чином, то потоки вздовж решти дуг визначаться однозначно. Цю процедуру можна використовувати для знаходження початкового розподілу потоків в алгоритмі 1. Нелінійні задачі розподілу потоків у мережах з фіксованими та вільними вузловими параметрами Системні дослідження та інформаційні технології, 2002, 4 113 4. ПРИКЛАД ЗАДАЧІ НАЙВИГІДНІШОГО ГАЗОРОЗПОДІЛУ Розглянемо задачу розподілу потоків газу в мережі, яка може бути сформу- льована у такий спосіб. У заданій по конфігурації газовій мережі відомими є довжина та пропускна спроможність кожної ділянки, споживання у ве- ршинах та місцезнаходження газоперекачуючих станцій (ГС). Об’єм подачі газу в систему з конкретних ГС не фіксований. Потрібно розрахувати опти- мальний розподіл потоків, у тому числі і подачу газу в систему в місцях роз- ташування ГС. Нехай NN ⊆0 - підмножина вершин графа G , в яких розташовані ГС, а довжину дуги ( ) Vji ∈, позначимо ijl . Тоді сформульована задача може бути записана таким чином. Мінімізувати функцію ( ) 10, , 1 1 <<= ∑ ∈ + α α Vji ijij xlF , (14) за обмежень ( )( ) Nidxx Vjij Vijj ijiij ∈=−∑ ∑ ∈ ∈ , ,: ,: , (15) ( ) Vjirxr ijijij ∈≤≤ +− ,, (16) та умові розв’язності ∑∑ ∈∈ =+ 00 \ 0 NNi i Ni i dd . (17) Введення додаткового коефіцієнта у (14) не впливає на знаходження точки мінімуму. Нам буде зручно мінімізувати функцію ( ) ∑ ∈ + << + = Vji ijij qlF , 1 1 10, 1 1 α α α . (18) Із теореми 1 отримаємо, що мінімум функції Лагранжа для задачі (18), (15), (17) з врахуванням простих обмежень (16) досягається у точці ( ) ( ) ( ) ( ) ( )⎪ ⎪ ⎪ ⎪ ⎩ ⎪⎪ ⎪ ⎪ ⎨ ⎧ ≥−− ≤−− ≥−− − − ≤−− = ++ + − −− .signпри ,sign ,sign приsign ,signпри 11 11 11 1 1 11 * αα αα αα α α αα λλλλ λλλλ λλλλ λλ λλ λλλλ ijijijijij ijijijij ijijijij ij ij ij ijijijijij ij lrr lr lr l lrr x (19) Крім того виконуються співвідношення О.Є. Кірік ISSN 1681–6048 System Research & Information Technologies, 2002, 4 114 00 , Nii ∈= λλ , (20) ( ) Vjixxl ijijijij ∈+= ,,sign α λλ . (21) Функція xsign визначається з умови ⎪ ⎩ ⎪ ⎨ ⎧ < = > − = .0 ,0 ,0 ,1 ,0 ,1 sign x x x x Співвідношення (20), (21) використовуються на кроці 2 алгоритму 1. При розв’язанні двоїстої задачі 1maxΦ (22) значення змінних iλ , Ni∈ , як було зазначено в теоремі 1, збігаються для тих вершин NNi ⊆∈ 0 , де розташовані ГС. При реалізації алгоритму 1 для розв’язання задачі без обмежень (22) використовувався метод покоординатного спуску, питання збіжності якого для задач на мережах досліджувалися у роботі [2]. Застосування цього мето- ду дозволило особливо ефективно враховувати адитивність цільової функції і за рахунок цього зменшити кількість обчислень на кожному кроці. Форму- ли (19) служили для повернення до вихідних змінних. Продемонструємо послідовність розрахунків на невеликому тестовому прикладі (рис. 1). При розрахунках двосторонні обмеження (16) розглядалися у формі ( ) Vjirx ijij ∈≤ ,, , 31 4 2 6 7 8 5 [+50] [-6] (3,5) [-12] (1,12) [+20][-15] [-17] [-10] (4,22) (5,25) (1,15) (2,20) (6,7) (3,3) (7,12) (5,11) (4,18) Рис. 1. Модельний приклад мережі із заданими параметрами: [фіксоване споживання у вузлі]; (довжина дуги, пропускна спроможність дуги) Нелінійні задачі розподілу потоків у мережах з фіксованими та вільними вузловими параметрами Системні дослідження та інформаційні технології, 2002, 4 115 тобто вважалося, що потоки газу у протилежних напрямках є рівноможливими з точки зору технологічних обмежень на пропускну спроможність дуг ме- режі. Надамо дугам мережі довільної початкової орієнтації, наприклад, бу- демо вважати, що кожна дуга орієнтована від вершини з меншим номером до вершини з більшим номером (рис. 2). Процедура знаходження початкового розподілу потоків, наведена в розділі 3, починається з виділення на графі максимального дерева (рис. 3). На рис. 4 представлений обчислений за алгоритмом 1 розподіл потоків, коли параметри джерел є фіксованими. Розмір загальних затрат на транспортування газу у цьому тестовому прикладі становить 431 одиницю. [-10] 3 1 4 2 6 7 8 5 [+50] [-6] [-12] [+20][-15] [-17] [-10] Рис.3. Максимальне дерево графа: — дуги, що належать до максимального дерева; — дуги, на яких початковий розподіл потоків задається довільним чином [-10] 1 31 4 2 6 6 7 8 5 [ + [+50] ] [[-6] [-1 [-12] [+20][-15] [-17] [-10] x x35 x x 14 Рис. 2. Орієнтований граф x13 x35 x56 x57 x58 x67 x78 x34 x14 x24 x12 О.Є. Кірік ISSN 1681–6048 System Research & Information Technologies, 2002, 4 116 На рис. 5 представлений розв’язок цієї ж задачі, але тепер споживання у ву- злах 2, 3, 4, 5, 6, 8 фіксоване, а подача газу в систему у вузлах 1 і 7 оптимізу- ється разом з потоковими змінними. Загальні витрати становлять 285 одиниць, тобто виграш в ефективності становить майже третину попередніх витрат. 5. ОСОБЛИВОСТІ ЗАСТОСУВАННЯ МЕТОДУ ЛІНЕАРИЗАЦІЇ ДО ЗАДАЧ РОЗРАХУНКУ ПОТОКІВ Модель потокової задачі, наведена у розділі 1, має опуклу цільову функцію. Нижче розглянемо метод розв’язання нелінійних задач за- гального вигляду, який, взагалі кажучи, не вимагає опуклості функцій. Рис.5. Розподіл потоків з оптимізацією подачі газу в мережу 31 4 2 6 7 8 5 [ 1d ] [-6] (4,5) [-12] (12) [ 7d ][-15] [-17] (14) (9) (14,5) (20) (5) (3) (1) (6,5) (5) [-10] [-10] [-10] 31 4 2 6 7 8 5 [+50] [-6] (5) [-12] (12) [+20][-15] [-17] [-10] (22) (24) (15) (11) (5) (3) (8) (13) (4) Рис.4. Розподіл потоків у мережі з фіксованими джерелами: [споживання у вузлі]; (значення потоку вздовж дуги) Нелінійні задачі розподілу потоків у мережах з фіксованими та вільними вузловими параметрами Системні дослідження та інформаційні технології, 2002, 4 117 Звичайно, у цьому випадку розв’язок може суттєво залежати від вибору по- чаткової точки. Для зручності перепишемо задачу розподілу потоків у матричному ви- гляді. Будемо важати, що nN = , mV = , тобто граф складається з n вузлів та m перенумерованих дуг k , Vk∈ . На множині вузлів заданий n -вимірний вектор споживання ( )idd = , ni ,...,1= , невід’ємні елементи яко- го відповідають джерелам. Потокові змінні перенумеровані аналогічно ду- гам і утворюють m -вимірний вектор ( )kxx = , mk ,...,1= , кожен елемент якого — це потік вздовж певної дуги. У задачі ( ) ( ) min 1 →≡ ∑ = m k kk xFxF (23) dAx = , (24) +− ≤≤ rxr , (25) цільова функція може мати вигляд (1) або бути сумою інших неперервно диференційованих функцій, які відображають вартість протікання потоків вздовж дуг. Матриця A — це матриця інциденцій вузли-дуги, розмірністю mn× , елементи якої визначаються за правилом: ( ) ( ) ⎪ ⎩ ⎪ ⎨ ⎧ ∗=− ∗= = випадках.інших в0 ,,дуга якщо,1 ,,дуга якщо,1 ik ik aik Для спрощення записів вважаємо, що в рівняннях (24) всі компоненти вектора споживання є фіксованими. Для розв’язання задачі (23)–(25) застосуємо метод лінеаризації [5], ос- новна ідея якого полягає в заміні вихідної задачі послідовністю задач квад- ратичного програмування з одиничною матрицею квадратичної форми. Специфічна форма цих допоміжних задач дозволяє ефективно врахувати структуру обмежень задач на мережах. Алгоритм 2. 1. Виберемо довільний початковий розподіл потоків, наприклад за процедурами, описаними у розділі 3. Позначимо цей початковий вектор- потік 0x . 2. Загальний крок алгоритму. Якщо побудована точка kx , розв’язуємо задачу ( )( ) min 2 1, 2 →+′ ppxF , (26) 0=−+ dAxAp , (27) xrpxr −≤≤− +− , (28) О.Є. Кірік ISSN 1681–6048 System Research & Information Technologies, 2002, 4 118 де p — евклідова норма, а ( )px, — скалярний добуток. Ця задача розв’язується за фіксованого kxx = відносно mRp∈ і її розв’язок позна- чається kp . 3. Коли kp знайдено, то покладаємо k k kk pxx α+=+1 , де kα може бути вибране за одною з формул, наведених у [5]. 4. Умовою зупинки алгоритму є виконання вимоги 0=p . Основною обчислювальною процедурою цього алгоритму є розв’язання квадратичної задачі (26)–(28). Для знаходження її розв’язку застосуємо ме- тодику переходу до двоїстої задачі без обмежень, яка була розглянута вище, з тією різницею, що тепер ця процедура застосовується не до вихідної, а до допоміжної задачі. Якщо позначити nR∈λ вектор двоїстих змінних, що відповідають об- меженням (27), то легко отримати, що двоїста задача до (26)–(28) буде поля- гати в максимізації функції ( ) ( ) ( )∑ ∑ = = −+−= m k n i iiik dxAhH 1 1 2 2 1 λλλ , (29) де ( ) ( ) ( ) ( ) ( )⎪ ⎪ ⎪ ⎩ ⎪ ⎪ ⎪ ⎨ ⎧ −′−≥− −′−> <−′− ′−− −′−≤− = −− − + ++ ,якщо, , , якщо, ,якщо, )( kkkk T kkk kkkk T k T kkkkk kk T k kkkk T kkk k rxFxAxr rxFxA ArxFx xFA rxFxAxr h λ λ λ λ λ λ (30) причому iA та T kA — відповідно i -й та k -й рядки матриці інциденцій та транспонованої до неї. Для розв’язання задачі (29) може бути застосований метод спряжених градієнтів, модифікації якого для задач із структурою обмежень, характерних для моделей на мережах, наведені у [6]. Повернення до вихідних змінних допоміжної задачі здійснюється за формулами (30): ( ) mkhp kk ,...,1, == λ . Наостанок зазначимо, що у випадку, коли розглядається задача оп- тимізації потокорозподілення без технологічних обмежень, тобто у вигляді (23), (24), задача (29) переходить у задачу максимізації квадратичної функції ( ) ( ) ( )( ) ( ) 2 2 1,, 2 1 xFdAxxFAAAH T ′−+−′−−= λλλλ , Нелінійні задачі розподілу потоків у мережах з фіксованими та вільними вузловими параметрами Системні дослідження та інформаційні технології, 2002, 4 119 де 0≥TAA , що випливає з лінійної залежності строк матриці інциденцій. ВИСНОВКИ Дослідження задачі оптимального розподілу потоків в мережах з інтегральною цільовою функцією дозволило охопити спільним підходом достатньо ши- рокий спектр мереж і виробити єдину концепцію їх аналізу. При розрахун- ках конкретних задач можливе додаткове підвищення ефективності при всебічному врахуванні обчислювальних аспектів. На відміну від традиційно підходу, як невідомі розглядалися не тільки дугові, але й вузлові змінні. У розділі 4 показано, що в тих задачах, де така постановка задачі можлива і доцільна, відбувається значне зменшення затрат на транспортування потоків. Декілька слів щодо відсутністі жорсткої фіксації напрямків протікання потоків. При розрахунках діючих трубопроводів ідея зміни напрямку протікання потоку на протилежний, навіть значно ефективніший економічно, може бути нереалізовною з точки зору інженерних рішень. Але на етапах проектування розподільчих систем ідея визначення оптимального напрямку протікання потоків виявилась цілком доречною. ЛІТЕРАТУРА 1. Ловецкий С.Е., Меламед И.И. Статические потоки в сетях // Автоматика и те- лемеханика. — 1987. — № 10. — С. 3–29. 2. Пшеничный Б.Н. Расчет энергетических сетей на электронных вычислительных машинах // Журн. вычисл. математики и мат. физики. — 1962. — 2, № 5. — С. 942–947. 3. Кирик Е.Е., Пшеничный Б.Н. Теория и методы расчета сетей // Обозрение при- кладной и промышленной математики. — М., 1995. — 2, вып. 1. — С. 49–69. 4. Пшеничный Б.Н. Выпуклый анализ и экстремальные задачи. — М.: Наука, 1980. — 320 с. 5. Пшеничный Б.Н. Метод линеаризации. — М.: Наука, 1983. — 136 с. 6. Кірік О.Є. Розв‘язання нелінійної задачі оптимального газорозподілу // Наукові вісті НТУУ «КПІ», 2000. — №5. — С. 30–34. Надійшла 06.12.2002
id	journaliasakpiua-article-176059
institution	System research and information technologies
keywords_txt_mv	keywords
language	Ukrainian
last_indexed	2025-07-17T10:26:08Z
publishDate	2019
publisher	The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
record_format	ojs
resource_txt_mv	journaliasakpiua/76/9312e207326bbdc59cc5e0501c7b8476.pdf
spelling	journaliasakpiua-article-1760592019-08-15T19:35:31Z Nonlinear network flow distribution problems with fixed and free node parameters Нелинейные задачи распределения потоков в сетях с фиксированными и свободными узловыми параметрами Нелінійні задачі розподілу потоків у мережах з фіксованими та вільними вузловими параметрами Kirik, O. E. The problem of flows distribution in networks presented as a connected flat graph is considered. This problem is formulated as an extremal one with nonlinear objective function and bilateral capacity bounds. In some continuity equations the right sides are presented as unknowns, i.e. optimization is realized not only over arc but over node variables as well. Solution algorithms based on nonlinear programming methods are proposed. Рассматривается задача распределения потоков в сетях, которые представляются в виде связных плоских графов. Проблема формулируется как экстремальная задача с нелинейной целевой функцией и двусторонними технологическими ограничениями на переменные. В некоторых уравнениях непрерывности правые части представлены как неизвестные, т.е. оптимизация осуществляется не только по дуговым, но и по узловым переменным. Предлагаются алгоритмы расчетов, базирующиеся на методах нелинейного программирования. Розглядається задача розподілу потоків у мережах, що представляються у вигляді зв’язних плоских графів. Проблема формулюється як екстремальна задача з нелінійною цільовою функцією та двосторонніми технологічними обмеженнями на змінні. В деяких рівняннях неперервності праві частини представлені як невідомі, тобто оптимізація відбувається не тільки за дуговими, але й вузловими змінними. Пропонуються алгоритми розрахунків, що базуються на методах нелінійного програмування. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2019-08-15 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/176059 System research and information technologies; No. 4 (2002); 106-119 Системные исследования и информационные технологии; № 4 (2002); 106-119 Системні дослідження та інформаційні технології; № 4 (2002); 106-119 2308-8893 1681-6048 uk https://journal.iasa.kpi.ua/article/view/176059/175898 Copyright (c) 2021 System research and information technologies
spellingShingle	Kirik, O. E. Нелінійні задачі розподілу потоків у мережах з фіксованими та вільними вузловими параметрами
title	Нелінійні задачі розподілу потоків у мережах з фіксованими та вільними вузловими параметрами
title_alt	Nonlinear network flow distribution problems with fixed and free node parameters Нелинейные задачи распределения потоков в сетях с фиксированными и свободными узловыми параметрами
title_full	Нелінійні задачі розподілу потоків у мережах з фіксованими та вільними вузловими параметрами
title_fullStr	Нелінійні задачі розподілу потоків у мережах з фіксованими та вільними вузловими параметрами
title_full_unstemmed	Нелінійні задачі розподілу потоків у мережах з фіксованими та вільними вузловими параметрами
title_short	Нелінійні задачі розподілу потоків у мережах з фіксованими та вільними вузловими параметрами
title_sort	нелінійні задачі розподілу потоків у мережах з фіксованими та вільними вузловими параметрами
url	https://journal.iasa.kpi.ua/article/view/176059
work_keys_str_mv	AT kirikoe nonlinearnetworkflowdistributionproblemswithfixedandfreenodeparameters AT kirikoe nelinejnyezadačiraspredeleniâpotokovvsetâhsfiksirovannymiisvobodnymiuzlovymiparametrami AT kirikoe nelíníjnízadačírozpodílupotokívumerežahzfíksovanimitavílʹnimivuzlovimiparametrami

Нелінійні задачі розподілу потоків у мережах з фіксованими та вільними вузловими параметрами

Репозитарії

Схожі ресурси