1. Ранг матрицы r(a) – это наивысший порядок отличных от 0 миноров этой матрицы

Ранг матрицы тесно связан с понятием линейной независимости строк (столбцов) матрицы.

Методы поиска ранга матрицы: метод окаймляющих миноров и метод элементарных преобразований

Метод окаймляющих миноров

Пусть некоторый минор матрицы k-ого порядка М_k0, тогда ранг этой матрицы по меньшей мере равен k, т.е. r(A)  k . Рассмотрим все окаймляющие (содержащие в себе минор М_k) миноры k+1 порядка. Если все они равны 0, то значит ранг матрицы равен k, но если найдётся хотя бы один M_k+10, тогда процедура повторяется снова

Метод элементарных преобразований

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

Св-ва ранга

1) 0≤ r(A)  min {m,n}

2) r(AВ)  min {r(A) r(В) }

3) r(A) = r(A^T)= r(AА^т)

4) r(A+В) ≤ r(A) + r(В)

5) ранг произведений некоторой матрицы А слева или справа на невырожденную матрицу подходящего размера равен рангу исходной матрицы. r(AВ)= r(СA) , │В│≠ 0, │С│≠ 0

2. Метод подстановки в решении ЗНЛП с ограничениями-равенствами

Метод применяется для решения задач вида:

f(x)max(min) (1)

x_i=_i(x_m+1,x_m+2,…x_n), i=1,m (2)

Для решения задачи (1)-(2) производится подстановка выражений (2) в целевую функцию, после чего возникает задача без ограничений.

f(x)=f(₁(x_m+1,…x_n), ₂(x_m+1,…x_n),… _m(x_m+1,…x_n) x_m+1,x_m+2,…x_n)=ψ(x_m+1…x_n)max(min) (3)

В итоге задача поиска экстремума функции f(x) с ограничениями свелась к задаче поиска экстремума функции без ограничений. Эту задачу можно решить классическим методом и получить x^*_m+1, x^*_m+2, …, x^*_n

Подстановка этих значений в (2) даёт искомое значение для x₁^*, x₂^*, … , x_m^*

БИЛЕТ 49

1. Графический метод решения ЗЛП

Применяется для решения задач малой размерности, когда число перем.-арг. Цел. Ф-ии ≤ 3. В основе метода лежит факт, что град. ф-ции ортогонален гиперплоскости во всех точках кот. целев. ф-ция принимает одинаков. значения. Рассмотрим гиперплоскость П_β, представляющую собой мн-во уровня _β целевой ф-ии f(x)=c^tx:

П_β = {xЄRⁿ : c^тx=β}

Пусть Z-направл отрезок, соедин. т. х и у из гипер-ти П_β. Из усл. след., что z=y-x. Рассм. скаляр. произ-ие град f(x) от целевой ф-ии f(x)= c^tx=c1x1+…+cnxn, и вектора z, лежащего в гиперплоскости П_β, имеем <градf(x),z >=град трансf(x)z=(c1,…cn)*(z1,…zn)=c1z1+….+cnzn=c^tz=c^t (y-x)= c^ty- c^tx=0 (c^ty= c^tx= _β, т к x и yЄ П_β). Поскольку скалярной произведение =0, то это означает ортоганальность П_β и град f(x).

______________________________________________________________

Схем реализ. графич. метода:

Шаг 1: графич. способом строится обл. огр. D ЗЛП.

Шаг 2: строится направляющий вектор с = градf, как направленный отрезок соединяющий точку начала координат с точкой с.

Шаг 3: через любую точку области D проводится плоскость(прямая), ортогональная вектору с.

Шаг 4: построенная на шаге 3 плоскость перемещается в направлении вектора с параллельно самой себе до точки последнего соприкосновения перемещаемой плоскости (прямой) с областью D. Точка отрыва определяет оптимальный план задачи.

Шаг 5: Устанавливаютя точные значения компонент оптим плана для чего решантся система уравнений, определяющих те прямые в рез-те пересечения которых возникает точка оптимального плана.

2. Двойственные ЗЛП.

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

Прямая ЗЛП: Двойственная ЗЛП:

f(x) = c^тx → max(1) g(y) = b^тy → min(3)

Ax ≤ b (2) A^тy ≥ c(4)

x ≥ 0 y ≥ 0

c, x Є Rⁿ, b Є R^m b, y Є R^m, c Є Rⁿ

Эти задачи образуют двойственную пару ЗЛП.

БИЛЕТ 50

1. Понятие вектор-функции и матрицы Якоби

Функция g(x) наз-ся m-мерной вектор-ф-ей, если она представляет собой m-мерный вектор, компоненты которого суть вещественные ф-ии ,т.е.

g^T(x)=(g₁(x),g₂(x),…g_m(x)).

М-цей Якоби Rg(x) m-мерной вектор-функции g(x) наз-ся матрица р-ра m×n, элементы rij(x) которой определяются формулами:

r_ij(x)=g_i(x)/x_j i=1,m j=1,n

2. Двойственные ЗЛП.

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

Прямая ЗЛП: Двойственная ЗЛП:

f(x) = c^тx → max(1) g(y) = b^тy → min(3)

Ax ≤ b (2) A^тy ≥ c(4)

x ≥ 0 y ≥ 0

c, x Є Rⁿ, b Є R^m b, y Є R^m, c Є Rⁿ

Эти задачи образуют двойственную пару ЗЛП.

Теорема о представлении оптимального плана прямой ЗЛП. Пусть оптимальный план прямой ЗЛП (14.10)-(14.11) определяется базисными переменными (все свободные равны нулю). Тогда справедливо соотношение

(14.12)

где матрица, составленная из векторов стоящих при базисных переменных в исходной системе ограничений (14.11).

Теорема о представлении оптимального плана двойственной ЗЛП. Пусть прямая ЗЛП имеет оптимальный план . Тогда оптимальный план двойственной ЗЛП определяется по формуле

(14.15)

где та же матрица, что и в (14.12), а вектор, составленный из коэффициентов при базисных переменных в целевой функции прямой ЗЛП