APPROXIMATE METHOD OF OPTIMIZATION OF NONLINEAR PROGRAMMING PROBLEMS

Abstract


Currently, the problem of choosing the optimal solution is one of the most important and urgent problems in industry, economy, agriculture and the military sphere. Methods and approaches of the theory of nonlinear programming are used to solve many applied optimization problems. The main difficulty of nonlinear optimization is the lack of a universal method for solving this class of problems. To solve this problem, special methods are being developed for solving particular nonlinear programming problems, for example, for positive or limited initial data The paper investigates the problem of analytical optimization of nonlinear programming problems. The purpose of this work is to develop a new approximate method for solving optimization problems of a nonlinear function under nonlinear constraints in the form of equalities. To do this, an approximation (expansion in a series) of the objective function and constraints is performed. All variables are considered bounded at the top and bottom. The objective function and constraints are considered infinitely differentiable by the set of arguments, and all their derivatives are assumed to be limited in absolute value by a given number. In this article, the theorem on the conditional maximum of the objective function under given constraints is proved. the results of which are the justification of the developed method. Since the developed optimization method is approximate, the error of the proposed representation of the objective function and constraint functions is estimated. In problems of an applied nature, the boundaries of variable changes are often set approximately and they can be adjusted. In addition, it is possible to adjust the point relative to which the functions are decomposed into series. Therefore, the article analyzes the sensitivity of the optimal solution of the problem when changing the decomposition point into a series of functions for different values of the coordinates of the left boundaries when searching for the maximum of the objective function. To explain the operation of the method, a specific numerical example is analyzed in detail. Modeling in the MS Excel environment was used to solve it. Graphs of the sensitivity study of the solution of the problem when changing the initial data are constructed. Nonlinear programming models are used, for example, to solve the following practically important issues: minimizing costs in the sale of products, optimizing consumer choice, maximizing production volume, determining the rational behavior of an individual in a given situation, rational use of resources, forming an optimal portfolio of securities.

Full Text

Введение Для задач нелинейного программирования (НП), в отличие от задач линейного программирования, нет единого метода решения, аналогичного симплекс-методу [1]. Поэтому для каждого класса задач НП применяются свои методы решения. Многие из этих методов изложены в фундаментальных трудах по НП [2; 3]. На основе анализа научных публикаций можно выделить следующие направления исследований в данной области: • аналитические методы оптимизации, использующие модифицированную функцию Лагранжа [4] и теорему Куна - Таккера [5; 6]; • численные итерационные методы [7; 8]; • приближенные алгоритмы на основе алгоритмов аппроксимации задач НП [9; 10], в том числе линейной [11; 12]; • приближенная робастная формулировка задачи, использующая линеаризацию множества неопределенностей [13]. Одним из направлений решения задач оптимизации является наложение ограничений на условия задачи. Например, в статье [14] разработан метод решения с нелинейной и дифференцируемой целевой функцией, линейными ограничениями (интервалами возможных значений аргументов - переменных) и условием нормировки аргументов. В работе [15] предложен метод максимизации линейной функции при одном линейном ограничении с положительными коэффициентами, в статье [16] поиск квазиоптимального решения производится с помощью анализа координат проекций на гиперплоскости (алгоритм проектирования), поиск оптимального решения осуществляется путем задания приращений ограничениям (алгоритм приращений). Целью данной работы является разработка приближенного метода решения задач НП путем аппроксимаций (разложения в ряды) целевой функции и ограничений. 1. Материалы и методы Рассматриваемая задача формулируется следующим образом. Требуется найти переменные , удовлетворяющие системе уравнений (1) и сообщающие абсолютный максимум (минимум) целевой функции (2) При этом все переменные удовлетворяют ограничениям Рассмотрим случай максимизации. При минимизации у функции (2) ставится знак «-». Исходя из оценок для , можно оценить , подставив в каждое неравенство (1) вместо сначала левую, а потом правую границу. Тогда общая правая граница для будет рассматриваться как минимальная из полученной правой и данной при . Будем рассматривать функции и L бесконечно дифференцируемыми по совокупности аргументов, т.е. разлагающимися в ряды в окрестности некоторой точки , содержащей многогранник . Тогда , где , (3) Отсюда следует, что область дифференцируемости функций должна содержать многогранник . (4) Координаты точки A определим позднее, но будем считать, что , . Введем обозначение: , здесь . Пусть , . Отсюда находим: (5) Аналогичное представление получается для функций . Во избежание громоздкости выписывать его не будем. Это аналог формулы (5), но вместо L стоит , вместо коэффициентов «c» будут стоять соответствующие коэффициенты «b», связанные с производными функций : . Пусть все функции L и , а также все их производные ограничены по абсолютной величине числом M. Для оценки числа M вычисляются все производные функций L, до m-го порядка включительно и оцениваются с избытком, исходя из того, что . Покажем, как оценивается погрешность , аналогично будут оцениваться погрешности функций . Сначала на основе оценок для переменных находим соответствующие оценки для переменных «y». Например, , и т.д. (6) Согласно формуле Стирлинга, . (7) С учетом этого формулу (3) запишем в виде: . (8) Здесь - максимальное значение производной при , …, в точке, удовлетворяющей условию (4). Пусть и (например, ,), и . Тогда правая часть (8) не превосходит . (9) Предположим, что , где - сколь угодно малое положительное число, т.е. . (10) При выполнении этого условия погрешность будет сколь угодно малой. Затем система (1) представляется в виде системы (11) Здесь , , s равно количеству слагаемых во множестве B без множества . Поэтому проверка выполнения условия (10) начинается при m = 3. Если оно не выполняется, то полагаем m = m + 1 и т.д. Итак, с точностью функция (2) может быть представлена суммой (5). Аналогичные представления имеют функции (1). А именно: , (12) , - значение функции в точке . При этом выполняются ограничения (6). Не нарушая общности, рассмотрим случай, когда . Приведем левые части уравнений системы (12) к диагональному виду (11) с коэффициентом 1 при переменных в левой части. Тогда . (13) Если , то в (13) часть переменных у каждого уравнения уходят из правой части в левую. Определим, как это сделано в [15], с учетом того, что и для коэффициентов в правой части (11) на основе (6) значения переменных следующим образом: (14) ; (15) здесь . Аналогично (16) и т. д. Наконец (17) . Теорема Условный максимум функции L при выполнении условий (6), (10), (13), (14), (15), (16), (17) с точностью будет равен (18) Доказательство. Обозначим через правую часть (17). Допустим, что в точке функция L принимает максимальное значение, равное . Тогда можно представить в виде, где правая часть отличается от правой части только тем, что вместо стоит , вместо стоит и т.д. Найдем разность . Имеем: Из (14)-(17) следует, что слагаемые в (18) неотрицательны. Отсюда следует, что . Кроме того, выполняется условие (6). Теорема доказана. Если условие (6) не будет выполнено, то возможна, исходя из практической реализации, корректировка ограничений на переменные или координат точки A. Это будет показано на конкретном примере. 2. Результаты и их обсуждение Рассмотрим конкретный пример. Максимизируется функция (19) при ограничениях (20) Имеем: Считаем: Пусть m = 3, тогда ; Оценим . Имеем Отсюда . Проверка выполнения условия (10) при m = 3 и . Можно показать, что данное неравенство выполняется при . Пусть . Тогда с точностью т.е. Составим систему и приведем ее к диагональному виду: Определим согласно (15) ( ). т.к. т.к. . Тогда Отсюда . Данные значения и выходят за рамки ограничений на и и не удовлетворяют системе (1). Надо улучшить этот результат. Можно использовать следующий подход. В задачах прикладного характера часто границы изменения переменных задаются приближенно, и их можно корректировать. Кроме того, можно корректировать и точку, относительно которой функции разлагаются в ряды. Поскольку в рассматриваемом примере в формировании значений и участвуют нижние границы изменения переменных (верхние не участвуют), а также координаты точки разложения, то корректировке подлежат эти значения. Пусть, для примера, нижняя граница для будет 0,34. Тогда . В этом случае найденные значения удовлетворяют системе ограничений и второму уравнению системы (1). При этом не выполняется первое уравнение системы (1). С привлечением средства MS Excel «Поиск решения» получены результаты . Погрешность не превосходит 0,8 %. Левая часть первого уравнения системы (1) при и равна 5,8894, а должна быть 6. Погрешность в этом случае составляет 1,8 %. Вывод: результат получился достаточно точный. Рассмотрим на графике (рис. 1) изменение результата при разных значениях левых границ и (например, изменяется от 0,3 до 0,6; изменяется от 0,1 до 0,3 при ). Рис. 1. Изменение x1 при разных значениях левых границ Рис. 2. Изменение x2 при разных значениях левых границ Другой вариант. При данных границах и изменяются и с соблюдением условия . Тогда где . На рис 3, 4 построены графики зависимости и от значений координат и точки разложения в ряд функций при изменении от 0,8 до 1,3, - от 0,2 до 0,3 при ; . Рис. 3. Изменение x2 при разных значениях координат a1 и a2 левых границ Рис. 4. Изменение x1 при разных значениях координат a1 и a2 левых границ Замечание. Если коэффициенты разложения функций имеют более сложную, чем полиномиальная зависимость от и , то они разлагаются в ряд с заданной степенью точности. Заключение В статье разработан новый метод приближенного решения оптимизационной задачи нелинейного программирования. Для пояснения вычислительного алгоритма разобран конкретный пример.

About the authors

A. V Ganicheva

Tver State Agricultural Academy

A. V Ganichev

Tver State Technical University

References

  1. Ганичев А.В., Ганичева А.В. Математическое программирование. - Тверь: ТвГТУ, 2017. - 88 с.
  2. Jensen P.A., Bard J.F. Nonlinear Programming Methods. S1 Separable Programming. - Wiley, 2002. - 700 p.
  3. Luenberger D.G., Ye. Y. Linear and nonlinear programming. - Basel: Springer International Publishing, 2016. - 546 p.
  4. Salman A.M., Al-Jilawi A. S. Solving nonlinear optimization problem using approximation methods // International Journal of Health Sciences. - 2022. - Vol. 6(S3). - P. 1578-1586. - doi: 10.53730/ijhs.v6nS3.5699.
  5. Данданян А.Н., Хайдарова Л.А., Курганова М.В. Решение задач нелинейного программирования по условиям Куна-Таккера // Наука XXI века: актуальные направления развития. - 2020. - № 1-2. - С. 24-27.
  6. Тимофеев А.Г., Лебединская О.Г. Поиск быстрого решения задачи нелинейного программирования // Транспортное дело России. - 2019. - № 2. - С. 48-51. - EDN: TMQJRU
  7. Таныгина, В.В. Решение задачи нелинейного программирования методом Франка - Вулфа // Научному прогрессу - творчество молодых. - 2019. - № 1. - С. 81-84. - EDN: TSVJEY.
  8. Mai T., Mortari D. Theory of functional connections applied to quadratic and nonlinear programming under equality constraints // Journal of Computational and Applied Mathematics. - 2022. - Vol. 406. - Art. 113912. - doi: 10.1016/j.cam.2021.113912.
  9. Wang J. Approximate nonlinear programming algorithms for solving stochastic programs with recourse // Annals of Operations Research. - 1991. - Vol. 31. - P. 371-384. - doi: 10.1007/BF02204858
  10. Antczak T. An h-approximation method in nonlinear vector optimization // Nonlinear Analysis: Theory, Methods & Applications - 2005. - Vol. 63, iss. 2. - P. 225-236. - doi: 10.1016/j.na.2005.05.008.
  11. Still C., Westerlund T. A linear programming-based optimization algorithm for solving nonlinear programming problems // European Journal of Operational Research. - 2010. - Vol. 200, iss. 3. - P. 658-670. - doi: 10.1016/j.ejor.2009.01.033.
  12. Approximation Algorithms for Optimization of Combinatorial Dynamical Systems / I. Yang, S.A. Burden, R. Rajagopal, S.S. Sastry, C.J. Tomlin // IEEE Transactions on Automatic Control. - 2016. - Vol. 61, no. 9. - P. 2644-2649. - doi: 10.1109/TAC.2015.2504867.
  13. Diehl M., Bock H.G., Kostina E.A. An approximation technique for robust nonlinear optimization // Mathematical Programming. - 2006. - Vol. 107, iss. 1-2. - P. 213-230. - doi: 10.1007/s10107-005-0685-1.
  14. Djukic R.R. Partial stability of multi attribute decision-making solutions for interval determined criteria weights - the problem of nonlinear programming // Military Technical Courier. - 2020. - Vol. 68, iss. 3. - P. 488-529. - doi: 10.5937/vojtehg68-27014
  15. Ганичева А.В. Метод решения некоторых классов оптимизационных задач // Моделирование, оптимизация и информационные технологии. - 2019. - Т. 7, № 2 (25). - С. 43-54. - doi: 10.26102/2310-6018/2019.25.2.002. - EDN: KVLRNG
  16. Ганичева А.В., Ганичев А.В. Метод проектирования и приращений решения задач линейного программирования // Моделирование, оптимизация и информационные технологии. - 2022. - Т. 10, № 3. - С. 1-16. - doi: 10.26102/2310-6018/2022.38.3.022. - EDN: TQAVJW

Statistics

Views

Abstract - 99

PDF (Russian) - 92

Refbacks

  • There are currently no refbacks.

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies