| Предисловие к серии «Учебник Школы прикладной математики и информатики МФТИ» | 6
|
| Предисловие | 8
|
| Глава 1. Общая теория | 9
|
| 1.1. Введение | 9
|
| 1.2. Выпуклые множества | 10
|
| 1.3. Аффинные подпространства | 14
|
| 1.4. Теорема Каратеодори | 18
|
| 1.5. Теоремы Радона и Хелли | 22
|
| 1.6. Теоремы отделимости | 26
|
| 1.7. Вторая теорема отделимости в конечномерном случае | 28
|
| 1.8. Аффинная независимость. Симплексы | 29
|
| 1.9. Относительная внутренность. Первая теорема отделимости в конечномерном случае | 33
|
| 1.10. Выпуклые функции | 36
|
| 1.11. Теорема Каруша—Куна—Таккера | 39
|
| 1.12. Субдифференциал | 43
|
| 1.13. Теорема Ферма в субдифференциальной форме | 46
|
| 1.14. Субдифференциальное исчисление. Теорема Моро—Рокафеллара | 48
|
| 1.15. Теорема Дубовицкого—Милютина | 52
|
| 1.16. Субдифференциальная форма теоремы Каруша—Куна—Таккера | 55
|
| 1.17. Двойственность выпуклых множеств | 57
|
| 1.18. Двойственность выпуклых функций | 58
|
| 1.19. Сопряженные функции. Преобразование Лежандра—Фенхеля—Юнга | 61
|
| 1.20. Двойственность экстремальных задач | 65
|
| Глава 2. Линейное программирование | 67
|
| 2.1. Задача линейного программирования в нормальной форме и двойственная к ней | 67
|
| 2.2. Конус. Замкнутость конечнопорожденного конуса | 68
|
| 2.3. Существование решения задачи линейного программирования и двойственной к ней | 71
|
| 2.4. Теорема о двойственности в задаче линейного программирования | 73
|
| 2.5. Различные формы задач линейного программирования и соответствующие двойственные задачи | 75
|
| 2.6. Задача линейного программирования со смешанными ограничениями | 78
|
| 2.7. Выпуклый анализ и теория линейных неравенств | 80
|
| 2.8. Крайние точки в задаче линейного программирования | 83
|
| 2.9. Симплекс-метод решения задач линейного программирования | 87
|
| 2.10. Пример применения симплекс-метода | 95
|
| 2.11. Метод искусственного базиса [-0.2pt]для нахождения начальной крайней точки | 96
|
| 2.12. Примеры задач линейного программирования | 100
|
| 2.12.1. Задача оптимального планирования производства | 100
|
| 2.12.2. Транспортная задача | 101
|
| 2.12.3. Задача на минимакс | 102
|
| 2.13. Транспортная задача | 103
|
| 2.14. Свойства транспортной задачи | 107
|
| 2.15. Методы нахождения начальной крайней точки в транспортной задаче | 109
|
| 2.15.1. Метод «северо-западного угла» | 110
|
| 2.15.2. Минимум по матрице | 113
|
| 2.15.3. Минимум по строке | 115
|
| 2.15.4. Минимум по столбцу | 117
|
| 2.16. Задача, двойственная к транспортной задаче. Метод потенциалов | 120
|
| 2.17. Алгоритм решения транспортной задачи с помощью метода потенциалов | 126
|
| Глава 3. Дополнения | 133
|
| 3.1. Наилучшее приближение в линейном нормированном пространстве | 133
|
| 3.2. Наилучшее равномерное приближение многочленами. Теорема Чебышева | 134
|
| 3.3. Многочлены Чебышева | 138
|
| Литература | 140
|
| Предметный указатель | 141
|
Курс выпуклого анализа читается студентам третьего курса факультета управления и прикладной математики МФТИ в осеннем семестре. Он является первой частью курса оптимизации, который продолжает читаться в последующих семестрах. Свойство выпуклости позволяет проще решать оптимизационные задачи. Этим объясняется появление этой темы в самом начале рассмотрения задач оптимизации. Более того, на примере выпуклых задач ярко демонстрируется принцип двойственности, при котором каждой оптимизационной задаче ставится в соответствие некоторая другая, называемая двойственной. Совместное рассмотрение этих двух задач позволяет глубже изучить их свойства и получить решения, как правило, и той, и другой. Оптимизационные выпуклые задачи находят много применений на практике, в частности, в экономике. Поэтому в читаемом курсе уделяется достаточно внимания задачам линейного программирования.
В основе предлагаемого пособия лежат лекции, которые автор читал на механико-математическом факультете
МГУ и на факультете управления и прикладной математики МФТИ. При написании пособия автор систематически обращался к работам своих коллег Г. Г. Магарил-Ильяева, В. М. Тихомирова [5] и Э. М. Галеева [2], которым глубоко благодарен за ценные обсуждения и советы.
Осипенко Константин Юрьевич
Доктор физико-математических наук, профессор кафедры общих проблем управления механико-математического факультета МГУ имени М. В. Ломоносова. Читает курсы лекций по выпуклому анализу, вариационному исчислению и оптимальному управлению на механико-математическом факультете МГУ и на кафедре математических основ управления МФТИ. Область научных интересов: теория приближений, теория оптимального восстановления. Автор более 160 научных работ.
