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

Statistics

Views

Abstract - 153

PDF (Russian) - 138

Refbacks

• There are currently no refbacks.