Исследование операций и методы оптимизации в экономике. Часть 1. Лекционный курс

Введение 7

Тема 1. Линейное программирование 12

1.1. Постановка задачи линейного программирования 12

1.2 Примеры задач линейного программирования 13

Вопросы для самопроверки 19

Тема 2. Решение задач линейного программирования 20

2.1 Графический метод решения задач линейного программирования 20

2.2 Формы записи задач (ЗЛП) 21

2.3 Основы симплекс-метода 24

2.4. Алгоритм симплекс метода 26

2.5 Поиск начального базиса 31

2.5.1. Метод симплексного преобразования 32

2.5.2. Метод искусственного базиса 33

Вопросы для самопроверки 37

Тема 3. Двойственная задача линейного программирования 38

3.1 Постановка двойственной задачи 38

3.2 Свойства взаимно двойственных задач 39

3.3 Теоремы двойственности 40

Вопросы для самопроверки 45

Тема 4. Транспортная задача 46

4.1 Экономико – математическая модель транспортной задачи 46

4.2 Решение транспортной задачи симплексным методом 51

4.3 Первоначальное закрепление потребителей за поставщиками 52

4.4 Метод потенциалов 54

4.5 Улучшение оптимального плана перевозок (циклы перераспределения) 56

4.6 Открытая модель транспортной задачи 58

Вопросы для самопроверки 60

Тема 5. Целочисленное программирование 61

5.1 Графический метод решения ЗЦП 61

5.2 Метод Гомори (МГ) 62

5.2.1 Алгоритм МГ с использованием СМ 62

5.2.2. Решение частично целочисленных задач методом Гомори 65

5.3. Метод ветвей и границ 67

5.3.1 Алгоритм МВГ 71

5.4 Задача о назначениях 73

5.5 Задача о коммивояжере 74

5.6. Венгерский метод 75

Вопросы для самопроверки 78

Тема 6. Задачи многокритериальной оптимизации 79

6.1. Метод уступок 80

6.2. Метод справедливого компромисса 83

Вопросы для самопроверки 84

Тема 7. Методы оптимизации функций 85

7.1. Основные понятия и определения 85

7.2. Классификация задач оптимизации 88

7.3. Необходимые и достаточные условия существования экстремума 89

7.3.1 Скалярный случай

89

7.3.2 Векторный случай 89

7.3.3 Минимизация при ограничениях 90

7.4. Критерии останова 90

7.5. Характеристики алгоритмов оптимизации 91

Вопросы для самопроверки 92

Тема 8. Методы поиска экстремумов функции одной переменной 93

8.1 Прямые методы оптимизации 93

8.1.1 Метод равномерного поиска (МРП) 93

8.1.2 Метод деления отрезка пополам (МДОП) 93

8.1.3 Метод Фибоначчи (МФ) 94

8.1.4 Метод золотого сечения (МЗС) 95

8.2 Сравнение прямых методов оптимизации 96

8.3 Полиномиальная аппроксимация и методы точечного оценивания 97

8.3.1 Квадратичная аппроксимация 97

8.3.1 Метод Пауэлла 99

8.4 Методы с использованием производных 101

8.4.1 Метод Ньютона-Рафсона 101

8.4.2 Метод средней точки (поиск Больцано) 102

8.4.3 Другие методы поиска экстремума функций 103

8.4.4 Метод оптимизации с использованием кубичной аппроксимации 104

8.5 Сравнение методов одномерной оптимизации 106

Вопросы для самопроверки 106

Тема 9. Поиск экстремумов функции нескольких переменных (безусловная оптимизация) 108

9.1 Классификация методов безусловной оптимизации 108

9.2. Методы прямого поиска 108

9.2.1 Симплексный метод 109

9.2.2 Метод Хука-Дживса 111

9.3 Градиентные методы 113

9.3.1 Метод сопряженных направлений 114

9.3.2 Метод наискорейшего спуска (метод Коши) 118

9.3.3 Метод Ньютона (МН) 120

9.3.4 Модифицированный метод Ньютона 120

9.3.5 Метод Флетчера–Ривза (МФР) 121

9.3.6 Вариант Полака-Рибьера (МПР) 122

9.4 Квазиньютоновские методы (КМ) (методы с переменной метрикой) 123

9.4.1 Метод Дэвидона–Флетчера–Пауэлла (ДФП) 124

Вопросы для самопроверки 125

Тема 10. Нелинейное программирование 126

10.1. Задачи с ограничениями в виде равенств 126

10.1.1 Метод замены переменных (МЗП) 126

10.1.2 Метод множителей Лагранжа (ММЛ) 127

10.2. Необходимые и достаточные условия оптимальности задач

с ограничениями общего вида 129

Вопросы для самопроверки 131

Тема 11. Методы штрафов 132

11.1. Общая схема метода штрафов 132

11.2. Основные типы штрафов 132

11.2.1 Квадратичный штраф 133

11.2.1 Бесконечный барьер 133

11.2.3 Логарифмический штраф 134

11.2.4 Штраф типа обратной функции 134

11.2.5 Штраф типа квадрата срезки 135

11.3. Примеры использования штрафов 137

Вопросы для самопроверки 140

Тема 12. Квадратичное программирование 141

12.1. Задача квадратичного программирования 141

12.2 Задача выбора портфеля ценных бумаг 141

12.3. Условие Куна-Таккера для ЗКП 144

12.4 Решение ЗКП методом симплексного преобразовании коэффициентов уравнений 145

12.5 Метод решения ЗКП с помощью искусственного базиса 146

Вопросы для самопроверки 147

Тема 13. Модели динамического программирования 148

13.1. Общая постановка задачи динамического программирования 148

13.2. Принцип оптимальности и уравнения Беллмана 150

13.3. Задача о распределении средств между предприятиями 154

13.4. Задача об оптимальном распределении ресурсов между отраслями на лет

158

13.5. Задача о замене оборудования 161

Вопросы для самопроверки 166

Литература 167