Застосування модифікованого методу лінеаризації для розв’язання нелінійних задач розподілу потоків
The optimization problem of flows calculation in networks of given configuration is considered. The solution is achieved with application of combination of the first and second order linearization methods. The constructed algorithm converges from any initial approach and has the accelerated speed of...
Збережено в:
| Дата: | 2019 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2019
|
| Онлайн доступ: | https://journal.iasa.kpi.ua/article/view/171685 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | System research and information technologies |
| Завантажити файл: |  |
Репозитарії
System research and information technologies| _version_ | 1866391913717825536 |
|---|---|
| author | Kirik, H. E. |
| author_facet | Kirik, H. E. |
| author_sort | Kirik, H. E. |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2019-06-27T14:30:07Z |
| description | The optimization problem of flows calculation in networks of given configuration is considered. The solution is achieved with application of combination of the first and second order linearization methods. The constructed algorithm converges from any initial approach and has the accelerated speed of convergence in comparison with the first order methods. |
| first_indexed | 2025-07-17T10:25:24Z |
| format | Article |
| fulltext |
© О.Є. Кірік, 2004
40 ISSN 1681–6048 System Research & Information Technologies, 2004, № 3
УДК 519.8
ЗАСТОСУВАННЯ МОДИФІКОВАНОГО МЕТОДУ
ЛІНЕАРИЗАЦІЇ ДЛЯ РОЗВ’ЯЗАННЯ НЕЛІНІЙНИХ ЗАДАЧ
РОЗПОДІЛУ ПОТОКІВ
О.Є. КІРІК
Розглядається оптимізаційна задача розрахунку потоків в мережах заданої
конфігурації. Розв’язок отримується із застосуванням комбінації методів ліне-
аризації першого та другого порядків. Побудований алгоритм збігається з до-
вільного початкового наближення і має прискорену швидкість збіжності у по-
рівнянні з методами першого порядку.
ВСТУП
Задача знаходження найкращого розподілу потоків посідає важливе місце у
розрахунках розподільчих мереж. Причому при дослідженні енергетичних
систем, таких як газові, електричні, теплові, будуються математичні моделі
з нелінійними цільовими функціями. У роботах [1– 4 ] вивчалися особливос-
ті застосування методів нелінійної оптимізації для розв’язання задач оптима-
льного розподілу потоків в енергетичних мережах. Зокрема в роботі [4] роз-
глядалося розв’язання задачі оптимального газорозподілу за допомогою
методу лінеаризації Б.М. Пшеничного. Основна ідея цього методу поля-
гає у заміні розв’язання нелінійної задачі розв’язанням послідовності лінеа-
ризованих задач, доповнених квадратичним штрафом за великі ухилен-
ня аргументу.
Метод лінеаризації виявився зручним для задач розподілу потоків в ме-
режах, оскільки він дає можливість врахувати їх специфічну структуру і по-
будувати обчислювальні процедури, ефективні з точки зору збереження та
обробки інформації. До переваг цього методу можна віднести і те, що він
забезпечує збіжність з широкої області початкових наближень. Але в деяких
задачах швидкість збіжності методів першого порядку виявляється недоста-
тньою. Тоді ідея лінійної апроксимації цілком природно приводить до ідеї
квадратичної апроксимації.
Нижче розглядається розв’язання нелінійної задачі розподілу потоків із
застосуванням модифікованого методу лінеаризації, який є методом другого
порядку. Зберігаючи основні переваги методу лінеаризації, він має приско-
рену швидкість збіжності, яку можна оцінити для конкретних класів задач.
Оскільки наша мета — побудова зручного та ефективного методу роз-
поділу потоків, а основною процедурою при реалізації методів лінеаризації
як першого, так і другого порядку є розв’язання допоміжних задач квадра-
тичного програмування, то подальші зусилля будуть направлені на створен-
ня ефективних алгоритмів для задач розподілу потоків з квадратичними ці-
льовими функціями.
При розв’язанні допоміжних квадратичних задач пропонується перехо-
дити до двоїстих задач без обмежень, а потім застосовувати метод спряже-
Застосування модифікованого методу лінеаризації для розв’язання нелінійних задач ...
Системні дослідження та інформаційні технології, 2004, № 3 41
них градієнтів як такий, що збігається за скінченне число кроків і не вима-
гає, взагалі кажучи, невиродженості матриці квадратичної форми.
Нижче досліджується питання існування розв’язку та докладно розгля-
даються обчислювальні аспекти.
Оцінка швидкості збіжності наводиться для задач розподілу потоків із
сильно опуклими цільовими функціями.
1. ФОРМУЛЮВАННЯ ЗАДАЧІ
Розподільча мережа представляється у вигляді зв’язного орієнтовного графа
( )VNG ,= , де N та V — множини, що містять, відповідно, n вузлів та m
дуг, причому кожній дузі Vk ∈ співставлена упорядкована пара вузлів
( )ji, , Nji ∈, , що є її початком і кінцем.
Якщо кожній дузі графа ( )ji, приписаний деякий потік ijx , причому
задана функція вартості протікання одиниці потоку ( )ijij xF , а для кожного
вузла i відоме споживання id , можна сформулювати задачу знаходження
розподілу потоків мінімальної вартості.
Мінімізувати функцію
( ) ( )
( )
∑
∈
=
Vji
ijij xFxF
,
(1)
при обмеженнях
( )( )
Nidxx
Vjij Vijj
ijiij ∈=−∑ ∑
∈ ∈
,
,: ,:
. (2)
Як випливає з рівнянь (2), величини id мають додатне значення у вуз-
лах-«джерелах» і від’ємне — у вузлах, де розташовані споживачі. Умова
сумісності системи (2) отримується додаванням всіх рівнянь з урахуванням
їх специфічної структури
∑
=
=
n
i
id
1
0 . (3)
Якщо функція ( )xF є строго опуклою, а множина ( ) ( ){ }xFxFx ′≤: об-
межена при довільному x′ , то задача (1),(2) має єдиний розв’язок.
Як приклад задач зазначеного типу можна навести задачу розрахунку
гідравлічних систем з цільовою функцією
( )
( )
α
α
+
∈
+ ∑=
1
,
1
1
Vji
ijij xlxF ,
де величина α в залежності від задачі обирається з умови 20 ≤<α , а ijl —
деякі константи, які відображають вартість протікання потоку вздовж дуг
( ) Vji ∈, .
Відмітимо: якщо покласти 0=α , а ijl позначити довжину відповідних
дуг, то отримаємо звичайну транспортну задачу, яка тут не розглядається,
бо для неї запропоновано багато ефективних методів, що базуються на ідеях
лінійного програмування.
О.Є. Кірік
ISSN 1681–6048 System Research & Information Technologies, 2004, № 3 42
Нашою ж метою далі буде побудова алгоритмів розподілу потоків для
задач з нелінійними опуклими цільовими функціями.
Якщо вважати, що всі дуги графа G перенумеровані від 1 до m , то за-
дачу (1), (2) можна переписати у більш зручному вигляді
( ) ( ) min
1
→≡∑
=
m
k
kk xFxF , (4)
dAx = , (5)
де ),...,,( 21 ndddd = — вектор споживання, а A ( )mn× — матриця інциден-
цій вузли — дуги, елементи якої задаються таким чином: 1=ika , якщо k -а
дуга є вихідною для i -го вузла; 1−=ika , якщо k -а дуга є вхідною для i -го
вузла; 0=ika , якщо i -й вузол та k -а дуга ніяк не пов’язані між собою. Та-
ким чином, кожний k -й стовпець матриці інциденцій відповідає дузі
),( jik = , Nji ∈, і містить тільки два ненульових елементи ( 1+ у рядку i
та 1− у рядку j ).
2. АЛГОРИТМИ ОПТИМІЗАЦІЇ
Будемо вважати, що функція ( )xF є неперервно диференційованою. Ідея
методу лінеаризації Б.М. Пшеничного [5] реалізується шляхом побудови
ітераційного процесу
k
k
kk pxx α+=+1 , 10 ≤< kα , (6)
де на кожному кроці напрям зсуву ( ) mkk Rxpp ∈= знаходиться при фіксо-
ваному mk Rxx ∈= з допоміжної задачі квадратичного програмування з
одиничною матрицею квадратичної форми
( ) min
2
1, 2 →+′ ppxF , (7)
0=−+ dAxAp . (8)
Тут ( )xF ′ — градієнт функції ( )xF ; p означає евклідову норму;
px, — скалярний добуток.
Нижче побудуємо алгоритм розв’язання нелінійної задачі розподілу
потоків (4),(5) з використанням модифікованого методу лінеаризації, в яко-
му застосовується квадратична апроксимація цільової функції ( )xF на кож-
ному кроці. В цьому випадку послідовність { }kx генерується за формулою
(6), однак напрям зсуву визначається шляхом розв’язання задачі
( ) ( ) min,
2
1, →′′+′ ppxFpxF , (9)
0=−+ dAxAp , (10)
Застосування модифікованого методу лінеаризації для розв’язання нелінійних задач ...
Системні дослідження та інформаційні технології, 2004, № 3 43
де ( ) ( )
mj
miji xx
xFxF
,...,1
,...,1
2
=
=⎪⎭
⎪
⎬
⎫
⎪⎩
⎪
⎨
⎧
∂∂
∂
=′′ — матриця других похідних функції ( )xF .
Задачу (7), (8) будемо використовувати тільки на першому етапі – для
знаходження початкового наближення. Ця процедура докладно розглядаєть-
ся у наступному розділі.
3. ВИБІР ДОПУСТИМОЇ ПОЧАТКОВОЇ ТОЧКИ
Введемо позначення:
( )xFc ′= ,
dAxb −= .
При розв’язанні квадратичної задачі
min
2
1, 2 →+ ppc , (11)
0=+ bAp (12)
з обмеженнями-рівностями можна отримати явний вигляд формул розв’язку
тільки за умови лінійної незалежності строк матриці обмежень. В задачі
розподілу потоків умова (3) вказує на лінійну залежність строк матриці A .
Тому задачу (11), (12) будемо розв’язувати поетапно.
Побудуємо для цієї задачі функцію Лагранжа
bupuAcpbApuppcupL T ,,
2
1,
2
1,),( 22 +++=+++= ,
де nRu∈ — вектор двоїстих змінних. Необхідні умови екстремуму [6]
отримуємо, прирівнюючи похідні від L по p до нуля
( ) 0, =++=′ uApcupL T
p .
Використовуючи останнє співвідношення, можна перейти до двоїстої
задачі без обмежень
max
2
1,,
2
1 2 →−−−− cubAcuuAAT , (13)
де 0, ≥uuAA T при всіх nRu ∈ .
Після розв’язання задачі (13) можна повернутися до вихідних змінних,
застосовуючи формулу
cuAp T −−= . (14)
Оскільки вільний член в (13) не впливає на знаходження точки макси-
муму, в подальшому будемо його опускати.
Побудуємо алгоритм розв’язання задачі (13), спираючись на ідеї мето-
ду спряжених градієнтів. Вибір цього методу не є випадковим. При
розв’язанні допоміжних задач, які є внутрішніми підзадачами більш загаль-
О.Є. Кірік
ISSN 1681–6048 System Research & Information Technologies, 2004, № 3 44
них процедур, доцільно використовувати скінченні алгоритми, тобто такі,
які дають розв’язок за скінченне число кроків.
Нагадаємо, що вектори iz , ni ,...,1= називаються спряженими віднос-
но матриці C , якщо вони лінійно незалежні і jizCz ji ≠= ,0, . Спряжені
вектори визначені неоднозначно, однак їх знання дозволяє розв’язати задачу
пошуку максимуму квадратичної функції
( ) ysyCyyf ,,
2
1
−−= . (15)
Якщо 0y — деяка точка, то довільна інша точка y може бути предста-
влена у вигляді
∑
=
+=
n
i
i
i zyy
1
0 β .
Підставивши цей вираз у (15), отримаємо
( ) ∑ ∑
= =
+−−−−=
n
i
n
i
i
i
ii
i zsCyzCzysyCyyf
1 1
02000 ,,
2
1,,
2
1 ββ .
Тобто
( ) ( ) ( )∑ ∑
= =
′+−=
n
i
n
i
i
i
ii
i zyfzCzyfyf
1 1
020 ,,
2
1 ββ . (16)
Розглянемо праву частину (16) як функцію від iβ і знайдемо її макси-
мум по iβ
( ) 0,, 0 =′+− iii
i zyfzCzβ .
Звідси
( )
ii
i
i
zCz
zyf
,
,0′
=β . (17)
Можливі такі випадки:
1. 0, =ii zCz , ( ) 0,0 ≠′ izyf . Верхня грань (16) по iβ дорівнює
∞+ , оскільки у даному випадку (16) — лінійна функція.
2. 0, =ii zCz , ( ) 0,0 =′ izyf . Оскільки f від iβ фактично не зале-
жить, iβ може вибиратися довільно.
3. 0, ≠ii zCz , ( ) 0,0 ≠′ izyf . Величина iβ обчислюється за форму-
лою (17).
Таким чином необхідною і достатньою умовою того, що квадратична
функція (15) обмежена зверху, є виконання співвідношення ( ) 0,0 =′ izyf
для всіх 0y та для всіх i , для яких 0, =ii zCz .
У нашому випадку для задачі (13)
Застосування модифікованого методу лінеаризації для розв’язання нелінійних задач ...
Системні дослідження та інформаційні технології, 2004, № 3 45
2
,,, zAzAzAzzAAzCz TTTT === . (18)
З формули (18) видно, що 0, =zCz тільки за умови 0=zAT .
Нагадаємо: кожний стовпець матриці A (а значить кожна строка мат-
риці TA ) містять рівно два ненульові елементи 1 та – 1 у позиціях, які від-
повідають номерам вузлів, що є початком та кінцем дуги, номер якої — но-
мер відповідного стовпця матриці A ( строки матриці TA ).
Якщо позначити T
kA k -ту строку матриці TA , де ( )jik ,= , Nji ∈, , то
для довільного вектора nRz∈
ji
T
k zzzA −= , (19)
причому різниця (19) обертається в нуль тільки за умови співпадіння ком-
понент ji zz = . Оскільки в праву частину формули (18) всі компоненти век-
тора z входять у вигляді попарних різниць, то, в силу зв’язності мережі G ,
квадратична форма 0, =zzAAT тоді і тільки тоді, коли абсолютно всі
компоненти вектора z є однаковими. При побудові системи спряжених век-
торів такі вектори не розглядаються. Це означає, що випадок 1 можна ви-
ключити, тобто квадратична функція (13) обмежена зверху.
Отже є справедливою
Теорема 1. В задачі максимізації (13) квадратична функція обмежена
зверху, якщо A — матриця інциденцій зв’язної мережі.
Таким чином, максимум квадратичної функції (13) досягається, причо-
му оптимальна точка представляється у вигляді
∑
=
+=
n
i
i
i zyy
1
0* β ,
де iβ визначається за формулою (17).
Послідовні наближення iy до оптимальної точки можуть бути отрима-
ні за рекурентними формулами
1
1
1 +
+
+ += i
i
ii zyy β , 1,...,1,0 −= ni ,
причому питання знаходження β розглянуте вище, а методи побудови
спряжених градієнтів можуть бути різними. Один із варіантів побудови сис-
теми спряжених векторів наведено в роботі [5]. Він виявився достатньо зру-
чним і для нашої задачі.
Початкова точка 0y обирається довільно. Далі обчислення здійсню-
ються за рекурентними формулами для 1,...,1,0 −= ni .
( )
( )⎪
⎪
⎩
⎪
⎪
⎨
⎧
>
′
′
=
=
−
+ ,0,
,0,0
21
2
1 i
yf
yf
i
i
i
iγ
О.Є. Кірік
ISSN 1681–6048 System Research & Information Technologies, 2004, № 3 46
( )
( )⎪⎩
⎪
⎨
⎧
>+′
=′
=
+
+
,0,
,0,
1
1
izyf
iyf
z
i
i
i
i
i
γ
(20)
( )
11
1
1
,
,
++
+
+
′
=
ii
ii
i
zCz
zyf
β ,
1
1
1 +
+
+ += i
i
ii zyy β .
Цей процес збігається за число кроків ni ≤ , причому умовою зупинки є
обертання чергового градієнта ( )iyf ′ в нуль.
Зауваження. Оскільки TAAC = , то можемо записати формулу для 1+iβ
у вигляді
( )
21
1
1
,
+
+
+
′
=
iT
ii
i
zA
zyf
β і при обчисленнях враховувати (19). Це дає
можливість при реалізації алгоритму виключити непотрібні операції мно-
ження матриць на вектори.
Коли задача (13) розв’язана, повертаємося до вихідних змінних p . Від-
мітимо, що в алгоритмі лінеаризації Б.М. Пшеничного передбачена ще
спеціальна процедура пошуку ]1,0(∈α , яка визначає крок вздовж напрямку
( )xp . Оскільки нашою метою в цьому розділі є просто побудова довільної
допустимої точки, то можна вибрати 10 =α і покласти ( )001 xpxx += .
Множина { }dAxxX == : є опуклою. Це означає: довільна точка x , яка
лежить на відрізку, що з’єднує допустимі точки 1x і 2x , також буде допус-
тимою. Тобто, якщо представити точку x у вигляді
( ) 211 xxx µµ +−= , де 10 ≤≤ µ ,
то
( ) ( ) dAddAxAxAx =+−=+−= µµµµ 11 21 .
Опуклість множини X дозволяє стверджувати, що при побудові ітера-
ційного процесу у випадку, якщо початкова точка x задовольняє обмежен-
ням, то їм будуть задовольняти і всі точки px α+ .
4. ДОПОМІЖНА ЗАДАЧА МОДИФІКОВАНОГО МЕТОДУ ЛІНЕАРИЗАЦІЇ
Розглянемо тепер задачу квадратичного програмування (9), (10), яка береть-
ся за основу в модифікованому методі лінеаризації.
Позначивши ( )xFB ′′= та використовуючи введені ще раніше позна-
чення, перепишемо цю задачу у вигляді
.0
,min,
2
1,
=+
→+
bAp
pBppc
(21)
Застосування модифікованого методу лінеаризації для розв’язання нелінійних задач ...
Системні дослідження та інформаційні технології, 2004, № 3 47
Оскільки функція ( )xF є сепарабельною, тобто представляється у ви-
гляді суми функцій ( )kk xF , mk ,...,1= , кожна з яких визначена на певній
дузі, то матриця B , очевидно, є діагональною, причому на діагоналі
розташовані елементи
( )
2
2
k
kk
dx
xFd
, mk ,...,1= .
Як було вже зазначено, у загальній задачі квадратичного програмуван-
ня оптимум або досягається, або цільова функція є необмеженою. Ми пока-
зали, що за умови сумісності обмежень (5) максимум функції (13), а значить
і розв’язок задачі (4), (5), завжди існує.
Розглянемо процедуру розв’язання задачі (21).
Для побудови двоїстої до неї задачі випишемо функцію Лагранжа
( ) =+++= bApupBppcupL ,,
2
1,,
bupuAcpBp T ,,,
2
1
+++= .
Необхідно обчислити
( ) ( )upLu ,inf=ψ .
Зважаючи на структуру матриці B , можемо записати
( )
0, 2
1
2
2
≥= ∑
=
k
m
k k
kk p
dx
xFd
pBp .
Суттєвою особливістю розподільчих систем, яка враховується при ма-
тематичному моделюванні функціонування енергетичних комплексів, є
забезпечення ненульових потоків по всіх дугах мережі. Нелінійність
цільових функцій оптимізаційних задач забезпечує виконання цієї умови.
Будемо надалі припускати: функції вартості побудовані таким чином, що
жодна із других похідних в точках побудованої послідовності (6) не
обертається в нуль. Тоді можемо вважати, що матриця ( )xFB ′′= для
довільної такої точки є невиродженою. Прирівнюючи похідні від L по p до
нуля, отримаємо
( ) 0, =++=′ uABpcupL T
p ,
( )uAcBp T+−= −1 . (22)
Підставляючи цю формулу у вираз для ( )upL , , маємо
( ) ( ) .,,
2
1 1 buuAcuAcBu TT +++−= −ψ
Перетворимо квадратичний член цього виразу.
( ) =++− uAcuAcB TT ,
2
1 1
ccBucABuuAAB T ,
2
1,,
2
1 111 −−− ++= .
О.Є. Кірік
ISSN 1681–6048 System Research & Information Technologies, 2004, № 3 48
Тут враховано, що оскільки матриця B має діагональний вигляд, то
BBT = , ( ) 11 −− = BB
T
.
Таким чином, задача двоїста до (21) має вигляд
( ) ≡uψ max,
2
1,,
2
1 111 →−−− −−− ccBucABuuAAB T . (23)
Як було показано вище, максимум в задачі (13), двоїстої до квадратич-
ної задачі розподілу потоків, завжди досягається. Проаналізуємо питання
існування розв’язку задачі (23).
При розв’язанні квадратичної задачі (23) можемо використати проце-
дуру спряжених градієнтів (20) для випадку, коли TAABC 1−= . Оскільки, як
показано у розділі 3, всі компоненти спряжених векторів не можуть співпа-
дати, то будемо вважати, що для довільного вектора z із системи спряже-
них векторів 0≠zAT , тобто
0,, 11 ≠= −− zAzABzzAAB TTT .
Якщо розв’язок задачі (23) знайдено, то, підставивши його у формулу
(22), отримаємо розв’язок прямої задачі (21).
Можемо стверджувати, що виконується
Теорема 2. Нехай в задачі квадратичного програмування (21) матриця
квадратичної форми B невироджена, а матриця обмежень A — це матриця
інциденцій вузли – дуги зв’язної мережі. Тоді розв’язок прямої та двоїстої
задач завжди існує, причому розв’язок двоїстої задачі можна отримати шля-
хом застосування процедури (20), а прямої — обчисленням за формулою (22).
5. РОЗВ’ЯЗАННЯ НЕЛІНІЙНОЇ ЗАДАЧІ РОЗПОДІЛУ ПОТОКІВ
Ми приділили багато уваги задачам розподілу потоків з квадратичними ці-
льовими функціями, які є допоміжними при реалізації розглянутих вище
оптимізаційних алгоритмів. Однак нашою кінцевою метою є розв’язання
задачі розподілу потоків (4),(5) з нелінійною цільовою функцією.
При побудові ітераційного процесу (6) лишається ще вирішити питання
обчислення кроку α на кожній ітерації. Як показано в роботі [5], при реалі-
зації методу лінеаризації з допоміжною задачею (9), (10) вибір кроку можна
здійснювати, виходячи з формули
( ) ( ) ( ) kkkkkk pxFpxFpxF ′′−≤+ ,εαα . (24)
При цьому буде вірною така теорема.
Теорема 3. [5]. Нехай ( )kxF — опукла двічі неперервно-диферен-
ційовна функція і нехай ( ) 2, pmpxFp ≥′′ , 0>m . Тоді наведений вище
алгоритм опуклого програмування, де на кожному кроці розв’язується зада-
ча (9),(10), а крок знаходиться за формулою (24), збігається швидше довіль-
ної геометричної прогресії з будь-якого початкового наближення 0x , що
задовольняє обмеженням задачі.
Застосування модифікованого методу лінеаризації для розв’язання нелінійних задач ...
Системні дослідження та інформаційні технології, 2004, № 3 49
ВИСНОВКИ
При розв’язанні задач нелінійного програмування ідея застосування комбі-
нації методу першого порядку, який має глобальну збіжність, та методу дру-
гого порядку, цікавого з точки зору швидкості збіжності, є достатньо попу-
лярною. Проблематичним залишається вибір моменту переходу від однієї
процедури до іншої, оскільки неможливо заздалегідь оцінити близькість до
оптимальної точки.
Задачі розподілу потоків мають систему лінійних обмежень, що дозво-
ляє при їх розв’язанні цілком природним способом поєднати методи першо-
го та другого порядків, використовуючи методи першого порядку для по-
шуку допустимого початкового наближення, а другого — для швидкого
досягнення оптимуму всередині допустимої області.
Перевагами застосування методу лінеаризації до задач розподілу пото-
ків є збіжність з довільного початкового наближення, зручні розрахункові
процедури, а для модифікованого методу лінеаризації — прискорена швид-
кість збіжності у порівнянні з методами першого порядку. Запропонований
в статті підхід до розв’язання задач розподілу потоків дозволяє врахувати і
зберегти переваги обох методів.
Тестові розрахунки підтвердили ефективність застосування методу
спряжених градієнтів для розв’язання квадратичних задач розподілу пото-
ків. Як було доведено вище, оптимум у таких задачах для довільної зв’язної
мережі завжди є обмеженим. Це гарантує існування розв’язку допоміжних
задач і є принципово важливим при реалізації методу лінеаризації та його
модифікацій.
Дослідження, проведені у статті, можуть служити відправною точкою
для побудови ітераційних обчислювальних процесів, де на кожному кроці
при побудові допоміжних задач замість матриці других похідних викорис-
товуються її різноманітні апроксимації, що значно розширює класи мереже-
вих задач, які можна розв’язувати із застосуванням ідей послідовного квад-
ратичного програмування.
ЛІТЕРАТУРА
1. Пшеничный Б.Н., Кирик Е.Е. Алгоритмы оптимального распределения потоков
в сетях // Кибернетика и системный анализ. — 1993. — № 4. — С. 29–39.
2. Пшеничный Б.Н., Кирик Е.Е. Методы нелинейного программирования и потоки
в сетях // Кибернетика и системный анализ. — 1994. — № 6. — С. 67–77.
3. Кирик Е.Е., Пшеничный Б.Н. Теория и методы расчета сетей // Обозрение при-
кладной и промышленной математики. — М.: ТВП, 1995. — 2, вып. 1. — С.
49–69.
4. Кірік О.Є. Розв’язання нелінійної задачі оптимального газорозподілу// Наук.
вісті НТУУ «КПІ». — 2000. — № 5. — С. 30–34.
5. Пшеничный Б.Н. Метод линеаризации. — М.: Наука, 1983. — 136 с.
6. Пшеничный Б.Н., Данилин Ю.М. Численные методы в экстремальных задачах.
— М.: Наука, 1975. — 320 с.
Надійшла 26.11.2003
|
| id | journaliasakpiua-article-171685 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2025-07-17T10:25:24Z |
| publishDate | 2019 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/c2/6c5552908b6ed1a06bfabd1fa49fd9c2.pdf |
| spelling | journaliasakpiua-article-1716852019-06-27T14:30:07Z Application of the modified linearization method for solution of nonlinear flow distribution problems Применение модифицированного метода линеаризации для решения нелинейных задач распределения потоков Застосування модифікованого методу лінеаризації для розв’язання нелінійних задач розподілу потоків Kirik, H. E. The optimization problem of flows calculation in networks of given configuration is considered. The solution is achieved with application of combination of the first and second order linearization methods. The constructed algorithm converges from any initial approach and has the accelerated speed of convergence in comparison with the first order methods. Рассматривается оптимизационная задача расчетов потоков в сетях заданной конфигурации. Решение получается с применением комбинации методов линеаризации первого и второго порядков. Построенный алгоритм сходится из произвольного начального приближения и имеет ускоренную скорость сходимости в сравнении с методами первого порядка. Розглядається оптимізаційна задача розрахунку потоків в мережах заданої конфігурації. Розв’язок отримується із застосуванням комбінації методів лінеаризації першого та другого порядків. Побудований алгоритм збігається з довільного початкового наближення і має прискорену швидкість збіжності у порівнянні з методами першого порядку. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2019-06-27 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/171685 System research and information technologies; No. 3 (2004); 40-49 Системные исследования и информационные технологии; № 3 (2004); 40-49 Системні дослідження та інформаційні технології; № 3 (2004); 40-49 2308-8893 1681-6048 uk https://journal.iasa.kpi.ua/article/view/171685/171389 Copyright (c) 2021 System research and information technologies |
| spellingShingle | Kirik, H. E. Застосування модифікованого методу лінеаризації для розв’язання нелінійних задач розподілу потоків |
| title | Застосування модифікованого методу лінеаризації для розв’язання нелінійних задач розподілу потоків |
| title_alt | Application of the modified linearization method for solution of nonlinear flow distribution problems Применение модифицированного метода линеаризации для решения нелинейных задач распределения потоков |
| title_full | Застосування модифікованого методу лінеаризації для розв’язання нелінійних задач розподілу потоків |
| title_fullStr | Застосування модифікованого методу лінеаризації для розв’язання нелінійних задач розподілу потоків |
| title_full_unstemmed | Застосування модифікованого методу лінеаризації для розв’язання нелінійних задач розподілу потоків |
| title_short | Застосування модифікованого методу лінеаризації для розв’язання нелінійних задач розподілу потоків |
| title_sort | застосування модифікованого методу лінеаризації для розв’язання нелінійних задач розподілу потоків |
| url | https://journal.iasa.kpi.ua/article/view/171685 |
| work_keys_str_mv | AT kirikhe applicationofthemodifiedlinearizationmethodforsolutionofnonlinearflowdistributionproblems AT kirikhe primeneniemodificirovannogometodalinearizaciidlârešeniânelinejnyhzadačraspredeleniâpotokov AT kirikhe zastosuvannâmodifíkovanogometodulínearizacíídlârozvâzannânelíníjnihzadačrozpodílupotokív |