Санкт-Петербургский Государственный Технологический Институт
(Технический Университет
)
Кафедра математического моделирования и оптимизации химико-технологических процессов
Факультет
Курс
Дисциплина: Системный анализ химической технологии
КУРСОВАЯ РАБОТА
Вариант № 4
Тема: Выбор оптимального места строительства очистного сооружения
Студент:
Преподаватель:
Оценка за курсовую работу:
Санкт-Петербург
2011
Введение
В последнее время особое внимание в промышленности стало обращаться на инженерный анализ и оптимизацию производственных процессов. Однако из-за высокой интеграции химико-технологических процессов их анализ и оптимизация весьма сложны и неизменно требуют применения вычислительной техники. Отсутствие соответствующего программного обеспечения, наряду с ограничением стоимости работ и времени, необходимых для выполнения работ, может привести к анализу и оптимизации только части существующей технологии или рассмотрению меньшего количества вариантов технических решений. Кроме того, для более полной проработки режимов работы технологии и управления в масштабах завода в некоторых случаях возникает необходимость моделирования химико-технологических систем в динамических условиях.
Ранее, процесс моделирования технологических процессов и систем требовал применения языков программирования и поэтому использовался исключительно специалистами, свободно разбирающимися в химической технологии, моделировании и программировании. Бурное развитие мощных персональных компьютеров позволило создать специализированные программные оболочки, автоматизирующие сложные вычисления и наглядно отображающие результаты расчета.
При проектировании ХТС решаются следующие задачи:
Среди математических задач, связанных с разработкой и совершенствованием ХТС выделяют следующие: задача синтеза, анализа и оптимизации.
Задача синтеза ХТС: Заданы элементы, из которых может быть построена система, а так же заданы сырье и целевые продукты. Требуется разработать структуру ХТС для реализации технологического процесса, т.е. необходимо выбрать элементы из числа имеющихся, установить связи между ними, определить конструктивные и технологические параметры элементов ХТС.
Задача анализа ХТС:
Целью анализа структуры ХТС является выявление ее структурных особенностей и нахождение последовательности расчета элементов.
Целью анализа качества функционирования является получение количественных оценок ее основных свойств: чувствительности, надежности и т.д.
Задача оптимизации ХТС является комплексной и включает в себя как оптимизацию структуры, так и оптимизацию режимов функционирования элементов. Целью оптимизации является обеспечение наиболее высоких технико-экономических показателей ХТС.
Задание
Выбор оптимального места строительства очистного сооружения.Сточные воды трех химических комбинатов, расположенных и точках В1
В2, В3,должны подаваться для обработки на очистное сооружение.
Выбрать оптимальное место строительства этою сооружения, если целевая функция, представляющая затраты на строительство, имеет вид
R=A1
W1
L1
+A2
W2
L2
+A3
W3
L3
где Li
– длина соответствующего участка трубопровода, км,
определяется по формуле
Ai
– коэффициент, учитывающий сложность строительства участка трубопровода, руб.*ч/км*м3
;
Wi
–объемный расход, м3
/ч;
Xi
, Уi
– координаты химического комбината, км;
X, У – координаты очистного сооружения, км;
Условие окончания счета
Решение задачи провести с помощью градиентных методов. Выполнить сравнительный анализ эффективности методов.
Вариант задания ниже.
1 Теория : Постановка задачи решения системы уравнений в терминах методов оптимизации
Задача решения системы уравнений:
(1)
с nэквивалентна задаче минимизации функции
(2)
или какой-либо другой возрастающей функции от абсолютных величин | fi
|невязок (ошибок) , . Задача отыскания минимума (или максимума) функции n переменных и сама по себе имеет большое практическое значение.
Для решения этой задачи итерационными методами начинают с произвольных значений и строят последовательные приближения:
или покоординатно:
(3)
которые сходятся к некоторому решению при .
Различные методы отличаются выбором «направления» для очередного шага, то есть выбором отношений
.
Величина шага (расстояние, на которое надо передвинуться в заданном направлении в поисках экстремума) определяется значением параметра λ[j]
, минимизирующим величину как функцию от λ[j]
. Эту функцию обычно аппроксимируют её тейлоровским разложением или интерполяционным многочленом по трем-пяти выбранным значениям λ[j]
. Последний метод применим для отыскания max и min таблично заданной функции F(x1
,x2
,...,xn
).
1.1 Градиентные методы
Основная идея методов заключается в том, чтобы идти в направлении наискорейшего спуска, а это направление задаётся антиградиентом :
где λ[j]
выбирается
· постоянной, в этом случае метод может расходиться;
· дробным шагом, то есть длина шага в процессе спуска делится на некое число;
· наискорейшим спуском:
1.2 Метод наискорейшего спуска (метод градиента)
Выбирают , где все производные вычисляются при , и уменьшают длину шага λ[j]
по мере приближения к минимуму функции F.
Для аналитических функций F и малых значений fi
тейлоровское разложениеF(λ[j]
) позволяет выбрать оптимальную величину шага
(5)
где все производные вычисляются при . Параболическая интерполяция функции F(λ[j]
) может оказаться более удобной.
Алгоритм
1. Задаются начальное приближение и точность расчёта
2. Рассчитывают , где
3. Проверяют условие останова:
o Если , то j = j + 1 и переход к шагу 2.
o Иначе и останов.
1.3 Метод покоординатного спуска (Гаусса—Зейделя)
Улучшает предыдущий метод за счёт того, что на очередной итерации спуск осуществляется постепенно вдоль каждой из координат, однако теперь необходимо вычислять новые раз за один шаг.
Алгоритм
1. Задаются начальное приближение и точность расчёта
2. Рассчитывают , где
3. Проверяют условие останова:
o Если , то и переход к шагу 2.
o Иначе и останов.
1.4 Метод сопряжённых градиентов
Метод сопряженных градиентов — метод нахождения локального минимума функции на основе информации о её значениях и её градиенте. В случае квадратичной функции в минимум находится за n
шагов.
Определим терминологию:
Пусть .
Введём на целевую функцию.
Вектораназываются сопряжёнными
, если:
·
·
где — матрица Гессе.
| Теорема (о существовании). Существует хотя бы одна система сопряжённых направлений для матрицы , т.к. сама матрица (её собственные вектора) представляет собой такую систему. |
1.4.1 Обоснование метода
Нулевая итерация
:center;">
Рисунок 2 - Иллюстрация последовательных приближений метода наискорейшего спуска (зелёная ломаная) и метода сопряжённых градиентов (красная ломаная) к точке экстремума.
Пусть
Тогда .
Определим направление так, чтобы оно было сопряжено с :
Разложим в окрестности и подставим :
Транспонируем полученное выражение и домножаем на справа:
В силу непрерывности вторых частных производных. Тогда:
Подставим полученное выражение в (3):
Тогда, воспользовавшись (1) и (2):
Если , то градиент в точке перпендикулярен градиенту в точке , тогда по правилам скалярного произведения векторов:
Приняв во внимание последнее, получим из выражения (4) окончательную формулу для вычисления :
[править]К-я итерация
На k-й итерации имеем набор.
Тогда следующее направление вычисляется по формуле:
где непосредственно рассчитывается на k-й итерации, а все остальные уже были рассчитаны на предыдущих.
Это выражение может быть переписано в более удобном итеративном виде:
Алгоритм
· Пусть — начальная точка, — направление антиградиента и мы пытаемся найти минимум функции . Положим и найдем минимум вдоль направления . Обозначим точку минимума .
· Пусть на некотором шаге мы находимся в точке , и — направление антиградиента. Положим , где выбирают либо (стандартный алгоритм — Флетчера-Ривса, для квадратичных функций с ), либо (алгоритм Полака–Райбера). После чего найдем минимум в направлении и обозначим точку минимума . Если в вычисленном направлении функция не уменьшается, то нужно забыть предыдущее направление, положив и повторив шаг.
Формализация
1. Задаются начальным приближением и погрешностью:
2. Рассчитывают начальное направление:
3.
o Если или , то и останов.
o Иначе если , то и переход к 3; иначе и переход к 2.
1.5 Метод Ньютона
Метод Ньютона является градиентным методом поиска минимума функции нескольких переменных, использующим информацию о первых и вторых производных функции. На основе квадратичной аппроксимации функции формируется последовательность итераций таким образом, чтобы во вновь получаемой точке градиент аппроксимирующей функции обращался в нуль.
Метод Ньютона определяет направление эффективного поиска в окрестности точки минимума, но не обладает свойством убывания функции от итерации к итерации. Однако в случае положительной определенности матрицы Гессе направление по методу Ньютона оказывается направлением спуска.
Обоснование
Чтобы численно решить уравнение методом простой итерации, его необходимо привести к следующей форме: , где — сжимающее отображение.
Для наилучшей сходимости метода в точке очередного приближения должно выполняться условие . Решение данного уравнения ищут в виде , тогда:
В предположении, что точка приближения «достаточно близка» к корню , и что заданная функция непрерывна, окончательная формула для такова:
С учётом этого функцияопределяется выражением:
Эта функция в окрестности корня осуществляет сжимающее отображение[1]
, и алгоритм нахождения численного решения уравнения сводится к итерационной процедуре вычисления:
По теореме Банаха последовательность приближений стремится к корню уравнения .
Рисунок 1 - Иллюстрация метода Ньютона (синим изображена функция , нуль которой необходимо найти, красным — касательная в точке очередного приближения ). Здесь мы можем увидеть, что последующее приближение лучше предыдущего .
Геометрическая интерпретация
Основная идея метода заключается в следующем: задаётся начальное приближение вблизи предположительного корня, после чего строится касательная к исследуемой функции в точке приближения, для которой находится пересечение с осью абсцисс. Эта точка и берётся в качестве следующего приближения. И так далее, пока не будет достигнута необходимая точность.
Пусть — определённая на отрезке и дифференцируемая на нём вещественнозначная функция. Тогда формула итеративного исчисления приближений может быть выведена следующим образом:
где α — угол наклона касательной в точке .
Следовательно искомое выражение для имеет вид:
Итерационный процесс начинается с некоего начального приближения x
0
(чем ближе к нулю, тем лучше, но если предположения о нахождении решения отсутствуют, методом проб и ошибок можно сузить область возможных значений, применив теорему о промежуточных значениях).
Алгоритм
1. Задается начальное приближение x
0
.
2. Пока не выполнено условие остановки, в качестве которого можно взять или (то есть погрешность в нужных пределах), вычисляют новое приближение: .
2. Решение задачи в Mathcad 14
2.1 Первый способ - Сопряженный градиент
| Начальное приближение |
| Функция Minimize ищет минимум Функции методом сопряженного градиента |
Таким образом координаты оптимального места строительства очистного сооружения
Х=4.585, У=5.654 дают минимум затрат R=23890
2.2 Второй способ - Квази-Ньютон
При разных дополнительных параметрах. Результат одинаков
Дает такой же ответ
Таким образом координаты оптимального места строительства очистного сооружения
Х=4.585, У=5.654 дают минимум затрат R=23890
Заключение
Были рассмотрены градиентные методы нахождения экстремумов функции :
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