Шпаргалка по "Математике"

Они расположены в вершинах прямоугольника. Его диагональ, на которой  стоит разреш. Эл-т aks и преобразуемый aij – главная. Другая диагонпль – побочная. Из (14) следует, что преобразуемы эл-т bij равен разности произведений элементов, расположенных на главной и побочной диагоналях, деленные на разреш. Эл-т.

Замечание:из (14) следует, что если в разреш. Строке некоторый эл-т akj=0,

То bij= aij, т.е. эл-ты столбца, в котором расположен 0й эл-т разреш. строки,  остается после шага жордан. Исключения без изменений.если в разреш. Столбце имеется 0й эл-т, то соотв ему строка остается на дан. Шаге неизменной.

 

4.Решение систем  линейных уравнений

Рассмотрим систему m линейных уравнений с n неизвестными.      (1)       Пусть ранг матрицы коэффициентов a_ij (i=1,m ;j=1,n) = r ;   rang(a_ij) = r. Запишем систему в виде 0 равенств:

Полученную систему запишем  в Жорданову таблицу (таблица 1)

	1	-x1	…..	-xn
0=	a10	a11	…..	a1n
…..	…..	…..	…..
0=	am0	am1	…..	amn

Над этой таблицей можно  провести r шагов последовательных Жордановых исключений. В результате будет получена  след. Таблица 2 :

	1	0	….	0	-xr+1	….	-xn
x1=	b10	b11	….	b1r	b1,r+1	….	b1n
….	….	….	….	….	….	….	….
xr=	br0	br1	….	brr	br,r+1	….	brn
0=	br+1,0	br+1,1	….	br+1,r	0	….	0
….	….	….	….	….	….	….	….
0=	bm0	bm1	….	bm,r	0	….	0

Эта таблица отображает систему (1) и эта система совместна  тогда и только тогда, когда для  некоторой совокупности значений   x₁, x₂…. x_n выполнены одновременно все равенства (1). Это возможно если в таблице 2 эти элементы b_r+1,0=….=b_m0=0.Если хотя бы один из свободных членов b_r+1,0….b_m0 отличен от 0, то система несовместна.В случае совместности системы, таблица 2 получ. Общее решение системы:(2).    Придавая переменным  x_r+1….x_n произв. значения: x_r+1=α_r+1….. x_n=α_n    вычисляют соответственно значения оставшихся неизвестных. Система (2) будет выглядеть: Таким образом получено частное решение системы (1).Так можно определить бесчисленное множество решений системы (1).  В случае когда r=n через n шагов Жордановых исключений все переменные x₁, x₂…. x_nокажутся в левом заглавном столбце таблицы 2, а их место на верху таблицы займут нули, поэтому система (1) будет иметь единственной решение :x₁=b₁₀……x_n=b_n0. 

 

 

 

Вывод. Для решения СЛУ ее записывают в форме Жордановой таблицы и проделывают возможное число шагов Жордановых исключений, вычеркивая после каждого шага разрешающий столбец и строки, если они целиком состоят из нулевых элементов. Если в ходе исключения появится строка все элементы которой кроме свободного члена =0, то данная система несовместна. В противном случае система совместна, при этом она имеет бесчисленное множество решений. Если в верхней заглавной строке последней Жордановой таблицы останется хотя бы одна переменная и система имеет единственное решение если все переменные окажутся в левом заглавном столбце.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

5.Базисные решения  системы линейных уравнений

Рассмотрим m-мерные векторы координаты которых = коэффициенту при неизвестных и свободных членах уравнения системы(1).  ….,   С помощь таких столбцов систему (1)……….

По последнему соотношению  заключаем, что решение системы  уравнений (1) сводится к нахождению коэффициента разложения x₁….x_n  ,вектора a₀ по векторам a₁….. a_n. Эти коэффициенты находятся методом Жордановых исключений. В результате Жорд. искл. Расширенная матрица СЛУ (1) будет выглядеть:

Матрица системы уравнений (1) примет вид:

Так обратные векторы a₁….a_r преобразуются в единичные. Эти векторы являются линейными независимыми и составляют базис системы исходных векторов.   Систему rуравнений в которой столбцы коэффициентов при r неизвестных являются единичными векторами будем называть приведенной к единичному базису.    Переменные x₁, …. x_r которые соответствуют векторам a₁….a_r - базисные. Переменные x_r+1, …. x_n которые соответствуют векторам a_r+1….a_n – называют свободными, им можно придавать свободные значения.

Если общее решение  системы (1) свободным переменным придать нулевые значения, то получится частное решение      В векторной записи: (b₁₀, ……b_r0 , 0…,0)    - базисное решение.    Замечание! Из данной системы n векторов можно выбрать макс. C_n^r:   

Вывод. Максимально возможное число базисных решений опред. C_n^r. В действительности их решений может оказаться меньше т.к. некоторые группы по r векторов могут быть меньше зависимыми и следовательно не будут образовывать базиса и соотв. этим векторам переменные. Чтобы определить базисные решения системы уравнений нужно преобразовать систему последовательно переходя от одного ед. базиса к другому с помощью жорд.искл.

 

 

 

 

 

 

6.Способ отыскания  опорных решений

Т.к. в экономических задачах  отрицательные значения переменных практически не имеют смысла, следует  искать не отрицательные решения  системы линейных уравнений. В МП их называют опорными решениями или  опорным планом.

Предположим, что в табл 1 все элементы столбца свободных членов не отрицательны. Основная задача: как сохранить не отрицательность свободных членов в процессе жорд.искл.

	1	-x1	…..	-xn
0=	a10	a11	…..	a1n
…..	…..	…..	…..
0=	am0	am1	…..	amn

Первый шаг жорд.искл. проводиться с разрешающим элементом a_ks после выполнения шага свободный член в разрешающей строке a_k0/a_ks он будет не отрицательным если a_ks>0 (т.к. разрешающий элемент положительный по предположению, то a_k0>0)- первое требование к разрешающему элементу.

	1	……..	-xs	…….
…………..	…………..	………….	…………..	…………..
0=	ai0		ais
…………..	…………….	……………	……………….	……………
0=	ak0		aks
…………….	……………..	……………..	……………..	………………..

                                                                                                                   (Табл 2)

Пусть отношение a_k0/a_ks выполняется, после шага жорд.искл. свободный член произвольной i_той строки:

 

Оно будет не отрицательным  если:     ₍₁₎  .  Т.к. a_i0>=0 , a_k0>=0 , a_ks>0 ,то неравенство (1) можно переписать в виде:                              - второе требование к разрешающему элементу, а именно: отношение свободного члена разрешающей стрки к разрешающему элементу должно удовлетворять условию минимальности, т.е. оно должно быть наименьшим из всех отношений соотв. членов к соотв. положительным элементам разрешающей строки.

Если этому требованию удовлетворяет сразу несколько  отношений, то разрешающий элемент можно взять в любой строке соотв. одному из этих соотношений. 

Вывод. Для отыскания опорного решения СЛАУ ее нужно представить в виде жорд.таблицы так, чтобы все свободные члены были не отрицательны, а затем произвести возможное число шагов жорд.искл. выбирая разрешающие элементы среди положительных чисел основной части таблицы по наименьшему отношению свободных членов к соотв. Положительным элементам столбца выбранного разрешающим. Искомое опорное решение найдется приравниванием верхних св. переменных к нулю, а базисных (боковых) к свободным членам. Если в ходе жорд.искл.встретится ноль строка в которой все элементы не положительные, а свободный член не отрицательный, то данная система не имеет не отрицательных (опорных) решений хотя и является совместной.

 

7. Эквивалентные  преобразования системы линейных  уравнений и неравенств 

Решением линейного неравенства  с двумя неизвестными  a₁x₁+a₂x_2a

Решением является бесконечное  множество решений состоящих  из пар значений этих неизвестных ,удовлетворяющих неравенству a₁x₁+a₂x_2a

Чтобы найти искомую полуплоскость, нужно найти граниченую прямую ,нужно взять точку ,лежащую по ту или другую сторону и определить какому из неравенств удовлетворяет ее координата : a₁x₁+a₂x₂a   или   a₁x₁+a₂x_2a

Теорема:

Всякому решению α₁,α_2…..,α_n

a₁x₁+….. а_nx_na,соответствует определённое решение уравнения a₁x₁+a₂x₂+….а_nx_n+x_n+1=а

В котором x_n+10

Верна и обратна теорема :

На основании прямой теоремы ,верно, что неравенство a₁x₁+….. а_nx_na  эквивалентно  уравнению a₁x₁+a₂x₂+….а_nx_n+x_n+1=а и неравенству x_n+10

Аналогично, неравенству :

a₁x₁+….. а_nx_na

a₁x₁+a₂x₂+…. а_nx_n-x_n+1=а

x_n+10

Переменную  x_n+1назовём дополнительной (балансовой) 
На основании теоремы :

а₁₁x₁+….. а_nx_na10

…………………………

a_m1x₁+…..+ a_mnx_nam0

можно заменить эквивалентной  системой уравнения :

а₁₁x₁+….. +а_1nx_nxn+1=a₁₀

…………………………………….

a_m1 x₁+…..+ a_mnx_n+ x _n+m=a_m0

где x_{n+10 ,}  x_n+m0

Эта система эквивалентна в системе ,что всякому решению α₁, _…..,α_nсистем

 

 

а₁₁x₁+….. а_nx_na10

…………………………

a_m1x₁+…..+ a_mnx_nam0 соответствует определённое решение α₁, _…..,α_{n  ,}α_n+1…α_n+m системы

а₁₁x₁+….. +а_1nx_nxn+1=a₁₀

…………………………………….

a_m1 x₁+…..+ a_mnx_n+ x _n+m=a_m0,      причёмx_{n+1………..}x_n+m,удовлетворяют условию

неотрицательностиx_{n+10 ,}  x_n+m0

 

 

 

 

8. различные формы  записи задач линейного программирования. Свойство решения задач линейного  программирования 

Общей задачей Л.П ,заданных в произвольной форме записи называется задача ,в которой требуется максимизировать или минимизировать общую функцию

 

F(x₁……x_n)=    -целевая функция

При ограничениях :

a_ijx_j ≤ a_i0                                 (i=1,s)

a_ijx_j ≤ a_i0 (i=s+1,m)

Задачи Л.П заданные в симметричной форме записи,называют задачу ,в которой требуется найти maxF(x₁……x_n)=       при a_ijx_j ≤ a_i0                  (i=1,s) и при Xj≥ (j=1,n)

Задачи Л.П в канонической форме назыв. задачу ,в которой требуется найти F(x₁……x_n)=    при условии a_ijx_j ≤ a_i0                  (i=s+1,m)   ,где s=0 и выполн. условие Xj≥ (j=1,n)

X=(X_1…….x_n) удовлетворяющих  ограничении задачи Л.П, назыв. ее планом

X^*=(X₁^*….. X_n^*),который достав. Max/min функции F(x₁……x_n)=  ,называется оптимальным.