Eng | Rus | Ukr
Исследование операций
28.09.2004

<< prev | ^up^ | next >>

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)

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

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

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

 ,                          (8.4.31)

 ,  соответственно.

Применяя стохастический квазиградиентный метод для первых двух случаев в процедуре (8.4.30), положим  , соответственно. Тогда приходим к процедуре

 .                    (8.4.32)

При этом для соответствующей функции  имеем

Для задачи минимизации функции

в процедуре (8.3.2) или (8.3.3) в качестве вектора  можно взять :

 .              (8.4.33)

Тогда соответствующая рекуррентная процедура поиска оценки центрального момента -го порядка примет вид :

 .          (8.4.34)

Можно легко показать, что при этом . Действительно, в силу независимости  и  от  имеем

        (8.4.35)

<< prev | ^up^ | next >>

 
     
  Copyright © 2002-2004