8.2. ДВухэтапные ЗАДАЧИ СТОХАСТИЧескОГО ПРОГРАММИРОВАНИЯ
Постановка двухэтапной задачи
При исследовании многих задач планирования и управления в условиях действия случайных возмущений возможно и целесообразно процесс принятия решений представить разделенным на два этапа.
На первом этапе выбирается предварительный план, позволяющий провести подготовительные работы. На втором этапе производится компенсация невязок, выявленных после наблюдения реализованных значений случайных параметров условий задачи. Естественно, что предварительный план и план-компенсация должны быть согласованы таким образом, чтобы обеспечить минимум среднего значения суммарных затрат, возникающих на обоих этапах решения задачи. В разрешимой задаче выбор предварительного плана должен гарантировать существование плана-компенсации.
Рассмотрим следующую задачу:
минимизировать 
(8.2.1)
при условиях
; (8.2.2)
; (8.2.3)
, (8.2.4)
где 
, 
; 
, 
, ; 
, 
.
Допустим, что элементы матрицы 
и векторов 
, 
- случайные величины, зависящие от реализации некоторого случайного события 
, а решение 
необходимо принимать до наблюдения случайных параметров 
.
Представим себе процесс решения задачи (8.2.1)-(8.2.4) следующим образом. Выберем сначала (на первом этапе) вектор , удовлетворяющий условиям (8.2.3), (8.2.4). Затем зафиксируем реализацию 
случайного события и соответствующие ему значения 
, оценим невязку 
в условиях (8.2.2) и вычислим вектор 
, компенсирующий невязки в соответствии с соотношением
,
где 
- матрица компенсации. В общем случае элементы 
- случайные. Если задачу (8.2.1)-(8.2.4) интерпретировать в терминах планирования производства и 
- матрица основных технологических способов производства, то интерпретируется как матрица аварийных технологических способов, определяющих возможные пути компенсации обнаруженных невязок.
За нарушение условий задачи устанавливается штраф, зависящий от величины составляющих вектора у, компенсирующего невязку. Будем характеризовать штраф величиной 
, причем в общем случае 
- случайный 
-мерный вектор, 
.
Вектор у может быть выбран многими способами. Обычно, его выбирают таким образом, чтобы обеспечить минимальный ожидаемый штраф за компенсацию условий задачи, определяемых предварительным планом х. Иными словами, на втором этапе решается задача
минимизировать 
(8.2.5)
при условиях
, (8.2.6)
. (8.2.7)
Оба этапа могут быть сведены в один. Тогда приходим к постановке двухэтапной задачи стохастического программирования
(8.2.8)
при условиях
; (8.2.9)
; (8.2.10)
. (8.2.11)
Таким образом, решение двухэтапной стохастической задачи состоит из двух векторов: детерминированного 
-мерного вектора x, определяющего предварительный план, и случайного -мерного вектора 
, определяющего план-компенсацию. Для решения задачи достаточно вычислить оптимальный предварительный план x. После реализации случайного события (т.е. после реализации случайных параметров условий задачи) соответствующая реализация оптимального плана-компенсации вычисляется как решение задачи ЛП (8.2.5)-(8.2.7).
Затраты на план-компенсацию должны быть наименьшими. Поэтому целесообразно для перспективного планирования (двухэтапной схемы) использовать малочувствительные к вариации параметров условия задачи.
Область определения планов первого этапа. Рассмотрим множество предварительных планов x двухэтапной задачи.
Пусть x - вектор, удовлетворяющий ограничениям задачи (8.2.8)-(8.2.10). В общем случае, когда матрица компенсации B задана произвольным образом, нет гарантии, что не существует такой реализации 
, при которой система
, ,
не будет иметь решения. В этом случае невозможно ликвидировать возникшую невязку с помощью вектора компенсации y. Для того, чтобы вектор x был допустимым планом двухэтапной задачи, необходимо, чтобы для всех 
существовал вектор 
такой, что
.
Такие неявно заданные ограничения на выбор вектора называют индуцированными (или приведенными) [57]. Условия (8.2.9), (8.2.11) называются фиксированными.
Обозначим множество векторов 
, определяемое фиксированными ограничениями, через 
, а индуцированными - через 
, т.е.
;
.
Тогда область определения вектора X задается множеством 
. Рассмотрим случай, когда матрица B детерминированная. Установим достаточные условия для того, что 
, где 
- -мерное эвклидово пространство, т.е. достаточные условия того, чтобы множество планов задачи второго этапа было непусто. Они формулируются в следующей теореме [18; 57].
Теорема 8.1. Для того, чтобы , достаточно выполнения следующих условий:
матрица компенсации 
размерности 
имеет ранг 
(
);
существует неотрицательное решение системы 
, причем
, при 
. (8.2.12)
Проверка условия (8.2.12) достаточно затруднительна. Однако в некоторых случаях эти условия могут быть конструктивными.
Пусть, например, 
. Тогда условие (8.2.12) принимает вид
. (8.2.13)
По условию 1) теоремы первые столбцов 
матрицы линейно-независимы, и потому 
. В силу условия 2) имеем 
. Поэтому соотношение (8.2.13) принимает вид
.
Если все 
, то 
. Итак, теорема 8.1 справедлива. Справедливо также следующее утверждение: множество предварительных планов двухэтапной задачи выпукло.
Условия разрешимости задачи второго этапа. Запишем задачу (8.2.8)-(8.2.11) в виде
минимизировать 
(8.2.14)
при условиях
, (8.2.15)
, (8.2.16)
где
, (8.2.17)
, (8.2.18)
. (8.2.19)
Условия разрешимости задачи второго этапа (8.2.17)-(8.2.19) формулируются следующим образом [57].
Теорема 8.2. Для разрешимости задачи второго этапа при любых реализациях 
и любом предварительном плане необходимо, чтобы система неравенств
(8.2.20)
была разрешимой.
Доказательство. По условию множество планов задачи (8.2.17)-(8.2.19) непусто. Согласно теореме двойственности функции ЛП 
, ограничена
снизу тогда и только тогда, когда область определения планов двойственной задачи для каждого x, A и B
(8.2.21)
при условии
, (8.2.22)
непуста.
Поскольку область определения задачи (8.2.21), (8.2.22) не зависит от 
, то при выполнении условия (8.2.22), задача второго этапа разрешима при всех , а при его нарушении задача не имеет решений ни при каких значениях этих переменных.
Эквивалентная детерминированная задача. Построим детерминированный эквивалент двухэтапной задачи стохастического программирования. Ее решением является предварительный план X. По составляющим оптимального предварительного плана X и реализации параметров условий задачи строится задача второго этапа - задача ЛП, решение которой определяет необходимую компенсацию плана.
Эквивалентная детерминированная задача имеет вид:
.
Исследуем функционал 
- показатель качества предварительного плана. Выразим 
через статистические характеристики параметров условий задачи и докажем, что детерминированная задача, эквивалентная задаче стохастического программирования, является задачей выпуклого программирования.
Рассмотрим задачу второго этапа (8.2.17) - (8.2.19) и двойственную к ней задачу (8.2.21), (8.2.22) для каждого .
Предположим, что задача второго этапа и двойственная к ней разрешимы. По теореме 2.5 двойственности для задач ЛП имеем
=
,
где 
- оптимальное решение задачи (8.2.21), (8.2.22), зависящее от параметров .
Учитывая эти обозначения, двухэтапную задачу можно переписать так:
(8.2.23)
или
.
Детерминированная задача (8.2.23), эквивалентная двухэтапной задаче (8.2.14)-(8.2.19), является задачей выпуклого программирования.
Некоторые частные постановки двухэтапной задачи
В общем случае отыскание точного решения детерминированного эквивалента двухэтапной задачи представляет значительные трудности, поэтому решение ищут приближенно. Однако в ряде частных случаев эта задача существенно упрощается и может быть решена классическими методами линейного и выпуклого программирования.
Рассмотрим некоторые случаи.
Рассмотрим двухэтапную задачу, в которой случайным является только вектор ограничений 
, а матрица компенсации D после соответствующей перестановки строк и столбцов может быть представлена в виде 
, где E - единичная матрица размером 
.
Аналогичным образом разобьем векторы и 
на две части: 
и 
, соответствующие матрицам E и 
. Тогда задача (8.2.8)-(8.2.11) будет иметь вид
(8.2.24)
при условиях
, (8.2.25)
, (8.2.26)
где
, (8.2.27)
при условиях
; (8.2.28)
. (8.2.29)
Здесь 
- -мерные векторы. Очевидно, что задача (8.2.29) второго этапа имеет планы при произвольной реализации и при любом предварительном плане , т.е. и 
.
Необходимое и достаточное условие существования конечного решения задачи второго этапа в данном случае приобретает следующий простой вид. Как известно, в общем случае это условие записывается в форме
.
В рассматриваемом случае 
. Так как обычно
, то это условие всегда выполняется .
Задача, двойственная к (8.2.27)-(8.2.29), записывается так:
(8.2.30)
при условии
. (8.2.31)
Задача (8.2.30) легко решается и ее решение имеет вид
, (8.2.32)
где
(8.2.33)
Поэтому эквивалентная выпуклая задача для двухэтапной стохастической задачи (8.2.27)-(8.2.29) записывается следующим образом:
(8.2.34)
при условиях
, (8.2.35)
, (8.2.36)
где 
определяются из соотношений (8.2.33).
Приведем еще одну форму записи этой же задачи. Введем обозначения
, (8.2.37)
, (8.2.38)
. (8.2.39)
Заметим, что функции 
так же, как и 
, выпуклы по 
. Двухэтапная стохастическая задача в этой простейшей постановке сводится, таким образом, к задаче выпуклого программирования:
(8.2.40)
при условиях
, (8.2.41)
, (8.2.42)
. (8.2.43)
Исследуем функции . Для этого обозначим через 
соответственно точные верхнюю и нижнюю грани случайной величины 
, через 
- математическое ожидание вектора ограничений, а через 
- функцию распределения компонент 
. Разобьем множество значений 
на три области: 
.
Если не имеет нижней грани (соответственно верхней), то положим 
.
Вычислим значения 
в каждой из этих областей. Используя (8.2.33), получим
Отсюда
. (8.2.44)
Рассмотрим три случая.
1. Пусть 
. Тогда 
и с (8.2.33) получим
.
2. Пусть 
. Тогда функция на этом отрезке выражается соотношением
.
3. 
. В этом случае множество 
совпадает со всей областью изменения , т.е. 
, и поэтому
Следовательно, функция на интервале 
имеет вид
.
Как видим, функция непрерывна и выпукла на всей числовой оси.
При некоторых частных распределениях составляющих вектора 
двухэтапная задача может быть сведена к стандартным задачам ЛП или выпуклого программирования. Рассмотрим некоторые такие случаи [18].
Пример 8.2. Пусть сотавляющие 
равномерно распределены на отрезке 
. Тогда
(8.2.45)
Допустим, что
.
Тогда
.
Учитывая, что
,
получаем
.
Тогда двухэтапная задача стохастического программирования (8.2.40)-(8.2.43) приводится к следующей задаче квадратичного программирования [18]:
(8.2.46)
при условиях
,
или
; (8.2.47)
; (8.2.48)
. (8.2.49)
Пример 8.3. Пусть все компоненты 
вектора 
распределены экспоненциально, т.е.
(8.2.50)
и
.
В таком случае, в соответствии с формулой (8.2.50), получим
. (8.2.51)
Интегрируя выражение (8.2.51) по частям, после несложных преобразований получим
(8.2.52)
Подставляя (8.2.52) в (8.2.44) и учитывая, что 
, находим
(8.2.53)
Следовательно, двухэтапная задача стохастического программирования сводится к следующей задаче выпуклого программирования:
(8.2.54)
при условиях (8.2.41), (8.2.42).
В случае, когда можно предполагать, что 
, разложив функцию 
в ряд Тейлора, получим
.
Итак, эта задача сводится к задаче квадратичного программирования.
Пример 8.4. Рассмотрим случай конечного числа реализаций случайного вектора . Пусть составляющие вектора могут принимать значения 
с вероятностями 
. Из формулы (8.2.39) следует, что в случае дискретного распределения случайной величины 
функции 
являются кусочно-линейными функциями переменных 
. Ввод дополнительных переменных и ограничений позволяет свести выпуклую кусочно-линейную задачу к задаче ЛП.
Обозначим
(8.2.55)
Введем переменные 
, удовлетворяющие условиям:
(8.2.56)
В этом случае 
Итак, задача стохастического программирования (8.2.40)-(8.2.43) сводится к задаче ЛП вида
(8.2.57)
при условиях
; (8.2.58)
, (8.2.59)
где
; (8.2.60)
; (8.2.61)
. (8.2.62)
Пример 8.5. Двухэтапную задачу, в которой все случайные компоненты вектора 
имеют непрерывную функцию распределения, можно приближенно свести к задаче квадратичного программирования. Для этого необходимо заменить непрерывную гладкую функцию распределения ступенчатой функцией и представить в виде суммы равномерно распределенных случайных величин:
, (8.2.63)
Соответствующая детерминированная задача тогда запишется следующим образом:
(8.2.64)
при условиях
; (8.2.65)
; (8.2.66)
. (8.2.67)
Пример 8.6. Рассмотрим задачу, приводящую к двухэтапной модели стохастического программирования.
Пусть существует несколько предприятий, производящих некоторый однородный продукт. Предприятия расположены в пунктах 
.
Объемы производства продукта обозначим соответсвенно
. Кроме того, имеется 
пунктов потребления этого продукта 
с уровнями спроса 
соответственно.
Обозначим производственные затраты по производству единицы продукта в пункте 
через 
, а транспортные затраты по перевозке единицы продукта из пункта в пункт 
- через 
. Допустим, что величина спроса в пунктах 
- случайная, с известной функцией распределения 
, и пусть 
- равномерное распределение на отрезке 
.
Обозначим через 
затраты по хранению единицы избыточного продукта в пункте . Если спрос превышает объем ввоза 
, то необходимы дополнительные затраты по производству и ввозу продукции. Обозначим удельные затраты по производству и ввозу единицы продукта в пункт через 
.
Допустим, что величины 
и 
случайные, с известными средними 
и 
. Требуется определить такие объемы перевозок 
из пункта в пункт , а также планы выпуска дополнительной продукции 
, при которых минимизируется сумма ожидаемых затрат по производству и перевозке продукции и хранению избыточного запаса.
Решение. Составим математическую модель задачи. На первом этапе необходимо найти такой план перевозок 
, для которого
(8.2.68)
при условиях
. (8.2.69)
Обозначим объем производства продукта, ввезенного в пункт , через 
. Очевидно,
.
Введем вектор компенсации 
, где 
и матрицу компенсации 
,
где
Используя соотношения (8.2.40)-(8.2.43), запишем детерминированный эквивалент
для данной задачи в следующем виде:
(8.2.70)
при условиях
; (8.2.71)
; (8.2.72)
. (8.2.73)
Используя выражение (8.2.46), приведем эту задачу к виду
(8.2.74)
при ограничениях
; (8.2.75)
; (8.2.76)
где
. (8.2.77)
Задача (8.2.74)-(8.2.77) является задачей квадратичного программирования с ограничениями-равенствами и ограничениями-неравенствами. Для ее решения , применим теорему Куна-Таккера.
Составим функцию Лагранжа для данной задачи
Запишем необходимые и достаточные условия оптимальности:
; (8.2.78)
; (8.2.79)
(8.2.80)
. (8.2.81)
Для дальнейшего решения этой задачи применим стандартные методы ЛП или метод перебора вариантов.
