Проблема існування розв’язку в задачах розподілу потоків

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2011
1. Verfasser:	Кірік, О.Є.
Format:	Artikel
Sprache:	Ukrainian
Veröffentlicht:	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України 2011
Schriftenreihe:	Системні дослідження та інформаційні технології
Schlagworte:	Математичні методи, моделі, проблеми і технології дослідження складних систем
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/50133
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Проблема існування розв’язку в задачах розподілу потоків / О.Є Кірік // Систем. дослідж. та інформ. технології. — 2011. — № 4. — С. 119-128. — Бібліогр.: 7 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-50133
record_format	dspace
spelling	irk-123456789-501332013-10-11T12:11:37Z Проблема існування розв’язку в задачах розподілу потоків Кірік, О.Є. Математичні методи, моделі, проблеми і технології дослідження складних систем Досліджено питання існування розв’язку в задачі розподілу потоків в енергетичних мережах. Сформульовано алгоритм апріорного визначення сумісності обмежень такої задачі. Запропоновано модель з системою рівнянь неперервності, побудованої таким чином, щоб забезпечити існування допустимого розв’язку за умови зведення до мінімуму порушень замовлень споживачів. Исследованы вопросы существования решения в задаче распределения потоков в энергетических сетях. Сформулирован алгоритм априорного определения совместности ограничений такой задачи. Предложена модель с системой уравнений непрерывности, построенной таким образом, чтобы обеспечить существование допустимого решения при условии сведения к минимуму нарушений заказов потребителей. Questions of the existence of a solution for the problem of flow distribution in power networks are investigated. The algorithm of a priori definition of restrictions compatibility of this problem is formulated. A model with the system of equations of continuity, built in such a way as to ensure the existence of a feasible solution provided to minimize disruption customer orders is constructed. 2011 Article Проблема існування розв’язку в задачах розподілу потоків / О.Є Кірік // Систем. дослідж. та інформ. технології. — 2011. — № 4. — С. 119-128. — Бібліогр.: 7 назв. — укр. 1681–6048 http://dspace.nbuv.gov.ua/handle/123456789/50133 519.8 uk Системні дослідження та інформаційні технології Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Математичні методи, моделі, проблеми і технології дослідження складних систем Математичні методи, моделі, проблеми і технології дослідження складних систем
spellingShingle	Математичні методи, моделі, проблеми і технології дослідження складних систем Математичні методи, моделі, проблеми і технології дослідження складних систем Кірік, О.Є. Проблема існування розв’язку в задачах розподілу потоків Системні дослідження та інформаційні технології
description	Досліджено питання існування розв’язку в задачі розподілу потоків в енергетичних мережах. Сформульовано алгоритм апріорного визначення сумісності обмежень такої задачі. Запропоновано модель з системою рівнянь неперервності, побудованої таким чином, щоб забезпечити існування допустимого розв’язку за умови зведення до мінімуму порушень замовлень споживачів.
format	Article
author	Кірік, О.Є.
author_facet	Кірік, О.Є.
author_sort	Кірік, О.Є.
title	Проблема існування розв’язку в задачах розподілу потоків
title_short	Проблема існування розв’язку в задачах розподілу потоків
title_full	Проблема існування розв’язку в задачах розподілу потоків
title_fullStr	Проблема існування розв’язку в задачах розподілу потоків
title_full_unstemmed	Проблема існування розв’язку в задачах розподілу потоків
title_sort	проблема існування розв’язку в задачах розподілу потоків
publisher	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
publishDate	2011
topic_facet	Математичні методи, моделі, проблеми і технології дослідження складних систем
url	http://dspace.nbuv.gov.ua/handle/123456789/50133
citation_txt	Проблема існування розв’язку в задачах розподілу потоків / О.Є Кірік // Систем. дослідж. та інформ. технології. — 2011. — № 4. — С. 119-128. — Бібліогр.: 7 назв. — укр.
series	Системні дослідження та інформаційні технології
work_keys_str_mv	AT kíríkoê problemaísnuvannârozvâzkuvzadačahrozpodílupotokív
first_indexed	2025-07-04T11:37:20Z
last_indexed	2025-07-04T11:37:20Z
_version_	1836716173769572352
fulltext	© О.Є. Кірік, 2011 Системні дослідження та інформаційні технології, 2011, № 4 119 УДК 519.8 ПРОБЛЕМА ІСНУВАННЯ РОЗВ’ЯЗКУ В ЗАДАЧАХ РОЗПОДІЛУ ПОТОКІВ О.Є. КІРІК Досліджено питання існування розв’язку в задачі розподілу потоків в енерге- тичних мережах. Сформульовано алгоритм апріорного визначення сумісності обмежень такої задачі. Запропоновано модель з системою рівнянь непе- рервності, побудованої таким чином, щоб забезпечити існування допустимого розв’язку за умови зведення до мінімуму порушень замовлень споживачів. ВСТУП Розподіл потоків у розподільчих мережах — це складна задача, математична модель якої може містити до кількох десятків тисяч змінних. При постанов- ці прикладних задач оптимізації розподілу потоків у таких системах доціль- но спочатку дослідити питання існування розв’язку, аби за необхідності га- рантувати розв’язність задачі. Перша частина роботи присвячена дослідженням існування розв’язків задач розподілу потоків, що базуються на теоремі про максимальний потік і метод розстановки позначок [1]. Наведені викладки дозволяють заздале- гідь, до здійснення процесу оптимізації, визначити, чи є сформульована за- дача розв’язною. У випадку дослідження реальних мереж визначення відсут- ності розв’язку конкретної задачі є недостатнім. Бажано певним чином переформулювати задачу, гарантувавши сумісність системи обмежень. У другій частині роботи запропоновано модель розподілу потоків із системою рівнянь неперервності, яку побудовано таким чином, щоб забез- печити існування допустимого розв’язку. Оскільки технологічна пропускна здатність ділянок мережі є величиною фіксованою, то корегувати можна тільки замовлення споживачів та подачу речовини з витоків. При цьому по- рушення замовлень споживачів має бути зведене до мінімуму. Мінімізовані похибки вектора споживання отримуємо в явному вигляді, що дає простір для консультацій з експертами та є важливим з огляду на прикладну спря- мованість задач, що досліджуються. Мета роботи — дослідження питання існування розв’язку для оптимі- заційної задачі зі структурою обмежень, характерною для задач розподілу потоків, побудова алгоритму визначення сумісності такої задачі, а також побудова мережевої моделі, що гарантує існування розв’язку в задачі розпо- ділу потоків. РІВНЯННЯ ДЛЯ ВИЗНАЧЕННЯ ДОПУСТИМОГО ПОТОКУ Розподільчу мережу топологічно можна представити як зв’язний плоский граф [2]. Позначимо його ),,( VNG = де N — множина вершин, V — мно- О.Є. Кірік ISSN 1681–6048 System Research & Information Technologies, 2011, № 4 120 жина дуг, що їх з’єднують. Кожному Vv∈ співставлена упорядкована пара вершин ),( ji , ,, Nji ∈ що є, відповідно, початком і кінцем цієї дуги. Якщо споживачі розташовані у вершинах графу і для кожної вершини i відоме споживання, то кожній дузі графу v може бути приписаний деякий потік, що забезпечує доставку відповідного продукту споживачам. Нехай )(id — функція споживання, визначена у вершинах графу, ),( jix — функція потоку, визначена на дугах графу G . Розглянемо умови, що накладаються на ці функції в класичній задачі розподілу потоків. Основною системою рівнянь є система, що відображає закон збережен- ня речовини у вершинах графу: ( )( ) .,)(),(),( ,: ,: Niidjixjix Vjij Vijj ∈=−∑ ∑ ∈ ∈ (1) Система рівнянь (1) демонструє той факт, що кількість речовини, що втікає у вершину i мінус кількість, що витікає з цієї вершини, має дорівню- вати споживанню в цій вершині. Як випливає з рівнянь (1), величини )(id мають додатне значення у вузлах — «джерелах» і від’ємне — у вузлах, де розташовані споживачі. Виконання співвідношень (1) гарантує задоволення всіх споживачів. Надалі зручно використовувати такі позначення. Якщо K та I під- множини множини ,N то символом ),( IK позначаємо множину всіх дуг, що ведуть із Kk∈ в Ij∈ . Покладемо ∑ ∈ = Ki idKd )()( для всіх ;NK ⊆ ∑ ∈ = Ki idKd )()( 22 для всіх ;NK ⊆ ∑ ∈ ∈ = Vji Kj jixKix ),( ),(),( для всіх NK ⊆ ; ∑∑ ∈ ∈ ∈∈ == ),(),( ),( , ),(),(),( KIji Vji KjIi jixjixKIx для всіх NI ⊆ , NK ⊆ . З огляду на введені позначення система (1) буде мати вигляд: .),(),(),( NiidiNxNix ∈=− (2) Теорема 1. Для розв’язності системи (2) необхідно, аби виконувалося співвідношення .0)( =Nd (3) Для доведення сумуємо (2) по Ni∈ та отримуємо: )(),(),( NdNNxNNx =− . Умова (3) є умовою збалансованості системи (2). У реальних розподільчих мережах важливою умовою є задоволення технологічних обмежень на пропускну здатність ділянок мережі (дуг графу). )()()( vrvxvr +− ≤≤ , (4) де −)(vr та +)(vr — задані числа, що називаються мінімальною та максима- льною пропускною здатністю дуги. Проблема існування розв’язку в задачах розподілу потоків Системні дослідження та інформаційні технології, 2011, № 4 121 Дослідимо тепер проблему існування розв’язку системи (2) за обме- жень (4). Для цього розглянемо теорему про максимальний потік та мініма- льний розріз. ЗАДАЧА ПРО МАКСИМАЛЬНИЙ ПОТІК Сформулюємо задачу знаходження максимального потоку. Припустимо, що 0)( =− vr для всіх Vv∈ . Нехай у графі G виділено дві вершини ,, Nts ∈ що називаються витоком та стоком і виконуються такі співвідношення: ,),(),( qsNxNsx =− ,,,0),(),( tsiiNxNix ≠=− (5) .),(),( qtNxNtx −=− Зазначимо, що ця система має в якості частинного розв’язку — нульо- вий (при цьому 0=q ). Задача пошуку максимального потоку полягає в знаходженні qmax (6) за обмежень (5). Нехай ),( KK — підмножина дуг ),( ji графу G , де ,NK ⊂ ,\ KNK = Ki∈ , Kj∈ . Розрізом графу G , що відділяє вершини s та ,t називатимемо таку підмножину дуг ),( KK , що Ks∈ , Kt∈ . Для цього розрізу ),( KK може бути визначена його пропускна здатність, що дорівнює величині ),( KKr + , тобто сумі пропускних здатностей дуг з ),( KK . Якщо ),( KK — розріз, то з (5), сумуючи по Ki∈ , отримаємо: qKNxNKx =− ),(),( . Враховуючи, що NKK =∪ , розпишемо ліву частину цієї рівності: qKKxKKxKKxKKxKKKxKKKx =−−+=∪−∪ ),(),(),(),(),(),( . Звідси qKKxKKx =− ),(),( . (7) За припущенням 0)( =− vr для всіх ,Vv∈ тобто 0),( ≥KKx . Оскільки ),(),( KKrKKx +≤ , то заміняючи в лівій частині (7) перше число на більше, а друге на менше, отримаємо: qKKr ≥+ ),( . Цей результат може бути сформульований таким чином. Теорема 2. Величина q довільного потоку з витоку s у стік t не може перевищувати пропускну здатність довільного розрізу. Мінімальним розрізом називаємо розріз з мінімальною пропускною здатністю. Тепер може бути сформульована основна теорема. Теорема 3. Для довільної мережі максимальна величина потоку з s у t дорівнює пропускній здатності мінімального розрізу. О.Є. Кірік ISSN 1681–6048 System Research & Information Technologies, 2011, № 4 122 При цьому для довільного мінімального розрізу дуги з ),( KK є на- сиченими максимальним потоком, тобто ),(),()( KKvvrvx ∈= + , ,0)( =vx ),( KKv∈ . Доведення. З огляду на теорему 2 достатньо показати, що існують по- тік x та розріз ),( KK , для яких величина потоку та пропускна здатність розрізу є рівними. Оскільки нульовий потік задовольняє всім обмеженням задачі про мак- симальний потік, то задача лінійного програмування (6), (5) є сумісною. Усі розв’язки задачі є обмеженими. Лінійна функція досягає на замкненій об- меженій множині максимального значення, як наслідок, існує і максималь- ний потік. Опишемо процедуру розстановки позначок для побудови допустимого та максимального потоків. Попередньо введемо деякі позначення. Послідовність Njjjj km ∈),,...,,( 21 , називається шляхом, що з’єднує вершини 1j та mj , якщо ,),( 1 Vjj kk ∈+ 1,...,1 −= mk , li jj ≠ , li ≠ . Нехай шлях =J ),...,,( 21 mjjj з’єднує вершини aj =1 , bjm = . Покладемо випадках.інших всіх у ,1,...,1,),(,,: якщо ,1,...,1,),(,,: якщо 0 ,1 ,1 ),( 11 11 −=∈==∃ −=∈==∃ ⎪ ⎩ ⎪ ⎨ ⎧ − + = ++ ++ mkVjjjjjik mkVjjjjjik ji kkkk kkkk Jω Для кожного шляху J функція Jω визначає вектор, розмірність якого співпадає з числом дуг графу G , тобто V . Між векторами Jω та шляхами в графі G існує взаємно однозначна відповідність. Якщо J — шлях з вершини Na∈ у вершину Nb∈ , то ⎪ ⎩ ⎪ ⎨ ⎧ ≠ =− =+ =− .,для0 ,для1 ,для1 ),(),( bai bi ai iNNi JJ ωω ,Ni∈ (8) Для обґрунтування цього співвідношення достатньо розглянути прос- тий шлях ),( baJ = , що складається лише з однієї неорієнтованої дуги. Можливі два випадки: Vba ∈),( або .),( Vab ∈ Якщо bai ,≠ , то всі доданки в лівій частині дорівнюють нулю, і (11) виконується. Якщо ai = , то в лівій частині (8) тільки один доданок 1),( =baJω є відмінним від нуля, і тому ліва частина дорівнює одиниці. Якщо ж ,),( Vab ∈ то 1),( −=abJω , решта до- данків дорівнюють нулю, і (8) знову виконується. Аналогічно для випадку .bi = Для загального шляху ),...,,( 21 mjjjJ = , mjj ≠1 , результат визнача- ється з того факту, що ∑ − = += 1 1 1),( m k kkJ jjωω і крім початкової 1j та кінцевої mj вершин, решта вершин ky входять у два елементарні шляхи ),( 1 kk jj − та ),( 1+kk jj один раз як кінцева, другий — як початкова. Проблема існування розв’язку в задачах розподілу потоків Системні дослідження та інформаційні технології, 2011, № 4 123 Якщо J-цикл, то 0),(),( =− iNNi JJ ωω для всіх Ni∈ . Цей факт випли- ває із попереднього з врахуванням того, тепер усі вершини є початковими для одного елементарного шляху та кінцевими для іншого. Нехай ),(vx Vv∈ — максимальний потік. Система позначок графу бу- дується таким чином. Вершину s помічаємо парою ),( s∞+ . На кожному кроці вершина j отримує позначку )),(( ijα в одному з двох випадків. Якщо ,),( Vji ∈ i — позначена вершина, а j — непозначена вершина та ),(),( jixjir >+ , то )}(),,(),({min)( ijixjirj αα −= + . Якщо Vij ∈),( та 0),( >jix , то )}(),,({min)( ijixj αα = . Процес розстановки позначок є скінченим, оскільки жодна вершина не помічається двічі. Припустимо, що ми на одному з етапів помітили вершину t і перша компонента цієї позначки є 0>α . Тоді, повертаючись назад по іншим ком- понентам позначок, обов’язково прийдемо до вершини ,s з якої починався цей процес. Таким чином утворюється шлях від вершини s до вершини t . Позначимо його .J Нехай новий потік з s у t дорівнює )()()( vtvx Jωα+ . За теоремою 3 він задовольняє всім обмеженням (5). Отже, потік збільшився на величину )(tα . Таким чином, якщо вдалося позначити вершину ,t то величину потоку можна збільшити. Але оскільки, за припущенням, потік )(vx був максима- льним, це приводить до суперечності. Ми не можемо позначити вершину t , тому процес позначок зупиниться до того, як відбудеться помітка вершини t . Позначимо через K множину позначених вершин і розглянемо дуги ),( KK та ),( KK . Оскільки неможливо з множини K позначити жодну вершину з K , це означає, що )()( vrvx += для всіх ),( KKv∈ . Так само 0)( =vx для всіх ),( KKv∈ . Тоді з (7) отримаємо, що qKKr =+ ),( . Показано, що пропускна здатність деякого розрізу дорівнює потужності максимального потоку. Звідси випливає, що: • цей розріз має мінімальну пропускну здатність; • якщо взяти довільний інший мінімальний розріз, то таким самим чи- ном на ньому всі дуги з ),( KK є насиченими, а всі дуги з ),( KK ненасиче- ними. Доведення завершене. УМОВИ РОЗВ’ЯЗНОСТІ ДЛЯ ЗАДАЧІ РОЗПОДІЛУ ПОТОКІВ Повернемося до проблеми розв’язності системи )(),(),( idiNxNix =− , ,Ni∈ )()()( vrvxvr +− ≤≤ , Vv∈ . (9) Для вирішення питання щодо сумісності системи достатньо побудувати по- тік, що їй задовольняє. О.Є. Кірік ISSN 1681–6048 System Research & Information Technologies, 2011, № 4 124 Вважаємо, що 0)( =− vr . Дійсно, якщо це не так, то розглянемо нові потоки )()()( vrvxvx −−= . Підставивши )(vx у (9), прийдемо до нової сис- теми: )(),(),( idiNxNix =− , Ni∈ , )()()( vrvxvr +− ≤≤ , Vv∈ , де )()()( vrvrvr −++ −= , ).,(),()()( NirNiridid −− +−= Це означає, що можна звести задачу, що розглядається, до попередньої, в якій нижні грані обмежень дорівнюють нулю. Отже, розглядаємо питання про розв’язність системи (9), коли 0)( =− vr . Побудуємо новий граф ,G′ додавши до графу ),( VNG додаткові вершини s та t , тобто NtsN ∪∪=′ }{}{ . Розіб’ємо N на дві таких множи- ни S та ,T що TSN ∪= , ∅=∩TS та }0)(:{ >∈= idNiS , }0)(:{ ≤∈= idNiT . До множини V додамо нові дуги Siis ∈),,( та ),,( ti Ti∈ . Розширену множину дуг позначимо V ′ . Введемо обмеження на про- пускні здатності нововведених дуг: )(),(0 idisx ≤≤ , Si∈ , ≤≤ ),(0 tix )(id−≤ , .Ti∈ Для нового графу ),( VNG ′′=′ розглянемо задачу про максимальний потік та мінімальний розріз. Розглянемо множину }{s . Доповненням до неї буде множина }{tN ∪ . Пропускна здатність розрізу }){,( tNs ∪ визначається пропускними здат- ностями дуг, що утворюють цей розріз і дорівнює )(),( sdSsr =+ . Розгля- немо тепер множину вершин Ns ∪}{ . Доповненням до неї буде єдина вер- шина t . Відповідно, пропускна здатність розрізу ),}({ tNs ∪ визначається пропускними здатностями дуг, що ведуть у t . Вона дорівнює =+ ),( tTr )(Td= . Насиченість усіх дуг множини ),( Ss забезпечує виконання у вершинах Si∈ балансових співвідношень, оскільки в цьому випадку −),( Nix 0),(),( =−− isxiNx , )(),( idisx = для всіх Si∈ . Тому )(),(),( idiNxNix =− для всіх Si∈ . Аналогічно, якщо всі дуги множини ),( tT є насиченими, то викону- ються умови: 0),(),(),( =+− tixiNxNix , )(),( idtix −= для всіх ,Ti∈ або )(),(),( idiNxNix −=− для всіх Ti∈ . Таким чином, якщо існує потік, що насичує дуги ),( Ss та ),( tT розши- реного графу G′ , то цей потік задовольняє умовам (9) для вихідного графу G . Згідно з теоремою про максимальний потік і мінімальний розріз, вимога насиченості дуг є справедливою для мінімальних розрізів. Виведемо умови, за яких розрізи }){,( tNs ∪ і ),}({ tNs ∪ будуть мінімальними. Розглянемо довільний розріз )\,}({ KNKsK ∪=′ , NK ⊂ . Випишемо значення його пропускної здатності. Вона дорівнює сумі пропускних здат- ностей відповідних дуг ),(),(),( tKTrKKrKSsr ∩++∩ +++ . З умови Проблема існування розв’язку в задачах розподілу потоків Системні дослідження та інформаційні технології, 2011, № 4 125 мінімальності розрізу }){,( tNs ∪ отримаємо −+∩ + ),()( KKrKSd )()( SdKTd ≥∩− . Звідси випливає, що ++∩−≥+ )()(),( SdKSdKKr )( KTd ∩+ . Перетворимо праву частину нерівності, враховуючи, що KKN ∪= : [ ] )()()()()()( KdKTdKSdKTdKSdSd =∩+∩=∩+∩− . Ми отримали умову )(),( KdKKr ≥+ . Аналогічно для розрізу ),}({ tNs ∪ )()(),()( TdKTdKKrKSd ≥∩−+∩ + , =∩−∩+−≥+ )()()(),( KSdKTdTdKKr )()()()( kdKdKSdKTd =−=∩−∩−= . Для задачі з ненульовою нижньою гранню обмежень ця нерівність пе- ретвориться до вигляду: )(),(),( KdKKrKKr ≥− −+ . (10) Сформулюємо умови розв’язності. Теорема 4. Необхідною і достатньою умовою розв’язності системи (9) є виконання для кожної підмножини вузлів NK ⊂ нерівності (10). Ця умова означає, що відтік з довільної підмножини вузлів NK ⊂ не має перевищувати пропускну здатність дуг, які ведуть з K (або приплив у довільну підмножину вузлів NK ⊂ не має перевищувати пропускну здатність дуг, які ведуть у K ). Сформулюємо алгоритм для визначення сумісності системи (9). Алгоритм 1. 1. Розширюємо вихідний граф G введенням додаткового витоку та стоку. 2. Проводимо процедуру збільшення потоку, наведену в доведенні тео- реми 3. 3. Перший варіант. Буде отриманий максимальний потік, що означає сумісність системи. 4. Другий варіант. Буде визначена неможливість побудувати макси- мальний потік, що і буде означати несумісність системи. При цьому множи- ни K та K , для яких порушується (10), знаходяться автоматично, якщо че- рез K позначити множину помічених, а через K — множину непомічених вузлів. РОЗПОДІЛ ПОТОКІВ ІЗ МІНІМІЗАЦІЄЮ ПОХИБКИ ФУНКЦІЇ СПОЖИВАННЯ Припустимо, що система (9) не є сумісною. Відсутність допустимого розв’язку спонукає до пошуку модифікацій моделі, які гарантували б сумісність системи обмежень. О.Є. Кірік ISSN 1681–6048 System Research & Information Technologies, 2011, № 4 126 Пропускна здатність ділянок мережі залежить від технологічних харак- теристик системи і не може бути за бажанням змінена. Тому залишається корегувати замовлення споживачів або подачу речовини з витоків. При цьо- му порушення замовлень споживачів бажано звести до мінімуму. Для графу ),( VNG = сформулюємо задачу розподілу потоків з оптимі- зацією доставки продукту споживачам та мінімізацією порушень замовлень. За основу візьмемо нелінійну модель розподілу потоків, що дозволяє опису- вати широкий спектр розподільчих мереж та докладно досліджена в [3]. Мі- німізувати затрати на доставку продукту споживачам та похибку функції споживання ∑∑ ∈∈ + + + = NiVji ijixjilF )( 2 1),(),( 1 1 2 ),( 1 ε α α (11) за обмежень ,),()(),(),( NiiidiNxNix ∈+=− ε (12) )()()( vrvxvr +− ≤≤ , Vv∈ . (13) Функція вартості доставки (довжина ділянки мережі) ),( jil визначена на дугах графу .G Коефіцієнт α у виразі цільової функції дозволяє врахо- вувати фізичні закономірності для різних розподільчих мереж. При 0=α замовлення доставляється споживачам найкоротшим шляхом, як у лінійній транспортній задачі. Функції Nii ∈),(ε відображають можливі відхилення функцій споживання від замовлень споживачів. Необхідною умовою сумісності обмежень (12), тобто збалансованості розподільчої системи, є виконання співвідношення 0)()( =+ NNd ε . (14) Поставимо у відповідність кожному i -му співвідношенню (12) множ- ник Лагранжа iu , Ni∈ , а співвідношенню (14) — u . Випишемо для задачі (11)–(14) функцію Лагранжа та сформулюємо не- обхідні умови екстремуму. ( ) ++ + = ∑∑ ∈∈ + NiVji ijixjilL )( 2 1),(),( 1 1 2 , 1 ε α α [ ] [ ]=++−−−+ ∑∑ ∈∈ NiNi iiduiidiNxNixiu )()()()(),(),()( εε [ ] ( ) ∑ ∈ + + ⎭ ⎬ ⎫ ⎩ ⎨ ⎧ −+ + = Vji jujujixjixjil , 1 )()(),(),(),( 1 1 α α [ ] [ ]∑ ∈ ⎭ ⎬ ⎫ ⎩ ⎨ ⎧ −−−−+ Ni iuuidiuuii )()()()()( 2 1 2 εε . За теоремою Куна-Такера [4], для того, аби величини )(vx , Vv∈ , )(iε , Ni∈ були розв’язком поставленої задачі (11)–(14), необхідно і достатньо, щоб знайшлися числа iu , Ni∈ та u , щоб відповідні невідомі доставляли б мінімум функції Лагранжа L за обмежень (13). Проблема існування розв’язку в задачах розподілу потоків Системні дослідження та інформаційні технології, 2011, № 4 127 З теорії двоїстості [4] розв’язування задачі (11)–(14) є еквіва- лентним максимізації вгнутої неперервно дифференційовної функції Lu jirjirjix )],(),,([),( min)( +−∈ =Φ . Позначимо .))()((sign)()(),( 1 iujuiujuiju −−= α З необхідних умов екстремуму отримуємо, що мінімум функції L з врахуванням простих обмежень (13) досягається в точці: ( ) ⎪ ⎪ ⎪ ⎩ ⎪⎪ ⎪ ⎨ ⎧ ≥ ≤ ≥ ≤ = ++ + −− −− .),(),(),(при),( ,),(),(),( ,),(),(),(при),(),( ,),(),(),(при),( , 1 1 1 1 1 * α α α α α jiljirijujir jiljiriju jiljirijujiliju jiljirijujir jix (15) Крім того, виконуються співвідношення )()( iuui −=ε , .Ni∈ (16) Використовуючи (15), конкретизуємо вигляд функції Φ : [ ] [ ] [ ]∑∑ ∈∈ ⎭ ⎬ ⎫ ⎩ ⎨ ⎧ −+−−−=Φ NiVji ji idiuuiuuiujuu )()()( 2 1)()()( 2 ),( ),(φ , (17) де ( ) ⎪ ⎪ ⎪ ⎩ ⎪ ⎪ ⎪ ⎨ ⎧ ≥ + ≤ ≥ + − ≤ + = +++ + −− −+− .),(),(),(при),( 1 1 ,),(),(),( ,),(),(),(при),(),( 1 ,),(),(),(при),( 1 1 1 1 1 1 1 1 1 , α α α α α α α α α α α φ jiljirijujirl jiljiriju jiljirijujiliju jiljirijujirl ij ij ji Таким чином, двоїста задача зводиться до задачі безумовної оптимізації )(max uΦ , (18) причому її цільова функція має неперервні похідні, які ми можемо обчислити. Знаючи оптимальні значення )(iu , Ni∈ , та необхідні умови екстрему- му можемо за формулами (16), (17) обчислити оптимальне значення потоків ijx , Vji ∈),( та нові значення функцій споживання )()()( iidid ε+= , Ni∈ . АЛГОРИТМ РОЗВ’ЯЗАННЯ ДВОЇСТОЇ ЗАДАЧІ Для розв’язання задачі (18) можна використати довільний метод нелінійного програмування [5, 6]. Можемо застосувати метод покоординатного спуску, ідея якого полягає в тому, що на кожному кроці варіюється тільки одна змінна за умови фіксації решти. О.Є. Кірік ISSN 1681–6048 System Research & Information Technologies, 2011, № 4 128 Розв’язок одновимірних задач )( max iu Φ зводиться до обертання на нуль похідної цільової функції. Оскільки функція Φ є вгнутою, то похідні моно- тонно спадають. Для знаходження нуля неперервної монотонно спадаючої функції скористаємось методом січних, опис якого наведено у роботі [7]. Сформулюємо тепер покроковий алгоритм розв’язання задачі (18). Алгоритм 2. 1. Вибираємо довільні початкові значення )(iu , Ni∈ та u . 2. Розв’язуємо задачу знаходження оптимальних значень )(iu , Ni∈ максимізуючи функцію Φ методом покоординатного спуску. 3. Знаючи оптимальні значення )(iu , ,Ni∈ і, використовуючи необ- хідні умови екстремуму, повертаємося до вихідних змінних ),( jix , ,),( Vji ∈ що дає розподіл потоків, який гарантує мінімальне порушення замовлень споживачів )(iε у кожному вузлі Ni∈ . ВИСНОВКИ Запропонована математична модель розподілу потоків із мінімізацією по- рушень функцій споживання є, звичайно, результатом певної ідеалізації процесу планування ресурсорозподільчих процесів. Вона орієнтована на апріорний аналіз функціонування системи на наявність «вузьких місць», про які свідчитиме значне відхилення вектора споживання від планового. Ясно, що допустимі показники цих порушень будуть різними для різних продук- топроводів. За бажанням можна накласти двосторонні обмеження на порушення функції споживання на кшталт двосторонніх технологічних обмежень (13). Завдяки цьому можна відокремити підмножину вузлів, де порушення є не- бажаними або взагалі недопустимими. Математична модель оптимальної доставки продукту споживачам з мінімізацією відхилень вектора спожи- вання та вузловими технологічними обмеженнями може бути предметом подальших досліджень. ЛІТЕРАТУРА 1. Форд Л., Фалкерсон Д. Потоки в сетях. — М.: Мир, 1966. — 276 с. 2. Оре О. Графы и их применение. — М.: Мир, 1965. — 174 с. 3. Кірік О.Є. Розподіл потоків в мережах складної кільцевої топології // Наук. вісті НТУУ «КПІ». — 2009. — № 2. — С. 18–26. 4. Пшеничный Б.Н. Выпуклый анализ и экстремальные задачи. — М.: Наука, 1980. — 320 с. 5. Пшеничный Б.Н., Кирик Е.Е. Методы нелинейного программирования и потоки в сетях // Кибернетика и системный анализ. — 1994. — № 6. — С. 67–77. 6. Кірік О.Є. Алгоритми лінеаризації та спряжених градієнтів для нелінійних задач розподілу потоків // Наук. вісті НТУУ «КПІ». — 2007. — № 3. — С. 67–73. 7. Кірік О.Є. Оптимізація заповнення сховищ в задачах розподілу потоків для розподільчих мереж // Наук. вісті НТУУ «КПІ». — 2010. — № 1. — С. 28–35. Надійшла 04.09.2010

Проблема існування розв’язку в задачах розподілу потоків

Institution

Ähnliche Einträge