Ермольев Ю.М. Методы стохастического программирования
Подождите немного. Документ загружается.
«НАУКА»
r
ЛАВНАЯ
РЕДАКЦИЯ
ФИЗИКа-МАТЕМАТИЧЕСКОЙ
ЛИТЕРАТУРЫ
MOCI<BA
1976
Ю.
М.
ЕРМОЛЬЕВ
МЕТОДЫ
СТОХАСТИЧЕСКОГО
ПРОГРАММИРОВАНИЯ
ИЗДАТЕЛЬСТВО
«НАУКА,
ГЛАВНАЯ
РЕДАКЦИЯ
ФИЗИКО.МАТЕМАТИЧЕСКОЙ
ЛИТЕРАТУРЫ
мосКВА
1976
518
Е
93
УДК
519.95
Методы
стохастического
программирования,
Е
р
м
о
л
ь
е
в
Ю.
М.
Главная
редакция
физико
математической
литературы
изд-ва
«Наука»,
1976.
Книга
посвящена
численным
методам
реще
ния
нелинейных
экстремальных
задач
вероят
ностной
природы.
Основное
вниманис
уделяется
развитию
стохастических
процедур
поиска
экст
ремума
в
задачах
с
ограничениями,
для
реше
llИЯ
которых
невозможно
применить
известные
методы
нелинейного
программирования.
Обсуж
даются
приложения
к
вопросам
перспективного
планирования
в
условиях
неопределенности,
оптимизации
систем
обслуживания,
вопросам
ек;';щирования,
управления
случайными
процсс
calMI
и
запасами,
к
задачам
математичсС1(ОЙ
статистики.
Книга
построена
таким
образом,
что
для
ее
чтения
не
требуется
серьезного
знакомства
со
специальными
разделами
высшей
математики.
О"а
может
быть
полезна
как
специалистам-пр
и
кладникам,
использующим
в
своей
работе
тео
рию
оптимизации,
ТаК
и
научным
раБОТНИЮIМ,
аспирантам
и
студентам,
специализирующимся
в
этой
области.
20203-052
Е---
69-75
053 (02)-76
©
Главна"
реда,,,!и"
физика
математическо([
ЛНlrР::IТурtJl
издательства
.НауК
....
1976
ОГЛАВЛЕНИЕ
Предисловие
. • • • • • • • . . . . • . . 7
г
л
а
в
а
1.
Вспомогательные
сведения
11
§
1.
Теоретико-вероятностные
понятия
11
§
2.
Выбор
реше/N1Й
в
условиях
риска
инеопределенности
24
§
3.
Нелинейное
и
стохастическое
программирование
31
§
4.
Примеры
и
общие
постановки
задач
стохастического
программирования
52
Дополнения
к
гл~ве
1 . • • • • • • • • • • • • • • • • • • •
•.
63
г
л
а в
а
11.
Непрямые
методы
стохастического
программирования
67
§
1.
Опризнаках
экстремума
67
§
2.
Параметризация
в
задачах
оперативного
стохастического
программирования
. . . . • • • . •
76
§
3.
Приближенная
замена
. . . . . . •
79
§
4.
Эквивалентные
детерминированные
аналоги
82
Дополнения
к
главе
IJ . . . . . . . . .
91
г
л
а
в
а
!II.
Стохастические
квазиградиентные
методы
94
§
1.
Метод
проектирования
стохастических
квазиградиентов.
Стохастические
квазифейеровские
последовательности
..
95
§
2.
Локальная
сходимость
. . . . . . . . .
102
§ 3.
Большая
размерность.
Методы
случайного
поиска,
помехоустойчивость
. . . . . . .
107
§
4.
Стохасти"еский
метод
сокращения
невязок
. •
112
§ 5.
Решение
систем
неравенств
. . . . . . . . • • •
117
§
6.
Об
одном
~Jетоде
поиска
экстрсмума
.....•...
"
125
§
7.
Скорость
сходимости
Устойчивость
методов
нелинейиого
программирования
. . . . . . . . • . . . . . . . . . .
..
128
г
л
а
в
а
IV.
Прямые
методы
стохастического
программирования
133
§
1.
Метод
стохастической
аппроксимации
.•••••••.•
133
§
2.
Игровая
стохастическая
задача
. . . • • . • • • • • •
..
138
~
:1.
Задачи
двухэтапного
стохастического
программирования
143
§
4.
Программное
управление
случайным
процессом
148
6
ОГЛАВЛЕНИЕ
§
5.
Экстремальные
зада'lИ
математической
статистики
.
161
§
6.
Моделирование
и
оптимизация.
Численные
раСЧС1'Ы
lG3
Дополнения
к г
Лilве
1V
170
r
л
а
в
а
У.
Обобщения
179
§
1.
О
сходимости
процедур
ПОИСКiI
решений
179
§
2.
Нсгладкие
н
неныпуклые
функции
186
§ 3.
Предельные
экстремальные
Задачи
194
§
4.
Сложные
функции
регрессии.
Оп
ерация
усреднения
201
§ 5.
Стохастическая
процедура
линеаризации
Потоки
в
стоха·
стических
сетях
215
§
6.
О
методах
СТОХilстического
программирования
с
конеч·
ным
числом
испытаний
223
Дополнения
к
г
лаве
V . .
228
Библиографические
указания
232
Литература
••••••••.•
236
ПРЕДИСЛОВИЕ
Эта
книга
посвящена
численным
методам
решения
сложных
экстремальных
задач,
для
которых
неприменимы
известные
методы
нелинейного
программирования.
Основ
ные
особенности
рассматриваемых
задач
связаны
с
отсут
ствием
полной
информации
о
функции
цели
и
функциях
ограничений,
о
их
производных
И
С
негладким
харак
тером
этих
фуикций.
Наиболее
сложными
являются
те
задачи,
в
которых
отсутствует
точная
информация
о
зна
чениях
самих
функций
цели
и
ограничений,
т. е.
когда
для
заданного
решения
нельзя
указать
точного
значения
функции
цели
и
проверить
справедливость
требуемых
ограничений.
Менее
сложными
оказываются
задачи,
в
которых
нет
точной
информации
только
о
производных
этих
функций.
Принципиальные
трудности
связаны
также
с
отсутствием
непрерывных
производных
функций
цели
и
ограничений,
поскольку
в
этом
случае
практически
невозможно
найти
вектор,
характеризующий
направление
их
убывания
или
возрастания.
Экстремальные
задачи
с
отмеченными
особенностями
являются
типичными
для
различных
приложений
из
облас
ти
исследования
операций.
Например,
с
помощью
кусочно
линейных
функций
часто
отражаются
общие
затраты
произ
водства
с
учетом
его
реконструкций,
при
этом
разрывы
производных
отвечают
скачкам
себестоимости,
связанным
с
определенными
вариантами
перестройки
производства.
Точные
значения
градиентов
не
вычисляются
даже
для
классической
задачи
на
безусловный
экстремум
при
значительном
числе
переменных,
ибо
это
требует
состав
ления
значительного
числа
подпрограмм
для
вычисления
всех
частных
производных.
Отдельные
частные
производ
ные
не
вычисляются
точно
для
функций,
заданных
алго
ритмически.
Наиболее
сложными
оказываются
функции,
встречающиеся
при
оптимизации
вероятностных
систем
в
стохастическом
программировании:
обычно
они
имеют
8
ПРЕДИСЛОВИИ
негладкий
характер,
неизвестны
точные
значения
произ
водных
и
значения
самих
функций.
Основная
идея
предлагаемых
численных
методов,
наз
ванных
стохастическими
квазиградиентными,
состоит
в
использовании
вместо
точных
значений
градиентов
или
их
аналогов
(для
нег
ладких
функций)
случайных
направ
лений
-
стохастических
квазиградиентов,
являющихся
статистическими
оценками
этих
векторов.
В
книге
на
примере
различных
задач
указаны
способы
построения
стохастических
квазиградиентов,
причем
основное
вни
мание
уделяется
задачам
стохастического
программи
рования.
Стохастическое
программирование
является
тем
разде
лом
общей
теории
оптимальных
решений,
в
котором
изучаются
вопросы
выбора
решений
в
ситуациях,
харак
теризуемых
случайными
величинами.
С
формальной
точки
зрения
стохастическое
программирование
--
это
теория
решения
экстремальных
задач
стохастической
природы.
Частные
классы
таких
задач,
как
правило,
задач
на
без
условный
экстремум,
встречаются
в
классической
матема
тической
статистике,
в
современной
теории
статистических
решений.
В
стохастическом
программировании,
вообще
говоря,
рассматриваются
задачи
на
условный
экстремум
с
наличием
дополнительных
ограничений.
Термин
«стохастическое
программирование>)
появился
в
начале
50-х годов,
когда
Данцигом,
Чарнсом,
Купером
стали
анализироваться
задачи
линейного
программирова
ния
со
случайными
коэффициентами,
возникающие
при
планировании
в
ситуациях
с
неопределенностью
и
рис
ком.
Примерно
в
эти
же
годы
начало
развиваться
нелинейное
программирование,
и
этим,
по
всей
видимости,
объясняется
то,
что
в
большинстве
работ
по
стохасТичес
кому
программированию
авторы
стремятся
свести
сто
хастические
задачи
к
задачам
нелинейного
програм
мирования
и
применить
широко
известные
численные
методы.
Как
станет
ясно
из
дальнейшего,
методы
нелиней
ного
программирования
можно
применить
для
решения
только
весьма
узкого
класса
стохастических
задач,
по
скольку
они
намного
сложнее
задач
нелинейного
програм
мирования
и
требуют
своих
специфических
методов.
Основная
трудность
в
стохастическом
программиро
вании
по
сравнению
с
нелцнейным
программированием,