Оптимизация и математические методы принятия решений, Сеславин А.И., Сеславина Е.А., 2011

Оптимизация и математические методы принятия решений, Сеславин А.И., Сеславина Е.А., 2011.
 
   Учебное пособие содержит теоретический материал, методику решения и примеры экономико-математических моделей, решаемых методами Линейного программирования. Задачи, представленные в пособии, охватывают полный перечень вопросов применения данного раздела прикладной математики для анализа современных экономических ситуаций, требующих принятия оптимизационных решений. Предназначено для студентов, магистров и аспирантов, изучающих математическое моделирование экономических процессов.

Симплексный способ преодоления зацикливания.
Пусть на некотором этапе симплекс алгоритма коэффициент с, в линейной форме - отрицателен и существуют ограничения, правые части которых положительны. Заметим, что все правые части ни на каком этапе симплекс алгоритма не могут стать одновременно нулевыми. Это следует из того, что уравнение с разрешающим элементом на предыдущем этапе симплекс алгоритма преобразуется в уравнение с положительной правой частью. Далее, укажем, что если все коэффициенты aki, с которыми входит свободное переменное xi в вырожденные уравнения, отрицательны, то разрешающий элемент будет выбран в невырожденных уравнениях и шаг симплекс алгоритма сразу приведет к уменьшению функции L. Если же среди указанных коэффициентов aki, найдется положительный, то сразу сделать такой шаг невозможно, а следует прибегнуть к следующей процедуре. Выделим из системы ограничений те, в правых частях которых находятся нули.
Разделим каждое из этих уравнений на xi и перенесем aki, в правые части. В тех случаях, когда отрицательны, умножим соответствующие уравнения на -1. К полученной новой системе ограничений присоедини и L без аддитивной константы, но разделенную на xi. Будем искать решение во вновь полученной задаче линейного программирования с помощью симплекс метода. Возможны два варианта. В первом - у задачи нет допустимого решения. Тогда, нет допустимого решения и в исходной задаче линейного программирования.
Содержание
ЧАСТЬ 1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ. ОБЩИЕ ПОДХОДЫ
1. Пояснение к теме. Понятие о задачах линейного программирования
2. Приведение общей задачи линейного программирования к основной задаче этого метода
3. Каноническая задача линейного программирования
4. Симплекс алгоритм
5. Примеры решения задач симплекс алгоритмом
6. Симплекс метод решения основной задачи линейного программирования
6.1 Пояснение к теме
6.2 Нахождение допустимого решения системы ограничений
6.3 Нахождение допустимого базисного решения
7. Примеры решения задачи линейного программирования симплекс методом
7.1 Базовые примеры
7.2 Применение замечания Вальда для упрощения расчетов при решении задач с помощью симплекс метода
7.3 Упрощение применения симплекс метода при частичном преобразовании основной задачи линейного программирования в каноническую задачу Линейного программирования
7.4 Понятие о симплекс-таблицах
7.5 Метод «большого М» (М-метод)
8. Проблема возможного зацикливания симплекс алгоритм
8.1 Пояснение к теме
8.2 Симплексный способ преодоления зацикливания
8.3 Преодоление зацикливания методом возмущения
9. Задачи с ограниченными сверху неизвестными
9.1 Пояснение к теме
10. Видоизмененный симплекс алгоритм для задач линейного программирования ограниченными сверху переменными
10. 1 Описание и обоснование алгоритма
10.2 Пример решения задач с ограниченными сверху переменными
11. Параметрическое Линейное программирование
11.1 Пояснение к теме
11.2 Постановка простейшей задачи параметрического линейного программирования
11.3 Методы решения задач параметрического линейного программирования
11.4. Некоторые обобщения
12. Минимаксная задача линейного программирования
13. Модифицированный симплекс метод
13.1 Пояснение к теме. Матричная запись задачи Линейного программирования
14. Геометрическая интерпретация задач Линейного программирования
14.1 Геометрическая интерпретация задач Линейного программирования с двумя независимыми переменными
14.2 Геометрическая интерпретация симплекс алгоритма
15. Теория двойственности задач Линейного программирования
15.1 Пояснение к теме
15.2. Метод исключения Фурье-Моцкина
15.3. Лемма Фаркаша
15.4. Аффинная теорема Фаркаша
15.5. Двойственные задачи Линейного программирования
15.6. Теорема двойственности
15.7. Задача, двойственная к задаче со смешанными ограничениями. Теорема о дополняющей нежесткости
15.8. Двойственный симплекс-метод
15.9. Прямодвойственный симплекс метод
15.10. Экономический смысл переменных в двойственной задаче Линейного программирования
16. Связь линейного программирования с теорией матричных игр.
16.1 Матричные игры двух лиц
16.2 Верхняя и нижняя цена игры. Матрица с седловой точкой
16.3. Смешанные стратегии
16.4. Доказательство основной теоремы теории матричных игр и сведение матричной игры к задаче линейного программирования
16.5 Нахождение начального базисного плана. Пояснение к теме
16.6. Пример нахождения оптимальных смешанных стратегий
16.7. Сведение задачи Линейного программирования к матричной игре
ЧАСТЬ 2. ТРАНСПОРТНАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИPOBАНИЯ
1. Постановка классической транспортной задачи Линейного программирования
2. Методы нахождения базисного плана
2.1. Нахождение базисного плана диагональным методом
2.2. Нахождение базисного плана методом наименьшей стоимости
3. Методы улучшения базисного плана
3.1. Идея распределительного метода
3.2. Циклы пересчета в матрице
3.3. Распределительный метод
3.4. Связь распределительного метода с симплекс-алгоритмом
3.5. Метод потенциалов
3.6 Алгоритм построения цикла пересчета
3.7. Замечание о целочисленности решения транспортной задачи
3.8. Особенности решения вырожденных транспортных задач
3.9. Способы преодоления вырожденности
4. Другие виды транспортной задачи
4.1. Несбалансированная транспортная задача
4.2. Транспортная задача с запрещенными коммуникациями
4.3. Многопродуктовая транспортная задача
4.3.1. Постановка задачи
4.3.2. Сведение многопродуктовой транспортной задачи к однопродуктовой
4.4. Задача с ограничениями на пропускные способности
4.4.1. Проблема нахождения опорного плана
5. Задача о назначениях
5.1. Пояснения к теме
5.2. Приведение задачи о назначениях к стандартному виду транспортной задачи
6. Транспортная задача по критерию времени
6.1. Пояснение к теме
6.2. Метод решения транспортной задачи по критерию времени
6.3. Пример решения транспортной задачи по критерию времени
6.4. Минимаксная задача о назначениях
Литература.