2190

Рис. 47

Отредактированный итоговый сценарий приведен на рис. 48. При этом видно, что введение дополнительных логических условий ухудшает целевую функцию.

Рис. 48

ЛЕКЦИЯ 12 НЕЛИНЕЙНЫЕ ОПТИМИЗАЦИОННЫЕ МОДЕЛИ

Особенности задач нелинейного программирования

иметоды их решения

Вобщем виде задача нелинейной оптимизации может быть сформулирована следующим образом:

130

extr f(x);

gi (x) ( , )bi ,i 1,m;

xj 0j 1,n,

где хотя бы одна из функций f(x), gi(x) является нелинейной.

На переменные xj также могут накладываться ограничения: dj x j Dj, где dj и Dj- нижняя и верхняя границы для

каждой j-й переменной. Задача баз ограничений называется задачей безусловной оптимизации, задача с ограничениями - задачей условной оптимизации.

Для задачи безусловной оптимизации функции нескольких переменных extrf(X), гдеX (x1,...,xn ) необ-

X Rn

ходимое условие экстремума заключается в том, что в точке

оптимума X*все частные производные оптимизмруемой функции по переменным x1,…,xn должны быть равны нулю:

f (X*) 0 xj 1,n.

xj

Достаточным условием экстремума является положительная определенность в точке X* матрицы вторых производных (матрицы Гессе) функции для минимума или отрицательная определенность для максимума:

- матрица Гессе.

131

Рассмотрим частный случай задачи нелинейного программирования, предполагая, что система ограничений содержит только уравнения и отсутствуют условия неотрицательности переменных. Такая задача называется задачей на условный экстремум или классической задачей оптимизации.

extr f (x);

gi (x) bi ,i 1, m.

Решение данной задачи может быть получено с помощью метода множителей Лагранжа. Введем набор переменных

1, 2... m, называемых множителями Лагранжа и соста-

вим функцию Лагранжа:

F(x1,...,xn , 1,..., m) f (x1,...,xn )

где 1,..., m - произвольные действительные числа. Затем

рассматривается система n+m уравнений с n+m неизвестными, в которых каждая производная приравнивается нулю:

Решив систему, получим точки, в которых функция может иметь экстремум. Дальнейшее исследование найденных точек осуществляется так же, как и в случае безусловного экстремума.

Множитель Лагранжа является аналогом двойственной оценки в задаче линейного программирования и показывает, как изменится целевая функция при изменении правой части соответствующего ограничения на единицу.

132

Пример 1. По плану производства продукции предприятию необходимо изготовить 180 изделий. Эти изделия могут быть изготовлены двумя технологическими способами. При производстве x1 изделий способом I затраты равны

4x1 x12 р., а при изготовлении x2 изделий II- м способом они

составляют 8x2 x22 р. Определить, сколько изделий каж-

дым из способов необходимо изготовить, чтобы общие затраты на производство продукции были минимальными.

Математическая постановка задачи заключается в определении минимального значения функции

f 4x1 x12 8x2 x22

при условиях

x1 x2 180; x1,x2 0.

Решим задачу с использованием метода множителей Лагранжа. Найдем минимальное значение данной функции без учета требования неотрицательности переменных. Для этого составим функцию Лагранжа:

F(x1,x2, ) 4x1 x12 8x2 x22 (180 x1 x2 ),

найдем ее частные производные по x1 и x2 и приравняем их нулю. В результате получим систему уравнений

F

x1 4 2x1 0

F

180 x1 x 2

Решив систему, получим: x1 = 91, x2 = 89, = -186. Чтобы проверить, достигается ли в точке (91; 89)

условный экстремум, нужно провести дополнительные исследования и проверить знакоопределенность квадратичной формы. Это может быть произведено с помощью критерия Силь-

133

вестра. Согласно этому критерию квадратичная форма

X AX положительно определена тогда, когда все главные (угловые) миноры j матрицы A положительны:

Квадратичная форма отрицательно определена тогда и только тогда, когда 1 > 0, а далее знаки чередуются: 2 < 0, 3 > 0 и т.д. Если все j > 0 ( j < 0), но некоторые j = 0, то квадратичная форма положительно (отрицательно) полуопределена. Если ни одно из перечисленных выше условий не выполняется, квадратичная форма является неопределенной.

Найдем матрицу вторых производных функции F(X, )(производные берутся только по переменным x1 и x2):

1 = 2 > 0, 2 = 4 > 0, следовательно, найденная точка (91; 89) является точкой минимума исходной функции.

Метод множителей Лагранжа можно применять и в том случае, когда ограничения представляют собой неравенства. Так, если требуется найти экстремум функции f(X) при условии g(X) b, то сначала следует найти точки безусловного экс-

xk

среди этих точек отобрать те, координаты которых удовлетворяют уравнению связи g(X)<b и, наконец, определить точки, удовлетворяющие системе уравнений

Точки, найденные в результате решения этой системы, вместе с точками, определенными на первом этапе и удовле-

134

творяющими условию g(X)<b, подлежат дальнейшему исследованию, как и при нахождении безусловного экстремума.

Одним из наиболее распространенных приемов решения нелинейных задач с ограничениями (реализованных также и в EXCEL) является их сведение к задачам безусловной оптимизации. Для учета функциональных ограничений обычно используется метод штрафных функций. При этом решение задач с ограничениями сводится к решению последовательностей задач безусловной оптимизации. В общем виде такое преобразование задачи условной оптимизации в задачу без ограничений осуществляется при помощи введения специальным образом сконструированной функции H(X), называемой

штрафной функцией или функцией штрафа.

Пусть решается задача минимизации функции f(X) при

ограничениях gi(X) bi, i=1,m.

Для решения производится переход от целевой функции f(X) к следующей целевой функции: Ф(X)=f(X)+H(X). Существует два метода построения штрафных функций:

1) внутренних штрафных функций (барьерных функ-

ций);

2) внешних штрафных функций.

Методы внутренних штрафных функций характеризуются следующими функциями штрафа:

где - параметр штрафа, значение параметра может быть постоянным (случай 1) или меняться на различных итерациях (случай 2). В случае 2 параметр k выбирается таким образом, чтобы его значения стремились к нулю при k (k-номер итерации).

При использовании внутренних штрафных функций поиск оптимума следует начинать с внутренней точки допу-

135

стимой области, то есть с точки, в которой все ограничения выполнены как строгие неравенства. При выходе на границу допустимой области штраф будет бесконечным, следовательно, оптимизационный процесс никогда не выйдет за пределы допустимой области. Недостатком данного метода является то, что он требует существования внутренних точек дополнительной области, т.е. не позволяет решать задачи с ограничениями типа равенств. Кроме того, для их использования необходимо знать начальную допустимую точку.

В методах внешних штрафных функций функции штрафа могут иметь следующий вид:

H(x) k i (x), (H(x) ki i (x)).

Во втором случае k изменяется в процессе поиска таким образом, чтобы при приближении к оптимальной точке влияние функции штрафа постепенно ослабевало. Функции

i(x) могут иметь следующий вид:

i (x) (min{0;gi (x) bi})2;

i (x) | min{0;gi (x) bi}|.

Если ограничение не нарушается, т.е. gi(x) bi , то

i(x) 0, следовательно, H(X)=0. Если ограничение нару-

шается, то величина штрафа зависит от степени нарушения ограничения.

Таким образом, задачи с ограничениями с помощью аппарата штрафных функций могут быть сведены к задачам безусловной оптимизации. Алгоритмы безусловной оптимизации составляют инвариантную часть алгоритмического обеспечения, предназначенного для решения оптимизационных задач. При этом учет ограничений осуществляется на внешнем уровне и не затрагивает инвариантное алгоритмическое ядро.

136

Алгоритмы безусловной оптимизации представляют собой итерационные процедуры, реализующие последовательное приближение к искомому экстремуму:

X K 1 X K K SK ,

где k - номер итерации, Sk - направление движения на k-й итерации, k - величина шага в этом направлении. При этом

Xk (x1k ,...,xkn ),Sk (s1k ,...,skn )

Процесс поиска начинается с некоторой начальной точки X0, которая называется начальным приближением и задается пользователем. Получаемая в процессе поиска последовательность

точек X0,X1...Xk называется траекторией поиска и должна сходиться к оптимальной точке X*. Таким образом, алгоритмы безусловной оптимизации различаются по способам выбора

направления поиска Sk и величины шага, причем способ выбора направления поиска является определяющим.

В зависимости от способа выбора направления поиска методы безусловной оптимизации делятся на методы 0, 1 и 2- го порядка.

Методы 0-го порядка - методы, в которых для определения направления поиска используются только значения целевой функции. Производные в данном случае не вычисляются. Этот класс алгоритмов называется еще методами прямого поиска или поисковыми методами оптимизации. К ним отно-

сятся методы переменного многогранника и различные алгоритмы покоординатной оптимизации и случайного поиска. Особенностью методов поисковой оптимизации является то, что они могут быть использованы при алгоритмическом задании критериев оптимальности и ограниченности.

Методы первого порядка - методы, в которых для определения направления поиска используются первые производные целевой функции по управляемым параметрам. Эти методы называют также градиентными. В качестве направления поиска на каждой итерации в них выбирается градиент (в за-

137

дачах максимизации) или антиградиент (в задачах минимизации) оптимизируемой функции. Обобщенная стратегия методов градиентного спуска может быть представлена следующим образом:

X k 1 X k k f (X*) (минимизация); X k 1 X k k f (X*) (максимизация).

Методы второго порядка - это методы, в которых для определения направления поиска используются 2-е производные целевой функции. К этому классу относят метод Ньютона и его модификации. Основная стратегия данных методов заключается в следующем:

[ 2 f (X k )] - матрица вторых производных целевой функции f(X) в точке Xk.

Среди всех методов безусловной оптимизации метод Ньютона обладает самой высокой скоростью сходимости, однако он является самым трудоемким, так как требует вычисления матрицы 2-х производных на каждом шаге.

При работе различных алгоритмов поиска необходимо задать точность для останова алгоритма. В качестве критерия останова в EXCEL используется условие: fk fзад, где

дачи.

138

ЛЕКЦИЯ 13 РЕШЕНИЕ ЗАДАЧ НЕЛИНЕЙНОГО

ПРОГРАММИРОВАНИЯ СРЕДСТВАМИ EXCEL

Решение непрерывных задач нелинейного программирования

Решение задачи нелинейного программирования рассмотри на следующем примере. Пусть требуется определить размеры бака, имеющего форму параллелепипеда заданного объема:

h

b

a

Объем бака

V=abh.

Полная поверхность

S=2(ab)+2(a+b)h=2(ab+(a+b)h).

Принимаем, что стоимость материала

C=ks,

где k-стоимость единицы площади материала. В результате получим

C=2k(ab+(a+b)h).

После введения рассмотренных величин сформулируем задачу оптимизации следующим образом:

139