Общая характеристика задач
стохастического программирования
В стохастическом программировании рассматриваются проблемы принятия решений в условиях действия случайных факторов, которые необходимо учитывать в соответствующих математических моделях.
Рассмотрим типичную задачу нелинейного программирования:
найти такой вектор Х, для которого
(8.1)
при ограничениях
, (8.2)
. (8.3)
Задачи стохастического программирования возникают в случаях, когда функции 
, 
зависят также от случайных параметров 
. При этом предполагается, что является элементом пространства состояний природы (или пространства случайных параметров) 
. Тогда задачу стохастического программирования можно сформулировать так [17;18]:
минимизировать 
(8.4)
при условиях
, (8.5)
.
Постановка задач стохастического программирования существенно зависет от того, есть ли возможность при выборе решений уточнить состояние природы путем некоторых наблюдений или нет. В связи с этим различают задачи оперативного и перспективного стохастического программирования [17].
В задачах оперативного стохастического программирования решение принимается после некоторого эксперимента над состоянием природы , оно зависит от результатов эксперимента и является случайным вектором 
. Такие задачи возникают, например, в оперативном планировании, медицинской диагностике. В задачах перспективного стохастического программирования решение x принимается до проведения каких-либо наблюдений над состоянием природы и поэтому является детерминированным. Такие задачи возникают в перспективном технико-экономическом планировании, в задачах проектирования, когда параметры системы должны быть выбраны конкретными детерминированными величинами, в расчете на определенный диапазон возможных возмущений.
Задачи стохастического программирования обычно задаются в одной из следующих форм:
минимизировать 
(8.6)
при условиях
, (8.7)
где 
- операция математического ожидания;
минимизировать 
(8.8)
при ограничениях
, (8.9)
где 
- некоторые числа; 
- вероятность.
Возможные и некоторые комбинации задач (8.6), (8.7) и (8.8), (8.9).
Например, найти минимум (8.6) при условиях (8.9) или минимум (8.8) при условиях (8.7). Несмотря на кажущееся различие в постановках задач (8.6), (8.7) и (8.8), (8.9), они могут быть сведены к некоторой общей формулировке, например вида (8.6), (8.7). Для этого необходимо ввести характеристические функции:
(8.10)
(8.11)
для которых
Задача (8.8), (8.9) тогда приводится к виду
минимизировать 
(8.12)
при условии
Существует два основных подхода к решению задач стохастического программирования:
1) непрямые методы, которые заключаются в нахождении функций 
, 
и решении эквивалентной задачи НП вида (8.6), (8.7);
2) прямые методы стохастического программирования, основанные на информации о значении функций , 
, получаемой в результате проведения экспериментов.
8.1. ОДНОЭТАПНЫЕ ЗАДАЧИ СТОХАСТИЧескОГО ПРОГРАММИРОВАНИЯ
К одноэтапным задачам стохастического программирования относятся задачи, в которых решения принимаются на основе известных стохастических характеристик распределения случайных параметров условий задачи до наблюдения за их реализациями. При этом должно приниматься наилучшее в среднестатистическом смысле решение.
Постановки задач стохастического программирования различаются по трем признакам: 1) характеру решений; 2) выбору показателя качества решения (критерия); 3) способу декомпозиции ограничений задачи.
Ограничение на вид функции. В задаче стохастического программирования обычно принимают такие функционалы, как математическое ожидание или дисперсия целевой функции, или вероятность превышения целевой функцией некоторого порога.
Задачи с целевой функцией вида 
называют М-моделями, задачи в которых требуется минимизировать дисперсию 
называют V-моделями, а стохастические задачи, в которых максимизируется вероятность 
, называют Р-моделями [18; 57].
В последнюю группу моделей включают также и задачи, где требуется минимизировать порог 
, который не должен быть превышен с заданной вероятностью 
, например:
минимизировать
при условии
.
Ограничения могут быть представлены в одной из следующих форм:
а) 
б) 
в) 
Рассмотрим некоторые варианты моделей одноэтапных задач стохастического программирования.
1. Пусть задана задача линейного стохастического программирования с вероятностными ограничениями типа а):
максимизировать (8.1.1)
при условиях
; (8.1.2)
. (8.1.3)
При детерминированной матрице 
и случайном векторе 
задача (8.1.1)-(8.1.3) сводится к эквивалентной детерминированной задаче ЛП следующим образом.
Пусть 
- совместная плотность распределения составляющих 
случайного вектора 
. Находим плотность распределения :
Вычислим 
из уравнения
. (8.1.4)
Если решение уравнения (8.1.4) неединственно, то в качестве выберем наибольший корень.
Очевидно, что условия (8.1.2) при этом эквивалентны неравенствам
,
где удовлетворяет соотношениям (8.1.4). Отсюда следует, что задаче стохастического программирования (8.1.1)-(8.1.3) будет эквивалентна следующая детерминированная задача ЛП:
(8.1.5)
при условиях
, (8.1.6)
, (8.1.7)
где 
; - корень уравнения 
, или 
, 
- функция распределения случайной величины .
Для стохастической задачи (8.1.1)-(8.1.3) с детерминированной матрицей 
можно записать двойственную задачу с вероятностными ограничениями.
Рассмотрим задачу
(8.1.8)
при условиях
, (8.1.9)
. (8.1.10)
Ее решение определяется в виде детерминированного вектора. Пусть 
- функция распределения случайного коэффициента 
функции (8.1.1), т.е.
. Если 
, то запись 
эквивалентна записи 
. Задача (8.1.8)-(8.1.10) может быть переписана в виде
(8.1.11)
при условии
. (8.1.12)
Сравнивая эту задачу с исходной (8.1.1)-(8.1.3), убеждаемся, что при 
следующие две одноэтапные задачи стохастического программирования с вероятностными ограничениями представляют собой двойственную пару:
; (8.1.13)
. (8.1.14)
2. Рассмотрим теперь более общий случай, когда А - случайная матрица. Пусть элементы матрицы А и составляющие вектора 
- независимые между собой, нормально распределенные случайные величины: 
, т.е. 
- случайная нормально распределенная величина с математическим ожиданием 
и дисперсией 
. Пусть, кроме того, в условиях (8.1.2),
Покажем, что при таких предположениях стохастическая задача (8.1.1)-(8.1.3) сводится к детерминированной задаче выпуклого программирования с линейной целевой функцией и квадратичными ограничениями.
Действительно, при принятых допущениях невязка 
-го условия - случайная величина 
- является нормально распределенной величиной с математическим ожиданием
и дисперсией
,
т.е.
.
Тогда условия 
эквивалентны неравенствам
, (8.1.15)
или (что то же самое)
. (8.1.16)
Обозначив 
, последнее неравенство (8.1.16) приведем к виду
,
откуда
.
Учитывая выражения для 
, получим окончательно
. (8.1.17)
Согласно с допущением 
. Поэтому 
, и можно убедиться, что область, определяемая условиями (8.1.17), выпуклая.
Аналогичный результат получим, когда случайные элементы строки -го условия 
коррелированы между собой.
Введем следующие обозначения:
Тогда, рассуждая, как и выше, получим
. (8.1.18)
Если матрица 
положительно определенная, и , 
, то допустимое множество решений, которое задается (8.1.18), будет выпукло.
Итак, при принятых выше допущениях линейная стохастическая задача (8.1.1)-(8.1.3) с вероятностными ограничениями сводится к детерминированной задаче выпуклого программирования вида
при условии
, .
3. Рассмотрим задачу стохастического программирования, заданную
Р-моделью:
минимизировать (8.1.19)
при условии
. (8.1.20)
Будем считать, что случайные коэффициенты 
, распределены нормально с математическим ожиданием 
и корреляционной матрицей 
, где 
. При принятых допущениях линейная форма 
распределена с математическим ожиданием 
и дисперсией 
. Поэтому соотношение (8.1.20) может быть переписано в виде
. (8.1.21)
Отсюда следует, что минимизация при условии (8.1.20) эквивалентна минимизации
.
При 
представляет собой выпуклую вниз функцию по переменным 
. Таким образом, при сделанных допущениях задаче стохастичного программирования вида:
минимизировать (8.1.22)
при условиях
, (8.1.23)
, , (8.1.24)
соответствует следующий детерминированный эквивалент:
(8.1.25)
при условии
, (8.1.26)
.
Задача (8.1.25), (8.1.26) представляет собой задачу выпуклого программирования. Для ее решения можно применить теорему Куна-Таккера, или использовать один из вариантов метода возможных направлений и прочие методы НП.
Пример 8.1. Пусть крупная свиноферма имеет возможность покупать от одного до четырех различных видов зерна и приготавливать из них различные виды смесей. Разные зерновые культуры содержат различное количество необходимых компонентов. Допустим, что принимаются в расчет 4 компонента 
.
Исходные данные этой задачи приводятся в табл. 8.1. Пусть фермер установил, что комбикорм для свиней должен удовлетворять некоторым минимальным требованиям с точки зрения питательности. Они приведены в табл. 8.1. Пусть удельные затраты на закупку единицы веса зерна видов 1, 2 и 3 составляют соответственно 41, 35 и 96 услов.денеж.ед. на 1 кг зерна. Требуется определить, какая из всех возможных смесей, удовлетворяющих требованиям на питательность, является самой дешевой. Обозначим через 
искомое количество зерна каждого вида.
Таблица 8.1
|
Ингредиенты в составе смеси |
Содержание ингредиента в единице зерна вида |
Минимальные потребности на период |
||
|
1 |
2 |
3 |
||
|
А |
2 |
3 |
7 |
³1250 |
|
B |
1 |
1 |
0 |
³250 |
|
C |
5 |
3 |
6 |
³900 |
|
D |
0,6 |
0,25 |
1 |
³232,5 |
Тогда требуется найти такие для которых
(1)
при условиях
, (ингредиент А);
, (ингредиент В);
(ингредиент С); (2)
(ингредиент D).
Допустим, что минимальные суммарные потребности в компонентах 
, 
, 
, 
являются случайными величинами 
, распределенными равномерно в интервалах [1000, 1500], [200, 300], [500, 1000], [150, 250] соответственно.
Построить соответствующую минимизационную модель, которая бы обеспечивала минимальные потребности во всех компонентах с вероятностью не менее чем 0.80. Соответствующие детерминированные эквиваленты вероятностных ограничений будут иметь вид
(3)
где 
- соответствующее значение случайной величины 
, удовлетворяющее условию 
=0.80, откуда =1400. Аналогично находят значения 
. Далее решают детерминированную эквивалентную задачу ЛП (1), (3). Ее оптимальное решение: 
= 162.5, 
= 177.5, 
= 103.5, а соответствующие минимальные расходы равны 20.693.
