Учебное пособие для специалистов, бакалавров и магистров
экономических специальностей. — М.: МИИТ, 2011. — 152 с.
Учебное пособие содержит теоретический материал, методику решения и
примеры экономико-математических моделей, решаемых методами
Линейного программирования. Задачи, представленные в пособии,
охватывают полный перечень вопросов применения данного раздела
прикладной математики для анализа современных экономических
ситуаций, требующих принятия оптимизационных решений. Предназначено
для студентов, магистров и аспирантов, изучающих математическое
моделирование экономических процессов.
Линейное программирование. Общие подходы.
Пояснение к теме. Понятие о задачах линейного программирования.
Приведение общей задачи линейного программирования к основной задаче этого метода.
Каноническая задача линейного программирования.
Симплекс алгоритм.
Примеры решения задач симплекс алгоритмом.
Симплекс метод решения основной задачи линейного программирования.
Пояснение к теме.
Нахождение допустимого решения системы ограничений.
Нахождение допустимого базисного решения.
Примеры решения задачи Линейного программирования симплекс методом.
Базовые примеры.
Применение замечания Вальда для упрощения расчетов при решении задач с помощью симплекс метода.
Упрощение применения симплекс метода при частичном преобразовании основной задачи линейного программирования в каноническую задачу Линейного программирования.
Понятие о симплекс-таблицах.
Метод «большого М» (М-метод).
Проблема возможного зацикливания симплекс-алгоритма.
Пояснение к теме
Симплексный способ преодоления зацикливания.
Преодоление зацикливания методом возмущения.
Задачи с ограниченными сверху неизвестными.
Пояснение к теме.
Видоизмененный симплекс-алгоритм для задач Линейного программирования с ограниченными сверху переменными.
Описание и обоснование алгоритма.
Пример решения задач с ограниченными сверху переменными.
Параметрическое Линейное программирование.
Пояснение к теме.
Постановка простейшей задачи параметрического Линейного программирования.
Методы решения задач параметрического Линейного программирования.
Некоторые обобщения.
Минимаксная задача Линейного программирования.
Модифицированный симплекс-метод.
Пояснение к теме. Матричная запись задачи Линейного программирования.
Геометрическая интерпретация задач Линейного программирования.
Геометрическая интерпретация задач Линейного программирования с двумя независимыми переменными.
Геометрическая интерпретация симплекс алгоритма.
Теория двойственности задач Линейного программирования.
Пояснение к теме.
Метод исключения Фурье-Моцкина.
Лемма Фаркаша.
Аффинная теорема Фаркаша.
Двойственные задачи Линейного программирования.
Теорема двойственности.
Задача, двойственная к задаче со смешанными ограничениями. Теорема о дополняющей нежесткости.
Двойственный симплекс-метод.
Прямодвойственный симплекс-метод.
Экономический смысл переменных в двойственной задаче Линейного программирования.
Связь линейного программирования с теорией матричных игр.
Матричные игры двух лиц.
Верхняя и нижняя цена игры. Матрица с седловой точкой.
Смешанные стратегии.
Доказательство основной теоремы теории матричных игр и сведение матричной игры к задаче линейного программирования.
Нахождение начального базисного плана. Пояснение к теме.
Пример нахождения оптимальных смешанных стратегий.
Сведение задачи Линейного программирования к матричной игре.
Транспортная задача линейного программирования.
Постановка классической транспортной задачи Линейного программирования.
Методы нахождения базисного плана.
Нахождение базисного плана диагональным методом.
Нахождение базисного плана методом наименьшей стоимости.
Методы улучшения базисного плана.
Идея распределительного метода.
Циклы пересчета в матрице.
Распределительный метод.
Пояснение к теме. Понятие о задачах линейного программирования.
Приведение общей задачи линейного программирования к основной задаче этого метода.
Каноническая задача линейного программирования.
Симплекс алгоритм.
Примеры решения задач симплекс алгоритмом.
Симплекс метод решения основной задачи линейного программирования.
Пояснение к теме.
Нахождение допустимого решения системы ограничений.
Нахождение допустимого базисного решения.
Примеры решения задачи Линейного программирования симплекс методом.
Базовые примеры.
Применение замечания Вальда для упрощения расчетов при решении задач с помощью симплекс метода.
Упрощение применения симплекс метода при частичном преобразовании основной задачи линейного программирования в каноническую задачу Линейного программирования.
Понятие о симплекс-таблицах.
Метод «большого М» (М-метод).
Проблема возможного зацикливания симплекс-алгоритма.
Пояснение к теме
Симплексный способ преодоления зацикливания.
Преодоление зацикливания методом возмущения.
Задачи с ограниченными сверху неизвестными.
Пояснение к теме.
Видоизмененный симплекс-алгоритм для задач Линейного программирования с ограниченными сверху переменными.
Описание и обоснование алгоритма.
Пример решения задач с ограниченными сверху переменными.
Параметрическое Линейное программирование.
Пояснение к теме.
Постановка простейшей задачи параметрического Линейного программирования.
Методы решения задач параметрического Линейного программирования.
Некоторые обобщения.
Минимаксная задача Линейного программирования.
Модифицированный симплекс-метод.
Пояснение к теме. Матричная запись задачи Линейного программирования.
Геометрическая интерпретация задач Линейного программирования.
Геометрическая интерпретация задач Линейного программирования с двумя независимыми переменными.
Геометрическая интерпретация симплекс алгоритма.
Теория двойственности задач Линейного программирования.
Пояснение к теме.
Метод исключения Фурье-Моцкина.
Лемма Фаркаша.
Аффинная теорема Фаркаша.
Двойственные задачи Линейного программирования.
Теорема двойственности.
Задача, двойственная к задаче со смешанными ограничениями. Теорема о дополняющей нежесткости.
Двойственный симплекс-метод.
Прямодвойственный симплекс-метод.
Экономический смысл переменных в двойственной задаче Линейного программирования.
Связь линейного программирования с теорией матричных игр.
Матричные игры двух лиц.
Верхняя и нижняя цена игры. Матрица с седловой точкой.
Смешанные стратегии.
Доказательство основной теоремы теории матричных игр и сведение матричной игры к задаче линейного программирования.
Нахождение начального базисного плана. Пояснение к теме.
Пример нахождения оптимальных смешанных стратегий.
Сведение задачи Линейного программирования к матричной игре.
Транспортная задача линейного программирования.
Постановка классической транспортной задачи Линейного программирования.
Методы нахождения базисного плана.
Нахождение базисного плана диагональным методом.
Нахождение базисного плана методом наименьшей стоимости.
Методы улучшения базисного плана.
Идея распределительного метода.
Циклы пересчета в матрице.
Распределительный метод.