- Лекция 9 Дисперсионный и регрессионный анализы 9.1 Дисперсионный анализ
- 9.2 Регрессионный анализ. Множественная регрессия Линейная модель множественной регрессии имеет вид: Y i =
- Y = X
- Y =Ха + е= +е
- Лекция 10 стохастическое программирование
- 1. Линейное программирование.
- 3. Формальная постановка стохастической задачи
- 4. Методы решения задач стохастического программирования
Основы теории Стохастических систем (лекции). Основы теории стохастических систем
 Скачать 18.19 Mb.
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
.
,
.
.
.
.
,Источник дисперсии |
Сумма квадратов |
Число степеней свободы |
Дисперсия |
Статистика Фишера |
Фактор А Остаток |
QA Qe |
υA υe |
sA2 se2 |
F |
Общий |
Q |
υ |
s2 |
Пример. К закаленному стеклу предъявляются высокие требования к допускам на отклонения гнутых изделий от заданной формы. Форму и размеры гнутых изделий проверяют по контрольному шаблону [8]. Контролируется также поперечная кривизна по отклонению образующей линии от цилиндрической поверхности.
Необходимо оценить влияние конфигурации вырабатываемых закаленных автомобильных стекол на дисперсию отклонения образующей линии от цилиндрической поверхности, в мм 2 .
Конфигурация стекла, определяется стороной остекления, фактор A. Кодировалась числами: левое – 0, правое -1, k=2. Объем выборки при анализе составил n=313 измерений.
В таблице приведены результаты дисперсионного анализа влияния конфигурации стекла на отклонение образующей цилиндра.
Источник дисперсии |
Сумма квадратов, мм 2 |
Число степеней свободы |
Дисперсия, мм 2 |
Статистика Фишера |
Фактор А Остаток |
3,74 34,32 |
1 312 |
3,74 0,11 |
34 |
Общий |
38,06 |
312 |
0,122 |
Для уровня значимости 0,05, числа степеней свободы υA=2-1=1 и υe=312 квантиль распределения Фишера равен Fтаб=3,87.
Так как выборочное значение статистики оказалось больше критического, нулевая гипотеза отвергается и принимается альтернативная: влияние конфигурации стекла на отклонение образующей цилиндра существенно.
Подобным образом в двухфакторном дисперсионном анализе оценивается влияние двух факторов AиB, а также ихвзаимодействияAB на результативный признак Х. При этом проверяются три соответствующие нулевые гипотезы. По аналогии исследуются влияние на признак Х большего числа факторов с их парными взаимодействиями и взаимодействиями высших порядков.
9.2 Регрессионный анализ. Множественная регрессия
Линейная модель множественной регрессии имеет вид:
Y i = 0 + 1x i 1 +2x i 2 +…+ m x i m + i ,
(9.1.)коэффициент регрессии j показывает, на какую величину в среднем изменится результативный признак Y, если переменную xj увеличить на единицу измерения, т. е. j является нормативным коэффициентом. Обычно предполагается, что случайная величина i имеет нормальный закон распределения с математическим ожиданием равным нулю и с дисперсией
.Анализ уравнения (9.1) и методика определения параметров становятся более наглядными, а расчетные процедуры существенно упрощаются, если воспользоваться матричной формой записи уравнения (9.2.):
Y = X + , (9.2.)
Y – это вектор зависимой переменной размерности п 1, представляющий собой п наблюдений значений уi, Х— матрица п наблюдений независимых переменных X1, X 2, X 3 , … X m, размерность матрицы Х равна п (т+1); — подлежащий оцениванию вектор неизвестных параметров размерности (т+1) 1; — вектор случайных отклонений (возмущений) размерности п 1. Таким образом,
Y = 
, X = 
, = 
Уравнение (9.1) содержит значения неизвестных параметров 0,1,2,… ,m
. Эти величины оцениваются на основе выборочных наблюдений, поэтому полученные расчетные показатели не являются истинными, а представляют собой лишь их статистические оценки. Модель линейной регрессии, в которой вместо истинных значений параметров подставлены их оценки (а именно такие регрессии и применяются на практике), имеет видY =Ха + е=
+е, (9.3)где а — вектор оценок параметров; е — вектор «оцененных» отклонений регрессии, остатки регрессии е = Y - Ха;
—оценка значений Y, равная Ха.Оценка параметров модели множественной регрессии с помощью метода наименьших квадратов.
Формулу для вычисления параметров регрессионного уравнения приведем без вывода
a = (XтX )-1XтY (9.4).
Одним из условий регрессионной модели является предположение о линейной независимости объясняющих переменных, т. е., решение задачи возможно лишь тогда, когда столбцы и строки матрицы исходных данных линейно независимы. Для экономических показателей это условие выполняется не всегда. Линейная или близкая к ней связь между факторами называется мультиколлинеарностью и приводит к линейной зависимости нормальных уравнений, что делает вычисление параметров либо невозможным, либо затрудняет содержательную интерпретацию параметров модели. Мультиколлинеарность может возникать в силу разных причин. Например, несколько независимых переменных могут иметь общий временной тренд, относительно которого они совершают малые колебания. В частности, так может случиться, когда значения одной независимой переменной являются лагированными значениями другой. Считают явление мультиколлинеарности в исходных данных установленным, если коэффициент парной корреляции между двумя переменными больше 0.8. Чтобы избавиться от мультиколлинеарности, в модель включают лишь один из линейно связанных между собой факторов, причем тот, который в большей степени связан с зависимой переменной.
В качестве критерия мультиколлинеарности может быть принято соблюдение следующих неравенств:
ryxi > rxixk , ryxk > rxixk , rxixk < 0.8
Если приведенные неравенства (или хотя бы одно из них) не выполняются, то в модель включают тот фактор, который наиболее тесно связан с Y.
Оценка качества модели регрессии.
Качество модели регрессии оценивается по следующим направлениям:
проверка качества всего уравнения регрессии;
проверка значимости всего уравнения регрессии;
проверка статистической значимости коэффициентов уравнения регрессии;
проверка выполнения предпосылок МНК.
Для оценки качества модели множественной регрессии вычисляют коэффициент множественной корреляции (индекс корреляции) R икоэффициент детерминацииR2. Чем ближе к 1 значение этих характеристик, тем выше качество модели.
В многофакторной регрессии добавление дополнительных объясняющих переменных увеличивает коэффициент детерминации. Следовательно, коэффициент детерминации должен быть скорректирован с учетом числа независимых переменных. Скорректированный R2, или
, рассчитывается так:
, (9.5)где n — число наблюдений;
k — число независимых переменных.
Проверка значимости модели регрессии
Для проверки значимости модели регрессии используется F-критерий Фишера, вычисляемый по формуле:
(9.6)Если расчетное значение с 1= k и 2 = (n - k - 1) степенями свободы, где k – количество факторов, включенных в модель, больше табличного при заданном уровне значимости, то модель считается значимой.
Анализ статистической значимости параметров модели
Значимость отдельных коэффициентов регрессии проверяется по t-статистике путем проверки гипотезы о равенстве нулю j-го параметра уравнения (кроме свободного члена):
taj =
/ Saj , (9.7.)где Saj— это стандартное (среднеквадратическое) отклонение коэффициента уравнения регрессии aj.Величина Saj представляет собой квадратный корень из произведения несмещенной оценки дисперсии
и j -го диагонального элемента матрицы, обратной матрице системы нормальных уравнений.Saj =
, (9.8)где bjj - диагональный элемент матрицы (ХТ Х)-1.
Если расчетное значение t-критерия с (n - k - 1) степенями свободы превосходит его табличное значение при заданном уровне значимости, коэффициент регрессии считается значимым. В противном случае фактор, соответствующий этому коэффициенту, следует исключить из модели, при этом оставшиеся в модели параметры должны быть пересчитаны.
Проверка выполнения предпосылок МНК.
Проверка выполнения предпосылок МНК выполняется на основе анализа остаточной компоненты.
Анализ остатков позволяет получить представление, насколько хорошо подобрана сама модель и насколько правильно выбран метод оценки коэффициентов. Согласно общим предположениям регрессионного анализа, остатки должны вести себя как независимые (в действительности, почти независимые) одинаково распределенные случайные величины. В классических методах регрессионного анализа предполагается также нормальный закон распределения остатков.
Исследование остатков полезно начинать с изучения их графика. 0н может показать наличие какой-то зависимости, не учтенной в модели. Скажем, при подборе простой линейной зависимости между Y и X график остатков может показать необходимость перехода к нелинейной модели (квадратичной, полиномиальной, экспоненциальной) или включения в модель пе
График остатков хорошо показывает и резко отклоняющиеся от модели наблюдения — выбросы. Подобным аномальным наб риодических компонент.людениям надо уделять особо пристальное внимание, так как их присутствие может грубо искажать значения оценок. Устранение эффектов выбросов может проводиться либо с помощью удаления этих точек из анализируемых данных, (эта процедура называется цензурированием), либо с помощью применения методов оценивания параметров, устойчивых к подобным грубым отклонениям.
Независимость остатков проверяется с помощью критерия Дарбина – Уотсона.
Корреляционная зависимость между текущими уровнями некоторой переменной и уровнями этой же переменной, сдвинутыми на несколько шагов, называется автокорреляцией.
Автокорреляция случайной составляющей нарушает одну из предпосылок нормальной линейной модели регрессии.
Наличие (отсутствие) автокорреляции в отклонениях проверяют с помощью критерия Дарбина – Уотсона. Численное значение коэффициента равно
(9.9)Значение dw статистики близко к величине 2(1–r(1)), где r(1) - выборочная автокорреляционная функция остатков первого порядка. Таким образом, значение статистики Дарбина - Уотсона распределено в интервале от 0 до 4. Соответственно, идеальное значение статистики - 2 (автокорреляция отсутствует). Меньшие значения критерия соответствуют положительной автокорреляции остатков, большие значения - отрицательной. Статистика учитывает только автокорреляцию первого порядка. Оценки, получаемые по критерию, являются не точечными, а интервальными. Верхние (d2) и нижние (d1) критические значения, позволяющие принять или отвергнуть гипотезу об отсутствии автокорреляции, зависят от количества уровней динамического ряда и числа независимых переменных модели. Значения этих границ для уровня значимости
= 0,05 даны в специальных таблицах (Приложение 9.1).Приложение 9.1. d-статистика Дарбина - Уотсона: d1и d2, уровень значимости в 5%
n |
k =1 |
k =2 |
||
d1 |
d2 |
d1 |
d2 |
|
15 |
1,08 |
1,36 |
0,95 |
1,54 |
16 |
1,10 |
1,37 |
0,98 |
1,54 |
17 |
1,13 |
1,38 |
1,02 |
1,54 |
18 |
1,16 1,16 |
1,39 |
1,05 |
1,53 |
19 |
1,18 |
1,40 |
1,08 |
1,53 |
20 |
I,20 |
1,41 |
1,10 |
1,54 |
21 |
1,22 |
1,42 |
1,13 |
1,54 |
22 |
1,24 |
1,43 |
1,15 |
1,54 |
23 |
1,26 |
1,44 |
1,17 |
1,54 |
24 |
1,27 |
1,45 |
1,19 |
1,55 |
25 |
1,29 |
1,45 |
1,21 |
1,55 |
При сравнении расчетного значения dwстатистики (9.9) с табличным могут возникнуть такие ситуации: d2 < dw < 2 – ряд остатков не коррелирован; dw < d1 – остатки содержат автокорреляцию; d1 < dw < d2 – область неопределенности, когда нет оснований ни принять, ни отвергнуть гипотезу о существовании автокорреляции. Если d превышает 2, то это свидетельствует о наличии отрицательной корреляции. Перед сравнением с табличными значениями dw критерий следует преобразовать по формуле dw´=4 – dw.
Установив наличие автокорреляции остатков, переходят к улучшению модели. Если же ситуация оказалась неопределенной (d1 < dw < d2 ), то применяют другие критерии. В частности, можно воспользоваться первым коэффициентом автокорреляции
(4.10)Для принятия решения о наличии или отсутствии автокорреляции в исследуемом ряду фактическое значение коэффициента автокорреляции r(1) сопоставляется с табличным (критическим) значением для 5%-ного уровня значимости (вероятности допустить ошибку при принятии нулевой гипотезы о независимости уровней ряда). Если фактическое значение коэффициента автокорреляции меньше табличного, то гипотеза об отсутствии автокорреляции в ряду может быть принята, а если фактическое значение больше табличного – делают вывод о наличии автокорреляции в ряду динамики.
Обнаружение гетероскедастичности
Для обнаружения гетероскедастичности обычно используют три теста, в которых делаются различные предположения о зависимости между дисперсией случайного члена и объясняющей переменной: тест ранговой корреляции Спирмена, тест Голдфельда - Квандта и тест Глейзера [Доугерти].
При малом объеме выборки для оценки гетероскедастичности может использоваться метод Голдфельда — Квандта.
Данный тест используется для проверки такого типа гетероскедастичности, когда дисперсия остатков возрастает пропорционально квадрату фактора. При этом делается предположение, что, случайная составляющая
распределена нормально.Чтобы оценить нарушение гомоскедастичности по тесту Голдфельда - Квандта необходимо выполнить следующие шаги.
Упорядочение п наблюдений по мере возрастания переменной х.
Разделение совокупности на две группы (соответственно с малыми и большими значениями фактора х) и определение по каждой из групп уравнений регрессии.
Определение остаточной суммы квадратов для первой регрессии
и второй регрессии 
.
Вычисление отношений
(или 
). В числителе должна быть большая сумма квадратов.
Полученное отношение имеет F распределение со степенями свободы k1=n1-m и k2=n-n1-m, (m– число оцениваемых параметров в уравнении регрессии).
Если
, то гетероскедастичность имеет место.Чем больше величина F превышает табличное значение F -критерия, тем более нарушена предпосылка о равенстве дисперсий остаточных величин.
Оценка влияния отдельных факторов на зависимую переменную на основе модели (коэффициенты эластичности, - коэффициенты).
Важную роль при оценке влияния факторов играют коэффициенты регрессионной модели. Однако непосредственно с их помощью нельзя сопоставить факторы по степени их влияния на зависимую переменную из-за различия единиц измерения и разной степени колеблемости. Для устранения таких различий при интерпретации применяются средние частные коэффициенты эластичности Э(j) и бета-коэффициенты (j), которые рассчитываются соответственно по формулам:
(9.11.)
(9.12.)где Sxj — среднеквадратическое отклонение фактора j
где
Коэффициент эластичности показывает, на сколько процентов изменяется зависимая переменная при изменении фактора j на один процент. Однако он не учитывает степень колеблемости факторов.
Бета-коэффициент показывает, на какую часть величины среднего квадратического отклонения Sy изменится зависимая переменная Y с изменением соответствующей независимой переменной Хj на величину своего среднеквадратического отклонения при фиксированном на постоянном уровне значении остальных независимых переменных.
Указанные коэффициенты позволяют упорядочить факторы по степени влияния факторов на зависимую переменную.
Долю влияния фактора в суммарном влиянии всех факторов можно оценить по величине дельта - коэффициентов (j):
где
— коэффициент парной корреляции между фактором j (j = 1,...,m) и зависимой переменной.Использование многофакторных моделей для анализа и прогнозирования развития систем и процессов.
Одна из важнейших целей моделирования заключается в прогнозировании поведения исследуемого объекта. Обычно термин «прогнозирование» используется в тех ситуациях, когда требуется предсказать состояние системы в будущем. Для регрессионных моделей он имеет, однако, более широкое значение. Как уже отмечалось, данные могут не иметь временной структуры, но и в этих случаях вполне может возникнуть задача оценки значения зависимой переменной для некоторого набора независимых, объясняющих переменных, которых нет в исходных наблюдениях. Именно в этом смысле — как построение оценки зависимой переменной — и следует понимать прогнозирование в эконометрике.
При использовании построенной модели для прогнозирования делается предположение о сохранении в период прогнозирования существовавших ранее взаимосвязей переменных.
Построение точечных и интервальных прогнозов на основе регрессионной модели. Какие факторы влияют на ширину доверительного интервала?
Для того чтобы определить область возможных значений результативного показателя, при рассчитанных значениях факторов следует учитывать два возможных источника ошибок: рассеивание наблюдений относительно линии регрессии и ошибки, обусловленные математическим аппаратом построения самой линии регрессии. Ошибки первого рода измеряются с помощью характеристик точности, в частности, величиной Sy. Ошибки второго рода обусловлены фиксацией численного значения коэффициентов регрессии, в то время как они в действительности являются случайными, нормально распределенными.
Для линейной модели регрессии доверительный интервал рассчитывается следующим образом. Оценивается величина отклонения от линии регрессии (обозначим ее U):
(9.13)где
Контрольные вопросы
1. Дисперсионный анализ и его назначение.
2. Алгоритм проведения дисперсионного анализа.
3. Регрессионный анализ. Оценка параметров модели регрессии.
4. Мультиколлениарность в исходных данных, Причины мультиколлениарности.
5. Оценка качества модели регрессии.
6. Проверка статистической значимости параметров модели регрессии.
7. Проверка выполнения предпосылок м.н.к.
8. Оценка влияния отдельных факторов на зависимую переменную на основе модели.
9. Использование многофакторных моделей для анализа и прогнозирования развития систем и процессов.
10. Построение точечных и интервальных прогнозов на основе регрессионной модели.
Лекция 10
стохастическое программирование
Стохастическим программированием называют метод решения оптимизационных задач, в которых целевая функция недоступна для вычисления в чистом виде, а может быть оценена или вычислена с погрешностью, например из эмпирических наблюдений или экспериментов.
Термин стохастическое программирование (СП) появился в начале 50-х гг. XX в., когда Данциг, Чарнс и Купер стали анализировать задачи линейного программирования со случайными коэффициентами, возникающие при планировании в ситуациях с неопределенностью и риском [9]. При решении задач СП нельзя обойтись детерминированными методами и приходится использовать специальные стохастические процедуры. В задачах СП максимизации или минимизации обычно подлежит некоторая характеристика случайной функции, например ее математическое ожидание. При этом в некоторых постановках задач СП допускается выполнение ограничения в виде равенства (или неравенства) с некоторой положительной вероятностью.
Стохастическое программирование может применяться для решения задач оценки параметров стохастических объектов, управления, динамической идентификации, однако, в отличие от прямых методов решения этих задач, стохастическое программирование не требует хранения всей накопленной информации об объекте, а предлагает способ адаптивной коррекции оценки по данным следующего наблюдения. Рассматриваются такие методы как Робинса–Монро, Киффера–Вольфовица, конечно-сходящиеся алгоритмы, методы случайного поиска. Кроме того, рассматриваются нейросетевые и генетические алгоритмы, как частные случаи алгоритмов стохастического программирования для решения специфических задач. Курс предназначен для студентов, специализирующихся в области математических методов анализа и интерпретации данных.
1. Линейное программирование.
Ответственные решения в современных целенаправленных системах планирования и управления должны быть в некотором смысле экстремальными или близкими к ним. Отступление от этого принципа обычно связано с излишними затратами (часто весьма значительными) и снижает эффективность управления (часто весьма существенно). Большое число задач планирования, управления и проектирования укладывается в схему линейного программирования:
C x → max, (1.1)
Ax ≤ b, (1.2)
x ≥ 0. (1.3)
Еще более широкий класс задач выбора эффективного решения укладывается в рамки общей схемы математического программирования.
План, набор команд управления или проект часто могут быть формально представлены в виде системы чисел или функций, удовлетворяющих определенным ограничениям — равенствам, неравенствам или логическим соотношениям. План, система команд управления или проект оптимальны, если они, кроме того, обращают в минимум или в максимум (в зависимости от постановки задачи) некоторую функцию от искомых параметров — показатель качества решения.
Запись (1.1)—(1.3), вполне осмысленная при детерминированных значениях параметров условий задачи, теряет определенность и требует дополнительных разъяснений при случайных значениях исходных данных. Между тем во многих прикладных задачах коэффициенты cjцелевой функции, элементы матрицы условий А или составляющие вектора ограничений b — случайные величины. Исходная информация для планирования, проектирования и управления, как правило, недостаточно достоверна. Планирование производства обычно ведется в условиях неполной информации об обстановке, в которой будет выполняться план и реализовываться произведенная продукция. Во всех случаях в моделях математического программирования, к исследованию которых сводятся задачи планирования, проектирования и управления, отдельные или все параметры целевой функции и ограничений могут оказаться неопределенными или случайными. Естественный на первый взгляд путь анализа подобных задач—замена случайных параметров их средними значениями и вычисление оптимальных планов полученных таким образом детерминированных моделей—не всегда оправдан. При сглаживании параметров условий задачи может быть нарушена адекватность модели изучаемому явлению. Усреднение исходных данных может привести к потере полезной информации и привнести в модель ложную информацию.
Решение детерминированной задачи с усредненными параметрами может не удовлетворять ограничениям исходной модели при допустимых реализациях параметров условий.
2. Стохастическое программирование
В одних случаях опыт, статистика и изучение процессов, определяющих изменение исходных данных и формирующих условия, в которых реализуется план, проект или система управления, позволяют устанавливать те или иные вероятностные характеристики параметров целевой функции и ограничений задачи. В других случаях нет оснований, для каких бы то ни было суждений о статистических особенностях явлений, способных изменить предполагаемые значения параметров условий задачи.
Ситуации первого типа называются ситуациями, связанными с риском, а ситуации второго типа - неопределенными. И те, и другие ситуации являются предметом исследования стохастического программирования. Стохастическое программирование является разделом математического программирования, изучающего теорию и методы решения условных экстремальных задач при неполной информации о параметрах условий задачи.
Постановки задач стохастического программирования существенным образом зависят от целевых установок и информационной структуры задачи.
В приложениях стохастическое программирование используется для решения задач двух типов:
- в задачах первого типа прогнозируются статистические характеристики поведения множества идентичных экстремальных систем. Соответствующий раздел стохастического программирования будем называть пассивным стохастическим программированием;
- модели второго типа предназначены для построения методов и алгоритмов планирования и управления в условиях неполной информации. Соответствующий раздел стохастического программирования будем называть активным стохастическим программированием, подчеркивая этим действенную целевую направленность моделей.
Подходы к постановке и анализу стохастических экстремальных задач существенно различаются в зависимости от того, получена ли информация о параметрах условий задачи (или об их статистических характеристиках) в один прием или по частям (в два или более этапов). При построении стохастической модели важно также знать, необходимо ли единственное решение, не подлежащее корректировке, или можно по мере накопления информации один или несколько раз подправлять решение. Другими словами, речь идет о том, какая задача рассматривается: статическая или динамическая. В соответствии с этим в стохастическом программировании исследуются одноэтапные, двухэтапные и многоэтапные задачи.
Статические, или одноэтапные, задачи стохастического программирования представляют собой естественные стохастические аналоги детерминированных экстремальных задач, в которых динамика поступления исходной информации не играет роли, а решение принимается один раз и не корректируется. Одноэтапные стохастические задачи, как те, что порождены детерминированными моделями стохастического программирования, так и те, что имеют смысл только при случайных параметрах условий, различаются характером ограничений и выбором целевой функции.
Разработка предварительного плана и компенсация невязок - два этапа решения одной задачи. В соответствии с этим задачи рассматриваемого типа называют двухэтапными задачами стохастического программирования . Естественным обобщением двухэтапных задач являются многоэтапные (динамические) задачи стохастического программирования. Часто в процессе управления представляется возможность последовательно наблюдать ряд реализаций параметров условий и соответствующим образом корректировать план. Естественно, что как предварительный план, так и последовательные корректировки должны, помимо содержательных ограничений, учитывать априорные статистические характеристики случайных параметров условий на каждом этапе.
К анализу многоэтапных задач стохастического программирования сводятся формальные исследования численных методов планирования производства и развития экономической системы. Роль стохастических моделей и методов в исследовании закономерностей поведения экономических систем и в разработке количественных методов планирования экономики и управления производством имеет два аспекта — методологический и вычислительный. И тот и другой связаны с одной из важнейших категорий современной математической логики — с понятием сложности, точнее, с понятиями «сложность алгоритма», «сложность вычислений» и «сложность развития».
Роль вычислительного аспекта проблемы определяется тем, что планирование, управление и проектирование происходят, как правило, в условиях неполной информации. Рыночная конъюнктура, спрос на продукцию, изменения в состоянии оборудования не могут быть точно предсказаны. В условиях конкурентной экономики дополнительно возникает направленная дезинформация.
Учет случайных факторов и неопределенности в планировании и управлении — важная задача стохастического программирования. Однако этим не исчерпывается роль стохастических методов в анализе процессов. Принципы стохастического программирования дают основание для сопоставления затрат на накопление и хранение информации с достигаемым экономическим эффектом, позволяют аргументировать рациональное разделение задач между человеком и вычислительной машиной и служат теоретическим фундаментом для алгоритмизации управления сложными системами.
Принципы стохастического программирования позволяют сблизить точные, но узко направленные формальные математические методы с широкими, но нечеткими содержательными эвристическими методами анализа. И здесь, таким образом, мы переходим к методологической роли стохастического программирования в исследовании сложных систем.
В связи с оценками сложности алгоритмов и вычислений представляет смысл условно разделить задачи планирования, управления и проектирования на задачи вычислительного и не вычислительного характера. Многие задачи управления, должны быть отнесены к классу задач не вычислительного характера. Т.о. необходимо согласование сложности управляемого объекта и управляющего устройства за счет рационального упрощения объекта (разумной переформулировки задачи).
3. Формальная постановка стохастической задачи
Приведем формальную постановку многоэтапной стохастической задачи. Пусть i—набор случайных параметров i-го этапа, a xi—решение, принимаемое на i-м этапе. Обозначим k =(1 , 2 , k) , xk= (x1 , … , xn), k = 1,…, n. Общая модель многоэтапной задачи стохастического программирования имеет вид:
M(n, E(n, xn) → max, (3.1)
M (k, k (k, xk )) ≤ M(bk (k-1)), (3.2)
xk ≤ Gk , k=1,…, n. (3.3)
Здесь E (n, xn) —случайная функция от решений всех nэтапов;
(k (k, xk)) - случайная вектор-функция, определяющая ограничения k-го этапа;
bk (k-1) —случайный вектор;
Gk —некоторое множество, определяющее жесткие ограничения k-го этапа;
M (k/(k-1)) - условное математическое ожидание M(k) в предположении, что на этапах, предшествующих k - му, реализован набор (k-1) =(1,2,.. (k-1)).
Предполагается, что совместное распределение вероятностей всех случайных параметров условий задано (или, по крайней мере, известно, что оно существует). Для того чтобы постановка задачи (3.1)—(3.3) была полной, необходимо еще указать, среди какого класса функций (решающих правил) x=x(Х) от реализаций случайных исходных данных следует разыскивать решение.
К моменту, когда должно быть принято решение k-то этапа, можно успеть обработать результаты наблюдения реализаций случая на этапах s1, s2..., sk-1. В задачах решение на i-м этапе принимается после реализации случайных параметров условий на предыдущем (i—1)-м этапе.
Решающие правила имеют вид xi=xi (i-1) , i = 1,…,n, x(0)=c.
Будем называть такие задачи многоэтапными задачами стохастического программирования с условными ограничениями и с априорными решающими правилами. Сведение задачи управления к анализу модели стохастического программирования позволяет разделить процесс выбора решения на два этапа.
Первый - трудоемкий предварительный - использует структуру задачи и априорную статистическую информацию для получения решающего правила (или решающего распределения) - формулы, таблицы или инструкции, устанавливающей зависимость решения (или функции распределения оптимального плана) от конкретных значений параметров условий задачи.
Второй - нетрудоемкий оперативный этап - использует решающее правило (решающее распределение) и текущую реализацию условий для вычисления оптимального плана (или его распределения).
4. Методы решения задач стохастического программирования
Основные классы задач, для решения которых создается вычислительный комплекс непосредственно или методами стохастического расширения, формулируются как модели стохастического программирования.
Вообще говоря, все модели выбора решения, сформулированные в терминах математического программирования могут быть (в практических задачах, отвечающих управлению сложными системами и процессами, должны быть) сформулированы как модели стохастического программирования.
Соответствие формально построенных стохастических моделей содержательным постановкам является решающим условием успешного управления в условиях неполной информации. Вряд ли могут быть приведены универсальные рекомендации по выбору информационной структуры модели и статистических характеристик, используемых для формирования целевого функционала задачи и области его определения.
Анализ опыта решения практических экстремальных задач методами математического программирования свидетельствует о серьезных успехах этого подхода (и о внедрении данных методов в практику планирования, управления и проектирования) в задачах относительно простой структуры. Главным образом решаются одноэкстремальные задачи при не слишком большой размерности, когда число переменных и ограничений (в моделях достаточно общего вида) не превышает сотен или тысяч.
Однако методы детерминированного математического программирования не прививаются в системах большой сложности, отвечающих многоэкстремальным задачам или задачам большой размерности.
До сих пор нет достаточно конструктивного метода решения общей (даже линейной) двухэтапной задачи стохастического программирования. Стандартные методы выпуклого программирования в общем случае неприменимы для вычисления предварительного плана — решения выпуклой задачи первого этапа. Основная трудность в том, что целевая функция и область определения планов первого этапа заданы, вообще говоря, неявно. В случаях, когда область имеет относительно простую структуру или задача оказывается с простой рекурсией, эффективным, хотя и трудоемким методом вычисления предварительного плана, оказывается метод стохастических градиентов, представляющий собой итеративный метод типа стохастической аппроксимации.
Все это подсказывает путь алгоритмизации решения сложных задач в автоматизированных системах управления - замену трудоемких процедур, отвечающих обоснованным (точным или приближенным) методам решения детерминированных экстремальных задач, относительно простыми «законами управления» - решающими правилами или решающими распределениями стохастического расширения соответствующих задач.
Платой за упрощение задачи и за переход от громоздких алгоритмов к относительно простым решающим механизмам служат трудоемкая предварительная работа по построению «законов управления» и некоторая потеря эффективности решения задачи в каждом отдельном случае.
В литературе по стохастическому программированию описаны многочисленные модели выбора решений, сформулированные в терминах стохастического программирования. Разнообразные задачи управления запасами - классические примеры стохастических моделей. Синтез систем массового обслуживания, удовлетворяющих заданным требованиям и оптимизирующих пропускную способность системы или определяемый ею доход, сводится к решению экстремальных стохастических задач.
Контрольные вопросы
1. Что называется стохастическим программированием?
2. Для решения, каких задач может применяться стохастическое программирование?
3. Для решения, каких задач применяется линейное программирование?
4. Формулирование задачи линейного программирования.
5. Формальная постановка задачи стохастического программирования.
6. Одноэтапные и многоэтапные задачи стохастического программирования.
7. Методы решения задач стохастического программирования.
8. Особенности решения одноэкстремальные задачи стохастического программирования.
9. Особенности решения двухэтапной задачи стохастического программирования.