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

К оглавлению 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
17

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

f(x1, x2, ..., xn) (Б.1)

при условии, что переменные удовлетворяют соотношениям:

ì gi(x1, x2, ..., xn) £ bi, (i = 1, 2, ..., k)

í (Б.2)

î gi(x1, x2, ..., xn) £ bi, (i = k+1, ..., n)

где f и gi некоторые известные функции, bi - заданные числа.

Решение этой задачи X* = (x1*, x2*, ..., xn*), удовлетворяющее (Б.1) и (Б.2), такое, что для любого другого X = (x1, x2, ..., xn), удовлетворяющего (Б.2), имеем:

f(x1*, x2*, ..., xn*) ³ f(x1, x2, ..., xn) - для задачи максимизации;

f(x1*, x2*, ..., xn*) £ f(x1, x2, ..., xn) - для задачи минимизации.

Соотношения (Б.2) называются системой ограничений. Условия неотрицательности переменных могут быть заданы непосредственно. В евклидовом пространстве En (Б.2) определяет область допустимых решений поставленной задачи (в отличии от задач линейного программирования эта область может быть не выпуклой).

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

f(x1, x2, ..., xn) = h.

Эта точка может быть как на границе, так и внутри области.

Процесс решения задачи в геометрической интерпретации включает этапы:

Определение области допустимых решений соответствующих (Б.2) (если она пуста, то решений задачи - нет);

Построение гиперповерхности f(x1, x2, ..., xn) = h;

Определение гиперповерхности наивысшего (наинизшего) уровня или устанавливают неразрешимость задачи из-за неограниченности (Б.1) сверху (снизу) на множестве допустимых решений;

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

Рассмотрим следующую задачу. Найти максимальное значение функции:

F = x2 - x12 + 6x1,

при условиях

ì 2x1 + 3x2 £ 24

ï x1 + 2x2 £ 15

í 3x1 + 2x2 £ 24

ï x2 £ 4

î x1, x2 ³ 0

Строим область допустимых решений и линии уровня:

12 3x1 + 2x2 = 24

F = 13

Линии уровня: F = x2 - x12 + 6x1 = h

F = 10

8 Область допустимых решений: ðOABC

F = 9

D B

A x2 = 4

x1 + 2x2 = 15

O C x1

0 3 8 12 15

2x1 + 3x2 = 24

При каждом значении h получаем параболу, которая расположена тем выше, чем больше h. Максимум F в области допустимых решений достигается в точке D - единственной общей точке линии уровня при h = 13 и ðOABC. Координаты ее находятся из системы уравнений:

ì x2 - x12 + 6x1 = 13,

î x2 = 4.

Решение ее будет: x1* = 3, x2* = 4, а Fmax = 13. Следует заметить, что точка D не является вершиной.

Метод множителей Лагранжа.

Общая постановка задачи состоит в нахождении максимума (минимума) функции:

f(x1, x2, ..., xn)

при условии:

g(x1, x2, ...,xn) = bi , i = 1, 2, ..., m.

Условия неотрицательности xj могут отсутствовать. Имеем задачу на условный экстремум - классическая задача оптимизации.

Задача решается следующим образом. Вводится набор переменных li (i = 1, 2, ..., m) - множителей Лагранжа и составляется функция:

F(x1, x2, ..., xn, l1, l2, ..., lm) = f(x1, x2, ..., xn) + å li[bi - gi(x1, x2, ..., xn)]

i=1

Далее определяют частные производные:

¶F/¶xj (j = 1, 2, ..., n) и ¶F/¶li , (i = 1, 2, ..., m).

На следующем шаге рассматривается система n + m уравнений:

ì ¶F/¶xj = ¶f/¶xj - å li¶gi/¶xj = 0, j = 1, 2, ..., n,

í i=1

î ¶F/¶li = bi - gi(x1, x2, ..., xn) = 0, i = 1, 2, ..., m.

Любое решение этой системы определяет точку X = (x10, x20, ..., xn0), в которой может иметь место экстремум функции f(x1, x2, ..., xn). Таким образом, разрешив построенную систему определяют все точки, в которых функция f может иметь экстремум. Далее исследование идет как в случае безусловного экстремума.

Итак, этапы решения задачи нелинейного программирования методом множителей Лагранжа заключаются в следующем:

1. Составляют функцию Лагранжа.

2. Находят частные производные функции Лагранжа по xj и li и приравнивают их 0.

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

4. Среди точек, подозрительных на экстремум, находят точки, в которых достигается экстремум, и вычисляют значения f(x1, x2, ..., xn) в этих точках и среди них выбирают те, которые удовлетворяют условиям задачи.

Рассмотрим следующую задачу. По плану фабрике необходимо изготовить 180 изделий. Изделия могут быть изготовлены двумя способами. При производстве x1 изделий I-ым способом затраты равны 4x1 + x12 тыс. руб., а при изготовлении x2 изделий II-ым способом затраты составят 8x2 + x22 тыс. руб. Определить, сколько изделий каждым из способов следует изготовить, так чтобы общие затраты на производство продукции были минимальными.

Р е ш е н и е. Необходимо определить минимум функции:

f = 4x1 + x12 + 8x2 + x22,

при условиях:

x1 + x2 = 180, x1, x2 ³ 0.

Строим функцию Лагранжа:

F(x1, x2, l) = 4x1 + x12 + 8x2 + x22 + l(180 - x1 - x2).

Дифференцируя F, получаем систему:

ì ¶F/¶x1 = 4 + 2x1 - l =0,

í ¶F/¶x2 = 8 + 2x2 - l = 0,

î ¶F/¶l = 180 - x1 - x2.

Отсюда:

ì x1 - x2 = 2,

î x1 + x2 = 180, или x1* = 91, x2* = 89 и C = fmin(x1*, x2*) = 17278 тыс. руб.

Выпуклое программирование.

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

f(x1, x2, ...,xn)

при условиях:

gi(x1, x2, ..., xn) £ bi (i = 1, 2, ..., m), xj ³ 0 (j = 1, 2, ..., n).

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

Несколько определений.

Функция f(x1, x2, ..., xn) на выпуклом множестве X называется выпуклой, если для любых двух точек X2 и X1 из X и любого 0 £ l £ 1, выполнено соотношение:

f[lX2 + (1 - l)X1] ³ lf(X2) + (1 - l)f(X1).

Множество допустимых решений удовлетворяет условию регулярности, если существует хотя бы одна точка Xi этой области такая, что gk(Xi) < bk (k = 1, 2, ..., m).

Задача выпуклого программирования возникает, если функция f является вогнутой (выпуклой), а gi - выпуклы.

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

F(x1, x2, ..., xn, l10, l20, ..., lm0) £ F(x10, x20, ..., xn0, l10, l20, ..., lm0) £

£ F(x10, x20, ..., xn0, l1, l2, ..., lm),

для всех xj ³ 0 и li ³ 0.

Для задачи выпуклого программирования, множество допустимых решений которой обладает свойством регулярности, точка Xo = (x10, x20, ..., xn0) является оптимальным решением тогда, когда существует такой вектор L0= (l10, l20, ..., lm0), что точка (X0, L0) является седловой точкой функции Лагранжа, построенной для исходной задачи.

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

¶F0/¶xj £ 0, xj0¶F0/¶xj = 0, xj0 ³ 0,

¶F0/¶li ³ 0, li0¶F0/¶li = 0, li0 ³ 0.

(частные производные берется в седловой точке).

Для задачи нахождения минимума седловая точка определяется соотношениями:

F(x10, x20, ..., xn0, l1, l2, ..., lm) £ F(x10, x20, ..., xn0, l10, l20, ..., lm0) £

£ F(x1, x2, ..., xn, l10, l20, ..., lm0).

Условия седловой точки в этой задаче представляются в виде:

¶F0/¶xj ³ 0, xj0¶F0/¶xj = 0, xj0 ³ 0,

¶F0/¶li £ 0, li0¶F0/¶li = 0, li0 ³ 0.

Градиентные методы.

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

Суть метода заключается в том, что начиная от некоторой точки X(k) осуществляется последовательный переход к другим точкам до тех пор пока не получим приемлемое решение исходной задачи. Методы можно разделить на две группы.

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

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

Нахождение решения идет итерационным процессом до тех пор пока градиент функции f(x1, x2, ..., xn) в очередной точке X(k+1) не станет равным 0 или пока ½f(X(k+1)) - f(X(k))½ < e, где e достаточно малое положительное число, эту величину часто называют точностью полученного решения.

Метод Франка-Вулфа. Найти максимум вогнутой функции:

f(x1, x2, ..., xn),

при условии:

åaijxj £ bi, (i = 1, 2, ..., m) xj ³ 0, j = 1, 2, ..., n.

j=1

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

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

Ñf(X(k)) = (¶f(X(k))/¶x1, ..., ¶f(X(k))/¶xn)

и строят линейную функцию:

F = ¶f(X(k))/¶x1×x1 + ... + ¶f(X(k))/¶xn×xn.

Находят максимум функции F при сформулированных ограничениям. Пусть решение этой задачи Z(k). Тогда за новое допустимое решение принимают:

X(k+1) = X(k) + lk(Z(k) - X(k)),

где lk некоторое число, называемое шагом вычислений (0 £ lk £ 1). Число lk - произвольное и выбирают его так, чтобы значение функции в точке X(k+1) , зависящее от lk, было максимальным. Для этого находится решение уравнения df/dlk = 0 и выбрать его наименьший корень. Если корни уравнения больше 1, то берется lk = 1. Затем определяется X(k+1) и f(X(k+1)) и выясняют необходимость перехода к точке X(k+2). Если такая необходимость имеется, то вычисляется в точке X(k+1) градиент целевой функции и переходят к соответствующей задаче линейного программирования и решают ее. Определяют координаты точки X(k+2) и определяется необходимость дальнейших вычислений. После конечного числа шагов получают с необходимой точностью решение исходной задачи.

Итак, этапы решения задачи методом Франка-Вулфа заключаются в следующем:

Определяют одно из допустимых решений.

Находят градиент функции f в точке допустимого решения.

Строят функцию F и находят ее максимальное значение при условиях исходной задачи.

Определяют шаг вычислений.

По формуле X(k+1) = X(k) + lk(Z(k) - X(k)) находят следующее допустимое решение.

Проверяют необходимость перехода к следующему допустимому решению. В случае необходимости переходят к этапу 2), если такой необходимости нет, то найдено приемлемое решение.

Рассмотрим следующую задачу. Найти максимум функции:

f = 2x1 + 4x2 + x12 + 2x22

при условии:

ì x1 + 2x2 £ 8,

î 2x1 - x2 £ 12, x1, x2 ³ 0.

Р е ш е н и е. Находим градиент функции f:

Ñf = (¶f/¶x1, ¶f/¶x2) = (2 - 2x1; 4 - 4x2).

Исходное допустимое решение X(0) = (0, 0), а в качестве критерия оценки качества (точности) берем:

|f(X(k+1)) - f(X(k))| £ 0.01.

Первая итерация. В точке X(0) Ñf(X(0) ) = (2, 4). Находим максимум функции:

F1 = 2x1 + 4x2,

при условиях исходной задачи. Эта задача имеет решение Z(0) = (0, 4).

Новое допустимое решение ищем в виде:

X(1) = X(0) + l1(Z(0) - X(0) ), 0 £ l1 £ 1.

Подставив сюда X(0) и Z(0) имеем:

ì x1(1) = 0 + l10,

î x2(1) = 0 + l14.

Подставив их в f имеем:

f(l1) = 16l1 - 32l12.

Находим производную этой функции и приравниваем ее 0, имеем:

f¢(l1) = 16 - 64l1 = 0, l1 = 1/4.

Итак:

X(1) = (0, 1), f(X(1)) = 2, но f(X(1)) - f(X(0)) = 2.

Вторая итерация. Имеем:

Ñf(X(1) ) = (2, 0).

Ищем максимум функции:

F2 = x1,

при условии исходной задачи. Решение этой задачи будет:

Z(1) = (6.4, 0.8).

Определяем далее:

X(2) = X(1) + l2(Z(1) - X(1)).

Подставив сюда Z(1), получим:

ì x1(2) = 6.4l2,

î x2(2) =1 + 0.2l2.

f(l2) = 2 + 12.8l2 - 41.04l22.

f¢(l2) = 12.8 - 82.08l2 = 0, l2 » 0.16.

x1(2) » 1.02, x2(2) » 0.94, f(X(2)) » 2.9978.

f(X(2)) - f(X(1)) = 0.9978 > 0.01.

Проводя аналогичные вычисления для третьей итерации, получим:

f(X(3)) » 2.99991,

f(X(3)) - f(X(2)) = 0.00211 < 0.01,

X(3) » (1.0098, 1.0003).

Максимум же достигается в точке X* = (1, 1).

Метод штрафных функций.

Пусть имеем вогнутую функцию f(x1, x2, ..., xn), необходимо найти максимум этой функции при условиях:

gi(x1, x2, ..., xn) £ bi , (i = 1, 2, ...,m), xj ³ 0,

где gi - выпуклые функции.

Строится функция:

F(x1, x2, ..., xn) = f(x1, x2, ..., xn) + H(x1, x2, ..., xn),

где функция H(x1, x2, ..., xn) определяется системой ограничений и называется штрафной функцией. Она может быть построена многими способами. Чаще всего эта функция строится в виде:

H(x1, x2, ..., xn) = å ai(x1, x2, ..., xn) qi(x1, x2, ..., xn),

i=1 где

ì 0, если bi - gi ³ 0,

ai = í ai - весовые коэффициенты

î ai, если bi - gi < 0,

qi = bi - gi

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

xj(k+1) = max{0; xj(k) + l[¶f(X(k) )/¶xj + å ai¶qi(X(k) )/¶xj]} (Б.3)

i=1

Из (Б.3) следует, что если предыдущая точка находится в области допустимых решений, то второе слагаемое в квадратных скобках равно 0 и переход к последующей точке определяется только градиентом целевой функции. Если же предыдущая точка не принадлежит области допустимых решений, то за счет указанного слагаемого на последующих итерациях достигается возвращение в область допустимых решений. При этом, чем меньше ai, тем быстрее находится приемлемое решение, но точность определения решения снижается. Поэтому в начале ai берут малым, постепенно увеличивая.

Итак, процесс решения включает этапы:

Определяют исходное допустимое решение.

Выбирают шаг вычислений.

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

По (Б.3) определяют координаты точки - возможное новое решение.

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

Устанавливаются значения весовых коэффициентов и переходят к этапу 4.

Рассмотрим следующую задачу. Найти максимум функции:

f = -x12 - x22,

при условиях:

(x1 - 7)2 + (x2 - 7)2 £ 18, x1, x2 ³ 0.

Р е ш е н и е. Целевая функция является вогнутой (это отрицательно определенная квадратичная форма). Область допустимых решений - выпукла. Строится область допустимых решений и уровни целевой функции. Ниже приводится графическая интерпретация этого процесса.

X(1) X(0)

X(2)

X(3) X(4)

X(5)

Полагаем X(0) = (6, 7). Берем l =0.1. Пусть g(x1, x2) = 18 - (x1 - 7)2 - (x2 - 7)2, определяем частные производные:

¶f/¶x1 = -2x1; ¶g/¶x1 = -2x1 + 14; ¶f/¶x2 = -2x2; ¶g/¶x2 = -2x2 + 14.

Используем (Б.3) и строим последовательность точек, одна из которых определяет приемлемое решение.

Итерация 1. Точка X(0) =(6, 7) находится в области допустимых решений, следовательно выражение в квадратных скобках в (Б.3) равно 0, т.е. координаты следующей точки X(1) можно вычислить по формулам:

x1 = max {0; x1(0) + l ¶f(X(0))/¶x1} = max{0; 6 + 0.1(-2)× 6} = 4.8,

x2 = max {0; x2(0) + l ¶f(X(0))/¶x2} = max{0; 7 + 0.1(-2) ×7} = 5.6.

Проверяем, входит ли точка с координатами (x1(1), x2(1)) в область допустимых решений. Находим

g(X(1)) = 18 - 4.84 - 1.96 = 11.2 > 0.

Следовательно, точка X(1) принадлежит области допустимых решений и в этой точке f(X(1)) = -54.4.

Проведя еще две подобных итерации, получим то, что точка X(3) выйдет за пределы области допустимых решений. Рассмотрим следующую итерацию.

Итерация 4. В соответствии с (Б.3) решение представляем в виде:

x1(4) = max {0; x1(3) + l[¶f(X(3))/¶x1 + a¶g(X(3))/¶x1]} =

= max(0; 3.072 + 0.1[(-2) ×3.072 + a((-2)3.072 + 14)]} = max{0; 2.4576 + a0.7856},

x2(4) = max {0; x2(3) + l[¶f(X(3))/¶x2 + a¶g(X(3))/¶x2]} =

= max(0; 3.584 + 0.1[(-2) ×3.584 + a((-2)3.584 + 14)]} = max{0; 2.8672 + a0.6832}.

Выбираем a такое, чтобы точка X(4) оказалась как можно ближе к границе области допустимых решений и принадлежала бы этой области. Берем a = 1.9 и вычисляем:

x1(4) = max {0; 2.4576 + 1.9 ×0.7856} » 3.950,

x2(4) = max {0; 2.8672 + 1.9 ×0.6832} » 4.165,

g(X(4)) = 18 - 9.3025 - 8.037225 » 0.660, f(X(4)) = - 32.950.

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

Итерация 12.

x1(12) = max{0; 3.203 + 0.1[(-2)3.203 + 1.9((-2)3.203 + 14)]} » 4.005,

x2(12) = max{0; 3.205 + 0.1[(-2)3.205 + 1.9((-2)3.205 + 14)]} » 4.008,

g(X(12))= 18 - 8.970025 - 8.952064 » 0.078; f(X(12)) = - 32.104.

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

f(X(12)) - f(X(11)) = -32.104 - (-32.116) = 0.012 < 0.1,

т.е. найденное на двенадцатом шаге итерации решение является приемлемым.

Такой же вывод можно сделать, если исследовать поведение вектор-градиентов функций f(X) и g(X) в точке X(12):

Ñf(X(12)) = (-8.01, -8.016), Ñg(X(12)) = (5.99, 5.984).

Вычисляем отношения одноименных координат этих векторов:

-8.01/5.99 » -1.337; -8.016/5.984 » 1.339,

т.е. отношения почти равны. Это значит, что векторы Ñf(X(12)) и Ñg(X(12)) почти коллинеарны (параллельны). Точка X(12) находится вблизи границы области допустимых решений (поскольку g(X(12)) » 0.078), следовательно x1* = 4.005 и x2* = 4.102 приемлемое решение.

Метод Эрроу-Гурвица.

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

ai(k) = max{0; ai(k-1) - lgi(X(k))} (i = 1, 2, ..., m),

ai(0) - произвольные числа больше 0.

З А Д А Ч И П О Т Е М Е

ЗАДАЧА Б.1.

Найти максимум функции F = 3x1 + 4x2 при условии:

ì x12 + x22 £ 25,

í x1×x2 ³ 4,

î x1, x2 ³ 0.

ЗАДАЧА Б.2.

На двух предприятиях нужно изготовить 200 изделий некоторой продукции. Затраты, связанные с производством x1 изделий на первом предприятии, равны 4x12 тыс.руб., а затраты обусловленные изготовлением x2 изделий на втором предприятии, составляют 20x2 + 6x22 тыс. руб. Определить, сколько изделий на каждом предприятии следует произвести, чтобы общие затраты были минимальные.

f(x1, x2, ..., xn) (Б.1)

при условии, что переменные удовлетворяют соотношениям:

ì gi(x1, x2, ..., xn) £ bi, (i = 1, 2, ..., k)

í (Б.2)

î gi(x1, x2, ..., xn) £ bi, (i = k+1, ..., n)

где f и gi некоторые известные функции, bi - заданные числа.

f(x1*, x2*, ..., xn*) ³ f(x1, x2, ..., xn) - для задачи максимизации;

f(x1*, x2*, ..., xn*) £ f(x1, x2, ..., xn) - для задачи минимизации.

f(x1, x2, ..., xn) = h.

Эта точка может быть как на границе, так и внутри области.

Процесс решения задачи в геометрической интерпретации включает этапы:

Определение области допустимых решений соответствующих (Б.2) (если она пуста, то решений задачи - нет);

Построение гиперповерхности f(x1, x2, ..., xn) = h;

Рассмотрим следующую задачу. Найти максимальное значение функции:

F = x2 - x12 + 6x1,

при условиях

ì 2x1 + 3x2 £ 24

ï x1 + 2x2 £ 15

í 3x1 + 2x2 £ 24

ï x2 £ 4

î x1, x2 ³ 0

Строим область допустимых решений и линии уровня:

12 3x1 + 2x2 = 24

F = 13

Линии уровня: F = x2 - x12 + 6x1 = h

F = 10

8 Область допустимых решений: ðOABC

F = 9

D B

A x2 = 4

x1 + 2x2 = 15

O C x1

0 3 8 12 15

2x1 + 3x2 = 24

ì x2 - x12 + 6x1 = 13,

î x2 = 4.

Решение ее будет: x1* = 3, x2* = 4, а Fmax = 13. Следует заметить, что точка D не является вершиной.

Метод множителей Лагранжа.

Общая постановка задачи состоит в нахождении максимума (минимума) функции:

f(x1, x2, ..., xn)

при условии:

g(x1, x2, ...,xn) = bi , i = 1, 2, ..., m.

F(x1, x2, ..., xn, l1, l2, ..., lm) = f(x1, x2, ..., xn) + å li[bi - gi(x1, x2, ..., xn)]

i=1

Далее определяют частные производные:

¶F/¶xj (j = 1, 2, ..., n) и ¶F/¶li , (i = 1, 2, ..., m).

На следующем шаге рассматривается система n + m уравнений:

ì ¶F/¶xj = ¶f/¶xj - å li¶gi/¶xj = 0, j = 1, 2, ..., n,

í i=1

î ¶F/¶li = bi - gi(x1, x2, ..., xn) = 0, i = 1, 2, ..., m.

1. Составляют функцию Лагранжа.

2. Находят частные производные функции Лагранжа по xj и li и приравнивают их 0.

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

Р е ш е н и е. Необходимо определить минимум функции:

f = 4x1 + x12 + 8x2 + x22,

при условиях:

x1 + x2 = 180, x1, x2 ³ 0.

Строим функцию Лагранжа:

F(x1, x2, l) = 4x1 + x12 + 8x2 + x22 + l(180 - x1 - x2).

Дифференцируя F, получаем систему:

ì ¶F/¶x1 = 4 + 2x1 - l =0,

í ¶F/¶x2 = 8 + 2x2 - l = 0,

î ¶F/¶l = 180 - x1 - x2.

Отсюда:

ì x1 - x2 = 2,

î x1 + x2 = 180, или x1* = 91, x2* = 89 и C = fmin(x1*, x2*) = 17278 тыс. руб.

Выпуклое программирование.

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

f(x1, x2, ...,xn)

при условиях:

gi(x1, x2, ..., xn) £ bi (i = 1, 2, ..., m), xj ³ 0 (j = 1, 2, ..., n).

Несколько определений.

f[lX2 + (1 - l)X1] ³ lf(X2) + (1 - l)f(X1).

Задача выпуклого программирования возникает, если функция f является вогнутой (выпуклой), а gi - выпуклы.

F(x1, x2, ..., xn, l10, l20, ..., lm0) £ F(x10, x20, ..., xn0, l10, l20, ..., lm0) £

£ F(x10, x20, ..., xn0, l1, l2, ..., lm),

для всех xj ³ 0 и li ³ 0.

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

¶F0/¶xj £ 0, xj0¶F0/¶xj = 0, xj0 ³ 0,

¶F0/¶li ³ 0, li0¶F0/¶li = 0, li0 ³ 0.

(частные производные берется в седловой точке).

Для задачи нахождения минимума седловая точка определяется соотношениями:

F(x10, x20, ..., xn0, l1, l2, ..., lm) £ F(x10, x20, ..., xn0, l10, l20, ..., lm0) £

£ F(x1, x2, ..., xn, l10, l20, ..., lm0).

Условия седловой точки в этой задаче представляются в виде:

¶F0/¶xj ³ 0, xj0¶F0/¶xj = 0, xj0 ³ 0,

¶F0/¶li £ 0, li0¶F0/¶li = 0, li0 ³ 0.

Градиентные методы.

Метод Франка-Вулфа. Найти максимум вогнутой функции:

f(x1, x2, ..., xn),

при условии:

åaijxj £ bi, (i = 1, 2, ..., m) xj ³ 0, j = 1, 2, ..., n.

j=1

Ñf(X(k)) = (¶f(X(k))/¶x1, ..., ¶f(X(k))/¶xn)

и строят линейную функцию:

F = ¶f(X(k))/¶x1×x1 + ... + ¶f(X(k))/¶xn×xn.

X(k+1) = X(k) + lk(Z(k) - X(k)),

Итак, этапы решения задачи методом Франка-Вулфа заключаются в следующем:

Определяют одно из допустимых решений.

Находят градиент функции f в точке допустимого решения.

Строят функцию F и находят ее максимальное значение при условиях исходной задачи.

Определяют шаг вычислений.

По формуле X(k+1) = X(k) + lk(Z(k) - X(k)) находят следующее допустимое решение.

Рассмотрим следующую задачу. Найти максимум функции:

f = 2x1 + 4x2 + x12 + 2x22

при условии:

ì x1 + 2x2 £ 8,

î 2x1 - x2 £ 12, x1, x2 ³ 0.

Р е ш е н и е. Находим градиент функции f:

Ñf = (¶f/¶x1, ¶f/¶x2) = (2 - 2x1; 4 - 4x2).

Исходное допустимое решение X(0) = (0, 0), а в качестве критерия оценки качества (точности) берем:

|f(X(k+1)) - f(X(k))| £ 0.01.

Первая итерация. В точке X(0) Ñf(X(0) ) = (2, 4). Находим максимум функции:

F1 = 2x1 + 4x2,

при условиях исходной задачи. Эта задача имеет решение Z(0) = (0, 4).

Новое допустимое решение ищем в виде:

X(1) = X(0) + l1(Z(0) - X(0) ), 0 £ l1 £ 1.

Подставив сюда X(0) и Z(0) имеем:

ì x1(1) = 0 + l10,

î x2(1) = 0 + l14.

Подставив их в f имеем:

f(l1) = 16l1 - 32l12.

Находим производную этой функции и приравниваем ее 0, имеем:

f¢(l1) = 16 - 64l1 = 0, l1 = 1/4.

Итак:

X(1) = (0, 1), f(X(1)) = 2, но f(X(1)) - f(X(0)) = 2.

Вторая итерация. Имеем:

Ñf(X(1) ) = (2, 0).

Ищем максимум функции:

F2 = x1,

при условии исходной задачи. Решение этой задачи будет:

Z(1) = (6.4, 0.8).

Определяем далее:

X(2) = X(1) + l2(Z(1) - X(1)).

Подставив сюда Z(1), получим:

ì x1(2) = 6.4l2,

î x2(2) =1 + 0.2l2.

f(l2) = 2 + 12.8l2 - 41.04l22.

f¢(l2) = 12.8 - 82.08l2 = 0, l2 » 0.16.

x1(2) » 1.02, x2(2) » 0.94, f(X(2)) » 2.9978.

f(X(2)) - f(X(1)) = 0.9978 > 0.01.

Проводя аналогичные вычисления для третьей итерации, получим:

f(X(3)) » 2.99991,

f(X(3)) - f(X(2)) = 0.00211 < 0.01,

X(3) » (1.0098, 1.0003).

Максимум же достигается в точке X* = (1, 1).

Метод штрафных функций.

Пусть имеем вогнутую функцию f(x1, x2, ..., xn), необходимо найти максимум этой функции при условиях:

gi(x1, x2, ..., xn) £ bi , (i = 1, 2, ...,m), xj ³ 0,

где gi - выпуклые функции.

Строится функция:

F(x1, x2, ..., xn) = f(x1, x2, ..., xn) + H(x1, x2, ..., xn),

H(x1, x2, ..., xn) = å ai(x1, x2, ..., xn) qi(x1, x2, ..., xn),

i=1 где

ì 0, если bi - gi ³ 0,

ai = í ai - весовые коэффициенты

î ai, если bi - gi < 0,

qi = bi - gi

xj(k+1) = max{0; xj(k) + l[¶f(X(k) )/¶xj + å ai¶qi(X(k) )/¶xj]} (Б.3)

i=1

Итак, процесс решения включает этапы:

Определяют исходное допустимое решение.

Выбирают шаг вычислений.

По (Б.3) определяют координаты точки - возможное новое решение.

Устанавливаются значения весовых коэффициентов и переходят к этапу 4.

Рассмотрим следующую задачу. Найти максимум функции:

f = -x12 - x22,

при условиях:

(x1 - 7)2 + (x2 - 7)2 £ 18, x1, x2 ³ 0.

X(1) X(0)

X(2)

X(3) X(4)

X(5)

Полагаем X(0) = (6, 7). Берем l =0.1. Пусть g(x1, x2) = 18 - (x1 - 7)2 - (x2 - 7)2, определяем частные производные:

¶f/¶x1 = -2x1; ¶g/¶x1 = -2x1 + 14; ¶f/¶x2 = -2x2; ¶g/¶x2 = -2x2 + 14.

Используем (Б.3) и строим последовательность точек, одна из которых определяет приемлемое решение.

x1 = max {0; x1(0) + l ¶f(X(0))/¶x1} = max{0; 6 + 0.1(-2)× 6} = 4.8,

x2 = max {0; x2(0) + l ¶f(X(0))/¶x2} = max{0; 7 + 0.1(-2) ×7} = 5.6.

Проверяем, входит ли точка с координатами (x1(1), x2(1)) в область допустимых решений. Находим

g(X(1)) = 18 - 4.84 - 1.96 = 11.2 > 0.

Следовательно, точка X(1) принадлежит области допустимых решений и в этой точке f(X(1)) = -54.4.

Итерация 4. В соответствии с (Б.3) решение представляем в виде:

x1(4) = max {0; x1(3) + l[¶f(X(3))/¶x1 + a¶g(X(3))/¶x1]} =

= max(0; 3.072 + 0.1[(-2) ×3.072 + a((-2)3.072 + 14)]} = max{0; 2.4576 + a0.7856},

x2(4) = max {0; x2(3) + l[¶f(X(3))/¶x2 + a¶g(X(3))/¶x2]} =

= max(0; 3.584 + 0.1[(-2) ×3.584 + a((-2)3.584 + 14)]} = max{0; 2.8672 + a0.6832}.

x1(4) = max {0; 2.4576 + 1.9 ×0.7856} » 3.950,

x2(4) = max {0; 2.8672 + 1.9 ×0.6832} » 4.165,

g(X(4)) = 18 - 9.3025 - 8.037225 » 0.660, f(X(4)) = - 32.950.

Итерация 12.

x1(12) = max{0; 3.203 + 0.1[(-2)3.203 + 1.9((-2)3.203 + 14)]} » 4.005,

x2(12) = max{0; 3.205 + 0.1[(-2)3.205 + 1.9((-2)3.205 + 14)]} » 4.008,

g(X(12))= 18 - 8.970025 - 8.952064 » 0.078; f(X(12)) = - 32.104.

f(X(12)) - f(X(11)) = -32.104 - (-32.116) = 0.012 < 0.1,

т.е. найденное на двенадцатом шаге итерации решение является приемлемым.

Такой же вывод можно сделать, если исследовать поведение вектор-градиентов функций f(X) и g(X) в точке X(12):

Ñf(X(12)) = (-8.01, -8.016), Ñg(X(12)) = (5.99, 5.984).

Вычисляем отношения одноименных координат этих векторов:

-8.01/5.99 » -1.337; -8.016/5.984 » 1.339,

Метод Эрроу-Гурвица.

ai(k) = max{0; ai(k-1) - lgi(X(k))} (i = 1, 2, ..., m),

ai(0) - произвольные числа больше 0.

З А Д А Ч И П О Т Е М Е

ЗАДАЧА Б.1.

Найти максимум функции F = 3x1 + 4x2 при условии:

ì x12 + x22 £ 25,

í x1×x2 ³ 4,

î x1, x2 ³ 0.

ЗАДАЧА Б.2.

5rik.ru

Материалы для учебы и работы

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