dx(i) >0, если x(i)=0, i=1,n

(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)*+½ ∑ ∑ 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.

Характерной особенностью данной задачи является, то, что число уравнений меньше числа неизвестных, т.е. m<n. Требуется найти неотрицательные значения переменных, которые удовлетворяют уравнениям (1) и обращают в минимум целевую функцию:

(2) q=c1x+ .+anx

Более компактно задачи ЛП могут быть записаны в матричной форме:

q(x)=cx=min

(3) Ax=B (B≥0), x≥0

где А - матрица размером m*n, В m - мерный вектор, х и c n - мерные вектора. Матрицу А называют матрицей условий задачи векторов В - вектор ограничений задачи (3).

ГЕОМЕТРИЧЕСКА ИНТЕРПРИТАЦИЯ ОСНОВНОЙ ЗАДАЧИ ПРОГРОММИРОВАНИЯ.

В пространстве Еn множество R1 можно рассматривать как пересечение полупространств (при n=2 - полуплоскостей). _

(Ax)i≥bi, ( i=1,m)

x≥0 (j=1,n)

СИМПЛЕКС МЕТОД.

1) Идея метода.

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

Рассмотрим задачи (каноническую) ЛП:

(4) min<c, x> R0 ={x; Ax=b, x≥0}

x∈R0

Задача (4)-невырожденная, т.е. невырожденна каждая угловая точка ∈R0. Итерационный шаг состоит в переходе от одной угловой точки х круговой точке х', при котором значение целевой функции убывает; <C, x'> < <C, x> x -угловая точка. Базис В образует, первые m столбцов матрицы А. Будем записывать матрицу А=[В,D], где В=[a1, a2, ., am].

D=[an+1, an+2, ., an]

xT=(xвТ, xдТ), CТ=(CвТ, CдТ)

хВ - базис компоненты, хд - в небазисные компоненты.

2) Выбор столбца для ввода в базис.

Известна угловая точка х: хв>0, хд=0, det(В)≠0, Вхв=в

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

ℷ k=(m+1,n)

0

где ℷ является к - й компонентой вектора х.

Если хв>0, то при малых ℷ>0; хk≥0, т.к. Ахk=в, то хk∈R○ при малых ℷ>0. Кроме того:

<C1 xk>=<C1 x>-ℷ[<Cв, B-1ak>-Ck]=<C, x>-ℷ∆k

∆к - определитель для любого к=1,n, причем при к=1,m;

∆к=<Cв, B-1ak>-Ck=<Cв, Cк>Cк=Cк-Cк=0

Окончательно; <C1 xк>=<C1x>-ℷ∆x (k=1,n)

3)Выбор столбца для ввода из базиса.

В зависимости от значков величины ∆к и (В-1ak); возникает 3 случая. _

a)Если для любого к=1,n будет ∆к=0, то точка х - оптимальная. _

б) Если найдется номер к≥m+1 такой, что ∆к>0 и В-1ak≤0, то множество R0 неограниченно и функция <С1х> неограниченна снизу на R0.

в) Пусть найдутся такие к≥m+1 и i≤m, что ∆к>0 и (В-1akа )>0.

4)Конечность метода.

хk - новая угловая точка, причем <C1k>=<C1x>-ℷ0 ∆k < <C1 x>. Из этого следует, что итерационный шаг симплексного метода состоит в таком переходе от базиса а1, а2, ., аs, аs+1, am к базису a1, a2, ., as-1, as+1, ., am, ak при котором целевая функция убывает, а значит, симплексный метод приводит к угловой точке х*, в которой достигает минимума за конечное число итераций.

Стр: 19 [ВЮЮ1]

Стр: 19 [ВЮЮ2]

Стр: 29 [ВЮЮ3]

Стр: 1 [ВЮЮ4]