Методы оптимальных решений

Екатеринбург
Издательство Уральского университета
2020

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ  
РОССИЙСКОЙ ФЕДЕРАЦИИ

УРАЛЬСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ  
ИМЕНИ ПЕРВОГО ПРЕЗИДЕНТА РОССИИ Б. Н. ЕЛЬЦИНА

МЕТОДЫ
ОПТИМАЛЬНЫХ
РЕШЕНИЙ

Учебное пособие

Рекомендовано методическим советом
Уральского федерального университета в качестве учебного пособия
для студентов вуза, обучающихся по направлениям подготовки
38.03.01 «Экономика», 38.03.05 «Бизнес-информатика»,
по специальностям 38.05.01 «Экономическая безопасность»,
38.05.02 «Таможенное дело»

УДК 
330.4(075.8)
ББК 
65.290+65.05я73

 
М54

ISBN 978-5-7996-2956-4 
© Уральский федеральный университет, 2020

М54
Методы оптимальных решений : учебное пособие / О. Я. Шевалдина, 
А. В. Зенков, О. Ю. Жильцова [и др.] ; под общ. ред. Е. А. Трофимовой ; Ми-
нистерство науки и высшего образования Российской Федерации, Уральский 
федеральный университет. —  Екатеринбург : Изд-во Урал. ун-та, 2020. — 187 с. : 
ил. —  100 экз. —  ISBN 978-5-7996-2956-4. —  Текст : непосредственный.

ISBN 978-5-7996-2956-4

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

УДК 330.4(075.8)
ББК 65.290+65.05я73

А в т о р ы:
О. Я. Шевалдина, А. В. Зенков, О. Ю. Жильцова,
Е. А. Трофимова, Д. В. Гилёв, Н. В. Кисляк

П о д  о б щ е й  р е д а к ц и е й
Е. А. Трофимовой

Ре ц е н з е н т ы:
отдел аппроксимации и приложений
Института математики и механики им. Н. Н. Красовского УрО РАН
(заведующий отделом доктор физико- математических наук А. Г. Бабенко);
Г. Б. Захарова, кандидат технических наук, ведущий научный сотрудник
научно- исследовательской части Уральского государственного
архитектурно- художественного университета

ОГЛАВЛЕНИЕ

Предисловие 
5
1.  Элементы линейной алгебры и ее приложения 
6
1.1.  Векторы. Действия с n-мерными векторами 
6
1.2.  Матрицы и определители 
9
1.3.  Ранг матрицы 
12
1.4.  Системы линейных алгебраических уравнений 
13
1.5. Метод Гаусса —  Жордана построения общего решения  
системы линейных уравнений 
15
1.6.  Обращение матриц методом Гаусса —  Жордана 
25
1.7.  Нахождение базиса системы векторов A1, A2, …, Am (Aj ∈ Rn) 
26
1.8.  Нахождение неотрицательного базисного решения 
31
1.9.  Линейная балансовая модель Леонтьева 
36
1.9.1.  Применение модели Леонтьева в планировании 
39
1.9.2.  Продуктивность балансовой модели 
40
1.9.3.  Процесс решения задачи средствами Microsoft Excel 
43
Задачи для самостоятельного решения 
50
2.  Общая задача линейного программирования и составление моделей задач 
математического программирования 
52
2.1.  Необходимость экономико-математического моделирования 
52
2.2.  Разные формы постановки задачи линейного программирования 
53
2.3. Правила перехода от одной формы задачи линейного программирования 
к другой 
56
2.4. Построение экономико-математических моделей, сводящихся к задачам 
линейного программирования 
57
Задачи для самостоятельного решения 
66
3.  Графическое решение задачи линейного программирования 
74
3.1.  Геометрическая интерпретация задачи 
74
3.2.  Реализация графического метода решения 
77

3.3.  Примеры графического решения задач линейного программирования 
78
Задачи для самостоятельного решения 
85
4.  Симплексный метод решения задач линейного программирования 
88
4.1.  Симплекс-метод 
88
4.2.  Теоретическое обоснование симплекс-метода 
89
4.3.  Алгоритм решения задачи симплексным методом 
95
4.4.  Альтернативный вариант оформления симплекс-метода 
98
4.5.  Симплекс-анализ 
99
4.6.  Метод искусственного базиса 
115
4.6.1.  М-метод 
116
4.6.2.  Вырожденность 
124
Задачи для самостоятельного решения 
129
5.  Теория двойственности в линейном программировании 
134
5.1.  Понятие двойственной задачи линейного программирования 
134
5.2.  Правила перехода от прямой задачи к двойственной 
136
5.3.  Теоремы двойственности и их экономический смысл 
141
5.4.  Анализ чувствительности задачи линейного программирования 
153
Задачи для самостоятельного решения 
156
6.  Транспортная задача 
160
6.1.  Постановка модели транспортной задачи 
160
6.2. Методы нахождения первоначального базисного решения транспортной 
задачи закрытого типа 
164
6.3. Критерий оптимальности базисного решения транспортной задачи и метод 
потенциалов 
171
6.4.  Решение транспортной задачи открытого типа 
179
6.5.  Применение транспортных моделей в экономических задачах 
180
Задачи для самостоятельного решения 
181

ПРЕДИСЛОВИЕ

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

1. ЭЛЕМЕНТЫ ЛИНЕЙНОЙ АЛГЕБРЫ  
И ЕЕ ПРИЛОЖЕНИЯ

1.1. Векторы. Действия с n-мерными векторами

Упорядоченная совокупность n действительных чисел a1, a2, …, an называется 
n-мерным вектором и обозначается a = (a1, a2, …, an). Числа 
,
1,
ia i
n
=
 
называются компонентами вектора а.
Два n-мерных вектора a = (a1, a2, …, an) и b = (b1, b2, …, bn) называются равными, 
если равны соответствующие компоненты векторов, то есть

 
1
1
2
2
,
,
,
.
n
n
a
b a
b
a
b
=
⇔
=
=
=
a
b


Нулевым вектором называют вектор 
(0,
, 0).
θ =


Суммой двух векторов a = (a1, a2, …, an) и b = (b1, b2, …, bn) называется вектор

 
(
)
1
1
2
2
,
,
,
.
n
n
a
b a
b
a
b
+
=
+
+
+
a
b


Для любого вектора а справедливо 
.
+
=
a
a
q

Произведением действительного числа l на вектор а называется вектор

 
(
)
1
2
,
,
,
.
n
a
a
a
λ = λ
λ
λ
a


Вектор (−1) · a называют вектором, противоположным а, и обозначают −а, 
таким образом:

 
( 1)
.
−
⋅
= −
a
a

С в о й с т в а  линейных операций над векторами:
1) a + b = b + a;
2) (a + b) + c = a + (b + c);
3) 
,
(
)
(
) ;
∀λ µ∈
λ µ
= λµ
R
a
a

4) 
,
(
)
;
∀λ µ∈
λ + µ
= λ + µ
R
a
a
a

5) 
(
)
;
∀λ∈
λ
+
= λ + λ
R
a
b
a
b

6) 
(0, 0,
, 0):
,
;
∃
=
+
=
∀
a
a
a

q
q

7) 
(
)
∀ ∃ −
a
a (противоположный вектор): 
(
)
;
+ −
= θ
a
a

8) 1
,
.
⋅
=
∀
a
a
a

Множество всех n-мерных векторов с введенными операциями сложения 
векторов и умножения вектора на число, удовлетворяющими свойствам 1–8 
(рассматриваемым как аксиомы), называется пространством арифметических 
векторов (n-мерным векторным пространством) и обозначается Rn.
Скалярное произведение двух n-мерных векторов a = (a1, a2, …, an) и b = (b1, 
b2, …, bn) определяется формулой

 
1 1
2 2
( , )
.
n n
a b
a b
a b
=
+
+
+
a b


Операция скалярного произведения векторов обладает следующими легко 
проверяемыми с в о й с т в а м и:
1) (a, b) = (b, a) (симметричность);
2) 
1
2
1
2
(
, )
(
, )
(
, )
+
=
+
a
a b
a b
a b  (аддитивность);
3) (
, )
( , )
( ,
)(
)
λ
= λ
=
λ
∀λ∈R
a b
a b
a
b
 (однородность);
4) ( , )
0,
( , )
0
≥
=
⇔
= θ
a a
a a
a
 (невырожденность).
Ненулевые векторы a и b называются ортогональными, если их скалярное 
произведение равно нулю, т. е. (a, b) = 0.
Система векторов называется ортогональной, если векторы этой системы 
попарно ортогональны.
Линейной комбинацией векторов a1, a2, …, as называется сумма произведе-
ний этих векторов на произвольные вещественные числа:

 
1
1
2
2
,
,
1, .
s
s
i
i
s
λ
+ λ
…+ λ
λ ∈
=
R
a
a
a

Числа 
1
2
,
,
,
s
λ λ … λ  называются коэффициентами линейной комбинации.
Система векторов a1, a2, …, as называется линейно зависимой, если найдутся 
такие числа 
1,
,
,
s
λ
λ

 одновременно не равные нулю, что

 
1
1
2
2
.
s
s
λ
+ λ
+…+ λ
=
a
a
a
q

В противном случае эта система называется линейно независимой, то есть

 
1
1
2
2
0,
1, .
s
s
i
i
s
λ
+ λ
…+ λ
= θ ⇔ λ =
=
a
a
a

Пусть Q —  произвольное множество арифметических векторов.
Упорядоченная система векторов 
1
2
{ ,
,
,
}
s
Q
…
⊂
e e
e
 называется базисом в Q, 
если:
1) система 
1
2
{ ,
,
,
}
s
…
e e
e
 линейно независима;
2) для любого вектора 
Q
∈
a
 существуют такие действительные числа li, что

 
1 1
2
2

1

.

s

s
s
i
i

i=
= λ
+ λ
…+ λ
=
λ
∑
a
e
e
e
e  
(1.1)

Формула (1.1) называется разложением вектора а по базису 
1
2
{ ,
,
,
}.
s
…
e e
e
 
Коэффициенты li называются координатами вектора а в базисе 
1
2
{ ,
,
,
}.
s

e e
e

Справедливы утверждения:
1. Разложение вектора a по базису 
1
2
{ ,
,
,
}
s

e e
e
 единственно.
2. Если система векторов 
n
Q ⊂ R  обладает базисами, то все они состоят 
из одинакового числа векторов, называемого рангом системы Q и обозначаемого 
rang(Q) = r(Q).
Максимальное число линейно независимых векторов системы Q равно рангу 
матрицы A (см. далее п. 1.3), составленной из компонент векторов этой системы.
3. Ранг пространства Rn равен n и называется размерностью этого про-
странства: n = dim Rn —  число векторов в любом базисе Rn.
4. Теорема Штейница*. Если каждый из векторов b1, b2, …, bm является 
линейной комбинацией векторов a1, a2, …, an и m > n, то векторы b1, b2, …, bm 
линейно зависимы.
Следствие. В любой системе n-мерных векторов не может быть более чем 
n линейно независимых векторов.
В качестве базиса в Rn можно взять систему единичных векторов {e1, e2, …, en},  
где

 

1

1

(1, 0,
, 0),
(0,1,
, 0),

(0, 0,
,1).
n

=


=



=







e
e

e

Этот базис называют каноническим (единичным).

Любому вектору 

1

:

n

n

k
k
k

a

=
∈
=∑
R
a
a
e  можно сопоставить координатный век-

тор-столбец вектора a в базисе {e1, e2, …, en}: 

1

2

n

a
a
A

a







= 









 и наоборот. То есть

 

1

2

1

:
.

n
n
k
k
k

n

a
a
a
A

a

=







∀ ∈
=
⇔
= 








∑
R

a
a
e

* Эрнст Штейниц (также Штайниц, 1871–1928) —  немецкий математик. Основные труды 
посвящены теории графов и топологии. Штейниц также внес фундаментальный вклад в теорию 
многогранников.

Также 
,
.
C
A
B
B
A
=
+
⇔
=
+
= λ ⇔
= λ
c
a
b
b
a

Каждый n-мерный вектор можно записать в виде линейной комбинации 
векторов канонического базиса с коэффициентами a1, …, an:

 
(
)
(
)
(
)
(
)
1
2
1
2
,
,
,
1,0,
,0
0,1,
,0
0,0,
,1
n
n
a
a
a
a
a
a
=
=
+
+
+
a






или

 

1

2
1
1
2
2
1
2

1
0
0
0
1
0 .

0
0
1

n
n
n

n

a
a
A
a E
a E
a E
a
a
a

a



 
 
 


 
 
 


 
 
 
=
=
+
+
=
+
+
+


 
 
 


 
 
 


 
 
 


 
 
 








Замечание. Следует различать компоненты вектора и его координаты. При 
этом, используя для них одинаковые обозначения, мы должны помнить, что координаты 
вектора совпадают с его компонентами только в каноническом базисе.
Приведем ряд утверждений.
1. Система векторов A1, A2, …, Am линейно зависима тогда и только тогда, 
когда хотя бы один из векторов является линейной комбинацией остальных, 
т. е. 
{1,
,
}:
j
m
∃ ∈


 
1
1
1
1
1
1
.
j
j
j
j
j
m
m
A
A
A
A
A
−
−
+
+
= β
+
+β
+β
+
+β



2. Если система векторов включает нулевой вектор, то она линейно зависима.
3. Если система векторов включает часть линейно зависимых векторов, 
то и вся система будет линейно зависимой.
Вопросы, связанные с нахождением базиса и ранга системы векторов  
A1, A2, …, 
(
),
n
m
i
A
A ∈R
 будут рассмотрены позже.

1.2. Матрицы и определители

Матрица чисел aij

 

11
1
1

1

1

A
A
,

j
n

i
ij
in
m n

m
mj
mn

a
a
a

a
a
a

a
a
a

×









=
= 

























состоящая из m строк и n столбцов, называется матрицей размера m × n. Числа 
aij называются ее элементами (индекс i указывает номер строки, индекс 

j —  номер столбца, на пересечении которых находится элемент). Используют 
сокращенную запись: A = (aij) = (aij)m, n.
При m = n матрица называется квадратной матрицей n-го порядка. Элементы 
a11, a22, …, ann квадратной матрицы n-го порядка образуют ее главную диагональ.
Матрица, состоящая из одного столбца (т. е. если n = 1) или из одной строки 
(т. е. если m = 1), называется вектором-столбцом (или, соответственно, вектором-
строкой):

 

1

2
1
2
A
,
( ,
,
,
).
n

n

a
a
b b
b

a







=
=









b



Квадратная матрица n-го порядка, у которой все элементы, находящиеся 
выше и ниже главной диагонали, равны нулю, называется диагональной.
Диагональная матрица называется единичной, если все ее элементы, расположенные 
на главной диагонали, равны единице.
Матрица любого размера называется нулевой, если все ее элементы равны 
нулю.
Две матрицы A = (aij) и B = (bij) размера m × n называются равными, если 
они совпадают поэлементно, то есть

 
,
1,
,
;
1,
, .
ij
ij
a
b
i
m j
n
=
=
=



Операция умножения матрицы A = (aij) на число λ∈R задается по правилу:

 
A
(
)
(
),
1,
,
;
1,
, ,
ij
ij
a
a
i
m j
n
λ
= λ
= λ
=
=



то есть при умножении матрицы на число l нужно каждый элемент матрицы A 
умножить на число l.
Операция сложения матриц A = (aij) и B = (bij) одного и того же размера 
m×n задается по правилу:

 
(
)
A
B
,
1,
,
;
1,
, .
ij
ij
a
b
i
m j
n
+
=
+
=
=



Матрица (−1) A = −A называется противоположной к А.
Матрица AT, полученная из матрицы А заменой строк на соответствующие 
столбцы, называется транспонированной к матрице А:

 

11
12
1
11
21
1

21
22
2
12
22
2
T

1
2
1
2

A
,
A
.

n
m

n
m

m
m
mn
n
n
mn

a
a
a
a
a
a
a
a
a
a
a
a

a
a
a
a
a
a













=
=


































Произведением матрицы A = (aij) размера m × n на матрицу B = (bij) размера 
n × l называется матрица C = (cij) размера m × l, каждый элемент cij которой равен 
сумме произведений элементов i-й строки матрицы А на соответствующие 
элементы j-го столбца матрицы В:

 

(
)

1

2
1
2

1 1
2
2

1

,
,
,

,
1,
,
;
1,
, .

j

j
ij
i
i
in

nj

n

i
j
i
j
in nj
ik
kj

k

b
b
c
a
a
a

b

a b
a b
a b
a b
i
m j
l

=







=
=









=
+
+
+
=
=
=
∑








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

 

11
12
1

21
22
2

1
2

A
.

n

n
n

n
n
nn

a
a
a
a
a
a

a
a
a

= ∆ =











Для вычисления определителей n-го порядка на практике используют 
теорему Лапласа*. Для ее рассмотрения введем некоторые понятия. Пусть дана 
квадратная матрица А n-го порядка.
Минором элемента aij квадратной матрицы A называется число Mij, равное 
определителю матрицы (n − 1)-го порядка, полученной из A вычеркиванием i-й 
строки и j-го столбца.
Алгебраическим дополнением Aij элемента aij матрицы A называется его 
минор, взятый со знаком (−1) i + j:

 
( 1)
.
i
j
ij
ij
A
M
+
= −

* Пьер-Симон, маркиз де Лаплас (1749–1827) —  французский математик, механик, физик 
и астроном; известен работами в области небесной механики, дифференциальных уравнений, 
один из создателей теории вероятностей. Лаплас состоял членом шести академий наук и ко-
ролевских обществ, в том числе Петербургской академии (1802), и членом Французского гео-
графического общества. Его имя внесено в список величайших ученых Франции, помещенный 
на первом этаже Эйфелевой башни.

Теорема 1.1 (теорема Лапласа о разложении определителя). Определитель 
квадратной матрицы порядка n равен сумме произведений элементов любой 
его строки (столбца) на их алгебраические дополнения:

 
1
1
2
2
1
A

n

n
i
i
i
i
in
in
ij
ij
j
a A
a A
a A
a A

=
= ∆ =
+
+
+
=∑


(разложение по элементам i-й строки, i = 1, …, m);

 
1
1
2
2

1

A

n

n
j
j
j
j
nj
nj
ij
ij

i

a A
a A
a A
a A

=
= ∆ =
+
+
+
=∑


(разложение по элементам j-го столбца, j = 1, …, n).
Квадратная матрица В называется обратной по отношению к матрице A 
того же порядка, если

 
AB
BA
E.
=
=

Обратная матрица обозначается символом A–1.
Матрица A называется невырожденной (неособенной), если ее определитель 
|A| ≠ 0.

1.3. Ранг матрицы

В матрице A = Am×n вычеркиванием каких-либо строк или столбцов можно 
получить квадратную матрицу порядка k × k. Определитель Mk такой матрицы 
называется минором k-го порядка, 
min( , ).
k
m n
≤

Рангом матрицы A = Am×n называется наивысший порядок r отличных 
от нуля миноров этой матрицы. Любой минор порядка r, отличный от нуля, 
называется базисным минором, если при этом все миноры порядка r + 1 равны 
нулю или таковых нет.
Ранг матрицы A обозначается rang A или r(A).
Очевидно, что в матрице может быть несколько разных базисных миноров, 
и все они имеют один и тот же порядок.
Столбцы и строки, на пересечении которых расположен базисный минор, 
называются базисными столбцами и строками.
Каждую строку (столбец) матрицы A = Am×n будем рассматривать как вектор 
из Rn(Rm).
Теорема 1.2. Ранг матрицы A равен рангу системы ее векторов-строк (векто-
ров-столбцов); при этом система векторов-строк (векторов-столбцов), содержащая 
базисный минор, образует базис в системе всех строк (столбцов) этой матрицы.
Назовем элементарными преобразованиями матрицы следующие операции: