Задача потокораспределения с нефиксированными расходами в узлах
У теорії гідравлічних ланцюгів, створеної для моделювання гідравлічних систем, зокрема трубопровідного транспорту, зазвичай розглядається задача потокорозподілення із заданими витратами середовища, яке транспортується, назовні і ззовні транспортної системи в окремих вузлах. Досліджено випадок, що ст...
Збережено в:
| Дата: | 2011 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2011
|
| Назва видання: | Кибернетика и системный анализ |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/72204 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Задача потокораспределения с нефиксированными расходами в узлах / С.П. Епифанов, В.И. Зоркальцев // Кибернетика и системный анализ. — 2011. — № 1. — С. 81-92. — Бібліогр.: 7 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-72204 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-722042014-12-20T03:01:23Z Задача потокораспределения с нефиксированными расходами в узлах Епифанов, С.П. Зоркальцев, В.И. Системный анализ У теорії гідравлічних ланцюгів, створеної для моделювання гідравлічних систем, зокрема трубопровідного транспорту, зазвичай розглядається задача потокорозподілення із заданими витратами середовища, яке транспортується, назовні і ззовні транспортної системи в окремих вузлах. Досліджено випадок, що становить практичний інтерес, коли витрати середовища в окремих вузлах не фіксовані, а залежать від тиску в цих вузлах. 2011 Article Задача потокораспределения с нефиксированными расходами в узлах / С.П. Епифанов, В.И. Зоркальцев // Кибернетика и системный анализ. — 2011. — № 1. — С. 81-92. — Бібліогр.: 7 назв. — рос. http://dspace.nbuv.gov.ua/handle/123456789/72204 519.85+532.542 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| 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/72204 |
| citation_txt |
Задача потокораспределения с нефиксированными расходами в узлах / С.П. Епифанов, В.И. Зоркальцев // Кибернетика и системный анализ. — 2011. — № 1. — С. 81-92. — Бібліогр.: 7 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT epifanovsp zadačapotokoraspredeleniâsnefiksirovannymirashodamivuzlah AT zorkalʹcevvi zadačapotokoraspredeleniâsnefiksirovannymirashodamivuzlah |
| first_indexed |
2025-07-05T21:03:17Z |
| last_indexed |
2025-07-05T21:03:17Z |
| _version_ |
1836842376958574592 |
| fulltext |
ÓÄÊ 519.85+532.542
Ñ.Ï. ÅÏÈÔÀÍÎÂ, Â.È. ÇÎÐÊÀËÜÖÅÂ
ÇÀÄÀ×À ÏÎÒÎÊÎÐÀÑÏÐÅÄÅËÅÍÈß Ñ ÍÅÔÈÊÑÈÐÎÂÀÍÍÛÌÈ
ÐÀÑÕÎÄÀÌÈ Â ÓÇËÀÕ
Êëþ÷åâûå ñëîâà: çàäà÷à ïîòîêîðàñïðåäåëåíèÿ, ãèäðàâëè÷åñêèå öåïè, èñõîäíàÿ
è äâîéñòâåííàÿ çàäà÷è îïòèìèçàöèè.
 òåîðèè ãèäðàâëè÷åñêèõ öåïåé [1–3] èññëåäóþòñÿ ìàòåìàòè÷åñêèå ìîäåëè ôóíêöè-
îíèðîâàíèÿ ðàçëè÷íûõ ãèäðàâëè÷åñêèõ ñèñòåì, â òîì ÷èñëå ñèñòåì òåïëî-, âîäî-,
íåôòå- è ãàçîñíàáæåíèÿ.  íåé òðàäèöèîííî ðàññìàòðèâàåòñÿ ñëåäóþùàÿ çàäà÷à ïî-
òîêîðàñïðåäåëåíèÿ, êîòîðóþ íàçîâåì êëàññè÷åñêîé. Çàäàíû ðàñõîäû òðàíñïîðòèðóå-
ìîé ñðåäû â óçëàõ, ïîñòàâëÿåìûå èçâíå â ñèñòåìó èëè âîâíå èç ñèñòåìû (äëÿ êðàò-
êîñòè — ðàñõîäû â óçëàõ), è ïðèðàùåíèÿ äàâëåíèÿ íà äóãàõ ãðàôà ãèäðàâëè÷åñêîé
öåïè. Ïåðåìåííûìè (ðàñ÷åòíûìè) âåëè÷èíàìè ÿâëÿþòñÿ äàâëåíèå â óçëàõ, ïîòåðè
äàâëåíèÿ íà äóãàõ, ïîòîêè ñðåäû íà äóãàõ (îáúåìû òðàíñïîðòèðóåìîé ñðåäû â åäè-
íèöó âðåìåíè, äëÿ êðàòêîñòè — ðàñõîäû ñðåäû íà äóãàõ).
Íàðÿäó ñ óêàçàííîé çàäà÷åé èíòåðåñ ïðåäñòàâëÿþò è äðóãèå çàäà÷è ïîòîêîðàñ-
ïðåäåëåíèÿ. Îñíîâíîé ïðåäìåò èññëåäîâàíèÿ äàííîé ñòàòüè — íåêëàññè÷åñêàÿ çà-
äà÷à ïîòîêîðàñïðåäåëåíèÿ, ó êîòîðîé ðàñõîäû ñðåäû â íåêîòîðûõ óçëàõ íå ôèêñè-
ðîâàíû, à çàâèñÿò îò äàâëåíèÿ â ýòèõ óçëàõ. Ãëàâíàÿ öåëü èññëåäîâàíèé — âûÿñíå-
íèå âîïðîñîâ ñóùåñòâîâàíèÿ è åäèíñòâåííîñòè ðåøåíèÿ ó òàêîé íåêëàññè÷åñêîé
çàäà÷è. Ïðè ýòîì, êàê áóäåò ïîêàçàíî, äàííóþ íåêëàññè÷åñêóþ çàäà÷ó ïîòîêîðàñ-
ïðåäåëåíèÿ ìîæíî ïðåäñòàâèòü â âèäå çàäà÷ âûïóêëîãî ïðîãðàììèðîâàíèÿ, ÷òî
äàåò áîëüøèå âîçìîæíîñòè âûáîðà ýôôåêòèâíûõ ìåòîäîâ åå ðåøåíèÿ.
Íåîáõîäèìîñòü èññëåäîâàíèÿ òàêîé íåêëàññè÷åñêîé çàäà÷è ïîòîêîðàñïðåäåëå-
íèÿ âûçâàíà òåì, ÷òî íà ïðàêòèêå ïðè ðàñ÷åòå ðåæèìîâ ôóíêöèîíèðîâàíèÿ òðóáîï-
ðîâîäíûõ ñèñòåì íåðåäêî èìååò ìåñòî ñèòóàöèÿ, êîãäà ðàñõîäû ñðåäû âîâíå èëè
èçâíå òðóáîïðîâîäíîé ñèñòåìû çàâèñÿò îò äàâëåíèÿ. Òàê, â öåíòðàëèçîâàííûõ ñèñ-
òåìàõ âîäîñíàáæåíèÿ ðàñõîä âîäû ó ïîòðåáèòåëåé çàâèñèò îò äàâëåíèÿ â òî÷êàõ îò-
áîðà. Ñîãëàñíî [4] êàæäàÿ àòìîñôåðà äàâëåíèÿ, ïðåâûøàþùàÿ íîðìàòèâíîå â óçëå
îòáîðà, óâåëè÷èâàåò íà 5–8 % ðàñõîä âîäû â ýòîì óçëå. Òàêæå ðàñõîä âîäû, ïîñòó-
ïàþùåé â ðåçåðâóàðû è âîäîíàïîðíûå áàøíè, ñóùåñòâåííî çàâèñèò îò äàâëåíèÿ
â ìåñòàõ ïðèñîåäèíåíèÿ ðåçåðâóàðîâ ê ñèñòåìå. Åñëè óçåë ïðåäñòàâëÿåò èñòî÷íèê
ïîñòóïàþùåé â òðóáîïðîâîäíóþ ñèñòåìó æèäêîñòè — íàñîñíóþ ñòàíöèþ, òî åãî
òàêæå ìîæíî è ñëåäóåò ðàññìàòðèâàòü êàê óçåë ñ íåôèêñèðîâàííûìè ðàñõîäàìè.
 ýòîì óçëå îáúåì çàêà÷èâàåìîé æèäêîñòè â åäèíèöó âðåìåíè óìåíüøàåòñÿ ïðè
óâåëè÷åíèè äàâëåíèÿ.
Ñíà÷àëà ðàññìîòðèì êëàññè÷åñêóþ çàäà÷ó ïîòîêîðàñïðåäåëåíèÿ è åå îñíîâíûå
ñâîéñòâà . Çàòåì íà áàçå êëàññè÷åñêîé çàäà÷è ðàññìîòðèì íåêëàññè÷åñêóþ çàäà÷ó
ñ ðàñõîäàìè â îòäåëüíûõ óçëàõ, çàâèñÿùèìè îò äàâëåíèÿ â íèõ. Ïðè ýòîì áóäåì
ïîëüçîâàòüñÿ îáîçíà÷åíèÿìè, ââåäåííûìè äëÿ êëàññè÷åñêîé çàäà÷è. Ïðèâîäèìûå
ôàêòû î ñâîéñòâàõ èçó÷àåìîé íåêëàññè÷åñêîé çàäà÷è ïîòîêîðàñïðåäåëåíèÿ áóäóò
ðàññìàòðèâàòüñÿ êàê ðàçâèòèå àíàëîãè÷íûõ ôàêòîâ î ñâîéñòâàõ êëàññè÷åñêîé çàäà÷è.
Èçëîæåíèå ðåçóëüòàòîâ äëÿ êàæäîé èç äâóõ ÷àñòåé (ò.å. äëÿ êëàññè÷åñêîé è çà-
òåì íåêëàññè÷åñêîé çàäà÷ ïîòîêîðàñïðåäåëåíèÿ) âåäåòñÿ â äâà ýòàïà. Ñíà÷àëà èñ-
ñëåäóþòñÿ çàäà÷è ïîèñêà ðåøåíèÿ ñèñòåìû óðàâíåíèé è íåðàâåíñòâ îáùåãî âèäà,
íå ó÷èòûâàþùèå ñïåöèôèêó ìîäåëåé ïîòîêîðàñïðåäåëåíèÿ.  ÷àñòíîñòè, â ýòèõ çà-
äà÷àõ èñïîëüçóåòñÿ íåêîòîðàÿ ïðîèçâîëüíàÿ ìàòðèöà A âåùåñòâåííûõ ÷èñåë ðàçìå-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 1 81
© Ñ.Ï. Åïèôàíîâ, Â.È. Çîðêàëüöåâ, 2011
ðà m n� . Çàòåì ïîëó÷åííûå ðåçóëüòàòû èçëàãàþòñÿ ïðèìåíèòåëüíî ê ìîäåëÿì ïîòî-
êîðàñïðåäåëåíèÿ, ó êîòîðûõ A — ìàòðèöà èíöèäåíöèé ãðàôà ãèäðàâëè÷åñêîé öåïè.
Îñíîâíûì èíñòðóìåíòîì èññëåäîâàíèé çäåñü áóäåò òåîðèÿ ñèììåòðè÷íîé äâîé-
ñòâåííîñòè äëÿ çàäà÷ âûïóêëîãî ïðîãðàììèðîâàíèÿ ñ ëèíåéíûìè îãðàíè÷åíèÿ-
ìè [5], îñíîâàííàÿ íà èñïîëüçîâàíèè ñâîéñòâ ñîïðÿæåííûõ ôóíêöèé Ôåíõåëÿ [6].
ÝÊÂÈÂÀËÅÍÒÍÛÅ ÑÈÑÒÅÌÀ ÓÐÀÂÍÅÍÈÉ È ÇÀÄÀ×È ÎÏÒÈÌÈÇÀÖÈÈ,
ÊËÀÑÑÈ×ÅÑÊÀß ÇÀÄÀ×À ÏÎÒÎÊÎÐÀÑÏÐÅÄÅËÅÍÈß
 äàííîì ðàçäåëå ïðèâåäåì ñèñòåìó óðàâíåíèé è íåñêîëüêî çàäà÷ îïòèìèçàöèè
ñ îäíèì è òåì æå ñîñòàâîì èñõîäíûõ äàííûõ. Õîòÿ âñå ðàññìàòðèâàåìûå çäåñü çàäà-
÷è âíåøíå ñóùåñòâåííî ðàçëè÷àþòñÿ, îíè ðàâíîñèëüíû: ëèáî âñå íå èìåþò ðåøåíèÿ,
ëèáî âñå èìåþò ðåøåíèÿ, è ðåøåíèå ëþáîé èç íèõ ÿâëÿåòñÿ ðåøåíèåì îñòàëüíûõ.
 ÷àñòíîì ñëó÷àå ïðè ñïåöèôè÷åñêîé ñòðóêòóðå èñõîäíûõ äàííûõ ïðèâîäè-
ìûå çäåñü ñèñòåìà óðàâíåíèé è ïðîáëåìû îïòèìèçàöèè, êàê áóäåò ïîêàçàíî, ÿâëÿ-
þòñÿ ýêâèâàëåíòíûìè ôîðìàìè çàïèñè êëàññè÷åñêîé çàäà÷è ïîòîêîðàñïðåäåëåíèÿ.
Ðàçíûå ôîðìû çàïèñè ýòîé çàäà÷è ìîãóò áûòü ïîëåçíû äëÿ èçó÷åíèÿ åå ñâîéñòâ è
ðàçðàáîòêè àëãîðèòìîâ åå ðåøåíèÿ. Íåêîòîðûå, ïðèâåäåííûå çäåñü ôàêòû î ñâîé-
ñòâàõ è âçàèìîñâÿçÿõ ðàçíûõ ôîðìóëèðîâîê êëàññè÷åñêîé çàäà÷è ïîòîêîðàñïðåäå-
ëåíèÿ è ïîëó÷åííûå íà ýòîé îñíîâå íîâûå ðåçóëüòàòû â òåîðèè ãèäðàâëè÷åñêèõ
öåïåé, ïîäðîáíî èçëîæåíû â ðàáîòàõ [5, 7].
Îñíîâíàÿ öåëü äàííîãî ðàçäåëà ñîñòîèò â èçëîæåíèè òåîðåòè÷åñêîé áàçû, èñ-
ïîëüçóåìîé ïðè èçó÷åíèè êëàññè÷åñêîé çàäà÷è ïîòîêîðàñïðåäåëåíèÿ, íà îñíîâå
ðàçâèòèÿ êîòîðîé áóäåò èññëåäîâàòüñÿ çàäà÷à ïîòîêîðàñïðåäåëåíèÿ ñ íåôèêñèðî-
âàííûìè ðàñõîäàìè.
Èñõîäíûå äàííûå. Ïóñòü çàäàíû âåêòîðû b R c Rm n� �, , ìàòðèöà A ðàçìåðà
m n� , à òàêæå ôóíêöèè âåùåñòâåííîãî àðãóìåíòà f j ïðè j n�1, ,� , ïðè÷åì ôóíê-
öèè f j âîçðàñòàþùèå, íåïðåðûâíûå, ïðèíèìàþùèå çíà÷åíèÿ îò �� äî � � è ðàâíû
íóëþ â íóëå.
Ìíîæåñòâî ôóíêöèé, îáëàäàþùèõ óêàçàííûìè ñâîéñòâàìè, îáîçíà÷èì
~
Z.
Èòàê,
~
Z ñîñòîèò èç ôóíêöèé w âåùåñòâåííîãî àðãóìåíòà òàêèõ, ÷òî
w w R( ) ( ) , , ,� � � � � �� � � (1)
lim ( ) ( ) ,
� �
� � �
� �w w R (2)
lim ( ) , lim ( ) ,
� �
� �
��
��
� �� � � �w w (3)
w( ) .0 0� (4)
Çäåñü R — ìíîæåñòâî âåùåñòâåííûõ ÷èñåë.
Èç (1)–(4) ñëåäóåò, ÷òî äëÿ ëþáîé ôóíêöèè èç
~
Z ñóùåñòâóåò îáðàòíàÿ åé ôóíêöèÿ,
òàêæå ïðèíàäëåæàùàÿ
~
Z. Îáîçíà÷èì � j ôóíêöèþ, îáðàòíóþ f j . Èòàê, � j Z�
~
è
� � � � � � �j j j jf f R j n( ( )) , ( ( )) , , , .� � � �1 � (5)
Êàæäîé ôóíêöèè èç
~
Z ñîîòâåòñòâóåò åäèíñòâåííàÿ ïåðâîîáðàçíàÿ ôóíêöèÿ,
ðàâíàÿ íóëþ â íóëå. Ìíîæåñòâî òàêèõ ïåðâîîáðàçíûõ ôóíêöèé îáîçíà÷èì Z.
 ÷àñòíîñòè, ìíîæåñòâó Z ïðèíàäëåæàò ôóíêöèè
F f d d Rj j j j( ) ( ) , ( ) ( )� � � � � � � �
� �
� � �� �
0 0
�
ïðè j n�1, ,� . Îòìåòèì, ÷òî ôóíêöèè èç Z ñòðîãî âûïóêëûå, èìåþùèå àáñîëþò-
íûé ìèíèìóì, êîòîðûé äîñòèãàåòñÿ â íóëå è ðàâåí íóëþ.
82 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 1
Äâå ôóíêöèè èç Z, ÿâëÿþùèåñÿ ïåðâîîáðàçíûìè äëÿ âçàèìíî îáðàòíûõ ôóíê-
öèé èç
~
Z, íàçûâàþòñÿ ñîïðÿæåííûìè. Ýòî ÷àñòíûé ñëó÷àé ñîïðÿæåííûõ ôóíêöèé
Ôåíõåëÿ [6].  ÷àñòíîñòè, ñîïðÿæåííûìè ÿâëÿþòñÿ ïàðû ôóíêöèé F j è � j äëÿ âñåõ
j n�1, ,� . Äëÿ ñîïðÿæåííûõ ôóíêöèé èç Z âûïîëíÿþòñÿ ñëåäóþùèå óñëîâèÿ [5–7]:
åñëè y f xj j j� ( ), òî F x y x y j nj j j j j j( ) ( ) , , , ,� � �� 1 � (6)
åñëè y f xj j j
( ), òî F x y x y j nj j j j j j( ) ( ) , , , .� � �� 1 � (7)
Ââåäåì ôóíêöèè îò âåêòîðîâ x y R n, � :
F x F x y yj j j j
j
n
j
n
( ) ( ), ( ) ( ).� �
��
�� � �
11
Ïóñòü
f x F x y y( ) ( ), ( ) ( )�� ��� �
— âåêòîð-ôóíêöèè îò âåêòîðîâ x y R n, � ñ êîìïîíåíòàìè f xj j( ) è � j jy( ),
j n�1, ,� .
Ñèñòåìà óðàâíåíèé. Ðàññìîòðèì çàäà÷ó îïðåäåëåíèÿ âåêòîðîâ x R n� ,
y R n� , u R m� , óäîâëåòâîðÿþùèõ óñëîâèÿì
Ax b� , (8)
y A u cT� � , (9)
y f x� ( ). (10)
Ó ýòîé ñèñòåìû óñëîâèÿ (8), (9) ëèíåéíûe, óñëîâèå (10) ñîñòîèò èç n íåëèíåé-
íûõ, â îáùåì ñëó÷àå, îãðàíè÷åíèé.
Îòìåòèì, ÷òî äëÿ ëþáûõ âåêòîðîâ x y u, , , óäîâëåòâîðÿþùèõ óñëîâèÿì (8), (9),
âûïîëíÿåòñÿ ðàâåíñòâî
( , ) ( , ) ( , ),c x b u x y� � (11)
ãäå ( , )� � — ñêàëÿðíîå ïðîèçâåäåíèå âåêòîðîâ. Äåéñòâèòåëüíî,
c x b u y A u x b u y x u Ax b u y x u b Ax yT T T T T T T T T T T� � � � � � � � � � �( ) ( ) x.
Çàìå÷àíèå. Íàëè÷èå íåëèíåéíûõ îãðàíè÷åíèé â ñèñòåìå (8)–(10) îñëîæíÿåò
èçó÷åíèå âîïðîñîâ ñóùåñòâîâàíèÿ è åäèíñòâåííîñòè ðåøåíèÿ íåïîñðåäñòâåííî èç
àíàëèçà ýòîé ñèñòåìû. Èññëåäîâàíèå ýòèõ âîïðîñîâ îáëåã÷àåòñÿ ïðè èñïîëüçîâàíèè
ïðåäñòàâëåíèÿ ñèñòåìû â âèäå ýêñòðåìàëüíûõ ïðîáëåì.
Èñõîäíàÿ çàäà÷à îïòèìèçàöèè: íàéòè âåêòîð x R n� , ÿâëÿþùèéñÿ ðåøåíèåì
ýêñòðåìàëüíîé ïðîáëåìû
F x c x( ) ( , ) min�
(12)
ïðè óñëîâèè (8).
Äëÿ òîãî ÷òîáû âåêòîð x áûë ðåøåíèåì çàäà÷è (12), íåîáõîäèìî è äîñòàòî÷íî,
÷òîáû ñóùåñòâîâàëè âåêòîðû y R n� , u R m� , êîòîðûå âìåñòå ñ äàííûì âåêòîðîì x
ñîñòàâëÿþò ðåøåíèå ñèñòåìû (8)–(10). Ýòî âûòåêàåò èç óñëîâèé îïòèìàëüíîñòè
Ëàãðàíæà äëÿ çàäà÷è (12) [5, 6]. Îòìåòèì, ÷òî õîòÿ çàäà÷à (12) íå ñîäåðæèò â ÿâíîì
âèäå âåêòîðà ïåðåìåííûõ u, îí ïðèñóòñòâóåò â íåé íåÿâíî — ýòî âåêòîð ìíîæèòå-
ëåé Ëàãðàíæà îãðàíè÷åíèé äàííîé çàäà÷è. Ðàñïîëàãàÿ âåêòîðîì x, ïî óñëîâèþ (10)
ìîæíî îïðåäåëèòü âåêòîð y.
Èç ñâîéñòâ (1)–(4) ïðîèçâîäíûõ ôóíêöèé F j nj , , ,�1 � , ñëåäóåò, ÷òî ôóíêöèÿ
F x c x( ) ( , )� ïðè ëþáîì çàäàííîì c R n� ñòðîãî âûïóêëa, è äëÿ ëþáîãî � ìíîæåñ-
òâî âåêòîðîâ x, óäîâëåòâîðÿþùèõ íåðàâåíñòâó
F x c x( ) ( , )� � �,
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 1 83
áóäåò îãðàíè÷åííûì èëè ïóñòûì. Ïîýòîìó åñëè çàäà÷à (12) èìååò äîïóñòèìîå
ïî óñëîâèþ (8) ðåøåíèå, òî îíà èìååò è îïòèìàëüíîå ðåøåíèå, ïðè÷åì ýòî ðå-
øåíèå åäèíñòâåííî.
Èòàê, íåîáõîäèìûì è äîñòàòî÷íûì óñëîâèåì ñóùåñòâîâàíèÿ ðåøåíèÿ çàäà÷è
(12) ÿâëÿåòñÿ ñîâìåñòíîñòü ñèñòåìû ëèíåéíûõ óðàâíåíèé (8). Êîíñòðóêòèâíûé êðè-
òåðèé äëÿ âûÿâëåíèÿ ñëó÷àÿ íåñîâìåñòíîñòè îãðàíè÷åíèé (8) äàåò àëüòåðíàòèâà
Ôðåäãîëüìà [5]: ýòà ñèñòåìà íå áóäåò èìåòü ðåøåíèé â òîì è òîëüêî òîì ñëó÷àå,
åñëè íàéäåòñÿ òàêîé âåêòîð �� R m, ïðè êîòîðîì
A bT T� ��
0 0, . (13)
Äâîéñòâåííàÿ çàäà÷à îïòèìèçàöèè: íàéòè âåêòîðû u R m� , y R n� , ÿâëÿþ-
ùèåñÿ ðåøåíèÿìè ýêñòðåìàëüíîé ïðîáëåìû
�( ) ( , ) miny b u�
(14)
ïðè óñëîâèè (9).
Ïî óñëîâèÿì îïòèìàëüíîñòè Ëàãðàíæà äëÿ òîãî, ÷òîáû âåêòîðû u y, ñîñòàâëÿ-
ëè îïòèìàëüíîå ðåøåíèå çàäà÷è (14), íåîáõîäèìî è äîñòàòî÷íî, ÷òîáû ïðè íåêîòî-
ðîì x R n� äàííûå âåêòîðû ñîñòàâëÿëè ðåøåíèå ñèñòåìû (8)–(10) [5, 7]. Ýòîò âåê-
òîð x ñîñòîèò èç ìíîæèòåëåé Ëàãðàíæà îãðàíè÷åíèé (9) çàäà÷è (14).
Çàäà÷à (14) âñåãäà èìååò äîïóñòèìîå ðåøåíèå. Íàïðèìåð, óñëîâèþ (9) óäîâ-
ëåòâîðÿþò âåêòîðû u y c� �0, . Çàäà÷à (14) ìîæåò íå èìåòü ðåøåíèÿ â òîì è òîëüêî
òîì ñëó÷àå, åñëè öåëåâàÿ ôóíêöèÿ íå îãðàíè÷åíà ñíèçó íà ìíîæåñòâå äîïóñòèìûõ
ðåøåíèé. À ýòî èìååò ìåñòî òîãäà è òîëüêî òîãäà, êîãäà ïðè íåêîòîðîì �
âûïîëíÿþòñÿ óñëîâèÿ (13) [5, 7].
 ñèëó ñòðîãîé âûïóêëîñòè ôóíêöèè�, åñëè çàäà÷à (14) èìååò ðåøåíèå, òî äëÿ
ëþáîãî ðåøåíèÿ âåêòîð y áóäåò åäèíñòâåííûì. Åñëè rank A m� , òî âåêòîð u èç ðå-
øåíèÿ çàäà÷è (14) åäèíñòâåííûé. Âåêòîð u èç ðåøåíèÿ çàäà÷è (14) áóäåò íååäèí-
ñòâåííûì, åñëè rank A m� .
 [5] äîêàçàíà òåîðåìà, îáîáùàþùàÿ ïðèâåäåííûå âûøå óòâåðæäåíèÿ î âçàè-
ìîñâÿçÿõ ñèñòåìû óðàâíåíèé (8)–(10), èñõîäíîé (12) è äâîéñòâåííîé (14) çàäà÷
îïòèìèçàöèè.
Òåîðåìà 1. Äëÿ ðàññìàòðèâàåìûõ òðåõ çàäà÷ (ñèñòåìû óðàâíåíèé (8)–(10), èñ-
õîäíîé çàäà÷è îïòèìèçàöèè (12) è äâîéñòâåííîé çàäà÷è îïòèìèçàöèè (14)) âîçìîæ-
íû òîëüêî äâà ñëó÷àÿ.
1. Âñå îíè íå èìåþò ðåøåíèÿ.  ýòîì ñëó÷àå îãðàíè÷åíèÿ (8) èñõîäíîé çàäà÷è
îïòèìèçàöèè (12) íåñîâìåñòíû, öåëåâàÿ ôóíêöèÿ äâîéñòâåííîé çàäà÷è îïòèìèçà-
öèè (14) íå îãðàíè÷åíà ñíèçó íà ìíîæåñòâå äîïóñòèìûõ ïî âñåì îãðàíè÷åíèÿì
ýòîé çàäà÷è ðåøåíèé.
2. Âñå òðè çàäà÷è èìåþò ðåøåíèå. Åñëè âåêòîðû x y u, , ñîñòàâëÿþò ðåøåíèå
ñèñòåìû óðàâíåíèé (8)–(10), òî âåêòîð x — îïòèìàëüíîå ðåøåíèå çàäà÷è îïòèìè-
çàöèè (12), u — âåêòîð ìíîæèòåëåé Ëàãðàíæà îãðàíè÷åíèé ýòîé çàäà÷è; âåêòîðû
y u, — îïòèìàëüíîå ðåøåíèå äâîéñòâåííîé çàäà÷è (14), ïðè ýòîì x — âåêòîð
ìíîæèòåëåé Ëàãðàíæà ýòîé çàäà÷è.
Äëÿ ðåøåíèé ðàññìàòðèâàåìûõ òðåõ çàäà÷ âåêòîðû x y, åäèíñòâåííû, âåêòîð u
ìîæåò áûòü íååäèíñòâåííûì â òîì è òîëüêî òîì ñëó÷àå, åñëè rank A m� .
Îòìåòèì, ÷òî èç óñëîâèé (6), (7) è ðàâåíñòâà (11) âûòåêàþò ñëåäóþùèå óòâåð-
æäåíèÿ. Åñëè âåêòîðû x y u, , óäîâëåòâîðÿþò ëèíåéíûì îãðàíè÷åíèÿì (8), (9), òî
F x y c x b u( ) ( ) ( , ) ( , ) ,� � � �� 0 F x y x y( ) ( ) ( , ) .� � �� 0
Òàêèå âåêòîðû áóäóò óäîâëåòâîðÿòü óñëîâèþ (10) â òîì è òîëüêî òîì ñëó÷àå,
åñëè
F x y c x b u( ) ( ) ( , ) ( , ) ,� � � �� 0 F x y x y( ) ( ) ( , ) .� � �� 0
84 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 1
Ïîýòîìó â ñèñòåìå (8)–(10) óñëîâèÿ (10) ìîæíî çàìåíèòü íà ëþáîå èç ýòèõ ðàâåíñòâ.
Êëàññè÷åñêàÿ çàäà÷à ïîòîêîðàñïðåäåëåíèÿ.  ÷àñòíîì ñëó÷àå ïðè ìàòðèöå
A ñïåöèàëüíîãî âèäà ïðåäñòàâëåííûå âûøå ñèñòåìà óðàâíåíèé è çàäà÷è îïòèìèçà-
öèè ÿâëÿþòñÿ ðàçíûìè ýêâèâàëåíòíûìè ôîðìàìè çàïèñè êëàññè÷åñêîé çàäà÷è ïî-
òîêîðàñïðåäåëåíèÿ.
Ñòðóêòóðà ìîäåëèðóåìîé ãèäðàâëè÷åñêîé ñèñòåìû ìîæåò áûòü îïèñàíà îðèåí-
òèðîâàííûì ãðàôîì. Ïóñòü m — ÷èñëî óçëîâ, n — ÷èñëî äóã ýòîãî ãðàôà, òîãäà A
— ìàòðèöà èíöèäåíòíîñòè ðàçìåðà m n� ñ ýëåìåíòàìè: aij �1, åñëè äóãà j âûõîäèò
èç óçëà i; aij � �1, åñëè äóãà j âõîäèò â óçåë i; aij � 0, åñëè äóãà j íå èíöèäåíòíà
óçëó i. Â êàæäîì ñòîëáöå òàêîé ìàòðèöû òîëüêî äâà íåíóëåâûõ ýëåìåíòà: îäèí ðà-
âåí +1, äðóãîé ðàâåí –1. Ñëåäîâàòåëüíî, ñóììà âñåõ ñòðîê ìàòðèöû A áóäåò íóëå-
âîé ñòðîêîé, ò.å. ýòà ìàòðèöà èìååò ðàíã, ìåíüøèé m. Äàëåå áóäåì ñ÷èòàòü, ÷òî ðàñ-
ñìàòðèâàåìûé ãðàô ñâÿçíûé. Òîãäà rank A m� �1.
Êîìïîíåíòû âåêòîðà b — çàäàííûå äëÿ óçëîâ i m�1, ,� ðàñõîäû ñðåäû, ïî-
ñòàâëÿåìûå èçâíå (åñëè bi � 0 ) â ñèñòåìó èëè âîâíå (åñëè bi � 0 ) èç ñèñòåìû. Êîì-
ïîíåíòû c j , j n�1, ,� , âåêòîðà c — çàäàííûå ïðèðàùåíèÿ äàâëåíèÿ íà îòäåëüíûõ
äóãàõ. Åñëè c j � 0, òî ïðîèñõîäèò ïðèðàùåíèå äàâëåíèÿ íà äóãå j, åñëè c j � 0 —
äðîññåëèðîâàíèå äàâëåíèÿ íà äóãå j. Êîìïîíåíòû âåêòîðîâ ïåðåìåííûõ x è y —
âåëè÷èíû ðàñõîäîâ è ïîòåðü äàâëåíèÿ íà îòäåëüíûõ äóãàõ.
Êîìïîíåíòû âåêòîðà ïåðåìåííûõ u õàðàêòåðèçóþò äàâëåíèå â óçëàõ
i m�1, ,� .
Óðàâíåíèå (8) âûðàæàåò áàëàíñ ðàñõîäîâ âî âñåõ óçëàõ. Ïîêîìïîíåíòíûå ðà-
âåíñòâà (8) â ýòîì ñëó÷àå åùå íàçûâàþòñÿ óðàâíåíèÿìè íåðàçðûâíîñòè ïîòîêà.
Óðàâíåíèå (9) îïðåäåëÿåò áàëàíñ ìåæäó ïåðåïàäîì äàâëåíèÿ ( )A uT
j è àëãåá-
ðàè÷åñêîé ñóììîé ïîòåðè y j è ïðèðàùåíèÿ c j äàâëåíèÿ íà êàæäîé äóãå j.
Ñîîòíîøåíèå (10) âûðàæàåò çàâèñèìîñòè ìåæäó ðàñõîäîì x j è ïîòåðåé äàâëå-
íèÿ yj ïî âñåì äóãàì j n�1, ,� .
Íåîáõîäèìûì óñëîâèåì ñóùåñòâîâàíèÿ ðåøåíèÿ êëàññè÷åñêîé çàäà÷è ïîòîêî-
ðàñïðåäåëåíèÿ ÿâëÿåòñÿ âûïîëíåíèå ðàâåíñòâà
bi
i
m
�
� �
1
0 . (15)
Èíà÷å äëÿ âåêòîðà �, ñîñòîÿùåãî èç åäèíèö, ñïðàâåäëèâî (13).  ñëó÷àå åñëè
ãðàô ãèäðàâëè÷åñêîé öåïè ÿâëÿåòñÿ ñâÿçíûì, óñëîâèå (15) ÿâëÿåòñÿ äîñòàòî÷íûì
äëÿ ñóùåñòâîâàíèÿ ðåøåíèÿ, åñëè ôóíêöèè f j óäîâëåòâîðÿþò óñëîâèÿì (1)–(4).
Ðàçíûå ðàâíîñèëüíûå ôîðìû çàïèñè êëàññè÷åñêîé çàäà÷è ïîòîêîðàñïðåäåëå-
íèÿ, â òîì ÷èñëå ïðèâåäåííûå çäåñü, ìîãóò áûòü ïîëåçíû äëÿ êîíñòðóèðîâàíèÿ àë-
ãîðèòìîâ ðåøåíèÿ çàäà÷è.  ÷àñòíîñòè, áîëüøîå êîëè÷åñòâî ðàçëè÷íûõ ìåòîäîâ
âûïóêëîãî ïðîãðàììèðîâàíèÿ ìîæåò èñïîëüçîâàòüñÿ äëÿ ðåøåíèÿ èñõîäíîé (12) è
äâîéñòâåííîé (14) çàäà÷ îïòèìèçàöèè.
Çàìûêàþùèå ñîîòíîøåíèÿ.  òåîðèè ãèäðàâëè÷åñêèõ öåïåé [1, 2] çàâèñè-
ìîñòè ìåæäó ðàñõîäàìè ñðåäû x j íà âåòâè j è ïåðåïàäîì äàâëåíèÿ yj ïðèíÿòî íà-
çûâàòü «çàìûêàþùèìè ñîîòíîøåíèÿìè». Èõ âûðàæàþò ôóíêöèè f j è � j . Â ðàáî-
òàõ ïî ãèäðàâëè÷åñêèì öåïÿì ÷àñòî ðàññìàòðèâàåòñÿ ñòåïåííàÿ ôóíêöèÿ
f x r x x j nj j j j
t
j( ) | | , , ,� �sign 1 � ,
ïðè çàäàííûõ r tj � �0 0, . Îáðàòíîé åé áóäåò òàêæå ñòåïåííàÿ ôóíêöèÿ
� �j j j j
q
jy y y j n( ) | | , , ,� �sign 1 � ,
ïðè çàäàííûõ � j q� �0 0, , ïðè÷åì äîëæíû âûïîëíÿòüñÿ ñîîòíîøåíèÿ
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 1 85
tq r r j nj
t
j j j
q� � � �1 1 1 1, , , , , ,� � �
ãàðàíòèðóþùèå, ÷òî ôóíêöèè f j è � j âçàèìíî îáðàòíûå. Ïðè ðàñ÷åòàõ îáû÷íî
ðàññìàòðèâàåòñÿ ñëó÷àé t � 2 . Òîãäà q �1 2/ . Äàííûå ñòåïåííûå ôóíêöèè óäîâ-
ëåòâîðÿþò óñëîâèÿì (1)–(4).
À.Ï. Ìåðåíêîâ â [1] äëÿ ñòåïåííîé ôóíêöèè ñ t� [ , ]1 2 ñôîðìóëèðîâàë è äîêà-
çàë óòâåðæäåíèå î åäèíñòâåííîñòè ðåøåíèÿ (åñëè ñóùåñòâóåò, òî åäèíñòâåííîå)
êëàññè÷åñêîé çàäà÷è ïîòîêîðàñïðåäåëåíèÿ. Ïîä åäèíñòâåííîñòüþ ðåøåíèÿ çäåñü
ïîíèìàåòñÿ òîëüêî åäèíñòâåííîñòü âåêòîðîâ x è y. Âåêòîð u íååäèíñòâåííûé â ðå-
øåíèè, ïîñêîëüêó â êëàññè÷åñêîé çàäà÷å ïîòîêîðàñïðåäåëåíèÿ rank A m� .
Ïðàêòè÷åñêèé èíòåðåñ ìîãóò ïðåäñòàâëÿòü íå òîëüêî ñòåïåííûå çàâèñèìîñòè.
Íàïðèìåð, â [1] îñîáî âûäåëÿëàñü êàê ïîòåíöèàëüíî ïîëåçíàÿ ôóíêöèÿ
f x x x xj j j j j j j( ) � �� � 2 sign
ïðè çàäàííûõ � �j j� 0, . Âîçìîæíîñòè èñïîëüçîâàíèÿ òàêîé ôóíêöèè, âåðîÿòíî, ñâÿ-
çàíû ñ òåì, ÷òî ïðè ìàëîì ïî àáñîëþòíîé âåëè÷èíå ðàñõîäå x j áóäåò ïðåâàëèðîâàòü
ëèíåéíàÿ çàâèñèìîñòü, ÷òî ñîîòâåòñòâóåò òðåíèþ ïðè ëàìèíàðíîì ðåæèìå òå÷åíèÿ
ñðåäû. Ïðè óâåëè÷åíèè àáñîëþòíîãî çíà÷åíèÿ x j ïðåâàëèðóþùåé ñòàíîâèòñÿ êâàäðà-
òè÷íàÿ çàâèñèìîñòü, îòðàæàþùàÿ òðåíèå ïðè ïîòîêàõ ñ òóðáóëåíòíîñòÿìè. Äàííàÿ
ôóíêöèÿ, êàê è îáðàòíàÿ åé, òàêæå óäîâëåòâîðÿåò óñëîâèÿì (1)–(4).
Äëÿ çàäàíèÿ âèäà âîçìîæíûõ çàìûêàþùèõ ñîîòíîøåíèé èñïîëüçîâàëñÿ è àê-
ñèîìàòè÷åñêèé ïîäõîä ïóòåì ââåäåíèÿ íàáîðà òðåáîâàíèé ê ôóíêöèÿì f j .  [4]
ïðåäëîæåíà ñëåäóþùàÿ ñèñòåìà òðåáîâàíèé. Ôóíêöèè f j äîëæíû áûòü: 1) íåïðå-
ðûâíî äèôôåðåíöèðóåìûìè, 2) íå÷åòíûìè, 3) ìîíîòîííî âîçðàñòàþùèìè, 4) ðàâ-
íûìè íóëþ â íóëå.  ýòîì íàáîðå ïîñëåäíåå òðåáîâàíèå èçáûòî÷íîå, ïîñêîëüêó ðà-
âåíñòâî çíà÷åíèÿ ôóíêöèè íóëþ â íóëå ñëåäóåò èç íå÷åòíîñòè ôóíêöèè.
Á.Í. Ïøåíè÷íûé äëÿ ïàññèâíîé ãèäðàâëè÷åñêîé öåïè, ò.å. êîãäà c � 0, ïðè óêà-
çàííûõ âûøå òðåáîâàíèÿõ ê ôóíêöèÿì f j , äîêàçàë åùå â 1962 ã. óòâåðæäåíèå î ñó-
ùåñòâîâàíèè è åäèíñòâåííîñòè ðåøåíèÿ êëàññè÷åñêîé çàäà÷è ïîòîêîðàñïðåäåëåíèÿ
(ïðè ýòîì ÷åòâåðòîå òðåáîâàíèå îí íå ââîäèë).
Ðàññìàòðèâàåìûå â äàííîé ñòàòüå óñëîâèÿ (1), (2), (4) îñëàáëÿþò ïåðâûå òðè òðå-
áîâàíèÿ èç [1]. Íåò íåîáõîäèìîñòè â íåïðåðûâíîé äèôôåðåíöèðóåìîñòè — äîñòàòî÷-
íî òîëüêî íåïðåðûâíîñòè ôóíêöèé f j . Íå òðåáóåòñÿ è íå÷åòíîñòè ýòèõ ôóíêöèé —
äîñòàòî÷íî, ÷òîáû îíè áûëè âîçðàñòàþùèìè, ïðèíèìàþùèìè íóëåâûå çíà÷åíèÿ â
íóëå. Ýòî, â ÷àñòíîñòè, ïîçâîëÿåò ðàññìàòðèâàòü âîçìîæíûå ñëó÷àè ðàçíûõ ãèäðàâëè-
÷åñêèõ ñîïðîòèâëåíèé íà îäíîé è òîé æå äóãå, â çàâèñèìîñòè îò íàïðàâëåíèÿ ïîòîêà
ñðåäû â íåé. Ìîæíî îòìåòèòü, ÷òî âûïîëíåíèå òðåáîâàíèé (1), (2), (4) äîñòàòî÷íî äëÿ
äîêàçàòåëüñòâà óòâåðæäåíèÿ Á.Í. Ïøåíè÷íîãî: ñóùåñòâîâàíèÿ è åäèíñòâåííîñòè ðå-
øåíèÿ çàäà÷è ïîòîêîðàñïðåäåëåíèÿ ïðè c � 0 è íåïðîòèâîðå÷èâîñòè óñëîâèÿ (8).
Èñõîäÿ òîëüêî èç òðåáîâàíèé (1), (2), (4), íåëüçÿ äîêàçàòü ñóùåñòâîâàíèå ðåøåíèÿ
çàäà÷è ïîòîêîðàñïðåäåëåíèÿ ïðè ëþáîì c R n� . Âìåñòå ñ òåì òðåáîâàíèå (3) ìîæíî
îñëàáèòü. Íàïðèìåð, âìåñòî (3) äîñòàòî÷íî, ÷òîáû ïðè äàííîì c R n� âûïîëíÿëèñü
óñëîâèÿ: f x cj j j( ) � ïðè íåêîòîðîì x j � 0 è f x cj j j( ) � ïðè íåêîòîðîì x j � 0 äëÿ
âñåõ j n�1, ,� . Ýòîãî óñëîâèÿ äîñòàòî÷íî, ÷òîáû ìíîæåñòâî äîïóñòèìûõ ðåøåíèé çà-
äà÷è (12) ñî çíà÷åíèåì öåëåâîé ôóíêöèè, íå ïðåâîñõîäÿùåì ëþáîé äàííûé óðîâåíü,
áûëî îãðàíè÷åííûì. Ýòî âìåñòå ñî ñòðîãîé âûïóêëîñòüþ F äàåò ñóùåñòâîâàíèå è åäè-
íñòâåííîñòü ðåøåíèÿ çàäà÷è (12). Îòñþäà, â ÷àñòíîñòè, ñëåäóåò, ÷òî óñëîâèå (3) ìî-
æåò íå ââîäèòüñÿ äëÿ ôóíêöèé f j ïðè c j � 0 äëÿ äàííîé âåòâè j.
ÇÀÄÀ×À ÏÎÒÎÊÎÐÀÑÏÐÅÄÅËÅÍÈß Ñ ÐÀÑÕÎÄÀÌÈ Â ÓÇËÀÕ,
ÇÀÂÈÑßÙÈÌÈ ÎÒ ÄÀÂËÅÍÈß
Ïóñòü â íåêîòîðûõ óçëàõ ðàñõîäû ÿâëÿþòñÿ ôóíêöèÿìè îò äàâëåíèÿ â íèõ, ò.å.
86 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 1
â óñëîâèè (8) âìåñòî çàäàííûõ âåëè÷èí bi èñïîëüçóþòñÿ ôóíêöèè
~
( )b ui i . Áóäåì
ñ÷èòàòü òàêîâûìè ïåðâûå m1 óçëîâ.  îñòàëüíûõ óçëàõ ðàñõîäû — ïî-ïðåæíåìó
ôèêñèðîâàííûå âåëè÷èíû. Îáîçíà÷èì m2 ÷èñëî ýòèõ óçëîâ, m m m2 1� � . Èòàê,
â ñèñòåìå (8)–(10) óñëîâèå (8) çàìåíÿåòñÿ íà óñëîâèÿ
A x b u1 �
~
( ), A x b2
2� ,
ãäå A A1 2, — ìàòðèöû ðàçìåðîâ m n1� è m n2 � , ñîñòàâëÿþùèå èñõîäíóþ ìàòðè-
öó A,
A
A
A
�
�
�
�
�
�
�
1
2
.
Âåêòîð b 2 èç R
m2 ñîñòîèò èç ïîñëåäíèõ m2 êîìïîíåíò âåêòîðà b â óñëîâèè (8).
Âåêòîð-ôóíêöèÿ
~
( )b u ñîñòîèò èç ôóíêöèé
~
( ), , ,b u i mi i �1 1� .
Áóäåì ñ÷èòàòü, ÷òî
~
( ) ( )b u b g ui i i i i� �1 , ãäå bi
1 — çàäàííàÿ âåëè÷èíà ðàñõîäà
â óçëå i ïðè íóëåâîì äàâëåíèè, gi — íåïðåðûâíàÿ, âîçðàñòàþùàÿ ôóíêöèÿ, ðàâíàÿ
íóëþ â íóëå, ò.å. ôóíêöèè gi óäîâëåòâîðÿþò óñëîâèÿì (1), (2), (4). Èç ýòèõ óñëîâèé
ñëåäóåò, ÷òî ñóùåñòâóþò âåëè÷èíû
p g r gi i i i� �
��
�
lim ( ), lim ( )
� �
� �
òàêèå, ÷òî p ri i� �0 . Åñëè p ri i� �� ��, , òî ôóíêöèÿ gi ïðèíàäëåæèò ââåäåííî-
ìó â íà÷àëå ñòàòüè êëàññó ôóíêöèé
~
Z. Äàëåå áóäåì ñ÷èòàòü, ÷òî pi è ri ìîãóò ïðè-
íèìàòü è êîíå÷íûå çíà÷åíèÿ, ò.å. óñëîâèÿ (3) äëÿ ôóíêöèé gi ìîãóò íå âûïîëíÿòü-
ñÿ, è ïîýòîìó ýòè ôóíêöèè ïðèíàäëåæàò áîëåå øèðîêîìó, ÷åì
~
Z, êëàññó ôóíêöèé.
Èç (1), (2) ñëåäóåò, ÷òî ñóùåñòâóåò îáðàòíàÿ gi ôóíêöèÿ, çàäàííàÿ íà îòêðûòîì
èíòåðâàëå (p ri i, ). Îáîçíà÷èì åå d i . Èòàê, ïðè ëþáîì âåùåñòâåííîì �
d gi i( ( )) ,� ��
ïðè÷åì d i áóäåò âîçðàñòàþùåé, íåïðåðûâíîé è ðàâíîé íóëþ â íóëå. Äëÿ ôóíê-
öèé gi , d i âåäåì ïåðâîîáðàçíûå ôóíêöèè, ðàâíûå íóëþ â íóëå. Ïóñòü
G g d R D d d p ri i i i i i( ) ( ) , ( ) ( ) ( , ).� � � � � � � �
� �
� � � �� �
0 0
Îòìåòèì, ÷òî ôóíêöèè Di , êàê è èõ ïðîèçâîäíûå d i , îïðåäåëåíû òîëüêî íà îò-
êðûòîì èíòåðâàëå (p ri i, ). Ôóíêöèè Gi è Di óäîâëåòâîðÿþò óñëîâèþ ñîïðÿæåííîñ-
òè Ôåíõåëÿ. Ïðè ëþáûõ i m�1 1, ,� , u z p ri i i i� �� � �( , ), ( , ) :
åñëè z g ui i i� ( ), òî D z G u z ui i i i i i( ) ( ) ,� � (16)
åñëè z g ui i i
( ), òî D z G u z ui i i i i i( ) ( ) .� � (17)
Ðàññìîòðèì ñèñòåìó óðàâíåíèé è íåðàâåíñòâ îòíîñèòåëüíî âåêòîðîâ ïåðåìåí-
íûõ x R z R u R u Rn m m m� � � �, , ,1 1 21 2 :
A x z b1
1� � , (18)
A x b2
2� , (19)
y A u A u cT T� � �1
1
2
2 , (20)
x y j nj j j� �� ( ), , , ,1 � (21)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 1 87
z g u i mi i i� �( ), , , ,1 1� (22)
p z r i mi i i� � �, , , .1 1� (23)
Îòìåòèì, ÷òî ñèñòåìà (18)–(22) èìååò ïî÷òè òàêîé æå âèä, êàê è ñèñòåìà
(8)–(10), òîëüêî ïðèìåíèòåëüíî ê ðàñøèðåííîìó íàáîðó ïåðåìåííûõ è ìàòðèöå
A
A I
A
�
�
�
�
�
�
�1
2 0
,
ãäå I — åäèíè÷íàÿ ìàòðèöà ðàçìåðà m m1 1� , 0 — ìàòðèöà ðàçìåðà m m2 1� , ñî-
ñòîÿùàÿ èç íóëåé. Íàáîð ïåðåìåííûõ ðàñøèðÿåòñÿ çà ñ÷åò äîáàâëåíèÿ ê âåêòîðó
x âåêòîðà ïåðåìåííûõ z R
m� 1 . Äëÿ ýòèõ äîïîëíèòåëüíûõ ïåðåìåííûõ àíàëîã
êîìïîíåíò âåêòîðà c ñ÷èòàåì ðàâíûì íóëþ. Îáîçíà÷èì � âåêòîð R
m2 , ÿâëÿþ-
ùèéñÿ àíàëîãîì âåêòîðà y äëÿ äîïîëíèòåëüíûõ ïåðåìåííûõ. Ñ ó÷åòîì îñîáåí-
íîñòåé ìàòðèöû A àíàëîã óðàâíåíèÿ (9) èìååò âèä
� i iu i m� � �0 1 1, , , ,�
ò.å.
� i iu i m� �, , , ,1 1�
÷òî è ó÷òåíî â âûðàæåíèè (22), ÿâëÿþùèìñÿ àíàëîãîì (10).
Åñëè áû d Zi �
~
äëÿ âñåõ i m�1 1, ,� , òî óñëîâèå (23) áûëî áû èçëèøíèì, ïî-
ñêîëüêó p ri i� �� ��, äëÿ âñåõ i m�1 1, ,� .  ýòîì ñëó÷àå íà ñèñòåìó (18)–(23)
ìîæíî íåïîñðåäñòâåííî ïåðåíåñòè âñå ôàêòû, óñòàíîâëåííûå ðàíåå äëÿ ñèñòåìû
(8)–(10). Äîêàæåì, ÷òî ñâîéñòâà ñèñòåìû (8)–(10) ìîæíî ïåðåíåñòè íà ñèñòåìó
(18)–(23) è â ñëó÷àå, êîãäà d Zi
~
, ò.å. êîãäà âñå èëè íåêîòîðûå èç âåëè÷èí p ri i, êî-
íå÷íûe, â ñèëó ÷åãî íåðàâåíñòâà (23) ñòàíîâÿòñÿ ñóùåñòâåííûìè.
Ââåäåì ôóíêöèè îò âåêòîðîâ R
m1 :
D z D zi i
i
m
( ) ( )�
�
�
1
1
ïðè p z r� � ,
G u G ui i
i
m
( ) ( )1 1
1
1
�
�
� ïðè u R
m1 1� ,
ãäå p r, — âåêòîðû R
m1 , ñîñòàâëåííûå èç âåëè÷èí pi è r i mi , , ,�1 1� . Ïîñêîëüêó
âñå ôóíêöèè D Gi i, ñòðîãî âûïóêëûå, èìåþùèå àáñîëþòíûé ìèíèìóì â íóëå, òî
ôóíêöèè D z( ) è G u( )1 òàêæå áóäóò ñòðîãî âûïóêëûìè, àáñîëþòíûé ìèíèìóì ó
íèõ áóäåò äîñòèãàòüñÿ ïðè íóëåâîì çíà÷åíèè âåêòîðîâ ïåðåìåííûõ. Îòìåòèì,
÷òî åñëè íåêîòîðûå êîìïîíåíòû âåêòîðà ïåðåìåííûõ äîñòèãàþò ãðàíèö èíòåðâà-
ëà îïðåäåëåíèÿ ôóíêöèè D, ò.å. z pi i� èëè z ri i� ïðè íåêîòîðûõ i m�{ }1 1, ,� ,
òî ñ÷èòàåì D zi i( ) �� è, ñëåäîâàòåëüíî, D z( ) ��.
Èñõîäíàÿ çàäà÷à îïòèìèçàöèè: íàéòè âåêòîðû x R z Rn m� �, 1 , ÿâëÿþùèåñÿ
ðåøåíèåì ýêñòðåìàëüíîé ïðîáëåìû
R x z F x D z c x( , ) ( ) ( ) ( , ) min! � �
(24)
ïðè óñëîâèÿõ (18), (19) è îãðàíè÷åíèè
p z r i mi i i� � �, , , .1 1� (25)
Çäåñü îãðàíè÷åíèÿ (25) ÿâëÿþòñÿ ðàñøèðåíèåì óñëîâèé (23), îáåñïå÷èâàþùèõ
çàìêíóòîñòü ìíîæåñòâà äîïóñòèìûõ ðåøåíèé çàäà÷è (24).
Âîçìîæíû òðè ñëó÷àÿ. Çàäà÷à (24) íå èìååò äîïóñòèìûõ ðåøåíèé: åå îãðàíè-
88 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 1
÷åíèÿ íåñîâìåñòíû. Òîãäà îíà íå èìååò è îïòèìàëüíûõ ðåøåíèé.
Âòîðîé ñëó÷àé — äëÿ ëþáûõ äîïóñòèìûõ ðåøåíèé íåêîòîðûå êîìïîíåíòû
âåêòîðà z ïðèíèìàþò ãðàíè÷íûå ïî óñëîâèÿì (25) çíà÷åíèÿ. Ñëåäîâàòåëüíî, ïðè
ëþáîì äîïóñòèìîì ðåøåíèè çíà÷åíèå öåëåâîé ôóíêöèè ðàâíî �. Ñëåäîâàòåëüíî,
è äëÿ «îïòèìàëüíîãî» ðåøåíèÿ (îíî íóæäàåòñÿ çäåñü â äîîïðåäåëåíèè, ñâÿçàííûì
ñî ñðàâíåíèåì áåñêîíå÷íûõ ÷èñåë) â ýòîì ñëó÷àå öåëåâàÿ ôóíêöèÿ áóäåò èìåòü çíà-
÷åíèå, ðàâíîå áåñêîíå÷íîñòè. Áóäåì ñ÷èòàòü, ÷òî è â ýòîì ñëó÷àå â ñèëó áåñêîíå÷-
íîñòè «îïòèìàëüíîãî» çíà÷åíèÿ öåëåâîé ôóíêöèè çàäà÷à (24) íå èìååò ðåøåíèÿ.
Íàêîíåö, òðåòèé âîçìîæíûé ñëó÷àé — çàäà÷à (24), (18), (19), (25) èìååò äîïó-
ñòèìîå ðåøåíèå, ñîñòàâëÿþùåå âåêòîðû x z, , ïðè êîòîðîì íåðàâåíñòâà (25) âûïîë-
íÿþòñÿ â ñòðîãîé ôîðìå. Çíà÷åíèå R x z( , ) áóäåò êîíå÷íûì. Ìíîæåñòâî Ëåáåãà
{ }( , ): ( , ) ( ~, ~), ,x z R x z R x z x R z Rn m� � � 1
áóäåò íåïóñòûì, âûïóêëûì è êîìïàêòíûì. Ñëåäîâàòåëüíî, â ýòîì ñëó÷àå ñóùå-
ñòâóåò è, â ñèëó ñòðîãîé âûïóêëîñòè ôóíêöèé F è D, åäèíñòâåííîå îïòèìàëüíîå
ðåøåíèå çàäà÷è (24). Ïóñòü ýòî îïòèìàëüíîå ðåøåíèå ñîñòàâëÿþò âåêòîðû
x R z Rn m� �, 1 . Ïîñêîëüêó çíà÷åíèå R x z( , ) êîíå÷íîå, òî âåêòîð z óäîâëåòâîðÿåò
óñëîâèþ (25) â ñòðîãîé ôîðìå, ò.å. äëÿ íåãî âûïîëíÿþòñÿ íåðàâåíñòâà (23).
 ñèëó óñëîâèé îïòèìàëüíîñòè Ëàãðàíæà äëÿ òîãî, ÷òîáû äàííûå âåêòîðû x z,
ïðè z, óäîâëåòâîðÿþùåì (23), áûëè îïòèìàëüíûì ðåøåíèåì çàäà÷è (24), íåîáõî-
äèìî è äîñòàòî÷íî, ÷òîáû ïðè íåêîòîðûõ âåêòîðàõ u R u R
m m1 21 2� �, âûïîëíÿ-
ëèñü ðàâåíñòâà (18)–(22). Çäåñü âåêòîðû u 1 è u 2 ñîñòîÿò èç ìíîæèòåëåé Ëàãðàí-
æà îãðàíè÷åíèé (18) è (19) äëÿ çàäà÷è îïòèìèçàöèè (24).
Äâîéñòâåííàÿ çàäà÷à îïòèìèçàöèè: íàéòè âåêòîðû y R n� , u R
m1 1� ,
u R
m2 2� , ÿâëÿþùèåñÿ ðåøåíèÿìè ýêñòðåìàëüíîé ïðîáëåìû
�( ) ( ) ( , ) ( , ) miny G u b u b u� � �
1 1 1 2 2 (26)
ïðè óñëîâèè (20). Öåëåâàÿ ôóíêöèÿ äàííîé çàäà÷è ñòðîãî âûïóêëà ïî ïåðåìåí-
íûì, ñîñòàâëÿþùèì âåêòîðû y è u 1, ëèíåéíà ïî ïåðåìåííûì, ñîñòàâëÿþùèì
âåêòîð u 2. Ïîýòîìó åñëè çàäà÷à (26) èìååò îïòèìàëüíîå ðåøåíèå, òî ýòî ðåøå-
íèå áóäåò åäèíñòâåííûì ïî ïåðåìåííûì y è u 1. Ïî ïåðåìåííûì u 2, åñëè
rank A m2 2� , ìîæåò áûòü íååäèíñòâåííîå ðåøåíèå.
Çàäà÷à (26) âñåãäà èìååò äîïóñòèìîå ðåøåíèå.  ÷àñòíîñòè, åãî ñîñòàâëÿþò
âåêòîðû u u y c1 20 0� � �, , . Âîçìîæíû òðè ñëó÷àÿ.
1. Öåëåâàÿ ôóíêöèÿ ìîæåò áûòü íå îãðàíè÷åíà ñíèçó íà ìíîæåñòâå äîïóñòèìûõ
ðåøåíèé çàäà÷è (26).  ýòîì ñëó÷àå çàäà÷à íå èìååò ðåøåíèÿ, ÷òî ñîîòâåòñòâóåò ïåðâîìó
ñëó÷àþ äëÿ èñõîäíîé çàäà÷è îïòèìèçàöèè — íåñîâìåñòíîñòè îãðàíè÷åíèé çàäà÷è (24).
2. Èíôèìóì öåëåâîé ôóíêöèè çàäà÷è (26) äîñòèãàåòñÿ ïðè áåñêîíå÷íûõ çíà-
÷åíèÿõ íåêîòîðûõ ïåðåìåííûõ.  ýòîì ñëó÷àå òàêîâûìè áóäóò ïåðåìåííûå, ÿâëÿþ-
ùèåñÿ êîìïîíåíòàìè âåêòîðà u 1. Ýòî èìååò ìåñòî ïðè ðåàëèçàöèè âòîðîãî ñëó÷àÿ
äëÿ çàäà÷è (24), ò.å. êîãäà îïòèìàëüíîå ðåøåíèå çàäà÷è (24) äîñòèãàåòñÿ ïðè áåñêî-
íå÷íîì çíà÷åíèè åå öåëåâîé ôóíêöèè. Áóäåì ñ÷èòàòü, ÷òî â ýòîì ñëó÷àå çàäà÷à (26)
íå èìååò îïòèìàëüíîãî ðåøåíèÿ.
3. Çàäà÷à (26) èìååò îïòèìàëüíîå ðåøåíèå. Ïóñòü ýòî ðåøåíèå ñîñòàâëÿþò âåêòîðû
y u u, ,1 2. Òîãäà ñîãëàñíî íåîáõîäèìûì è äîñòàòî÷íûì óñëîâèÿì îïòèìàëüíîñòè Ëàã-
ðàíæà ïðè íåêîòîðîì x R n� áóäóò âûïîëíÿòüñÿ äëÿ äàííûõ y u u, ,1 2 ðàâåíñòâà
(18)–(22). Âåêòîð x áóäåò ñîñòîÿòü èç ìíîæèòåëåé Ëàãðàíæà îãðàíè÷åíèé (20) äëÿ çàäà-
÷è (26).  ýòîì ñëó÷àå ïî âûðàæåíèþ (22) èç âåêòîðà u 1 ìîæíî ïîëó÷èòü âåêòîð z, èìå-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 1 89
þùèé êîìïîíåíòû z q u i mi i i� �( ), , ,1
11 � . Âåêòîð z â ñèëó ñâîéñòâ ôóíêöèé gi áóäåò
óäîâëåòâîðÿòü íåðàâåíñòâàì (23). Èòàê, äîêàçàíî ñëåäóþùåå óòâåðæäåíèå.
Òåîðåìà 2. Äëÿ ñèñòåìû óðàâíåíèé è íåðàâåíñòâ (18)–(23) èñõîäíîé (24)
è äâîéñòâåííîé (26) çàäà÷ îïòèìèçàöèè âîçìîæíû òîëüêî äâà ñëó÷àÿ.
1. Âñå îíè íå èìåþò ðåøåíèÿ.  ýòîì è òîëüêî â ýòîì ñëó÷àå óñëîâèÿ (18),
(19), (23) íå ñîâìåñòíû, ò.å. íå ñóùåñòâóåò âåêòîðîâ x R z Rn m� �, 1 , óäîâëåòâîðÿþ-
ùèõ èì âñåì.
2. Âñå òðè çàäà÷è èìåþò ðåøåíèÿ. Åñëè âåêòîðû x z y u u, , , ,1 2 ñîñòàâëÿþò ðå-
øåíèå ñèñòåìû óðàâíåíèé (18)–(23), òî âåêòîðû x z, ñîñòàâëÿþò îïòèìàëüíîå ðåøå-
íèå çàäà÷è (24), âåêòîðû u u1 2, ñîñòîÿò èç ìíîæèòåëåé Ëàãðàíæà çàäà÷è (24), âåê-
òîðû y u u, ,1 2 ÿâëÿþòñÿ îïòèìàëüíûìè ðåøåíèÿìè çàäà÷è (26), âåêòîð x ñîñòîèò èç
ìíîæèòåëåé Ëàãðàíæà îãðàíè÷åíèé çàäà÷è (26).
Äëÿ ðåøåíèé ðàññìàòðèâàåìûõ òðåõ çàäà÷ âåêòîðû x y z u, , , 1 èìåþò åäèíñòâåííûå
çíà÷åíèÿ, âåêòîð u 2 ìîæåò áûòü íååäèíñòâåííûì â òîì ñëó÷àå, åñëè rank A m2 2� .
Çàäà÷à ïîòîêîðàñïðåäåëåíèÿ. Ïóñòü A — ìàòðèöà èíöèäåíöèé óçëîâ è äóã
ãðàôà ãèäðàâëè÷åñêîé öåïè. Áóäåì ñ÷èòàòü, ÷òî ãðàô ÿâëÿåòñÿ ñâÿçíûì. Èíà÷å èç
íåñâÿçíûõ ïîäãðàôîâ ñëåäóåò ôîðìèðîâàòü îòäåëüíûå, íå ñâÿçàííûå ìåæäó ñîáîé
çàäà÷è ïîòîêîðàñïðåäåëåíèÿ. Èç ñâÿçíîñòè ãðàôà ñëåäóåò, ÷òî rank A m� �1. Ñ÷èòà-
åì, ÷òî èìåþòñÿ óçëû, â êîòîðûõ ðàñõîäû çàâèñÿò îò äàâëåíèÿ, ò.å. m1 1� . Ñëåäîâà-
òåëüíî, rank A m2 2� , ò.å. A
2
— ìàòðèöà, ñîñòîÿùàÿ èç ëèíåéíî íåçàâèñèìûõ
ñòðîê. Îòñþäà ñëåäóåò, ÷òî ó ìàòðèöû A ëþáûå èç ïîñëåäíèõ m2 ñòðîê íå âûðàæà-
þòñÿ â âèäå ëèíåéíûõ êîìáèíàöèé îñòàëüíûõ ñòðîê ýòîé ìàòðèöû. Ïåðâûå ëþáûå
èç m1 ñòðîê ýòîé ìàòðèöû òàêæå íå ìîãóò áûòü âûðàæåíû â âèäå ëèíåéíûõ êîìáè-
íàöèé îñòàëüíûõ ñòðîê A, ïîñêîëüêó ñòðîêè äèàãîíàëüíîé ïîäìàòðèöû ëèíåéíî
íåçàâèñèìû. Èòàê, rank A m� .
Ñîâìåñòíîñòü ñèñòåìû (18)–(23) îçíà÷àåò, ÷òî ïðè íåêîòîðîì z R
m� 1 , óäîâ-
ëåòâîðÿþùåì (23), äîëæíû âûïîëíÿòüñÿ ðàâåíñòâà
A x b z1
1� � , A x b2
2� .
Åñëè ïîäìàòðèöû A A1 2, îáðàçóþò ìàòðèöó èíöèäåíòíîñòè ñâÿçíîãî ãðàôà, òî
ïðèâåäåííûå ðàâåíñòâà áóäóò âûïîëíÿòüñÿ â òîì è òîëüêî òîì ñëó÷àå, åñëè
( )
i
m
i i i
i
m
b z b
� �
� �� � �
1
1 2
1
1 2
0
ïðè íåêîòîðîì z, óäîâëåòâîðÿþùåì (23).
Èòàê, åñëè A — ìàòðèöà èíöèäåíöèé ñâÿçíîãî ãðàôà, òî äëÿ ñîâìåñòíîñòè
îãðàíè÷åíèé (18), (19), (23) íåîáõîäèìî è äîñòàòî÷íî âûïîëíåíèÿ íåðàâåíñòâ
p b b ri
i
m
i
i
m
i
i
m
i
i
m
� � � �
� � � �� � �
1
1
1
2
1 1
1 1 2 1
.
(27)
Åñëè ãðàô ñâÿçíûé, m1 1� , íåðàâåíñòâà (27) âûïîëíÿþòñÿ, òî íåêëàññè÷åñêàÿ
çàäà÷à ïîòîêîðàñïðåäåëåíèÿ èìååò ðåøåíèå, è ýòî ðåøåíèå åäèíñòâåííî ïî âñåì
ïåðåìåííûì, ñîñòàâëÿþùèì âåêòîðû x z y u u, , , ,1 2. Äëÿ ïîèñêà ðåøåíèÿ ìîæíî èñ-
ïîëüçîâàòü ëþáîé èç àëãîðèòìîâ âûïóêëîé îïòèìèçàöèè ïðèìåíèòåëüíî ê èñõîä-
íîé (24) èëè äâîéñòâåííîé (26) çàäà÷àì îïòèìèçàöèè.
90 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 1
ÑÀÌÎÑÎÏÐßÆÅÍÍÀß È ÑÈÌÌÅÒÐÈ×ÍÀß ÇÀÄÀ×È ÎÏÒÈÌÈÇÀÖÈÈ
Íàðÿäó ñ ñèñòåìîé óðàâíåíèé è íåðàâåíñòâ (18)–(23) è çàäà÷àìè âûïóêëîãî ïðîãðàì-
ìèðîâàíèÿ (24), (26) èíòåðåñ ïðåäñòàâëÿþò è äðóãèå ôîðìû çàïèñè èññëåäóåìîé çà-
äà÷è ïîòîêîðàñïðåäåëåíèÿ ñ ðàñõîäàìè â óçëàõ, çàâèñÿùèìè îò äàâëåíèÿ â íèõ.
Çàìåòèì, ÷òî ó çàäà÷ îïòèìèçàöèè (24), (26) ñîâåðøåííî ðàçíûé (íå ïåðåñåêà-
þùèéñÿ) ñîñòàâ ïåðåìåííûõ. Ïðèâîäèìóþ íèæå çàäà÷ó îïòèìèçàöèè ìîæíî ïîëó-
÷èòü ïðîñòûì ñëîæåíèåì öåëåâûõ ôóíêöèé çàäà÷ (24), (26) è îáúåäèíåíèåì èõ
îãðàíè÷åíèé. Ýòà çàäà÷à îáëàäàåò äâóìÿ îñîáûìè ñâîéñòâàì. Âî-ïåðâûõ, äâî-
éñòâåííàÿ ê íåé áóäåò îíà ñàìà, èç-çà ÷åãî è íàçâàíà «ñàìîñîïðÿæåííîé» — äâî-
éñòâåííîé ñàìîé ñåáå. Ýòî îçíà÷àåò, ÷òî ìíîæèòåëè îãðàíè÷åíèé Ëàãðàíæà áóäóò
ñîâïàäàòü ñ îïòèìàëüíûìè çíà÷åíèÿìè ïåðåìåííûõ.
Âòîðîå ïîëåçíîå ñâîéñòâî ñîñòîèò â òîì, ÷òî ïðè ëþáîì äîïóñòèìîì ðåøåíèè
çíà÷åíèå öåëåâîé ôóíêöèè äàííîé çàäà÷è áóäåò íåîòðèöàòåëüíûì. Äëÿ îïòèìàëü-
íîãî ðåøåíèÿ, è òîëüêî äëÿ íåãî (èç äîïóñòèìûõ ðåøåíèé), çíà÷åíèå öåëåâîé
ôóíêöèè áóäåò íóëåâûì. Àïðèîðíàÿ èíôîðìàöèÿ îá îïòèìàëüíîì çíà÷åíèè öåëå-
âîé ôóíêöèè ìîæåò èñïîëüçîâàòüñÿ â àëãîðèòìàõ ïîèñêà ðåøåíèÿ òàêîé çàäà÷è
âûïóêëîãî ïðîãðàììèðîâàíèÿ.
Ñàìîñîïðÿæåííàÿ çàäà÷à îïòèìèçàöèè: íàéòè âåêòîðû x R z Rn m� �, ,1
y R u R u Rn m m� � �, ,1 21 2 , ÿâëÿþùèåñÿ ðåøåíèÿìè ýêñòðåìàëüíîé ïðîáëåìû
F x D z y G u c x b u b u( ) ( ) ( ) ( ) ( , ) ( , ) ( , ) min� � � � � �
� 1 1 1 2 2 (28)
ïðè îãðàíè÷åíèÿõ (18)–(20), (23).
Òåîðåìà 3. Çàäà÷à (28) èìååò îïòèìàëüíîå ðåøåíèå â òîì è òîëüêî òîì ñëó÷àå,
åñëè óñëîâèÿ (18), (19), (23) ñîâìåñòíûå.
Åñëè âåêòîðû x z y u u, , , ,1 2, ñîñòàâëÿþò äîïóñòèìîå, íî íå îïòèìàëüíîå ðåøå-
íèå çàäà÷è (28), òî çíà÷åíèå öåëåâîé ôóíêöèè ýòîé çàäà÷è áóäåò ïîëîæèòåëüíûì.
Åñëè äîïóñòèìûå ïî óñëîâèÿì çàäà÷è âåêòîðû x z y u u, , , ,1 2 ñîñòàâëÿþò îïòè-
ìàëüíîå ðåøåíèå çàäà÷è (28), òî ìíîæèòåëè Ëàãðàíæà îãðàíè÷åíèé (18) ñîñòàâëÿ-
þò âåêòîð u 1, îãðàíè÷åíèé (19) — âåêòîð u 2, îãðàíè÷åíèé (20) — âåêòîð x, çíà÷å-
íèå öåëåâîé ôóíêöèè áóäåò ðàâíî íóëþ.
Äîêàçàòåëüñòâî. Òîò ôàêò, ÷òî âåêòîðû îïòèìàëüíîãî ðåøåíèÿ x u u, ,1 2 ñî-
ñòàâëÿþò ìíîæèòåëè Ëàãðàíæà ñàìîñîïðÿæåííîé çàäà÷è, ñëåäóåò èç òåîðåìû 2. Èç
òåîðåìû 2 òàêæå ñëåäóåò, ÷òî äëÿ ñóùåñòâîâàíèÿ îïòèìàëüíîãî ðåøåíèÿ ó çàäà÷è
(28) íåîáõîäèìî è äîñòàòî÷íî ñîâìåñòíîñòè óñëîâèé (18)–(20), (23).
Ïóñòü âåêòîðû x z y u u, , , ,1 2 ñîñòàâëÿþò äîïóñòèìîå ðåøåíèå çàäà÷è (28), ò.å.
âåêòîðû x z, ñîñòàâëÿþò äîïóñòèìîå ðåøåíèå çàäà÷è, (24) ïðè óñëîâèè (23), âåêòî-
ðû y u u, ,1 2 ñîñòàâëÿþò äîïóñòèìîå ðåøåíèå çàäà÷è (26). Äëÿ ýòèõ âåêòîðîâ âûïîë-
íÿåòñÿ ðàâåíñòâî, ÿâëÿþùååñÿ àíàëîãîì (11):
( , ) ( , ) ( , ) ( , ) ( , )c x b u b u x y z u� � � �1 1 2 2 1 . (29)
Äåéñòâèòåëüíî, ïîñëåäîâàòåëüíî èñïîëüçóÿ (20), çàòåì (18), (19), èìååì
( , ) ( , ) ( , ) ( ) ( ) (c x b u b u y A u A u x b u bT T T T� � � � � � �1 1 2 2
1
1
2
2 1 1 2 2)T u �
� � � � � � �y x u b A x u b A x y x u zT T T T T( ) ( ) ( ) ( ) ( ) .1 1
1
2 2
2
1
Åñëè ðàññìàòðèâàåìûå âåêòîðû âûñòóïàþò îïòèìàëüíûì ðåøåíèåì çàäà÷è
(28), òî äëÿ íèõ âûïîëíÿþòñÿ óñëîâèÿ (21), (22), èç êîòîðûõ ñëåäóþò ðàâåíñòâà
(6), (16). Èç (6), (16) èìååì, ÷òî
F x D z G u x y z u( ) ( ) ( ) ( , ) ( , ) .� � � � �1 1 0
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 1 91
 ñèëó (29) â ýòîì ñëó÷àå öåëåâàÿ ôóíêöèÿ çàäà÷è (28) ðàâíà íóëþ.
Åñëè ðàññìàòðèâàåìûå âåêòîðû íå ñîñòàâëÿþò îïòèìàëüíîå ðåøåíèå çàäà÷è
(28), ò.å. èëè äëÿ íåêîòîðûõ j n�{ }1, ,� íå âûïîëíÿåòñÿ óñëîâèå (21), èëè äëÿ íåêî-
òîðûõ i m�{ }1 1, ,� íå âûïîëíÿåòñÿ óñëîâèå (22), òî èëè äëÿ íåêîòîðûõ j ñïðàâåä-
ëèâî íåðàâåíñòâî (7), èëè äëÿ íåêîòîðûõ i ñïðàâåäëèâî íåðàâåíñòâî (17). Ïðè ýòîì
íå èñêëþ÷àåòñÿ âîçìîæíîñòü îáåèõ ñèòóàöèé. Èç (6), (7), (16), (17) ïîëó÷àåì
íåðàâåíñòâî
F x D z G u x y z u( ) ( ) ( ) ( , ) ( , ) .� � � � �1 1 0
 ñèëó (29) â ýòîì ñëó÷àå öåëåâàÿ ôóíêöèÿ çàäà÷è (28) èìååò ïîëîæèòåëüíîå
çíà÷åíèå.
Òåîðåìà 3 äîêàçàíà.
Ñèììåòðè÷íàÿ çàäà÷à îïòèìèçàöèè: íàéòè âåêòîðû x R z Rn m� �, ,1 y R n� ,
u R u R
m m1 21 2� �, , ÿâëÿþùèåñÿ ðåøåíèåì ýêñòðåìàëüíîé ïðîáëåìû
F x D z G u x y z u( ) ( ) ( ) ( , ) ( , ) min� � � �
1 1 (30)
ïðè îãðàíè÷åíèÿõ (18)–(20), (23).
Äàííàÿ çàäà÷à ïîëó÷åíà èç çàäà÷è (28) ïóòåì ïðåîáðàçîâàíèÿ öåëåâîé ôóíêöèè
íà îñíîâå ðàâåíñòâà (29). Èç òåîðåìû 3 è óñëîâèÿ îïòèìàëüíîñòè Ëàãðàíæà ïîëó÷à-
åì ñëåäóþùåå óòâåðæäåíèå.
Òåîðåìà 4. Çàäà÷à (30) èìååò îïòèìàëüíîå ðåøåíèå â òîì è òîëüêî òîì ñëó÷àå,
åñëè óñëîâèÿ (18), (19), (23) ñîâìåñòíûå.
Åñëè âåêòîðû x z y u u, , , ,1 2 ñîñòàâëÿþò äîïóñòèìîå, íî íå îïòèìàëüíîå ðåøå-
íèå çàäà÷è (30), òî çíà÷åíèå öåëåâîé ôóíêöèè ýòîé çàäà÷è áóäåò ïîëîæèòåëüíûì.
Äëÿ îïòèìàëüíîãî ðåøåíèÿ çíà÷åíèå öåëåâîé ôóíêöèè çàäà÷è (30) ðàâíî
íóëþ, ìíîæèòåëè Ëàãðàíæà îãðàíè÷åíèé (18)–(20) âñå ðàâíû íóëþ.
Çàìå÷àíèå. Èíôîðìàöèÿ î çíà÷åíèè ìíîæèòåëåé Ëàãðàíæà îãðàíè÷åíèé çàäà-
÷è (30) ìîæåò ýôôåêòèâíî èñïîëüçîâàòüñÿ â àëãîðèòìàõ ïîèñêà ðåøåíèé ýòîé çàäà÷è.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ì å ð å í ê î â À . Ï . , Õ à ñ è ë å â  . ß . Òåîðèÿ ãèäðàâëè÷åñêèõ öåïåé. — Ì.: Íàóêà, 1985. — 294 ñ.
2. Ì å ð å í ê î â À . Ï . , Ñ å í í î â à Å . Â . , Ñ ó ì à ð î ê î â Ñ . Â . , Í î â è ö ê è é Í . Í . è ä ð .
Ìàòåìàòè÷åñêîå ìîäåëèðîâàíèå è îïòèìèçàöèÿ ñèñòåì òåïëî-, âîäî-, íåôòå- è ãàçîñíàáæåíèÿ. —
Íîâîñèáèðñê: Íàóêà, 1992. — 407 ñ.
3. Ï ø å í è ÷ í û é Á . Í . Ðàñ÷åò ýíåðãåòè÷åñêèõ ñåòåé íà ÝÂÌ // Æóðí. âû÷èñë. ìàòåìàòèêè è ìàò.
ôèçèêè. — 1962. — ¹ 5. — Ñ. 942–947.
4. Ê î æ è í î â È . Â . , Ê î ë å ñ î â Â . Â . , Ì à é ç å ë ü ñ Ì . Ï . è ä ð . Íàëàäêà è èíòåíñèôèêàöèÿ
ðàáîòû ãîðîäñêèõ ñèñòåì ïîäà÷è è ðàñïðåäåëåíèÿ âîäû. — Ì.: Ñòðîéèçäàò, 1978. — 111 ñ.
5. Ç î ð ê à ë ü ö å â Â . È . , Õ à ì è ñ î â Î . Â . Ðàâíîâåñíûå ìîäåëè â ýêîíîìèêå è ýíåðãåòèêå. —
Íîâîñèáèðñê: Íàóêà, 2006. — 221 ñ.
6. Ð î ê à ô å ë ë à ð Ð . Âûïóêëûé àíàëèç. — Ì.: Ìèð, 1973. — 469 ñ.
7. Å ï è ô à í î â Ñ . Ï . , Ç î ð ê à ë ü ö å â Â . È . Ïðèëîæåíèå òåîðèè äâîéñòâåííîñòè ê ìîäåëÿì
ïîòîêîðàñïðåäåëåíèÿ // Âû÷èñëèòåëüíûå òåõíîëîãèè. — 2009. — 14, ¹ 1. — Ñ. 67–80.
Ïîñòóïèëà 18.02.2009
92 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 1
|