Реферат Выбор оптимального места строительства очистного сооружения

Работа добавлена на сайт bukvasha.net: 2015-10-28

Поможем написать учебную работу

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

Предоплата всего

от 25%

Подписываем

договор

Имя

Выберите тип работы:

Принимаю Политику конфиденциальности

Скидка 25% при заказе до 17.2.2025

Санкт-Петербургский Государственный Технологический Институт

(Технический Университет)
Кафедра математического моделирования и оптимизации химико-технологических процессов
Факультет

Курс

Дисциплина: Системный анализ химической технологии
КУРСОВАЯ РАБОТА

Вариант № 4

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

                                                                            Студент:
                                                                            Преподаватель:
Оценка за курсовую работу:
Санкт-Петербург

2011

Введение

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

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

При проектировании ХТС решаются следующие задачи:

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

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

Задача анализа ХТС:

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

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

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

Задание

Выбор оптимального места строительства очистного сооружения. Сточные воды трех химических комбинатов, расположенных и точках В₁ В2, В3, должны подаваться для обработки на очистное сооружение.

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

R=A₁W₁L₁+A₂W₂L₂+A₃W₃L₃

где L_i – длина соответствующего участка трубопровода, км,

определяется по формуле

A_i – коэффициент, учитывающий сложность строительства участка трубопровода, руб.*ч/км*м³;

W_i –объемный расход, м³/ч;

X_i, У_i – координаты химического комбината, км;

X, У – координаты очистного сооружения, км;

Условие окончания счета

Решение задачи провести с помощью градиентных методов. Выполнить сравнительный анализ эффективности методов.

Вариант задания ниже.

1 Теория : Постановка задачи решения системы уравнений в терминах методов оптимизации

Задача решения системы уравнений:

$\left\{ \begin{array}{lcr} f_1(x_1, x_2, \ldots, x_n) & =& 0 \\ \ldots & & \\ f_n(x_1, x_2, \ldots, x_n) & =& 0 \end{array}\right.$ (1)

с n $x_1, x_2, \ldots, x_n$ эквивалентна задаче минимизации функции

$F(x_1, x_2, \ldots, x_n)\equiv\sum_{i=1}^n|f_i(x_1, x_2, ..., x_n)|^2$ (2)

или какой-либо другой возрастающей функции от абсолютных величин | f_i | невязок (ошибок) $f_i = f_i(x_1, x_2, \ldots, x_n)$ , $i=1, 2, \ldots,n$ . Задача отыскания минимума (или максимума) функции n переменных и сама по себе имеет большое практическое значение.

Для решения этой задачи итерационными методами начинают с произвольных значений $x_i^{[0]} (i = 1, 2, ..., n)$ и строят последовательные приближения:

$\vec{x}^{[j+1]}=\vec{x}^{[j]}+\lambda^{[j]} \vec{v}^{[j]}$

или покоординатно:

$x^{[j+1]}_i = x^{[j]}_i + \lambda^{[j]}v^{[j]}_i ,\quad i=1, 2, \ldots,n,\quad j = 0, 1, 2, \ldots$ (3)

которые сходятся к некоторому решению $\vec{x}^{[k]}$ при ${j\to\infty}$ .

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

$v^{[j]}_1: v^{[j]}_2: \ldots :v^{[j]}_n$ .

Величина шага (расстояние, на которое надо передвинуться в заданном направлении в поисках экстремума) определяется значением параметра λ^[j], минимизирующим величину $F(x^{[j+1]}_1, x^{[j+1]}_2, \ldots, x^{[j+1]}_n )$ как функцию от λ^[j]. Эту функцию обычно аппроксимируют её тейлоровским разложением или интерполяционным многочленом по трем-пяти выбранным значениям λ^[j]. Последний метод применим для отыскания max и min таблично заданной функции F(x₁,x₂,...,x_n).

1.1 Градиентные методы

Основная идея методов заключается в том, чтобы идти в направлении наискорейшего спуска, а это направление задаётся антиградиентом $-\nabla F$ :

$\overrightarrow{x}^{[j+1]}=\overrightarrow{x}^{[j]}-\lambda^{[j]}\nabla F(\overrightarrow{x}^{[j]})$

где λ^[j] выбирается

·                     постоянной, в этом случае метод может расходиться;

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

·                     наискорейшим спуском: $\lambda^{[j]}=\mathrm{argmin}_{\lambda} \,F(\vec{x}^{[j]}-\lambda^{[j]}\nabla F(\vec{x}^{[j]}))$

1.2 Метод наискорейшего спуска (метод градиента)

Выбирают $v^{[j]}_i = -\frac{\partial F}{\partial x_i}$ , где все производные вычисляются при $x_i = x^{[j]}_i$ , и уменьшают длину шага λ^[j] по мере приближения к минимуму функции F.

Для аналитических функций F и малых значений f_i тейлоровское разложение F(λ^[j]) позволяет выбрать оптимальную величину шага

$\lambda^{[j]}=\frac{\sum_{k=1}^n(\frac{\partial F}{\partial x_k})^2}{\sum_{k=1}^n\sum_{h=1}^n\frac{\partial^2 F}{\partial x_kdx_h}\frac{\partial F}{\partial x_k}\frac{\partial F}{\partial x_h}}$ (5)

где все производные вычисляются при $x_i = x^{[j]}_i$ . Параболическая интерполяция функции F(λ^[j]) может оказаться более удобной.

Алгоритм

1.                 Задаются начальное приближение и точность расчёта $\vec{x}^0, \quad \epsilon$

2.                 Рассчитывают $\overrightarrow{x}^{[j+1]}=\overrightarrow{x}^{[j]}-\lambda^{[j]}\nabla F(\overrightarrow{x}^{[j]})$ , где $\lambda^{[j]}=\mathrm{argmin}_{\lambda} \,F(\vec{x}^{[j]}-\lambda^{[j]}\nabla F(\vec{x}^{[j]}))$

3.                 Проверяют условие останова:

o                     Если $|\vec{x}^{[j+1]}-\vec{x}^{[j]}|>\epsilon$ , то j = j + 1 и переход к шагу 2.

o                     Иначе $\vec{x}=\vec{x}^{[j+1]}$ и останов.

1.3 Метод покоординатного спуска (Гаусса—Зейделя)

Улучшает предыдущий метод за счёт того, что на очередной итерации спуск осуществляется постепенно вдоль каждой из координат, однако теперь необходимо вычислять новые $\lambda \quad n$ раз за один шаг.

Алгоритм

1.                 Задаются начальное приближение и точность расчёта $\vec{x}^0_0, \quad \epsilon$

2.                 Рассчитывают $\left\{\begin{array}{lcr} \vec{x}^{[j]}_1 & = & \vec{x}^{[j]}_0-\lambda^{[j]}_1\frac{\partial F(\vec{x}^{[j]}_0)}{\partial x_1}\vec{e}_1 \\ \ldots & & \\ \vec{x}^{[j]}_n & = & \vec{x}^{[j]}_{n-1}-\lambda^{[j]}_n\frac{\partial F(\vec{x}^{[j]}_{n-1})}{\partial x_n}\vec{e}_n \end{array} \right.$ , где $\lambda^{[j]}_i=\mathrm{argmin}_{\lambda} \,F\left( \vec{x}^{[j]}_{i-1}-\lambda^{[j]}\frac{\partial F(\vec{x}^{[j]}_{i-1})}{\partial x_{i-1}} \vec{e}_i \right)$

3.                 Проверяют условие останова:

o                     Если $|\vec{x}^{[j]}_n-\vec{x}^{[j]}_0|>\epsilon$ , то $\vec{x}^{[j+1]}_0=\vec{x}^{[j]}_n,\quad j=j+1$ и переход к шагу 2.

o                     Иначе $\vec{x}=\vec{x}^{[j]}_n$ и останов.

1.4 Метод сопряжённых градиентов

Метод сопряженных градиентов — метод нахождения локального минимума функции на основе информации о её значениях и её градиенте. В случае квадратичной функции в $\mathbb{R}^n$ минимум находится за n шагов.

Определим терминологию:

Пусть $\vec{S_1},\ldots,\vec{S_n} \in \mathbb{X} \subset \mathbb{R}^n\!$ .

Введём на $\mathbb{X}\!$ целевую функцию $f(\vec{x})\in \mathrm{C^2}(\mathbb{X})\!$ .

Вектора $\vec{S_1},\ldots,\vec{S_n}\!$ называются сопряжёнными, если:

· $\vec{S_i}^T H \vec{S_j}=0, \quad i\neq j, \quad i,j=1,\ldots,n\!$

· $\vec{S_i}^T H \vec{S_i}\geqslant 0, \quad i=1,\ldots,n\!$

где $H\!$ — матрица Гессе $f(\vec{x})\!$ .

Теорема (о существовании).
Существует хотя бы одна система $n\!$ сопряжённых направлений для матрицы $H\!$ , т.к. сама матрица $H\!$ (её собственные вектора) представляет собой такую систему.

1.4.1 Обоснование метода

Нулевая итерация

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

Пусть $\vec{S_0}=-\nabla f(\vec{x_0})\qquad (1)\!$

Тогда $\vec{x_1}=\vec{x_0}+\lambda_1 \vec{S_0} \qquad (2)\!$ .

Определим направление $\vec{S_1}=-\nabla f(\vec{x_1})+\omega_1 \vec{S_0}\!$ так, чтобы оно было сопряжено с $\vec{S_0}\!$ :

$\vec{S_0}^T H \vec{S_1}=0 \qquad (3)\!$

Разложим $\nabla f(\vec{x})\!$ в окрестности $\vec{x_0}\!$ и подставим $\vec{x}=\vec{x_1}\!$ :

$\nabla f(\vec{x_1})-\nabla f(\vec{x_0})=H \, (\vec{x_1}-\vec{x_0})=\lambda_1 H \vec{S_0}\!$

Транспонируем полученное выражение и домножаем на $H^{-1}\!$ справа:

$(\nabla f(\vec{x_1})-\nabla f(\vec{x_0}))^T H^{-1}=\lambda_1 \vec{S_0}^T H^T H^{-1}\!$

В силу непрерывности вторых частных производных $H^T=H\!$ . Тогда:

$\vec{S_0}^T=\frac{(\nabla f(\vec{x_1})-\nabla f(\vec{x_0}))^T H^{-1}}{\lambda_1}\!$

Подставим полученное выражение в (3):

$\frac{(\nabla f(\vec{x_1})-\nabla f(\vec{x_0}))^T H^{-1}H\vec{S_1}}{\lambda_1}=0\!$

Тогда, воспользовавшись (1) и (2):

$(\nabla f(\vec{x_1})-\nabla f(\vec{x_0}))^T (-\nabla f(\vec{x_1})-\omega_1\nabla f(\vec{x_0})))=0\qquad (4)\!$

Если $\lambda=\arg\min_\lambda f(\vec{x_0}+\lambda \vec{S_0})\!$ , то градиент в точке $\vec{x_1}=\vec{x_0}+\lambda \vec{S_0}\!$ перпендикулярен градиенту в точке $\vec{x_0}\!$ , тогда по правилам скалярного произведения векторов:

$(\nabla f(\vec{x_0}),\nabla f(\vec{x_1}))=0\!$

Приняв во внимание последнее, получим из выражения (4) окончательную формулу для вычисления $\omega\!$ :

$\omega_1=\frac{||\nabla f(\vec{x_1})||^2}{||\nabla f(\vec{x_0})||^2}\!$

[править] К-я итерация

На k-й итерации имеем набор $\vec{S_0},\ldots,\vec{S_{k-1}}\!$ .

Тогда следующее направление вычисляется по формуле:

$\vec{S_k}=-\nabla f(\vec{x_0})+\omega_1 \vec{S_0}+\ldots+\omega_k \vec{S}_{k-1},\quad \omega_i=\frac{||\nabla f(\vec{x_i})||^2}{||\nabla f(\vec{x}_{i-1})||^2},\!$

где $\omega_k\!$ непосредственно рассчитывается на k-й итерации, а все остальные уже были рассчитаны на предыдущих.

Это выражение может быть переписано в более удобном итеративном виде:

$\vec{S_k}=-\nabla f(\vec{x_k})+\omega_k \vec{S}_{k-1}\!$

Алгоритм

· Пусть $\vec{x}_0\!$ — начальная точка, $\vec{r}_0\!$ — направление антиградиента и мы пытаемся найти минимум функции $f(\vec{x})\!$ . Положим $\vec{S}_0=\vec{r}_0\!$ и найдем минимум вдоль направления $\vec{S}_0\!$ . Обозначим точку минимума $\vec{x}_1\!$ .

· Пусть на некотором шаге мы находимся в точке $\vec{x}_k\!$ , и $\vec{r}_k\!$ — направление антиградиента. Положим $\vec{S}_k=\vec{r}_{k}+\omega_k \vec{S}_{k-1}\!$ , где $\omega_k\!$ выбирают либо $\frac{(\vec{r}_k,\vec{r}_k)}{(\vec{r}_{k-1},\vec{r}_{k-1})}\!$ (стандартный алгоритм — Флетчера-Ривса, для квадратичных функций с $H>0\!$ ), либо $\max(0,\frac{(\vec{r}_k,\vec{r}_k-\vec{r}_{k-1})}{(\vec{r}_{k-1},\vec{r}_{k-1})})\!$ (алгоритм Полака–Райбера). После чего найдем минимум в направлении $\vec{S_k}\!$ и обозначим точку минимума $\vec{x}_{k+1}\!$ . Если в вычисленном направлении функция не уменьшается, то нужно забыть предыдущее направление, положив $\omega_k=0\!$ и повторив шаг.

Формализация

1.                 Задаются начальным приближением и погрешностью: $\vec{x}_0,\quad \varepsilon, \quad k=0\!$

2.                 Рассчитывают начальное направление: $j=0,\quad \vec{S}_k^j=-\nabla f(\vec{x}_k),\quad \vec{x}_k^j=\vec{x}_k\!$

3.

o Если $||\vec{S}_k^{j+1}||<\varepsilon\!$ или $||\vec{x}_k^{j+1}-\vec{x}_k^j||<\varepsilon\!$ , то $\vec{x}=\vec{x}_k^{j+1}\!$ и останов.

o Иначе если $(j+1)<n\!$ , то $j=j+1\!$ и переход к 3; иначе $\vec{x}_{k+1}=\vec{x}_k^{j+1},\quad k=k+1\!$ и переход к 2.

1.5 Метод Ньютона

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

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

Обоснование

Чтобы численно решить уравнение $f(x)=0\!$ методом простой итерации, его необходимо привести к следующей форме: $x=\varphi(x)\!$ , где $\varphi\!$ — сжимающее отображение.

Для наилучшей сходимости метода в точке очередного приближения $x^*\!$ должно выполняться условие $\varphi'(x^*)=0\!$ . Решение данного уравнения ищут в виде $\varphi(x)=x+\alpha(x)f(x)\!$ , тогда:

$\varphi'(x^*)=1+\alpha'(x^*)f(x^*)+\alpha(x^*) f'(x^*)=0.\!$

В предположении, что точка приближения «достаточно близка» к корню $\tilde{x}\!$ , и что заданная функция непрерывна $(f(x^*)\approx f(\tilde{x})=0)\!$ , окончательная формула для $\alpha(x)\!$ такова:

$\alpha(x)=-\frac{1}{f'(x)}.\!$

С учётом этого функция $\varphi(x)\!$ определяется выражением:

$\varphi(x)=x-\frac{f(x)}{f'(x)}.\!$

Эта функция в окрестности корня осуществляет сжимающее отображение^[1], и алгоритм нахождения численного решения уравнения $f(x)=0\!$ сводится к итерационной процедуре вычисления:

$x_{n+1}=x_{n}-\frac{f(x_n)}{f'(x_n)}.\!$

По теореме Банаха последовательность приближений стремится к корню уравнения $f(x)=0\!$ .

Рисунок 1 - Иллюстрация метода Ньютона (синим изображена функция $\scriptstyle{f(x)}$ , нуль которой необходимо найти, красным — касательная в точке очередного приближения $\scriptstyle{x_n}$ ). Здесь мы можем увидеть, что последующее приближение $\scriptstyle{x_{n+1}}$ лучше предыдущего $\scriptstyle{x_n}$ .

Геометрическая интерпретация

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

Пусть $f(x)\colon[a,\;b]\to\R\!$ — определённая на отрезке $[a,\;b]$ и дифференцируемая на нём вещественнозначная функция. Тогда формула итеративного исчисления приближений может быть выведена следующим образом:

$f'(x_n)=\mathrm{tg}\,\alpha=\frac{\Delta y}{\Delta x}=\frac{f( x_n)-0}{x_n-x_{n+1}}=\frac{0-f(x_n)}{x_{n+1}-x_n},\,\!$

где α — угол наклона касательной в точке $x_n\!$ .

Следовательно искомое выражение для $x_{n+1}\!$ имеет вид:

$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}.\,\!$

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

Алгоритм

1. Задается начальное приближение x₀.

2. Пока не выполнено условие остановки, в качестве которого можно взять $|x_{n+1}-x_n|<\varepsilon\!$ или $|f(x_{n+1})|<\varepsilon\!$ (то есть погрешность в нужных пределах), вычисляют новое приближение: $x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}\!$ .

2. Решение задачи в Mathcad 14

2.1 Первый способ - Сопряженный градиент

Начальное приближение

Функция Minimize ищет минимум Функции методом сопряженного градиента

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

Х=4.585, У=5.654 дают минимум затрат R=23890

2.2 Второй способ - Квази-Ньютон

При разных дополнительных параметрах. Результат одинаков

Дает такой же ответ

Заключение

Были рассмотрены градиентные методы нахождения экстремумов функции :

1.     Метод Ньютона,

2.     Сопряженных градиентов,

3.     Покоординатного спуска (Гаусса—Зейделя),

4.     Скорейшего спуска( метод градиента)

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

Х=4.585, У=5.654 дают минимум затрат R=23890

Список использованной литературы

1.                 Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. — М.: Высш. шк., 1986.

2.                 Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.

3.                 Коршунов Ю.М., Коршунов Ю.М. Математические основы кибернетики. — М.: Энергоатомиздат, 1972.

4.                 Максимов Ю.А.,Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.

5.                 Максимов Ю.А. Алгоритмы линейного и дискретного программирования. — М.: МИФИ, 1980.

6.                 Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576.

7.                 http://ru.wikipedia.org

Bukvasha