Размещено на http://www.allbest.ru/

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

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

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

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

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

Случаи, когда неизвестны статистические особенности процесса, называются неопределенными ситуациями.

Стохастическое программирование используется для решения задач двух типов. стохастическое программирование линейная задача

1. В задачах первого типа прогнозируются статистические характеристики множества одинаковых экстремальных систем. Это задачи пассивного СП.

2. В задачах второго типа строятся алгоритмы планирования и управления в условиях неполной информации. Это задачи активного СП.

В зависимости от постановки задачи стохастического программирования её решения или планы могут вычисляться в двух видах:

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

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

При построении моделей управления в условиях неполной информации существует два подхода к использованию информации:

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

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

Решающие распределения представляют собой функции, таблицы или инструкции, устанавливающие зависимость решения от некоторой априорной или апостериорной информации.

Постановка задач СП

Большое число военных, экономических, технических задач записывается в виде задачи ЛП:

В конкретных случаях коэффициенты C_j, a_ij, b_i могут быть случайными величинами. Простая замена случайных параметров их усредненными характеристиками не всегда возможна по двум причинам:

может исказиться модель самой исследуемой операции и не отражать реальных условий;

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

Задачи СП могут формулироваться в трех видах

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

Жесткая постановка задачи требует расширения гиперплоскостей ограничений, и в результате ОДР может оказаться вырожденной, а сама задача потеряет смысл. Таким образом, замена случайных параметров их средними значениями при жесткой постановке не всегда приводит к правильному решению задачи СП.

2. Во многих задачах нет необходимости удовлетворять ограничениям при каждой реализации случайного изменения параметра.

Если в конкретной задаче требуется только чтобы вероятность попадания решения в допустимую область превышала некоторое заранее заданное число >0 (обычно >1/2), то такая постановка задач СП называется моделью с вероятностными ограничениями.

Если коэффициент c_j детерминирован, то целевая функция задачи с вероятностными ограничениями не изменяется. Если с_j случайно, то в качестве целевой функции задачи с вероятностными ограничениями берут математическое ожидание целевой функции

(10.1)

или вероятность превышения целевой функции некоторого фиксированного порога F₀ :

P(F>F₀).

В некоторых задачах её условия позволяют заменить ограничения со случайными параметрами неравенствами, ограничивающими первые или вторые моменты распределения левых частей условий:



3. Если ограничения представляют собой не просто вторые моменты распределения условий, а вторые моменты некоторых функций S от невязок условий

(10.4)

такая постановка задач СП называется моделью со статистическими условиями.

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

Если в задачах присутствуют как вероятностные, так и статистические и жесткие условия, такие модели называются моделями со смешанными условиями.

Модели задач СП

Задачи СП различаются по трем признакам.

1. По характеру решений (детерминированный или случайный вектор, чистые или смешанные стратегии).

2. По выбору показателя качества, т. е. целевой функции. Если находится:

а) математическое ожидание от целевой функции, т.е.

, то такие задачи называются М-моделями;

б) если минимизируется дисперсия целевой функции

то такие задачи называются V-моделями;

в) если определяется вероятность превышения целевой функцией некоторого порога F₀, т. е. , то такие задачи называются Р-моделями.

3. По способу расчленения ограничений задачи могут быть:

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

где _i - вероятность соблюдения условий,

_0i =1 - _i вероятность несоблюдения условий.

б) С общими вероятностными ограничениями Р[АХ ? В] ? , когда могут быть коррелированы параметры не только строки, но и между строками. В такой модели не учитывается сравнительная важность отдельных ограничений.

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

Задача планирования добычи угля в априорных решающих правилах

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

мощность и угол падения пластов,

обводнённость участков,

склонность к выбрасыванию газов,

физико-механические свойства угля и пород,

надежность оборудования, эксплуатационные расходы.

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

Для простоты допускается:

показатель плана определяется средним значением суммарных затрат,

область определения плана задается спросом на добываемый уголь (требуемый объем добычи) и фондом заработной платы.

Задача планирования угледобычи следующая.

Для i шахты заранее разрабатывается несколько вариантов развития. Требуется установить наиболее рациональный, с точки зрения объединения шахт, вариант развития каждой шахты.

Пусть , если для i -й шахты принят j-й вариант, иначе По каждой шахте реализуется только один вариант, т. е. .

- годовые затраты на добычу угля в i-й шахте по j-му варианту при реализации w случайных параметров, зависящих от природных факторов.

- годовой объем добычи угля в i-й шахте по j-му варианту при реализации w случайных природных факторов.

- годовой фонд зарплаты i -й шахты по j-му варианту развития при реализации w случайных природных факторов.

d -- требуемая в соответствии с планом более высокого уровня годовая добыча угля по объединению в целом.

k - общий фонд зарплаты по объединению.

_d ,_k - заданные вышестоящей организацией вероятности соблюдения ограничений по обеспечению спроса и по фонду зарплаты соответственно. В этом случае целевая функция соответствует М-модели

.(10.5)

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

В целом это типичная модель задачи стохастического программирования.

Стохастическая транспортная задача

Обычная транспортная задача имеет целевую функцию и ограничения в виде

.

Будем рассматривать задачу при различном характере спроса, который является случайной величиной, т. е. зависит от случайных параметров w,

b_j=b_j(w) . (10.8)

При этом возможны два варианта формулировки модели задачи.

Вариант 1. Пусть спрос b_j непрерывно распределен с плотностью вероятности . Примем - это общий объем продукта, предназначенный в соответствии с планом, составленным до реализации b_j (w), для j-го пункта потребления.

После определения спроса может оказаться, что y_j < b_j(w), тогда спрос не будет удовлетворен, и ущерб за невыполнение потребности будет пропорционален величине невыполнения с некоторым коэффициентом q_j, где q_j - штраф за невыполнение заявки за каждую единицу недовезенного продукта. Общий ущерб определяется как

(10.9)

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

. (10.10)

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

, (10.11)

где пределы интегрирования очевидны и определяются на рис. 10.1 избыточным (1) или недовезенным грузом (2) функции плотности распределения _j (b_j).



Размещено на http://www.allbest.ru/

В общем виде целевая функция может быть представлена как

(10.12)

Продифференцируем дважды по ,

Это означает, что , а вместе с ней и F (x,y) будут функцией, выпуклой вниз относительно .

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

Вариант 2. Пусть спрос b_j(w) распределен дискретно и в j-м пункте потребления принимает значения b_ik с вероятностями: p_jk (k=1…s). Аналогично ранее рассмотренной задаче , - коэффициенты штрафа за дефицит и издержки хранения единицы продукции.

Введем вспомогательные переменные v_jk, и_jk - величины избытка и дефицита в j-м пункте потребления при реализации k-го варианта спроса, т.е. при b_j(w)=b_jk . Целевая функция - математическое ожидание суммарных затрат - будет включать общую стоимость перевозок и штрафы за дефицит и избыток:

(10.13)

Всегда имеет место равенство , которое означает, что спрос b_jk удовлетворяется привезенным продуктом и дефицитом и_jk за вычетом избытка v_ik. Подставляя полученное значение b_jk в целевую функцию после преобразования, получаем:

. (10.14)

Второе слагаемое не содержит параметра управления, поэтому формально в модели может не учитываться.

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

,

Последнее ограничение означает, что разница между запасами и удовлетворенным спросом определяется дефицитом или избытками.

Аналогично могут быть сформулированы и другие стохастические транспортные задачи, у которых случайным может быть, например, объем производства а_i = a_i(w).

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

Задачи с построчными вероятностными ограничениями

Типовая задача стохастического программирования представляет собой М-модель с построчными вероятностными ограничениями и имеет вид:

(10.16)

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

Вариант А. А =||a_ij|| - детерминированная матрица,

- случайная матрица-столбец, - случайные величины.

Считается, что задана совместная плотность распределения составляющих b_i случайного вектора В:

Чтобы определить плотность распределения одной компоненты, необходимо проинтегрировать совместную плотность распределения по всем параметрам, за исключением

.

Зная распределение одной случайной величины , можно определить значение порога из уравнения

, (10.17)

где является нижним пределом интегрирования.

Размещено на http://www.allbest.ru/

Она определяется как заданная вероятность _i превышения случайной величиной b_i порога , что иллюстрируется на рис. 10.2.

Следовательно, построчные вероятностные ограничения

(10.18)

можно записать в виде неравенства

(10.19)

Таким образом, задача для варианта А запишется в матричном виде

(10.20)

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

Таким образом, задача при детерминированной матрице А и случайном столбце В будет решаться как детерминированная задача ЛП.

Вариант В. Принимаются элементы матрицы А=||а_ij|| - нормально распределенные независимые случайные величины со средним значением и дисперсией . Составляющие случайного вектора B=||b_j||^T - нормально распределенные независимые случайные величины со средним значением и дисперсией . Принимаем, что вероятность соблюдения построчных ограничений а_i?0,5.

При принятых допущениях невязка i-го вероятностного ограничения из (10.16) будет случайной величиной с нормальным распределением, как линейная комбинация нормально распределенных a_ij и b_i . Таким образом, невязка имеет вид

.(10.21)

Эта невязка имеет среднее значение и дисперсию

Построчные вероятностные ограничения можно выразить через невязку в виде неравенства следовательно, . Или для нормального распределения вероятность можно определить по известной формуле нормального распределения

(10.22)

где ? - параметр интегрирования.

Вводя интеграл вероятности Ф, соотношение (10.22) можно записать в виде

или ,(10.23)

где - функция, обратная интегралу вероятности. Иначе: Подставляя сюда значения ,получаем

. (10.24)

Ф^-1()?0. Область, ограничиваемая этим соотношением, выпукла, а сами ограничения квадратичны, т.к. .

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

Вариант С. Рассматривается P-модель, у которой требуется минимизация порога k при заданной вероятности ?₀ непревышения целевой функцией этого порога.

. (10.25)

Заданы случайные коэффициенты целевой функции с_j, которые распределены нормально со средним значением и коррелированы между собой.

Корреляция определяется корреляционной матрицей . Целевая функция для нормально распределенной величины с_j будет также нормально распределенной со средним значением и дисперсией .

Среднее значение невязки из соотношения (10.25) . Вводя интеграл вероятности Ф, аналогично (10.23) в принятых обозначениях получим .

. (10.26)

Поэтому целевая функция для минимизации порога k запишется из выражения (10.26) в виде

. (10.27)

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

Например, рассмотрим задачу стохастического программирования, у которой заданы целевая функция в виде Р - модели и построчные вероятностные ограничения в виде

где заданы вероятности ₀=0.37; ₁=₂=0.9.

Матрица системы детерминирована, c₁ ,c₂ ,b₁ ,b₂ - нормально распределенные независимые между собой пары случайных величин со средними значениями, и корреляционными матрицами, .

Можно рассмотреть плотность распределения одной из случайных величин, например b₁ , т. е. , приведенную на рис. 10.3.

По заданному среднему значению строится, смещенная относительно начала координат. Известная величина ₁=0.9 задает площадь под функцией плотности распределения, которая определяет границу=2.72 порога в ограничении, как следует из уравнения (10.17). Из табличных значений обратного интеграла вероятности находится Ф -¹ (0.37) =0.33.

Таким образом, детерминированный эквивалент рассматриваемой задачи будет иметь целевую функцию



и систему ограничений

Размещено на http://www.allbest.ru/

Решение стохастической задачи полностью сводится к решению детерминированной задачи.

Одноэтапные стохастические задачи с линейными решающими правилами

В рассмотренных ранее задачах решение определялось в виде детерминированного вектора.

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

Имеется два типа таких моделей:

1-й тип моделей - функциональный вид решающих правил задается заранее. Характер зависимости решения от реализованных параметров определяется из содержания задачи. Решение стохастической задачи сводится к вычислению детерминированных параметров решающих правил.

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

Рассматриваем стохастические модели со следующими условиями:

а) модель имеет построчные вероятностные ограничения;

б) решающие правила представляют собой линейные функции случайных параметров условий задачи;

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

Таким образом, анализируем М-модель с построчными вероятностными ограничениями в виде

(10.28)

где - детерминированная матрица, - независимые случайные векторы, компоненты которых a_ij, b_i и с_j могут быть коррелированы между собой.

Задаем решающее правило в виде X = DB, где [D] =||d_ij|| - неизвестная детерминированная матрица размерностью .

Найти решение задачи означает вычислить элементы матрицы D.

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

Вводим элементы определяемой матрицы в целевую функцию, учитывая, что:

(10.29)

где - математическое ожидание векторов С, В.

Теперь изменяем вид ограничений задачи. Обозначим - -ю строку матрицы А, тогда построчное вероятностное ограничение можно записать как

(10.30)

Рассмотрим невязку ограничения и обозначим её как S_i , т. е. S_i = b_i - a_iDB, а её среднее значение будет

Вводим вспомогательную случайную переменную в виде

, (10.31)

где _si - среднеквадратическое отклонение невязки:

.

Тогда, подставив значения S_i и, получим

, (10.32)

Её математическое ожидание , т.к. _i - центрированная случайная величина, а дисперсия , т.к. центрированная случайная величина () делится на свое среднеквадратичное отклонение .

Выразим ограничения (10.30) через невязку

(10.33)

а саму невязку - через вспомогательную случайную переменную из выражения (10.31)

.

Невязка в пределе будет равна нулю, если .

Ограничение (10.33) в этом случае будет

,

где - неслучайная величина, т.к. _si и - неслучайные параметры.

С обратной функцией интеграла вероятности (аналогично варианту В) это ограничение будет ,

где k_i =Ф ^-1 (1 - p_i) - зависит только от вероятности р_i и не зависит от элементов матрицы D. Подставив значения , получим . Вводим вспомогательную переменную так, что

. (10.34)

Это соотношение эквивалентно системе неравенств:

(10.35)

Теперь можно ввести функции, зависящие от искомой величины D:

Тогда вся задача может быть записана в виде детерминированного эквивалента относительно искомой переменной D и вспомогательной Z_i:

(10.36)

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

Двухэтапные задачи СП

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

в виде детерминированного вектора;

в виде случайного вектора.

Детерминированный вектор определяет предварительное решение, принимаемое до реализации условий задачи.

Случайный вектор соответствует коррекции, вводимой в решение после наблюдения реализованных параметров условий задачи.

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

первая группа определяет предварительное решение об объеме продукции, что позволяет руководству предприятия подготовить технологию, заключить договора, заказать материалы и начать выпуск продукции;

вторая группа параметров вычисляется после установления спроса (т.е. наблюдения реализации случайных параметров условий задачи) - это коррекция плана.

Коррекция необходима для компенсации невязок - несоответствия между спросом и объемом выпускаемой продукции, определенными предварительным планом.

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

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

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

Рассматриваем задачу, у которой часть элементов матрицы А имеет дополнительные ограничения:

(10.37)

A(w), B(w), C(w) зависят от случайных параметров, т.е. элементы матрицы и векторов являются случайными величинами.

Решение X следует принять до наблюдения реализации случайных параметров. Процесс решения задачи будет следующим.

выбирается решение, удовлетворяющее условиям (3), (4).

фиксируется реализация случайного события, вычисляются соответствующие ему значения B() и А().

оценивается невязка условия (2), т.е.

вычисляется вектор Y ? 0, компенсирующий невязки в соответствии с соотношением , где - матрица невязок компенсации.

В общем случае элементы матрицы компенсации К случайны. В производственных терминах: если А - матрица основных технологических способов, то матрица К понимается как матрица аварийных технологических способов, определяющих пути компенсации обнаруженных невязок.

За нарушение условий задачи устанавливается штраф, зависящий от величины составляющих вектора Y с некоторым случайным коэффициентом Q.

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

Следовательно, на втором этапе решается задача:

(10.38)

Оба этапа решения задачи (10.37) и (10.38), сведенные в один, приводят к двухэтапной задаче стохастического программирования:

(10.39)

Таким образом, решение двухэтапной задачи СП состоит из двух векторов:

детерминированного n-мерного вектора X, определяющего предварительный план;

случайного п-мерного вектора Y=Y(w), определяющего план компенсации невязок.

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

Размещено на Allbest.ru