Алгоритми розв'язання задачі сепарабельного квадратичного програмування
Розглянуто математичну модель задачі сепарабельного квадратичного програмування та методи розв'язання задачі за допомогою алгоритмів негладкої оптимізації. Описано програмні реалізації методів на основі модифікації r-алгоритму. Наведено результати обчислювальних експериментів з розв'язуван...
Gespeichert in:
| Veröffentlicht in: | Компьютерная математика |
|---|---|
| Datum: | 2017 |
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Ukrainisch |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2017
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/168465 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Алгоритми розв'язання задачі сепарабельного квадратичного програмування / П.І. Стецюк, О.В. Фесюк, В.А. Сидорук // Компьютерная математика. — 2017. — № 2. — С. 137-146. — Бібліогр.: 11 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859482931988267008 |
|---|---|
| author | Стецюк, П.І. Фесюк, О.В. Сидорук, В.А. |
| author_facet | Стецюк, П.І. Фесюк, О.В. Сидорук, В.А. |
| citation_txt | Алгоритми розв'язання задачі сепарабельного квадратичного програмування / П.І. Стецюк, О.В. Фесюк, В.А. Сидорук // Компьютерная математика. — 2017. — № 2. — С. 137-146. — Бібліогр.: 11 назв. — укр. |
| collection | DSpace DC |
| container_title | Компьютерная математика |
| description | Розглянуто математичну модель задачі сепарабельного квадратичного програмування та методи розв'язання задачі за допомогою алгоритмів негладкої оптимізації. Описано програмні реалізації методів на основі модифікації r-алгоритму. Наведено результати обчислювальних експериментів з розв'язування квадратичних задач знаходження електричних навантажень енергоблоків теплових електростанцій ОЕС України.
Рассмотрена математическая модель задачи сепарабельного квадратичного программирования и методы решения задачи с помощью алгоритмов негладкой оптимизации. Описаны программные реализации методов на основе модификации r-алгоритма. Приведены результаты вычислительных экспериментов для решения квадратичных задач нахождения электрических нагрузок энергоблоков тепловых электростанций ОЭС Украины.
A mathematical model of the problem of separable quadratic programming and the methods for solving the problem using nonsmooth optimization algorithms are given. Software implementations of the methods based on modification of r-algorithm are described. Computational experiment results for the quadratic problems of finding the electrical loads for power units of thermal power plants of the Ukrainian IPS are presented.
|
| first_indexed | 2025-11-24T15:05:08Z |
| format | Article |
| fulltext |
Компьютерная математика. 2017, № 2 137
Розглянуто математичну модель
задачі сепарабельного квадратич-
ного програмування та методи
розв'язання задачі за допомогою
алгоритмів негладкої оптимізації.
Описано програмні реалізації ме-
тодів на основі модифікації r-ал-
горитму. Наведено результати
обчислювальних експериментів з
розв'язування квадратичних задач
знаходження електричних наван-
тажень енергоблоків теплових
електростанцій ОЕС України.
П.І. Стецюк, О.В. Фесюк,
В.А. Сидорук, 2017
УДК 519.85
П.І. СТЕЦЮК, О.В. ФЕСЮК, В.А. СИДОРУК
АЛГОРИТМИ РОЗВ'ЯЗАННЯ ЗАДАЧІ
СЕПАРАБЕЛЬНОГО КВАДРАТИЧНОГО
ПРОГРАМУВАННЯ
Вступ. Функцію 1( , , )nf x x від n змінних
називають сепарабельною, якщо її можна
представити у вигляді 1
1
( , , ) ( )
n
n i i
i
f x x f x
,
де ( )i if x – функція від однієї змінної,
1, ,i n . Сепарабельне програмування (se-
parable programming) – сукупність методів
розв’язання задач нелінійного програмуван-
ня з сепарабельною цільовою функцією та
лінійною системою обмежень. Задачею сепа-
рабельного нелінійного програмування є
ELD-задача завантаження енергосистеми [1].
У ній цільова функція задає сумарні витрати
умовного палива, необхідні для функціону-
вання енергосистеми, та визначається неза-
лежними один від одного навантаженнями
енергоблоків.
У статті розглядаються алгоритми розв’я-
зання задачі сепарабельного квадратичного
програмування та їх застосування до квадра-
тичних ELD-задач завантаження енергосис-
теми. У розділі 1 наведено опис задачі сепа-
рабельного квадратичного програмування та
алгоритмів її розв'язання за допомогою ме-
тодів негладкої оптимізації. У розділі 2 наве-
дено модифікацію r-алгоритму, яка покладе-
на в основу програмних реалізацій послідов-
ного та паралельного алгоритмів. У розділі 3
описано застосування алгоритмів для розв’я-
зання ELD-задачі з квадратичною цільовою
функцією. Приведено результати обчислю-
вальних експериментів щодо задач знаход-
ження електричних навантажень енергобло-
ків теплових електростанцій ОЕС України
для різних за напруженістю графіків заван-
таження працюючих енергоблоків ТЕС.
П.І. СТЕЦЮК, О.В. ФЕСЮК, В.А. СИДОРУК
138 Компьютерная математика. 2017, № 2
1. Задача сепарабельного квадратичного програмування та її властиво-
сті. Розглянемо таку задачу квадратичного програмування: знайти
* 2
1
min ( ) ( )
n
n
i i i i i
x E i
f f x c x d x e
(1)
при обмеженнях
,low upb Ax b (2)
,low upx x x (3)
де 0ic , ic R , id R , ie R , 1,...,i n , m nA R – m n -матриця, low mb R
і up mb R – нижні (low) і верхні (up) границі, накладені на рядки-обмеження,
low nx R і up nx R – нижні і верхні границі можливих значень змінних nx R .
Задачу (1) – (3) можна записати у еквівалентній формі: знайти
* 2
1
min ( )
n
n
i i i i i
x E i
f c x d x e
(4)
при обмеженнях
1
0, 1, , ,
n
up
ij j i
j
a x b i m
(5)
1
0, 1, , ,
n
low
ij j i
j
a x b i m
(6)
0, 1, , ,up
i ix x i n (7)
0, 1, , .low
i ix x i n (8)
Задача (4) – (8) має n змінних та 2 2M m n лінійних обмежень. Вона є
частковим випадком задачі квадратичного програмування, що обумовлено сепа-
рабельністю цільової функції. Задачу (4) – (8) та еквівалентну їй задачу (1) – (3)
будемо називати задачами сепарабельного квадратичного програмування.
Якщо 0ic для всіх 1, ,i n , то цільова функція (4) є строго опуклою.
Це гарантує єдиний розв'язок задачі (4) – (8), якщо система лінійних обмежень
(5) – (8) є сумісною. У випадку, коли 0ic для деяких 1, ,i n , то задача
(4) – (8) може мати багато розв'язків. Це стосується також випадку, коли 0ic
для всіх 1, ,i n і задача (4) – (8) переходить у задачу лінійного програмування.
Задачу (4) – (8) можна розв’язати за допомогою стандартних програм
розв’язання задач квадратичного програмування. Для цього можна використати
такі відомі програми як Ipopt, Knitro, LANCELOT, LOQO, MINOS та інші. Для
розв’язання задачі (4) – (8) можна застосувати методи мінімізації негладких
опуклих функцій. Для цього задачу (4) – (8) потрібно звести до задачі безумов-
ної мінімізації негладкої опуклої функції, що легко зробити за допомогою мето-
ду негладких штрафних функцій.
АЛГОРИТМИ РОЗВ'ЯЗАННЯ ЗАДАЧІ СЕПАРАБЕЛЬНОГО КВАДРАТИЧНОГО ПРОГРАМУВАННЯ
Компьютерная математика. 2017, № 2 139
Нехай система обмежень (5) – (8) задовольняє умові Слейтера. Для задачі
(4) – (8) позначимо * * *
1{ ,..., }mU U U та * * *
1{ ,..., }mu u u – оптимальні значення
множників Лагранжа для обмежень (5) та (6), * * *
1{ ,..., }nV V V та * * *
1{ ,..., }nv v v –
оптимальні значення множників Лагранжа для обмежень (7) та (8), а 1 2{ , }P P P
– вектор із двох додатних штрафних коефіцієнтів.
Теорема 1. Якщо * * * *
1 1 1max{ ,..., , ,..., }m mP U U u u і * * * *
2 1 1max{ ,..., , ,..., }n nP V V v v ,
то задача мінімізації негладкої опуклої функції
2
1
( ) min ( )
n
n
P i i i i ix E i
F x c x d x e
1 1
1 1 1 1
max{0, } max{0, }
m n m n
up low
ij j i ij j i
i j i j
P a x b P a x b
2 2
1 1
max{0, } max{0, }
n n
up low
i i i i
i i
P x x P x x
(9)
еквівалентна задачі (4) – (8) в тому сенсі, що множина мінімумів функції ( )PF x
збігається з множиною оптимальних розв'язків задачі (4) – (8).
Теорема 1 є наслідком теореми 4.2 [2, стор. 188], якщо для задачі (4) – (8)
вибрати найпростіший варіант негладкої функції штрафу
0, якщо 0,
( )
, якщо 0,i
i
t
p t
c t t
1,...,2 2i m n ,
а коефіцієнти ic апроксимувати зверху максимальними значеннями оптималь-
них множників Лагранжа, які відповідають обмеженням (5), (6) та обмеженням
(7), (8), відповідно.
На основі теореми 1 можна будувати різноманітні алгоритми для
розв’язання задачі сепарабельного квадратичного програмування, вибираючи
різні методи для мінімізації негладкої опуклої функції виду (9). При цьому
досить впевнитися, що обмеження (5) – (8) задовольняють умові Слейтера. Така
перевірка зводиться до задачі мінімізації негладкої опуклої функції.
Теорема 2. Система обмежень (5) – (8) задовольняє умові Слейтера, якщо
негладка опукла функція
2
1
( ) ( ) min ( )
n
n
P P i i i i ix E i
x F x c x d x e
1 1
1 1 1 1
max{0, } max{0, }
m n m n
up low
ij j i ij j i
i j i j
P a x b P a x b
2 2
1 1
max{0, } max{0, }
n n
up low
i i i i
i i
P x x P x x
(10)
досягає мінімального значення * *( ) 0P P x при 1 0P і 2 0P .
П.І. СТЕЦЮК, О.В. ФЕСЮК, В.А. СИДОРУК
140 Компьютерная математика. 2017, № 2
Для мінімізації негладких опуклих функцій ( )PF x та ( )P x можно викорис-
товувати подану далі модифікацію r-алгоритмів Шора (субградієнтних методів
з розтягування простору в напрямку різниці двох послідовних субградієнтів).
2. r-алгоритм та програма ralgb5a [3]. Розглянемо задачу пошуку точки
мінімуму деякої опуклої функції ( )f x , nx R . Мінімальне значення функції
позначимо * *= ( )f f x , де * *.x X Будемо вважати, що множина мінімумів *X
є обмеженою, тобто виконується умова lim ( ) =
x
f x
, яка забезпечує
коректність регулювання кроку в r -алгоритмах. Позначимо – коефіцієнт роз-
тягування простору, > 1.
Означення. ( )r -алгоритмом мінімізації функції ( )f x називається ітера-
тивна процедура знаходження послідовності n -вимірних векторів =0{ }k kx
та послідовності n n -матриць =0{ }k kB за наступним правилом:
1 1= , = ( ), = 0,1,2, ,k k k k k k k kx x h B B B R k (11)
де
*
0
( )
= , = arg min ( ),
( )
T
k f k
k k k k k kT h
k f k
B g x
h h f x hB
B g x
(12)
1= , = ( ) ( ).
T
k k
k k f k f kT
k k
B r r g x g x
B r
(13)
Тут 0x – стартова точка; 0 = nB I – одинична n n -матриця1; *
kh – величина
кроку до точки мінімуму функції ( )f x у напрямку нормованого антисуб-
градієнта в перетвореному просторі змінних; ( ) = ( 1) T
nR I – оператор
стиснення простору субградієнтів у нормованому напрямку з коефіцієнтом
= 1 < 1 ; ( )f kg x і 1( )f kg x – субградієнти функції ( )f x в точках kx та 1kx .
Якщо на ітерації k процесу (11) – (13) виконані деякі критерії (умови) зупинки,
то вважаємо *k k , *
k kx x і закінчуємо роботу алгоритму.
Коментар. На кожній ітерації r -алгоритмів реалізується субградієнтний спуск
для опуклої функції ( ) = ( )ky f B y в перетвореному просторі змінних = ky A x ,
де 1=k kA B . Дійсно, якщо обидві частини формули 1 =k k k k kx x h B домножити
зліва на матрицю kA , то отримаємо
1 1
( ) ( )
= = = = ,
( )( )
T
k f k k
k k k k k k k k k k kT
kk f k
B g x g y
y A x A x h y h y h
g yB g x
(14)
1За матрицю 0B часто вибирають діагональну матрицю nD з додатними коефіцієнтами
на діагоналі, за допомогою якої здійснюється масштабування змінних.
АЛГОРИТМИ РОЗВ'ЯЗАННЯ ЗАДАЧІ СЕПАРАБЕЛЬНОГО КВАДРАТИЧНОГО ПРОГРАМУВАННЯ
Компьютерная математика. 2017, № 2 141
де вектор ( ) = ( )T
k k f kg y B g x є субградієнтом функції ( ) = ( )ky f B y у точці
=k k ky A x простору змінних = ky A x . Субградієнт функції ( )f x задовільняє
нерівності
( ) ( ) ( ( )) ( ) ,T n
k f k kf x f x g x x x x E
звідки, здійснюючи заміну змінних = kx B y , отримаємо
( ) ( ) ( ( )) ( ) = ( ) ( ( )) ( ) .T T T n
k k f k k k k ky y B g x y y y g y y y y E
Сімейство ( )r -алгоритмів визначається коефіцієнтом розтягування про-
стору 1 і послідовністю величин кроків =0{ }k kh . Їх вибір (допускається
, що відповідає 0 ) у поєднанні з вибором критеріїв зупинки
визначають той чи інший варіант ( )r -алгоритмів.
Регулювання кроку. Регулювання величини kh задає певний спосіб
реалізації одновимірного спуску в напрямку нормованого антисубградієнта
функції ( ) = ( ),ky f B y який здійснюється в перетвореному просторі змінних
= ky A x (див. формулу (14)). В r -алгоритмах використовуються два способи
регулювання кроку [2, 4].
При першому способі величина kh вибирається з умови *=k kh h ( *
k kh h ),
що означає точний (чи наближений) одновимірний пошук мінімуму функції,
який гарантує, що r -алгоритми є монотонними (майже монотонними) по функ-
ції, яка мінімізується. Таке регулювання кроку використовуться в теоретично
обгрунтованих модифікаціях ( )r -алгоритмів, коли коефіцієнт можна виби-
рати досить великим. Це дозволило показати, що граничний варіант r -алго-
ритмів (при 0 ) є проективним методом спряжених градієнтів, та об-
грунтувати для граничного варіанта r -алгоритмів з відновленням квадратичної
швидкості збіжності до точки мінімуму опуклої двічі неперервної диферен-
ційовної функції при деяких умовах гладкості та регулярності. Знайдено також
такі умови для кусково-гладких опуклих функцій, при яких ( )r -алгоритм
збігається до точки мінімуму.
Другий спосіб регулювання кроку полягає у тому, що величина kh налаш-
товується (адаптується) в процесі виконання одновимірного спуску, який завер-
шується, як тільки знайдено субградієнт, що утворює негострий кут з субграді-
єнтом, який визначає напрямок одновимірного спуску (умова завершення спуску
за напрямом). Налаштування величини кроку kh здійснюється за допомогою
чотирьох параметрів: 0 0h – величина початкового кроку (використовується на
першій ітерації, а на кожній наступній уточнюється); 1q ( 1 1q ) – коефіцієнт
зменшення кроку (якщо умова завершення спуску за напрямком виконується
П.І. СТЕЦЮК, О.В. ФЕСЮК, В.А. СИДОРУК
142 Компьютерная математика. 2017, № 2
за перший крок); 2q ( 2 1q ) – коефіцієнт збільшення кроку. Через кожні
hn кроків одновимірного спуску ( 1hh ) величина кроку збільшується в 2q раз.
Оскільки припускається, що lim ( ) =
x
f x
, то після скінченної кількості кроків
адаптивного спуску в напрямку нормованого антисубградієнта обов’язково
виконується умова завершення спуску за напрямом.
Другий спосіб регулювання кроку називається адаптивним і використову-
ється в практичних реалізаціях r -алгоритмів. Тут коефіцієнт не рекомен-
дується вибирати великим. Він має бути узгодженим з коефіцієнтом 1q , тому що
вони обидва, хоча і по різному, впливають на зменшення величини кроку kh .
В результаті визначаються ті два послідовні субградієнти, розтягування за різ-
ницею яких зменшує степінь витягнутості функції у перетвореному просторі
змінних. Цим пояснюється пришвидшена збіжність ( )r -алгоритмів для яруж-
них (з витягнутими поверхнями рівня) функцій. Кількість ітерацій ( )r -алго-
ритму, необхідна для знаходження точки *k
x , для якої *
*( )
k
f x f , емпірично
оцінюється як * ( log(1 ))k O n , де n – кількість змінних.
Octave-функция ralgb5a [3]. Програма ralgb5a – спрощена (для зручності
використання) версія програми ralgb5 [5, с. 383–386]. У ній зафіксовані два най-
більш часто використовувані параметри 2 1.1q і 3hn . Величина початкового
кроку для чергової ітерації може максимально збільшуватися
в 610 раз. У програмі ralgb5a використовується параметр intp (interval for print),
який забезпечує друк інформації про хід процесу мінімізації через кожні intp
ітерацій. Цей параметр дозволяє скоротити протокол друку роботи програми
при мінімізації функції для сотень і тисяч змінних, коли кількість ітерацій
оцінюється тисячами і десятками тисяч. Програма використовує параметри x
і g для зупинки ітераційного процесу в точці * 1[ , ]k kk
x x x , де 1k k xx x
(зупинка за аргументом), або *( )f gk
g x (зупинка за нормою градієнта, яка
використовується для гладких функцій). Використовуються також стандартна
зупинка, якщо перевищено максимальну задану кількість ітерацій maxitn,
та аварійна зупинка, яка сигналізує про те, що або функція ( )f x не є обмеже-
ною знизу, або початковий крок 0h занадто малий, і його треба збільшити.
Код Octave-функції ralgb5a наведений у [3]. Якщо ітераційний процес
запускається зі стартової точки 0x , то параметри ( )r -алгоритму
рекомендується вибирати наступними: [2,4] , 1 1.0q (для негладких функ-
цій), 1 0.8 0.95q (для гладких функцій), *
0 0h x x – оцінка відстані від
стартової точки 0x до точки мінімуму *x . Як правило, використовуються такі
параметри зупинки: 610x
, 1210g
, maxitn 20 .n Тут параметр g
АЛГОРИТМИ РОЗВ'ЯЗАННЯ ЗАДАЧІ СЕПАРАБЕЛЬНОГО КВАДРАТИЧНОГО ПРОГРАМУВАННЯ
Компьютерная математика. 2017, № 2 143
використовується для гладких функцій, а параметр x для негладких функцій.
Якщо програма ralgb5a завершує роботу за умовою 8
1 10k k xx x
,
то цього цілком достатньо, щоб на 14 15 порядків зменшити різницю між
знайденим рекордним значенням квадратичної функції rf і її мінімальним
значенням *f .
3. Квадратична ELD-задача та обчислювальні експерименти. Нехай
енергосистема складається з N енергоблоків, які працюють паралельно. Для
кожного енергоблоку i , 1,...,i N , задані low
iP і up
iP – нижня та верхня межі йо-
го допустимого електричного навантаження. Позначимо T – тривалість плано-
вого періоду. Для кожного інтервалу t , 1,..., ,t T задано tE – планове елек-
тричне навантаження енергосистеми. Параметри iDR ( iUR ) задають допустимі
значення на послідовне зменшення (збільшення) навантаження для і-го енерго-
блоку.
Нехай ,i tx – невідоме електричне навантаження і-го енергоблоку в інтер-
валі .t Опукла квадратична ELD-задача має вигляд: знайти
* * 2
, ,
=1 =1
( ) = min ( )
T N
i i t i i t i
t i
f f x c x d x e (15)
при обмеженнях
,
=1
= , = 1, , ,
N
i t t
i
x E t T (16)
, , 1 , 2, , , 1, , ,i t i t ix x UR t T i N (17)
, 1 , , 2, , , 1, , ,i t i t ix x DR t T i N (18)
, , = 1, , , = 1, , ,low up
i i t iP x P i N t T (19)
де цільова функція (15) мінімізує витрати умовного палива, ic , id , ie – задані
параметри, такі що 0ic та 0id для 1, ,i N . Для розв’язання опуклих
квадратичних ELD-задач можна використовувати r -алгоритм [6].
З урахуванням заданої точності щодо виконання плану навантажень
енергоблоків задачу (15) – (19) можна звести до наступної задачі сепарабельного
квадратичного програмування: знайти
* * 2
, ,
=1 =1
( ) = min ( ) ( )
T N
i i t i i t i
t i
f f x f x c x d x e
(20)
при обмеженнях
,
=1
, = 1, , ,
N
t i t t
i
E x E t T (21)
, , 1 , 1, , , 2, , ,i i t i t iDR x x UR i N t T (22)
, , = 1, , , = 1, , ,low up
i i t iP x P i N t T (23)
П.І. СТЕЦЮК, О.В. ФЕСЮК, В.А. СИДОРУК
144 Компьютерная математика. 2017, № 2
де – достатньо мала величина, з точністю до якої потрібно виконати планове
навантаження енергосистеми у кожному інтервалі планового періоду.
Для розв'язання задачі (20) – (23) розроблено програмне забезпечення, яке
реалізує послідовний та паралельний алгоритми, де для мінімізації функцій
( )PF x та ( )P x (теореми 1 та 2) використовується octave-програма ralgb5a.
Алгоритми реалізовано на мові Octave з використанням бібліотеки OpenBLAS та
на мові С++ з використанням технології Nvidia CUDA (гібридний алгоритм).
Програмне забезпечення використовує вхідні файли для керування параметрами
задачі (20) – (23), для вибору параметрів ( )r -алгоритму з адаптивним кроком,
для визначення даних про енергоблоки та графік завантаження енергосистеми.
За допомогою розробленого програмного забезпечення проведено тестові
розрахунки для квадратичних ELD-задач завантаження енергоблоків. Для експе-
риментів були вибрані три графіки з різними за складністю навантаженнями
енергоблоків теплових електростанцій ОЕС України за інформацією з [7, 8].
Найлегшим до виконання є перший графік, який відповідає фактичному наван-
таженню 24 енергоблоків ТЕС, яке мало місце 6 червня 2017 року. Для другого
тесту вибрано графік середньої важкості, який відповідає фактичному наванта-
женню за 19 жовтня 2016 року, до якого залучено 33 енергоблоки. Найважчим
до виконання є третій графік, до якого залучено 40 енергоблоків. Він наведений
в табл. 1 та відповідає фактичному навантаженню теплових електростанцій ОЕС
України за 30 січня 2017 року.
ТАБЛИЦЯ 1. Фактичне навантаження ТЕС ОЕС України за 30 січня 2017 року
Година 1 2 3 4 5 6 7 8 9 10 11 12
Навантаження 7155 6696 6953 7158 6918 6868 8056 8747 9162 9585 9628 9655
Година 13 14 15 16 17 18 19 20 21 22 23 24
Навантаження 9720 9841 9945 10009 10065 10082 10033 10037 10042 10002 8980 8743
Експерименти з послідовним алгоритмом проводилися на персональному
комп’ютері з процесором Intel® Xeon® CPU E5-1607 / 3.00GHz×4, операційною
системою Ubuntu 14.04 LTS та за допомогою GNU Octave версії 4.2.1 з викорис-
танням бібліотеки OpenBLAS. В табл. 2 наведено результати обчислень для ко-
жного графіку навантаження з 20 та 40 хвилинними інтервалами. Тут N – кіль-
кість енергоблоків, T – кількість згенерованих періодів у проміжку від 7 години
ранку до 24 години вечора, відповідно до фактичного графіка навантаження, ко-
ли енергоблоки не вимикались, N T – кількість змінних задачі. У стовпчику
time вказано час у секундах, який затрачено на пошук оптимального розв’язку.
Для покриття графіків навантаження вибирались енергоблоки, які працюва-
ли у відповідні дні. Верхня межа навантаження та використання умовного пали-
ва ( fuel ) взяті з [7, 8], нижня межа допустимого навантаження енергоблоків
визначалася згідно [9]. Коефіцієнт ie визначався діленням величини fuel на 3;
id дорівнює ie поділеному на iavr – середнє значення навантаження енергоблоку i ;
ic дорівнює відповідно i id avr . Параметр DR відповідає плановій допустимій
АЛГОРИТМИ РОЗВ'ЯЗАННЯ ЗАДАЧІ СЕПАРАБЕЛЬНОГО КВАДРАТИЧНОГО ПРОГРАМУВАННЯ
Компьютерная математика. 2017, № 2 145
зміні навантаження на хвилину [10], яку помножено на 20 або 40, UR – непла-
новій допустимій зміні, яка помножена відповідно на 20 або 40.
ТАБЛИЦЯ 2. Результати обчислювальних експериментів
Розмірність задачіГрафік
завантаження N T N T (sec)
time
24 24 576 9,2508 липня 2017 24 29 696 16,64
33 24 792 19,619 жовтня 2016 33 49 1617 103,5
40 24 960 28,5430 січня 2017 40 50 2000 153,48
Обчислювальні експерименти із застосуванням гібридного алгоритму [11]
на основі технології NVidia CUDA показали пришвидшення часу розв’язання
задач у 8 – 10 раз. Це дозволяє розв’язувати вказані квадратичні ELD-задачі
завантаження енергоблоків в оперативному режимі (до 30 секунд) за допомогою
сучасного персонального комп’ютера.
Висновки. В роботі наведено математичну модель задачі сепарабельного
квадратичного програмування та описано методи її розв’язання за допомогою
алгоритмів негладкої оптимізації. Описано алгоритмічне та програмне забезпе-
чення на основі модифікації r-алгоритму та наведено результати обчислюваль-
них експериментів для квадратичних ELD-задач з різними (за складністю)
режимами навантажень енергоблоків теплових електростанцій ОЕС України.
Аналіз результатів проведених експериментів показує, що програмне забезпе-
чення можна використовувати для оперативного планування навантаження
енергоблоків теплових електростанцій ОЕС України.
1. Стецюк П.І., Лиховид О.П., Фесюк О.В. NLP-програми для ELD-задач завантаження
енергосистеми. Компьютерная математика. 2016. № 2. С. 142 – 150.
2. Шор Н.З. Методы минимизации недифференцируемых функций и их приложения. К.:
Наук. думка, 1979. 200 с.
3. Стецюк П.И., Фишер А. r-Алгоритмы Шора и octave-функция ralgb5a. Тези Міжнародної
наукової конференції «Сучасна інформатика: проблеми, досягнення та перспективи ро-
звитку», присвяченої 60-річчю заснування Інституту кібернетики імені В.М. Глушкова
НАН України (м. Київ, 13 – 15 грудня 2017 р.). К.: Ін-т кібернетики імені В.М. Глушкова
НАН України, 2017. С. 143 – 146.
4. Стецюк П.И. Теория и программные реализации r-алгоритмов Шора. Кибернетика и сис-
темный анализ. 2017. № 5. С. 43 – 57.
5. Стецюк П.И. Методы эллипсоидов и r-алгоритмы. Кишинэу. Эврика, 2014. 488 с.
6. Стецюк П.І., Фесюк О.В. Використання r-алгоритму для розв'язання квадратичної
ELD-задачі. Математичне та комп'ютерне моделювання. Серія: фізико-математичні
науки. 2017. № 15. С. 225 – 231.
7. ДП «Енергоринок» [Електронний ресурс]: http://www.er.gov.ua/.
П.І. СТЕЦЮК, О.В. ФЕСЮК, В.А. СИДОРУК
146 Компьютерная математика. 2017, № 2
8. ДП НЕК «Укренерго» [Електронний ресурс]:
http://www.ukrenergo.energy.gov.ua/Pages/main.aspx.
9. Яндульський О.С., Стелюк А.О., Лукаш М.П. Автоматичне регулювання частоти та пе-
ретокiв потужностi в енергосистемах: навч. посiб. / пiд загальною редакцiєю
д.т.н. О.С. Яндульського. Київ: НТУ України «КПI», 2010. 88 с.
10. РД 34.25.504 (НР 34-70-113-86). Нормы предельно допустимых скоростей изменения
нагрузки при работе энергоблоков 160–800 МВт в регулировочном диапазоне.
11. Стецюк П.І., Хіміч О.М., Сидорук В.А. Реалізація r-алгоритму на графічних процесорах.
Компьютерная математика. 2016. № 2. С. 100 – 109.
Одержано 30.11.2017
П.И. Стецюк, А.В. Фесюк, В.А. Сидорук
АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧИ СЕПАРАБЕЛЬНОГО КВАДРАТИЧНОГО
ПРОГРАММИРОВАНИЯ
Рассмотрена математическая модель задачи сепарабельного квадратичного программи-
рования и методы решения задачи с помощью алгоритмов негладкой оптимизации. Описаны
программные реализации методов на основе модификации r-алгоритма. Приведены
результаты вычислительных экспериментов для решения квадратичных задач нахождения
электрических нагрузок энергоблоков тепловых электростанций ОЭС Украины.
P.I. Stetsyuk, O.V. Fesiuk, V.A. Sidoruk
ALGORITHMS FOR SOLVING A SEPARABLE QUADRATIC PROGRAMMING PROBLEM
A mathematical model of the problem of separable quadratic programming and the methods for
solving the problem using nonsmooth optimization algorithms are given. Software implementations
of the methods based on modification of r-algorithm are described. Computational experiment
results for the quadratic problems of finding the electrical loads for power units of thermal power
plants of the Ukrainian IPS are presented.
Про авторів:
Стецюк Петро Іванович,
доктор фізико-математичних наук, завідувач відділу
Інституту кібернетики імені В.М. Глушкова НАН України,
Е-mail: stetsyukp@gmail.com
Фесюк Олександр Володимирович,
провідний інженер-програміст
Інституту кібернетики імені В.М. Глушкова НАН України,
Е-mail: sasha.fesyuk@gmail.com
Сидорук Володимир Антонович,
кандидат фізико-математичних наук, науковий співробітник
Інституту кібернетики імені В.М. Глушкова НАН України.
Е-mail: wolodymyr.sydoruk@gmail.com
|
| id | nasplib_isofts_kiev_ua-123456789-168465 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 2616-938Х |
| language | Ukrainian |
| last_indexed | 2025-11-24T15:05:08Z |
| publishDate | 2017 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Стецюк, П.І. Фесюк, О.В. Сидорук, В.А. 2020-05-02T19:15:18Z 2020-05-02T19:15:18Z 2017 Алгоритми розв'язання задачі сепарабельного квадратичного програмування / П.І. Стецюк, О.В. Фесюк, В.А. Сидорук // Компьютерная математика. — 2017. — № 2. — С. 137-146. — Бібліогр.: 11 назв. — укр. 2616-938Х https://nasplib.isofts.kiev.ua/handle/123456789/168465 519.85 Розглянуто математичну модель задачі сепарабельного квадратичного програмування та методи розв'язання задачі за допомогою алгоритмів негладкої оптимізації. Описано програмні реалізації методів на основі модифікації r-алгоритму. Наведено результати обчислювальних експериментів з розв'язування квадратичних задач знаходження електричних навантажень енергоблоків теплових електростанцій ОЕС України. Рассмотрена математическая модель задачи сепарабельного квадратичного программирования и методы решения задачи с помощью алгоритмов негладкой оптимизации. Описаны программные реализации методов на основе модификации r-алгоритма. Приведены результаты вычислительных экспериментов для решения квадратичных задач нахождения электрических нагрузок энергоблоков тепловых электростанций ОЭС Украины. A mathematical model of the problem of separable quadratic programming and the methods for solving the problem using nonsmooth optimization algorithms are given. Software implementations of the methods based on modification of r-algorithm are described. Computational experiment results for the quadratic problems of finding the electrical loads for power units of thermal power plants of the Ukrainian IPS are presented. uk Інститут кібернетики ім. В.М. Глушкова НАН України Компьютерная математика Теория и методы оптимизации Алгоритми розв'язання задачі сепарабельного квадратичного програмування Алгоритмы решения задачи сепарабельного квадратичного программирования Algorithms for solving a separable quadratic programming problem Article published earlier |
| spellingShingle | Алгоритми розв'язання задачі сепарабельного квадратичного програмування Стецюк, П.І. Фесюк, О.В. Сидорук, В.А. Теория и методы оптимизации |
| title | Алгоритми розв'язання задачі сепарабельного квадратичного програмування |
| title_alt | Алгоритмы решения задачи сепарабельного квадратичного программирования Algorithms for solving a separable quadratic programming problem |
| title_full | Алгоритми розв'язання задачі сепарабельного квадратичного програмування |
| title_fullStr | Алгоритми розв'язання задачі сепарабельного квадратичного програмування |
| title_full_unstemmed | Алгоритми розв'язання задачі сепарабельного квадратичного програмування |
| title_short | Алгоритми розв'язання задачі сепарабельного квадратичного програмування |
| title_sort | алгоритми розв'язання задачі сепарабельного квадратичного програмування |
| topic | Теория и методы оптимизации |
| topic_facet | Теория и методы оптимизации |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/168465 |
| work_keys_str_mv | AT stecûkpí algoritmirozvâzannâzadačíseparabelʹnogokvadratičnogoprogramuvannâ AT fesûkov algoritmirozvâzannâzadačíseparabelʹnogokvadratičnogoprogramuvannâ AT sidorukva algoritmirozvâzannâzadačíseparabelʹnogokvadratičnogoprogramuvannâ AT stecûkpí algoritmyrešeniâzadačiseparabelʹnogokvadratičnogoprogrammirovaniâ AT fesûkov algoritmyrešeniâzadačiseparabelʹnogokvadratičnogoprogrammirovaniâ AT sidorukva algoritmyrešeniâzadačiseparabelʹnogokvadratičnogoprogrammirovaniâ AT stecûkpí algorithmsforsolvingaseparablequadraticprogrammingproblem AT fesûkov algorithmsforsolvingaseparablequadraticprogrammingproblem AT sidorukva algorithmsforsolvingaseparablequadraticprogrammingproblem |