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

Построение аппроксимирующей задачи основано так же на кусочно-линейном приближении, но меняется уравнение сетки. По узлам сетки вычисляются расстояния между смежными узлами d_jk = X_{jk +1} – X_jk

и уравнение сетки записывается в виде x_j = d_j + ; (25) 0 £ y_jk £ 1, (26)

где y_jk – новые переменные. Для аппроксимации нелинейной составляющей функции критерия вычисляются разности ее значений в смежных узлах D _jk = f_j (X_{jk +1}) – f_j (X_jk), с помощью которых записывается аппрокимирующая функция (27)

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

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

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

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

В общем случае целевая функция имеет вид (28)

Такая функция легко преобразуется в линейную, если ее знаменатель при всех допустимых значениях переменных строго положителен. Для этого введем новую переменную r (29). Очевидно, что при оговоренном условии она может быть только больше нуля. Тогда функция (28) принимает вид Произведя замену произведения переменных (30) окончательно имеем (31) Получили линейную функцию от n неотрицательных переменных y_j и одной положительной переменной r. Эта функция должна рассматриваться вместе с условием, следующим из (29): или после замены (30) (32) Следует ограничения задачи записать в новых переменных. Для этого умножим обе части каждого ограничения на r и, произведя замену, получаем (33) В результате преобразований имеем задачу ЛП с критерием (31), ограничениями (32), (33) и переменными r > 0, y_j ³ 0, " j. Воспользовавшись (30) вернемся к исходным переменным. Возможность перехода к линейной задаче геометрически обусловлена тем, что линии уровня дробно-линейной функции описываются линейным уравнением. , из (28) следует или . (34) При изменением возникает поворот вокруг мн-ва вращения. Мн-во вращения – это множество точек, образованное пересечением нулевых линий уровня числителя и знаменателя: n=2 – точка, n=3 - прямая

15. Классификация и характеристика методов «спуска».

Так называются численные итерационные методы оптимизации, ориентированные на поиск минимума. При выборе метода следует учитывать свойства целевой функции: унимодальность или многоэкстремальнсть, дифференцируемость, выпуклость-вогнутость или их отсутствие и т. д. Кроме того, функции могут обладать особенностями, такими как седловые точки и овражность. “Овраг” (при максимизации “гребень”) проявляются в том, что вдоль него функция изменяется намного слабее, чем в поперечном направлении.

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

По информации, используемой для определения направления поиска выделяют методы:

- нулевого порядка или прямые, вычисляется только значение функции;

- первого порядка (градиентные), использующие первые производные;

- второго порядка, требующие вычисления также вторых производных;

- случайного поиска, механизм случайного выбора направления;

- генетические, элементы детерминизма и случайности выбора;

- комбинированные.

Все приводимые ниже методы предназначены для минимизации унимодальных функций.