Xreferat.com » Рефераты по математике » Математические основы теории систем

Математические основы теории систем

уменьшение числа шагов можно получить, если воспользоваться алгоритмом Ньютона, при этом представлении 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

(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 R0 ={x; Ax=b, x≥0}

x∈R0

Задача (4)-невырожденная, т.е. невырожденна каждая угловая точка ∈R0. Итерационный шаг состоит в переходе от одной угловой точки х круговой точке х', при котором значение целевой функции убывает; < 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. Кроме того:

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

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

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

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

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: