Оптимальний розподіл гідроресурсів у зрошувальних системах мережевої структури
Створено математичну модель транспортування та розподілу ресурсів із узагальненим законом збереження. Для цієї оптимізаційної задачі утримання потоків у певних межах побудовано алгоритми, що базуються на ефективних методах нелінійного програмування. Запропоновано підхід, який дає можливість розв’язу...
Збережено в:
| Дата: | 2010 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
2010
|
| Назва видання: | Системні дослідження та інформаційні технології |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/50071 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Оптимальний розподіл гідроресурсів у зрошувальних системах мережевої структури / О.Е. Кірік, В.В. Остапенко // Систем. дослідж. та інформ. технології. — 2010. — №4. — С. 79-90. — Бібліогр.: 9 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-50071 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-500712013-10-11T12:13:02Z Оптимальний розподіл гідроресурсів у зрошувальних системах мережевої структури Кірік, О.Є. Остапенко, В.В. Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах Створено математичну модель транспортування та розподілу ресурсів із узагальненим законом збереження. Для цієї оптимізаційної задачі утримання потоків у певних межах побудовано алгоритми, що базуються на ефективних методах нелінійного програмування. Запропоновано підхід, який дає можливість розв’язувати задачі розподілу потоків із різнотипними нелінійними цільовими функціями для мереж з довільною кількістю замкнених циклів. Создана математическая модель транспортировки и распределения ресурсов с обобщенным законом сохранения. Для этой оптимизационной задачи удержания потоков в определенных пределах построены алгоритмы, базирующиеся на эффективных методах нелинейного программирования. Предложен подход, который дает возможность решать задачи распределения потоков с разнотипными нелинейными целевыми функциями для сетей с произвольным количеством замкнутых циклов. A mathematical model of transportation and distribution of resources with a generalized conservation law is created. For this optimization problem of flow retention within the given limits, algorithms for efficient nonlinear programming are developed. The proposed approach gives the opportunity to solve problems of flow distribution with multitype nonlinear objective functions for networks with any number of closed loops. 2010 Article Оптимальний розподіл гідроресурсів у зрошувальних системах мережевої структури / О.Е. Кірік, В.В. Остапенко // Систем. дослідж. та інформ. технології. — 2010. — №4. — С. 79-90. — Бібліогр.: 9 назв. — укр. 1681–6048 http://dspace.nbuv.gov.ua/handle/123456789/50071 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 |
2010 |
| topic_facet |
Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/50071 |
| citation_txt |
Оптимальний розподіл гідроресурсів у зрошувальних системах мережевої структури / О.Е. Кірік, В.В. Остапенко // Систем. дослідж. та інформ. технології. — 2010. — №4. — С. 79-90. — Бібліогр.: 9 назв. — укр. |
| series |
Системні дослідження та інформаційні технології |
| work_keys_str_mv |
AT kíríkoê optimalʹnijrozpodílgídroresursívuzrošuvalʹnihsistemahmereževoístrukturi AT ostapenkovv optimalʹnijrozpodílgídroresursívuzrošuvalʹnihsistemahmereževoístrukturi |
| first_indexed |
2025-07-04T11:32:16Z |
| last_indexed |
2025-07-04T11:32:16Z |
| _version_ |
1836715854325088256 |
| fulltext |
© О.Є. Кірік, В.В. Остапенко, 2010
Системні дослідження та інформаційні технології, 2010, № 4 79
УДК 519.8
ОПТИМАЛЬНИЙ РОЗПОДІЛ ГІДРОРЕСУРСІВ У
ЗРОШУВАЛЬНИХ СИСТЕМАХ МЕРЕЖЕВОЇ СТРУКТУРИ
О.Є. КІРІК, В.В. ОСТАПЕНКО
Створено математичну модель транспортування та розподілу ресурсів із уза-
гальненим законом збереження. Для цієї оптимізаційної задачі утримання по-
токів у певних межах побудовано алгоритми, що базуються на ефективних ме-
тодах нелінійного програмування. Запропоновано підхід, який дає можливість
розв’язувати задачі розподілу потоків із різнотипними нелінійними цільовими
функціями для мереж з довільною кількістю замкнених циклів.
Реалізація програм меліорації передбачає вирішення низки складних питань,
передусім екологічних. Меліоративне будівництво вносить зміни в екологіч-
ний баланс великих природних водних систем. Наслідки таких змін для
навколишнього середовища ще недостатньо добре прогнозуються, а тому
домогтися найближчим часом радикальних позитивних змін водного балан-
су в сільському господарстві не вдається. Отже, найважливішим завданням
у найближчі роки є економія води в цій галузі, її раціональне використання.
В зрошувальному секторі не тільки найбільша потреба у воді, але й значні
можливості для її економії — при умові введення ефективних систем управ-
ління.
У роботі розглядається задача розподілу гідроресурсів у зрошувальних
системах мережевої конфігурації, які топологічно можуть бути представлені
як графи із циклами. Питання задоволення всіх користувачів за умови об-
меженої пропускної здатності каналів зрошувальної системи та необхідності
утримання потоків зрошувальної води в певних межах призводить до побу-
дови математичної моделі розподілу потоків з узагальненим законом збере-
ження, що описується за допомогою системи лінійних нерівностей, структу-
ра яких задається відповідним графом.
Математична формалізація розподілу потоків із узагальненим принци-
пом збереження виникла саме при розв’язанні задач керування рухом води в
каналах зрошувальних систем. Вперше її було розглянуто в роботах [1–3],
де запропоновано використовувати метод виключення невідомих із систем
лінійних нерівностей. Загалом, задачі розподілу потоків із узагальненим
принципом збереження найбільш повно досліджені у монографії [4].
У роботі задачу розподілу гідроресурсів представлено у вигляді екст-
ремальної задачі на графі. Економне споживання води розглянуто в кон-
тексті доставки її споживачам найкоротшим шляхом з найменшими витра-
тами. Вибір квадратичної цільової функції зумовлений тим, що на відміну
від лінійної, вона гарантує протікання води вздовж усіх каналів зрошуваль-
ної системи, крім того дозволяє використовувати для розв’язання цієї задачі
добре розроблений апарат квадратичного програмування.
Мета роботи — побудова нових моделей руху потоків у мережах та
розробка алгоритмів знаходження оптимальних потоків на основі неліній-
них методів оптимізації.
О.Є. Кірік, В.В. Остапенко
ISSN 1681–6048 System Research & Information Technologies, 2010, № 4 80
Нові моделі та методи орієнтовано на управління водорозподілом та
раціональним використанням води при експлуатації зрошувальних систем.
МОДЕЛЮВАННЯ РОЗПОДІЛУ ПОТОКІВ ЗА ДОПОМОГОЮ
УЗАГАЛЬНЕНОГО ЗАКОНУ ЗБЕРЕЖЕННЯ
Головною системою обмежень для змінних у класичних задачах розподілу
потоків у мережах є закон збереження. Згідно із цим законом необхідно,
щоб у кожній вершині виконувалася умова матеріального балансу, тобто
різниця кількості речовини, що втікає й витікає з вершини має дорівнювати
споживанню у ній. Розглянемо моделі процесів, в яких ця різниця може на-
лежати деякому проміжку.
У задачі керування рухом води у каналах зрошувальної системи
об’єктами керування є споруди, що перетинають та поділяють канали на
окремі ділянки або б’єфи, насосні станції, які подають воду у канал та водо-
забірні споруди. Основне завдання полягає у виконанні замовлень спожива-
чів при раціональному використанні води. Для розв’язання цього завдання
необхідно утримувати рівень води у каналах у заданих межах. Будемо вва-
жати, що основні споживачі розташовано в кінці ділянок, де також розміще-
но й вимірювальні прилади. Тому вивчатимемо задачу утримання рівнів во-
ди у вузлових точках системи, що сполучають б’єфи. Оскільки зрошувальні
системи мають складну топологічну структуру і містять у собі велику кіль-
кість об’єктів, то для аналізу процесів, які відбуваються у цих системах, не-
обхідно створювати прості, але ефективно працюючі моделі руху води у
кожному б’єфі.
Розглянемо рух води в одному б’єфі. Введемо позначення: ),( txh —
рівень води в точці x у момент t ; l — довжина б’єфу; 0=x ( lx = ) — ко-
ордината верхнього (нижнього) кінця б’єфу; )(tQ ( ( )tq− ) — витрати води,
яка тече через верхню (нижню) гідротехнічну споруду.
Припустимо, що до моменту 0=t у б’єфі був рівномірний постійний
рух води з рівнем .H Нехай у точках 0=x та lx = розташовано джерело та
стік води, які змінюють рівень води у цих точках (інші джерела не врахову-
ються), відповідно до функцій Hth +)(0 та .)( Hthl +
Витрати води — це кількість води, що протікає в одиницю часу через
будь-який переріз.
Рух води в каналі без урахування споруд, що перегороджують, опису-
ється рівняннями Сен-Венана [5]. Ці рівняння є квазілінійними і загалом не
мають аналітичного розв’язку. Але, якщо довести, що хвилі, які передають
витрати води ( )(tQ та )(tq ) відносно малі, то застосовуючи теорію хвиль
малої амплітуди [5], можна отримати розв’язок в аналітичному вигляді. Цей
розв’язок дає значення швидкостей руху води вниз та вгору за течією. По-
значимо ці швидкості відповідно +ω та −ω . Тоді +ω=τ /0 l — час прохо-
дження хвиль від верхнього до нижнього кінця б’єфу. Якщо знехтувати від-
биттям хвиль біля споруд, що перегороджують, то рівень води у точці lx =
буде визначатися за формулою
( ) ( ) ( ) Hththtlh l ++−= 0
0, τα , (1)
Оптимальний розподіл гідроресурсів у зрошувальних системах мережевої структури
Системні дослідження та інформаційні технології, 2010, № 4 81
де 0≥t , 10 ≤≤α — коефіцієнт згасання хвилі, яка пройшла шлях від 0=x
до lx = . Уточнюючи початкові умови, задамо
( ) ( ) 0,0,,0 0 ≤=−≤= ttqttQ τ . (2)
У цьому випадку .)0,( Hlh =
Будемо вважати, що споживачі розташовані у точці lx = . Випадок зі
споживачами, які розосереджені по всьому б’єфу, розглянутий у роботі [6], і
зводиться до випадку зі споживачами, які зосереджені у кінці б’єфу.
Будемо керувати рухом води, враховуючи її витрати, тоді головні об-
меження будуть накладатися на рівні води. Тому опишемо модель, яка
пов’язує витрати води і значення рівня води.
Припустимо, що )()()( 0110 thktQcth
dt
d
−= , ),()()( 1221 thktqcth
dt
d
−−=
де ic , ik , 2,1=i — додатні сталі. Умови (2) гарантують виконання умов
0)0(0 =h , 0)( 0 =τlh . Звідси випливає, що
( ) ( ) ( )∫ −=− −−
t
tk dtQceth
0
0
1
0
0 ,
1
τττ τ (3)
( ) ( ) ( )∫ −−−=−
t
tk dqceth
0
2
0
1 .
2
τττ τ (4)
Надалі необхідно визначити відношення ./ ii ck Зробимо це за допомо-
гою наступних міркувань. Витрати води, що втікає у б’єф, мають дорівнювати
витратам води, що переноситься сформованою хвилею:
( ) ( ) ,0 bthtQ += ω (5)
де b — ширина каналу. Оскільки рівність (5) має виконуватися за умови
const)( =tQ , то
( ) 1
0
1 1
=∫ −−
+
t
tk debc τω τ або ⎟
⎠
⎞⎜
⎝
⎛ += −
+
tkeb
c
k 1
11
1
ω .
Звідси для великих t отримуємо bck +≈ω11 / . Аналогічно ≈22 / ck
b−≈ω .
Як правило, швидкість течії води відносно мала у порівнянні зі швидкістю
переміщення хвиль. Тому спростимо модель, припускаючи, що −+ ω=ω .
У цьому випадку також цілком природно припустити, що ccc == 21 ,
kkk == 21 . Звідси з формул (3), (4) отримуємо
( ) ( ) ( ) ( )[ ] .,
0
0 τττττ dqQceHtlh
t
tk∫ −−+= −− (6)
Розглянемо питання сполучення декількох б’єфів. Для початку візьмемо
ланцюг, що складається з двох б’єфів. Нехай 1Q — витрати води, яка пода-
ється у перший б’єф; 2Q — витрати води, що перетікає із першого б’єфа у
О.Є. Кірік, В.В. Остапенко
ISSN 1681–6048 System Research & Information Technologies, 2010, № 4 82
другий; iq — величина споживання у i -му б’єфі. Нехай ),( tlh ii — рівень
води у кінці i -го б’єфу; iH — рівень до початку керування; ic та ik —
коефіцієнти, які зв’язують рівень і витрату води у i -му б’єфі; iτ — час
проходження хвилею i -го б’єфа; iα — коефіцієнт згасання для i -го б’єфа.
З формули (6) випливає
( ) ( ) ( ) ( ) ( )[ ]∫ −−−+= −−
t
tk dqQQceHtlh
0
121111111 ,, 1 τττττατ
( ) ( ) ( ) ( )[ ]∫ −−+= −−
t
tk dqQceHtlh
0
22222222
2, ττττατ .
Припустимо, що до першого б’єфу є суміжними не один, а два нижніх
б’єфи, які позначимо номерами .3,2=i Вважаємо, що у кінці першого
б’єфу розташовано дві споруди, що перегороджують, одна з яких пропускає
витрати води 2Q у другий б’єф, витрати 3Q у третій б’єф. У цьому випадку з
формули (6) випливає
( ) ( ) ( ) ( ) ( ) ( )[ ]∫ −−−−+= −−
t
tk dqQQQceHtlh
0
1321111111
1, ττττττατ ,
( ) ( ) ( ) ( )[ ]∫ −−+= −−
t
iiiii
tk
iii dqQceHtlh i
0
, ττττατ ( )3,2=i .
Розглянемо випадок сполучення двох б’єфів. Витрати iQ , 2,1=i , які
надходять до б’єфу, що їх сполучає, регулюються кожні своєю перегородкою,
яка знаходиться вгорі б’єфу. Нижні кінці обох б’єфів збігаються, і в цьому
місці розташовано споживача із витратами (стоком) q . Нехай )(th — рівень
води у точці сполучення цих об’єктів, H — початковий рівень. У цьому ви-
падку формула (6) змінюється таким чином:
( ) ( ) ( ) ( ) ( )[ ]∫ −−+−+= −−
t
tk dqQQceHth
0
222111 τττταττατ . (7)
За допомогою формул (6)–(7) опишемо рух води у зрошувальній систе-
мі, структура якої задається направленим графом ),( VNG = . Тут N —
множина вершин, V — множина дуг. Споруди, що перегороджують та на-
сосні станції, які подають воду до системи, інтерпретуватимемо як вершини
графа, а б’єфи — як дуги графа. Дуги направлено від верхнього кінця б’єфу до
нижнього.
Кожній вершині Ni∈ припишемо коефіцієнти ic та ik , які описують
зв’язок між витратами води та рівнями. Нехай )(thi — поточний; iH — по-
чатковий рівні перед i -ою перегородкою; iq — витрати споживача, який роз-
ташовано перед i -ою перегородкою. Будемо вважати, що вздовж дуг ),( ij
проходять потоки jiQ . Нехай jiα — коефіцієнт згасання хвилі при прохо-
дженні дуги ( )ij, , а jiτ — час проходження дуги ),( ij .
Оптимальний розподіл гідроресурсів у зрошувальних системах мережевої структури
Системні дослідження та інформаційні технології, 2010, № 4 83
Для кожної вершини Ni∈ визначимо множини ( )∈∈=+ jiNiiN ,:{)(
}V∈ , }),(:{)( VijNiiN ∈∈=− .
Множина ( )iN + описує всі початкові вершини дуг, які виходять із
вершини i ; множина )(iN − описує всі вершини дуг, які входять у вершину i .
Узагальнимо формули (6)–(7):
( ) ( ) ( )
( )
( ) ( )
( )
∫ ∑∑ ⎥
⎥
⎦
⎤
⎢
⎢
⎣
⎡
−−−+=
+− ∈∈
−−
t
iNk
iik
iNj
jijijii
tk
ii dqQQceHth i
0
τττττατ , .Vi∈ (8)
Зазначимо, що крім (8), величини jiQ мають задовольняти обмеженням
вигляду
max0 jiji QQ ≤≤ , (9)
де max
jiQ — деякі сталі.
Розглянемо питання утримання рівнів )(thi у заданих межах
( ) ViHthH iii ∈≤≤ +− , , (10)
де −
iH , +
iH — деякі сталі.
Сформулюємо задачу. На заданому проміжку часу [ ]T,0 необхідно вибра-
ти величини потоків )(tQ ji , які задовольнятимуть обмеженням (9) так, щоб
на цьому проміжку виконувались нерівності (10).
Припустимо, що ],[ +−∈ iii HHH . Тоді з [4] випливає, що умови (10) ви-
конуються, якщо для будь-якого [ ]Tt ,0∈ виконуються нерівності
( ) ( )
( )
( ) ( )
( )
≤
⎥
⎥
⎦
⎤
⎢
⎢
⎣
⎡
−−−≤− ∫ ∑∑
+− ∈∈
−−−
T
iNk
iik
iNj
jijiji
Tk
iii tqtQtQdecHH i
0
ταττ
., ViHH ii ∈−≤ + (11)
Система нерівностей (11) залежить від T . Оскільки 0>ik , то безпосе-
редньою перевіркою можна показати, що (11) випливає із системи
[ ] ( )
( )
−−≤− ∑
−∈
−
iNj
jijijiii
i
i tQHH
c
k
τα
( ) ( )
( )
[ ] ., ViHH
c
k
tqtQ ii
i
i
iNk
iik ∈−≤−− +
∈
∑
+
(12)
Система нерівностей (12) становить узагальнений закон збереження.
Розв’язуючи (12) разом із обмеженнями (9), одержуємо розв’язок задачі
утримання (10).
Узагальнимо задачу (12), (9). Розглянемо потоки, які описуються систе-
мою лінійних нерівностей:
О.Є. Кірік, В.В. Остапенко
ISSN 1681–6048 System Research & Information Technologies, 2010, № 4 84
( )
( )
( )
( )
,, ViAtxtx i
iNk
ikik
iNj
jijiji ∈∈−− ∑∑
+− ∈∈
βτα (13)
( ) ( ) ( ) [ ]∞∈∈∈ ,0,,, tEijtBtx jiji . (14)
Тут )(tAi , )(tB ji — задані проміжки, залежні від часу; 0>jiα і
0>ikβ — сталі; jiτ — час, за який течія )(tx ji проходить дугою ( ) ., ij Пе-
рехід від системи (12), (9) до системи (13), (14) здійснюється за формулами
( ) ( ) ( ) [ ],,0,1, max
jijiikjiji QtBtQtx === β
( ) ( ) ( ) ( )tqHH
c
k
HH
c
k
tA iii
i
i
ii
i
i
i +⎥
⎦
⎤
⎢
⎣
⎡
−−= +− , .
Якщо не враховувати час добігання хвилі, тобто надати значення
0=τ ji , то у кожний момент t формули (13) та (14) будуть утворювати систему
лінійних нерівностей. Якщо систему (13), (14) розглядати за ),0( ∞∈t і при
цьому const)( ≡tAi та const)( ≡tBij для всіх Ni∈ , Vji ∈),( , то можна об-
рати const)( ≡txij і система (13), (14) знову стає системою лінійних нерів-
ностей. Фізично цей випадок означає пошук течій при постійному режимі.
Отже, задача моделювання руху води за допомогою узагальненого за-
кону збереження без урахування часу добігання зводиться до розв’язання
систем лінійних алгебраїчних нерівностей із спеціальною структурою, що ви-
значається за допомогою відповідних графів.
ОПТИМІЗАЦІЙНА ЗАДАЧА РОЗПОДІЛУ ПОТОКІВ ІЗ УТРИМАННЯМ
РІВНІВ ВОДИ У ЗАДАНИХ МЕЖАХ
Нехай водорозподільчу мережу представлено у вигляді скінченого зв’язного
плоского орієнтовного графа ),( VNG , де N та V відповідно множини його
вершин і дуг, причому кожній дузі Vji ∈),( поставлено у відповідність вер-
шини Nji ∈, , що є її початком та кінцем. Знаючи потреби споживачів у во-
ді у вершинах графа, необхідно розподілити потоки води таким чином, аби
доставити воду споживачам оптимальним шляхом.
Сформулюємо оптимізаційну задачу так:
( )
∑
∈
→=
Vji
ijij xlF
,
2 min
2
1 , (15)
( ) ( )
,+
∈∈
− ∑∑
−+
≤−≤ i
iNj
jiji
iNj
ijiji dxxd αα Ni∈ , (16)
,+− ≤≤ ijijij rxr ( ) Vji ∈. . (17)
Оптимальний розподіл гідроресурсів у зрошувальних системах мережевої структури
Системні дослідження та інформаційні технології, 2010, № 4 85
Якщо дуга Vji ∈),( відображає певну ділянку (б’єф) водорозподільчої
мережі довжиною ijl , то jiij xx −= — величина потоку вздовж цієї дуги, а
0>ijα — коефіцієнт, що характеризує втрати води при її проходженні
вздовж цієї ділянки.
Узагальнений закон збереження (16) відображає той факт, що витра-
ти води у кожній вершині (різниця потоків, які витікають із вершини та
втікають у неї) залишаються у певних межах, що гарантують задоволення
споживачів. Величина потоків обмежується пропускною здатністю мере-
жі (17).
Цільова функція (15) задачі є сепарабельною і, з огляду на фізичний
зміст коефіцієнтів ijl , ,),( Vji ∈ додатньовизначеною. Таким чином, задача
(15)–(17) — це задача квадратичного програмування і її розв’язок, за умови
сумісності обмежень, завжди існує [7]. Виведемо необхідні умови екстре-
муму для цієї задачі.
Представимо обмеження (16) у вигляді системи односторонніх нерів-
ностей
( ) ( )
+
∈∈
≤α−α ∑∑
−+
i
iNj
jiji
iNj
ijij dxx , (18)
( ) ( )
−
∈∈
−≤α+α− ∑∑
−+
i
iNj
jiji
iNj
ijij dxx , (19)
і побудуємо для задачі (15), (17), (18), (19) функцію Лагранжа:
( )
( )
( )
( )
( )
∑ ∑∑∑
∈ ∈
−+
∈
−+
∈
−
⎥
⎥
⎦
⎤
⎢
⎢
⎣
⎡
−−−+=
−+Ni iNj
jijiii
iNj
ijijii
Vji
ijij xppxppxlL αα
,
2
2
1
( )=−− ∑
∈
−−++
Ni
iiii dpdp
( ) ( )[ ]
( )
( )∑∑
∈
−−++
∈
−+−+ −−
⎭
⎬
⎫
⎩
⎨
⎧ −−−+=
Ni
iiii
Vji
jijjijiiijijij dpdpppppxxl
.
2
2
1 αα . (20)
Тут −+
ii pp , Ni∈ — множники Лагранжа, що відповідають обмежен-
ням (18), (19).
Якщо точка }~,~,~{ −+
iiij ppx , де ,~ +− ≤≤ ijijij rxr Vji ∈),( , ,0~ ≥+
ip 0~ ≥−
ip ,
Ni∈ є сідловою точкою функції Лагранжа (20), то ijx~ є розв’язком вихідної
задачі [7].
Перш ніж перейти до побудови двоїстої задачі, розглянемо властивості
функції uxlxuxh += 2
2
1),( , де 0>l . Функція ),( uxh є опуклою при довіль-
ному u , а її похідна ulxuxhx +=),( є монотонно зростаючою функцією.
Розв’язок одновимірної задачі квадратичного програмування
О.Є. Кірік, В.В. Остапенко
ISSN 1681–6048 System Research & Information Technologies, 2010, № 4 86
( )uxh
rxr
,min
+− ≤≤
(21)
завжди існує.
Оскільки похідна цільової функції цієї задачі — монотонно зростаюча
функція, то при 0≥+− ulr мінімальне значення досягається на нижній гра-
ниці допустимого інтервалу −= rux )( . Якщо 0≤++ ulr , то з огляду на
від’ємність похідної, функція h спадає і її мінімальне значення досягається
на верхній межі інтервалу += rux )( . При 0<+− ulr , 0>++ ulr існує єди-
ний корінь всередині інтервалу ( )+−∈ rrx , , який знаходиться з умови
0=+ ulx .
Таким чином, точка мінімуму задачі (21) або приймає постійні значен-
ня, що співпадають із −r чи +r , або всередині інтервалу допустимості, за-
лежить від u .
Позначимо )(~ uh — мінімальне значення функції ),(~ uxh для
),( +−∈ rrx . Тоді, згідно з теоремою про похідну від функції мінімуму [7],
функція )(~ uh є диференційованою по u і її похідна дорівнюватиме значен-
ню похідної від ( )yxh , по u , взятій у точці мінімуму )(ux : )()( uxuhu =′ .
Враховуючи сказане вище, випишемо необхідні умови екстремуму для
одновимірної задачі
( ) ( )[ ]
⎭
⎬
⎫
⎩
⎨
⎧ −−−+ −+−+
≤≤ +− jijjijiiijijij
rxr
ppppxxl
ijijij
αα2
2
1min . (22)
Теорема 1. Якщо −= ijij rx , то похідна цільової функції задачі (22) має
бути невід’ємною: ijiijijjijij ppppxl αα )()( −+−+ −−−≥ . Якщо += ijij rx , то
похідна цільової функції задачі (22) має бути недодатньою: ≤ijij xl
ijiijijj pppp αα )()( −+−+ −−−≤ . Якщо ijx знаходиться всередині інтервалу,
то похідна має дорівнювати нулю ijiijijjijij ppppxl αα )()( −+−+ −−−= .
Позначимо ijiijijjij ppppp αα )()( −+−+ −−−= . З необхідних умов екст-
ремуму отримуємо, що мінімум L з врахуванням простих обмежень
],[ +−∈ ijijij rrx досягається в точці
⎪
⎪
⎩
⎪
⎪
⎨
⎧
≥
≤≤−
≤
=
++
+−
−−
.якщо,
,якщо,
,якщо,
ijijijij
ijijijijij
ij
ij
ijijijij
ij
crpr
lrplr
l
p
lrpr
x (23)
Згідно із теорією двоїстості [7], розв’язок задачі (14), (17), (18), (19)
еквівалентний максимізації вгнутої неперервно-диференційованої функ-
ції L
ijijij rxr +− ≤≤
=Φ min .
Оптимальний розподіл гідроресурсів у зрошувальних системах мережевої структури
Системні дослідження та інформаційні технології, 2010, № 4 87
Знаючи оптимальні значення 0~,0~ ≥≥ −+
ii pp , Ni∈ і використовуючи
формули (23), можемо повернутися до вихідних змінних ,~
ijx Vji ∈).( , що і
дає розподіл потоків, що мінімізує витрати під час транспортування води.
Використовуючи (23), конкретизуємо вигляд функції Φ :
( ) ( )
( )
∑ ∑
∈ ∈
ψ−ϕ=Φ
Vji Ni
iiijij pp
.
, (24)
де
( )
⎪
⎪
⎪
⎩
⎪
⎪
⎪
⎨
⎧
≥+
≤≤−
≤+
=
+++
+−
−−−
,якщо,)(
2
1
,якщо,
2
1
,якщо,)(
2
1
2
2
2
ijijijijijijij
ijijijijij
ij
ij
ijijijijijijij
ijij
lrprprl
lrplr
l
p
lrprpbl
pϕ
( ) −−++ −= iiiiii dpdppψ .
Враховуючи сказане вище, )()( ijijijij pxp =′ϕ .
Остаточно, похідні цільової функції двоїстої задачі дорівнюють
( ) ( ) +
∈∈
+
+−−−=
Φ ∑∑ i
Nj
jiijjiij
Nj
jiij
i
dxx
dp
d αααα ,
( ) ( ) −
∈∈
−
−−−−=
Φ ∑∑ iji
Nj
jiij
Nj
ijijji
i
dxx
dp
d αααα .
Таким чином, ми перейшли від вихідної задачі до двоїстої задачі з про-
стими обмеженнями
Φmax , (25)
Niipip ∈≥−≥+ ,0,0 . (26)
Цільова функція двоїстої задачі (25), (26) має неперервні похідні і ці
похідні ми можемо обчислити. Отже, маємо можливість застосувати довіль-
ний метод оптимізації, модифікований із врахуванням простих обмежень
(26). Зокрема це може бути метод спряжених градієнтів.
Позначимо },...,{ 1
+++ = Nppp , },...,{ 1
−−− = Nppp . Тоді },{ −+= ppp ,
NRp 2∈ — вектор двоїстих змінних. Введемо позначення також для мно-
жини індексів двоїстих змінних }2,...,2,1{ NJ = .
Загальна ідея розв’язання задачі (25), (26) полягає в упорядкованому
переборі граней допустимої множини. Задаємо довільну точку, що задо-
вольняє нерівностям (26). Виділяємо серед обмежень ті, що задовольняють-
ся як рівності. Ці обмеження визначають деяку грань багатогранної множи-
ни. Знаходимо максимум )( pΦ на цій грані, застосовуючи метод спряжених
градієнтів. Отримуємо точку, яка є розв’язком поставленої задачі, інакше
О.Є. Кірік, В.В. Остапенко
ISSN 1681–6048 System Research & Information Technologies, 2010, № 4 88
можна вказати перехід на деяку нову грань, після чого процедура повто-
рюється. Ця нова грань утворюється у випадку, якщо одне або декілька
обмежень-нерівностей обертаються у рівності, тобто приєднуються до
активного набору.
Опишемо дії на одній зовнішній ітерації процесу розв’язання задачі
(25), (26), беручи до уваги, що внутрішніми ітераціями будуть кроки алгори-
тму спряжених градієнтів для вгнутих функцій
s
s
ss zpp β+=+1 , (27)
де
( )00 pz Φ= , ( ) ( ) ( ) ( )
( )
1
1
1
,
,
−
−
−
Φ′
Φ′−Φ′Φ′
+Φ′= s
ss
sss
ss z
zp
ppp
pz , 0>s ,
а вибір множника sβ , на кожному s кроці здійснюється з вимоги
)(max)(
0
sss
s
s zpzp ββ
β
+Φ=+Φ
≥
. ...,2,1,0=s .
Нагадаємо, що необхідні та достатні умови того, аби точка *p була
розв’язком задачі (25, 26) описуються співвідношеннями:
( )( ) 0* =Φ′ kp , якщо 0* >kp , Jk∈ , (28)
( )( ) 0* ≤Φ′ kp , якщо 0* =kp , Jk∈ ,
де kp))((Φ′ — k - та компонента вектора )( pΦ′ .
Покладемо },0:{)( JkpkpJ k ∈== . Починаємо з довільної точки 0p ,
що задовольняє обмеженням 00 ≥kp , Jk ∈ . Знайдемо множину )( 0pJ .
Якщо 0))(( 0 =Φ′ kp , )( 0pJi∉ , то це означає, що точка 0p є точкою
мінімуму )( pΦ за обмежень 0=ip , )( 0pJi∈ . Якщо до того ж
0))(( 0 ≤Φ′ kp для )( 0pJk∈ , то 0p є розв’язком задачі (25), (26), оскільки в
цій точці виконано необхідні й достатні умови максимуму (28).
Якщо 0))(( 0 >Φ′ kp для деяких )( 0pJk∈ , то покладемо =′J
}0))((:)({ 00 ≤Φ′∈= kppJi і будемо застосовувати метод спряжених гра-
дієнтів для максимізації )( pΦ , беручи за змінні тільки kp , Jk ′∉ і зали-
шаючи всі kp рівними нулю для Jk ′∈ . Якщо ж існують такі індекси k , що
0))(( 0 ≠Φ′ kp , )( 0uJi∉ , то в цьому випадку покладаємо )( 0pJJ =′ .
При цьому ми весь час маємо контролювати виконання обмежень
0>kp , JJk ′∈ \ . Якщо крок методу спряжених градієнтів призводить до
від’ємності однієї з цих змінних, то довжина кроку обмежується таким
чином, аби в точності обернути цю змінну в нуль. Для цього при обчислен-
нях за методом спряжених градієнтів весь час додатково обчислюємо
величину sβ :
Оптимальний розподіл гідроресурсів у зрошувальних системах мережевої структури
Системні дослідження та інформаційні технології, 2010, № 4 89
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
−= s
k
s
k
ks
z
p
minβ , (29)
де мінімум береться по всіх JJk ′∈ \ , для яких 0<s
kz , і порівнюємо цю
величину з sβ .
Якщо ss ββ < , то
s
ks
s
k
s
k zpp β+=+1 , Jk ′∉ , 01 ==+ s
k
s
k pp , Jk ′∈ . (30)
Якщо ss ββ ≥ , то
s
ks
s
k
s
k zpp β+=+1 , Jk ′∉ , 01 ==+ s
k
s
k pp , Jk ′∈ . (31)
Процес обчислень перерветься за скінчене число кроків. При цьому або
буде знайдено точку 1+sp таку, що в ній )( pΦ досягає мінімуму при умовах
0=kp , Jk ′∈ , або таку, де ss ββ ≥ , тобто якесь із неактивних обмежень
порушується. В останньому випадку JpJ s
k ′⊃+ )( 1 , причому існують
)( 1+∈ s
kpJk , такі що Jk ′∉ . В обох випадках точка 1+s
kp , отримана за про-
цедурою (30) або (31) вважається за початкову і процес повторюється.
Метод спряжених градієнтів будує послідовність точок, в яких цільова
функція монотонно зростає. Саме це гарантує, що число граней є скінченим,
тому що активні набори не можуть повторюватися.
ОЦІНКА ШВИДКОСТІ ЗБІЖНОСТІ
Як показано вище, запропонований у попередньому розділі алгоритм здійс-
нює пошук розв’язку шляхом перебору скінченої кількості граней. Це озна-
чає, що збіжність процесу в цілому залежить від збіжності методу спряже-
них градієнтів при максимізації на відповідній грані. Функція (24) є
кусково-квадратичною. Отже, є справедливою
Теорема 2. Якщо точка максимуму *p кусково-квадратичної функції
(24) двоїстої задачі (25), (26) належить квадратичній складовій, то метод збі-
гається за скінчене число кроків. Якщо ж точка *p є місцем поєднання декі-
лькох квадратичних функцій, то процес збігається зі швидкістю методу
спряжених градієнтів для вгнутих функцій.
ВИСНОВКИ
Формулювання проблеми розподілу ресурсів у вигляді оптимізаційної задачі
дозволяє не тільки вирішити питання задоволення споживачів, але й мінімі-
зувати витрати на транспортування. Крім того, перевагою такої математич-
ної моделі є незалежність методу розв’язання задачі від структури графа, що
дає можливість описувати зрошувальні системи складної структури, з дові-
льною кількістю замкнених циклів.
О.Є. Кірік, В.В. Остапенко
ISSN 1681–6048 System Research & Information Technologies, 2010, № 4 90
Відмітимо, що запропоновану теорію можна застосовувати до широкого
кола розподільчих мереж. Так, у випадку транспортування газу в магістральних
трубопроводах виникає задача утримання (10), де )(thi — тиск газу в певній
точці трубопроводу; iH — початковий тиск перед i -ю станцією підкачки;
),( tlh ii — тиск газу у кінці i -го проміжку трубопроводу; ic та ik — кое-
фіцієнти, які зв’язують тиск і витрати газу у i -му проміжку трубопроводу
iq ; iτ — час проходження хвилею i -го проміжку трубопроводу; iα — кое-
фіцієнт згасання для i -го проміжку трубопроводу.
Моделювання процесу розподілу потоків здійснюється за допомогою
задачі квадратичного програмування. За наявності більш складної неліній-
ної функції цілі можна замінити вихідну задачу послідовністю задач квадра-
тичного програмування, що будуть апроксимувати, у певному сенсі, вихідну
задачу, як це робиться для потокових задач з класичним законом збережен-
ня [8, 9].
ЛІТЕРАТУРА
1. Остапенко В.В., Павлыгин А.И. Динамические потоки в сетях для обобщенного
закона Кирхгофа // Кибернетика и системный анализ. — 1996. — № 3. —
С. 96–102.
2. Остапенко В.В., Павлыгин А.И. Линейные неравенства для обобщения закона
Кирхгофа // Кибернетика и системный анализ. — 1997. — № 3. —
С. 130–148.
3. Остапенко В.В., Финин Г.С. Моделирование движения воды с обобщенным за-
коном Кирхгофа // Проблемы управления и автоматики. — 1999. — № 4. —
С. 86–90.
4. Остапенко В.В., Скопецький В.В., Фінін Г.С. Розподіл ресурсів у просторі та
часі. — Київ: Наук. думка, 2003. — 322 с.
5. Картвелишвили Н.А. Потоки в недеформируемых руслах. — Л.: Гидро-
метеоиздат, 1978. — 279 с.
6. Данильченко В.Е., Остапенко В.В., Яковлева А.П. Математические вопросы
моделирования и управления в задачах водораспределения. — Киев,
1989. — 18 с. (Препр. / АН УССР. Ин–т кибернетики им. В.М. Глушкова;
89-14).
7. Пшеничный Б.Н. Выпуклый анализ и экстремальные задачи. — М.: Наука,
1980. — 320 с.
8. Кірік О.Є. Алгоритми лінеаризації та спряжених градієнтів для нелінійних
задач розподілу потоків // Наук. вісті НТУУ «КПІ», 2007. — № 3. —
С. 67–73.
9. Кірік О.Є. Алгоритми ітераційного квадратичного програмування для задач
оптимального розподілу потоків // Системні дослідження та інформаційні
технології. — 2008. — № 1. — С. 101–113.
Надійшла 18.03.2010
|