D-постановка

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

d_jk = X_{jk +1} – X_jk

и уравнение сетки записывается в виде

x_j = d_j + ; (8.25)

0 £ y_jk £ 1, (8.26)

где y_jk – новые переменные.

Из представления переменной в виде (8.25), (8.26) следует:

· x_j = d_j, когда " y_jk =0;

· x_j находится в первом интервале, когда y_{j 1} Î (0, 1), остальные y_jk =0;

· x_j находится во втором интервале, когда y_{j 1}=1, y_{j 2} Î (0, 1), остальные y_jk =0;

· x_j находится в k -ом интервале, когда y_{j 1} = y_{j 2} =... = y_{jk -1} = 1, 0 £ y_jk £ 1,

остальные y_jk =0.

Таким образом, для правильной аппроксимации должно выполняться установленное соответствие между значениями переменной x_j и y_jk. Это требование аналогично правилу смежных весов. При ином представлении значения x_j будет нарушена кусочно-линейная аппроксимация функции.

Для аппроксимации нелинейной составляющей функции критерия вычисляются разности ее значений в смежных узлах

D _jk = f_j (X_{jk +1}) – f_j (X_jk),

с помощью которых записывается аппрокимирующая функция

(8.27)

Тогда функция, аппроксимирующая критерий, имеет вид

Аналогично аппроксимируются ограничения j_ij (x_j):

Как и в l-постановке, если имеет место задача выпуклого программирования, то требования к переменным y_jk выполняются автоматически и полученное решение будет приближенным глобальным решением исходной задачи. В противном случае, необходимо придерживаться правила ограниченного ввода относительно переменных y_jk: если первые k переменных равны единице, вводить можно только y_{jk +1}.

При практическом решении сепарабельных задач сначала можно взять малое число узлов и получить приближенное оптимальное решение. Затем в качестве исходных принять интервалы, на которых лежат оптимальные x_j, и выполнить аппроксимацию функций только на этих интервалах с малыми расстояниями между узлами. Такой способ снижает размерность решаемых задач и повышает точность получаемого решения.

Следует заметить, что в ряде случаев несепарабельная функция может быть преобразована к сепарабельной. Способ преобразования зависит от структуры функции. Например, произведение двух сепарабельных функций S (X)× T (X) можно привести к сепарабельному виду, заменив его перменной v с дополнительными равенствами

S (X) = z – y; T (X) = z + y.

Тогда v = (z - y)(z + y) = z ² – y ² – сепарабельная функция. Так функция

f = x ₁ + x ₂ ×x ₃² заменяется на сепарабельную f = x ₁ + v с дополнительными сепарабельными ограничениями

Пример 8.4. Покажем, что некоторые стохастические задачи могут сводиться к сепарабельным. Стохастические модели описывают ситуации выбора решения в условиях риска, обусловленного влиянием случайных факторов. Предполагается, что закон распределения случайных величин известен.

Пусть зависимости от искомых переменных линейны, но коэффициенты критерия и ограничений зависят от случайной величины w (состояния среды). В этом случае в качестве критерия берется обычно математическое ожидание линейной формы M (L)= M [ C ^T(w) X ]= а запись ограничений зависит от требований к их выполнению. При допустимости некоторых нарушений условий задачи ограничения записываются в вероятностной форме:

где p_i - заданное значение вероятности. выполнения i -го условия. Такое ограничение заменяется эквивалентным детерминированным условием

(*)

где - математические ожидания, - дисперсия , - дисперсия , = t (p_i) – значение функции, обратной функции распределения (например, нормального).

В результате детерминированная модель стохастической задачи включает линейный критерий и существенно нелинейные ограничения (*). Очевидно, что она не является сепарабельной. Сделаем простое преобразование. Обозначим

.

Тогда каждое ограничение (*) заменяется двумя условиями:

Первое из них – линейное, а второе – сепарабельное. Таким образом, стохастическая задача приведена к сепарабельной.

Примечание. Если случайным является только вектор ограничений, то, как следует из (*), стохастическая задача сводится к линейной.