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

Побудовано та досліджено математичні моделі розподілу потоків обмежених ресурсів у енергетичних системах. Розроблено методи розв’язання задач розподілу потоків, що базуються на поєднанні екстремального підходу до розрахунку мереж та спільного розв’язку двох основних систем Кірхгофа. Запропоновано еф...

Повний опис

Збережено в:

Бібліографічні деталі
Опубліковано в: :	Системні дослідження та інформаційні технології
Дата:	2013
Автор:	Кірік, О.Є.
Формат:	Стаття
Мова:	Українська
Опубліковано:	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України 2013
Теми:	Методи оптимізації, оптимальне управління і теорія ігор
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/85133
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Розподіл ресурсів у розподільчих системах з оптимальним перерозподілом навантаження постачальників продукту / О.Є. Кірік // Системні дослідження та інформаційні технології. — 2013. — № 4. — С. 38-51. — Бібліогр.: 8 назв. — укр.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

_version_	1860235223261773824
author	Кірік, О.Є.
author_facet	Кірік, О.Є.
citation_txt	Розподіл ресурсів у розподільчих системах з оптимальним перерозподілом навантаження постачальників продукту / О.Є. Кірік // Системні дослідження та інформаційні технології. — 2013. — № 4. — С. 38-51. — Бібліогр.: 8 назв. — укр.
collection	DSpace DC
container_title	Системні дослідження та інформаційні технології
description	Побудовано та досліджено математичні моделі розподілу потоків обмежених ресурсів у енергетичних системах. Розроблено методи розв’язання задач розподілу потоків, що базуються на поєднанні екстремального підходу до розрахунку мереж та спільного розв’язку двох основних систем Кірхгофа. Запропоновано ефективний алгоритм ув’язки мережі для знаходження початкового наближення до розв’язку більш складної нелінійної транспортної задачі. Проаналізовано проблему оптимального перерозподілу навантаження постачальників продукту. Як приклад розглянуто задачу поставки споживачам суміші речовини у певних пропорціях або з певними кількісними обмеженнями. Завдяки загальній постановці задачі запропоновані моделі, методи та алгоритми можуть використовуватися для розрахунку різнотипних розподільчих мереж та трубопроводів. Построены и исследованы математические модели распределения потоков ограниченных ресурсов в энергетических системах. Разработаны методы решения задач распределения потоков, базирующиеся на сочетании экстремального подхода к расчету сетей и совместного решения двух основных систем Кирхгофа. Предложен эффективный алгоритм увязки сети для нахождения начального приближения к решению более сложной нелинейной транспортной задачи. Проанализирована проблема оптимального перераспределения нагрузки поставщиков продукта. В качестве примера рассмотрена задача поставки потребителям смеси вещества в определенных пропорциях или с определенными количественными ограничениями. Благодаря общей постановке задачи предложенные модели, методы и алгоритмы могут использоваться для расчета разнотипных распределительных сетей и трубопроводов. Mathematical models of flow distribution of scarce resources in energy systems are constructed and investigated. Methods for solving problems of flow distribution, based on a combination of extreme approach to the calculation of nets and joint solution of the two main systems of Kirchhoff are developed. An efficient network link algorithm to find an initial approximation to the solution of complex nonlinear transportation problem is proposed. The problem of optimal redistribution of load of product suppliers is analyzed. As an example the problem of delivery to consumers the mixture of substance in certain proportions or with certain quantitative restrictions is considered. Thanks to the general formulation of the problem the proposed models, methods and algorithms can be used to calculate the different types of distribution of the networks and pipelines.
first_indexed	2025-12-07T18:22:50Z
format	Article
fulltext	© О.Є. Кірік, 2013 38 ISSN 1681–6048 System Research & Information Technologies, 2013, № 4 УДК 519.8 РОЗПОДІЛ РЕСУРСІВ У РОЗПОДІЛЬЧИХ СИСТЕМАХ З ОПТИМАЛЬНИМ ПЕРЕРОЗПОДІЛОМ НАВАНТАЖЕННЯ ПОСТАЧАЛЬНИКІВ ПРОДУКТУ О.Є. КІРІК Побудовано та досліджено математичні моделі розподілу потоків обмежених ресурсів у енергетичних системах. Розроблено методи розв’язання задач роз- поділу потоків, що базуються на поєднанні екстремального підходу до розра- хунку мереж та спільного розв’язку двох основних систем Кірхгофа. Запропо- новано ефективний алгоритм ув’язки мережі для знаходження початкового наближення до розв’язку більш складної нелінійної транспортної задачі. Про- аналізовано проблему оптимального перерозподілу навантаження постачаль- ників продукту. Як приклад розглянуто задачу поставки споживачам суміші речовини у певних пропорціях або з певними кількісними обмеженнями. За- вдяки загальній постановці задачі запропоновані моделі, методи та алгоритми можуть використовуватися для розрахунку різнотипних розподільчих мереж та трубопроводів. ВСТУП Забезпечення оптимального розподілу ресурсів за рахунок найкращого управління потоками у розподільчій мережі — одне з найважливіших за- вдань експлуатації енергетичних систем. Основними інструментами моде- лювання та практичних розрахунків є мережеві потокові моделі та методи математичного програмування, реалізовані в сучасних інформаційних сис- темах. Для конкретності будемо використовувати термінологію, прийняту при розрахунках газових мереж, хоча загальний характер закономірнос- тей дозволяє застосовувати запропоновані обчислювальні процедури для розрахунків довільних розподільчих мереж. Потокорозподілення в мережі визначається двома системами умов або, що те ж саме, двома законами Кірхгофа [1]: загальна витрата продукту, що надходить до будь-якого вузла, дорівнює загальній витраті, що залишає його; загальна зміна тиску вздовж будь-якого замкнутого контуру мережі дорів- нює нулю. Існують два основні прийоми для розрахунку потокорозподілу. Пер- ший виходить із того, що потоки завжди задовольняють умові рівності нулю їх загального балансу в кожному вузлі й послідовно коригуються з тим, щоб задовольнити умові рівності нулю загальну зміну тиску вздовж кожного контуру. Другий базується на тому, що загальна зміна тиску уздовж кожно- го контуру завжди дорівнює нулю, а потоки на ділянках контуру послідовно підбираються так, щоб загальний їх баланс у кожному вузлі, врешті-решт, став рівним нулю. Перший метод називають методом балансування тис- ків, а другий — методом балансування потоків. З огляду на фізичний зміст цих методів вони отримали назву методів ув’язки [1]. Поряд із цим існує інший підхід до таких задач, який можна назвати екстремальним, коли йдеться про мінімізацію (або максимізацію) деякої Розподіл ресурсів у розподільчих системах з оптимальним перерозподілом навантаження … Системні дослідження та інформаційні технології, 2013, № 4 39 спеціальної функції, що відповідає тому чи іншому оптимізаційному прин- ципу, з урахуванням зв’язків, що накладаються рівняннями лише першого або другого законів Кірхгофа [2]. Таким чином, серед різних ідей розрахунку потокорозподілу з матема- тичної точки зору можна виділити дві основних — спільний розв’язок двох основних систем рівнянь або перехід до задач нелінійного програмування, зокрема, до нелінійної мережевої транспортної задачі. Мета роботи полягає у розробці ефективних методів розподілу ресур- сів у великих розподільчих мережах та їх застосуванні до розв’язання прак- тичних задач поставки споживачам суміші продуктів у певних пропорціях або певної якості. Буде розглянуто обчислювальні можливості екстремального методу у поєднанні з методом ув’язки мережі, коли спільний розв’язок двох основ- них систем Кірхгофа використовується як початкове наближення для розв’язання більш складної та великої задачі нелінійного програмування. Частину результатів, викладених у статті було отримано, в тій чи іншій формі, у роботах [3]–[5]. З метою замкненості викладу нижче з доведеннями наведено ті результати, що дають основу для розв’язання великої кількості проблем, пов’язаних із пошуком допустимих потоків у мережах та їх опти- мізацією. ФОРМУЛЮВАННЯ ПРОБЛЕМИ Розподільчу мережу представляємо у вигляді зв’язного орієнтовного графа ),,( VNG = де N та V — пара скінчених множин. Елементи i множини N називаються вершинами графу ,G елементи v множини V — дугами, при- чому кожному Vv∈ співставлено упорядковану пару вершин ),,( ji ,, Nji ∈ що є відповідно початком і кінцем дуги ).,( jiv = Нехай ijx — це величина потоку від вершини i у вершину j вздовж дуги .),( Vji ∈ Кожній дузі графа ),( jiv = ставиться у відповідність пара чисел − ijr , + ijr , що характеризують її верхню та нижню пропускну спромож- ність. Крім того, за допомогою двосторонніх обмежень можна зафіксувати певний напрям протікання потоків. У вузлах графа задаються функції споживання (замовлення споживачів та план постачання продукту), причому подача продукту з різних джерел може бути або константами (детерміновані джерела) або змінними (недетер- міновані джерела). Потрібно визначити такий план розподілу потоків вздовж мережі, що за рахунок можливого перерозподілу навантаження не- детермінованих джерел задовольнить споживачів із найменшими загальни- ми витратами. Основна система, що є обмеженнями для змінних в оптимізаційних за- дачах розподілу потоків — є система рівнянь, заданих у вершинах графа: ., ),(: ),(: Nidxx Vjij Vijj ijiij ∈=−∑ ∑ ∈ ∈ (1) Величина id означає кількість речовини, що споживається ( 0<id ) або подається у мережу ( 0≥id ) у вершині .i О.Є. Кірік ISSN 1681–6048 System Research & Information Technologies, 2013, № 4 40 Необхідною умовою сумісності рівнянь (1) є виконання співвідношення 0=∑ ∈Ni id , (2) що забезпечує збалансованість системи (1) . ),(: ),(: ∑ ∑ ∑ ∑ ∈ ∈ ∈ ∈ = Ni Vjij Ni Vijj jiij xx Система (1) — це аналог відомої системи Кірхгофа, що відображає за- кон збереження речовини та гарантує задоволення всіх споживачів, розта- шованих у вершинах графу. Випишемо тепер функцію, яка характеризує приналежність довільної дуги певному шляху на графі: ( ) ( ) ⎪⎩ ⎪ ⎨ ⎧ −=∈==∃− −=∈==∃+ = ++ ++ ,випадкахінших всіх у 0 ,1,...,1,,,,:якщо,1 ,1,...,1,,,,: якщо,1 11 11 , mkVjjjjjik mkVjjjjjik kkkk kkkk Jijω де =J ),...,,( 21 mjjj — шлях, що з’єднує вершини 1j та mj графа .G Друга важлива система рівнянь для енергетичних систем виникає із другого закону Кирхгофа, який вимагає, щоб падіння тиску вздовж довіль- ного замкненого контуру дорівнювало нулю: ( ) ,0 , ,∑ ∈ = Vji ijZij h s ω ,,...,2,1 ns = (3) де ijh — це падіння тиску на ділянці ,),( Vji ∈ а sZ — перенумеровані замкнені контури мережі. Тут sZij,ω характеризує приналежність дуги ),( ji до контуру .sZ Падіння тиску ijh вздовж дуги ),( ji — є функція від потоку ijx , тобто ).( ijijij xfh = (4) Нижче буде показано, що за умови виконання (2) спільний розв’язок рівнянь (1), (3), (4) існує, є єдиним і дає розподіл потоків, що реалізує міні- мум функції ∑ ∫ ∈ = Vji x ij ij dttfF ),( 0 )( на множині, що задається системою (1). ЗАДАЧА РОЗПОДІЛУ ПОТОКІВ ІЗ ДЕТЕРМІНОВАНИМИ ПОСТАВКАМИ ПРОДУКТУ Для графа ),( VNG = поставимо оптимізаційну задачу. Потрібно мінімізувати функцію ∑ ∫ ∈ = Vji x ij ij dttfF ),( 0 )( (5) Розподіл ресурсів у розподільчих системах з оптимальним перерозподілом навантаження … Системні дослідження та інформаційні технології, 2013, № 4 41 за обмежень ,, ),(: ),(: Nidxx Vjij Vijj ijiij ∈=−∑ ∑ ∈ ∈ (6) .),(, Vjirxr ijijij ∈≤≤ +− (7) Якщо задати функцію )( ijij xf таким чином, що вона буде відображати умовну вартість проходження потоку вздовж дуги ),( ji , то розв’язання за- дачі (5)–(7) дасть найвигідніший розподіл потоків уздовж мережі. Надалі будемо вважати, що для кожного ребра ),( ji функція )( ijij xf є неперервною, строго монотонно зростаючою та існує таке ijx , що .0)( =ijij xf Не обмежуючи загальності можемо покласти 0)0( =ijf при .0=t У [4] показано, що такі цілком природні припущення гарантують іс- нування мінімуму поставленої задачі. Випишемо для сформульованої задачі (5)–(7) функцію Лагранжа, вра- хувавши обмеження–рівності й поставивши у відповідність кожному i -му співвідношенню (6) множник Лагранжа iu , :Ni∈ ( ) = ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ −−+= ∑ ∫ ∑ ∑ ∑ ∈ ∈ ∈ ∈Vji x Ni Vjij Vijj ijiijiij ij dxxudttfL ),( 0 ),(: :),( ∑ ∑∫ ∈ ∈ − ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ −−= Vji Ni ii x ijijij duuuxdttf ij ),( 0 )()( . У [4] доведено, що умови, накладені на функції )( ijij xf забезпечують опуклість функцій xydttfyx x ijij −= ∫ 0 )(),(ϕ (8) для довільного .y Для оптимальних потоків ),( ijijij uuxx −= причому точка ijx є розв’язком одновимірної задачі мінімізації ∫ −− x ijij uuxdttf 0 )()( (9) за обмежень +− ≤≤ ijij rxr . З огляду на те, що в задачі ),(min yxij rxr ijij ϕ +− ≤≤ (10) похідна цільової функції yxf x ij ij −= ∂ ∂ )( ϕ є монотонно зростаючою функці- єю, то можливі наступні варіанти. О.Є. Кірік ISSN 1681–6048 System Research & Information Technologies, 2013, № 4 42 Якщо ,0)( ≥−− yrf ijij то функція ijϕ зростає і мінімальне значення досягається на нижній межі допустимого інтервалу .)( −= ijryx Якщо ,0)( ≤−+ yrf ijij то, зважаючи на від’ємність похідної, функція ijϕ є спадаю- чою та += ijryx )( . У випадку, коли ,0)( <−− yrf ijij 0)( >−+ yrf ijij існує єди- ний корінь всередині інтервалу ),( +−∈ ijij rrx і знаходиться з умови .)( yxfij = Це означає, що точка мінімуму задачі (10) або є постійним значенням, що співпадає з − ijr чи + ijr , або всередині інтервалу допустимості залежить від .y Таким чином, функція ijϕ досягає мінімуму в єдиній точці, тобто існує одне певне значення ),(yx яке є точкою мінімуму функції (8) при фіксовано- му .y Тепер можемо виписати необхідні та достатні умови екстремуму для вихідної задачі. Теорема 1 [4]. Для того, щоб потоки ,ijx Vji ∈),( були оптимальними, необхідно і достатньо, щоби знайшлися такі iu , ,Ni∈ для яких виконують- ся умови: • якщо −= ijij rx , то похідна функції (8) має бути невід’ємною: ijijij uuxf −≥)( ; (11) • якщо += ijij rx , то похідна функції (9) має бути недодатньою: ijijij uuxf −≤)( ; (12) • якщо +− << ijijij rxr , то похідна має дорівнювати нулю: ijijij uuxf −=)( . (13) Ці умови є необхідними та достатніми умовами існування розв’язку для задачі розподілу усталеного потоку вздовж ділянок мережі за умови, коли всі функції споживання (як замовлення споживачів, так і подача продукту в місцях розташування джерел) є константами. РОЗПОДІЛ ПОТОКІВ ІЗ ОПТИМАЛЬНИМ ПЕРЕРОЗПОДІЛОМ НАВАНТАЖЕННЯ ПОСТАЧАЛЬНИКІВ ПРОДУКТУ Будемо вважати тепер, що виділено деяку підмножину вершин ,NN ⊆ в яких величина id не є фіксованою. Таким чином, мінімізація функції (5) відбувається по всіх ,ijx ,),( Vji ∈ ,, Nidi ∈ зв’язаних обмеженнями (6), (7), за умови виконання (2). Як і раніше, поставимо у відповідність кожному i -му співвідношенню (6) множник Лагранжа iu , ,Ni∈ а співвідношенню (2) — .0u Розподіл ресурсів у розподільчих системах з оптимальним перерозподілом навантаження … Системні дослідження та інформаційні технології, 2013, № 4 43 Функцію Лагранжа представимо у такому вигляді: .)()()()( \ 0 ),( 0 0 ∑∑ ∑∫ ∈∈ ∈ −+−+ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ −−= NNi ii Vji Ni ii x ijijij duuduuuuxdttfL ij (14) Для того, щоб величини ijx , Vji ∈),( та id , ,Ni∈ були розв’язком за- дачі (5)–(7), та виконувалася умова (2), необхідно та достатньо, щоби знай- шлися такі числа iu , Ni∈ та 0u , що відповідні значення ijx та id , ,Ni∈ доставляли б мінімум функції Лагранжа за обмежень ,+− ≤≤ ijijij rxr .),( Vji ∈ Оскільки id , ,Ni∈ є тепер вільними, то 0uui = , ,Ni∈ тобто в тих ве- ршинах, де id не зафіксовані всі iu є однаковими. Це означає, що є справедливою наступна теорема. Теорема 2 [4]. Необхідною і достатньою умовою оптимальності пото- ків ijx , Vji ∈),( в задачі з недетермінованими витоками є існування таких множників Лагранжа ,iu ,\ NNi∈ для яких виконуються умови (11)–(13). Крім того 0uui = для ,Ni∈ причому величину 0u можна вибрати довільно. Перейдемо тепер до двоїстої задачі. Враховуючи (8), можемо записати: .)()()( \ 0 ),( 0, ∑∑ ∑ ∈∈ ∈ −+−+−= NNi ii Vji Ni iiijijij duuduuuuxL ϕ Знайдемо мінімум функції Лагранжа L по ijx . Якщо позначити міні- мальне значення функції ),( yxijϕ при +− ≤≤ ijijij rxr через )(yijϕ і врахува- ти, що 0uui = , ,Ni∈ то отримаємо вираз .)()( ),( \ 0∑ ∑ ∈ ∈ −+−=Φ Vji NNi iiijij duuuuϕ З теорії двоїстості, двоїста задача полягає в максимізації вгнутої функ- ції Φ по змінних iu , .\ NNi∈ З огляду на зроблені припущення функція )(yijϕ є неперервно диферен- ційовною, а згідно теореми про похідну від функції мінімуму [6], її похідна дорівнює значенню похідної від ),( yxijijϕ по ,y взятій у точці мінімуму :)(yxij .)( )( yx dy yd ij ij −= ϕ Звідси ).( )( ijij i ijij uux du uud −−= −ϕ Остаточно, похідна цільової функції двоїстої задачі дорівнює О.Є. Кірік ISSN 1681–6048 System Research & Information Technologies, 2013, № 4 44 .)()( i Ni jiji Ni ijij i duuxuux du d −−−−= Φ ∑∑ ∈∈ (15) Таким чином, ми звели вихідну задачу (5)–(7) до двоїстої задачі, що є задачею безумовної оптимізації Φmax . (16) Її цільова функція має неперервні похідні (15), які можна обчислити. Розв’я- завши задачу (16) та знайшовши оптимальні значення iu , ,\ NNi∈ можемо обчислити оптимальне значення потоків ,ijx Vji ∈),( з необхідних умов екстремуму (теорема 1). Для розв’язання задачі (16) з адитивно-сепарабельною цільовою функ- цією зручно застосувати метод покоординатного спуску, основна ідея якого полягає в тому, що на кожному кроці варіюється тільки одна змінна за умо- ви фіксації решти. Відмітимо, що число одновимірних задач, що розв’язуються на кожному кроці цього методу, буде визначатися кількістю елементів множини ,\ NN тобто дорівнюватиме числу вузлів мережі, за виключенням тих, у яких не задана величина споживання .id Розв’язок одновимірних задач iu Φmax зводиться до обертання на нуль похідної (15) цільової функції. Оскільки функ- ція Φ є вогнутою, то похідні монотонно спадають. Методи знаходження нуля неперервної монотонно спадаючої функції наведено, наприклад, у [3], [5]. МЕТОД УВ’ЯЗКИ МЕРЕЖІ Покажемо, як побудувати конкретні алгоритми розв’язання задачі (5)–(7) у випадках детермінованих та недетермінованих джерел на прикладі задачі поставки споживачам суміші продуктів із різних джерел. Але спочатку по- будуємо зручний алгоритм знаходження розподілу потоків, як розв’язок за- дачі (5), (6) без обмежень на пропускні здатності дуг. Цей розподіл потоків може служити для знаходження початкового наближення для розв’язання основної задачі. Кількість замкнених циклів мережі є значно меншою, ніж кількість ді- лянок мережі. Покажемо, як від задачі, розмірність якої визначається кількі- стю дуг мережі, перейти до задачі, розмірність якої є зіставною із кількістю замкнених циклів. Виберемо на зв’язному графі G довільним чином деяку вершину 0i . У методі розстановки позначок [4] ця вершина служить початковою при ви- діленні на графі максимального дерева. Як показано в [4], повний розв’язок системи (1) має вигляд , 1 , 0 ∑ = += g k Zijkijij k cxx ω (17) Розподіл ресурсів у розподільчих системах з оптимальним перерозподілом навантаження … Системні дослідження та інформаційні технології, 2013, № 4 45 , 00 \ ,, 0 ∑∑ ≠ ∈ ≠ ∈ += ik NNk kJij ik Nk kJijij ddx kk ωω (18) де 1+−= NVg , kJ — шляхи, що ведуть із початкової вершини 0i у інші вершини Nk∈ максимального дерева графа, а kZ — це замкнені циклічні шляхи, що обмежують скінчені області, на які граф G розбиває площину. У формулах (17)–(18) незалежними параметрами є kc , gk ,...,1= та id , .Ni∈ Підставимо вираз (17) в функцію (5). Цим задача з обмеженнями (5), (6), (2) зводиться до задачі безумовної мінімізації функції F за параметрами ,kc gk ,...,1= та id , .Ni∈ Похідні за незалежними параметрами знаходять- ся за формулами: ,)( ),( , ijij Vji Zij k xf dc dF k∑ ∈ = ω ,,...,1 gk = ,)( ),( , ijij Vji Jij k xf dd dF k∑ ∈ = ω ,Nk∈ (19) де ijx має вигляд (17). Сформулюємо тепер алгоритм розв’язання задачі (5), (6), (2) без обме- жень на пропускні здатності дуг. 1. Задаємо довільні початкові значення kc , gk ,...,1= та обираємо такі початкові значення kd , ,Nk∈ що задовольняють (2). 2. Знаходимо частковий розв’язок системи (1) за формулами . 00 \ ,, 0 ∑∑ ≠ ∈ ≠ ∈ += ik NNk kJij ik Nk kJijij ddx kk ωω 3. Мінімізуємо функцію, яку отримано в результаті підстановки (17) в (5) за незалежними параметрами kc , gk ,...,1= та kd , .Nk ∈ Оскільки фу- нкція F є опуклою і виведено формули (19) для обчислення її похідних, то для одновимірної мінімізації на кроці 3 алгоритму може бути застосовано довільний метод опуклого програмування. Повторюємо кроки 2–3 до отримання оптимальних значень незалежних параметрів. Знаючи оптимальні параметри kc , gk ,...,1= та kd , ,Nk ∈ зна- ходимо розподіл потоків за формулами (17), (18). Таким чином, у разі розв’язання задачі (5), (6), (2) без обмежень на пропускні здатності дуг із використанням співвідношень (17), (18) ми розв’язуємо лише \|\| Ng+ задач, що значно менше, ніж \|\\| NN . Алгоритм ув’язки мережі для випадку газотранспортної системи докла- дно розглянуто в [7]. В цьому підрозділі ми сформулювали метод ув’язки мережі, який може бути застосовано для розрахунку довільних розподільчих систем. О.Є. Кірік ISSN 1681–6048 System Research & Information Technologies, 2013, № 4 46 ЕКВІВАЛЕНТНІСТЬ ОПТИМІЗАЦІЙНОЇ ЗАДАЧІ З ІНТЕГРАЛЬНОЮ ЦІЛЬОВОЮ ФУНКЦІЄЮ СПІЛЬНОМУ РОЗВ’ЯЗАННЮ ОСНОВНИХ РІВНЯНЬ КІРХГОФА ДЛЯ МЕРЕЖ Покажемо тепер, що розв’язок оптимізаційної задачі (5), (6), (2) є дійсно ек- вівалентним спільному розв’язанню основних систем рівнянь для мереж. Теорема 3 [4]. Якщо J — шлях з вершини Na∈ у вершину ,Nb∈ то ∑ ∑ ∈ ∈ ⎪⎩ ⎪ ⎨ ⎧ ≠ =− =+ =− Vjij Vijj JjiJij bai bi ai ),(: ),(: ,, ,,для0 ,для1 ,для1 ωω .Ni∈ (20) Доведення. Розглянемо для початку простий шлях ),( baJ = , що скла- дається лише з однієї неорієнтованої дуги. Можливі два випадки: Vba ∈),( або .),( Vab ∈ Якщо ,,bai ≠ то всі доданки в лівій частині дорівнюють ну- лю, і (20) виконується. Якщо ,ai = то в лівій частині (20) тільки один до- данок 1, =Jabω є відмінним від нуля, і тому ліва частина дорівнює одиниці. Якщо ж ,),( Vab ∈ то ,1, −=Jbaω решта доданків дорівнює нулю, і (20) зно- ву виконується. Аналогічно, для випадку .bi = Для загального шляху ,),...,,( 21 mjjjJ = ,1 mjj ≠ результат отримає- мо, якщо врахувати, що крім початкової 1j та кінцевої mj вершин, решта вершин kj входять до двох елементарних шляхів ),( 1 kk jj − та ),( 1+kk jj перший раз як кінцева, другий — як початкова. Теорему доведено. Розглянемо застосування теореми 2 щодо необхідних умов екстремуму за відсутності обмежень (7) на пропускні здатності дуг. За цією теоремою, для того, аби потоки ,ijx Vji ∈),( в задачі (5), (6), (2) були оптимальними, необхідно і достатньо, щоби існували такі числа iu , ,Ni∈ що 0uui = для ,Ni∈ ,)( ijijij uuxf −= .),( Vji ∈ (21) Візьмемо довільний шлях ),...,,( 21 mjjjJ = , що з’єднує вершини Nba ∈, тобто aj =1 та .bjm = Нехай дуга ),(),( 1+= kk jjji належить цьо- му шляху. Тоді 1, =Jijω , ijijij uuxf −=)( . Якщо ,),(),( 1 kk jjji += то ,1, −=Jijω .)( jiijij uuxf −= Таким чином, завжди ijijijJij uuxf −=)(,ω . Тому для довільного шляху J ,)( ),( , ab Jji ijijJij uuxf −=∑ ∈ ω де a та b — початкова та кінцева вершини шляху .J Зокрема ,0)( ),( , =∑ ∈Jji ijijJij xfω (22) якщо J — цикл або a та b належать множині .N Розподіл ресурсів у розподільчих системах з оптимальним перерозподілом навантаження … Системні дослідження та інформаційні технології, 2013, № 4 47 Теорема 4 [4]. Умови (21) є необхідними та достатніми для оптималь- ності потоку ijx Vji ∈),( в задачі мінімізації функції ∑ ∫ ∈ = Vji x ij ij dttfF ),( 0 )( без обмежень. Доведення. Необхідність виконання цих умов доведено вище. Доведе- мо достатність. Візьмемо довільну вершину Na∈ та покладемо 0uua = , де 0u — довільне. Для решти вершин ab ≠ покладемо += ab uu ∑ ∈ + Jji ijijJij xf ),( , ,)(ω де J — шлях, що з’єднує вершини a та .b Покажемо, що величини bu не залежать від вибору шляху J та виконуються співвід- ношення (21). Дійсно, якщо ,Nb∈ то за припущенням 0)( ),( , =∑ ∈Jji ijijJij xfω та 0uub = . Тепер нехай NNb \∈ та ),...,,( 211 mjjjJ = — шлях з aj =1 в .bjm = Нехай ),...,,( 212 niiiJ = — інший шлях з ai =1 в bin = . Оскільки початкова та кінцева вершини цих шляхів співпадають, то існує принаймні один цикл, що утворюється компонентами цих шляхів. Не обмежуючи загальності, бу- демо вважати, що не співпадаючі компоненти шляхів 1J та 2J утворюють єдиний цикл. Нехай ∑ ∈ += 1 1 ),( , 1 )( Jji ijijJijab xfuu ω , .)( 2 2 ),( , 2 ∑ ∈ += Jji ijijJijab xfuu ω Якщо взяти різницю цих величин, то отримаємо ,0)()()( ),( , ),( ),( ,, 21 1 2 21 ∑∑ ∑ ∈∈ ∈ ==−=− Zji ijijZij Jji Jji ijijJijijijJijbb xfxfxfuu ωωω де Z — цикл, що складається з неспівпадаючих частин шляхів 1J та 2J . Таким чином, числа bu не залежать від вибору шляху. Нехай є дуга ),( ji , що з’єднує вершини i та .j Нехай J — шлях з a в i , а J — шлях із a в ,j що складається зі шляху J та доданої до нього дуги ),( ji . Тоді зрозуміло, що ∑∑ ∈∈ −−+=− Jji ijijJija Jji ijijJijaji xfuxfuuu ),( , ),( , .)()( ωω Оскільки за побудовою ),( jiJJ ∪= , то приходимо до співвідношення .)()()( ),( , ),( , ∑∑ ∈∈ += Jji ijijijijJij Jji ijijJij xfxfxf ωω Отже, ,)( ijijij xfuu =− що й потрібно було довести. Наслідок. Спільний розв’язок систем (1), (2) та (22) існує та реалізує єдиний мінімум функції (5) за зв’язків (6), (2). О.Є. Кірік ISSN 1681–6048 System Research & Information Technologies, 2013, № 4 48 ЗАДАЧА ПОСТАВКИ СПОЖИВАЧАМ СУМІШІ ПРОДУКТІВ У ПЕВНИХ ПРОПОРЦІЯХ Нехай у вершинах Ni∈ мережі G розташовані споживачі та постачальники продукту (джерела води, родовища газу, перекачувальні станції тощо), при- чому id , Ni∈ — питома кількість продукту, що споживається або подаєть- ся в мережу у i -му вузлі. Припустимо, що у вершинах Ni∈ розташовані витоки, відносно яких висунуто певні умови, наприклад, абсолютні величини подачі продукту з цих джерел заздалегідь невідомі, але потрібно, щоб витримувалися певні пропорції. Ці пропорції можуть визначатися ціновими показниками або по- казниками якості різних постачальників однорідного продукту. Для зручності будемо вважати, що при нумерації вузлів мережі недетер- міновані вузли перенумеровані першими. Якщо позначити ii dy = ,Ni∈ причому ,yky ii = ,\|\|,...,1 Ni = ,1 \|\| 1 =∑ = N i ik то умову матеріального балансу для цієї задачі можна переписати у такому вигляді .0 \ \|\| 1 =+ ∑∑ ∈= NNi i N i i dyk Звідси отримуємо . \ ∑ ∈ −= NNi idy Остаточно ∑ ∈ −= NNi iii dky \ , .Ni∈ (23) Оскільки всі величини id , NNi \∈ за умовою задачі є константами, співвідношення (23) означає, що у випадку, коли чітко визначені пропорції продукту, що повинен подаватися в мережу із заздалегідь визначених дже- рел, задача зводиться до повністю детермінованого випадку, тобто до задачі (5)–(7) з фіксованими значеннями функцій споживання id . Сформулюємо покроковий алгоритм розв’язання задачі (16) для випад- ку детермінованих джерел. Алгоритм розв’язання двоїстої задачі без обмежень 1. Обираємо довільні початкові значення iu , .Ni∈ Початкові зна- чення двоїстих змінних iu , Ni∈ можуть бути обчислені за формулами ),( ijijij xfuu += ,),( Vji ∈ де потоки ijx , Vji ∈),( знаходяться у процесі розв’язанні задачі (5), (6) без обмежень на пропускні здатності дуг. Алго- ритм розв’язання цієї задачі сформульовано вище. 2. Розв’язуємо задачу знаходження оптимальних значень iu , Ni∈ максимізуючи функцію Φ методом покоординатного спуску. Розподіл ресурсів у розподільчих системах з оптимальним перерозподілом навантаження … Системні дослідження та інформаційні технології, 2013, № 4 49 3. Знаючи оптимальні значення ,iu Ni∈ та використовуючи необхідні умови екстремуму, сформульовані у теоремі 1, повертаємося до вихідних змінних ijx , ,),( Vji ∈ що і дає розподіл потоків, який є розв’язком задачі (5)–(7). ПОСТАВКА СПОЖИВАЧАМ СУМІШІ ПРОДУКТІВ ПЕВНОЇ ЯКОСТІ Розглянемо випадок, коли важливо, щоб подача продукту з певних джерел не перевищувала деяких наперед заданих меж. Ці умови можуть виникнути, коли продукти з таких джерел відрізняються, наприклад, нижчою якістю або високою ціною, і подачу їх в мережу треба обмежити. Сформулюємо задачу функціонування мережі за умови мінімізації експлуа- таційних витрат та обмеження подачі у мережу продукту з певних джерел. Потрібно мінімізувати вираз ∑ ∫ ∈Vji x ij ij dttf ),( 0 )( (24) за обмежень ( )( ) ,\, ,: ,: NNidxx Vjij Vijj ijiij ∈=−∑ ∑ ∈ ∈ (25) ,, ),(: ),(: Niyxx Vjij Vijj ijiij ∈=−∑ ∑ ∈ ∈ (26) ,),(, Vjirxr ijijij ∈≤≤ +− (27) +− ≤≤ iii dyd .Ni∈ (28) Сумарний попит споживачів має знаходитися у балансі з подачею про- дукту в мережу 0 \ =+ ∑∑ ∈∈ Ni i NNi i yd . (29) Випишемо для задачі (24)–(29) функцію Лагранжа, використовуючи вве- дені раніше позначення. Кожному i -му співвідношенню (25, 26) ставиться у відповідність множник Лагранжа iu , ,Ni∈ а співвідношенню (29) — 0u . + ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ −−+= ∑ ∫ ∑ ∑ ∑ ∈ ∈ ∈ ∈Vji x NNi Vjij Vijj ijiijiij ij dxxudttfL ),( 0 \ ),(: ),(: )( =++ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ −−+ ∑∑ ∑ ∑ ∈∈ ∈ ∈ )(0 ),(: ),(: Ni ii Ni Vjij Vijj ijiiji dyuyxxu ∑ ∑∑∫ ∈ ∈∈ −+−+−−= Vji NNi ii Ni ii x ijijij duuuuyuuxdttf ij ),( \ 00 0 )()(])()([ . (30) Як сказано у теоремі 2, для того, щоб величини ijx , Vji ∈),( та ,iy ,Ni∈ були розв’язком задачі (24)–(29), необхідно та достатньо, щоби О.Є. Кірік ISSN 1681–6048 System Research & Information Technologies, 2013, № 4 50 знайшлися такі числа ,iu Ni∈ , та 0u , що відповідні значення ijx та iy , ,Ni∈ доставляли б мінімум функції Лагранжа за обмежень ,+− ≤≤ ijijij rxr ,),( Vji ∈ ,+− ≤≤ iii dyd .Ni∈ Точка ijx є точкою мінімуму функції ∫ −− x ijij uuxdttf 0 ][)( за обмежень ijij rxr +− ≤≤ . Ми позначили мінімальне значення цієї функції через )( ijij uu −ϕ . Точка iy є точкою мінімуму функції ∑ ∈ − Ni iuuy )( 0 за обмежень +− ≤≤ ii dyd , .Ni∈ Позначимо мінімальне значення цієї функції через )( 0 ii uu −γ . Випишемо вираз для цільової функції двоїстої задачі: ∑ ∑∑ ∈ ∈∈ −+−+−=Ψ Vji NNi ii Ni iiijij duuuuuu ),( \ 00 )()()( γϕ . Сформулюємо для задачі (24)–(29) необхідні умови екстремуму. Теорема 5. Для того, щоб потоки ijx , Vji ∈),( продукту вздовж мережі за умови обмеження продуктивності певних джерел iy , Ni∈ були оптима- льними, необхідно і достатньо, щоб знайшлися такі iu , Ni∈ та 0u , для яких виконуються умови теореми 2 і додаткові умови для вузлів :Ni∈ якщо ,−= ii dy то 0uui < ; якщо ,+= ii dy то 0uui > ; якщо ,+− << iii dyd то 0uui = . В останньому випадку, якщо для деяких оптимальних значень двоїстих змінних виконується співвідношення 0uui = , умови теореми 5 не визнача- ють відповідне значення прямих змінних .iy Для розв’язання проблеми визначення розв’язку вихідної задачі на ос- нові розв’язку двоїстої задачі [8] можна використати прийом корекції ці- льової функції (24) шляхом додавання до неї певного «регулюючого» члена: ,)2/)((( 2−+ ∈ −−∑ iii Ni i ddyε де iε — параметри квадратичної корекції, 0>εi . Це забезпечує неперервну диференційованість функції Ψ та однознач- ність визначення )(),( uyux iij для довільних .u Алгоритм розподілу потоків із оптимізацією навантаження недетермі- нованих джерел постачання продукту. 1. Вибираємо довільні початкові значення ,iu Ni∈ та .0u Початкові значення iu можуть бути обрані як розв’язок двоїстої задачі до задачі роз- поділу потоків із фіксованою продуктивністю джерел (витоків). 2. Розв’язуємо задачу знаходження оптимальних значень ,iu Ni∈ ма- ксимізуючи функцію .Ψ Розподіл ресурсів у розподільчих системах з оптимальним перерозподілом навантаження … Системні дослідження та інформаційні технології, 2013, № 4 51 3. Знаючи оптимальні значення ,iu Ni∈ та використовуючи необхідні умови екстремуму, повертаємося до вихідних змінних ,ijx ,),( Vji ∈ ,iy Ni∈ що дає розподіл потоків та продуктивність недетермінованих джерел, які є розв‘язком задачі (24)–(29). ВИСНОВКИ Розглянуто задачу розподілу потоків, причому подача продукту із заздале- гідь визначеного переліку джерел підлягає оптимізації за умови додаткових обмежень. Модель оптимізації функціонування розподільчої системи з обмежен- ням подачі продукту із наперед визначених витоків є узагальненням моделі розподілу потоків для мережі з нефіксованими вузловими параметрами. До- датково введені обмеження відображають технічні або економічні характе- ристики цих витоків. Задача розподілу потоків з подачею продукту з різних витоків у певних пропорціях зводиться до повністю детермінованого випадку. Перевагою побудованих алгоритмів є перехід до набору задач меншої розмірності в процесі розрахунків допустимих потоків та врахування адитивної сепарабельності цільових функцій мережевих задач, що є важ- ливим з огляду на дуже великі розмірності таких задач. У розглянутих задачах розподілу потоків додаткові обмеження накла- даються на вузлові параметри. У випадку, якщо потрібно витримати збере- ження пропорцій суміші продукту вздовж ділянок мережі у задачу потрібно вводити додаткові, часом нелінійні, обмеження і це може стати предметом подальших досліджень. ЛІТЕРАТУРА 1. Меренков А.П., Хасилев В.Я. Теория гидравлических цепей. — М.: Наука, 1985. — 235 с. 2. Системные исследования в энергетике / под ред. чл.-кор. РАН Н.И. Воропая. — Новосибирск.: «НАУКА», 2010. — 686 c. 3. Пшеничный Б.Н., Кирик Е.Е. Алгоритмы оптимального распределения потоков в сетях // Кибернетика и системный анализ. — 1993. — № 4. — С. 29–39. 4. Пшеничный Б.Н., Кирик Е.Е. Методы нелинейного программирования и потоки в сетях // Кибернетика и системный анализ. — 1994. — № 6. — С. 67–77. 5. Кирик Е.Е., Пшеничный Б.Н. Теория и методы расчета сетей. // Обозрение при- кладной и промышленной математики. — 1995. — т. 2, вып.1. — С. 49–69. 6. Пшеничный Б.Н. Выпуклый анализ и экстремальные задачи. — М.: Наука, 1980. — 320 с. 7. Кірік О.Є. Розподіл потоків в мережах складної кільцевої топології // Наукові вісті НТУУ «КПІ». — 2009. — № 2. — С. 18–26. 8. Шор Н.З. Методы минимизации недифференцируемых функций и их прило- жения. — Киев: Наук. думка, 1979. — 199 с. Надійшла 06.03.2013
id	nasplib_isofts_kiev_ua-123456789-85133
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn	1681–6048
language	Ukrainian
last_indexed	2025-12-07T18:22:50Z
publishDate	2013
publisher	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
record_format	dspace
spelling	Кірік, О.Є. 2015-07-19T16:33:47Z 2015-07-19T16:33:47Z 2013 Розподіл ресурсів у розподільчих системах з оптимальним перерозподілом навантаження постачальників продукту / О.Є. Кірік // Системні дослідження та інформаційні технології. — 2013. — № 4. — С. 38-51. — Бібліогр.: 8 назв. — укр. 1681–6048 https://nasplib.isofts.kiev.ua/handle/123456789/85133 519.8 Побудовано та досліджено математичні моделі розподілу потоків обмежених ресурсів у енергетичних системах. Розроблено методи розв’язання задач розподілу потоків, що базуються на поєднанні екстремального підходу до розрахунку мереж та спільного розв’язку двох основних систем Кірхгофа. Запропоновано ефективний алгоритм ув’язки мережі для знаходження початкового наближення до розв’язку більш складної нелінійної транспортної задачі. Проаналізовано проблему оптимального перерозподілу навантаження постачальників продукту. Як приклад розглянуто задачу поставки споживачам суміші речовини у певних пропорціях або з певними кількісними обмеженнями. Завдяки загальній постановці задачі запропоновані моделі, методи та алгоритми можуть використовуватися для розрахунку різнотипних розподільчих мереж та трубопроводів. Построены и исследованы математические модели распределения потоков ограниченных ресурсов в энергетических системах. Разработаны методы решения задач распределения потоков, базирующиеся на сочетании экстремального подхода к расчету сетей и совместного решения двух основных систем Кирхгофа. Предложен эффективный алгоритм увязки сети для нахождения начального приближения к решению более сложной нелинейной транспортной задачи. Проанализирована проблема оптимального перераспределения нагрузки поставщиков продукта. В качестве примера рассмотрена задача поставки потребителям смеси вещества в определенных пропорциях или с определенными количественными ограничениями. Благодаря общей постановке задачи предложенные модели, методы и алгоритмы могут использоваться для расчета разнотипных распределительных сетей и трубопроводов. Mathematical models of flow distribution of scarce resources in energy systems are constructed and investigated. Methods for solving problems of flow distribution, based on a combination of extreme approach to the calculation of nets and joint solution of the two main systems of Kirchhoff are developed. An efficient network link algorithm to find an initial approximation to the solution of complex nonlinear transportation problem is proposed. The problem of optimal redistribution of load of product suppliers is analyzed. As an example the problem of delivery to consumers the mixture of substance in certain proportions or with certain quantitative restrictions is considered. Thanks to the general formulation of the problem the proposed models, methods and algorithms can be used to calculate the different types of distribution of the networks and pipelines. uk Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України Системні дослідження та інформаційні технології Методи оптимізації, оптимальне управління і теорія ігор Розподіл ресурсів у розподільчих системах з оптимальним перерозподілом навантаження постачальників продукту Распределение ресурсов в распределительных системах с оптимальным перераспределением нагрузки поставщиков продукта Allocation of resources in distribution systems with optimal redistribution of load of the product suppliers Article published earlier
spellingShingle	Розподіл ресурсів у розподільчих системах з оптимальним перерозподілом навантаження постачальників продукту Кірік, О.Є. Методи оптимізації, оптимальне управління і теорія ігор
title	Розподіл ресурсів у розподільчих системах з оптимальним перерозподілом навантаження постачальників продукту
title_alt	Распределение ресурсов в распределительных системах с оптимальным перераспределением нагрузки поставщиков продукта Allocation of resources in distribution systems with optimal redistribution of load of the product suppliers
title_full	Розподіл ресурсів у розподільчих системах з оптимальним перерозподілом навантаження постачальників продукту
title_fullStr	Розподіл ресурсів у розподільчих системах з оптимальним перерозподілом навантаження постачальників продукту
title_full_unstemmed	Розподіл ресурсів у розподільчих системах з оптимальним перерозподілом навантаження постачальників продукту
title_short	Розподіл ресурсів у розподільчих системах з оптимальним перерозподілом навантаження постачальників продукту
title_sort	розподіл ресурсів у розподільчих системах з оптимальним перерозподілом навантаження постачальників продукту
topic	Методи оптимізації, оптимальне управління і теорія ігор
topic_facet	Методи оптимізації, оптимальне управління і теорія ігор
url	https://nasplib.isofts.kiev.ua/handle/123456789/85133
work_keys_str_mv	AT kíríkoê rozpodílresursívurozpodílʹčihsistemahzoptimalʹnimpererozpodílomnavantažennâpostačalʹnikívproduktu AT kíríkoê raspredelenieresursovvraspredelitelʹnyhsistemahsoptimalʹnympereraspredeleniemnagruzkipostavŝikovprodukta AT kíríkoê allocationofresourcesindistributionsystemswithoptimalredistributionofloadoftheproductsuppliers

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

Репозитарії

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