Метод кусочно-линейной аппроксимации

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

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

Функция F( ) называется сепарабельной, если её можно представить в виде суммы функций, каждая из которых зависит только от одной переменной, т.е. если

F( ) = .

Пусть в ЗВП целевая функция F(Х) и функции являются сепарабельными. Тогда ЗВП формулируется следующим образом. Найти минимум выпуклой (максимум вогнутой) целевой функции

F(Х) = F ( )= → min (max)

и соответствующие ему переменные при условии, что эти переменные удовлетворяют системе ограничений

, .

Сначала определяют интервал изменения каждой переменной . Затем каждый такой интервал разбивают на части точками ( ). По формулам

строят кусочно-линейную аппроксимацию для функций и . Далее записывают для исходной ЗВП приближённую задачу: найти экстремум целевой функции

F(Х) = → min (max)

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

, ,

, .

Получившаяся приближённая задача является ЗЛП, поэтому её можно решать обычными методами линейного программирования. При этом следует помнить, что для каждого есть не более 2-х соседних ненулевых , следовательно, нельзя брать в качестве основных переменных два с одинаковыми j и несоседними k.

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

Производной функции F(Х) = F ( ) по направлению l в точке Х называется предел

.

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

Градиент функции F(Х) = F ( ) – вектор, координаты которого равны соответствующим частным производным:

grad F(Х) .

В каждой точке Х направление наискорейшего возрастания функции F(Х) совпадает с направлением градиента , а направление наискорейшего убывания - направлением антиградиента - . На этом свойстве градиента базируются многие итерационные методы оптимизации функции, в том числе - и градиентный метод.

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

В случае поиска минимума функции говорят о методе наискорейшего спуска, в случае задачи максимизации – о методе наискорейшего подъёма.

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

, (5.23)

если ищется F_max, или

, (5.24)

если ищется F_min.

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

Если , то шаг выбирают из условия F( ) < F( ).

Если , то - стационарная точка. В этом случае итерационный процесс прекращается и при необходимости проводят дополнительное исследование поведения функции в окрестности точки , чтобы выяснить, достигнут ли в точке экстремум. Если F(Х) – выпуклая функция, то в стационарной точке всегда достигается минимум.

Замечания. 1) На практике итерации продолжаются до тех пор, пока не выполнится некоторый критерий счёта, например,

|F( )-F( )| ε,

где ε – заданное число (погрешность вычисления).

2) По методу наискорейшего спуска длина шага выбирается из условия экстремума функции .

Необходимое условие экстремума этой функции имеет вид:

(5.25)

- скалярное произведение градиентов целевой функции в точках и

равно нулю, что равносильно условию ортогональности градиентов.

3) Для упрощения вычислений в формулах (5.23) – (5.25) можно вместо брать любой вектор с тем же направлением (умножив координаты вектора на нужное положительное число).

Условие (5.25) даёт геометрическую интерпретацию градиентного метода в случае функции 2-х переменных: луч, идущий от точки к , перпендикулярен линии уровня целевой функции F(Х), проходящей через точку (т.к. направлен по градиенту), и касается линии уровня, проходящей через точку , т.е. на плоскости наискорейший спуск происходит по двум взаимно перпендикулярным направлениям.

Пример. Решить задачу:

F( ) = → min,

Решение.

1) Покажем, что данная задача является задачей выпуклого программирования. Частные производные функции F( ): , , , , . Матрица вторых частных производных имеет вид

А = .

Её главные миноры: . Условия критерия Сильвестра выполняются, следовательно, функция F( ) является строго выпуклой, а поставленная задача является ЗВП.

2) Решим ЗВП градиентным методом - методом наискорейшего спуска. ОДР задачи – криволинейная область АВС (рис. 46)

Найдём градиент целевой функции: .

В качестве исходной точки выберем точку Х₀ (2; 1), принадлежащую ОДР. Вычислим значение градиента в точке Х₀:

.

Следующую точку Х₁ найдём по формуле (5.24):

= (2; 1) - (2; - 2) = (2 - 2 ; 1 + 2 ).

Градиент в точке Х₁:

.

А

B

C

Рис.3. Область допустимых решений ЗВП

По условию (5.25) найдём :

.

Подставим это значение в выражения для Х₁ и , получим:

Х₁ = (1; 2); .

Так как градиент в точке Х₁ = (1; 2) равен нулю, то в этой точке достигается минимум целевой функции. F_min (1; 2) = - 2. Экстремум найден за 1 шаг, причём он достигается во внутренней точке ОДР.

Вычисления по методу наискорейшего спуска удобно представлять в таблице. Расчёты данной ЗВП занесём в табл. 21.

Таблица 21

k		F( )				∙
0	(2; 1)	0	(2; -2)	(2-2 ; 1+2 )	(2-4 ; -2+4 )	8 - 16	0,5
1	(1; 2)	- 2	(0; 0)

В данном примере экстремум достигался внутри ОДР. Если экстремум ЗВП достигается на границе ОДР, то поступают следующим образом.

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

Пусть система ограничений ЗВП линейна, т.е. имеет вид

, .

Пусть методом скорейшего спуска получена последовательность точек , причём точки лежат в ОДР, а нет. Это означает, что координаты точки не удовлетворяют хотя бы одному неравенству системы ограничений, например неравенству с номером i.

Если = , = , то условие

= + l равносильно равенствам

, , (5.26)

где - направление спуска, совпадающее с направлением градиента при задаче на максимум и с направлением антиградиента при задаче на минимум.

Для того, чтобы остаться в ОДР, нужно вместо взять точку, лежащую на том же направлении спуска, т.е. с координатами, удовлетворяющими равенствам (5.26), но с меньшей длиной шага .

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

, или

. (5.27)

По формуле (5.27) находят , при котором направление спуска пересекает границу ОДР. Если координаты не удовлетворяют нескольким неравенствам системы ограничений, то по формуле (5.27) находят для каждого из неравенств и выбирают из них наименьшее значение. Подставляя это в (5.26), находят координаты точки , являющейся исходной для следующего шага решения. Поскольку проекция градиента ( ) задачи с линейными ограничениями лежит на границе ОДР, то направление спуска l на следующем шаге берётся на этой границе. Экстремум достигается в той точке, где градиент перпендикулярен границе ОДР.

Если прямая на плоскости задана уравнением ax + by + c = 0, то её направление задаётся вектором или вектором .

Пример. Решить ЗВП градиентным методом:

F( ) = → max,

Решение. Область допустимых решений задачи – трапеция ОАВС (рис. 4). Градиент целевой функции .

А

B

C

O

Рис.4. Область допустимых решений ЗВП

В качестве исходной точки выберем точку Х₀ (1; 1), принадлежащую ОДР. Вычислим значение градиента в точке Х₀:

.

Следующую точку Х₁ найдём по формуле (23):

= (1; 1) + (3; 5) = (1 + 3 ; 1 + 5 ).

Градиент в точке Х₁: .

По условию (5.25) найдём :

.

Подставим это значение в выражение для Х₁, получим:

Х₁ = .

Точка Х₁ не принадлежит ОДР, причём не выполняются оба неравенства системы ограничений. По формуле (5.27) найдём для обоих неравенств:

=

.

Точка лежит на границе ОДР, а именно на прямой . Далее нужно двигаться в сторону увеличения целевой функции F(Х).

Направление прямой задаётся векторами или . Вычислим производную функции F(Х) по направлению в точке : = . Следовательно, в этом направлении функция возрастает и в качестве направления спуска нужно взять .

Следующую точку Х₂ найдём по формуле:

= (1,6; 2) + (1; 0) = (1,6 + ; 2).

Градиент в точке Х₂:

.

По условию (5.25) найдём :

.

Подставим это значение в выражения для Х₂ и , получим:

Х₂ = (3; 2); .

Точка Х₂ лежит на границе ОДР, на прямой . Вычислим производную функции F(Х) по направлению в точке Х₂:

= .

Так как проекция градиента на это направление равна нулю, значит, получено оптимальное решение. Максимум целевой функции F_max (3; 2) = 7.

Представим расчёты в табл. 1.

Таблица 1

k		F( )				∙
0	(1; 1)	- 1	(3; 5)	(1+3 ;1+5 )	(1+3 ;1+5 )	34 - 38	17/19
1	(3,7; 5,5) ОДР						1/5
	(1,6; 2)	5,04	(1; 0)	(1,6+ ; 2)	(2,8-2 ;3,6+ )	2,8 -	7/5
2	(3; 2)	7	(0; 5)

Оптимальное решение ЗВП найдено за 2 шага, причём максимум получен на границе ОДР в точке (3; 2).

Пример. Решить ЗВП градиентным методом:

F( ) = → max,

Решение. ОДР задачи – треугольник ОАВ (рис. 48).

Градиент целевой функции .

В качестве исходной точки выберем точку Х₀ (2; 2), принадлежащую ОДР.

Вычислим значение градиента в точке Х₀:

.

А

B

O

Рис.5. Область допустимых решений ЗВП

Следующую точку Х₁ найдём по формуле (5.23):

= (2; 2) + (4; 6) = (2 + 4 ; 2 + 6 ).

Градиент в точке Х₁: .

По условию (5.25) найдём :

.

Подставим это значение в выражения для Х₁ и , получим:

Х₁ = ; .

Точка Х₁ принадлежит ОДР. Следующую точку Х₂ найдём по формуле (5.23):

= + .

Градиент в точке Х₂: и т.д.

Вычисления с округлениями до 10^-2 представим в табл. 23.

На 5-м шаге вычисления можно остановить, т.к. значение целевой функции меняется незначительно:

|F( )-F( )| = |24,3323 – 24,3333| = 0,001.

Таким образом, можно считать, что максимум целевой функции (с точностью вычислений ε = 0,01) достигается в точке = (6,66; 7,33).

F_max(6,66; 7,33) = 24,33.

Таблица 2

k		F( )				∙
0	(2; 2)	- 1	(4; 6)	(2 + 4 ; 2 + 6 )	(4 - 2 ; 6 - 8 )	52 - 56	0,93
1	(5,71; 7, 57)	23,14	(2,14; -1,43)	(5,71+2,14 ; 7, 57-1,43 )	(2,14-5,71 ; 5 -1,43)	6,63-19,39	0,34
2	(6,45; 7,08)	24,28	(0,19; 0,28)	(6,5+0,2 ; 7,08+0,3 )	(-0,08-0,1 ; 0,34-0,4 )	0,08– 0,132	0,6
3	(6,62; 7,26)	24,31	(0,02; 0,1)	(6,62+0,02 ; 7,26+0,1 )	(0,02-0,06 ; 0,1-0,18 )	0,01– 0,02	0,5
4	(6,63; 7,31)	24,332	(-0,01; 0,01)	(6,63-0,01 ; 7,31+0,01 )	(0,05+0,03 ; 0,01-0,03 )	0,001-0,0021	0,48
5	(6,66; 7,33)	24,333	(0,01; 0)

Контрольные вопросы:

1. Сформулируйте задачу нелинейного программирования. Приведите примеры.

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

Литература:

1. Высшая математика для экономистов: Учебник для вузов / Н.Ш. Кремер, Б.А. Путко, И.М. Тришин, М.Н.Фридман. Под ред. Н.Ш. Кремера. – М.: ЮНИТИ, 2005. – 471 с.

2. Общий курс высшей математики для экономистов: Учебник. / Под ред. В.И. Ермакова. –М.: ИНФРА-М, 2006. – 655 с.

3. Сборник задач по высшей математике для экономистов: Учебное пособие / Под ред.В.И. Ермакова. М.: ИНФРА-М, 2006. – 574 с.

4. Гмурман В. Е. Руководство к решению задач по теории вероятностей и магматической статистике. - М.: Высшая школа, 2005. – 400 с.

5. Гмурман. В.Е Теория вероятностей и математическая статистика. - М.: Высшая школа, 2005.

6. Данко П.Е., Попов А.Г., Кожевникова Т.Я. Высшая математика в упражнениях и задачах. Ч. 1, 2. – М.: Оникс 21 век: Мир и образование, 2005. – 304 с. Ч. 1; – 416 с. Ч. 2.

7. Математика в экономике: Учебник: В 2-х ч. / А.С. Солодовников, В.А. Бабайцев, А.В. Браилов, И.Г. Шандара. – М.: Финансы и статистика, 2006.

8. Шипачев В.С. Высшая математика: Учебник для студ. вузов – М.: Высшая школа, 2007. – 479 с.