Прикладная математика. шпоры по прикладной математике. 1. слау основные определения, каноническая форма записи слау

• Название: 1. слау основные определения, каноническая форма записи слау
• Анкор: Прикладная математика
• Дата: 18.08.2022
• Размер: 0.72 Mb.
• Имя файла: шпоры по прикладной математике.doc
• Тип: Документы; #648287
• страница: 1 из 5

1.СЛАУ:основные определения, каноническая форма записи СЛАУ.

Система k уравнений с n неизвестными имеет следующий вид:

a₁₁x₁+a₁₂x₂+…+a_1nx_n=b₁

a₂₁x₁+a₂₂x₂+…+a_2nx_n=b₂

………………………..

a_m1x₁+a_m2x₂+…+a_mnx_n=b_m

Решением СЛАУ наз. Такая система чисел к₁,к₂,…к_n, кот.при подстановке обращает каждое из уравнений системы в верное тождество. В этом случае,когда система имеет решение,она наз.совместной, в противном случае противоречивой или несовместной. Совместная система наз.определенной или неопределенной в зависимости от того, имеет ли она одно или несколько решений. Две СЛАУ с одинаковым числом неизвестных наз.эквивалентгыми или равносильными, если они имеют одни и те же решения, либо вообще не имеет решений. При этом число уравнений в равносильных системах можетбыть различным. Те преобразования, кот.переводят СЛАУ в эквивалентную ей систему наз.элементарными.

Основные задачи решения СЛАУ: 1)совместна она или нет; 2)если совместна, то каково число решений; 3)найти решение системы. После того как будут получены решения системы, либо будет доказана её несовместность, система будет приведена к следующему виду:

х₁+q_1,m+1*x_m+1+…+q_1n*х_n=h₁

х₂+q_2,m+1*x_m+1+…+q_2n*х_n=h<sub>2

.</sub> . . . . . . . . . . . . . .

х_m+q_m,m+1*x_m+1+…+q_mn*х_n=h_m

В этом случае говорят,что СЛАУ приведена к предпочитаемому или каноническому виду.

2.Элементарные преобразования СЛАУ, формулы исключения(вывод), правило прямоугольника.

Элементарными преобразованиями СЛАУ наз.преобразования след-х трех типов:перестановка местами двух любых уравнений системы; умножение(деление) обоих частей уравнения на одно и тоже число; прибавление к обеим частям уравнения соотв-х частей другого уравнения, умноженных(деленных) на постоянное число. Элементарные преобразования переводят данную СЛАУ в эквивалентную систему.Подвергая СЛАУ элемент.преобразованиям,можно исключить любую неизвестную из всех уравнений,кроме к-л одного уравнения.

Пусть имеется СЛАУ1,в кот.выбрано разрешающее уравнение,разрешающая переменная x_s и разр-й коэф-т при этой неизвестной a_rs (r-номер разр.ур-я,s-номер разр.неизвестной). Необходимо исключить разр-щую переменную x_s из всех уравнений кроме этого. Тогда коф-ты новых ур-й рассчитываются по след.формулам исключения: a^|_ij=a_ig-a_is/a_rs*a_rg

a^|_rj=a_rg/a_rs

для свободных членов: b^|_I=b_i-a_is/a_rs*b_r

b^|_r=b_r/a_rs

Сущ-т правило прямоугольника:

a_ij …… a_is a_is …….. b_i

a_{rj ……….} a_rs a_rs …….. b_r

Для того чтобы получить новый коэф-т a^|_ij нужно старый эл-т a_ij умпожить на разр-щий эл-т a_rs, вычесть произведение эл-тов на др.стороне прямоугольника и поделить на разр-щий эл-т a_rs: a^|_ij=(a_ig*a_rs-a_rj*a_is)/a_rs

b^|_I=(b_i*a_rs-a_is*b_r)/a_rs

3.Исследование и решение СЛАУ методом послежовательного исключения неизвестных Жордана,нахождение различных предпочитаемых эквивалентов данной СЛАУ и базисных решений, общего решения.

Суть метода сост в том, что за счёт элемен-х преобр-й, за конечное число шагов система произ-ся к так назыв-му, предпочит-му или каноническому виду, кот легко исслед-ся и решаются. Выбирается разрешающее ур-е, в кот выбир неизвестная,коэф-т при кот отличен от нуля (разреш-ая неизвестная), а коэф-т при ней назыв разрешающий коэф-т. Путём элем-х преобразований разреш-ая неизвестная искл-ся из всех урав-й системы кроме разрешающей. Берётся след ур-е и след разреш-ая перем-ая отличная от первой, далее путём элем-х преобр-й она искл-ся из всех ур-й системы кроме разрешающей и т.д. пример:

а₁₁х₁+а₁₂х₂+а_1nх_n=b_{1 –} разреш урав-е

а₁₁0 а_m1х₁-разреш перем-ая

нужно искл х₁ из всех ур-й кроме разрешающего. Нужно 1-е ур-е *-а₂₁/а₁₁=

-а₂₁х₁- а₁₂*а₂₁/а₁₁*х₂ -…- а₂₁*а_1n/а₁₁*х_n=-b₁*а₂₁/а₁₁ + 2 ур-е системы

В рез-те преобр-й возможны след.случаи:

1) в процессе реш-я появл равенства 0*х₁+0-х₂+…+0-х_n=b_i в_i0

при появл такого равенства пишем что сис-ма несовместна.

2) левая и правая части i ур-я обращ-ся в 0, т.е.0=0  данное ур-е явл линейной комбинацией ур-й вход-х в эту систему, в этом случ это ур-е исключается из всей системы

3) после того как все ур-я слау будут испол для искл неиз-х, либо будут получены решения системы, либо будет доказана её несовместимость,система будет приведена к след виду: х₁+q_1,m+1*x_m+1+…+q_1n*х_n=h₁

х₂+q_2,m+1*x_m+1+…+q_2n*х_n=h<sub>2

.</sub> . . . . . . . . . . . . . .

х_m+q_m,m+1*x_m+1+…+q_mn*х_n=h_m

в этом сл гов, что слау приведена к предпочитаемому или канонич-му виду. Те неиз-ые,кот входят в одно конкретное ур-е системы и не входят в ост-ые назыв базисными неизвестными, все остал-е неиз-ые назыв свободными. При этом кол-во базисныз неизв-х должно быть предпочитаемому или каноничн виду. Выражение базисных через свободные неиз-ые назыв общим решением слау:

х₁=h₁-q_1,m+1-x_m+1-…-q_m*x_n

х₂=h₂-q_2,m+1-x_m+1-…-q_2n*x_n

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

x_m=h_m-q_m,m+1-x_m+1-…-q_mn*x_n

Придавая свободным неизв какие-либо зн-я будем получать опред зн-я базисных неизв-х. Такие решения слау наз частными небазисными реш-ми. В том случае, если все свободные перем-е = 0, то полученное знач-е базисных перем-х в совм-ти с нулевыми свободными назыв базисным решением слау: х₁=h₁ x₂=h₂ x_m+1=0 и т.д. х_n=0

4.Преобразование СЛАУ с сохранением неотрицательности правых частей уравнений,нахождение различных базисных неотрицательных решений, правила выбора разр-щей неизвестной и разр-щего уравнения,их обоснование.

Если правые части всех уравнений полученных систем окаж неотриц-ми,то соотв базисные решения также будут неотрицательными.=>чтобы получить неотриц базисные решения СЛУ,надо научиться вести процесс исключения неиз-х так, чтобы свободные члены всех ур-й на всех этапах этого процесса оставались неотрицательными.Для этого следует руковод-ся след правилам: 1)если в СЛАУ им отриц свободные члены,то все такие ур-я необх *(-1); 2)в кач-ве разр-щей приним ту переменную,коэф-т при кот хотя бы в одном ур-нии системы положителен; 3)для нахождения разрешающего уравнения находят тип отношений столбца свободных членов к положительным эл-там разр-щего солбца,в этом сл k-ое ур-е будет разр-щим

min(b_i/a_ij>o)=b_k/a_ij

Если хотя бы в одном из ур-й системы свободный член положителен,а все коэф-ты при неизв-х<0,то система неотрицательных реш-й не имеет.Преобразования системы в соотв с этими правилами наз симплекс преоб-ниями системы. Если указанный min достигается для неск-х ур-й системы,то такая система наз вырожденной. Необх-м условием вырожденной системы явл то,что свободный член хотя бы одного ур-я системы=0.
5.Многомерные векторы и действия над ними.n-мерное векторное пространство.

Сов-ть n чисел а₁,а₂,…,а_n, заданных в определенном порядке,наз n-мерным вектором.Числа a_i наз компонентами или координатами вектора,число n-его размерностью.Обозначают вектор след образом: а(а₁,а₂,…,а_n) А(а₁,а₂,…,а_n).

∑ векторов a и b наз вектор а+b=( а₁+b₁,а₂+b₂,…,а_n+b_n) каждая компонента кот =сумме соотв-х компонент слагаемых векторов. Произведением вектора а на число λ наз вектор λа= (λа₁, λа₂,…, λа_n) каждая компонента кот равна произведению соотв компоненты вектора а на это число. Скалярным произведением двух векторов одной размерности a и b наз число,равное сумме попарных произведений соотв компонент векторов a и b. Скалярное произведение

(a,b)=a₁b₁+a₂b₂+…a_nb_n=∑a_ib_i.

Множество R эл-тов a,b,c,…наз линейным пространством,если:1)имеется правило,кот позволяет построить для кажд двух эл-тов a и b из R третий эл-т из R,называемый суммой эл-в a и b (a+b); 2) имеется правило,кот позволяет построить для кажд эл-та a из R и любого действительного числа λ эл-т а^| из R,наз-мый произведением эл-та а на число λ и обозначаемый λа; 3)сущ нулевой эл-т обозначаемый 0,обладающий свойством а+0=а, для каждого эл-та а сущ эл-т –а и облад-й св-вом а+(-а)=0; 4)правила образования суммы эл-в и произведения эл-в на число удовлетворяют условиям a+b=b+a, (a+b)+c=a+(b+c), λ(μa)=(μλ)a,1*a=a, 0*a=0*λ=0, (μ+λ)a=λa+ μa, λ(a+b)λa+λb.Множество всех n-мерных векторов-упорядоченных систем действительных чисел-образует линейное пространство в смысле данного определения.Его часто наз арифметическим n-мерным пространством.

6.Матрицы, их классификация. Сложение матриц и умножение матрицы на число,умножение матрицы на матрицу,свойства.

Матрицей размера mxn наз таблица чисел, кот расположена в m-строках и n-столбцах

a₁₁ а₁₂ …а_1n

А= a₂₁ а₂₂ …а_2n или кратко А=(a_ij)

…………..

a_m1 а_m2 …а_mn

Если т= п, то матрица называется квадратной матрицей n-го по­рядка. Кв. матрица наз треугольной, если все ее элемен­ты, стоящие над или под главной диагональю, равны нулю. Кв. матрица называется диагональной, если все ее эл-ты, стоящие на главной диагонали, отличны от нуля, а остальные равны нулю. Диагональная матрица наз единичной, если а_ii=1, i=1,...,п.Транспонированной матрицей наз матрица, строки кот.заменены столбцами.Единичную матрицу принято обозначать буквой Е:




.

Суммой двух матриц одного размера называется матрица того же размера, каждый элемент которой равен сумме соответствующих эле­ментов матриц-слагаемых. Так, если А - || а_ij|| и В=|| b_ij||— матрицы размера т х п, то их суммой является матрица С = А + В, такая, что c_ij=a_ij+b_ij. Произведением матрицы А размера т х п на число А, называется матрица Dтого же размера, у которой d_ij=a_ijλ..Для транспонированных матриц справедли­вы следующие соотношения: 1)(А')' = A;

2)(АВ)' = В'А' ; 3) (А + В)' = А' + В'.

Произведением матрицы А размера т х п на матрицу В размера nх kназ матрица С размера т х k, эл-ты кот с_ij равны скалярному произведению i-й строки матрицы А на_j-й столбец мат­рицы В, т.е.



Произведение матриц обозначается С = АВ. Скалярное произве­дение векторов а и b можно представить как произведение вектора-строки (матрицы-строки) а на вектор-столбец (матрицу-столбец) b': (a, b) = ab'.Для операции произведения матриц справед­ливы следующие свойства: 1)A(BС) = (АВ)С; 2)(А + В)С = АС + ВС;
3)A(B+С)=AB+AC; 4) λАВ) = (λА)В.

7.Системы линейных алгебраических неравенств

Система т алгебраических неравенств первой степени с п неизвест­ными может быть записана в виде



Совокупность п чисел a₁,а.₂,,...,а_n, взятых в определенном поряд­ке, называется решением системы неравенств (1.2.30), если при под­становке этих чисел на место соответствующих неизвестных неравен­ства не нарушатся. Решение (<x_l5 a₂,..., а_/() системы неравенств назы­вается неотрицательным, если все а > 0. В этом случае,когда система имеет решение,она наз.совместной, в противном случае противоречивой или несовместной. Совместная система наз определенной или неопределенной в зависимости от того, имеет ли она одно или несколько решений. Две СЛАН с одинаковым числом неизвестных наз.эквивалентгыми или равносильными, если они имеют одни и те же решения, либо вообще не имеет решений. СЛАН часто преобразуют в СЛАУ путем введения дополнительных неотрицательных переменных (неизвестных) х_п+1 , x_n+2 ,, х_n+m:



Исследование и решение системы т линейных неравенств с п неизвестными сводится к исследованию и решению соответствующей системы m линейных уравнений с п + т неизвестными. В частности, нахождение неотрица­тельных решений системы линейных неравенств (1.2.30) связано с по­иском неотрицательных решений системы линейных уравнений (1.2.31).Векторная форма записи СЛАУ: a₁x₁+a₂x₂+…+a_nx_n=b

Матричная: A*x=b

8.Обратная матрица: определение, свойства, ур-е существования.

Пусть задана кв. матрица А.Если сущ-т матрица В, такая что А*В=Е,то гов что матрица В явл обратной по отношению к мат А: В=А^-1, А*А^-1=Е.

Свойства: 1)Обратная и исходная матрицы перестановочны и матрица,обратная обратной, совпадает с исходной:

А*А^-1=А^-1*А=Е.

2)Единственность матрицы:если для данной матрицы обратная мат сущ-т,то она только одна.

Как выяснить явл ли кв. матрица обратной? Пусть исход матрица А имеет вид: а₁₁ а₁₂ а₁₃

А= а₂₁ а₂₂ а₂₃

а₃₁ а₃₂ а₃₃

Предпол что имеется какая-то мат В, В=(х_ij)=А^-1,кот явл обратной по отношению к исходной мат-це А. Тогда должно выполняться:

а₁₁ а₁₂ .. а_1n x₁₁ x₁₂ .. x_1n 10….0

а₂₁ а₂₂ .. а_2n * x₂₁ x₂₂ .. x_2n = 010...0

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

а₃₁ а₃₂ .. а_3n x_m1 x_m2 .. x_mn 000001

Это матричное ур-е можно переписать в виде системы n² линейных ур-й с n² неизвестными.

9.Обращение матрицы методом Жордана.

Как известно, метод Жордана не требует предварительного иссле­дования системы уравнений на совместность — ее исследование и решение проводятся одновременно. Достоинством явл и то что все коэф-ты в соотв-х СЛАУ явл одинаковыми. Выпишем матрицу А и припи­шем к ней столбцы свободных членов всех n подсистем:



Как обычно, будем подвергать элементарным преобразованиям систему строк этой вспомогательной матрицы. Приписанные столб­цы свободных членов подсистем уравнений образуют единичную мат­рицу того же порядка, что и данная матрица А. В случае совместнос­ти системы уравнений на некотором этапе преобразований на месте матрицы А получится единичная матрица, и тогда каждый столбец приписанной матрицы будет представлять решение соотв-щей подсистемы ур-й, т.е. на месте этой матрицы появит­ся обратная матрица. Схема обращения невырожденной матрицы А кратко может быть записана в виде (А,Е)->(Е,А^-1).Если на некотором этапе процесса преобразований вспомогатель­ной матрицы (1.2.39) в матрице А появится строка нулей, то это будет свидетельствовать о вырожденности матрицы А и, следовательно, о ее необратимости.

10 Обращенный базис СЛАУ. Приведение СЛАУ к предпочитаемому виду с помощью обращенного базиса.

Дана система т линейных алгебраических уравнений с п неизвест­ными (т < п):



Исследуем ее, вычислив ранги матрицы СЛАУ и расширенной матрицы с помощью миноров. Предположим, что система оказалась совместной, все уравнения линейно зависимы, и пусть, для опреде­ленности, ненулевой минор М_тнаивысшего порядка m (базисный минор) порождается подматрицей В, составленной из коэффициен­тов при первых т неизвестных. Матрицу В назовем базисной. Найдем для нее обратную матрицу B^-1:

a₁₁….а_1mu₁₁….u_1m

А= ……… ,B^-1= ……… , M_m=|B|

a_m1….a_mmu_m1….u_mm

Матрицу В^-1часто называют обращенным базисом. В матричной форме система алгебраических ур-й (1.2.43) записывается следующим образом:



где (слева проставлены в скобках размеры соотв-х матриц):

(т х п) А — матрица коэффициентов;

(n х 1) х — вектор-столбец неизвестных;

(mх1)b— вектор-столбец правых частей ур-й.

Разобьем вектор х на вектор базисных переменных х_B(первые т переменных) и вектор свободных переменных x_R(остальные п-т перем-х).Тогда матрица A соотв-щим образом разделит­ся на подматрицы В (коэффициенты при базисных переменных) и R(коэффициенты при свободных переменных). При таком разделении матричное уравнение (1.2.45) примет вид

Bx_B+Rx_R=b. (1.2.46)

Поскольку базисная матрица В невырожденна,то обратная мат­рица В^-1существует. Умножим соотношение (1.2.46) слева на В^-1, тогда с учетом того, что B^-1B = Е, получим Откуда выразим базисные неизвестные через свободные неизвестные и правые части СЛАУ:

Матричное соотношение (1.2.47) в развернутой алгебраической форме записывают след образом:

х₁+q_1,m+1*x_m+1+…+q_1n*х_n=h₁

х₂+q_2,m+1*x_m+1+…+q_2n*х_n=h<sub>2

.</sub> . . . . . . . . . . . . . .

х_m+q_m,m+1*x_m+1+…+q_mn*х_n=h_m

Мы пришли к предпочитаемому эквиваленту исходной СЛАУ. Ба­зисными оказались те первые т неизвестных, из коэффициентов при которых был составлен ненулевой минор наивысшего порядка при исследовании системы.Т.о., матрица Gсистемы (1.2.48) и матрица А системы (1.2.1), а также матрицы-столбцы hи bих правых частей связаны со­отношениями: G=B^-1A, h=B^-1b

11. Задача оптимального производственного планирования и ее математическая модель.

П редположим, что предприятие выпускает n видов продукции при использовании m видов ресурсов. Известны: технологическая матрица расходов iго вида ресурса на единицу jго вида продукции – (а_ij), где i= ; j= . Матрица запаса ресурсов B =
Известны прибыль, полученная предприятием от производства и реализации продукции jго вида. Требуется составить план производства продукции:

x = (x₁, x₂, x₃,...x_n), при котором предприятие получит наибольшую прибыль. Суммарная

прибыль предприятия c_j x_j
а ₁₁x₁ + a₁₂x₂ + … a_1nx_n ≤ b₁

а₂₁x₁ + a₂₂x₂ + … a_2nx_n ≤ b₂

. . . . .

а_m1x₁ + a_m2x₂ + … a_mnx_n ≤ b_m.
где b_i-запас ресурса iго вида,

x₁≥0, x₂≥0, ...x_n≥0.

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

Найти неотрицательные значения переменных x_j, j=1,n, при которых линейная форма

z = c_j x_j → max. Если переменная x_j удовлетворяет следующим ограничениям:




a_ijx_j ≤ b_i

x_j≥ 0; i= ; j= .
12. Общая задача математического прог-раммирования.

Задачу линейного программирования нередко

формулируют как задачу минимизации или макси-мизации линейной формы L=c₁x₁+c₂x₂+...c_nx_n (1) при ограничениях x₁≥0, x₂≥0, ...x_n≥0 и

∑ a_ijx_j≤b_i, i=1,2,...m₁,

∑ a_ijx_j=b_i, i= m₁+1, m₁+2,...m₂,

∑ a_ijx_j≥b_i, i= m₂+1, m₂+2,...m.

Такую запись называют общей задачей линейного программирования.

Обозначим через А матрицу системы линейных уравнений:




а₁₁x₁ + a₁₂x₂ + … a_1nx_n = b₁

а₂₁x₁ + a₂₂x₂ + … a_2nx_n = b₂ (2)

. . . . .

а_m1x₁ + a_m2x₂ + … a_mnx_n = b_m.
Через X и B – матрицы-столбцы (векторы) неизвестных и свободных членов:
а₁₁ … а_1n x₁ b₁

А = ... ... , X= ... , B= ...

a_m1 ... a_mn x_n b_m

а также введем в рассмотрение n-мерный вектор C = (с₁ … с_n), компонентами которого служат коэффициенты линейной формы (1), и n-мерный нуль-вектор 0(0, 0, …, 0). Тогда линейную форму (1) можно рассматривать как скалярное произведение L=CX (3), систему линейных уравнений (2) заменить одним матричным уравнением AX=B (4), а условия x₁≥0, x₂≥0, ...x_n≥0 записать в виде X≥0 (5). Поэтому часто основную задачу линей-ного программирования кратко записывают как задачу минимизации линейной формы (3) при линейных ограничениях (4) и (5).

13. Различные формулировки задачи линей-ного программирования, функция цели, до-пустимые и оптимальные решения. Основная задача ЛП, ее векторная и матричная формы записи.

Многие проблемы, возникающие в экономических исследованиях, планировании и управлении, будучи сформулированными математически, представляют собой задчи, в которых необходимо решить с-му линейных алгебраических уравнений или неравенств и среди всех неотрицательных решений найти то решение, при котором линейная однородная функция принимает наибольшее или наименьшее значение. Изучение методов исследования и решения математических задач указанного типа составляет содержание раздела математики, кот. Принято называть линейным программированием.

О сновную задачу ЛП сформулируем следующим образом: даны система m линейных уравнений с n неизвестными

а₁₁x₁ + a₁₂x₂ + … a_1nx_n = b₁

а₂₁x₁ + a₂₂x₂ + … a_2nx_n = b₂ (1)

. . . . .

а_m1x₁ + a_m2x₂ + … a_mnx_n = b_m.

Где неизвестные могут принимать только неотрицательные значения x₁≥0, x₂≥0, ...x_n≥0 (2), и линейная однородная ф-я от тех же переменных L=c₁x₁+c₂x₂+...c_nx_n (3). Требуется среди всех решений системы уравнений (1) найти такое неотрицательное решение, при котором линейная форма (3) принимает наименьшее возможное значение.

Любое неотрицательное значение системы называют допустимым, а допустимое решение, при котором целевая ф-я (3) принимает наименьшее значение – оптимальным решением задачи ЛП (1)-(3).

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