Определенная и неопределенная СЛАУ

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

Система из k ур-ний первой степени с n неизвестными им.след.вид:

a₁₁x₁+a₁₂x₂+…+a_1nx_n=b_1, где b – cвоб.члены;

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

………………………..

a_m1x₁+a_m2x₂+…+a_mnx_n=b_m

Составим матрицу А из коэф-тов при неизвестных системы лин.алгебр.ур-ний. Она наз. матрицей системы, а матрицу A, получающуюся добавлением к А столбца своб.членов системы, наз.расширенной матрицей:

а₁₁ а₁₂ a_1n а₁₁ а₁₂ a_1n b₁

А= а₂₁ а₂₂ а_2n A = а₂₁ а₂₂ а_2n b₂

_{…………………………… ……………………………}

а_k1 а_k2 а_kn а_k1 а_k2 а_kn b_k

Введем в рассмотрение векторы-столбцы(матрицы-столбцы): a_j-коэф-ты при неизвестной x_j (j=1…n), b –своб.члены, x-неизвестные:

а_1j b₁ x₁

а_j= а_2j b= b₂ x= x₂

_{………………………………………………….}

а_kj b_k x_k

Очевидно, левые части ур-ний исх.сист. совпадают с эл-тами матрицы-произв-я Ах, а j-е слагаемые во всех ур.системы предст. собой эл-ты вектора-столбца a_jx_j, получаемого умножением вектора a_j на число x_j. Поэт.исх.СЛАУ м.зап. в векторной и матричной формах:

a₁x₁+a₂x₂+…+a_nx_n=b или Ax=b. прим(А-затраты,В-обьем,С-прибыль)

4.Дайте определение матрицы, обратной квадратной матрице А. Какое условие является необходимым и достаточным условием существования обратной матрицы?

Жордана – Гаусса. с помощью преобразований за конечное число шагов приводят систему в равносильную систему, которая легко исследуется и решается. Решение - такая система m чисел при подстановки которой в каждое из уравнений системы, обращает любое уравнение в верное тождество.

не имеет решений, если все коэфф при неизвест = 0, а правая сторона уравнения не равна 0. (, где ).

имеет уравнение, являющееся линейной комбинацией каких-либо других уравнений системы: если левая и правая чиста уравнения обращаются в 0 (т.е. 0=0). тогда уравнение удаляют и продолжают решение системы.

5.СЛАУ решается методом Жордана- Гаусса. Каким образом в процессе решения убедиться в том, что СЛАУ:1)не имеет решения?2)имеет уравнение, являющееся линейной комбинацией каких-либо других уравнений системы?

Жордана – Гаусса. с помощью преобразований за конечное число шагов приводят систему в равносильную систему, которая легко исследуется и решается. Решение - такая система m чисел при подстановки которой в каждое из уравнений системы, обращает любое уравнение в верное тождество.

не имеет решений, если все коэфф при неизвест = 0, а правая сторона уравнения не равна 0. (, где ).

имеет уравнение, являющееся линейной комбинацией каких-либо других уравнений системы: если левая и правая части уравнения обращаются в 0 (т.е. 0=0). тогда уравнение удаляют и продолжают решение системы.

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

При нахождении неотрицательных решений СЛАУ выбирается разрешающая неизвестная, при кот хотя бы в одном уравнении имеется положительный коэффициент. А для нахождения разрешающего уравнения находят тип отношений столбца свободных членов к положительным элементам разрешающего столбца, в этом случае k-ое уравнение будет разрешающим. min(b_i/a_ij>o)=b_k/a_ij. И минимальное отношение покажет разрешающее уравнение. Если хотя бы в одном из ур-й системы свободный член положителен,а все коэф-ты при неизв-х<0,то система неотрицательных реш-й не имеет. Преобразования системы в соотв с этими правилами наз симплекс преоб-ниями системы. Если указанный min достигается для неск-х ур-й системы, то такая система наз вырожденной. Необх-м условием вырожденной системы явл то, что свободный член хотя бы одного ур-я системы=0.

7)Дайте определения: разрешающая неизвестная, разрешающее уравнение, базисная и свободная переменная, базисное и общее решение

Разрешающ неизвестная – та, коэффициент при которой не равен 0. Разрешающее уравнение – в котором содержится разрешающая переменная. Базисная переменная – та, которая входит только в 1 уравнение системы. Свободная переменная – та, которая не является базисной, входит в несколько уравнений системы. Общее решение – выражение базисных неизвестных через свободные. Базисное решение – когда свободные переменные имеют нулевое значение. (х₁=h₁ x₂=h₂ x_m+1=0 и т.д. х_n=0). Небазисные решения – когда свободные неизвестным придаются какие-либо значения.

9) Дайте определение ранга матрицы размером m*n. Определите ранг матрицы (матрица задана).

Рангом системы n-мерных в-ров называется максимальное число линейно независимых в-ров этой системы. ранг системы единичных в-ров равен n.

Ранг системы в-ров не изменяется, если она подвергается элементарным преобразованиям:

Умножение какого-нибудь в-ра системы на число, отличное от 0;

Прибавление к какому-нибудь в-ру системы другого в-ра этой же системы, умноженного на число.

Перестановка каких-либо в-ров системы.

У матрицы размером mxn можно рассматривать строки как n-мерные в-ры, а столбцы как m-мерные в-ры.

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

Ранг матрицы – максимальное число линейно независимых рядов.

10) Дайте определения: Совместная и несовместная СЛАУ,

Определенная и неопределенная СЛАУ.

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

11)Действия над матрицами: сумма, произведение, транспонирование. Свойства и формулы для расчета элементов.

Матрицей размера 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 называется матрица С размера m х k, эл-ты кот с_ij равны скалярному произведению i-й строки матрицы А на_j-й столбец мат­рицы В, т.е.

Произведение матриц обозначается С = АВ.

Д ля операции произведения матриц справедливы следующие свойства: 1) A(BС) = (АВ)С; 2)(А+В)С=АС+ВС;
3)A(B+С)=AB+AC; 4) λ(АВ) = (λА)В.

Каждой квадратной матрице А n-го порядка можно поставить в соответствие некоторое число, называемое определителем, или детерминантом, n- го порядка и обозначается как: det(A), |А| или Δ(A).

Для матрицы первого порядка детерминантом является сам единственный элемент этой матрицы:

Для матрицы 2*2 детерминант определяется как

12)Единичная матрица: определение, формулы для элементов

Матрица – это прямоугольная таблица чисел, содержащая m строк и n столбцов.

a₁₁ а₁₂ …а_1n

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

…………..

a_m1 а_m2 …а_mn

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

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

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

Свойства:

1)Обратная и исходная матрицы перестановочны и матрица, обратная обратной, совпадает с исходной: А*А^-1=А^-1*А=Е.

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

Только квадратная матрица может иметь обратную.

Для нахождения обратной матрицы можно использовать следующий алгоритм:

Смотрим, квадратная ли матрица: если нет, обратной матрицы не существует; если квадратная, переходим к след. пункту;

Вычисляем определитель ∆А; если он равен 0, обратной матрицы не существует; если он не равен 0, переходим к след. пункту;

Вместо каждого элемента матрицы ставим его алгебраическое дополнение (алгебраическим дополнением некоторого элемента определителя называется минор этого элемента, умноженный на (-1)^s, где s – сумма номеров строки и столбца, на пересечении которых расположен этот элемент);

Полученную матрицу транспонируем;

Каждый элемент полученной матрицы делим на определитель исходной матрицы и получаем матрицу, обратную данной.

Постановка линейной производственной задачи, смысл переменных, векторов и матриц, допустимый и оптимальный план, математическая модель

Лин производ зад – это задача о рац испол производ мощностей. Смысл - предпр выпускает n видов изделия на m видах оборуд. А –матрица издержек, a_ij - издержки, затраты на изгот ед j-ого изделия на i-том оборуд. Вектор В – это объем ресурсов, b_i,- имеющееся количество i-го ресурса, а вектор С – прибыль от реализации единицы изделия каждого вида, с_j - прибыль на единицу j-й про­дукции, х_j - искомое количество единиц j-й продукции. Матем модель: задача -найти производ программу X = (x_1, x₂, x₃, x₄), максимиз прибыль. По составленным неравенствам рисуем на графике область допустимых решений. Допустимое решение – набор x_1, x₂, x₃, x_4, который удовлет усл зад и каждая компонента которого неотрицателна. рисуем линии уровня функции прибыли, которые перпендик вектору-градиенту прибыли. Ищем наибольшее значение функции прибыли в ОДР, координаты этой точки являются оптимальным планом.

Постановка общей задачи математического программирования. Основные понятия

Задачу линейного программирования нередко формулируют как задачу минимизации или макси-мизации линейной формы 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 – матрицы-столбцы (векторы) неизвестных и свободных членов:

, ,

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

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

Вектор-градиент – вектор, который при графическом решении задачи ЛП указывает направление наиболее быстрого роста целевой функции. Линия уровня функции Z перпендикулярны gradZ и образуют семейство паралл прямых. ОДЗ –та область, кот задана огранич, т.е. прямыми. Допустимые решения х образуют в множестве точек допустимую область, кот является пересеч замкнутых полупространств. область - многогранник в n-мерном пространстве, гранями -участки гиперплоскостей вида или . Множество выпуклым, если вместе с любыми двумя его точками ему принадлежит и отрезок, соединяющий эти точки. Полупространство – выпуклое множество, допустимый многогранник также является им. Замкнутым - множество, сод все свои граничные точки. Угловые точки выпуклого множества – точки, не являющиеся выпуклой комбинацией двух различных точек множества. Выпуклое замкнутое ограниченное множество на плоскости, имеющее конечное число точек, называется выпуклым многоугольником. Многоугольник решений может быть точкой, лучом, отрезком, многоугольником и неограниченной многоугольной областью. Задача ЛП - отыскать такие точки многоугольника, координаты которых обеспечивают целевой функции минимальное\ максимальное значений. Графич мет- зад с двумя переменными. два этапа. На первом - строится множество допустимых решений. Допустимым решением называется любой вектор, удовлетворяющий всем ограничениям задачи. 2 - ищется оптимальное решение. Оптимальное решение – допустимое решение с наибольшей/наименьшей целевой функцией. из точки (0,0) градиент показывает направление увеличения функции.