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

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

Министерство образования и науки РФ

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Сибирский государственный индустриальный университет»

Кафедра информационных технологий в металлургии

Курсовая работа

по дисциплине «Оптимизация в технике и технологиях»

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

Выполнил: ст. группы ИСТ-11

Попов П.В.

Проверил: к.т.н., доцент Рыбенко И.А.

Новокузнецк 2014

Оглавление

1. Теоретическая особенности оптимизации метода Гаусса-Зейделя

2. Программная реализация системы на ЭВМ

2.1 Структура программы

2.2 Инструкция по использованию программы

2.3 Результаты отладки программы на контрольных примерах

3. Исследование работы методов

Заключение

1. Теоретическая особенности оптимизации метода Гаусса-Зейделя

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

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

U = f(x₁, x₂).

Функция имеет экстремум в виде максимума. Необходимо найти x₀ = (x₁₀, x₂₀) такие, которые определяют максимум функции

U_max = f(x₁₀, x₂₀).

В трехмерном пространстве координат U, x₁, x₂ функция

U = f(x₁, x₂)

описывает некоторую поверхность с экстремумом в виде вершины. Если рассечь эту поверхность плоскостью U = const на определенном уровне и спроецировать пересечение на плоскость x₁, x₂ то на плоскости отобразится замкнутая линия (рис.). Меняя высоту сечения, получим семейство вложенных концентрических линий, в центре которых находится экстремум с координатами x₁₀, x₂₀.

Метод покоординатного движения заключается в следующем. В исходной точке фиксируют все координаты x, кроме одной. Этой координате x_i задают приращение в сторону ее увеличения и в сторону уменьшения и получают две точки. Вычисляют значение целевой функции f в этих точках и сравнивают между собой. Следующей исходной точкой будет та, для которой функция f будет иметь наибольшее значение.

В случае двумерной целевой функции (рис. 1) происходят последовательные вычисления и движения смещение по координате x₁, затем по x₂.

Рис. 1.

При этом выполняются следующие действия.

1. В точке 1 фиксируется значение второй переменной x₂₁ = const. Задается приращение Дx₁ > 0. Определяют значения и первой переменной:

Вычисляются значения целевой функции в точках и

Значения и сравниваются между собой. Наибольшее из них определяет следующую искомую точку (точка 2 на рис. 5).

2. В точке 2 фиксируется значение первой переменной . Задается приращение Дx₂ > 0, и определяются значения и второй переменной:

Производится вычисление целевой функции для этих точек:

Значения и сравниваются между собой, и по их соотношению определяется следующая исходная точка 3. Далее происходит переход к действию 1 и т. д.

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

В методе Гаусса-Зейделя величина шага движения регулируется в зависимости от скорости изменения функции f. При этом используется соотношение

,

где t - параметр, определяющий величину шага. Знак производной определяет направление движения.

Поиск экстремума заканчивается на шаге k, когда дважды подряд выполняется неравенство , где - заданная ошибка определения экстремума

Достоинством методов покоординатного движения и Гаусса-Зейделя является простота. Недостаток - медленное движение к экстремуму, особенно когда количество входных переменных велико.

2. Программная реализация системы на ЭВМ

2.1 Структура программы

Реализация программы производилась в WPF. Windows Presentation Foundation (WPF) - это система следующего поколения для построения клиентских приложений Windows с визуально привлекательными возможностями взаимодействия с пользователем. С помощью WPF можно создавать широкий спектр приложений.

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

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

Для распознавания выражения используется сторонняя библиотека ELW.Library.Math, распространяемая по открытой лицензии.

2.2 Инструкция по использованию программы

Форма имеет компоненты для ввода функции и начального вектора поиска. Так же можно задать точно поиска. Выражение нужно вводить, руководствуясь правилами ввода для MS Excel. Программа распознает приоритеты операций. При задании границ или точности следует выбирать в качестве разделителя тот символ, который выбран в региональных настройках компьютера. (В России по умолчанию).

2.3 Результаты отладки программы на контрольных примерах

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

f(x)=(x₁-2)⁴+(x₁-2x₂)²

Результаты оптимизации показаны на рисунке 2.

Рис. 2.

3. Исследование работы методов

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

1) Точности

Рис. 3.

2) Расстояния от начального значения до минимума (при постоянной точности равной 0,01). Точка минимума выражения заранее известна (2,016 и 1,008).

Рис 4.

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

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

3) Количества входных переменных.

Рис. 5.

Получается зависимость очень похожая на функцию вида f(x)=x.

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

f(x)=(x₁²+x₂-11)²+(x₁+x₂²-7)²

Выберем четыре точки для каждого варианта расчёта: (0,0), (0,4), (0,-5), (-3,-2). Результат предоставим на рисунках с 6 по 9.

Рис. 6.

Рис. 7.

Рис. 8.

Рис. 9.

гаусс программный компьютерный windows

Заключение

В результате выполнения работы была создана система для решения задач безусловной многомерной оптимизации методам Гаусса-Зейделя. Для одномерной оптимизации выбран метод локализации оптимума. Для программной реализации выбран язык программирования С#. По результатам исследования работоспособности программы, можно сделать вывод о, том что программа способна оптимизировать функцию сколько угодно большого числа переменных. Недостаток программы заключается в неудобном вводе выражения и отсутствия поддержки множества логарифмических, тригонометрических и прочих функций.

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