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

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

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

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

F () = .

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

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

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

, .

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

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

F (Х) = → min (max)

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

, ,

, .

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

Поиск по сайту: