Исследование операций и методы оптимизации. Часть 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

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

Задачи многокритериальной оптимизации..................................................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