Главная страница

Линал экзамен 1курс(2). Линейное программирование 34. Предмет лп. Матем модель эк зад


Скачать 0.51 Mb.
НазваниеЛинейное программирование 34. Предмет лп. Матем модель эк зад
АнкорЛинал экзамен 1курс(2).doc
Дата23.04.2018
Размер0.51 Mb.
Формат файлаdoc
Имя файлаЛинал экзамен 1курс(2).doc
ТипДокументы
#18417
КатегорияМатематика

Подборка по базе: Тема 1. Предмет статистики.docx, Информатика и программирование.docx, Основные понятия предмета.docx, 1-тема. Введение к предмету ЭЛЕКТРОНИКА.pptx, 1 Предмет фиософии, основные характеристики философии. структура, 1 Предмет психология.docx, Практическое задание по предмету Социодинамика культуры.docx, Тестовые задания по предмету «Физиологическое акушерство».pdf, Бланк протокола осмотра предметов.doc, Тесты по предмету.docx




Линейное программирование

34. Предмет ЛП. Матем модель эк зад

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

Найти экстремум целевой ф-ции задачи

Z(x)=f(x1, x2,…, xn)→max(min)

и соответствующие ему переменные, если они удовлетворяют системе ограничений

φi1, х2,…, хn) = b (i=1,2…l)

φi (х1, х2,…, хn) > < (или равно)0 (i=e+1, e+2 … m)
Z(x)=c1x1+c2x2+…+cnxn → max (min)

a11x1+a12x2+…+a1nxn=b1

a21x1+a22x2+…+a2nxn=b2

………………………………

am1x1+am2x2+…+amnxn=bm

xi ≥ 0

35. Общая задача линейного программ-ия

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

Построение экономико-математической модели состоит из следующих этапов:

1)выбор переменных задач

2)составление системы ограничений

3)построение целевой функции

Переменными задачами наз величины х1, х2,…, хn, которые полностью характеризуют экономический процесс. Х=(х1,…,хn )

Х – переменные задачи

Система ограничений включ в себя систему ур-ний и неравенств, которым удовлетворяют переменные задачи и которые следуют из ограниченности ресурсов или других условий.

Целевой ф-цией наз ф-цию переменных задач, которая характеризует качество выполненной задачи, и экстремум которой надо найти (должно удовл системе ограничений)

Если целевая ф-я и сист ограничений линейны, то задача матем программ наз зад лин программ

Допустимым решением(планом) задачи лин прогр-вания наз любой n-мерный в-р, удовлетворяющий системе ограничений и условиям неотрицат.

Множество допустимых решений(планов) задачи образуют область определения допустимых решений(ОДР).

Оптимальным решением(планом) задачи лин прогр-ния наз такое допустимое решение, при котором целевая ф-ция достигает экстремума.
36. Мат.модели эк.задач.

1) задача исп-я ресурсов;

b – запасы ресурсов, aij – расход каждого i-ого вида ресурса на изготовление единицы j-ой продукции, сj – прибыль

Z(x)=c1x1+c2x2+…+cnxn → max

a11x1+a12x2+…+a1nxn≤b1

a21x1+a22x2+…+a2nxn≤b2

………………………………

am1x1+am2x2+…+amnxn≤bm

xi ≥ 0

2) задача о составлении рациона питания;

b- животные должны получать ежедневно не менее b, aij – содержание iого пит вещества в единице jого вида корма, cj – стоимость единицы jого вида корма.

Z(x)=c1x1+c2x2+…+cnxn → min

a11x1+a12x2+…+a1nxn≥b1

a21x1+a22x2+…+a2nxn≥b2

………………………………

am1x1+am2x2+…+amnxn≥bm

xi ≥ 0
37. Каноническая форма линейного прогр-ния

Задача лин прогр-ния наз канонической, если все ограничения есть уравнения, а переменные неотрицательны.

Различные формы записи задач лин прогр-ния:

1)Координатная форма записи задач:

Z(x)=c1x1+c2x2+…+cnxn → max (min)

a11x1+a12x2+…+a1nxn=b1

a21x1+a22x2+…+a2nxn=b2

…………………………

am1x1+am2x2+…+amnxn=bm

xi ≥ 0

Или:

Z(x)=Σcixi → max(min)

Σ aijxj=bi

xj≥0

2)Векторная форма записи задач:

Х=(х1, х2,…хn)

C=(c1, c2,…cn)

a11 b1

A1 = a21 ; B = b2

… …

am1 bm
Z(x) = C*X → max (min)

A1x1+A2x2+...+Anxn=B

X ≥ 0
3) Матричная форма записи:

a11…a1n

A= ………

am1…amn

Z(x) = C*X → max (min)

A*X=B

X ≥ 0

38. Приведение общей задачи ЛП к канон.форме:

(1) a1x1+a2x2+…+anxn ≤ b1

прибвим xn+1 так, чтобы лев.часть стала равна пр.ч.

a1x1+a2x2+…+anxn+ xn+1 = b1, где xn+1= b1 - a1x1 - a2x2 -…- anxn (xn+1-дополн.перем.)
Теорема. Каждому решению ß(β1…βn) нер-ва (1) соотв.единств.реш-е след.сис-мы:

a1x1+a2x2+…+anxn+ xn+1 = b1 (2)

xn+1≥ 0

Каждому реш-ю сис-мы (2) соотв.единств.реш-е нер-ва (1)

Док-во:1) пусть ß – реш-е нер-ва

a1β1+a2β2+…+anβn ≤ b1 (3)

0≤b1-a1β1-a2β2-…-anβn = βn+1

Если подст. βi в (2) вместо xi:

a1β1+a2β2+…+anβn+(b1-a1β1-a2β2-…-anβn)=b1

b1=b1

2) a1β1+a2β2+…+anβn+ βn+1=b1 (4)

βn+1≥0

Отбросим βn+1 из (4). Т.к. βn+1 – неотриц., отбросив ее, получим нер-во (3).
Замечание. Дополн.неизвест.не влияют на цел.ф-ю (т.е.вводятся с коэф-м 0).

Замечание. В зав-ти от знака нер-ва дополн.перем.надо либо прибав., либо вычит.

48. Правила составления двойственной задачи

1)Во всех ограничениях основной задачи неизвестные стоят слева,а свободные переменные справа

2)В ограничениях-неравенствах знаки должны быть направлены в одну сторону

Максимум--≤ , минимум-- ≥

4)Каждому ограничению исходной задачи соответствует переменная двойственной задачи,при этом ограничению нер-ву соответствует у>=0, а уравнению – не налагается усл неотрицат.

4) матрица системы ограничений двойтв.задачи-транспонированная матр системы огранич исходной

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

1) Если одна из пары двойственных задач имеет оптимальное решение,то и двойственная к ней имеет оптимальное решение,причём значения целевых ф-ий на своих оптимальных решениях совпадают.

2)Если одна из пары двойственных задач не имеет решения ввиду неограниченности целевой ф-ии,то и другая не имеет решения ввиду несовместности системы ограничений.

Док-во:
50. Вторая теорема двойственности

Для того,чтобы допустимые решения X=(x1 ,x2 ,xn ) и Y=(y1 ,y2 ,yn ) являлись оптимальными решениями пары двойственных задач необходимо и достаточно,чтобы выполнялись следующие равенства:

Xj(Σ(от m до j=1) aij*yi – cj)=0 j=1,2….,n

Yi(Σ от n до i=1 aij*xj – bi)=0 i=1,2….,m

Другими словами: Если при подстановке оптимального решения в систему ограничений i-е ограничение выполняется как строгое неравенство,то i-ая координата двойственной задачи=0 и наоборот если i-ая координата оптимального решения положительна,то i-ое ограничение двойственной задачи удовлетворяется оптимальным решением как равенство.
39. Графический метод решения ЗЛП.

ОДР имеет вид многоуг-ка, т.к. кажд.нер-во – полуплоскость. Цел.ф-я – прямая.

Прямая линия, ур-е кот.получ.из цел.ф-и, если приравнять ее константе, нзв линией уровня.

Лин.ур-ня, имеющая общ.точки с ОДР и располож.так, что ОДР наход.в одной из полуплоскостей, нзв опорной прямой.

Алгоритм реш-я плоской ЗЛП граф.методом:

*Строим обл.допуст.реш-й;

*Строим в-р n(c1;c2) с началом в т.(0;0);

*Строим лин.ур-ня, соотв.ур-ю с1х12х2=0;

*Лин.ур-ня перемещаем || самой себе до полож-я опор.прямой. На этой прямой и будут наход.знач-я max и min

в зав-ти от вида ОДР и цел.ф-и кол-во решений может быть различно.(если одр явл пустым множеством след реш нет, если линия уровня уходит в бесконечность, то задача не имеет решений ввиду неограниченности цел ф-ии, если целевая функция достигает экстремума в двух угловых точках, то бесконечное множ-во решений. Опт решением явл любая выпуклая линейная комбинация этих точек)

*после нахожд опт реш вычислить значение целевой ф-ии.

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



40. Графический метод решения задачи лин прогр-ния с n переменными(неизвестными).

Данным методом могут решаться задачи только имеющие каноническую форму и удовлетворяющ условию: n-r≤2,

*методом жор дана-гауса приведем сист уравнений-ограничений задачи к равносильной разрешенной. Одновременно исключим разрешенные неизвестные из целевой ф-ии

*запишем в преобразованном виде

*отбросим в уравнениях-ограничениях неотриц разрешенные неизвестные и заменим знак равенства на знак ≤, получим вспомогат задачу ЛП с двумя перменными

*решаем графически

*находим оптимальное решение

*вычисляем мин значение цел ф-ии

*находим опт решение исходной задачи. Для этого используем систему ограничений в разрешенном виде
ВЫПУКЛАЯ ЛИНЕЙНАЯ КОМБИНАЦИЯ. МНОЖЕСТВА

Точка М называется выпуклой линейной комбинацией точек А и В, если М = 1А+2В (≥0 и 1 + 2 = 1)

Угловой точкой множества называется точка которая не является выпуклой линейной комбинацией каких либо точек этого множества она не лежит на прямой соединяющей каике либо две точки множества.

Выпуклое множество – содержащее выпуклую линейную комбинацию любых своих точек.

Замкнутое множество содержащее все свои граничные точки.

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

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


Метод искусственного базиса

Применяется в том случае если, задача не имеет начального опорного решения с базисом из единичных векторов.

1.Составляем расширенную задачу. ( добавляем искусственные переменные – не отрицательные переменные которые вводятся в левую часть одного из уравнений системы ограничений с коэф. +1 и в целевую функцию на макс. -М в задаче на минимум +М).

2.Либо находим оптимальное решение, либо устанавливаем его отсутствие.

Особенности

1.Оценки разложений векторов условий j = Сб * Xj – cj состоят из двух слагаемых. Одно из которых не зависит от М. На первом этапе расчета, используем только слагаемые оценок J(M)

2.Векторы соответствующие иск. Переменным, которые выводятся из базиса, исключаем из рассмотрения.

3.Далее продолжаем симплексным методом с использованием оценок независящих от М.

Теорема. Признак оптим.оп. реш.

Если расширенная задача имеет оптим. Реш. У которого все иск. Переменные равны 0, то исходная задача, имеет оптим. Реш. Которое получается отбрасыванием всех нулей соответствующих иск. Переменным.

Теорема. Признак отсутствия решения ввиду несовместности системы.

Если расширенная задача имеет оптимальное решение, у которого хотя бы одна иск. Переменная не равна 0, то сходная задача не имеет решений ввиду несовместности.

Теорема. Признак отсутствия решения ввиду неограниченности целевой функции.

Если расширенная задача не имеет решения, ввиду неограниченности цел. Функции, то исходная задача тоже не имеет решения по той же причине.


51. ТЗЛП.





52. Необходимое и достаточное условие разрешимости транспортной задачи

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

 ai= bj –задача с правильным балансом
Ранг системы в-ров-усл-й ТЗЛП равен m+n-1
53. Понятие цикла.Условие опорности допустимого решения. Метод вычёркивания проверки опорности решения задачи.

Циклом называется такая последовательность клеток таблицы

(I ;j ), (I ; j ), (I ; j )…..(I ;j ) в к-й 2 и только 2 соседние клетки цикла расположены в одной строке или столбце,причём первая и последняя тоже находятся в одной строке или столбце. Цикл-замкнутая ломаная линия.

Допустимое решение транспортной задачи-X является опорным т/т/т,когда из занятых клеток таблицы нельзя составить ни одного цикла.

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

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

Метод северо-западного угла.

Заполняем таблицу с левого верхнего угла. Следя этому методу,исходя из запасов очередного поставщика и потребителя, заполняем только одну клетку и исключаем из рассмотрения поставщика или потребителя соответственно.

Правила:

1)если aj
2) если aj>bj, то пишем число и исключаем стоблец -потребителя.

3)если aj=bj, исключаем или поставщика или потребителя , не забываем про 0(базисный нуль)

Далее проверяем, что число занятых леток =n+r-1 и векторы-условия линейно независимы.


46. Теорема (об улучш.опор.реш-я). Если в задаче лин прогр-ния на max(min) хотя бы один из коэфф-ов целевой строки (-ck) явл отрицательным (положительным), то опорное решение может быть улучшено, т.е. можно найти новое опорное решение, на котором значение целевой ф-ции будет больше (меньше).

Следствие №1(условие наискорейшего нахождения оптимума): Для обеспечения изменения целевой ф-ции в сторону оптимальности при переходе от одного опорного решения к другому, необходим ыбор в-ра, вводимого в базис опорного решения, производить из условия:

1) в задаче на max => - ck <0.

2) в задаче на min => - ck>0.

В случае нескольких вариантов выбираем столбец из условия: |min θk*ck| = max

Следствие №2 Признак оптимальности опорного решения:

Опорное решение задачи лин прогр-ния на max (min) явл оптимальным, если все коэф-ты в целевой строке разрешен канонич задачи неотрицательны (неположительны).

Следствие №3 Признак единственности оптимал решения:

Оптимал решение задачи лин прогр-ния явл единственным, если все коэф-ты в целевой строке разрешен канонич задачи положительн (отрицательны).

Следствие №4 Признак существования бесконечного множ-ва оптимальных решений: Задача лин прогр-ния имеет бескон множество решений, если в целевой строке есть коэф-ты=0 в столбцах, соответствующих векторам, не входящим в базис.

Следствие №5 Признак отсутствия оптимальности решения ввиду неограниченности целевой функции: Задача лин прогр-ния не имеет решения ввиду неогранич целевой ф-ции, если при выборе разрешающего столбца, соответствующего обеспечению оптимальности решения все коэф-ты вектора условий отрицательны

47. Понятие о двойств.задачах. Мат.модель 2-ной ЗЛП.

Имеется m-видов сырья b1,……bn, к-ые используются для производства n-видов продукции.

Введём переменную aij-расход i-го сырья на изготовление единицы j-й продукции.

Сj–прибыль от реализации единицы i-го вида продукции, Xj–объём выпуска j-й продукции

Z(x)=c1x1+c2x2+…+cnxn →max

a11x1+a12x2+…+a1nxn≤b1

a21x1+a22x2+…+a2nxn≤b2

…………………………

am1x1+am2x2+…+amnxn≤bm

xj≥0

Предположим, что имеется 2-й производитель(2-я фирма) тоже производит какую-то продукцию и ей требуется то же сырьё, что и для 1-й. Рассматриваем задачу условий продажи сырья 1-й фирмы 2-й

Y=(y1,y2,…ym)-вектор цен единицы i-го вида сырья

F(Y)=b1y1 +b2y2+….+bmym →min

a11y1+a21y2+…+am1ym≥c1

a12y1+a22y2+…+am2ym≥c2

…………………………

a1ny1+a2ny2+…+amnym≥cn

yi≥0

Мы построили двойственную или сопряжённую исходной задачу.

Матрица коэффициентов сопряжённой задачи является транспонированной матрицей коэффициентов исходной задачи.

Математические модели двойственных задач

Симметричные пары

1) Z(x)=C*X=> max F(y)=Y*B=>min

A*X≤B Y*A≥С

x≥Ø Y≥Ø

2) Z(x)=C*X=>min F(y)=Y*B=>max

A*X≥B Y*A≤C

X≥Ø Y≥Ø

Несимметричные пары

1) Z(x)=C*X=>max F(y)=Y*B=>min

A*X=B Y*A≥C

X≥Ø

2)Z(x)=C*X=>min F(Y)=Y*B=>max

A*X=B Y*A≤C

X≥Ø



45. Симплексный метод решения задач

Симплексный метод основывается на след:

  1. ОДР ЗЛП явл выпуклым множеством с конечным числом угловых точек, т.е. многогранником или многоугольным множеством

  2. Опт решением ЗЛП явл одна из угловых точек ОДР

  3. Угловые точки ОДР алгебраически представляют некоторые базисные (опорные) решения системы ограничений задачи.

Основное содержание симплексного метода:

Найти нач опорн реш;

Осущ переход от опорного к оптимальному;

Определить критерии завершения процесса решения задачи, позволяющие своевременно прекратить перебор решений на оптимальном или сделать заключение об отсутствии реш-я
*привести к канонич виду при необходимости

*найти начальное опорное решение. Если опорное решение отсутствует, то задача не имеет решений ввиду несовместности сист огранич

*если выполняется признак единственности опт решения, то решение зад закончено

*если выполняется условие сущ бесконечности опт решений (в цел ф-ии есть 0 в столбце, соттв векторам не вошедших в базис), то выбираем в этом столбце разреш эл и решаем методом жордана-гауса

*если есть условия отсутствия опт решения(при выборе разреш элемента в столбце все эл ≤ 0), ввиду неограниченности целевой ф-ии

*если пункты 3-5 алгоритма не выполняя, то находим новое опорное решение и возвр к пункту 3
54. Метод минимальной стоимости.

Позволяет построить опорное решение, которое достаточно близко к опт. Состоит из ряда однотипных шагов, на каждом из которых заполняется только одна клетка таблицы , соотв мин стоимости, и исключается из рассмотрения только одна строка (поставщик) или один столбец (потребитель). Поставщик исключается из рассмотрения, если его запасы заканчиваются. Потребитель исключается если его запросы удовлетворены. На каждом шаге искл либо один поставщик, либо один потребитель. При этом если поставщик еще не исключен, но его запасы равны 0, то на том шаге, когда от него требуется поставить груз, в ссотв клетку ставим базисный ноль и лишь затем поставщик искл из рассмотрения.
55. Переход от одного опорного решения к другому. Означенный цикл. Сдвиг по циклу.

В транспортной задаче этот переход осуществляется с помощью цикла.

Теорема:

Если таблица ТЗ содержит опорное решение,то при сдвиге по любому циклу,содержащему одну пустую клетку,на величину

θ (θ =min“-“(xij)),снова получаем опорное решение.



42. Опорное реш-е ЗЛП

Теорема. Об экстремуме целевой функции. Целевая функция достигает максимума, в угловой точке ОДР, причем если этот экстремум достигается в нескольких угловых точках ОДР то этот экстремум достигается и в любой выпуклой лин. комбинации этих угл. точек.

Опорное решение – допустимое решение для которого, векторы условий соответствующие положительным компонентам этого решения являются линейно независимыми.

Теорема 1.

Любое опорное решение является угловой точкой ОДР.

57. Метод потенциалов.Его алгоритм.

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

Рассматривается группа неравенств u +v =c при положит.значениях объёмов перевозок,получаем систему уравнений.

m+n-1 уравнений,m+n неизвестных

Для того,чтобы найти решение системы одной из неизвестных присваиваем значение 0.

Алгоритм:проверяем необх и дост усл существ задачи

1) Строим нач.опорное решение

2) Проверяем правильность его построения методом вычёркивания

3) находим u v(для проверки оптимальности опорного решения) – решаем систему уравнений для нахождения потенциалов.

4) Вычисляем оценки свободных клеток и отрицат.оценки записываем в левый верхний угол(если все оценки неотриц.,то решение опорное) u +v -с=∆ij положит оценки пишем внизу, отриц – просто минус.

5) Для всех клеток с отриц.оценками строим цикл (самая большая оценка) и определяем параметр θ(минимум из грузов в цикле)

7)Далее см.пункт 3 И так продолжаем до получения оптимального опорного решения.

Замечание: если при сдвиге по циклу 0 образуется в нескольких клетках,то одну из них оставляем пустой,а в остальных ставим базисные нули,чтобы число занятых клеток было m+n-1.
58. Особенности реш-я ТЗ с неправ.балансом.

1) Если суммарные запасы поставщиков превосходят сум.запросы потреб-лей, в сис-ме ограничений первую группу ур-й Σxij=ai следует заменить нерав-ми: Σ(от n до j=1)xij≤ai. Для приведения к канон.форме вводят дополнительные перем-е.

=>чтобы задача имела реш-е, необходимо ввести фиктивного потребителя с запросами bn+1, равными разности сум.зап.пост.и запр.потр., и нулевыми стоимостями перевозок единиц груза.

2) Если суммарные запросы потребителей превышают сум.запасы поставщиков, вторая группа ур-й сис-мы ограничений Σxij=bj заменяется неравенствами: Σxij≤bj

=>чтобы задача имела реш-е, необходимо ввести фиктивного поставщика с запасами аm+1, равными разности сум.зап.пост.и запр.потр., и нулевыми стоимостями перевозок единиц груза.
** ai(отmдоi=1)>  bj - ai -  bj= bn+1 запасов больше груз не вывезен вводим фиктивного потребителя

 ai(отmдоi=1)<  bj - ai -  bj= am+1 вводим фиктивного поставщика с нулевыми стоимостями перевозок единиц груза.

Замеч.: при составлении нач.опор.реш-я в послед.очередь следует распред.запасы фиктивного поставщика/удовл.запросы фикт.потреб., несмотря на то, что им соотв.мин.стоимость перевозок=0
Метод минимальной стоимости

Позволяет строить опорное решение, достаточно близкое к оптимальному и в отличие от севзап угла используется матрица стоимостей.

Выписываем матрицу, выбираем мин стоимость и обводим в кружочек- в соответств клетку записываем макс возможный объем перевозок. Исключаем потр/пост так как запросы/запасы истощены/удовл. Далее проверяем число занятых клеток =n+m-1 и на лин зависимость векторов условий.







1 Линейные ур-ия. Системы лин.ур.

Имеет вид a1x1+a2x2+…+anxn=b

  • Тривиальное 0x1+0x2+…+0xn=0 имеет бесконечное мн реш, подходит любой вектор

  • Противоречивое 0x1+0x2+…+0xn= b не имеет ниодного решения, никакой вектор ему не может удовл

  • Один из коэф не=0можно решить отн х

Любой и-мерный векторХ = (X1, Х2 ... , Хn) называется решением уравнения, если при подстановке его координат уравнение обращается в тождество.
Системы лин уравнений

а11Х112Х2+ …1nхn =b1,

a2jX122Х2+ 2nхn =b2,

ai1x1 + ai2x2+ ... + ainxn= bi,

аm1x1т2Х2 + ... +атnхn =bm,

Решением системы уравнений называется такой n-мерный вектор Х = (Х1,Х2 ... , хn), который является решением каждого из уравнений системы.

Система является разрешенной,если каждое уравнение системы является разрешенным относительно своей неизвестной,которая не повторяется.

Общее решение с-мы-выражение разреш неизвестных через b и свободные неизв. Частное решение-общее при подстановке значений своб переменных; Базисное-частное, соответствующее нулевым значениям своб.переменных
Преобразования

Разрешение основывается на 2 элементарных преобразованиях- преобр Жордана

1)если обе части системы увеличить на число не =0 – равносильность не нарушится.

2)2 уравн можно сложить и 1 заменить суммой
Классификация систем л ур

Совместные: определенные единственное решение, неопределенныемножество; несовместныенет решений

Если число резреш неизв в разреш системе совпадает с числом уравнений, то система определенная; если неизв меньше, то система неопределенная

Метод Жордана Гаусса

1)Проверяем не является ли система несовместной(есть противоречивые ур-иянеовместна)

2)сокращение числа уравнений. Есть тривиальное-вычерк

3) если система разрешена- пишем общее решение и част

4)если нет, разрешаем.выбираем разрешающий элемент
Лин зависимость

Линейная комбинация векторов а1 а2 аn c коэфф -- 1a1+2a2+…+nan=

Сист векторов (A1,a2,..an) лин независима, если ее линейная комбинация = только при нулевом наборе коэффиц. Система лин зависима, если лин комбинация= и существует ненулевой набор коэфф

Нашли ненулевойX, подставили в систему, она =0завис

Свойства

1)Если система векторов линейно зависимая, то хотя бы один из векторов разлагается по остальным и, наоборот, если хотя бы один из векторов системы разлагается по остальным, то система векторов линейно зависимая.

2)Если какая-либо подсистема векторов линейно зависимая, то и вся система линейно зависимая.

3)Если система векторов линейно независимая, то любая ее подсистема линейно независимая.

4)Любая система векторов, содержащая нулевой вектор, линейно зависимая.

5)Система m-мерных векторов всегда является линейно зависимой, если число векторов n больше их размерности (n>m)
Базис системы векторов-такая ее подсистема B1 B2 Bn которая линейно независима и по которой разлагается любой вектор системы.

Алгоритм нахождения базиса:

1)соствить систему уравнений

2)привести к равносильной разрешенной системе

3)составить базис Б,включив в него векторы соответствующие разрешенным неизвестным

4)записать разложение по базису( коэффициентами будут координаты вектора)

5)система может иметь несколько базисов. вместо к будет r

Теорема Кронекера Капелли о совместности.

Для того,чтобы система была совместна,необхдимо и достаточно, чтобы ранг расширенной матрицы системы был равен рангу матрицы
Фундаментальная система решений для однородной системы уравнений .

1.Если имеется некоторое К решений однородной системы, то К, где  некоторое число, так же является решением этой системы. Действительно, так как АК = , А(К) = (АК) =  = .

2.Если векторы К1, К2 являются решением однородной системы уравнений, то К1 +К2 так же являются её решением. Т.к. АК1 = , АК2 = , то А(К1+К2) = АК1 +АК2=  +  = 0

Следствие, если векторы К1, К2, …, Кn являются решениями однородной системы уравнений, то любая их линейная комбинация, так же является решением этой системы.

Фунд. Сист. Реш. Однор. Сист. Ур–ий. Называется линейной независимая система векторов – решений системы F1,F2,…,Fk, по которой разлагается любое решение системы, т.е. любое решение системы уравнений равно X=F1t1+F2t2 + … +Fktk. Где t – вещественные числа.

Теорема, если ранг матрицы системы однородных уравнений R меньше числа неизвестны N, то система уравнений имеет фундаментальную систему решений, состоящую из N-R векторов – решений.

МАТРИЦЫ.

Матрицей размерности n на m, называется таблица чисел (элементов)содержащая n строк и m столбцов. Транспонированная матрица – матрица А, с переставленными соответствующими строками и столбцами местами.

Любую матрицу можно умножить на любое число,при этом все элементы матрицы умножатся на это число.

Две матрицы одной размерности можно сложить

A+B =B+A; (µ+)A=A+µA; (A+B)=A+B; (µA)=(µ)A
Матрица А-1 называется обратной по отношению к матрице А, если АА-1 = А-1А=Е. Обратная матрица может существовать только для квадратных матриц, т.е. для тех матриц, у которых число строк и столбцов совпадает.

Теорема. Необходимым и достаточным условием существования обратной матрицы, является её не вырожденность. Матрица называется невырожденной если её система векторов столбцов линейно независима, то есть r = n.





написать администратору сайта