Методы нахождения динамических потоков в сетях с обобщeнным законом Кирхгофа
Узагальнений закон Кірхгофа для потоків у мережах моделюється за допомогою системи лінійних нерівностей, яка має структуру відповідного графа. У випадку, коли граф має більше одного циклу, під час розв’язання системи виникають певні ускладнення. Запропоновано метод заміни циклу в графі зіркою. Gener...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2012 |
| Main Authors: | , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84018 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Методы нахождения динамических потоков в сетях с обобщeнным законом Кирхгофа / Е.Е. Кирик, В.М. Клименко, В.В. Остапенко // Кибернетика и системный анализ. — 2012. — Т. 48, № 1. — С. 83-88. — Бібліогр.: 8 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859468472776392704 |
|---|---|
| author | Кирик, Е.Е. Клименко, В.М. Остапенко, В.В. |
| author_facet | Кирик, Е.Е. Клименко, В.М. Остапенко, В.В. |
| citation_txt | Методы нахождения динамических потоков в сетях с обобщeнным законом Кирхгофа / Е.Е. Кирик, В.М. Клименко, В.В. Остапенко // Кибернетика и системный анализ. — 2012. — Т. 48, № 1. — С. 83-88. — Бібліогр.: 8 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Узагальнений закон Кірхгофа для потоків у мережах моделюється за допомогою системи лінійних нерівностей, яка має структуру відповідного графа. У випадку, коли граф має більше одного циклу, під час розв’язання системи виникають певні ускладнення. Запропоновано метод заміни циклу в графі зіркою.
Generalized Kirchhoff’s law for flows in networks is modeled by a system of linear inequalities that has the structure of the respective graph. In the case where the graph has more than one cycle, solving the system of inequalities involves certain difficulties. The paper proposes a method of replacing a cycle in the graph with a star.
|
| first_indexed | 2025-11-24T08:27:43Z |
| format | Article |
| fulltext |
ÓÄÊ 519.8
Å.Å. ÊÈÐÈÊ, Â.Ì. ÊËÈÌÅÍÊÎ, Â.Â. ÎÑÒÀÏÅÍÊÎ
ÌÅÒÎÄÛ ÍÀÕÎÆÄÅÍÈß ÄÈÍÀÌÈ×ÅÑÊÈÕ ÏÎÒÎÊÎÂ
 ÑÅÒßÕ Ñ ÎÁÎÁÙEÍÍÛÌ ÇÀÊÎÍÎÌ ÊÈÐÕÃÎÔÀ
Êëþ÷åâûå ñëîâà: ïîòîêè â ñåòÿõ, íàïðàâëåííûé ãðàô, äóãè, öèêëû, ñèñòåìû
ëèíåéíûõ íåðàâåíñòâ, ìåòîäû èñêëþ÷åíèÿ íåèçâåñòíûõ.
ÂÂÅÄÅÍÈÅ
 ðàáîòàõ [1, 2] îïèñàíû òåõíîëîãè÷åñêèå ïðîöåññû, êîòîðûå ìîäåëèðóþòñÿ
ñ ïîìîùüþ äèíàìè÷åñêèõ ïîòîêîâ â ñåòÿõ ñ îáîáùåííûì çàêîíîì Êèðõãîôà.
 ñòàöèîíàðíîì ñëó÷àå ïîòîêè íå çàâèñÿò îò âðåìåíè, è äëÿ èõ íàõîæäåíèÿ
íåîáõîäèìî ðåøèòü ñèñòåìó ëèíåéíûõ íåðàâåíñòâ ñî ñòðóêòóðîé ãðàôà.
 ñèëó òåõíîëîãè÷åñêèõ óñëîâèé [1] òàêàÿ ñèñòåìà ðåøàåòñÿ ìåòîäàìè èñêëþ-
÷åíèÿ íåèçâåñòíûõ.  [3] ïðåäëîæåí ìåòîä ïîñëåäîâàòåëüíîãî èñêëþ÷åíèÿ îä-
íîé íåèçâåñòíîé, â [1, 4] ðàçðàáîòàíû ìåòîäû èñêëþ÷åíèÿ ãðóïï íåèçâåñòíûõ.
 îáùåì ñëó÷àå ïðè èñêëþ÷åíèè îäíîé íåèçâåñòíîé èç ñèñòåìû, èìåþùåé m
äâóñòîðîííèõ íåðàâåíñòâ, ìîæåò âîçíèêíóòü íîâàÿ ñèñòåìà, ñîñòîÿùàÿ èç Cm
2 íåðà-
âåíñòâ. Ðàññìàòðèâàåìàÿ ñèñòåìà íåðàâåíñòâ èìååò ñòðóêòóðó ãðàôà, ïîýòîìó äëÿ åå
ðåøåíèÿ åñòåñòâåííî èñïîëüçîâàòü äàííóþ ñòðóêòóðó. Åñëè èñêëþ÷àòü ïîòîêè, ïðîòå-
êàþùèå ïî êîíöåâûì èëè ïðîìåæóòî÷íûì ãðàôàì, òî íîâàÿ ñèñòåìà èìååò ìåíüøåå
÷èñëî íåðàâåíñòâ è åé áóäåò ñîîòâåòñòâîâàòü íîâûé ãðàô, êîòîðûé ïîëó÷àåòñÿ èç èñ-
õîäíîãî ïóòåì ñòÿãèâàíèÿ ñîîòâåòñòâóþùåãî ðåáðà. Àíàëîãè÷íîå ïðîèñõîäèò ïðè
ðàññìîòðåíèè êîíöåâûõ è ïðîìåæóòî÷íûõ ïîäãðàôîâ è èñêëþ÷åíèè ãðóïï íåèçâåñò-
íûõ ïîòîêîâ, ïðîòåêàþùèõ ïî ýòèì ïîäãðàôàì.
Òàêèì îáðàçîì, â ãðàôå, èìåþùåì îäèí öèêë, äîñòàòî÷íî âíà÷àëå èñêëþ-
÷èòü ïîòîêè, ïðîòåêàþùèå ïî êîíöåâûì ðåáðàì. Îñòàíåòñÿ ãðàô â âèäå öèêëà,
âñå ðåáðà êîòîðîãî ÿâëÿþòñÿ ïðîìåæóòî÷íûìè. Åñëè â ãðàôå áîëüøå îäíîãî
öèêëà, òî ñèñòåìó íåðàâåíñòâ ïðèõîäèòñÿ ðåøàòü îáùèìè ìåòîäàìè [5]. ×òîáû
èçáåæàòü ïîäîáíîé ñèòóàöèè, â ðàáîòå [6] ïðåäëîæåí ïîäõîä ê ðåøåíèþ ñèñòå-
ìû íåðàâåíñòâ, ñîñòîÿùèé â çàìåíå èñõîäíîé ñèñòåìû íîâîé. Ïîñëåäíÿÿ èìååò
ñòðóêòóðó ãðàôà, êîòîðûé ïîëó÷àåòñÿ èç èñõîäíîãî ïóòåì çàìåíû êàêîãî-ëèáî
öèêëà çâåçäîé.
 äàííîé ñòàòüå èçó÷àþòñÿ äèíàìè÷åñêèå ïîòîêè, è â ñôîðìóëèðîâàííûõ
ìîäåëÿõ âàæíóþ ðîëü èãðàåò âðåìÿ ïðîõîæäåíèÿ ïîòîêîì ñîîòâåòñòâóþùåé
äóãè (âðåìÿ äîáåãàíèÿ).  ðàáîòàõ [1, 7] ðàññìàòðèâàþòñÿ âîïðîñû èñêëþ÷åíèÿ
íåèçâåñòíûõ ïîòîêîâ, ïðîòåêàþùèõ ïî êîíöåâûì è ïðîìåæóòî÷íûì äóãàì,
à òàêæå èñêëþ÷åíèÿ ãðóïï íåèçâåñòíûõ ïîòîêîâ, ïðîòåêàþùèõ ïî êîíöåâûì è
ïðîìåæóòî÷íûì îðèåíòèðîâàííûì ïîäãðàôàì.
Íàñòîÿùàÿ ñòàòüÿ îáîáùàåò ðåçóëüòàòû ðàáîòû [6]. Â ïðåäëàãàåìîì çäåñü
ïîäõîäå îðèåíòèðîâàííûé ñïåöèàëüíûì îáðàçîì ïîëóêîíòóð çàìåíÿåòñÿ îðèåí-
òèðîâàííîé çâåçäîé è ñîîòâåòñòâåííî ìåíÿþòñÿ ñèñòåìû íåðàâåíñòâ. (Îòìåòèì,
÷òî âñÿ òåðìèíîëîãèÿ òåîðèè ãðàôîâ âçÿòà èç [8].)
ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È
 [1] ïðåäëîæåíà ñëåäóþùàÿ ìîäåëü äèíàìè÷åñêèõ ïîòîêîâ â ñåòÿõ ñ îáîá-
ùåííûì çàêîíîì Êèðõãîôà. Ïóñòü G V E� { }, — îðèåíòèðîâàííûé ãðàô. Çäåñü
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1 83
© Å.Å. Êèðèê, Â.Ì. Êëèìåíêî, Â.Â. Îñòàïåíêî , 2012
V — ìíîæåñòâî âåðøèí, E — ìíîæåñòâî äóã, ò.å. îðèåíòèðîâàííûõ ðåáåð.
Äëÿ êàæäîé âåðøèíû v V� îáîçíà÷èì
N v u V u v E� � � �( ) :( , ){ } ,
N v u V u v E� � � �( ) :( , ){ } .
Ìíîæåñòâî N v� ( ) îïèñûâàåò âñå âåðøèíû, èç êîòîðûõ âûõîäÿò äóãè, âõî-
äÿùèå â âåðøèíó v , à ìíîæåñòâî N v� ( ) — âñå âåðøèíû, â êîòîðûå âõîäÿò äóãè,
èñõîäÿùèå èç âåðøèíû v .
Ïîñòàâèì çàäà÷ó: íàéòè ôóíêöèè x tji ( ) , t � �[ , ]0 , óäîâëåòâîðÿþùèå
óñëîâèÿì
a x t x t A tji ji ji ik
k N i
i
j N i
( ) ( ) ( )
( )( )
� � �
�� ��
�� � , i V� , (1)
x t Bji ji( ) � , ( , )i j E� . (2)
Çäåñü A ti ( ) , B ji — çàäàííûå îòðåçêè, � ji — ïîëîæèòåëüíûå êîýôôèöèåíòû,
êîòîðûå ïðè � ji � 1 ìîæíî èíòåðïðåòèðîâàòü êàê êîýôôèöèåíòû ïîòåðü ïðè
ïðîõîæäåíèè ïîòîêîì x ji äóãè ( , )j i . Âðåìÿ äîáåãàíèÿ � ji íàçîâåì äëèíîé
äóãè ( , )j i . Îãðàíè÷åíèÿ (1) èìåþò çàïàçäûâàþùèå àðãóìåíòû. Ïîýòîìó áóäåì
ñ÷èòàòü ôóíêöèè A ti ( ) èçâåñòíûìè íà îòðåçêå [ , ]�� 0 , ãäå � — âåëè÷èíà, âîç-
íèêàþùàÿ ïðè âûâîäå èçëîæåííûõ íèæå ðåçóëüòàòîâ.
Óñëîâèå (2) ÿâëÿåòñÿ îãðàíè÷åíèåì íà ïîòîêè, ïðîòåêàþùèå ïî äóãàì. Íà
îòðåçêè B ji íå íàëîæåíî íèêàêèõ äîïîëíèòåëüíûõ óñëîâèé. Ýòî îçíà÷àåò, ÷òî
ïîòîê x ji , êîòîðûé òåõíîëîãè÷åñêè ïðåäñòàâëÿåò ñîáîé ðàñõîä, ïðîòåêàþùèé ïî
äóãå ( , )j i , ìîæåò ïðèíèìàòü êàê ïîëîæèòåëüíûå, òàê è îòðèöàòåëüíûå çíà÷åíèÿ.
Ïîòîê ìîæåò ôîðìèðîâàòü ïîëîæèòåëüíóþ èëè îòðèöàòåëüíóþ âîëíó îòíîñè-
òåëüíî íåêîòîðîãî ñðåäíåãî óðîâíÿ. Íàïðàâëåíèå äóãè â ìîäåëè (1) îïðåäåëÿåòñÿ
òåì, ÷òî âûòåêàþùèå èç âåðøèíû i ïîòîêè (ïîëîæèòåëüíûå èëè îòðèöàòåëüíûå)
íå èìåþò çàïàçäûâàþùåãî àðãóìåíòà; ïîòîêè, âõîäÿùèå â âåðøèíó i , èìåþò çà-
ïàçäûâàþùèå àðãóìåíòû (â îáùåì ñëó÷àå çàïàçäûâàíèå ìîæåò ðàâíÿòüñÿ íóëþ è
íàïðàâëåíèå äóãè âûáèðàåòñÿ ñ ó÷åòîì äîïîëíèòåëüíûõ ñîîáðàæåíèé). Óñëîâèÿ
(2), òàêèå, êàê â [6], íåòðóäíî ñâåñòè ê âèäó
x tji ji( ) [ , ]� 0 � , � ji 0 . (3)
Ïðè îòñóòñòâèè âðåìåíè çàïàçäûâàíèÿ (� ji � 0) íàõîæäåíèå x tji ( ) ñâîäèòñÿ ê
ðåøåíèþ äëÿ êàæäîãî ôèêñèðîâàííîãî t ñèñòåìû ëèíåéíûõ íåðàâåíñòâ (1), (3).
Ìåòîäû ðåøåíèÿ òàêèõ ñèñòåì îïèñàíû âî ââåäåíèè ñòàòüè.
 ðàññìàòðèâàåìîì ñëó÷àå ïîòîê x ji âûõîäèò èç âåðøèíû j ñ àðãóìåíòîì
t x tji( ( )), à âõîäèò â âåðøèíó i ñ àðãóìåíòîì t ji� � (x tji ji( )� � ). Ïîýòîìó äëÿ ðå-
øåíèÿ ïîñòàâëåííîé çàäà÷è ñëåäóåò ïðåîáðàçîâàòü (1), (3) òàêèì îáðàçîì, ÷òîáû
èñêîìûå ïîòîêè âõîäèëè ñ îäíèì è òåì æå àðãóìåíòîì. Ñîãëàñíî [1, 7] ýòî ìîæ-
íî ñäåëàòü â ñëó÷àå, êîãäà ãðàô G — äåðåâî èëè îí èìååò îäèí ïîëóöèêë.
 äàííîé ñòàòüå ïðèâåäåí ïîëóöèêë îðèåíòèðîâàííîãî ïîäãðàôà, ñîñòîÿùèé
èç äâóõ ïóòåé.
ÑËÓ×ÀÉ ÐÀÂÅÍÑÒÂÀ ÊÎÝÔÔÈÖÈÅÍÒΠÅÄÈÍÈÖÅ
Ðàññìîòðèì ïîëóêîíòóð îðèåíòèðîâàííîãî ãðàôà, ñîñòîÿùèé èç äâóõ ïóòåé: P1 è P2
(ðèñ. 1). Îáà ïóòè íà÷èíàþòñÿ â âåðøèíå 1 (èñòîê) è çàêàí÷èâàþòñÿ â âåðøèíå m
(ñòîê). Ïåðâûé ïóòü çàäàåòñÿ âåðøèíàìè P1 � {1, 21, 31, ... , ( )k �1 1 , k1, m} , âòî-
84 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1
ðîé — P l l m2 1 22 32 1 2 2� �{ , , , ... , ( ) , , }. Äëèíà äóã ( , )121 , ( , ), ...2131 , (( ) , ),k k�1 1 1
( , )k m1 äëÿ ïóòè P1 ðàâíà ñîîòâåòñòâåííî � �1 2, , ...
�� �k k1, . Äëèíà äóã
( , ), ( , ), ..., (( ) , ), ( , )1 22 22 32 1 2 2 2l l l m� äëÿ ïóòè P2 ðàâíà ñîîòâåòñòâåííî
t t t tl l1 2 1, , ..., ,� . Ïî ýòèì äóãàì
ïðîòåêàþò ïîòîêè: äëÿ ïóòè
P1 — ïîòîê x x x xk k1 2 1, , ..., ,� ,
äëÿ ïóòè P2 — ïîòîê y y1 2, , ...
..., ,y yl l�1 .
Óñëîâèÿ (1), (3) ïåðåïèøåì
â âèäå
� � � �x t y t p t A t1 1 1 1( ) ( ) ( ) ( ) ,
x t x t p t A t1 1 2 2 21( ) ( ) ( ) ( )� � � �� ,
x t x t p t A t2 2 3 3 31( ) ( ) ( ) ( )� � � �� ,
…
x t x t p t A tk k k k k� �� � � �1 1 1( ) ( ) ( ) ( )� , (4)
y t t y t q t A t1 1 2 2 22( ) ( ) ( ) ( )� � � � ,
y t t y t q t A t2 2 3 3 32( ) ( ) ( ) ( )� � � � ,
…
y t t y t q t A tl l l l l� �� � � �1 1 2( ) ( ) ( ) ( ) ,
x ti i( ) [ , ]� 0 1� , y tj j( ) [ , ]� 0 2� , � i
1 0 , � j
2 0 , i k�1, ..., , j l�1, ..., . (5)
Çäåñü A t1 ( ) , A ti1 ( ) , A tj2 ( ) , A tm ( ) — îòðåçêè, çàäàþùèå îãðàíè÷åíèÿ
âèäà (1), êîòîðûå ñîîòâåòñòâóþò âåðøèíàì ïóòåé P1 è P2 , a � i
1 è � j
2 — îãðàíè÷å-
íèÿ âèäà (3) äëÿ ñîîòâåòñòâóþùèõ ïîòîêîâ. Ôóíêöèè p ti ( ) è q ti ( ) îïèñûâàþò
ïîòîêè (êðîìå ïîòîêîâ x ti ( ) è y tj ( )), êîòîðûå âõîäÿò èëè âûõîäÿò èç
ñîîòâåòñòâóþùèõ âåðøèí.
Ñôîðìóëèðóåì îñíîâíîå ïðåäïîëîæåíèå, ïðè êîòîðîì ïîëóêîíòóð, ñîñòîÿ-
ùèé èç ïóòåé P1 è P2 , ìîæíî çàìåíèòü îðèåíòèðîâàííîé çâåçäîé:
� �i
i
k
j
j
l
t
� �
� �� �
1 1
.
Î÷åâèäíî, ÷òî äëèíû ïóòåé P1 è P2 ñîâïàäàþò. Ýòî ïðåäïîëîæåíèå àíàëî-
ãè÷íî ïðåäïîëîæåíèÿì, ïðè êîòîðûõ âîçìîæíî èñêëþ÷åíèå ãðóïïû íåèçâåñòíûõ
ïîòîêîâ [1].  ñëó÷àå èõ íåâûïîëíåíèÿ äëÿ íàõîæäåíèÿ íåèçâåñòíûõ ïîòîêîâ
ïðèõîäèòñÿ ïåðåõîäèòü ê ëîêàëüíî-êîíå÷íûì, íî áåñêîíå÷íûì ãðàôàì (ñì. [1]).
Èç (4) ïîëó÷àåì
u t x t y t A t p t1 1 1 1 1( ) ( ) ( ) ( ) ( )� � � � � ,
v t x t x t A t p t1 1 2 1 21 1 2 1( ) ( ) ( ) ( ) ( )� � � � � � �� � � ,
v t x t x t A t p t2 2 1 3 1 2 31 1 2 3 1 2( ) ( ) ( ) ( ) (� � � � � � � � � � �� � � � � � � ) ,
…
v t x t x tk k k k k� � � �� � � � � � � � �1 1 1 2 1 1( ) ( ) ( )� � � �� �
� � � � � � � �� �A t p tk k k k1 1 1 1 1( ) ( )� � � �� � , (6)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1 85
Ðèñ. 1. Ñõåìà ïóòåé P1 è P2 èç èñòî÷íèêà 1 ê ñòîêó m
w t y t y t t A t t q t t1 1 2 1 22 1 2 1( ) ( ) ( ) ( ) ( )� � � � � � � ,
w t y t t y t t t A t t t q t t t2 2 1 3 1 2 32 1 2 3 1 2( ) ( ) ( ) ( ) (� � � � � � � � � � � ) ,
…
w t y t t t y t t tl l l l l� � � �� � � � � � � � �1 1 1 2 1 1( ) ( ) ( )� �
� � � � � � � �� �A t t t q t t tl l l l2 1 1 1 1( ) ( )� � ,
u t x t y t t t A t qk k l l m m2 1 1 1 1( ) ( ) ( ) ( ) (� � � � � � � � � � �� �� � � �� � ) .
Òàêèì îáðàçîì, ââåäåíû íîâûå ïîòîêè u t1 ( ) , u t2 ( ) , v ti ( ) , w tj ( ) ,
i k� �1 1, ..., , j l� �1 1, ..., . Ââîäèì íîâóþ âåðøèíó 0 è ñ÷èòàåì, ÷òî íîâûå ïîòîêè
ïðîòåêàþò ïî äóãàì
( , ), ( , ), ( , ), ..., ( , ), ( , ), ( , ), ..., (1 0 0 21 0 31 0 1 0 22 0 32k 0 2 0, ), ( , )l m . (7)
Ïðåæíèå äóãè, ïî êîòîðûì ïðîòå-
êàëè ïîòîêè x ti ( ) è y tj ( ), èñêëþ÷à-
åì. Ïîëó÷àåì âìåñòî äâóõ ïóòåé
îðèåíòèðîâàííóþ çâåçäó (ðèñ. 2).
Îòìåòèì, ÷òî åñëè ïðè ôèêñèðî-
âàííîì t èçâåñòíû ïîòîêè u1, u2 , vi ,
w j , òî èç ôîðìóë (6) ìîæíî îïðåäå-
ëèòü ïîòîêè xi , y j â óêàçàííûå â (6)
ìîìåíòû âðåìåíè.
Îïèøåì îãðàíè÷åíèÿ íà íîâûå
ïîòîêè. Èç îïðåäåëåíèÿ íîâûõ ïîòî-
êîâ ñëåäóåò
u t v t w t u ti
i
k
j
j
l
1
1
1
1
1
2 0( ) ( ) ( ) ( )� � � �
�
�
�
�
� � . (8)
Ðàâåíñòâî (8) ÿâëÿåòñÿ îãðàíè÷åíèåì â âåðøèíå 0 .
Ïîëüçóÿñü íîâûìè ïîòîêàìè, ïåðåïèøåì âêëþ÷åíèÿ (6) â âèäå
u t p t A t1 1 1( ) ( ) ( )� � ;
v t p t A t1 1 2 21( ) ( ) ( )� � �� ,
v t p t A t2 1 2 3 31( ) ( ) ( )� � � �� � ,
…
v t p t A tk k k k� �� � � � �1 1 1 1( ) ( ) ( )� �� ; (9)
w t t q t A t1 1 2 22( ) ( ) ( )� � � ,
w t t t q t A t2 1 2 3 32( ) ( ) ( )� � � � ,
…
w t t t q t A tl l l l� �� � � � �1 1 1 2( ) ( ) ( )� ;
u t q t A tm m2 ( ) ( ) ( )� � �� .
Âêëþ÷åíèÿ (9) è ðàâåíñòâî (8) îïèñûâàþò îãðàíè÷åíèÿ íà ïîòîêè, ïðîòåêà-
þùèå ïî äóãàì, óêàçàííûì â (7). Äàííûå äóãè îáðàçóþò ïîäãðàô â âèäå íàïðàâ-
ëåííîé çâåçäû. Äëèíû äóã, îïèñàííûõ â (7), ðàâíû ñîîòâåòñòâåííî
0 1 1 2 1 1 1 2 1 1, , , , , ..., ,� � � � � ��
� � � � �� �� � �k lt t t t t .
86 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1
Ðèñ. 2. Ñõåìà îðèåíòèðîâàííîé çâåçäû
Ñîãëàñíî îãðàíè÷åíèÿì (1) ïîòîêè, âõîäÿùèå â âåðøèíó, ìîãóò èìåòü çàïàç-
äûâàþùèå àðãóìåíòû; ïîòîêè, âûõîäÿùèå èç âåðøèíû, íå èìåþò çàïàçäûâàþ-
ùèõ àðãóìåíòîâ. Ðåáðî (1, 0) íå èìååò äëèíû, ïîýòîìó åãî ìîæíî îðèåíòèðîâàòü
â ðàçíûå íàïðàâëåíèÿ. Íî ïîñêîëüêó ïðåäïîëàãàåòñÿ, ÷òî âåðøèíà 1 ÿâëÿåòñÿ èñ-
òîêîì, òî ñ÷èòàåì, ÷òî ïîòîê u t1 ( ) ïðîòåêàåò èç âåðøèíû 1 â âåðøèíó 0 . Âñå
îñòàëüíûå ïîòîêè âûòåêàþò èç âåðøèíû 0 .
Îñòàíîâèìñÿ íà îãðàíè÷åíèÿõ (5). Áóäåì ñ÷èòàòü, ÷òî ïîòîêè â ñèñòåìå (9)
ïðîõîäÿò ïî äóãàì ïðåäñòàâëåííîé âûøå çâåçäû. Îïèøåì òàêèå îãðàíè÷åíèÿ íà
êàæäûé íîâûé ïîòîê, ÷òîáû èç ðåøåíèÿ ñèñòåìû (9) ñëåäîâàëî ðåøåíèå ñèñòå-
ìû (1), (3). Ñîãëàñíî ðàáîòå [6] äëÿ ýòîãî äîñòàòî÷íî íàëîæèòü îãðàíè÷åíèÿ
u t
k
1
1
( ) [ , ]� �� � , u t
k
2
1
( ) [ , ]� �� � , v t
k
i ( ) [ , ]� �
1
� � , w t
k
j ( ) [ , ]� �
1
� � , (10)
i k� �1 1, ..., , j l� �1 1, ..., .
Çäåñü � �� ��
� �
min min , }
,..., ,...,i k j l
i j
1 1
1 2 , k
n
� �
�
�
��2
([ ]x — öåëàÿ ÷àñòü ÷èñëà x), n k l� � .
Îòìåòèì [6], ÷òî åñëè n � 3 , k � 2 , l �1 è � � �i
1
1
2� � , òî ñèñòåìà (9) ñ îãðà-
íè÷åíèÿìè (10) ýêâèâàëåíòíà èñõîäíîé ñèñòåìå (1), (3), ò.å. åñëè ñèñòåìà (1), (3)
èìååò ðåøåíèå, òî è ñèñòåìà (9), (10) èìååò ðåøåíèå.
ÑËÓ×ÀÉ ÏÐÎÈÇÂÎËÜÍÛÕ ÊÎÝÔÔÈÖÈÅÍÒÎÂ
Ðàññìîòðèì ñëó÷àé íàëè÷èÿ êîýôôèöèåíòîâ � ji . Òîãäà (4) ïåðåïèøåòñÿ â âèäå
� � � �x t y t p t A t1 1 1 1( ) ( ) ( ) ( ) ,
� �1 1 1 2 2 21x t x t p t A t( ) ( ) ( ) ( )� � � � ,
� �2 2 2 3 3 31x t x t p t A t( ) ( ) ( ) ( )� � � � ,
…
� �k k k k k kx t x t p t A t� � �� � � �1 1 1 1( ) ( ) ( ) ( ) , (11)
�1 1 1 2 2 22y t t y t q t A t( ) ( ) ( ) ( )� � � � ,
� 2 2 2 3 3 32y t t y t q t A t( ) ( ) ( ) ( )� � � � ,
…
� l l l l l ly t t y t q t A t� � �� � � �1 1 1 2( ) ( ) ( ) ( ) ,
� �k k k l l m mx t y t t q t A t( ) ( ) ( ) ( )� � � � � .
Ïîëîæèì
u t x t y t1 1 1( ) ( ) ( )� � � ,
v t x t x t1 1 1 2 1( ) ( ) ( )� � �� � ,
v t x t x t2 2 2 1 3 1 2( ) ( ) ( )� � � � �� � � � ,
…
v t x t x tk k k k k k� � � � �� � � � � � � �1 1 1 1 2 1 1( ) ( ) ( )� � � � �� � , (12)
w t y t y t t1 1 1 2 1( ) ( ) ( )� � �� ,
w t y t t y t t t2 2 2 1 3 1 2( ) ( ) ( )� � � � �� ,
…
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1 87
w t y t t t y t t tl l l l l l� � � � �� � � � � � � �1 1 1 1 2 1 1( ) ( ) ( )� � � ,
u t x t y t t tk k k l l l2 1 1 1 1( ) ( ) ( )� � � � � � � �� �� � � �� � .
Èç îïðåäåëåíèé (12) âèäíî, ÷òî íîâûå ïîòîêè íå óäîâëåòâîðÿþò ïðîñòîìó
îãðàíè÷åíèþ âèäà (8). Áóäåì ïðåäïîëàãàòü, ÷òî � i � 1 , � j � 1 . Ýòîò ñëó÷àé îïè-
ñûâàåò ïîòåðè ïðè ïðîõîæäåíèè ïîòîêàìè ñîîòâåòñòâóþùèõ äóã.
Âîñïîëüçóåìñÿ ìåòîäàìè ðàáîòû [6]. Òîãäà ïîëó÷èì, ÷òî èñõîäíàÿ ñèñòå-
ìà (1), (3) áóäåò ñëåäñòâèåì ñèñòåìû (9), åñëè â âåðøèíå 0 ïîëîæèòü îãðàíè÷åíèÿ
�� � � � � �
�
�
�
�
� �u t v t w t u ti
i
k
j
j
l
1
1
1
1
1
2 0( ) ( ) ( ) ( ) , (13)
�� � �u t1 0( ) , �� � �u t2 0( ) , �� � �v ti ( ) 0 , �� � �w tj ( ) 0 , (14)
i k� �1 1, ..., , j l� �1 1, ..., , ãäå � � �� � � � � �1 2 1 2 1� �k l .
Òàêèì îáðàçîì, åñëè äëÿ êàæäîãî t ðåøåíà ñèñòåìà (9), (13), (14), òî è èñõîä-
íàÿ ñèñòåìà (1), (3) èìååò ðåøåíèå, à ïî èçâåñòíûì u1, u2 , vi , w j íàõîäÿòñÿ, ñëå-
äóÿ ôîðìóëå (12), íåèçâåñòíûå xi , y j â óêàçàííûå â (12) ìîìåíòû âðåìåíè.
ÇÀÊËÞ×ÅÍÈÅ
Èñïîëüçóÿ ìåòîäû ðàáîòû [6], ìîæíî èññëåäîâàòü ñëó÷àé, êîãäà êîýôôèöèåí-
òû � i , � j ìîãóò ïðèíèìàòü ïðîèçâîëüíûå çíà÷åíèÿ, à íå òîëüêî ìåíüøèå
åäèíèöû. (Îäíàêî àâòîðàì íåèçâåñòíû òåõíîëîãè÷åñêèå ìîäåëè, ñîîòâåòñòâóþ-
ùèå ýòèì ñëó÷àÿì.)
Ìîäåëü (1), (2) ìîæåò íàéòè ïðèìåíåíèå ïðè îïèñàíèè ïðîöåññà òðàíñïîðòà
âîäû â îðîñèòåëüíûõ ñèñòåìàõ èëè ãàçà â ìàãèñòðàëüíûõ òðóáîïðîâîäàõ. Ïîòîêè
x ji ïðåäñòàâëÿþò ñîáîé ðàñõîäû ïðîäóêòîâ, äâèæóùèåñÿ ïî êàíàëàì èëè òðóáî-
ïðîâîäàì, à îòðåçêè Ai îïèñûâàþò îãðàíè÷åíèÿ íà óðîâåíü âîäû â êàíàëàõ èëè
äàâëåíèå ãàçà â òðóáîïðîâîäàõ.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Î ñ ò à ï å í ê î  .  . , Ñ ê î ï å ö ü ê è é  .  . , Ô ³ í ³ í à . Ñ . Ðîçïîä³ë ðåñóðñ³â ó ïðîñòîð³ òà ÷àñ³. —
Êè¿â: Íàóê. äóìêà, 2003. — 323 ñ.
2. Î ñ ò à ï å í ê î Â . Â . , Ô è í è í Ã . Ñ . Ìîäåëèðîâàíèå äâèæåíèÿ âîäû îáîáùåííûì çàêîíîì Êèðõãîôà //
Ïðîáëåìû óïðàâëåíèÿ è èíôîðìàòèêè. — 1999. — ¹ 4. — Ñ. 86–90.
3. Î ñ ò à ï å í ê î Â . Â . , Ï à â ë û ã è í À . È . Ëèíåéíûå íåðàâåíñòâà äëÿ îáîáùåííîãî çàêîíà Êèðõãîôà //
Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 1997. — ¹ 3. — Ñ. 130–148.
4. Ô è í è í à . Ñ . Ìåòîä èñêëþ÷åíèÿ ãðóïïû íåèçâåñòíûõ ïîòîêîâ â ñåòÿõ ñ îáîáùåííûì çàêîíîì
Êèðõãîôà // Òàì æå. — 1999. — ¹ 6. — Ñ. 154–159.
5. × å ð í è ê î â Ñ . Í . Ëèíåéíûå íåðàâåíñòâà. — Ì.: Íàóêà, 1968. — 488 ñ.
6. Ê ë è ì å í ê î  . Ì . , Î ñ ò à ï å í ê î  .  . , Î ñ ò à ï å í ê î Î . Ñ . Ìåòîä ðîçâ’ÿçàííÿ ñèñòåì ë³í³éíèõ
íåð³âíîñòåé íà ãðàô³ øëÿõîì çì³íè éîãî ñòðóêòóðè // Íàóê. â³ñò³ ÍÒÓÓ «Êϲ». — 2004. — ¹ 6. —
Ñ. 135–142.
7. Î ñ ò à ï å í ê î  .  . , Ï à â ë û ã è í À . È . Äèíàìè÷åñêèå ïîòîêè â ñåòÿõ äëÿ îáîáùåííîãî çàêîíà
Êèðõãîôà // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 1966. — ¹ 3. — Ñ. 96–102.
8. Å ì å ë è ÷ å â Â . À . , Ì å ë ü í è ê î â Î . È . , Ñ à ð â à í î â Â . È . , Ò û ø ê å â è ÷ Ð . È . Ëåêöèè ïî òåîðèè
ãðàôîâ. — Ì.: Íàóêà, 1990. — 384 ñ.
Ïîñòóïèëà 14.10.2010
88 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1
|
| id | nasplib_isofts_kiev_ua-123456789-84018 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-11-24T08:27:43Z |
| publishDate | 2012 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Кирик, Е.Е. Клименко, В.М. Остапенко, В.В. 2015-07-02T08:11:58Z 2015-07-02T08:11:58Z 2012 Методы нахождения динамических потоков в сетях с обобщeнным законом Кирхгофа / Е.Е. Кирик, В.М. Клименко, В.В. Остапенко // Кибернетика и системный анализ. — 2012. — Т. 48, № 1. — С. 83-88. — Бібліогр.: 8 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/84018 519.8 Узагальнений закон Кірхгофа для потоків у мережах моделюється за допомогою системи лінійних нерівностей, яка має структуру відповідного графа. У випадку, коли граф має більше одного циклу, під час розв’язання системи виникають певні ускладнення. Запропоновано метод заміни циклу в графі зіркою. Generalized Kirchhoff’s law for flows in networks is modeled by a system of linear inequalities that has the structure of the respective graph. In the case where the graph has more than one cycle, solving the system of inequalities involves certain difficulties. The paper proposes a method of replacing a cycle in the graph with a star. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системный анализ Методы нахождения динамических потоков в сетях с обобщeнным законом Кирхгофа Методи знаходження динамічніх потоків у мережах з узагальненим законом Кірхгофа Methods to find dynamic flows in networks with generalized Kirchgoff’s law Article published earlier |
| spellingShingle | Методы нахождения динамических потоков в сетях с обобщeнным законом Кирхгофа Кирик, Е.Е. Клименко, В.М. Остапенко, В.В. Системный анализ |
| title | Методы нахождения динамических потоков в сетях с обобщeнным законом Кирхгофа |
| title_alt | Методи знаходження динамічніх потоків у мережах з узагальненим законом Кірхгофа Methods to find dynamic flows in networks with generalized Kirchgoff’s law |
| title_full | Методы нахождения динамических потоков в сетях с обобщeнным законом Кирхгофа |
| title_fullStr | Методы нахождения динамических потоков в сетях с обобщeнным законом Кирхгофа |
| title_full_unstemmed | Методы нахождения динамических потоков в сетях с обобщeнным законом Кирхгофа |
| title_short | Методы нахождения динамических потоков в сетях с обобщeнным законом Кирхгофа |
| title_sort | методы нахождения динамических потоков в сетях с обобщeнным законом кирхгофа |
| topic | Системный анализ |
| topic_facet | Системный анализ |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84018 |
| work_keys_str_mv | AT kirikee metodynahoždeniâdinamičeskihpotokovvsetâhsobobŝennymzakonomkirhgofa AT klimenkovm metodynahoždeniâdinamičeskihpotokovvsetâhsobobŝennymzakonomkirhgofa AT ostapenkovv metodynahoždeniâdinamičeskihpotokovvsetâhsobobŝennymzakonomkirhgofa AT kirikee metodiznahodžennâdinamíčníhpotokívumerežahzuzagalʹnenimzakonomkírhgofa AT klimenkovm metodiznahodžennâdinamíčníhpotokívumerežahzuzagalʹnenimzakonomkírhgofa AT ostapenkovv metodiznahodžennâdinamíčníhpotokívumerežahzuzagalʹnenimzakonomkírhgofa AT kirikee methodstofinddynamicflowsinnetworkswithgeneralizedkirchgoffslaw AT klimenkovm methodstofinddynamicflowsinnetworkswithgeneralizedkirchgoffslaw AT ostapenkovv methodstofinddynamicflowsinnetworkswithgeneralizedkirchgoffslaw |