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

<< prev | ^up^ | next >>

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

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

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

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

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

<< prev | ^up^ | next >>

 
     
  Copyright © 2002-2004