2 лабораторные работы по методу оптимизации

СОДЕРЖАНИЕ

1 Введение ............................................................................................................ 7

2 Поиск оптимального маршрута лодки....................................................... 8

2.1 Постановка задачи ...................................................................................... 8

2.2 Методы исключения интервалов ............................................................ 11

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

2.2.2 Метод деления отрезка пополам (метод дихотомии) ..................... 13

2.2.3 Метод Фибоначчи ............................................................................... 15

2.2.4 Метод золотого сечения..................................................................... 17

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

2.3.1 Квадратичная аппроксимация ........................................................... 20

2.3.2 Метод Пауэлла .................................................................................... 21

2.4 Методы с использованием производных ............................................... 25

2.4.1 Метод Ньютона – Рафсона ................................................................ 25

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

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

3 Проектирование канала наименьшей длины ......................................... 33

3.1 Постановка задачи .................................................................................... 33

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

3.2.1 Симплексный метод ........................................................................... 41

3.2.2 Метод поиска Хука – Дживса............................................................ 46

3.2.3 Метод сопряженных направлений Пауэлла..................................... 51

3.3 Градиентные методы и методы второго порядка ................................. 54

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

3.3.2 Метод Ньютона ................................................................................... 58

3.3.3 Модифицированный метод Ньютона ............................................... 60

3.3.4 Метод Марквардта.............................................................................. 63

3.3.5 Методы сопряженных градиентов .................................................... 66

3.3.6 Квазиньютоновские методы (методы с переменной метрикой).... 79

4

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

4.1 Постановка задачи .................................................................................... 90

4.2 Стандартная форма записи ЗЛП ............................................................. 92

4.3 Поиск начального базиса ......................................................................... 94

4.3.1 Метод Жордана – Гаусса ................................................................... 95

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

4.4 Графическое решение ЗЛП ................................................................... 100

4.5 Решение ЗЛП симплекс-методом ......................................................... 106

4.6 Целочисленное программирование ...................................................... 126

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

4.6.2 Метод Гомори ................................................................................... 129

5 Оптимизация плана доставки муки и хлеба ......................................... 133

5.1 Постановка задачи .................................................................................. 133

5.2 Сбалансированные и несбалансированные модели............................ 137

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

5.4 Решение транспортной задачи симплекс-методом ............................. 161

5.5 Решение транспортной задачи методом потенциалов ....................... 164

5.6 Задача о назначениях ............................................................................. 183

5.7 Венгерский метод решения задачи о назначениях ............................. 185

6 Определение наилучшего положения приемной антенны................. 193

6.1 Постановка задачи .................................................................................. 193

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

6.2.1 Метод замены переменных.............................................................. 199

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

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

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

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

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

второго порядка ............................................................................... 209

5

6.4 Методы штрафов .................................................................................... 211

6.4.1 Квадратичный штраф ....................................................................... 211

6.4.2 Логарифмический штраф................................................................. 216

6.4.3 Штраф типа обратной функции ...................................................... 218

6.4.4 Штраф типа квадрата срезки ........................................................... 220

6.5 Методы, основанные на линеаризации ................................................ 225

6.5.1 Базовый метод линеаризации .......................................................... 225

6.5.2 Алгоритм Франка – Вульфа............................................................. 230

6.5.3 Метод допустимых направлений Зойтендейка ............................. 234

6.5.4 Метод условного градиента............................................................. 243

6.6 Метод проекции градиента ................................................................... 252

6.6.1 Случай линейных ограничений....................................................... 252

6.6.2 Случай нелинейных ограничений................................................... 258

7 Краткий математический справочник .................................................. 261

7.1 Приближенные числа ............................................................................. 261

7.2 Уравнения и неравенства....................................................................... 265

7.2.1 Решение уравнений .......................................................................... 265

7.2.2 Решение систем уравнений ............................................................. 275

7.2.3 Доказательство неравенств.............................................................. 281

7.3 Векторы и матрицы ................................................................................ 286

7.3.1 Основные операции с матрицами ................................................... 290

7.3.2 Операции с квадратными матрицами ............................................. 296

7.3.3 Операции с векторами...................................................................... 304

7.4 Дифференцирование функций .............................................................. 307

7.4.1 Производная функции скалярного аргумента ............................... 308

7.4.2 Частные производные ...................................................................... 317

8 Контрольная работа ................................................................................... 327

8.1 Задание на контрольную работу ........................................................... 327

8.1.1 Анализ экстремальных задач .......................................................... 327

6

8.1.2 Одномерный поиск ........................................................................... 331

8.1.3 Функции многих переменных ......................................................... 339

8.1.4 Линейное программирование .......................................................... 351

8.1.5 Нелинейное программирование ...................................................... 376

8.2 Оформление работы ............................................................................... 385

9 Лабораторные работы ............................................................................... 387

9.1 Задание на лабораторную работу No 1 ................................................. 387

9.1.1 Одномерный поиск ........................................................................... 387

9.1.2 Многомерный поиск......................................................................... 390

9.2 Задание на лабораторную работу No 2 ................................................. 392

9.2.1 Линейное программирование .......................................................... 393

9.2.2 Нелинейное программирование ...................................................... 396

9.3 Работа в пакете Mathcad ........................................................................ 397

9.3.1 Интерфейс пакета Mathcad .............................................................. 398

9.3.2 Работа в редакторе документов....................................................... 403

9.3.3 Входной язык Mathcad ..................................................................... 408

9.3.4 Программирование в среде Mathcad............................................... 433

9.4 Тестирование .......................................................................................... 438

9.5 Оформление отчета ................................................................................ 442

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

Приложение А (обязательное) Образец титульного листа

контрольной работы ................................................................................. 444

Приложение Б (обязательное) Образец титульного листа

лабораторной работы ................................................................................ 445