Исследование операций и методы оптимизации

Введение ..............................................................................................................5

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

1.1 Основные понятия и определения ..................................................................7

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

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

1.4 Прямые методы поиска минимума .................................................................15

1.4.1 Метод равномерного поиска .......................................................................15

1.4.2 Метод дихотомии ........................................................................................17

1.4.3 Метод золотого сечения ..............................................................................20

1.4.4 Метод Пауэлла ............................................................................................22

1.5 Методы, основанные на использовании производных ..................................26

1.5.1 Метод Ньютона ............................................................................................26

1.5.2 Метод средней точки ...................................................................................27

1.6 Решение задачи определения цены на товар ................................................ 29

1.7 Сравнение методов одномерной оптимизации .............................................. 31

2 Методы многомерной оптимизации функций ................................................... 33

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

2.1.1 Метод Гаусса .................................................................................................34

2.1.2 Симплексный метод ......................................................................................36

2.1.3 Метод Хука – Дживса ...................................................................................42

2.2 Градиентные методы ........................................................................................46

2.2.1 Градиентный спуск ........................................................................................49

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

2.2.3 Метод Ньютона .............................................................................................54

2.2.4 Задача определения параметров регрессии .................................................55

2.3 Глобальная оптимизация с помощью случайных величин ...............................56

2.4 Решение обратных задач с помощью обратных вычислений ..........................59

3 Линейное программирование ............................................................................73

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

3.2 Примеры задач линейного программирования .............................................. 78

3.2.1 Задача об использовании ресурсов (задача планирования производства) .. 78

3.2.2 Задача составления рациона (задача о диете, задача о смесях) .................. 83

3.2.3 Задача об использовании мощностей (задача о загрузке оборудования) .... 87

3.2.4 Задача о раскрое материалов ...................................................................... 88

3.2.5 Задача технического контроля ..................................................................... 90

3.2.6 Задача об оптимальном ассортименте .......................................................... 91

3.3 Решение задач линейного программирования ................................................ 92

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

3.3.2 Основы симплекс-метода .............................................................................. 96

3.3.3 Алгоритм симплекс-метода ............................................................................ 99

3.3.4 Поиск начального базиса ............................................................................. 110

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

4 Транспортная задача .......................................................................................... 125

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

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

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

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

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

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

5.1 Графический метод решения задач целочисленного программирования ........ 146

5.2 Метод Гомори ................................................................................................... 148

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

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

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

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

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

5.6 Метод Монте-Карло .......................................................................................... 170

6 Нелинейное программирование. Задачи с ограничениями в виде равенств........ 174

6.1 Метод замены переменных ............................................................................... 174

6.2 Метод множителей Лагранжа ............................................................................ 175

6.3 Решение обратной задачи с помощью метода множителей Лагранжа .............. 178

Заключение ............................................................................................................. 181

Литература............................................................................................................... 182

Список сокращений ................................................................................................. 183

Глоссарий ................................................................................................................. 184