Учебное пособие «Линейное программирование. Линейные задачи оптимизации»
Автор: Лутманов С.В.
Источник - Библиотека ПГНИУ
Объем - 128 страниц
Год издания - 2004
Описание
В учебном пособии рассматриваются линейные задачи оптимизации в конечномерных пространствах, обычно называемые задачами линейного программирования. Приводятся основные типы прикладных задач линейного программирования, описывается графический и симплекс - методы их решения, развивается теория двойственности в линейном программировании и исследуется возможность применения линейного программирования в теории игр. Весь излагаемый материал поясняется на примерах, большинство из которых решены с применением пакета MATHEMATIC 4.2. Пособие предназначено для студентов, магистрантов и аспирантов математических специальностей, изучающих курсы, связанные с вопросами оптимизации.
Содержание
ПРЕДИСЛОВИЕ……………………………………………………………5
1. ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА…………………………….. 7|
1.1.Пространство n R ………………………………………………………….. 7
1.2. Точки и подмножества пространства n R …………………………….... 7
1.3. Алгебраические линейные комбинации подмножеств n R ….……...... 10
1.4. Расстояние Хаусдорфа………………………………………………..... 13
1.5. Определение выпуклого множества. Примеры…………………..….... 14
1.6. Операции над выпуклыми множествами………………….………….. 16
1.7. Выпуклые оболочки……………………………….………………….... 18
1.8. Опорные функции и множества………………………….……………. 22
1.9. Определение выпуклой функции. Примеры………….………………. 24
1.10. Действия с выпуклыми функциями………………….……………….. 27
1.11. Критерии выпуклости гладких функций…………….……………….. 29
1.12. Минимум выпуклой функции………………………..……………….. 33
1.13. Проекция точки на множество……………………………..…………. 35
1.14. Отделимость точки и множества………………..……………………. 36
1.15. Отделимость выпуклых множеств………………………………….….. 38
1.16. Некоторые следствия из теорем об отделимости выпуклых множеств. ……………………………………………………………………. 41
2. ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ…………………………………………………..46
2.1. Общая задача линейного программирования………………………… 46
2.2. Каноническая и стандартная форма задачи линейного программирования…………………………………………………………... 48
2.3. Примеры прикладных задач линейного программирования………….51
3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ…………………………………………………. 56
3.1. Графический метод……………………………………………………... 56
3.2. Угловые точки допустимого множества канонической задачи……… 61
3.3 Обоснование симплекс-метода…………………………………………. 67
3.4. Алгоритм симплекс метода…………………………………………….. 72
3.5. Существование решения задачи линейного программирования…….. 76
3.6. Алгоритм решения канонической задачи линейного программирования ………………………………………………………….. 79
3.7. Решение задачи линейного программирования на ЭВМ……………. 88
4. ТЕОРИЯ ДВОЙСТВЕННОСТИ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ………………………………………………… 92
4.1. Двойственная задача к общей задаче линейного программирования.. 92
4.2. Функция Лагранжа для задачи линейного программирования….…... 98
4.3. Теоремы двойственности и равновесия ….…………………………. 105
5. ПРИМЕНЕНИЕ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ В ТЕОРИИ ИГР……………………………………………………………… 112
5.1. Общее описание антагонистической игры………………………….. 112
5.2. Седловая точка игры. Цена игры…………………………………….. 115
5.3. Матричные игры…………………………………………….………… 117
ЛИТЕРАТУРА………………………………………............................ 127