Конспект лекций по линейному программированию. — Челябинск:
Издательство ЮУрГУ, 2001. — 59 с.
Пособие предназначено для студентов экономико-математических
специализаций. Цель данного курса - показать место и роль линейного
программирования при анализе и решении реальных задач. Основу
изложения составляет теория двойственности. Все основные алгоритмы
и результаты формируются в терминах этой теории. Использованный
математический аппарат не выходит за рамки стандартных курсов
математического анализа, линейной алгебры и аналитической геометрии
для студентов экономических специальностей вузов. По ходу изложения
материала ставятся задачи для практических занятий и внеаудиторной
работы.
Линейные модели планирования производства
Задача нахождения оптимального плана
Задача формирования равновесных цен на ресурсы
Геометрия линейного программирования
Выпуклые множества
Многогранные выпуклые множества
Двойственность в линейном программировании
Теорема Фаркаша и её варианты
Теоремы двойственности для канонической задачи
Отношение двойственности для задач линейного программирования
Теорема о дополняющей нежёсткости. Экономическая интерпретация двойственности
Геометрическая интерпретация двойственности
Симплекс метод
Симплекс-метод при известной вершине
Общий случай
Техника симплекс-таблиц для задач в стандартной форме
Пример численного решения задачи линейного программирования
Модифицированный симплекс-метод
Использование мультипликативного представления обратной матрицы
Прямодвойственный симплекс-метод
Прямодвойственный алгоритм для задачи о кратчайшем пути
ПРямодвойственный алгоритм для задач о максимальном потоке и минимальном разрезе
5. Дополнительная литература
Задача нахождения оптимального плана
Задача формирования равновесных цен на ресурсы
Геометрия линейного программирования
Выпуклые множества
Многогранные выпуклые множества
Двойственность в линейном программировании
Теорема Фаркаша и её варианты
Теоремы двойственности для канонической задачи
Отношение двойственности для задач линейного программирования
Теорема о дополняющей нежёсткости. Экономическая интерпретация двойственности
Геометрическая интерпретация двойственности
Симплекс метод
Симплекс-метод при известной вершине
Общий случай
Техника симплекс-таблиц для задач в стандартной форме
Пример численного решения задачи линейного программирования
Модифицированный симплекс-метод
Использование мультипликативного представления обратной матрицы
Прямодвойственный симплекс-метод
Прямодвойственный алгоритм для задачи о кратчайшем пути
ПРямодвойственный алгоритм для задач о максимальном потоке и минимальном разрезе
5. Дополнительная литература