DOI: 10.17586/2226-1494-2015-15-2-322-328


УДК519.85

МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ДОПОЛНИТЕЛЬНЫМИ ОГРАНИЧЕНИЯМИ НА ПЕРЕМЕННЫЕ ОПРЕДЕЛЕННОГО ТИПА

Урбан А. Р.


Читать статью полностью 
Язык статьи - Русский

Ссылка для цитирования: Урбан А.Р. Методы решения задачи линейного программирования с дополнительными ограничениями на переменные определенного типа // Научно-технический вестник информационных технологий, механики и оптики. 2015. Том 15. № 2. С. 322–328.

Аннотация

Представлено описание решения задачи, связанной с учетом специфических допустимых множеств на переменные в задачах линейного программирования. В работе речь идет о допустимом множестве, представляющем собой для некоторой переменной объединение отрезков с множительным параметром. Решение указанной задачи производится в два этапа: сначала решается релаксированная задача линейной оптимизации (без учета дополнительных ограничений на переменные), а затем на основании полученного решения строится вспомогательная задача нелинейной оптимизации. Решение указанной вспомогательной задачи основывается на специализированном методе нелинейной оптимизации – методе Бокса. Результатом является предложенный автором алгоритм для решения задачи линейного программирования с дополнительными ограничениями на переменные с указанием оценок точности. Решение указанной задачи имеет высокую практическую значимость. Такого рода ограничения на переменные в задачах линейного программирования возникают достаточно часто для производственных задач. Применение метода показано на примере задачи нахождения оптимального плана раскроев в бумагоделательной промышленности, при решении которой возникает задача округления количества накатов съема тамбура бумагоделательных машин в условиях найденного оптимального плана раскроев.


Ключевые слова: линейное программирование, нелинейная оптимизация, метод Бокса.

Список литературы
1. Урбан А.Р., Кузнецов В.А. Математические модели и методы учета сроков продукции в задаче раскроя тамбуров бумагоделательных машин // Ученые записки ПетрГУ. Серия: естественные и технические науки. 2014. № 4 (141). С. 112–115.
2. Кузнецов В.А. Задачи раскроя в целлюлозно-бумажной промышленности. СПб.: Изд-во СПбЛТА, 2000. 132 с.
3. Воронов Р.В. Математические модели и методы автоматизированных систем планирования производства бумаги: автореф. дисс. … канд. техн. наук. Петрозаводск, 2004. 22 с.
4. Westerlund T., Harjunkoski I., Isaksson J. Solving a production optimization problem in a paper-converting mill with MILP // Computers and Chemical Engineering. 1998. V. 22. N 4–5. P. 563–570.
5. Voronin A.V., Kuznetsov V.A., Arkhipov I.V., Shabaev A.I. Software system for sawmill operation planning // Proc. 12th Conference of FRUCT Association. St. Petersburg, Russia, 2012. P. 165–171.
6. Shabaev A.I., Arhipov I.V., Spirichev M.V., Urban A.R., Torozerov M.A. Development of planning system for plywood production using matrix designer // Proc. 14th Conference of FRUCT Association. St. Petersburg, Russia, 2014. P. 140–147.
7. Vasenin V.A., Vodomerov A.N. A formal model of a system for automated program parallelization // Programming and Computer Software. 2007. V. 33. N 4. P. 181–194. doi: 10.1134/S0361768807040019
8. Ilyushin A.I., Olenin M.A., Vasil'ev S.A. Solution of parallel computation problem based on «Space-Time» concept // Programming and Computer Software. 2012. V. 38. N 4. P. 189–200. doi: 10.1134/S0361768812040020
9. Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы. М.: Мир, 1982. 584 с.
 
10. Афанасьева А.С., Буздалов М.В. Выбор функции приспособленности особей генетического алгоритма с помощью обучения с подкреплением // Научно-технический вестник информационных технологий, механики и оптики. 2012. № 1 (77). С. 77–81.
11. Еремеев А.В. Генетический алгоритм с турнирной селекцией как метод локального поиска // Дискретный анализ и исследование операций. 2012. Т. 19. № 2. С. 41–53.
12. Shtovba S.D. Ant algorithms: theory and applications // Programming and Computer Software. 2005. V. 31. N 4. P. 167–178. doi: 10.1007/s11086-005-0029-1
13. Khapaev M.M., Tsygankov A.A. An algorithm for the constrained extremum problem // Computational Mathematics and Modeling. 1997. V. 8. N 4. P. 322–325.
14. Трифонов А.Г. Постановка задачи оптимизации и численные методы ее решения [Электронный ресурс]. Режим доступа: http://matlab.exponenta.ru/optimiz/book_2/index.php, свободный. Яз. рус. (дата обращения 25.01.2015)
15. Медынский М.М., Антоний Е.В. Численные методы нелинейной оптимизации: алгоритмы и программы. Учебное пособие. М.: МАИ, 2003. 192 с.
16. Городецкий С.Ю., Гришагин В.А. Нелинейное программирование и многоэкстремальная оптимизация. Нижний Новгород: Изд-во ННГУ, 2007. 489 с.
17. Kapitonova A.P., Smelyanskii R.L., Terekhov I.V. A support system for estimating computational complexity in programs // Computational Mathematics and Modeling. 1994. V. 5. N 4. P. 279–287. doi: 10.1007/BF01130310
18. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦМНО, 2000. 960 с.
19. Гасс С. Линейное программирование: методы и приложения. М.: Физматгиз, 1961. 304 с.
Информация 2001-2017 ©
Научно-технический вестник информационных технологий, механики и оптики.
Все права защищены.

Яндекс.Метрика