Федосеев В.В. и др. Экономико-математические методы и прикладные модели
Подождите немного. Документ загружается.
Основы линейного программирования
31
матическую подготовку экономистов. Для освоения задач и
методов в пределах данной главы необходимы знания ос-
новных понятий и элементов высшей математики, матрич-
ной и векторной алгебры. Некоторые необходимые сведе-
ния из этих разделов математики приведены ниже.
Матрицы и определители
Рассмотрим тхп действительных чисел, записанных в
виде прямоугольной таблицы из т строк и п столбцов:
А =
'13
*21
*22
Va„
Данная таблица чисел называется числовой матрицей
(в дальнейшем — просто матрицей). Числа ац, которые
входят в матрицу, называются ее элементами. Индексы i и
j элемента ац указывают соответственно номера строки и
столбца, в которых расположен элемент ац. Матрицу, содер-
жащую одну строку (или один столбец), называют также
вектор-строкой (или вектор-столбцом).
Матрица, все элементы которой равны нулю, называется
нулевой. Две матрицы называются равными, если числа
строк и столбцов одной из них равны соответственно чис-
лам строк и столбцов другой и элементы этих матриц, рас-
положенные на соответствующих местах, равны.
Матрицей, транспонированной к матрице А, называется
матрица вида:
А' =
а
п
«12
^
а
ы
°21
«22
а
2„
а )
т. е. — строками матрицы А' являются столбцы, а столбца-
ми — строки матрицы А.
32
Глава 2
Если число строк равно числу столбцов
(тп
= п), матрицу
называют квадратной матрицей порядка п.
Элементы оц,
a<ii,
«зз»---»
а
пп образуют так называемую
главную диагональ квадратной матрицы; элементы а\
п
, а2
П
-ъ
..., a
n
i — побочную диагональ квадратной матрицы.
Рассмотрим некоторые действия над матрицами.
1.
Произведением матрицы А на число
X,
(или, что то же
самое, числа X на матрицу А) называется матрица
Ы =
(Ха
п
Хд
2
1
Vtatml
Ха
12
Ад
2
2
'
ка
т2 •
•• Щп
•• k*2n
Ял„„
получающаяся из А путем умножения каждого ее элемента
на число X.
2.
Под суммой двух матриц
А =
а
п
«21
Umi
«12 •
«22
«m2 •
•• «lrc
•• «2л
a
mn
и В =
>21
КЬ
h2
&
22
ml
u
m2
b
2n
b
m.nJ
понимается матрица
A
+
B
«11 +
Ь
11 «12 +
&
12
«21
+
^21 «22
+
^22
V«ml +
6
ml «m2 +
b
m2
«In + hn
a
2n +
b
2n
+ K
элементы которой равны суммам соответствующих элемен-
тов матриц А и В. При этом подразумевается, что число
строк (столбцов) матрицы А равно числу строк (столбцов)
матрицы В. Подобным же образом определяется и разность
А-
В матриц А и В.
Основы линейного программирования
33
Линейные операции над матрицами подчиняются обыч-
ным законам арифметики, например:
А + В = В +А, А + 0 =А
(все элементы матрицы 0 — нули),
Х(А + В) = ХА + ХВ, 0-А = 0 (Х = 0).
3.
Произведением матрицы А из т строк и п столбцов на
матрицу Виз л строк и k столбцов называется матрица С =
АВ,
имеющая т строк и k столбцов, элемент Сц которой, рас-
положенный в i-й строке и /м столбце, равен сумме произве-
дений элементов i-й строки матрицы А на соответствующие
элементы ;-го столбца матрицы В, т.е. находится по формуле
скалярного произведения i-й вектор-строки| матрицы А на у'-й
вектор-столбец матрицы В:
Сц = а
п
Ьу + a
i2
b
2
j +•••+ a
in
b
n
j.
В случае квадратных матриц можно составить как произ-
ведение АВ, так и произведение ВА. В общем случае АВ
Ф
ВА,
т.е.
переместительный закон для матриц не выполняется.
Для произведения матриц остаются в силе следующие
законы арифметики:
1.
Распределительный закон (А + В) С
=
АС + ВС, С (А + В) =
= СА + СВ.
2.
Сочетательный закон (АВ) С
==
А (ВС).
Среди квадратных матриц особую роль играет матрица
(\ 0 ••• 0"|
\о о - I)
все элементы которой, расположенные на главной диагонали,
равны единице, а остальные — нулю. Можно проверить, что
для любой матрицы А: АЕ = ЕА = А. Матрица Е называется
единичной.
Матрица В называется обратной для матрицы А, если
АВ = ВА = Е. Матрица В, обратная матрице А, обозначается
через А
-1
.
С каждой квадратной матрицей определенным образом
связано некоторое число, называемое ее определителем.
34
Глава 2
Для вычисления определителя любого порядка необходимо
знание его свойств и теоремы о разложении определителя.
Приведем основные свойства определителей.
1.
При транспонировании матрицы ее определитель не
меняется. Это свойство свидетельствует о полном равнопра-
вии строк и столбцов определителя. Следовательно, если не-
которое утверждение справедливо относительно столбцов оп-
ределителя, то аналогичное утверждение справедливо и для
его строк.
2.
Если все элементы какого-либо столбца (строки) опреде-
лителя равны нулю, то и сам определитель равен нулю.
3.
При перестановке двух любых, столбцов (строк) опре-
делителя его знак меняется на противоположный, а абсо-
лютная величина остается неизменной.
4.
Определитель с двумя одинаковыми столбцами (строка-
ми) равен нулю.
5.
Если 7-й столбец (строка) Aj определителя D является
линейной комбинацией
Aj = ХВ +
\хС
двух произвольных столбцов (строк) В и С, то и сам опреде-
литель оказывается линейной комбинацией
D =
DjiTJB
+ цС) = Щ(В) + \iDj(C)
определителей Dj(B) и Dj(C).
Здесь Dj{B) и Dj(C) — определитель D, в котором столбец
(строка) j заменен соответственно на столбец (строку) В и
С. Остальные столбцы (строки) сохранены без изменения.
6. При умножении любого столбца (строки) определителя
на произвольное число X сам определитель умножается на
это же число.
7.
Если какой-либо столбец (строка) определителя явля-
ется линейной комбинацией других его столбцов (строк), то
определитель равен нулю.
8. Определитель не изменится, если к элементам любого
его столбца (строки) прибавить соответствующие элементы
другого столбца (строки), предварительно умноженные на
одно и то же число.
Основы линейного программирования
35
Рассмотрим определитель га-го порядка:
а
П
а
21
D
а
12
а
22
а
Г}
«2;
а
п
1
п1
Щ2
а
п2
а„
а.
nj
*пп
Выделим в нем некоторый элемент, например ац. Вы-
черкнем в определителе i-ю строку и у'-й столбец, в которых
расположен выделенный элемент ац. В результате останется
определитель (га - 1)-го порядка. Этот оставшийся определи-
тель называется минором элемента ац в определителе D и
обозначается Мц.
Величину Ац = (~1)
1+
>Мц называют алгебраическим до-
полнением элемента ац в определителе D (или в соответст-
вующей квадратной матрице).
Теорема о разложении определителя. Определитель мат-
рицы А равен сумме произведений всех элементов некоторого
столбца (строки) на их алгебраические дополнения:
п п
D
=
\A\
=
'ZatjAfj = Yu
a
n
A
n •
Рассмотрим примеры вычисления определителей (пред-
полагается знание правил вычисления определителей второго
порядка).
1.
Вычислить определитель
2 3 1
D = 4 2 -1 .
3 5 2
Разложим определитель D по элементам второго столбца:
D = ЗА\2 + 2А
2
2 + 5Л
3
2- Переходя к минорам, имеем:
D = 3(-1)
1+2
4 -1|
3 21
+ 2(-1)
2+2
2 1
13 2|
+ 5(-1)
3+2
= -3-11 + 2-1-5-(-6) = -1.
36
Глава 2
2.
Вычислить определитель четвертого порядка:
D
12 3 4
2 3 4 1
3 4 12
4 12 3
Используя свойства определителей, получим единичную
первую строку и разложим по ней определитель D; анало-
гично поступим с первым столбцом преобразованного опре-
делителя:
D
12 3 4
2 3 4 1
3 4 12
4 12 3
О О
-1 -2
-2 -8
О
-7
-10
4 -7 -10 -13
= (-D
(-If
l+i
-1
-2
-7
-2
-8
-10
-7
-10
-13
= -
12 7
2 8 10
7 10 13
4 -4
-4 -36
= -4-4
-1 1
1 9
2 7
4 -4
0 -4 -36
= -16(-9 -1)
= 16 • 10 =
160,
Решение систем линейных уравнений
Рассмотрим систему из п линейных уравнений с п неиз-
вестными (такие системы линейных уравнений называются
определенными):
а
п
х
х
+
а
12
х
2
+ ...+а
Хп
х
п
=Ь
г
,
a
2l*i +а
22
х
2
+ ...+ а
2п
х
п
= Ъ
2
,
а
п\Х\
+
о-
п2
х
2
+ ...+ а
пп
х
п
= Ь
п
.
(2.15)
Определитель А, составленный из коэффициентов при
неизвестных, называют определителем системы (2.15);
Основы линейного программирования
37
а
11
а
12
а
1п
А
=
а
п\
а
п2 '"
а
п
Решить систему уравнений (2.15) можно различными
методами, в частности, методом Крамера. В основе решения
системы уравнений (2.15) методом Крамера лежит следую-
щая теорема.
Теорема Крамера. Если определитель Л системы (2.15)
отличен от нуля, то система совместна и имеет единственное
решение, которое можно найти по формуле:
\,п .
В этой формуле Aj является определителем, полученным
из определителя системы А путем замены столбца j столб-
цом свободных членов.
Систему п линейных уравнений с п неизвестными (2.15)
можно записать в матричном виде: АХ = В, где А — квад-
ратная матрица порядка п, составленная из коэффициентов
при неизвестных; X — вектор-столбец из неизвестных; В —
вектор-столбец свободных членов:
4i
а
21
Um
а
12 *
а
22 '
а
п\
•
•• <*\п
•
а
2п
••
a
nJ
, в
=
№
ь
2
ybj
,х
=
(у \
х
2
UJ
Если А — невырожденная матрица, т.е. ее определитель
\А\
* 0 , то можно определить Л
-1
. С учетом этого имеют ме-
сто матричные соотношения:
А"
1
• АХ= А-
1
-В, Е-Х= А"
1
•
В, Х= А"
1
•
В. (2.16)
Обратная матрица может быть определена на базе сле-
дующей теоремы.
38
Глава
2
Теорема. Если определитель матрицы
А не
равен нулю,
то матрица А имеет обратную матрицу А
-1
, которая находится
по формуле
А"
1
= —
А ,
где А — матрица, присоединенная
к
матрице А.
А
Матрица
А
составляется
из
алгебраических дополнений
к элементам транспонированной матрицы:
^11
^21
А
12
А
22
U
1л
Нп
Л
л1
Таким образом, соотношение (2.16) лежит
в
основе реше-
ния системы уравнений (2.15) методом обратной матрицы.
Рассмотрим систему
т
линейных уравнений
с п
неиз-
вестными (при
т < п
такие системы называются неопреде-
ленными):
а
2\
х
\
+
а
22-*-2
+
• • •
+ а
2п
х
п
=
^2»
(2.17)
a
ml
x
l +
а
т2
х
2 +
• • •
+ ^тп
х
п ~
Ь
т-
или
в
векторной записи:
A
x
xi+
A
2
x
2
+...+ А
п
х
п
=В,
где
А
х
°21
\
a
mV
, А.2
=
Ч
2
Л
°22
\0-m2J
, ...,
А
п
м
а
2п
^•
a
mJ
,в
=
\ьЛ
ь
2
У
ь
т)
соответствующие вектор-столбцы.
Запишем расширенную матрицу этой системы
в
виде:
Основы линейного программирования
39
А,
Чх
а
2Х
^ml
Л "
а
Х2 •
°22 •
«т2 •
• К
-
<*,.
-
а
2п
•• а
тп
В
&х
ь
2
ъ
т
А =
Элементарными преобразованиями системы (2.17) (или
матрицы А) называются следующие преобразования:
• перестановка любых двух уравнений;
• умножение обеих частей одного из уравнений на любое
отличное от нуля число;
• прибавление к обеим частям одного уравнения соответ-
ствующих частей другого, умноженных на любое число,
отличное от нуля;
• вычеркивание нулевой строки (уравнения с нулевыми
коэффициентами и свободным членом, равным 0).
Можно показать, что элементарные преобразования пере-
водят данную систему уравнений в эквивалентную систему.
Две системы линейных уравнений называются эквивалент-
ными, или равносильными, если каждое решение первой
системы (если они существуют) является решением второй,
и наоборот. Соответствующие расширенные матрицы также
называются эквивалентными.
При практическом решении системы линейных уравне-
ний методом Жордана-Гаусса последовательно над строка-
ми матрицы А выполняют элементарные преобразования,
так что некоторое неизвестное исключается из всех уравне-
ний, кроме одного, т.е. в составе расширенной матрицы
формируется единичная матрица.
В процессе решения могут встретиться следующие случаи.
1.
Будет получена матрица А', эквивалентная матрице А, в
левой части некоторой строки ее стоят нули, а в правой —
число, отличное от нуля, что соответствует уравнению:
0*! + 0х
2
+ ... + 0х
п
= Ц , (Ь! * 0).
Это признак несовместности системы (2.17), т.е. система
не имеет решений.
40
Глава 2
2.
В результате преобразований получилась матрица А' вида:
'1 0 ••• О ЬС
О 1 ••• О Ъ'
2
\.0 0 - 1 К)
В этом случае система (2.17) совместна, определенная и
имеет единственное решение: х± = Ь{, х
2
= b
2
, ...,х
п
= Ъ'
п
.
3.
На некотором этапе получилась расширенная матрица вида
1
0
0
0
•
1
•
0 •
• 0
• 0
• 1
K
+
i
•
а
2г + 1
<
+
1 •
- <п
- *гп
- «С
Ч)
к
к)
Система совместна и имеет бесчисленное множество ре-
шений. Общее решение системы можно записать в виде:
Xi =Ь{- а{
г+1
х
г+1
-... - а{
п
х
п
*2
= ь
2 ~
a
2r+i
x
r+i -•••- а'2п
х
п
х
г
-
Ъ'
г
- a'
rr+1
x
r+l
-... - а'
гп
х
п
.
Придавая каждой из стоящих в правых частях равенств
переменных х
г+
\,
х
г+
2,
..-, х
п
произвольные значения, будем
получать частные решения системы.
Неизвестные х\, Х2,.-,х
г
называются базисными, или ос-
новными, они соответствуют линейно-независимым векто-
рам А\,
...,А
Г
.
Таким образом, любые г переменных называются базис-
ными (основными), если определитель матрицы коэффици-
ентов при них отличен от нуля, а остальные (п - г) перемен-
ных называются свободными, или неосновными. Базисным
решением системы уравнений называется частное решение,
в котором неосновные переменные имеют нулевые значе-
ния. Каждому разбиению на основные и неосновные пере-
А'
=