Нелинейное и динамическое программирование

Хедли Дж.(Hedley)

Table of contents :
Обложка ……Page 1
Титульный лист оригинала ……Page 3
Титульный лист перевода ……Page 4
Аннотация ……Page 5
От редактора перевода ……Page 6
Предисловие ……Page 8
1.1. Задачи математического программирования ……Page 10
1.2. Типы задач ……Page 12
1.3. Вычислительные методы ……Page 16
1.4. Трудности, порождаемые нелинейностями ……Page 17
1.5. Краткий исторический обзор ……Page 24
1.6. Обзор дальнейшего содержания ……Page 26
Литература ……Page 27
Упражнения ……Page 28
2.1. Матрицы и векторы ……Page 30
2.2. Системы линейных уравнений ……Page 39
2.3. Линейное программирование ……Page 41
2.4. Модифицированный симплекс-метод ……Page 45
2.5. Двойственность ……Page 49
2.6. Выпуклые множества ……Page 50
2.7. Характеристические числа и квадратичные формы ……Page 53
2.8. Функция п переменных ……Page 56
2.9. Частные производные ……Page 57
2.10. Теорема Тейлора ……Page 60
2.11. Теорема о неявных функциях ……Page 61
Упражнения ……Page 64
3.2. Максимум и минимум при отсутствии ограничений ……Page 66
3.3. Пример ……Page 71
3.4. Условный максимум и минимум. Множители Лагранжа ……Page 74
3.5. Общий случай ……Page 80
3.6. Случай неотрицательных переменных и ограничений в форме неравенств ……Page 83
3.7. Интерпретация множителей Лагранжа ……Page 86
3.8. Интерпретация функции Лагранжа; двойственность ……Page 87
3.9. Примеры ……Page 89
3.10. Выпуклые и вогнутые функции ……Page 98
3.11. Примеры ……Page 103
3.12. Максимум и минимум выпуклых и вогнутых функций ……Page 106
Упражнения ……Page 110
4.2. Построение приближенной задачи и определение локального максимума ……Page 117
4.3. Пример ……Page 124
4.4. Другая формулировка ……Page 130
4.5. Замена переменных для получения сепарабельности ……Page 133
4.6. Случаи, когда локальный экстремум одновременно является глобальным ……Page 137
4.7. Использование принципа декомпозиции при наличии ограничений сверху ……Page 141
4.8. Пример ……Page 144
4.9. Метод Хартли для максимизации функции на выпуклом множестве при сепарабельных ограничениях ……Page 149
4.10. Задача с фиксированными затратами ……Page 152
4.11. Пример задачи с фиксированными затратами ……Page 157
4.12. Транспортные задачи с выпуклыми сепарабельными целевыми функциями ……Page 160
Литература ……Page 164
Упражнения ……Page 165
5.1. Введение ……Page 171
5.2. Одношаговые стохастические задачи со случайностями, появляющимися только в спросе ……Page 173
5.3. Одношаговые стохастические задачи со случайными величинами в технологических коэффициентах ……Page 181
5.4. Многошаговые стохастические задачи ……Page 185
5.5. Средняя стоимость из-за неопределенности ……Page 192
Литература ……Page 193
Упражнения ……Page 194
6.2. Необходимые и достаточные условия для седловой точки ……Page 196
6.3. Теорема Куна-Таккера ……Page 201
6.4. Установление необходимых условий методом Куна-Таккера ……Page 205
6.5. Один частный случай и пример ……Page 213
Литература ……Page 216
Упражнения ……Page 217
7.1. Введение ……Page 221
7.2. Решение задачи квадратичного программирования с отрицательно определенной формой $x’Dx$ ……Page 223
7.3. Окончание процесса в случае отрицательной определенности формы $x’Dx$ ……Page 227
7.4. Способ Чарнса для случая неположительности квадратичной формы ……Page 230
7.5. Способ Вольфа, использующий параметризацию целевой функции ……Page 231
7.6. Пример ……Page 235
7.7. Другие методы решения задач квадратичного программирования ……Page 242
7.8. Двойственность в квадратичном программировании ……Page 247
Упражнения ……Page 250
8.1. Введение ……Page 255
8.2. Задача с фиксированными затратами ……Page 256
8.3. Определение глобального экстремума для приближенной задачи в $delta$-форме ……Page 257
8.4. Определение глобального экстремума для приближенной задачи в $lambda$-форме ……Page 259
8.6. Конечные альтернативы ……Page 261
8.8. Реализация проектов и календарное планирование ……Page 267
8.9. Задача о бродячем торговце ……Page 272
8.10. Капитальные вложения фирмы ……Page 274
8.11. Решение целочисленных задач линейного программирования ……Page 276
8.12. Алгоритм Гомори для решения полностью целочисленной задачи ……Page 277
8.13. Доказательство конечности ……Page 282
8.14. Алгоритм для решения частично целочисленных задач ……Page 288
8.16. Пример ……Page 292
Литература ……Page 296
Упражнения ……Page 297
9.1. Введение ……Page 303
9.2. Случай линейных ограничений ……Page 304
9.3. Сходимость итерационного процесса ……Page 310
9.4. Геометрическая интерпретация ……Page 313
9.5. Численное определение $r$ ……Page 316
9.6. Градиентный проективный метод ……Page 323
9.7. Геометрические иллюстрации ……Page 330
9.8. Сравнение методов определения $r$ ……Page 333
9.9. Решение задач линейного программирования с использованием градиентных методов ……Page 334
9.10. Задачи с нелинейными ограничениями ……Page 338
9.11. Градиентный метод для задач с сепарабельными ограничениями ……Page 341
9.12. Определение допустимого решения ……Page 348
9.13. Пример ……Page 349
9.14. Некоторые дополнительные замечания о сходимости ……Page 353
9.15. Градиентный метод Эрроу-Гурвица для вогнутого программирования ……Page 354
Упражнения ……Page 356
10.2. Сущность вычислительного метода ……Page 360
10.3. Эффективность метода ……Page 368
10.4. Основные свойства динамического программирования ……Page 370
10.5. Численный пример ……Page 373
10.6. Несколько других практических примеров ……Page 376
10.7. Случай непрерывности переменных ……Page 379
10.8. Случай выпуклости или вогнутости функций $f_j(x_j)$ ……Page 384
10.10. Простая задача об использовании рабочей силы ……Page 388
10.11. Детерминированные задачи создания запасов ……Page 392
10.12. Случай, когда $f_j(x_j,y_j)-вогнутые функции ……Page 395
10.13. Пример ……Page 400
10.14. Функциональные уравнения для систем с бесконечным числом шагов ……Page 402
10.15. Явное решение функционального уравнения ……Page 407
10.16. Задачи о замене оборудования ……Page 410
10.18. Стохастическая динамическая модель в теории создания запасов ……Page 415
10.19. Динамическое программирование и вариационное исчисление ……Page 423
10.20. Программы для решения задач методом динамического программирования на вычислительных машинах ……Page 427
Литература ……Page 428
Упражнения ……Page 429
11.2. Задача распределения с двумя ограничениями ……Page 437
11.3. Задача с двумя переменными управления ……Page 440
11.4. Случай непрерывности переменных ……Page 442
11.5. Сравнение линейного и динамического программирования ……Page 446
11.6. Использование динамического программирования в транспортных задачах с двумя пунктами производства ……Page 448
11.7. Использование множителей Лагранжа для уменьшения размерности ……Page 450
11.8. Замена оборудования ……Page 455
11.9. Некоторые задачи вариационного исчисления ……Page 457
11.10. Планирование выпуска продукции и задачи теории создания запасов ……Page 461
11.11. Случай квадратичных затрат ……Page 463
11.12. Доказательство эквивалентности стохастической и детерминированной задач в случае квадратичных затрат ……Page 468
11.13. Стохастические задачи последовательного принятия решений с бесконечным планируемым промежутком и марковские процессы ……Page 470
11.14. Пример ……Page 477
11.15. Оптимальность чистых стратегий ……Page 479
11.16. Сведение к задаче линейного программирования ……Page 481
11.17. Двойственная задача линейного программирования ……Page 484
11.18. Дополнительные обсуждения ……Page 488
11.19. Заключительные замечания о проблеме размерности ……Page 491
Литература ……Page 492
Упражнения ……Page 493
Именной указатель ……Page 497
Предметный указатель ……Page 498
Содержание ……Page 502