DOI: https://doi.org/10.20535/SRIT.2308-8893.2016.3.07

Розв’язання нелінійних оптимізаційних задач розподілу ресурсів у великих блочно-структурованих системах зі зв’язуючими параметрами

Olena E. Kirik

Анотація


Розв’язання нелінійних оптимізаційних задач блочної структури зі зв’язуючими параметрами (змінними) реалізується шляхом комбінації апроксимаційного та декомпозиційного підходів. Апроксимаційний метод обрано таким чином, щоб декомпозицію задачі математичного програмування можна виконувати без будь-яких припущень щодо опуклості або адитивної сепарабельності функцій критерію та обмежень. Координуюча та блочні підзадачі, що є допоміжними в апроксимаційному методі, розв’язуються за скінченну кількість кроків. У ході обчислень зв’язуючі параметри змінюються від кроку до кроку ітераційного процесу, забезпечуючи монотонне зменшення значення цільової функції координуючої задачі, тобто кількість загальних ресурсів змінюється таким чином, аби блочні підсистеми працювали дедалі ефективніше з точки зору ефективності роботи всієї системи.

Ключові слова


задачі розподілу ресурсів;оптимізаційні моделі;апроксимуючі методи;нелінійне програмування;алгоритми декомпозиції

Повний текст:

PDF

Посилання


Lesdon L.C. Optimizatsija bol'shih sistem / L.C. Lesdon. — M.: Nauka, 1975. — 432 s.

Tsurkov V.I. Dekompozitsija v zadachah bol'shoj razmernosti / V.I. Tsurkov. — M.: Nauka, 1981. — 352 s.

Laptin Ju.P. Nekotorye voprosy reshenija blochnyh nelinejnyh zadach optimizatsii so svjazyvajuschimi peremennymi / Ju.P. Laptin, N.G. Zhurbenko // Kibernetika i sistemnyj analiz. — 2006. — № 2. — S. 47–55.

Shefi R. Rate of Convergence Analysis of Decomposition Methods Based on the Proximal Method of Multipliers for Convex Minimization / R. Shefi, M. Teboulle // SIAM J. Optim. — 014. — 24, Issue 1. — P. 269–297. DOI: 10.1137/1309.10774.

Andersson H. A new decomposition algorithm for a liquefied natural gas inventory routing problem / H. Andersson, M. Christiansen, G. Desaulniers // International Journal of Production Research. — 2016. — 54, Issue 2. — P. 564–578. DOI: 10.1080/00207543.2015.1037024

Laptin Ju.P. Tochnye shtrafnye funktsii i vypuklye prodolzhenija funktsij v shemah dekompozitsii po peremennym / Ju.P. Laptin // Kibernetika i sistemnyj analiz. — 2016. — 52, № 1. — S. 93–104.

Kirik O.Ye. Pidkhid do rozv’jazannja nelinijnykh optymizatsijnykh zadach blochnoyi struktury zi zv’jazujuchymy obmezhennjamy / O.Ye. Kirik // Naukovi visti NTUU "KPI". — K., 2015. — № 5. — S. 32–38.

Kirik O.Ye. Alhorytmy linearyzatsiyi ta sprjazhenykh hradiyentiv dlja nelinijnykh zadach rozpodilu potokiv / O.Ye. Kirik // Naukovi visti NTUU "KPI". — K., 2007. — № 3. — S. 67–73.

Pshenichnyj B.N. Chislennye metody v ekstremal'nyh zadachah / B.N. Pshenichnyj, Ju.M. Danilin. — M.: Nauka, 1975. — 319 s.

Aleksandrova V.M. Optymizatsijni modeli ta alhorytmy dlja merezhevykh zadach rozpodilu resursiv / V.M. Aleksandrova, O.Ye. Kirik // Naukovi visti NTUU "KPI". — 2014. — № 4. — S. 39–45.

Pshenichnyj V.N. Vypuklyj analiz i ekstremal'nye zadachi / V.N. Pshenichnyj. — M.: Nauka, 1980. — 320 s.

Faddeev D.K. Vychislitel'nye metody linejnoj algebry / D.K. Faddeev, V.N. Faddeeva. — M.: Fizmatgiz, 1960. — 656 s.


Пристатейна бібліографія ГОСТ


1. Лэсдон Л.C. Оптимизация больших систем / Л.C. Лэсдон. — М.: Наука, 1975. — 432 с.

2. Цурков В.И. Декомпозиция в задачах большой размерности / В.И. Цурков. — М.: Наука, 1981. — 352 с.

3. Лаптин Ю.П. Некоторые вопросы решения блочных нелинейных задач оптимизации со связывающими переменными / Ю.П. Лаптин, Н.Г. Журбенко // Кибернетика и системный анализ. — 2006. — № 2. — C. 47–55.

4. Shefi R. Rate of Convergence Analysis of Decomposition Methods Based on the Proximal Method of Multipliers for Convex Minimization / R. Shefi, M. Teboulle // SIAM J. Optim. — 014. — 24, Issue 1. — P. 269–297. DOI: 10.1137/1309.10774.

5. Andersson H. A new decomposition algorithm for a liquefied natural gas inventory routing problem / H. Andersson, M. Christiansen, G. Desaulniers // International Journal of Production Research. — 2016. — 54, Issue 2. — P. 564–578. DOI: 10.1080/00207543.2015.1037024

6. Лаптин Ю.П. Точные штрафные функции и выпуклые продолжения функций в схемах декомпозиции по переменным / Ю.П. Лаптин // Кибернетика и системный анализ. — 2016. — 52, № 1. — C. 93–104.

7. Кірік О.Є. Підхід до розв’язання нелінійних оптимізаційних задач блочної структури зі зв’язуючими обмеженнями / О.Є. Кірік // Наукові вісті НТУУ «КПІ». — К., 2015. — № 5. — С. 32–38.

8. Кірік О.Є. Алгоритми лінеаризації та спряжених градієнтів для нелінійних задач розподілу потоків / О.Є. Кірік // Наукові вісті НТУУ «КПІ». — К., 2007. — № 3. — С. 67–73.

9. Пшеничный Б.Н. Численные методы в экстремальных задачах / Б.Н. Пшеничный, Ю.М. Данилин. — М.: Наука, 1975. — 319 с.

10. Александрова В.М. Оптимізаційні моделі та алгоритми для мережевих задач розподілу ресурсів / В.М. Александрова, О.Є. Кірік // Наукові вісті НТУУ «КПІ». — 2014. — № 4. — C. 39–45.

11. Пшеничный В.Н. Выпуклый анализ и экстремальные задачи / В.Н. Пшеничный. — М.: Наука, 1980. — 320 с.

12. Фаддеев Д.К. Вычислительные методы линейной алгебры / Д.К. Фаддеев, В.Н. Фаддеева. — М.: Физматгиз, 1960. — 656 с.