Книга посвящена изучению итеративных методов решения игр и задач оптимального программирования. Развитый в ней математический аппарат позволяет охватить с единой точки зрения значительный класс применяемых в этой области итеративных процессов, в частности, алгоритмы решения игр, градиентные методы и др. В общую схему включаются также и стохастические методы, например методы стохастической аппроксимации, поскольку показано, что случайные ошибки не нарушают сходимости.

Специальный раздел посвящён конкретным алгоритмам решения задач линейного и целочисленного программирования. Рассмотрена экспериментальная модификация итеративного алгоритма, позволяющая существенно повысить скорость сходимости. Описан эффективный алгоритм для решения задач большой размерности, и приводится ряд практических задач хозяйственного планирования, решённых с его помощью.

Книга представляет интерес для математиков, работающих в области вычислительных методов, в теории управления, а также для экономистов, занимающихся применением математики в хозяйственном планировании. Она будет полезна аспирантам и студентам старших курсов соответствующих специальностей.

Илл. 7, табл. 4, библ. 77 назв.

Введение	7

Раздел первый
ТЕОРЕТИЧЕСКИЙ АППАРАТ ИССЛЕДОВАНИЯ
СХОДИМОСТИ ИТЕРАТИВНЫХ ПРОЦЕССОВ

Г л а в а I. Предварительные сведения	23

§ 1. Основные понятия и определения выпуклого анализа	23
1. Обозначения (23) 2. Выпуклые множества (24) 3. Выпуклые функции (26). 4. Обобщённый градиент выпуклой вверх функции (27). 5. Квазивыпуклые функции (29).
§ 2. Точечно-множественные отображения	30
1. Замкнутость и полунепрерывность сверху (30). 2. Отображения типа K (31) 3. Теорема Какутани (33). 4. Полунепрерывные сверху функции (33).
§ 3. Некоторые сведения из теории функций вещественной переменной и теории вероятностей	34
1. Функции на полуоси t > 0 (34). 2. Измеримые функции. Интеграл Лебега (35) 3. Производные числа (36). 4. Сведения из теории вероятностей (36).

Г л а в а II. Итеративные процессы в общей форме	40

§ 4. Регулярные последовательности на выпуклых компактах. Признак сходимости	41
1. Регулярная последовательность на выпуклом компакте (41). 2. Предельные траектории регулярной последовательности (42) 3. Первая основная теорема (43).
§ 5. Стандартный процесс	45
1. Регулярный алгоритм (45). 2. Процесс (46). 3. Стандартный процесс (47) 4. Основное поле (48). 5. Примеры (50). 6. Обсуждение (52). 7. Замечание о процессах с ошибками (53).
§ 6. Интегральные кривые многозначного векторного поля	55
1. Интегральные кривые (55). 2. Теорема вложения (56).
§ 7. Функция Ляпунова как критерий сходимости итеративного процесса	59
1 Индикатриса сходимости (59) 2. Функция Ляпунова (61) 3. Индикатриса сходимости в терминах верхней производной по полю направлений (61). 4. Дополнительная лемма (63).
§ 8. Итеративные процессы при наличии случайных ошибок	64
1. Случайный стандартный процесс (65). 2. Теорема об устойчивости процесса относительно случайных ошибок (66). 3. Две леммы (68). 4. Доказательство теоремы устойчивости (71).
§ 9. Теоремы о локальной сходимости. Простой процесс на неограниченном множестве	73
1. Детерминированный процесс (73). 2. Процесс со случайными ошибками (75).
Комментарии к главе II	78

Г л а в а III. Игровые процессы	81

§ 10. Выпуклые игры с нулевой суммой	81
1. Выпуклая игра N игроков (81). 2. Точки равновесия и связанное с игрой отображение (82). 3. Игра двух игроков (84). 4. Равноправные и симметричные игры (87). 5. Сведение игры N лиц к равноправной игре двух лиц (88). 6. Матричные (полиэдральные) игры (89). 7. Игровой процесс (89). 8. Игры в смешанных стратегиях (91).
§ 11. Теоремы о сходимости игровых процессов	93
1. Вторая основная теорема (93). 2. Теорема о сходимости игровых процессов (96). 3. Сходимость игрового процесса с поочередным выбором оптимальных ответов (96). 4. Обобщение для игр в смешанных стратегиях (97).
§ 12. Распространение теоремы сходимости на процесс с ошибками. Ослабление условий выпуклости	99
1. Процесс с ошибками. Измерение ошибок (99). 2. Обобщение теоремы сходимости (100). 3. Некоторые побочные результаты (102).
§ 13. Игровые процессы в случае единственности оптимального ответа	104
1. Доказательство сходимости (104). 2. Оценка скорости сходимости случайного игрового процесса (105). 3. Оценка скорости сходимости детерминированного игрового процесса (108). 4. Итеративный процесс специального вида (110).

Раздел второй
ЗАДАЧИ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ

Г л а в а IV. Задачи выпуклого программирования	113

§ 14. Сведение общей задачи к игре	113
1. Функция Лагранжа (113). 2. Преобразование Лежандра (116). 3. Использование преобразования Лежандра для сведения задачи максимизации к игре (118). 4. Задача максимизации на ограниченном множестве (121).
§ 15. Экономическая интерпретация задачи линейного программирования и методы декомпозиции	124
1. Экономическая интерпретация (124). 2. Блочная задача линейного программирования (127). 3. Первый метод декомпозиции (метод Данцига-Вольфа) (128). 4. Второй метод декомпозиции (метод Корнан-Липтака) (129). 5. Использование преобразования Лежандра для построения алгоритмов декомпозиции в общем (нелинейном) случае (132).

Г л а в а V. Градиентные методы	134

§ 16. Общие теоремы о методах градиентного типа	135
1. Две геометрические леммы (135). 2. Проекционное поле (136). 3. Обобщение на случай неограниченного множества (139).
§ 17. Некоторые известные методы	141
1. Метод обобщённого градиента для решения задачи максимизации (141). 2. Метод обобщённого градиента для решения игры (142). 3. Метод «тяжёлого шарика» (145).

Г л а в а VI. Дополнительные примеры использования итеративных методов	148

§ 18. Метод максимизации вдоль кривой спроса	148
1. Постановка задачи (148). 2 Метод (150). 3 Доказательство сходимости (153).
§ 19. Дополнительные примеры итеративных процессов	156
1. Метод Неймана (156). 2. Метод Франка и Вольфа (157). 3. Метод Булавского (158).

Г л а в а VII. Стохастические методы	160

§ 20. Методы стохастической аппроксимации и стохастического градиента	160
1. Метод стохастической аппроксимации (160). 2. Стохастический градиентный метод (161). 3. Вычисление градиента по значениям функции в узлах случайной сетки (162).
§ 21. Минимизация сложной функции	165
1. Постановка задачи (166). 2. Алгоритм в простейшем случае (167). 3. Нахождение минимума с условием в виде равенства (167).

Раздел третий
АЛГОРИТМЫ

Г л а в а VIII. Вычислительные итеративные алгоритмы и их экспериментальное исследование	170

§ 22. Представление общей задачи линейного программирования как задачи минимизации неотрицательной линейно-квадратичной формы. Алгоритм «Заяц»	170
1. Игровая формулировка задачи линейного программирования (170). 2. Сведение к задаче минимизации линейно-квадратичной формы (172). 3. Связь с исходной задачей (174). 4. Алгоритм «Заяц» (176). 5. Вычислительные эксперименты (179).
§ 23. Построение высокоточного алгоритма на базе алгоритма малой точности	181
1. Идея метода (181). 2. Схема отсечения (183). 3. Алгоритм «Белка» (184). 4. Вычислительные эксперименты (185). 5 Некоторые практические замечания (186).
§ 24. Алгоритм решения матричных игр	188
1. Алгоритм (189). 2. Обобщение (191). 3. Возможная реализация основной процедуры (195).

Г л а в а IX. Итеративные алгоритмы решения задач планирования, содержащих непрерывные и дискретные переменные	197

§ 25 Основная модель	202
1. Модель (202). 2. Экономическая интерпретация (203).
§ 26. Примеры конкретных задач хозяйственного планирования, формализуемых с помощью основной модели	205
1. Модели оптимального развития отрасли нефтяного машиностроения (205). 2. Задача развития крупного угольного бассейна (210). 3. Задача о реконструкции дороги (211).
§ 27. Вычислительный алгоритм L для расчётов по основной модели без условий целочисленности	213
1. Сведение основной модели к игре (213). 2. Описание алгоритма L (216). 3. Анализ работы алгоритма (219). 4. Две леммы о сходимости (222).
§ 28. Алгоритм D для решения задач с дискретными переменными	228
1. Описание алгоритма (228). 2. О возможностях алгоритма (230).
§ 29. Практическое применение алгоритмов L и D	231
1. Практические приёмы ускорения сходимости (232). 2. Некоторые результаты расчётов (233).

Литература	235

Книги на ту же тему

Совершенный стратег или букварь по теории стратегических игр, Вильямс Д. Д., 1960
Игры и решения. Введение и критический обзор, Льюс Р. Д., Райфа Х., 1961
Введение в прикладную теорию игр, Дюбин Г. Н., Суздаль В. Г., 1981
Кооперативные игры и рынки, Розенмюллер И., 1974
Элементы теории игр. — 2-е изд., стереотип., Вентцель Е. С., 1961
Теоретико-игровые модели принятия решений в эколого-экономических системах, Горелик В. А., Кононенко А. Ф., 1982
Математические модели конфликтных ситуаций, Саати Т. Л., 1977
Экономико-математические методы. Вып. III: Экономико-математические модели народного хозяйства, 1966
Оптимальные решения в экономике, Канторович Л. В., Горстко А. Б., 1972
Оптимальные решения, Ланге О., 1967
Математическое программирование: Методы решения производственных и транспортных задач, Рейнфельд Н., Фогель У., 1960
Линейное программирование, Ашманов С. А., 1981
Методы оптимизации, Моисеев Н. Н., Иванилов Ю. П., Столярова Е. М., 1978
Введение в минимакс, Демьянов В. Ф., Малозёмов В. Н., 1972
Практические занятия по курсу математического программирования, Капустин В. Ф., 1976
Теория игр, Оуэн Г., 1971
Теоретико-игровые методы синтеза сложных систем в конфликтных ситуациях, Крапивин В. Ф., 1972
A Primer in Game Theory, Gibbons R., 1992
Введение в теорию линейного и выпуклого программирования, Еремин И. И., Астафьев Н. Н., 1976
Разрешимость и устойчивость задач полиномиального программирования, Белоусов Е. Г., Андронов В. Г., 1993
Линейное программирование: Пособие для экономистов, Габр Я., 1960
Методы оптимизации. Применение математических методов в экономике. Пособие для учителей, Монахов В. М., Беляева Э. С., Краснер Н. Я., 1978
Введение в теорию исследования операций, Гермейер Ю. Б., 1971
Математические методы исследования операций, Саати Т. Л., 1963
Современное состояние теории исследования операций, Моисеев Н. Н., ред., 1979
Прикладной функциональный анализ, Балакришнан А. В., 1980
Равновесная термодинамика и математическое программирование, Каганович Б. М., Филиппов С. П., 1995
Адаптация и обучение в автоматических системах, Цыпкин Я. З., 1968
Численные методы оптимизации: Единый подход, Полак Э., 1974
Параллельные алгоритмы целочисленной оптимизации, Хохлюк В. И., 1987
Прикладное оптимальное проектирование: Механические системы и конструкции, Хог Э. Д., Арора Я. С., 1983
Исследование операций в военном деле, Чуев Ю. В., 1970
Исследование операций, Динер И. Я., 1969
Динамические задачи дискретной оптимизации, Рихтер К., 1985
Теория максимина и её приложение к задачам распределения вооружения, Данскин Д. М., 1970
Элементы динамического программирования, Вентцель Е. С., 1964
Игровое моделирование экономических процессов (деловые игры), Гидрович С. Р., Сыроежин И. М., 1976

elapsed time 0.018 sec

/Наука и Техника/Математика

ОГЛАВЛЕНИЕ

Книги на ту же тему