RUS ENG

Методы оптимизации

Методы оптимизации: пособие / Р. Габасов [и др.]. - Минск : Издательство «Четыре четверти», 2011. —472 с.: ил. Авторы: Р. Габасов, Ф. М. Кириллова, В. В. Альсевич, А. И. Калинин, В. В. Крахотко, Н. С. Павленок.

Данное пособие является третьим изданием (первые два вышли в 1975 и 1981 гг.) аналогичного пособия. По сравнению с предыдущими здесь переработаны все темы. В частности, глава «Линейное программирование» полностью ориентирована на симплекс-метод для задач с двухсторонними прямыми ограничениями. В главе, посвященной выпуклому программированию, помимо задач оптимизации приводятся основы выпуклого анализа, в том числе негладкого. Расширена тематика задач оптимального управления, в которой рассматриваются задачи в различных классах управляющих воздействий, в том числе синтез оптимальных систем. Все утверждения снабжены подробными доказательствами, а каждая тема — набором модельных примеров, иллюстрирующих доказанные результаты.

Рассчитано на студентов математического и экономического профиля. Рекомендуется также преподавателям, аспирантам, специалистам, работающим в области приложений математики.


Оглавление

ПРЕДИСЛОВИЕ

4

ВВЕДЕНИЕ

5

Литература

15

Глава 1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

16

§ 1. Симплекс-метод

16

1.1. Производственная задача

16

1.2. Графический метод решения задач ЛП

17

1.3. Каноническая задача ЛП

21

1.4. Базисный план

24

1.5. Потенциалы и оценки

26

1.6. Критерий оптимальности

27

1.7. Итерация симплекс-метода

30

1.8. Алгоритм

34

1.9. Первая фаза

37

   

1.10. Конечность симплекс-метода

52

1.11. Три свойства канонической задачи

53

1.12. Задача произвольной формы

53

§ 2. Двойственный симплекс-метод

55

2.1. Двойственная каноническая задача

55

2.2. Базисные двойственный план и псевдоплан

59

2.3. Теория двойственности

65

2.4. Критерий оптимальности базисного двойственного плана

71

2.5. Итерация

75

2.6. Алгоритмы двойственного симплекс-метода

81

2.7. Вырожденный базисный двойственный план

85

2.8. Первая фаза

88

2.9. Задача ЛП в произвольной форме

90

2.10. Конечность двойственного симплекс-метода

93

§3. Анализ решения

93

3.1. Единственность оптимального прямого плана

93

3.2. Единственность оптимального двойственного плана

94

3.3. Анализ чувствительности решения задачи

95

3.4. Коррекция оптимальных планов при возмущении задач ЛП

99

3.5. Изменение размеров задачи

100

3.6. Нестационарные задачи

104

§ 4. Специальные задачи

105

4.1. Сетевая транспортная задача

106

4.2. Матричные транспортные задачи

124

§ 5. Некоторые приложения ЛП

138

5.1. Задачи на минимакс

138

5.2. Кусочно-линейная экстремальная задача

139

5.3. Приложение к исследованию линейных соотношений

141

5.4. Линейное программирование и матричные игры. Теорема о минимаксе

144

5.5. Задача о максимальном потоке

147

Литература

149

Глава 2. ВЫПУКЛОЕ ПРОГРАММИРОВАНИЕ

150

§ 6. Выпуклые множества и функции

151

6.1. Выпуклые множества

151

6.2. Отделимость выпуклых множеств

154

6.3. Выпуклые функции

160

6.4. Дифференцируемость выпуклых функций

175

6.5. Экстремумы выпуклых функций

179

§ 7. Основная задача выпуклого программирования. Теорема Куна - Таккера

181

7.1 Постановка задачи

181

7.2. Теорема Куна - Таккера

182

7.3. Задача ВП с линейными ограничениями

184

§ 8. Теория двойственности в выпуклом программировании

186

8.1. Двойственная задача

187

8.2. Соотношения двойственности

187

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

189

8.4. Задача геометрического программирования

190

§ 9. Общая задача квадратичного программирования

193

9.1. Каноническая задача КП

194

9.2. Графоаналитический метод

197

9.3. Алгоритм решения простой задачи квадратичного программирования

207

9.4. Алгоритм решения общей задачи квадратичного программирования

216

§ 10. Специальные методы численного решения задач выпуклого программирования

223

10.1. Непрямые методы

224

10.2. Прямые методы

225

Литература

231

Глава 3. НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

232

§ 11. Конечномерные экстремальные задачи

232

§ 12. Задача безусловной оптимизации

234

12.1. Необходимое условие минимума первого порядка

234

12.2. Условия оптимальности второго порядка

236

§ 13. Задачи с простыми ограничениями

238

§ 14. Задача со смешанными ограничениями

240

14.1. Обобщенное правило множителей Лагранжа

240

14.2. Классическое правило множителей Лагранжа

245

14.3. Условно стационарные и нормальные планы

247

14.4. Условия минимума второго порядка

250

14.5. Линейные ограничения

254

14.6. Общая схема исследования задачи НЛП

256

§ 15. Негладкие задачи

258

15.1. Минимизация функций, дифференцируемых по направлениям

258

15.2. Производная и субдифференциал Кларка

263

§ 16. Векторная оптимизация

265

16.1. Принципы выбора

265

16.2. Скаляризация критерия

266

16.3. Введение иерархии целевых функций

267

Литература

269

ГЛАВА 4. ЧИСЛЕННЫЕ МЕТОДЫ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

270

§ 17. Минимизация функций одной переменной

271

17.1. Поиск точек безусловного минимума. Метод Пауэлла

271

17.2. Методы поиска точек минимума унимодальных функций

273

17.3. Метод ломаных

279

§ 18. Безусловная минимизация функций

282

18.1. Методы градиентного типа

282

18.2. Метод Ньютона

285

§ 19. Условная минимизация функций

287

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

287

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

288

19.3. Метод модифицированных функций Лагранжа

289

19.4. Метод штрафных функций

291

Литература

292

ГЛАВА 5. ДИСКРЕТНОЕ ПРОГРАММИРОВАНИЕ

294

§ 20. Методы ветвей и границ

294

20.1. Постановка задачи дискретного программирования

294

20.2. Общая схема методов ветвей и границ

295

§ 21. Задача о рюкзаке

297

§ 22. Целочисленное линейное программирование

301

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

301

22.2. Метод отсечения Гомори

305

§ 23. Метод вариаций. Задача минимизации штрафов

309

Литература

311

ГЛАВА 6. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

312

§ 24. Оптимизация многошаговых процессов

312

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

312

24.2. Инвариантное погружение. Функция Беллмана

313

24.3. Принцип оптимальности. Уравнение Беллмана

314

24.4. Анализ результатов

315

24.5. Стандартная процедура

316

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

318

§ 25. Задача распределения ресурсов

320

§ 26. Построение кратчайшего пути на сети

324

§ 27. Задача сетевого планирования

327

Литература

330

ГЛАВА 7. ВАРИАЦИОННОЕ ИСЧИСЛЕНИЕ

331

§ 28. Основная задача вариационного исчисления

331

28.1. Задача о брахистохроне

331

28.2. Основная задача

332

28.3. Другие задачи вариационного исчисления

334

§ 29. Метод вариаций

335

29.1. Вариация допустимой кривой

335

29.2. Вариации функционала

336

29.3. Необходимые условия слабого минимума в терминах вариаций функционала

337

29.4. Уравнение Эйлера

338

29.5. Теорема Гильберта

341

29.6. Кусочно-гладкие допустимые кривые

342

§ 30. Исследование второй вариации

345

30.1. Присоединенная задача о минимуме

345

30.2. Условие Лежандра - Клебша

346

30.3. Условие Якоби

347

Литература

350

ГЛАВА 8. ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ

351

§ 31. Задача предельного быстродействия

351

31.1. Оптимальное по быстродействию управление механическим объектом

351

31.2. Сравнение задачи быстродействия с задачей о брахистохроне

352

31.3. Математическая модель задачи предельного быстродействия

353

§ 32. Принцип максимума

354

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

354

32.2. Существование оптимальных программ

355

32.3. Формула приращения критерия качества

359

32.4. Необходимое условие оптимальности программ (принцип максимума Понтрягина)

361

32.5. Достаточное условие оптимальности

363

32.6. Задачи оптимального управления с терминальными ограничениями

366

32.7. Принцип максимума для задач быстродействия

376

32.8. Краевая задача принципа максимума Понтрягина

380

32.9. Примеры

382

§ 33. Специальные задачи оптимального управления

401

33.1. Оптимизация непрерывных динамических систем в классе дискретных управляющих воздействий

401

33.2. Оптимизация дискретных систем

406

33.3. Оптимизация квазинепрерывных систем

410

33.4. Оптимизация непрерывных динамических систем в классе дискретно-импульсных управляющих воздействий

413

§ 34. Динамическое программирование в теории оптимального управления

420

34.1. Задача оптимального управления в классе кусочно-непрерывных управляющих воздействий

421

34.2. Связь динамического программирования с принципом максимума

426

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

428

§ 35. Проблема синтеза оптимальных систем управления

435

35.1. Синтез оптимальных систем управления с помощью принципа максимума

435

35.2. Применение динамического программирования к синтезу оптимальных систем управления

444

35.3. Оптимальные системы управления

446

35.4. Оптимальное управление в реальном времени

447

Литература

459

Предметный указатель

460

Другие сайты факультетаСтруктураОбразованиеМагистратураНаукаМеждународное сотрудничествоСтудентуНИРСАСовет молодых ученыхОлимпиадыАбитуриентуШкольникуЦентр
Компетенций
по ИТ
Microsoft
Imagine Premium
ИсторияИздания факультетаПрофбюро ФПМИПерсональные страницыФотогалереи Газета ФПМыНаши партнеры