Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
L - постановка
|
|
Предполагается, что переменные, которые входят в модель нелинейно, ограничены снизу и сверху: dj £ xj £ Dj. (19)
Для кусочно-линейной аппроксимации в этом диапазоне выбираются узловые точки. При этом первый узел совпадает с нижней границей, а последний – с верхней: Xj1 = dj, 
= Dj, где rj – число интервалов по переменной xj (rj +1 – число узлов). Тогда рассматриваемая переменная xj может быть выражена через новые переменные ljk в виде
, (20) 
, (21) 
. (22)
Выражение (20) называют уравнением сетки. С использованием узловых точек и новых переменных кусочно-линейная функция, аппроксимирующая
fj (xj), записывается в виде 
(23)
где fj (Xjk) – значение функции в узловых точках. Очевидно, что 
– функция, линейная относительно ljk. Пусть N – множество индексов нелинейных fj (xj). Тогда функция, аппроксимирующая f (X), имеет вид 
(24)
Если переменная xj входит нелинейно в несколько функций, узлы сетки выбираются с учетом нелинейности всех таких функций, так как для одной переменной может быть только одно уравнение сетки.
Поясним запись ограничений. Исходное ограничение S jij (xj) £ bi со всеми нелинейными jij. Тогда после аппроксимации оно принимает вид 
Хотя аппроксимирующая задача линейная, получаемое на ней решение не всегда является приближением к решению исходной задачи.
Отсюда следует правило смежных весов: из одного уравнения сетки отличными от нуля могут быть не более 2-х переменных ljk со смежными значениями k.
Если аппроксимирующая задача является задачей выпуклого программирования, то это правило выполняется автоматически и решение находится методом ЛП. Оптимальное решение аппроксимирующей задачи будет приближением глобального решения исходной задачи.
В противном случае алгоритм ЛП должен включать правило ограниченного ввода: если в базисном решении находится ljk, то допустимыми для ввода могут быть только ljk +1 или ljk -1. При этом нельзя утверждать, что получаемое решение является приближением к глобальному оптимуму исходной задачи. Скорее оно будет приближением локального оптимума.