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

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

F(X)= F₁(x₁)+F₂(x₂)+...+F_n(x_n),

(не исключено, что F­_i(x_i)=0 при некоторых i).

Пусть задана ЗВП: ограничения _i(x₁, x₂, ... , x_n)  b_i , i=1,2,...,m (1)

x₁, x₂, ... ,x_n  0,

и целевая функция Z=f(x₁, x₂, ... , x_n), (2)

причем все функции _i(Х) являются выпуклыми на некотором выпуклом множестве М, а функция Z либо выпукла на множестве М, либо вогнута. Пусть функция цели и ограничения _i являются сепарабельными. Тогда исходная задача имеет вид: найти минимум выпуклой (максимум вогнутой) функции Z= f₁(x₁)+f₂(x₂)+...+f(x_n) при ограничениях

Идея метода кусочно-линейной аппроксимации состоит в том, что все f_i и все _ij заменяются ломаными линиями, состоящими из прямолинейных отрезков. При этом исходная ЗВП заменяется новой, приближенной задачей, которая является задачей ЛП и решается обычно симплексным методом. Ее решение является приближенным решением исходной ЗВП.

h(x)

h’(x)

h_k

h_k+1

x₀=0

x₁

x_r=a

x_k

x_k+1

Для построения приближенной задачи рассмотрим кусочно-линейную аппроксимацию функции одной переменной h(x), заданной на отрезке [0,a]. Разобьем этот отрезок на r частей точками x₀<x₁<…<x_r так, чтобы x₀=0, x_r=a (см. рис.). Вычислим значения функции h_k(x) (k=0,1,…,r) в этих точках. Соединим попарно точки (x_k;h_k) и (x_k+1;h_k+1) отрезками прямых. Состоящая из этих отрезков ломаная h’(x) аппроксимирует функцию h(x) на отрезке [0,a]. (Точность приближения можно увеличить за счет более мелкого разбиения отрезка).

Уравнение участка ломаной h’(x) между точками (x_k;h_k) и (x_k+1;h_k+1) имеет вид (уравнение прямой по двум точкам). Если каждое из отношений в этом равенстве обозначить через , то получим:

(*) причем 01.

Отметим, что для каждого x[x_k;x_k+1] существует единственное значение , удовлетворяющее условиям (*) ( см. уравнение отрезка из определения выпуклого множества точек). Обозначив 1-=_к, =_к+1, можно переписать (*) в виде:

где _к+_к+1=1, _к0, _к+10.

Данные уравнения называются параметрическими уравнениями отрезка.

Таким образом, для любого x[0;а] уравнение ломаной можно записать в виде:

(**)

причем всегда отличны от 0 только два значения _к (если х является внутренней точкой к-го отрезка разбиения) или одно (если х совпадает с концами отрезка).

Возвращаясь к ЗВП с сепарабельными функциями, отметим, что прежде всего (в зависимости от системы ограничений) нужно определить интервал изменения каждой переменной x_j. Затем каждый этот интервал разбивается на части точками x_jk и с использованием формул (**) строится кусочно-линейная аппроксимация для функций f_i и _ij . После этого можно для исходной задачи записать приближенную задачу: найти максимум функции Z’= f’₁(x₁)+f’₂(x₂)+...+f’(x_n) при ограничениях

Пример. Найти минимум функции Z=2(x₁-1)²+(x₂-2)² при ограничениях

Решить задачу методом кусочно-линейной аппроксимации.

Решение. При условии неотрицательности переменных неравенство показывает, что х₁ может изменяться от 0 до 2, а х₂ – от 0 до 4.

Отрезок [0;2] разобьем точками х₁₀=0, х₁₁=1, х₁₂=2, а отрезок [0;4] - точками х₂₀=0, х₂₁=1, х₂₂=2, х₂₃=3, х₂₄=4. Функция Z – сепарабельная, т.к. f₁=2(x₁-1)², f₂=(x₂-2)².

Удобно сначала вычислить необходимые значения этих функций (т.к. имеем лишь одно ограничение, т.е. m=1, будем писать ₁ и ₂).

Х1	Х10	Х11	Х12		Х2	Х20	Х21	Х22	Х23	Х24
Х1	0	1	2		Х2	0	1	2	3	4
1	0	1	4		2	0	1	2	3	4
f1	2	0	2		f2	4	1	0	1	4

По формулам (**) имеем:

Т.о., приближенная задача для данной задачи имеет вид: найти максимум функции

Z’= 2₁₀+2₁₂+4₂₀+₂₁+₂₃+4₂₄ при ограничениях

Это ЗЛП с 8 переменными _ij. Решаем ее симплексным методом. На 3-ем шаге получаем оптимальное базисное решение: ₁₁=₂₂=1, ₁₀=₁₂=₂₀=₂₁=₂₃=₂₄=0. Переходя к исходным переменным х₁, х₂, получаем:

x₁=₁₁+2₁₂=1, x₂=₂₁+2₂₂+3₂₃+4₂₄=2.

Т.о., оптимальное решение приближенной задачи (1;2) и Z_min=0.