39912

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

Шпаргалка

Информатика, кибернетика и программирование

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

Русский

2013-10-11

210.22 KB

117 чел.

1 Модель парной линейной регрессии. Метод наименьших квадратов для оценки параметров уравнения регрессии и проверка его адекватности.

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

Модель линейной регрессии (линейное уравнение) является наиболее распространенным (и простым) видом зависимости между экономическими переменными. Определить тип уравнения можно, исследуя зависимость графически. Сущность МНК заключается в нахождении параметров модели (а0, а1), при которых минимизируется сумма квадратов отклонений эмпирических (фактических) значений результативного признака от теоретических, полученных по выбранному уравнению регрессии: . Проводят дифференцирование S по коэффицентам и приравнивают уравнения к 0.

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

Параметр а1 называется коэффициентом регрессии. Его величина показывает среднее изменение результата с изменением фактора на единицу.

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

Коэффициент детерминации R2, - это доля дисперсии зависимой переменной, объясняемая рассматриваемой моделью зависимости, то есть объясняющими переменными

Коэффициент корреляции R  вычисляется при наличии линейной связи между результативным и несколькими факторными признаками. Пределы изменения коэффициента корреляции: 0  R  1. Чем ближе R к 1, тем точнее уравнение множественной линейной регрессии отражает реальную связь.

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

. Коэффициент регрессии считается статистически значимым, если превышает tтабл  - табличное (теоретическое) значение t-критерия Стьюдента для заданного уровня значимости  (0,05) и n-k-1 степеней свободы: , где n - число наблюдений, k - число факторных признаков.

Проверка адекватности всей модели осуществляется с помощью F-критерия и величины средней ошибки аппроксимации .

Значение средней ошибки аппроксимации, определяемой по формуле

не должно превышать 12 - 15 %.

Расчетное значение F-критерия определяется по формуле и сравнивается с табличным:

, где - коэффициент множественной детерминации.

Величина Fтабл находится по таблицам при заданном уровне значимости  (0,05) и числе степеней свободы 1= k, 2= n-k-1.  Если Fрасч  Fтабл, связь признается существенной.


2 Модель множественной линейной регрессии. Общие подходы к определению ее параметров и анализу адекватности.

Изучение связи между тремя и более связанными между собой признаками носит название множественной (многофакторной) регрессии. Требуется определить аналитическое выражение связи между результативным признаком (У) и факторными признаками (х1…хn), найти функцию .

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

Среди многофакторных регрессионных моделей выделяют линейные и нелинейные. Основное значение имеют линейные модели, которые содержат независимые переменные только в первой степени: ,где а0 - свободный член, а1, а2, . . ., аk - коэффициенты регрессии; х1, х2, . . ., хk - факторные признаки.

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

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

,   - парные коэффициенты корреляции, - коэффициенты регрессии.

Множественный коэффициент корреляции R  вычисляется при наличии линейной связи между результативным и несколькими факторными признаками. 0  R  1. Чем ближе R к 1, тем точнее уравнение множественной линейной регрессии отражает реальную связь. Частный коэффициент детерминации показывает на сколько процентов вариация результативного признака объясняется вариацией iго признака.

Проверка адекватности моделей, построенных на основе уравнений регрессии, начинается с проверки значимости каждого коэффициента регрессии. Значимость коэффициента регрессии осуществляется с помощью t-критерия Стьюдента (отношение коэффициента регрессии к его средней ошибке): . Коэффициент регрессии считается статистически значимым, если превышает tтабл  - табличное (теоретическое) значение t-критерия Стьюдента для заданного уровня значимости  (0,05) и n-k-1 степеней свободы: , где n - число наблюдений, k - число факторных признаков. Проверка адекватности всей модели осуществляется с помощью F-критерия и величины средней ошибки аппроксимации . Значение средней ошибки аппроксимации, определяемой по формуле не должно превышать 12 - 15 %. Расчетное значение F-критерия определяется по формуле и сравнивается с табличным: , где - коэффициент множественной детерминации.

Величина Fтабл находится по таблицам при заданном уровне значимости  (0,05) и числе степеней свободы 1= k, 2= n-k-1. Если Fрасч  Fтабл, связь признается существенной.


3 Понятие нелинейных моделей регрессии и их типы.

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

Различают два класса нелинейных регрессий:

1. Регрессии, нелинейные относительно включенных в анализ объясняющих переменных, но линейные по оцениваемым параметрам, например

– полиномы различных степеней –

– равносторонняя гипербола –

–полулогарифмическая функция – .

2. Регрессии, нелинейные по оцениваемым параметрам, например

– степенная – ;

– показательная – ;

– экспоненциальная – .

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

Так, парабола второй степени  приводится к линейному виду с помощью замены: x=x1, x2=x2. В результате приходим к двухфакторному уравнению , оценка параметров которого при помощи МНК приводит к системе следующих нормальных уравнений:

                 

А после обратной замены переменных получим

                    

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

К внутренне линейным моделям относятся:

- степенная функция – ,

- показательная – ,

- экспоненциальная – ,

- логистическая –,

- обратная – .

К внутренне нелинейным моделям можно отнести следующие модели:

-,

.

Степенная модель

4 Общая характеристика временных рядов и динамических моделей. Автокорреляция уровней временного ряда и выявление его структуры.

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

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

Пусть исследуется показатель Y. Его значение в текущий момент (период) времени t обозначают yt; значения Y в последующие моменты обозначаются yt+1, yt+2, … , yt+k, … ; значения Y в предыдущие моменты обозначаются  yt-1,  yt-2, … ,  yt-k, … .

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

Переменные, влияние которых характеризуется определенным запаздыванием - лаговые переменные. Лаг - временное запаздывание.

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

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

  1.  Модели с распределенными лагами – содержат в качестве лаговых переменных лишь независимые (объясняющие) переменные. Примером является модель: .
  2.  Авторегрессионные модели – это модели, уравнения которых в качестве лаговых объясняющих переменных включают зависимые переменные. Примером является модель:

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

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

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

Если наиболее высоким оказался коэффициент автокорреляции первого порядка, исследуемый ряд содержит только тенденцию (то есть трендовый компонент T). Если наиболее высоким оказался коэффициент автокорреляции порядка τ, ряд содержит циклические колебания  (циклическую компоненту S) с периодичностью в τ моментов времени. Если ни один из коэффициентов автокорреляции не является значимым, можно сделать одно из двух предположений относительно структуры ряда: либо ряд не содержит тенденции и циклических колебаний, либо ряд содержит сильную нелинейную тенденцию, для выявления которой нужно провести дополнительный анализ.


5 Моделирование тенденции (тренда) временного ряда. Экстраполяция и прогнозирование в рядах динамики.

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

Применение экстраполяции базируется на следующих предпосылках:

  1. развитие исследуемого явления в целом следует описывать плавной кривой
  2. общая тенденция развития явления в прошлом и настоящем не претерпевает изменений в будущем.

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

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

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

Экстраполяцию можно представить формулой , где - прогнозируемый уровень, - текущий уровень прогнозируемого ряда, Т – период укрупнения, - параметр уравнения тренда.

Выделяют следующие методы экстраполяции:

  1. среднего абсолютного прироста - может быть выполнено в том случае, если есть уверенность считать общую тенденцию линейной, то есть метод основан на предположении о равномерном изменении уровня (под равномерностью понимается стабильность абсолютных приростов).,
  2. среднего темпа роста,
  3. экстраполяцию на основе выравнивания рядов по какой-либо аналитической формуле - аналитическое выражение тренда. При этом для выхода за границы исследуемого периода достаточно продолжить значения независимой переменной времени (t). Предполагается, что размер уровня, характеризующего явление, формируется под воздействием множества факторов, причем не представляется возможным выделить отдельно их влияние. В связи с этим ход развития связывается не с какими-либо конкретными факторами, а с течением времени, то есть y = f(t).

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

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

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

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

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

6 Общая характеристика систем уравнений, используемых в эконометрике.

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

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

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

– система независимых уравнений – когда каждая зависимая переменная y рассматривается как функция одного и того же набора факторов хi

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

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

y1=a11x1+a12x2+…+a1mxm+E1

yn=an1x1+an2x2+..+anmxm+En

система рекурсивных уравнений – когда зависимая переменная у одного уравнения выступает в виде фактора х в другом уравнении.

Для построения такой системы и нахождения ее параметров используется метод наименьших квадратов, применяемый последовательно к каждому уравнению в отдельности;
y1=a11x1+a12x2+…+a1mxm+E1

y2=b21y1+a21x1+…+a2mxm+E2

yn=bn1y1+bn2y2+…+b(nm-1)ym+an1x1+an2x2+..+anmxm+En

– система взаимосвязанных (совместных) уравнений – когда одни и те же зависимые переменные в одних уравнениях входят в левую часть, а в других – в правую. Система взаимозависимых уравнений получила название системы совместных или одновременных уравнений. Тем самым подчеркивается, что в системе одни и те же переменные y одновременно рассматриваются как зависимые в одних уравнениях и как независимые в других. В эконометрике эта система уравнений называется также структурной формой модели. В отличие от предыдущих систем каждое уравнение системы одновременных уравнений не может рассматриваться самостоятельно, и для нахождения его параметров традиционный М.Н.К. неприменим. С этой целью используются специальные приемы оценивания(косвенный и двухшаговый методы наименьших квадратов).

y1=b12y2+b13y3+…+b1nyn+a11x1+…+a1mxm+E1

y2=b21y1+b23y3+…+b2nyn+a21x1+…+a2mxm+E2

yn=bn1y1+bn2y2+…+b(nm-1)ym+an1x1+an2x2+..+anmxm+En


7 Статистические характеристики связей между случайными величинами, модели и алгоритмы их анализа и обработки.

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

Наиболее употребляемыми характеристиками связи 2х СВ являются меры их линейной связи.

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

, , ,   -1<f<1.

Корреляционный анализ дает возможность установить, ассоциированны ли наборы данных по величине, т.е. большие значения из одного набора данных связаны с большими значениями другого набора (+ корреляция), или малые значения одного набора данных связаны с большими значениями другого набора данных ( «-» корреляция), или данные 2х диапазонов никак не связаны (корреляция близка к 0).

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

Ковариационный анализ дает возможность установить, ассоциированны ли наборы данных по величине, т.е. большие значения из одного набора данных связаны с большими значениями другого набора (+ ковариация), или малые значения одного набора данных связаны с большими значениями другого набора данных ( «-»ковариация), или данные 2х диапазонов никак не связаны (ковариация близка к 0).

«+» переменные изменяются в одном направлении

«-» в противоположных.

Закон распределения полностью характеризует случайную величину. Однако часто закон распределения неизвестен и приходится пользоваться, так называемыми, числовыми характеристиками случайной величины. К ним относятся:

  1. Математическое ожидание M,
  2. Дисперсия D,
  3. Среднее квадратичное отклонение .

Математическое ожидание дискретной случайной величины X – это сумма произведений всех ее возможных значений на их вероятности.

Математическое ожидание непрерывной случайной величины X, возможное значение которой принадлежит отрезку [a,b] – это определенный интеграл

Дисперсия – средний квадрат отклонений индивидуальных значений признака от средней величины.

Для непрерывной случайной величины:

СКО – обобщающая характеристика размеров вариации признака в совокупности. =


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

Одномерная оптимизация заключается в нахождении точки х*, в которой целевая функция f(x) принимает минимальное (максимальное) значение: f(х*) → min (max). Функция f(x) имеет локальный минимум, если в окрестности х* справедливо неравенство: f(x) > f(х*). Глобальный минимум – неравенство выполняется на множестве .

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

Если вторая производная в данной точке больше 0, то это min. Наоборот – max.

Многомерная безусловная оптимизация.

Пусть задана функция n действительных переменных f(x1, …, xn)=f(x), определенная на множестве , х – вектор-столбец , обозначающий точку в n-мерном евклидовом пространстве с координатами x1, …, xn.

Функция f(x) имеет локальный минимум в точке , если в ее окрестности выполняется: f(x*)  f(x), глобальный минимум – неравенство выполняется на множестве .

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

Данная система может иметь как одно, так и несколько решений. Точки х* называются стационарными. Для проверки полученных точек на экстремум необходимо провести исследование вторых производных. При этом рассчитывается матрица Гессе Н(х*), представляющая квадратную матрицу вторых частных производных f(x). Достаточным условием минимума является положительно определенная матрица Н, а максимума - отрицательно.

Основные этапы решения задач оптимизации:

1. Выделение объекта или системы (выделение совокупности факторов, влияющих на целевую функцию; формирование вида допустимой области и характера ограничений).

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

3. Математическое описание объекта, т.е. построение мат. модели.

4. Выбор способа оптимизации (прямой – на объекте методами поиска и планирования эксперимента; на основе мат. моделей).

5. Выбор метода оптимизации, который определяется тремя факторами: вид критерия, характер ограничений, размерность задачи. Аналитические, графические, численные.

6. Реализация задачи на ЭВМ

7. Анализ результатов и проверка на объекте.


9 Симплексные методы решения задач оптимизации.

Обычный симплекс – метод.

Симплексом в пространстве n переменных называют выпуклый многогранник, имеющий n+1 вершину. В обычном симплекс-методе используется правильный симплекс (все ребра которого равны). На примере двумерного случая рассмотрим решение задачи оптимизации. Выбирается начальный симплекс – треугольник, т.к. двумерное пространство, с вершинами х(1) – х(2) – х(3). Размещение правильного симплекса в пространстве может быть осуществлено двумя путями:

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

2.Центр симплекса перемещается в начало координат, а (n+1)-я вершина на ось х0. Остальные вершины располагаются симметрично относительно координатных осей.

В вершинах исходного симплекса рассчитывается значение целевой функции ,,. Из этих трех значений выбирается «наихудшая» точка. Через центр тяжести противолежащей грани хц.т. строится новая вершина симплекса х(4). В результате получается новый симплекс х(2)(3)(4). Вычисляется значение целевой функции в х(4). Среди новых вершин ищется «наихудшая». Эта вершина вновь отображается через середину противолежащей грани, вся процедура повторяется. Признаком окончания поиска является процедура зацикливания, когда вновь отображенная вершина оказывается «наихудшей». В этом случае необходимо уменьшить размеры симплекса. Процедура повторяется до тех пор, пока длина ребра не станет меньше заданной точности.

Метод деформируемых многогранников (метод Нельдера – Мида).

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

  1. Выбирают начальный симплекс и рассчитывают целевую функцию в вершинах.
  2. Из найденных значений ищут и .
  3. Отображают «наихудшую» вершину относительно центра тяжести противоположной грани. .
  4. а) , то происходит растяжение симплекса, β > 1 ,

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

б) , то сжатие β < 1.

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


10 Градиентные методы решения задач оптимизации.

К численным методам первого порядка относятся алгоритмы, в которых в процессе поиска кроме информации о самой функции используется информация о производных первого порядка (градиенте). К таким методам относятся: метод градиента, метод наискорейшего градиентного спуска (крутого восхождения), метод покоординатного спуска (метод релаксаций), метод сопряженных градиентов (Флетчера-Ривса) и другие. Во всех этих методах вектор градиента определяют одним из трех способов: аналитически, численным дифференцированием, линеаризацией функции в некоторой области (метод Бокса-Уилсона). Суть всех методов первого порядка заключается в использовании вектора градиента для определения направления движения к оптимуму. Вектор градиента обладает рядом свойств, которые и обуславливаю его  эффективное применение при поиске экстремальных значений функции. Поэтому иногда методы этой группы называют градиентными. Поскольку в точке экстремума градиент функции обращается в ноль, это свойство часто используется для проверки условия окончания поиска в методах первого порядка .

Метод градиента. Общий алгоритм всех градиентных методов при поиске максимума заключается в построении из некоторой начальной точки  последовательности приближений  где  – скаляр, определяющий величину шага в направлении градиента. При поиске минимума f(x) следует двигаться в направлении противоположном направлению градиента. Величина h  сильно влияет на траекторию спуска и в целом на эффективность метода. При большом значении h траектория спуска будет представлять собой колебательный процесс, а при слишком больших h процесс может расходиться. При выборе малых h траектория спуска будет плавной, но и процесс будет сходиться очень медленно. Существует несколько разновидностей метода градиента: 1) с постоянным шагом 2) с нормированным вектором градиента 3) с адаптацией шага

Градиентные методы с дроблением шага. Методы с постоянным шагом.

Величина шага αk выбирается: , где 0 < ε < 1 - произвольно выбранная постоянная величина. При минимизации функции выбираем α > 0. На k-й итерации проверяем выполнение неравенства при αk = α. Если оно выполнено, полагаем αk = α и переходим к следующей итерации. Если нет, то шаг αk дробим до тех пор, пока оно не выполнится.

Метод наискорейшего спуска или крутого восхождения Бокса - Уилсона.

Метод наискорейшего спуска – это процесс, на каждой итерации которого шаг αk выбирается из условия минимума функции f(x) в направлении движения, т.е. .

X0

X1

X2

f(x)=c3

f(x)=c2

f(x)=c1

X*

-f’(x0)

-f’(x1)

-f’(x2)

В этом методе направление движения из точки xk касается линии уровня в точке xk+1. Последовательность точек x0, x1, … , xk, зигзагообразно приближается к точке минимума х*, причем звенья этого зигзага ортогональны между собой. Шаг α выбирается из условия минимизации по α функции , поэтому .Т.о., направления спуска на двух последовательных итерациях взаимно ортогональны.


11. Постановка и методы решения задачи линейного программирования. Ее геометрическая и экономическая интерпретации.

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

Задача ЛП в общем случае формулируется как нахождение таких значений действительных переменных x1 ,x2, …, xn, для которых линейная целевая функция f(x) принимает min (max) значение на некотором множестве  – общая задача ЛП. В матричной форме (стандартная задача):

называется симметричной формой записи задачи ЛП Каноническая форма записи задачи ЛП:  

Для решения задач ЛП разработано много методов, которые можно разделить на две группы: конечные (точные), т.е. гарантирующие нахождение точного решения за конечное число шагов, и приближенные. Конечные методы можно разделить на три группы: 1) последовательного улучшения плана (симплекс-метод Данцинга) и его модификации 2) последовательного уточнения оценок (двойственный симплекс метод) 3) метод одновременного решения прямой и двойственной задач. К приближенным методам относятся различные варианты градиентных систем оптимизации, методы случайного поиска. Наибольшее распространение получили симплекс метод решения задачи ЛП и его наиболее часто встречающаяся модификация – двухфазный симплекс метод, по существу представляющие собой последовательный перебор угловых точек, при котором значение целевой функции улучшается от итерации к итерации.

Для задачи ЛП с n переменными, подчиненными m ограничениям (m<n), можно получить решение, придавая каким либо из (n-m) переменным  произвольные значения  и разрешая систему m уравнений относительно оставшихся m переменных. Когда (n-m) переменных приравниваются к нулю. Переменные приравненные к нулю, называются свободными, остальные базисными и образуют базис. Если полученное решение содержит только положительные компоненты, то оно называется базисным допустимым или опорным планом. Эк. содержание задачи определяется 3 факторами: 1) b1, b2,…,bm – ограниченные ресурсы; 2) j=1,2,…,n – возможные способы их использования; 3) цель наиболее эффективного использования ресурсов. сj-это оценка эффективности j-того способа использования ресурсов. Графически задача решается для 2- и 3-мерного пространства. Пусть задача ЛП задана в двумерном пространстве, т.е. ограничения содержат две переменные. В этом случае каждое условие определяет полуплоскость с граничной прямой: ai1x1+ai2x2=bi ,  i=(1,2,…,m), x1=0, x2=0. В итоге образовывается плоскость, ограниченная всеми прямыми – допустимая область – многоугольник. Необходимо найти точку многоугольника, в которой прямая F(x) = c1x1 + c2x2 = 0 является опорной и функция достигает min (max). Т.о. оптимальное решение - одна из вершин многоугольника ОДР.

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

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

12. Транспортная задача линейного программирования. Постановка и методы решения.

Транспортная задача (классическая) — задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи).

Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку).

Методы решения

Классическую транспортную задачу можно решить симплекс-методом, но в силу ряда особенностей её можно решить проще (для задач малой размерности). Условия задачи располагают в таблице, вписывая в ячейки количество перевозимого груза из в груза , а в маленькие клетки — соответствующие тарифы .

Итерационное улучшение плана перевозок

Нахождение опорного плана

Требуется определить опорный план и путём последовательных операций найти оптимальное решение. Опорный план можно найти следующими методами: «северо-западного угла», «наименьшего элемента», двойного предпочтения и аппроксимации Фогеля.

Метод северо-западного угла (диагональный)

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

Метод наименьшего элемента

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

Алгоритм:

  1. Из таблицы стоимостей выбирают наименьшую стоимость и в клетку, которая ей соответствует, вписывают большее из чисел.
  2. Проверяются строки поставщиков на наличии строки с израсходованными запасами и столбцы потребителей на наличие столбца, потребности которого полностью удовлетворены. Такие столбцы и строки далее не рассматриваются.
  3. Если не все потребители удовлетворены и не все поставщики израсходовали товары, возврат к п. 1, в противном случае задача решена.

Итерации

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

  1.  Метод падающего камня (нем.)
  2.  Метод потенциалов (нем.).


13. Ресурсная задача, классическая постановка и основные методы ее решения

Типичным примером задачи ЛП является задача распределения ресурсов, ограничения-равенства в которых соответствуют необходимости полного использования ресурсов. Коэффициенты aij обычно означают либо расход i-того ресурса на производство единицы j-той продукции (ресурсом может быть сырье, машинное время, электроэнергия и др.), либо содержание некоторого ингредиента в исходном ресурсе (железа в руде, золы в угле, белков в пищевом продукте и т.д.). Свободные члены bi обычно означают запас ресурса или потребное количество ингредиента в производимой продукции. Постановка задачи: для изготовления j видов продукции на предприятии используют i видов сырья. При этом производство ограниченно количеством ежедневно получаемого сырья b1, b2,…,bi aij - количество единиц i-того вида сырья, затрачиваемых на изготовление j-той продукции. pj-величина прибыли получаемой от реализации единицы j-той продукции. Требуется составить такой план выпуска продукции, чтобы при ее реализации получить максимальную прибыль. Обозначим через xj –количество единиц j-той продукции выпускаемых ежедневно. Прибыль от реализации этой продукции будет равна p1+p2+…+pj и ее нужно максимизировать: ; количество ресурсов ограничено: , i = 1,2, …,m. Кроме того, количество продукции неотрицательное число, поэтому: xj , j = 1,2,…,n.

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

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


14. Постановка задачи нелинейного программирования. Классические методы ее решения для системы ограничений в виде равенств

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

В задаче НЛП требуется найти такой вектор переменных x=(x1, x2, …, xn), для которого min(max), при условиях .

Рассмотрим частный случай общей задачи НЛП, предполагая, что система ограничений содержит только уравнения, а f(x) и hi(x) - функции непрерывные вместе со своими частными производными: max(min) и hi(x)=0 , . Данную задачу называют задачей на условный экстремум или классической задачей оптимизации. D - допустимое множество, на котором определен критерий, зависит от соотношения d = n - m - дефект системы. 1. d = 0, если система уравнений является совместной, D - совокупность корней системы. В этом случае для решения задачи достаточно просмотреть эту совокупность и выбрать ту точку, в которой f(x) оптимальна. Если система линейна, то система имеет единственный корень. Если нелинейная, то число корней может быть сколько угодно большим. 2. d = 1, если система линейна - множество D - прямая, d=2 – плоскость, d=3 многогранник, если нелинейна при d=1 множество D представляет собой некоторую кривую, при d=2 – поверхность, при d=2 и более – конус. 3. d < 0, исключив лишние ограничения, придем к одному из рассмотренных вариантов или определим несовместимость системы. 4. при d > 0 поступают следующим образом. Часть переменных - m, выразим в явном виде из ограничений через другие n-m. В целевую функцию f(x) вместо xn-m+1, xn-m+2, …., xn подставляем преобразованные переменные. В результате получаем задачу безусловной оптимизации меньшей размерности f(x1, x2, …xn-m, )min (max). Можем воспользоваться необходимыми условиями экстремума и найти решение продифференцировав целевую функцию по всем переменным и приравняв их к нулю.

Не всегда удается получить разрешение в форме в элементарных функциях; в этом случае обычно используется метод множителей Лагранжа. Для решения задачи вводят набор дополнительных переменных , называемых множителями Лагранжа и составляют функцию Лагранжа. Необходимые условия экстремума функции f(x) при наличии ограничений можно получить, приравняв нулю частные производные функции F(x,) по всем xj, j=, и по всем , i=. Точка в которой достигается относительный max (min) должна удовлетворять системе из m+n уравнений

- функция Лагранжа

Каждая точка x, в которой достигается относительный max (min) при x, будет являться решением системы. Этот метод позволяет найти лишь необходимые условия существования условного экстремума для непрерывных функций, имеющих непрерывные производные. Полученные решения могут и не давать экстремального значения функции f(x). Поэтому найденные т.о. значения переменных должны быть проверены на экстремум с помощью анализа производных более высокого порядка.


15. Задачи управления запасами, назначение, основные модели и алгоритмы, реализующие задачи управления запасами.

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

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

Любая модель управления запасами в конечном счете должна дать ответ на два вопроса:

1. Какое количество продукции заказывать? 2. Когда заказывать?

Модель управления запасами с фиксированным размером заказа

Название модели говорит о ее ключевом параметре – размере заказа. Он строго зафиксирован и не меняется при изменении условий движения запаса. Так как размер восполняющего заказа представляет собой исходную информацию для расчета других параметров модели, требуется зафиксировать оптимальный или близкий к оптимальному размер заказа. Методика управления запасами на основе фиксации размера заказа заключается в том, что заказы на пополнение запаса делаются в момент снижения запаса в объеме, равном оптимальному размеру заказа. Все параметры модели рассчитываются таким образом, что при соблюдении исходных данных модель гарантирует бездефицитное обслуживание потребности в условиях определенности (т.е. в условиях постоянного темпа потребления). Исходные данные для расчета параметров модели с фиксированным размером заказа: объем потребности в запасе; оптимальный размер заказа; время выполнения заказа; возможные задержки поставки. Расчетные параметры модели с фиксированным размером заказа: максимальный желательный запас; пороговый уровень запаса; страховой запас.

Модель управления запасами с фиксированным интервалом времени между заказами

В модели заказы делаются в строго определенные моменты времени, которые отстают друг от друга на равные интервалы. Фиксированный интервал времени между заказами должен иметь оптимальный размер. Оптимизация уровня запаса связывается с оптимизацией размера заказа на восполнение запаса. Таким образом, определить оптимальный интервал времени между заказами следует на основе оптимального размера заказа. Оптимальный размер заказа позволяет минимизировать совокупные затраты на содержание и пополнение запаса, а также достичь наилучшего сочетания таких факторов, как используемая площадь складских помещений, издержки на хранение запаса и стоимость заказа. Расчет интервала времени между заказами можно производить следующим образом:, где  - интервал времени между заказами; N – число рабочих дней в плановом периоде;  - оптимальный размер заказа; S – объем потребности в запасе, единиц; Методика управления запасами на основе фиксации интервала между заказами заключается в том, что заказы на пополнение запаса делаются в заранее определенный момент через фиксированные интервалы между заказами в размере, который обеспечивает пополнение запасами до максимально желательного уровня. Размер заказа Q является постоянно пересчитываемой величиной.

 


 

А также другие работы, которые могут Вас заинтересовать

49722. РАССЧЁТ ОСНОВНЫХ ХАРАКТЕРИСТИК ЦИФРОВОЙ СИСТЕМЫ ПЕРЕДАЧИ НЕПРЕРЫВНЫХ СООБЩЕНИЙ 670 KB
  Проведен анализ сложного входного сигнала и проанализировано его прохождение через схемы разработанных радиотехнических устройств. СПИСОК СОКРАЩЕНИЙ АМ амплитудная модуляция ИКМ импульснокодовая модуляция ОФМ относительная фазовая модуляция СПМ спектральная плотность мощности ТЭС теория электрической связи ФМ фазовая модуляция ФНЧ фильтр нижних частот ЦСП цифровая система передачи ОСНОВНЫЕ ОБОЗНАЧЕНИЯ аt передаваемое непрерывное сообщение bt непрерывный сигнал соответствующий передаваемому сообщению bикмt...
49723. Розробка технології термічної обробки шпильки 161.88 KB
  У проекті був проведений вибір матеріалу для виготовлення деталі відповідного призначення типу шпилька та вибраний режим її термічної обробки. Було запропоновано прогресивні методи термічної обробки, гартування та відпуск. Був проведений вибір основного та допоміжного обладнання.
49724. Совершенствование обязательно документированных процедур 1004.28 KB
  АНАЛИЗ ПРОЦЕДУРЫ ПРОВЕДЕНИЯ АУДИТА. КРАТКОЕ РАЗЪЯСНЕНИЕ ЭТАПОВ АУДИТА. Аудит систематический независимый и документированный процесс получения свидетельств аудита и объективного их оценивания с целью установления степени выполнения согласованных критериев аудита Аудитор – лицо обладающее компетентностью для проведения аудита
49725. Оценка кредитоспособности физического лица 346 KB
  Целью данной курсовой работы является оценка кредитоспособности клиента от различных параметров. Основными задачами настоящей курсовой работы являются: Изучение факторов, влияющих кредитоспособность; Изучение принципов работы нейросети с использованием программы «Нейросимулятор»;
49726. ТЕПЛОВЫЕ И МЕТАЛЛУРГИЧЕСКИЕ ПРОЦЕССЫ ПРИ СВАРКЕ 658.36 KB
  Цель работы разработка методики теплового расчета расчетов химического состава металла оценки равновесной концентрации кислорода и оценки стойкости металла шва к образованию горячих трещин. В результате исследования было рассчитано и построено температурное поле определен химический состав металла шва по смешению и с учетом коэффициентов перехода определена концентрация кислорода и оценена стойкость металла шва к образованию горячих трещин.1 Расчет состава металла шва 16 6.3 Оценка склонности металла шва к образованию горячих трещин 27...
49728. Проблема оценки эффективности инвестиционных проектов на действующих промышленных предприятиях 252.33 KB
  Инновационная деятельность – одна из важнейших составляющих деятельности любого предприятия, в том числе и промышленных. Без составления и грамотной реализации инвестиционной стратегии невозможно достижение и поддержание в долгосрочном плане не только конкурентных преимуществ предприятия, но и его нормального функционирования.