Регрессионный анализ. Решение оптимизационных задач

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

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

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

Постановка задачи оптимизации предполагает существование конкурирующих свойств процесса, например:

§ количество продукции - расход сырья

§ количество продукции - качество продукции

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

При постановке задачи оптимизации необходимо:

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

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

а) получить максимальную производительность при заданной себестоимости;

б) получить минимальную себестоимость при заданной производительности;

В первом случае критерий оптимизации - производительность а во втором себестоимость.

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

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

4. Учет ограничений.

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

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

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

Линейное программирование - один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого начала развиваться сама дисциплина «математическое программирование». Термин «программирование» в названии дисциплины ничего общего с термином «программирование (т.е. составление программ) для ЭВМ» не имеет, так как дисциплина «линейное программирование» возникла еще до того времени, когда ЭВМ стали широко применяться при решении математических, инженерных, экономических и др. задач. Термин «линейное программирование» возник в результате неточного перевода английского «linear programming». Одно из значений слова «programming» - составление планов, планирование. Следовательно, правильным переводом «linear programming» было бы не «линейное программирование», а «линейное планирование», что более точно отражает содержание дисциплины.

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

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

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

§ рационального использования сырья и материалов; задачи оптимизации раскроя;

§ оптимизации производственной программы предприятий;

§ оптимального размещения и концентрации производства;

§ составления оптимального плана перевозок, работы транспорта;

§ управления производственными запасами;

§ и многие другие, принадлежащие сфере оптимального планирования.

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

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

Оптимизационные задачи такого рода можно классифицировать на основе структурных особенностей нелинейных целевых функций. Если целевая функция F - квадратичная функция, то мы имеем дело с задачей квадратичного программирования; если F – это отношение линейных функций, то соответствующая задача носит название задачи дробно-линейного программирования, и т.д. Деление оптимизационных задач на эти классы представляет значительный интерес, поскольку специфические особенности тех или иных задач играют важную роль при разработке методов их решения.

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

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

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

§ Max [xl, х2,...]— возвращает наибольшее значение из xi;

§ Max[{xl, x2,...}, {yl,...},...] — выбирает наибольший элемент из нескольких списков;

§ Min[xl, x2,...] — возвращает наименьшее значение из xi;

§ Min[{xl, x2,...}, {yl,...},...] — выбирает наименьший элемент из нескольких списков.

Регрессионный анализ

Функции для проведения регрессии

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

Регрессия – зависимость среднего значения какой-либо величины от некоторой другой величины или от нескольких величин.

Функции для линейной регрессии

Другой широко распространенной задачей обработки данных является представление их совокупности некоторой функцией у(х). Задача регрессии заключается в получении параметров этой функции такими, чтобы функция приближала облако исходных точек (заданных векторами VX и VY) с наименьшей среднеквадратичной погрешностью. Чаще всего используется линейная регрессия, при которой функция у(х) имеет вид: у(х)=а+ вх и описывает отрезок прямой. К линейной регрессии можно свести многие виды нелинейной регрессии при двупараметрических зависимостях у(х).

Для проведения линейной регрессии в систему встроен ряд приведенных ниже функций:

§ corr(VX, VY) — возвращает скаляр — коэффициент корреляции Пирсона;

§ intercrpt(VX, VY) — возвращает значение параметра а (смещение линии регрессии по вертикали);

§ slope(VX, VY) — возвращает значение параметра b (наклона линии регрессии).

На рисунке 1 показан пример проведения линейной регрессии для данных, представленных значениями элементов в векторах VX и VY.

Рисунок 5 - Линейная регрессия

Как видно на рисунке 3, прямая регрессии проходит в «облаке» исходных точек с максимальным среднеквадратичным приближением к ним Чем ближе коэффициент корреляции к 1, тем точнее представленная исходными точками зависимость приближается к линейной

Функция для линейной регрессии общего вида

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

F(x, К1 ,К2, ., Kn)= K1, F1(x)+K2 F2(x)+ +КnFn(x)

Таким образом, функция регрессии является линейной комбинацией функций F1(x), F2(x), ., Fn(x), причем сами эти функции могут быть нелинейными, что резко расширяет возможности такой аппроксимации и распространяет ее на нелинейные функции

Для реализации линейной регрессии общего вида используется функция linfit(VX,VY,F) Эта функция возвращает вектор коэффициентов линейной регрессии общего вида К, при котором среднеквадратичная погрешность приближения облака исходных точек, если их координаты хранятся в векторах VX и VY, оказывается минимальной Вектор F должен содержать функции F1(x), F2(x), , Fn(x), записанные в символьном виде

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

Рисунок 6 - Пример проведения линейной регрессии общего вида

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

Функции для одномерной и многомерной полиномиальной регрессии

Введена в новую версию MathCAD и функция для обеспечения полиномиальной регрессии при произвольной степени полинома регрессии regress(VX,VY, n)

Она возвращает вектор VS, запрашиваемый функцией interp(VS,VX,VY,x), содержащий коэффициенты многочлена п-й степени, который наилучшим образом приближает «облако» точек с координатами, хранящимися в векторах VX и VY

На рисунке 7 показан пример выполнения полиномиальной регрессии Для вычисления коэффициентов полинома регрессии используется функция submatrix

Рисунок 7 - Полиномиальная регрессия

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

Функция regress создает единственный приближающий полином, коэффициенты которого вычисляются по всей совокупности заданных точек, т е глобально Иногда полезна другая функция полиномиальной регрессии, дающая локальные приближения отрезками полиномов второй степени, — loess(VX, VY, span). Эта функция возвращает используемый функцией interp(VS,VX,VY,x) вектор VS, дающий наилучшее приближение данных (с координатами точек в векторах VX и VY) отрезками полиномов второй степени Аргумент span>0 указывает размер локальной области приближаемых данных (рекомендуемое начальное значение — 0,75) Чем больше span, тем сильнее сказывается сглаживание данных При больших span эта функция приближается к regress(VX,VY,2) сказывается сглаживание данных