Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата



____

(27) dL(x; ?)/d?j=0, j=1,m

КВАДРАТИЧНОЕ ПРОГРАММИРОВАНИЕ (КП).

Задачей КП называют задачи НЛП, в которой минимизируется сумма линейной и квадратичной форм при ограничениях типа линейных неравенств и не отрицательности переменных. В матричной форме эта задача имеет вид:

(28) q(x)=Cx+xTdx=min,

Ax?в, x?0

ИНТЕРАТИВНЫЕ МЕТОДЫ ПОИСКА ОПТИМУМА.

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

ГРАДИЕНТНЫЙ МЕТОД.

Этот метод представляет собой последовательность шагов, каждый из которых содержит две операции:

1) определение направления антиградиента функции q(х)

2) перемещение в выбранном направлении на заданное расстояние.

МЕТОД НАИСКОРЕИШЕГО СПУСКА (ПОДЪЕМА).

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

Если на каком-то шаге q(х) возросло, то движение в данном направлении прекращается, последний шаг снимается полностью или на половину и вычисляется новый градиент функции q(х), а значит и новое направление движения.

АЛГОРИТМ НЬЮТОНА.

В тех случаях, когда поверхность отклика достаточно хорошо описывается уравнением второго порядка, резкое уменьшение числа шагов можно получить, если воспользоваться алгоритмом Ньютона, при этом представлении q(х) в виде;

q(x)=q(x)*+Ѕ S S akj ?x(k) ?x(j) ГДЕ X=X -X -отклонение k j от точки оптимума.
Будет достаточным при значительном удалении от точки оптимума и в качестве матрицы Гп можно взять непосредственно матрицу А.
Однако элементы, аij матрицы А, вычисленные в точке оптимума, заранее не известны. Тем не менее, при достаточно хорошей поверхности отклика вторые производные функции q(х) вычисленные в произвольной точке х=хп будет близка к элементам aij матрицы А.

1.11. ЗАДАЧИ И МЕТОДЫ ЛИНЕЙНОГО ПРГРАММИРОВАНИЯ.

Дана система m линейно независимых уравнений с неизвестными х ,...,х называемая системой ограничений задачи линейного программирования: a11x1+...+a1nxn=в1

(1) ............................ am1x1+...+a1mxn=вn ___ где не уменьшая общности можно считать вi?0, i=1,m.
Характерной особенностью данной задачи является, то, что число уравнений меньше числа неизвестных, т.е. m0, хд=0, det(В)?0, Вхв=в

Рассмотрим векторы: хк=хк(?)= xв-?bak-1 ______

? k=(m+1,n)

0 где ? является к - й компонентой вектора х.
Если хв>0, то при малых ?>0; хk?0, т.к. Ахk=в, то хk?R? при малых ?>0.
Кроме того:
=-?[-Ck]=-??k
?к - определитель для любого к=1,n, причем при к=1,m;
?к=-Ck=Cк=Cк-Cк=0
Окончательно; =-??x (k=1,n)

3)Выбор столбца для ввода из базиса.
В зависимости от значков величины ?к и (В-1ak); возникает 3 случая.

Рекомендуем скачать другие рефераты по теме: сочинение 7 класс, диплом школа.

Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата