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

Пусть задана кв. матрица А.Если сущ-т матрица В, такая что А*В=Е,то гов что матрица В явл обратной по отношению к мат А: В=А^-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₁₁….а_1m u₁₁….u_1m

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

a_m1….a_mm u_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₂

_. ..............

х_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).

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

Основной задачей линейного программиро-вания называется задача отыскания min ли-нейной формы z = c_j x_j, при неотрицатель-ности входящих в нее переменных и системы ограничений в виде СЛАУ

 

a_ijx_j ≤ b_i

x_j≥ 0; i= ; j= .

С	базис	H	c1	c2	...	cm	cm+1	...	cj	cn
x1	x2	...	xm	xm+1	...	xj	xn
c1	x1	h1			...		g1,m+1	...	g1j	g1n
c2	x2	h2			...		g2,m+1	...	g2j	g2n
...	...	...	…	...	...	...	...	...	...	...
cm	xm	hm			...		gm,m+1	...	gmj	gmn
		L-L0			...		∆m+1	...	∆j	∆n

Для приведения линейной задачи произ-водственного планирования к основной за-даче линейного программирования необходи-мо:

1. Ф-я z заменяется на “-z”.

2. В левой части сис-мы ограничений СЛАН вводится по одной искусствен-ной переменной в каждое из неравен-ств.

Найти план производства x_j, j= обеспечивающий min линейной формы

-z = - c_j x_j → min. И ограничения

a_ijx_j + x^’_i = b_i

x_j ≥ 0; x^’_i≥0, i= ; j= .

Исходные параметры задачи могут быть представлены в виде технологической матрицы A затрат ресурсов на единицу продукции каждого вида, вектора B объемов ресурсов и вектора C удельной прибыли: C=(c₁, …, c_n).

Матричная форма записи:

 

14. Геометрическая интерпретация задачи ЛП и симплексного метода. Графическое решение задачи ЛП с 2мя переменными.

 

15. Симплексметод ЛП: задача ЛП в предпочитаемой форме, выражение функции цели через свободные неизвестные, вычис-ление относительных оценочных коеффици-ентов ∆_j и значение целевой функции соответ-ствующих данному базисному допустимому решению.

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

Минимизировать L=c₁x₁+c₂x₂+...c_nx_n (1), при условиях:

x₁ + g_1,m+1x_m+1 +... + g_1nx_n = h₁,

x₂ + g_2,m+1 x_m+1 +... + g_2nx_n = h₂, (2)

............

x_m + g_m,m+1 x_m+1 +... + g_mnx_n = h_m

 

и x_j≥0, j = 1,2,...n (3).

Одним из допустимых решений задачи линейного программирования (1)-(3) будет базисное неотрицательное решение системы (2): x₁=h₁, x₂=h₂,...x_m=h_m, x_m+1=0,...x_n=0 (4), ему соответствует значение целевой ф-ии равное

L₀=c₁h₁+c₂h₂+...c_mh_m+c_m+1*0+...+c_n*0 = c_i h_i (5).

Надо исследовать, является ли решение (4) оптимальным (т.е. является ли значение (5) наименьшим из всех возможных значений целевой ф-ии (1), отвечающих различным неотрицательным решениям системы (2)).

Учитывая что система уравнений (2) имеет предпочитаемый вид, находим для нее общее решение: x_i=h_i-g_i,m+1x_m+1-...-g_inx_n, i=1,2,...,m (6). Если свободным неизвестным придавать какие-нибудь неотрицательные значения, то будем получать различные решения системы (2), среди которых нас интересуют только неотрицательные. Подставляя их компоненты в линейную форму (1), можно подсчитать соответствующие значения целевой функции. Если переписать выражение (1) в виде:

- L = c₁x₁+c₂x₂+...c_mx_m+ c_m+1x_m+1+...+c_nx_n=0 (7). Для того чтобы исключить базисные неизвестные из (7), достаточно умножить первое уравнение системы (2) на c₁, второе- на c₂, …, m-e на c_m, сложить полученные произведения и из результата вычесть уравнение (7). Получим L=∆_m+1x_m+1+...+∆_nx_n=L₀ (8), где ∆_j = c₁g_1j + c₂g_2j +... + c_mg_mj - c_j, j=1,2,...n (9) или ∆_j = z_j - c_j, z_j= c_ig_ij, j=1,2,...n (9a). Целесообразно ввести вектор C (c₁,c₂,...c_m)`, компонентами которого служат коэффициенты при неизвестных в линейной форме (1), они записываются в том порядке, в котором расположены соответствующие базисные неизвестные в системе уравнений. Тогда, z_j можно представить как скалярное произведение

∆_j = CG_j- c_j, j=1,2,...n. А L₀ = CH.

Для проведения указанных вычислений обычно составляют таблицу (ТАБЛИЦА 1)

Ее называют – первой симплекс таблицей.

Из Ур-я (8) получаем выражение целевой ф-ии L через свободные неизвестные:

L=L₀-∆_m+1x_m+1-...-∆_nx_n.

 

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

Из выражения L=L₀-∆_m+1x_m+1-...-∆_nx_n (1) следует, что базисное решение x₁=h₁, x₂=h₂,...x_m=h_m, x_m+1=0,...x_n=0 (2) является оптимальным решением задачи ЛП

L=c₁x₁+c₂x₂+...c_nx_n,при условиях:

x₁ + g_1,m+1x_m+1 +... + g_1nx_n = h₁,

x₂ + g_2,m+1 x_m+1 +... + g_2nx_n = h₂,

............

x_m + g_m,m+1 x_m+1 +... + g_mnx_n = h_m

 

и x_j≥0, j = 1,2,...n, тогда и только тогда, когда в уравнении L=∆_m+1x_m+1+...+∆_nx_n=L₀ среди коэффициентов ∆_j при неизвестных нет ни одного положительного, т.е. условие оптимальности имеет вид: ∆_j ≤0, j=1,2,...n.

Действительно, если в общем решении x_i=h_i-g_i,m+1x_m+1-...-g_inx_n, i=1,2,...,m мы станем придавать различные неотрицательные значения свободным неизвестным так, чтобы соответствующие базисные неизв-е принимали неотрицательные значения, то одновременно с частными неотрицательными решениями с-мы ограничений будем получать согласно выражению (1), соответствующие им значения целевой ф-ии. В частности, при нулевых значениях свободных неизвестных получится базисное решение (2) и соответствующее ему значение линейной формы

L₀=c₁h₁+c₂h₂+...c_mh_m+c_m+1*0+...+c_n*0 = c_i h_i

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

При выполнении условия оптимальности базисное решение x₁=h₁, x₂=h₂,...x_m=h_m, x_m+1=0,...x_n=0 будет единственным оптимальным решением задачи ЛП тогда, и только тогда, когда все коэффициенты ∆_m+1, ∆_m+2,…, ∆_n при свободных неизвестных в последнем уравнении вспомогательной системы x_i + g_ijx_j = h_i, i= 1,2,...m,

(1)

L + ∆_jx_j = L₀

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

 

Если есть хотя бы одна свободная неизвестная, такая что коэффициент ∆_j при ней в последнем уравнении системы (1) положителен, а в первых m уравнениях той же системы среди коэффициентов g_1j, g_2j, …g_mj при ней нет ни одного положительного, то задача линейного прогрмаммирования неразрешима в силу неограниченности линейной формы L=c₁x₁+c₂x₂+...c_nx_nна множестве неотрицательных решений системы ограничений

 

x₁ + g_1,m+1x_m+1 +... + g_1nx_n = h₁,

x₂ + g_2,m+1 x_m+1 +... + g_2nx_n = h₂, (2)

............

x_m + g_m,m+1 x_m+1 +... + g_mnx_n = h_m.

 

 

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

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

min = , то за разрешающее Ур-е берем r-е. как только мы получим новое базисное неотрицательное решение системы ограничений, придется это решение исследовать на оптимальность.

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

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