Езу9у. Учебное пособие Рекомендовано методическим советом Уральского федерального университета в качестве учебного пособия для студентов вуза, обучающихся по направлениям подготовки
 Скачать 5.85 Mb.
|
|
Учебное пособие МЕТОДЫ ОПТИМАЛЬНЫХ РЕШЕНИЙ Екатеринбург Издательство Уральского университета 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 А в т о р ы: О. Я. Шевалдина, А. В. Зенков, О. Ю. Жильцова, Е. А. Трофимова, Д. В. Гилёв, Н. В. Кисляк П о д о б щ е й р е д а к ц и е й Е. А. Трофимовой Р е ц е н з е н т ы: отдел аппроксимации и приложений Института математики и механики им. Н. Н. Красовского УрО РАН (заведующий отделом доктор физико- математических наук А. Г. Бабенко); Г. Б. Захарова, кандидат технических наук, ведущий научный сотрудник научно- исследовательской части Уральского государственного архитектурно- художественного университета 3 ОГЛАВЛЕНИЕ Предисловие 5 1. Элементы линейной алгебры и ее приложения 6 1.1. Векторы. Действия с n-мерными векторами 6 1.2. Матрицы и определители 9 1.3. Ранг матрицы 12 1.4. Системы линейных алгебраических уравнений 13 1.5. Метод Гаусса — Жордана построения общего решения системы линейных уравнений 15 1.6. Обращение матриц методом Гаусса — Жордана 25 1.7. Нахождение базиса системы векторов A 1 , A 2 , …, A m (A j ∈ R n ) 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 5 ПРЕДИСЛОВИЕ Нередко нам приходится вырабатывать некоторую стратегию решения той или иной проблемы. Это касается и экономики. Как выработать наилучшее решение в сложной экономической ситуации? Каким образом получить мак- симальную прибыль, минимизировав затраты? Как добиться эффективного управления предприятием? На эти и многие другие вопросы можно ответить, применив особые приемы на стыке экономики и математики, которые называются «экономико-матема- тические методы». Именно им и будет посвящено данное учебное пособие, предназначенное для студентов-экономистов, аспирантов, преподавателей экономических дисциплин, предпринимателей, менеджеров и всех, кому ин- тересны способы решения проблем эффективного управления. Предпосылками написания данного пособия являлись необходимость си- стематизировать материал, накопленный при многолетнем прочтении лекций и проведении практических занятий у авторов данного пособия, а также воз- можность иметь полный комплект материалов, учитывающий новые разработки и обеспечивающий дисциплину «Методы оптимальных решений». Авторы пособия выработали свое особое видение на изложение экономико- математических методов, отказавшись везде, где это возможно, от громоздких математических доказательств, но при этом дополнив материал экономическими примерами, показывая прикладную значимость методов в современном мире. Данное учебное пособие написано в соответствии с требованиями государ- ственных образовательных стандартов, в его содержании учтены современные реалии и компетенции. 6 1. ЭЛЕМЕНТЫ ЛИНЕЙНОЙ АЛГЕБРЫ И ЕЕ ПРИЛОЖЕНИЯ 1.1. Векторы. Действия с n-мерными векторами Упорядоченная совокупность n действительных чисел a 1 , a 2 , …, a n назы- вается n-мерным вектором и обозначается a = (a 1 , a 2 , …, a n ). Числа , 1, i a i n = называются компонентами вектора а. Два n-мерных вектора a = (a 1 , a 2 , …, a n ) и b = (b 1 , b 2 , …, b n ) называются рав- ными, если равны соответствующие компоненты векторов, то есть 1 1 2 2 , , , n n a b a b a b = ⇔ = = = a b Нулевым вектором называют вектор (0, , 0). θ = Суммой двух векторов a = (a 1 , a 2 , …, a n ) и b = (b 1 , b 2 , …, b n ) называется вектор ( ) 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 7) ( ) ∀ ∃ − a a (противоположный вектор): ( ) ; + − = θ a a 8) 1 , ⋅ = ∀ a a a Множество всех n-мерных векторов с введенными операциями сложения векторов и умножения вектора на число, удовлетворяющими свойствам 1–8 (рассматриваемым как аксиомы), называется пространством арифметических векторов (n-мерным векторным пространством) и обозначается R n Скалярное произведение двух n-мерных векторов a = (a 1 , a 2 , …, a n ) и b = (b 1 , b 2 , …, b n ) определяется формулой 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. Система векторов называется ортогональной, если векторы этой системы попарно ортогональны. Линейной комбинацией векторов a 1 , a 2 , …, a s называется сумма произведе- ний этих векторов на произвольные вещественные числа: 1 1 2 2 , , 1, . s s i i s λ + λ …+ λ λ ∈ = R a a a Числа 1 2 , , , s λ λ … λ называются коэффициентами линейной комбинации. Система векторов a 1 , a 2 , …, a s называется линейно зависимой, если найдутся такие числа 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 существуют такие действительные числа l i , что 1 1 2 2 1 s s s i i i= = λ + λ …+ λ = λ ∑ a e e e e (1.1) 8 Формула (1.1) называется разложением вектора а по базису 1 2 { , , , }. s … e e e Коэффициенты l i называются координатами вектора а в базисе 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. Ранг пространства R n равен n и называется размерностью этого про- странства: n = dim R n — число векторов в любом базисе R n 4. Теорема Штейница * . Если каждый из векторов b 1 , b 2 , …, b m является линейной комбинацией векторов a 1 , a 2 , …, a n и m > n, то векторы b 1 , b 2 , …, b m линейно зависимы. Следствие. В любой системе n-мерных векторов не может быть более чем n линейно независимых векторов. В качестве базиса в R n можно взять систему единичных векторов {e 1 , e 2 , …, e n }, где 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 в базисе {e 1 , e 2 , …, e n }: 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) — немецкий математик. Основные труды посвящены теории графов и топологии. Штейниц также внес фундаментальный вклад в теорию многогранников. 9 Также , C A B B A = + ⇔ = + = λ ⇔ = λ c a b b a Каждый n-мерный вектор можно записать в виде линейной комбинации векторов канонического базиса с коэффициентами a 1 , …, a n : ( ) ( ) ( ) ( ) 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. Система векторов A 1 , A 2 , …, A m линейно зависима тогда и только тогда, когда хотя бы один из векторов является линейной комбинацией остальных, т. е. {1, , }: j m ∃ ∈ 1 1 1 1 1 1 j j j j j m m A A A A A − − + + = β + + β + β + + β 2. Если система векторов включает нулевой вектор, то она линейно зависима. 3. Если система векторов включает часть линейно зависимых векторов, то и вся система будет линейно зависимой. Вопросы, связанные с нахождением базиса и ранга системы векторов A 1 , A 2 , …, ( ) , n m i A A ∈R будут рассмотрены позже. 1.2. Матрицы и определители Матрица чисел a ij 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. Чис- ла a ij называются ее элементами (индекс i указывает номер строки, индекс 10 j — номер столбца, на пересечении которых находится элемент). Используют сокращенную запись: A = (a ij ) = (a ij ) m, n При m = n матрица называется квадратной матрицей n-го порядка. Элементы a 11 , a 22 , …, a nn квадратной матрицы n-го порядка образуют ее главную диагональ. Матрица, состоящая из одного столбца (т. е. если n = 1) или из одной строки (т. е. если m = 1), называется вектором-столбцом (или, соответственно, векто- ром-строкой): 1 2 1 2 A , ( , , , ). n n a a b b b a = = |