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

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

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

 или  

(не исключено, что  при некоторых i).

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

 .

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

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

Уравнение участка ломаной между точками (x ;h )и (x ;h ) имеет вид   (уравнение прямой, построенной по двум заданным точкам).

Если каждое из отношений в этом равенстве обозначить через , то получим:

и , причем .

Обозначив , можно переписать в виде:

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

,

причем всегда отличны от нуля только для значения l _k (если x является внутренней точкой k-го отрезка разбиения), или одно, (если x совпадает с концом отрезка).

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

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

Задача. Найти минимум функции  при ограничениях:

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

Решение.

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

Отрезок [0;2] разобьем точками , а отрезок [0;4] точками  Положим: .

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

x1	x10	x11	x12		x2	x20	x21	x22	x23	x24
x1	0	1	2		x2	0	1	2	3	4
	0	1	4			0	1	2	3	4
f1	2	0	2		f2	4	1	0	1	4

По формулам имеем:

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

Решая данную задачу линейного программирования, как описано ранее, получим:

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

Задачи для самостоятельного решения

1 . Найти максимум функции  при ограничениях

2. Найти минимум функции  при ограничениях

  3. Найти максимум функции  при ограничениях