8.4. ПРИМЕНЕНИЕ МЕТОДА СТОХАСТИЧескИХ КВАЗиГРАДиеНТоВ К ЗАДАЧАМ СТОХАСТИЧескОГО ПРОГРАММИРОВАНИЯ

Простейшая задача управления запасами

Пусть имеется некоторый склад вместимостью , в котором нужно создать запас некоторого однородного продукта. Пусть спрос на продукт случаен с функцией распределения . Обозначим планируемый объем запаса через единиц. Рассмотрим функцию затрат

(8.4.1)

где – удельные затраты по хранению единицы запасов; – удельный штраф вследствие дефицита. Требуется найти такой уровень запасов , при котором

. (8.4.2)

Поскольку функция – недифференцируема при , то в общем случае – тоже недифференцируема. Очевидно,

, (8.4.3)

то есть имеем частный случай минимаксной задачи.

Находим стохастический квазиградиент

(8.4.4)

и рекуррентный процесс определения оптимального объема запасов выглядит следующим образом:

или . (8.4.5)

Игровая стохастическая задача

Задачи этого типа возникают при выборе оптимальных решений в условиях неопределенности и риска, когда имеется первый игрок – ЛПР и второй игрок – противодействующая среда. Предположим, что все факторы можно разбить на три группы:

факторы, контролируемые первым игроком;

факторы, контролируемые вторым игроком;

- состояние природы (случайные факторы).

Пусть первый игрок принимает (выбирает) решение x из допустимого множества решений , второй игрок принимает решение y, , где – допустимое множество решений второго игрока, – элементарное событие некоторого вероятностного пространства .

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

Тогда ожидаемый проигрыш первого игрока равен

(8.4.6)

и надо найти такой , для которого

. (8.4.7)

Итак, приходим к минимаксной задаче, которая является задачей стохастического программирования.

Ее сложность состоит в том, что только в исключительных случаях можно найти в аналитическом виде, и, кроме того, не будет неперервно дифференцируемой даже при гладкой функции . Пусть множество выпукло и замкнуто, и при каждом x и существует такой , что

причем – непрерывная и выпуклая функция в области , а – ее обобщенный градиент по x при фиксированном y и . Применим для решения задачи (8.4.7) метод СКГ, в котором – стохастический квазиградиент, где – результаты независимых наблюдений за состоянием природы .

Чтобы убедиться в этом, покажем, что для любой точки выполняется неравенство

, (8.4.8)

другими словами, что . Очевидно,

В силу сделанных предположений относительно функции имеем

(8.4.9)

и поэтому

. (8.4.10)

Беря операцию условного математического ожидания от обеих частей (8.4.10) при фиксированных и , получим условие (8.4.8).

Стохастическая задача о наилучшем приближении
(стохастический аналог задачи Чебышева)

Задачу вида:

минимизировать , (8.4.11)

где , , называют стохастическим аналогом задачи Чебышева [18]. В этом случае вектор , определяемый как , будет иметь вид

(8.4.12)

Двухэтапная задача стохастического программирования

В разделе 8.2 была рассмотрена двухэтапная задача стохастического программирования:

минимизировать

(8.4.13)

при ограничениях

(8.4.14)

. (8.4.15)

Функция в общем случае не имеет непрерывных производных. В наиболее общем виде предварительный план и план-компенсация вместо (8.4.14) имеют при всех удовлетворять ограничениям

, . (8.4.16)

Далее, пусть затраты, связанные с реализацией плана и его коррекцией в состоянии , равны .

Обозначим через план-компенсацию, который минимизирует при условиях (8.4.16), (8.4.15) и фиксированных , . Тогда ожидаемые затраты на реализацию плана и его коррекцию составляют

, (8.4.17)

и необходимо найти такой , для которого

при условиях (8.4.15), (8.4.16). Предположим, что и при каждом выпуклы вниз при всех , и существует седловая точка функции Лагранжа:

(8.4.18)

при и .

Пусть , – обобщенные градиенты функций , по при фиксированном .

Тогда для решения задачи (8.4.13) методом СКГ при условиях (8.4.15), (8.4.16) на выпуклом и замкнутом множестве следует положить

(8.4.19)

, (8.4.20)

или

. (8.4.21)

Можно показать [17], что для функции и вектора , задаваемого в (8.4.19), , то есть – субградиент функции .

Рассмотрим двухэтапную задачу стохастического программирования с линейными ограничениями и функцией затрат

(8.4.22)

при ограничениях

(8.4.23)

. (8.4.24)

Вектор минимизирует

(8.4.25)

при ограничениях

(8.4.26)

то есть является решением задачи ЛП (8.4.25), (8.4.26).

Обозначим через – двойственные переменные, отвечающие . В этом случае вектор в методе СКГ вычисляется так: после -й итерации получаем , наблюдаем (например, моделируя некоторые сценарии на ЭВМ), находим и вычисляем , где – транспонированная матрица к .

Запишем задачу, двойственную к (8.4.25), (8.4.26):

максимизировать (8.4.27)

при ограничении

Поскольку , то двухэтапной задаче (8.4.22)–(8.4.24) соответствует следующая эквивалентная задача

минимизировать , (8.4.28)

а так как , то .

Соответствующая процедура для поиска оптимального решения записывается так:

– для задачи без ограничений;

– для задачи с ограничениями.

Экстремальные задачи математической статистики

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

Имеется случайная величина (или вектор) , распределение которой известно с точностью до параметров , и известны реализации случайной величины при . Требуется по этим наблюдениям определить .

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

Оценка среднего значения. Пусть – случайный вектор с неизвестным средним , а – независимые наблюдения вектора , по которым необходимо оценить . Рассмотрим функцию . Минимум этой функции достигается при = . Кроме того, для имеем . Тогда в соответствии с общим алгоритмом СКГ (8.3.2), (8.3.3) получим следующую процедуру оценивания[17]:

(8.4.29)

Если , а , то процедура (8.4.29) примет вид

, (8.4.30)

то есть получим классическую формулу оценки среднего.

Оценка моментов. Пусть в постановке задачи предыдущего раздела (оценка среднего) требуется оценить моменты . Предположим, что эти моменты принадлежат некоторому множеству .