Стохастическое программирование

- 18 -

Министерство образования и науки Украины

Харьковский национальный экономический университет

Индивидуальная научно-исследовательская работа

по курсу «Исследование операций»

на тему:

Стохастическое программирование

Выполнила:

студентка 2 курса, 6 группы

факультета МЭО

Умярова К.Э.

Харьков - 2006

Содержание

1. Стохастическое программирование

2. Общая характеристика задач стохастического программирования

3. Одноэтапные задачи стохастического программирования

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

Заключение

Список литературы

1. Стохастическое программирование

Стохастическое программирование -- это подход, позволяющий учитывать неопределённость в оптимизационных моделях.

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

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

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

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

2. Общая характеристика задач стохастического программирования

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

Рассмотрим типичную задачу нелинейного программирования:

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

(8.1)

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

, (8.2)

. (8.3)

Задачи стохастического программирования возникают в случаях, когда функции , зависят также от случайных параметров . При этом предполагается, что является элементом пространства состояний природы (или пространства случайных параметров) . Тогда задачу стохастического программирования можно сформулировать так [17;18]:

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

(8.4)

при условиях

, (8.5)

.

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

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

В задачах перспективного стохастического программирования решение x принимается до проведения каких-либо наблюдений над состоянием природы и поэтому является детерминированным. Такие задачи возникают в перспективном технико-экономическом планировании, в задачах проектирования, когда параметры системы должны быть выбраны конкретными детерминированными величинами, в расчете на определенный диапазон возможных возмущений.

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

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

(8.6)

при условиях

, (8.7)

где - операция математического ожидания;

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

(8.8)

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

, (8.9)

где a,P_i - некоторые числа; P- вероятность.

Возможные и некоторые комбинации задач (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) непрямые методы, которые заключаются в нахождении функций F(X), G_i(X) и решении эквивалентной задачи НП вида (8.6), (8.7);

2) прямые методы стохастического программирования, основанные на информации о значении функций , , получаемой в результате проведения экспериментов.

3. Одноэтапные задачи стохастического программирования

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

Постановки задач стохастического программирования различаются по трем признакам:

1. характеру решений;

2. выбору показателя качества решения (критерия);

3. способу декомпозиции ограничений задачи.

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

Задачи с целевой функцией вида называют М-моделями, задачи в которых требуется минимизировать дисперсию называют V-моделями, а стохастические задачи, в которых максимизируется вероятность , называют Р-моделями [18; 57].

В последнюю группу моделей включают также и задачи, где требуется минимизировать порог k, который не должен быть превышен с заданной вероятностью a, например:

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

при условии

.

Ограничения могут быть представлены в одной из следующих форм:

а)

б)

в)

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

1. Пусть задана задача линейного стохастического программирования с вероятностными ограничениями типа а):

максимизировать

(8.1.1)

при условиях

; (8.1.2)

. (8.1.3)

При детерминированной матрице и случайном векторе задача (8.1.1)-(8.1.3) сводится к эквивалентной детерминированной задаче ЛП следующим образом.

Пусть - совместная плотность распределения составляющих b_i случайного вектора b. Находим плотность распределения b_i:

Вычислим из уравнения

. (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)

где ; - корень уравнения , или , - функция распределения случайной величины b_i.

Для стохастической задачи (8.1.1)-(8.1.3) с детерминированной матрицей А можно записать двойственную задачу с вероятностными ограничениями.

Рассмотрим задачу

(8.1.8)

при условиях

, (8.1.9)

. (8.1.10)

Ее решение определяется в виде детерминированного вектора. Пусть - функция распределения случайного коэффициента С_j функции (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. Рассмотрим теперь более общий случай, когда A - случайная матрица. Пусть элементы матрицы А и составляющие вектора b - независимые между собой, нормально распределенные случайные величины: , т.е. a_ij - случайная нормально распределенная величина с математическим ожиданием и дисперсией . Пусть, кроме того, в условиях (8.1.2),

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

Действительно, при принятых допущениях невязка i-го условия - случайная величина - является нормально распределенной величиной с математическим ожиданием

и дисперсией

,

т.е.

.

Тогда условия эквивалентны неравенствам

, (8.1.15)

или (что то же самое)

. (8.1.16)

Обозначив , последнее неравенство (8.1.16) приведем к виду

,

Откуда

.

Учитывая выражения для , получим окончательно

. (8.1.17)

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

Аналогичный результат получим, когда случайные элементы строки i-го условия коррелированны между собой.

Введем следующие обозначения:

Тогда, рассуждая, как и выше, получим

 . (8.1.18)

Если матрица положительно определенная, и , , то допустимое множество решений, которое задается (8.1.18), будет выпукло.

Итак, при принятых выше допущениях линейная стохастическая задача (8.1.1)-(8.1.3) с вероятностными ограничениями сводится к детерминированной задаче выпуклого программирования вида

при условии

, .

3. Рассмотрим задачу стохастического программирования, заданную Р-моделью:

минимизировать k (8.1.19)

при условии

. (8.1.20)

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

. (8.1.21)

Отсюда следует, что минимизация k при условии (8.1.20) эквивалентна минимизации

.

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

Минимизировать k (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 кг зерна. Требуется определить, какая из всех возможных смесей, удовлетворяющих требованиям на питательность, является самой дешевой. Обозначим через х₁,х_2,х₃ искомое количество зерна каждого вида.

Таблица 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

Тогда требуется найти такие х₁,х_2,х₃ для которых

(1)

при условиях

, (ингредиент А);

, (ингредиент В);

(ингредиент С); (2)

(ингредиент D).

Допустим, что минимальные суммарные потребности в компонентах А, В, С, D являются случайными величинами a, b, c, d, распределенными равномерно в интервалах [1000, 1500], [200, 300], [500, 1000], [150, 250] соответственно.

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

 (3)

где a₁ - соответствующее значение случайной величины a, удовлетворяющее условию =0.80, откуда a₁ =1400. Аналогично находят значения b, c, d. Далее решают детерминированную эквивалентную задачу ЛП (1), (3). Ее оптимальное решение: = 162.5, = 177.5, = 103.5, а соответствующие минимальные расходы равны 20.693.

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