В стохастическом программировании рассматриваются проблемы принятия решений в условиях действия случайных факторов, которые необходимо учитывать в соответствующих математических моделях.
Рассмотрим типичную задачу нелинейного программирования:
найти такой вектор Х, для которого
(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) прямые методы стохастического программирования, основанные на информации о значении функций ,
, получаемой в результате проведения экспериментов.
К одноэтапным задачам стохастического программирования относятся задачи, в которых решения принимаются на основе известных стохастических характеристик распределения случайных параметров условий задачи до наблюдения за их реализациями. При этом должно приниматься наилучшее в среднестатистическом смысле решение.
Постановки задач стохастического программирования различаются по трем признакам: 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 кг зерна. Требуется определить, какая из всех возможных смесей, удовлетворяющих требованиям на питательность, является самой дешевой. Обозначим через искомое количество зерна каждого вида.
Ингредиенты в составе смеси |
Содержание ингредиента в единице зерна вида |
Минимальные потребности на период |
||
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.