МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

4. НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

Рассмотрим несколько примеров экономических задач, приводящих к задаче нелинейного программирования (ЗНЛП).

1. Минимизация издержек производства. Пусть необходимые затраты для производства х единиц продукта А выражаются следующим образом:

К(х) = ахк,      X > 0,   а > О,   К > 1.

Здесь общие издержки начиная с некоторого Xq увеличиваются быстрее, чем количество произведенных единиц продукта А (прогрессия издержек). Очевидно, что это экономически нежелательная ситуация.

Если издержки производства продукта А определены формулой

К(х) = ахк,      X > 0,   а > 0,   0 < К < 1,

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

Наконец, в редко встречающемся случае регрессии издержек справедливо соотношение

К(х) = а — Ьхк,      X > 0, а,Ь,К>0.

Если в общем случае затраты на производство Xj единиц продукта Aj (j = 1,2,..., п) на некотором предприятии заданы в виде

п

К(х1,х2,---,хп) = ^2üj,      Xj>0,   j = l,2,...,n,

i=i

60

где a,j, Kj > 0, а продукты Aj должны быть произведены в количестве не менее bj (j = 1,2,... ,п) и удовлетворять условию на

п

ассортимент ^ djXj > d, где dj,d > О, то минимизация издержек 3=1

на предприятии означает, что требуется найти минимум нелинейной

п

функции К(х) на множестве G = {{х\, х2,..., хп) : ^djXj > d,

3=1

Xj > bj, j = 1,2,...,те}.

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

fit /у ГУ*       1  ґу*       ^ r-y*--*-tb

if IXtti       tljty     ... .(j ,jj ,

где a,a\,a2,... ,an — известные числовые параметры, которые определяются на основе статистических данных. Пусть затраты, связанные с использованием единицы каждого j-ro фактора, равны Cj (j = 1,2,... ,п). Требуется добиться максимально возможного объема выпуска продукции у при условии, что общая стоимость факторов не превышает с.

Математическая модель задачи имеет такой вид: найти такие значения переменных Xi,x2,... ,хп, чтобы при Xj > 0 (количество факп

торов не может быть отрицательным) и ^ с,ж, < с (ограничения на

г=1

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

maxaxf1 х22 ... ж"".

В наиболее общем виде эти и подобные задачи можно сформулировать в терминах ЗНЛП, а именно: найти максимальное или минимальное значение функции /(ж) на заданном множестве М решений ж = (х\,х2,... ,хп). Для простоты изложения предположим, что множество М определяется конечной системой равенств и неравенств, хотя могут быть и другие способы задания этого множества.

Итак, рассмотрим следующую задачу: пусть заданы функции переменных /(ж), ірі(х), і = 1,2,... ,т, 'tpj{x), j = 1,2,... ,р, зависящие от многих переменных, т. е. ж = (х\, х2,..., хп). Найти

min /(ж)

61

при ограничениях

ipi(x) < О,

і = 1,2,..., m;

j = 1,2,...,p.

Если все функции /, tpi, ipj линейные, то соответствующая задача является ЗЛП. Если хотя бы одна из перечисленных функций нелинейная, то соответствующая задача является ЗНЛП.

В частности, в приведенных примерах нелинейными являются целевые функции К(х) и у = f(x\,X2,... ,хп); ограничения-неравенства в обоих случаях линейны; ограничения-равенства отсутствуют.

Существует несколько сравнительно простых ЗНЛП.

1. Классические задачи оптимизации. Эти задачи состоят в нахождении минимума (максимума) функции /(ж), ж = (х\,Х2,... ...,хп) при ограничениях-равенствах сгДж) = 0, і = 1,2,... ,т; т < п. Случай т = 0 соответствует задаче без ограничений. Существенным для этих задач является требование гладкости (наличие у функций / и §і непрерывных частных производных по меньшей мере до второго порядка включительно).

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

2. Задачи с нелинейной целевой функцией /(ж) и линейными ограничениями

3. Задачи квадратичного программирования. В этих задачах целевая функция представляет собой квадратичную функцию

п

г = 1,2,... ,т.

3=1

п п п

/И = £

С3Х3 +Y,Y,dkiXkXi

3=1 k=l 3=1

а ограничения имеют линейный вид:

п

г = 1,2,... ,т.

3=1

62

4. Задачи выпуклого программирования. В этих задачах целевая функция /(ж) и функции ограничений д%(х), і = 1,2,... ,т представляют собой выпуклые (вогнутые) функции.

5. Задачи с сепарабельной целевой функцией

/(ж) = /i(an) + /2Ы + •• • + /„(*„)

и аналогичными функциями ограничений <7і(ж).

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

Геометрическая интерпретация задачи нелинейного программирования

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

Определение. Множество точек ж = (х\, х%, ■ ■ ■ ,хп) составляет линию уровня функции /(ж), если они удовлетворяют соотношению /(ж) = const. Причем различным константам соответствуют различные линии уровня.

Например, для линейной функции /(ж) = ах± + Ъх% линиями уровня будут параллельные прямые ах\ + bx2 = const, где const определяет сдвиг относительно начала координат. Для квадратичной функции /(ж) = х\ + х\ линии уровня суть концентрические окружности различных радиусов г = «/ronst с центром в начале координат. Для функции /(ж) = (х\ —а)2 + (ж2 ^Ь)2) очевидно, линиями уровня будут также концентрические окружности, но с центром в точке (а, Ь), а если рассматривать функцию /(ж) = с(х\ — a)2 + d(x2 — Ь)2, где с > О, d > 0, то для нее линиями уровня будут концентрические эллипсы также с центром в точке (а, Ь).

63

Пример 1. Пусть ж = (xi,X2) Є Е2 и область допустимых решений D задается ограничениями

Х\ + Х2 < 6, Х\ — 2X2 > —8, Xl — Х2   <   1,        Х\ > О,     Х2 > 0.

Найти max/(ж) = 0,5хі + 2ж2-Оптимальным решением этой задачи будет

ж* = (4/3; 14/3);   /(ж*) = 10. Ту же задачу можно решить графически.

Пример 2. Найти минимум функции

/(ж) = 10(жі 3, 5)2 + 20(х2 4)2

при ограничениях, заданных в предыдущем примере.

Рассматриваемая задача представляет собой ЗНЛП с нелинейной (квадратичной) функцией цели и линейными ограничениями. Решение этой задачи, как видно из рисунка, сводится к отысканию х\, х% и z* = f(x\,x%), удовлетворяющих системе уравнений

х\ + х% = 6, /(ж*) = z* = W(xt 3,5)2 + 20(х*2 4)2, X* -4 = 0,5(х1 -3,5).

Эта система получена из очевидных с геометрической точки зрения фактов: оптимальное решение представляет собой точку (х\; xl), лежащую на прямой Х\ + Х2 = 6 и линии уровня /(ж*) = z*;

64

в точке (xj; xl) прямая Х\ + Х2 = 6 касается линии уровня /(ж*) = z*

откуда

dX2

dx\ dz/дхі dz/dx2

20(жі 3,5 Щх2 4) x\=x\: Х2=х2

Решая приведенную выше систему уравнений, получаем ж* =

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

Классический метод оптимизации нелинейных задач с помощью множителей Лагранжа

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

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

(2, 5; 3,5); г* = 15.

65

Напомним, что для функции f(x) стационарными являются точки, в которых ее производная равна нулю, т. е. f'(x) = 0. Для функции многих переменных /(ж) = /(жі,ж2, ■ ■ ■ ,хп) первой производной будет вектор, составленный из частных производных по всем переменным:

(dßx) df(x) df(x) X дх±

v/H

о      і ' ' ' і о ОХ2 ох„

Этот вектор называется градиентом функции. Чтобы определить, являются ли стационарные точки точками экстремума, необходимо исследовать в них вторую производную. Для функции /(ж) = = f(xi,X2, • • •,хп) это будет матрица Гессе вида

Я д2/(ж)

dxidxj 1,2,.

Индексы і, j указывают место элементов в матрице (і — номер строки; j — номер столбца). Так как производная не зависит от порядка дифференцирования, то, очевидно, матрица Н — является симметричной, т. е. выполняется равенство

d2f(x) = d2f(x) dxidxj     dxjdxi'

Определители, стоящие на главной диагонали матрицы Н, обоAi = I/

11

А2 /11

/21 /12 /22

/11

/12 •

fin

/21

/22 '

fin

fnl

/п2 '

fnn

d2f(x) dxidxj

вторые частные производные функции

K^l; ,ь2 5 ' ' ' 5 ,ьп)'

Здесь /у

f(xi, Х2, ■ ■ ■ ,хп), вычисленные в точке ж

Если определители имеют один знак (а именно положительные), то ж0 — точка относительного (локального) минимума. Если же Ai, А2,..., Дп поочередно меняют знак начиная с минуса (Ai < 0, А2 > 0, A3 < 0 и т. д.), то ж0 — точка относительного максимума. До тех пор, пока исследования проводятся в отдельных точках, речь идет именно о локальных (местных) экстремумах. Проанализировав всю допустимую область решений, можно выделить среди локальных экстремумов наибольший и наименьший, которые будут называться глобальными.

66

Пример 3. Пусть /(ж) = f(xi,X2) = Южі + 20ж2 + Жі*2 ^2ж| — 2х\ определена на всем пространстве Вґ. Для вычисления относительного экстремума этой функции имеем два уравнения

дх\ 10 + Х2 — 4жі = 0, 8X2 20 + X! 4ж2 = 0,

решив которые, найдем х\ = 4, ж§ = 6.

Матрица Гессе для этой функции имеет вид

Я

-4

1

 

1

-4

и

А,    -К 0, Д2

^4 1 1 -4 15 > 0.

Следовательно, точка ж0 = (4; 6) является точкой относительного максимума. Поскольку /(ж) в области определения других стационарных точек не имеет, то ж0 является также точкой глобального максимума.

Для задачи с ограничениями классический метод поиска условного экстремума состоит в следующем.

1. Находят множество Si (ж) всех стационарных точек /(ж) внутри допустимого множества D, которые исследуют на минимум (максимум) и определяют среди них наименьший (наибольший).

2. Исследуют точки границы ^(ж) и находят те из них, где функция /(ж) достигает минимума (максимума). Для этого выбирают произвольную границу, например <?і(ж) = 0. Если это уравнение можно решить относительно компонент точки ж = (х\, Х2, ■ ■ ■, хп), то подставив их в выражение для целевой функции, приходят к безусловной задаче оптимизации, т. е. к задаче без ограничений. Такой прямолинейный подход требует значительных вычислительных затрат и применим лишь в простейших случаях, а именно: при небольшом количестве ограничений <7,(ж) = 0, і = = 1,2, ...,т, причем таких, что каждое уравнение <?, (ж) = 0 легко может быть разрешено относительно всех переменных Х\,Х2, ■ ■ ■ ,хп, т. е. можно получить явные функции вида

Фк(Х1, ■ ■ ■ ,Хк-!,Хк+1, . . . ,Хп),

1,2,.

В частности, это возможно, если функции <7,(ж) линейны. В других ситуациях для вычисления точек экстремума функции /(ж) на границе допустимого множества применяются более эффективные методы.

67

Метод Лагранжа используется для решения ЗНЛП следующего вида: найти

/(ж) —¥ min (4.1) мо ограниченном множестве

D = {x: gi(x) = О, г = 1,2,... , тег}. (4.2)

Если функции /(ж), <7г(ж) непрерывно дифференцируемы, то для задачи (4.1)-(4.2) строится функция Лагранжа

т

Цх, Л) = /(ж) + £ Хг9г(х).

г=1

Пусть в некоторой точке ж0 = (х\,х%,... ,хап) существует вектор Л° = (Aj, Х2, • • •, А^) такой, что выполняется необходимое условие экстремума функции Ь(х, А) вида

дЦх°,\°)

= 0,      7 = 1,2,те:

dxj

дЬ(х°,Х°) дХі

0,      і = 1,2,... ,тег,

тогда ж0 является решением задачи (4.1) с ограничениями (4.2).

Пример 4. Имеется два способа производства некоторого продукта. Пусть х\, х2 — количества, произведенные соответствующим способом. Издержки производства зависят от произведенных количеств Х\ и х2 следующим образом:

-Ні(жі) = «о+ ai*i+ «г*2, ао)«і)«2 > 0; Н2(х2) = bQ+ Ьі*2+ Ь2х\,      bQ,bi,b2 > 0.

За некоторый промежуток времени необходимо произвести с единиц продукции (т. е. с = *i + х2), распределив ее для двух способов так, чтобы минимизировались общие издержки.

В терминах общей постановки задача имеет такой вид: найти

/(ж) = Hi(x\) + Н2(х2) —¥ min

68

при условии

Ql (ж) = С — Жі — Ж2 = 0.

При этом функция Лагранжа приобретает вид L(xi, ж2, А) = ао + а\Х\ + а2ж2 + bo + Ьіж2 + Ь2ж| + А(с — х\ — ж2), откуда

дЬ

—— = а\ + 2ü2Xi — А = 0, дх\

дЬ

-— = Ъ\ + 2Ь2ж2 — А = 0,

ОХ2

—— = С — Х\ — Х2 = 0.

ОХ

Решив эту систему, находим количества

п        b2 bi — ai о       а2 bi ai

X_                                                                            /і ......I..... _                                                                             ■                                  '>* _ f ............ 1                             1             I      _ ,                 1     \ 1 1

a2 + b2      2(a2 + b2) "    (i2 + b2      2(a2 + b2)

Элементы выпуклого анализа

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

Определение 1. Множество X называется выпуклым, если любые две его точки можно соединить отрезком, который полностью принадлежит этому множеству или, что то же самое, для любых его точек ж1, ж2 и произвольного числа А: 0 < А < 1 точка у = Аж1 + (1 — А)ж2 также принадлежит этому множеству.

Выпуклыми множествами являются, например, отрезок, луч, прямая, шар.

Определение 2. Функция /(ж), определенная на некотором выпуклом множестве X, называется выпуклой, если для любых mo

rn

чек Xі и X2 из множества X и произвольного числа Л: 0 < Л < 1 выполняется неравенство

/ (Аж1 + (1 Л)ж2) < АДж1) + (1 А)/(ж2).

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

Если функция /(ж) выпуклая, то —/(ж) — вогнутая. Если функция <?(ж) выпуклая, то множество W, заданное неравенством <?(ж) < < 0, является выпуклым. Пересечение выпуклых множеств, т. е. множество, заданное системой ограничений вида W = {ж : д%{х) < О, і = 1,2,..., т}, где все функции <7, (ж) выпуклые, является либо пустым, либо выпуклым и замкнутым множеством.

В наиболее общей постановке задача выпуклого программирования имеет такой вид: найти

min/(ж) (4.3)

при ограничениях

9i(x)<0,      »= 1,2,...,т, (4.4)

где функции /(ж) и §г(х), і = 1,2,... ,т — выпуклые функции многих переменных ж = (х\, Х2, ■ ■ ■, хп).

70

Если множество допустимых решений ЗВП (4.3), (4.4) пустое, то задача не имеет решений, а если оно неограниченное, то не существует оптимальное решение. На замкнутом ограниченном множестве задача выпуклого программирования обладает следующим очень важным свойством, которое облегчает поиск решения.

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

Приведем теорему Куна — Таккера, которую можно рассматривать как обобщение теоремы двойственности в линейном программировании, а множители Лагранжа {А,,г = 1,2,... ,т} являются допустимыми решениями двойственной ЗЛП.

Теорема Куна — Таккера. Пусть множество W= {x:gi (ж) < О, і = 1,2,... ,т} имеет внутренние точки, т. е. выполняется условие Слейтера: существует ж Є W, что gi(x) < 0 для всех i= 1,2,...,т. Тогда для того чтобы ж* было оптимальным решением задачи (4.3) (4.4), необходимо и достаточно, чтобы существовал неотрицательный т-мерный вектор А* = {А*}™1 такой, что пара (ж*, А*) является седловой точкой функции Лагранжа

т

L(x,X) = /(ж) + £а,5,(ж),      ж Є Еп,   Xi > О,

г=1

т. е. выполняются неравенства

mm т

/(ж) + £ Хі9і(х) > /(ж*) + £ Хі9і(хП > /(ж*) + £ X*gi(x*),

г=1 і=1 і=1

А, > 0,   і = 1,2,... ,т.

Наиболее общие методы решения нелинейных задач оптимизации

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

71

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

С помощью численных методов решения ЗНЛП из любой точки допустимой области можно приблизиться к некоторому локальному (а для ЗВП — глобальному) минимуму целевой функции. Поскольку эти вычисления носят циклический характер (многократно повторяющиеся однотипные действия), применять ЭВМ особенно эффективно.

Если задача математического программирования не имеет ограничений, т. е. отсутствуют условия (4.2), то поиск экстремума ведется на всем пространстве Rn (напомним, что R1 — числовая ось; R2 — плоскость и т. д.).

Удачно выбирая направление поиска, можно с достаточной точностью прийти к экстремальной точке за конечное количество шагов (итераций). В частности, для дифференцируемой целевой функции градиент указывает направление наибольшего возрастания функции, антиградиент (градиент с противоположным знаком) — направление убывания функции (градиентные методы). Если к тому же целевая функция имеет и вторые производные по всем переменным, то направление движения можно уточнить с помощью матрицы Гессе (вторых производных) (метод Ньютона). Для недифференцируе-мых функций перспективные направления выбираются среди направлений координатных осей (метод покоординатного спуска) или направлений, полученных случайным образом (метод случайного поиска). Наличие ограничений существенно усложняет методы решения нелинейных оптимизационных задач. Для того чтобы вычислительные процедуры не выходили за пределы допустимой области, необходимо решить вспомогательные задачи. Например, если направление градиента (антиградиента) является недопустимым (выходит за пределы допустимой области), требуется операция проектирования градиента на допустимую область, а это достаточно сложная задача, особенно при нелинейных ограничениях (метод проекции градиента).

Если поиск ведется в некоторых возможных направлениях, не выходящих за пределы допустимой области, то для выбора наилучших среди них необходимо решить вспомогательную ЗЛП (метод возможных направлений).

72

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

Квадратичное программирование

Одним из наиболее простых и важных классов ЗНЛП являются задачи квадратичного программирования, которые заключаются в минимизации (максимизации) квадратичной функции при линейных ограничениях. В векторной форме эта задача имеет такой вид: найти

где D — симметричная матрица размерности те х те; ж — неизвестный те-мерный вектор; с, Ь — векторы соответственно теи тег-мерные; А — матрица ограничений размерности тег х те. Например, для матриц

и векторов с = (4, 2), Ь = (2,3,1), х = {х\,Х2) в координатной форме

задача будет иметь такой вид:

найти

тіп(ж2 + Ах\Х2 + 2х\ + 4ж — 1 + 2ж2) при ограничениях

mm[(Dx,x) + (с, ж)]

при ограничениях

Ах < Ь

-Х± + Х2 < 2 2хл        < 3

Xl — Х2 < 1

так как

73

(Dx,x) = (x\ + 2ж2)жі + (2жі + Зж2)ж2 = х\ + 4жіж2 + Зж|;

/ _1     і \ /-а?і+ ж2\

Лж =       2     О     і    1   І = 2а?і

V    1-і/1і2І     I x^xj

Способы решения задачи квадратичного программирования во многом определяются видом матрицы D: если D — неотрицательно определенная матрица, то это ЗВП, и любой локальный минимум этой задачи будет ее решением; если D — неположительно определенная матрица, то имеем задачу вогнутого программирования; при этом может быть большое количество неэквивалентных локальных минимумов, но глобальный минимум, если он существует, достигается в одной из вершин допустимого многогранного множества М, определенного системой ограничений Ах < Ь. Большинство известных процедур точного решения задач вогнутого программирования в той или иной степени предполагает перебор вершин множества М. Эти методы по структуре напоминают методы дискретного программирования.

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

74

 

 ...  7



Обратная связь

По любым вопросам и предложениям

Имя и фамилия*

Е-меил

Сообщение*

↑ наверх