Файл: Кафаров, В. В. Принципы математического моделирования химико-технологических систем (введение в системотехнику химических производств) учеб. пособие.pdf

следующую основную задачу, не принимая во внимание (что проще

вобозначениях), можно или нельзя разбить ее на подзадачи.

Ос н о в н а я з а д а ч а . Максимизировать / (х) при условии

где X — /i-мерный вектор; / (х) — скалярная функция цели; G (х) — тга-компо- нентная векторная функция х (т <; тг); S — любое компактное подмножество евклидова тг-мерного пространства.

причем к" означает транспонированный вектор.

Задача Лагранжа формулируется следующим образом: максими­ зировать L (X, к) при фиксированном к (х £ S ).

При соответствующем выборе множества S лагранжева задача имеет конечное решение для всех к в евклидовом тг-мерном прост­ ранстве. Поэтому с данного момента полагаем, что S было выбрано определенным образом. Знание х, которое максимизирует L (х , А,) для любого данного к, обозначим через х* (к) или, если это не при­

Для дальнейшего изложения необходимо ввести дополнительное понятие «опорная плоскость для множества». Гиперплоскость ff, данная уравнением к'х = а, является опорной гиперплоскостью для множества R, если оно полностью содержится в одной из половин пространства, образованного Н, и граница R имеет по крайней мере одну общую точку с //.

317

На рис. ѴІ-9 гиперплоскость Н является опорной плоскостью для множества R в точке / (х*). Множество не имеет опорной плоскости в точке Р.

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

Теорема 1. Решение основной задачи х* также решает лагранжеву задачу, если (и только если) множество R имеет опорную плоскость в точке

![/(**). gl (ж*)і &>!(**).......... ftn(**)]

Следствие 1. Решение задачи Лагранжа для соответствующего Я также решает основную задачу, если опорная плоскость в х* соприкасается с мно­ жеством R только в точке

[/ (**). gl (X*), . ■., gm (**)]

Д о к а з а т е л ь с т в о т е о р е м ы 1

1. Если R имеет опорную плоскость в х*, то, согласно определению опорной плоскости

2. Если X * максимизирует функцию Лагранжа и решает основную задачу,

то в соответствии со следующими рассуждениями множество R имеет опорную плоскость, уравнение которой

/(*)-/(**) = W (*)

Д о к а з а т е л ь с т в о с л е д с т в и я 1

Доказано уже, что х* максимизирует L (х, Я0). Если дополнительно потребо­ вать, чтобы X * было единственным, то следствие вытекает немедленно. Несколько

более общим способом высказывания того же самого является требование, чтобы опорная плоскость в точке [/ (х*), G (х*)] касалась множества R только в [/ (х*),

318

G (а:*)]. Это все еще допускает кратные значения для х*, но тогда максимум L (X, Я0) должен быть

/ (х*), а G (х*) = 0

Многоуровневый алгоритм требует, чтобы функция Лагранжа была макси­ мизирована для последовательности множителей Я, поскольку оптимальный множитель Я0 пе известен априори.

Для того чтобы выяснить, что произойдет, если Я Ф Я0, рассмотрим следу­ ющую теорему.

Теорема 2. Если х* максимизирует функцию Лагранжа L (х, Ях) для некото­ рого вектора множителей Ях, то это решает следующую задачу:

Правая часть уравнения (VI,57) является функцией Лагранжа для задачи (VI,55). Кроме того, х = х* решает уравнение (VI,55).

Теорема 2 говорит, что посредством максимизации функции Лагранжа решается задача, которая подобна первоначальной основной задаче, причем разница заключается в том, что G (хJ) ф 0. Однако более важно то, что эта теорема приводит к формулируемому ниже следствию.

Следствие 2а■ Максимум функции Лагранжа L (х*(Я), Я) дает верхнюю гра­ ницу целевой функции основной задачи.

Доказательство: уравнение (VI,56) справедливо для любого Яі и любого х. Если заменить Ях на Я и взять х = х*, то уравнение (VI,56) принимает вид

так как G (х*) = 0.

Если в X* имеется опорная плоскость, то в соответствии с теоремой 1

Следствие 26. Множитель Я0 минимизирует функцию Лагранжа. Согласно уравнениям (VI,58) и (VI,59)

L ( X * (Я), Я) Sä L ( X * (Яо), Яо)

Рис. ѴІ-10 иллюстрирует положение для Яі ф Я0. Опорная плоскость касается границы множества R в (/ (х* (Я!)), G (х* (Ях)). Отрезок плоскости с осью G (х) = 0 дает значение двойственной функции

у(Ях), [у(Ях) = L(** (Яі), Яі)]

Теперь посмотрим, что произойдет, если множество R не имеет опорной плоскости в X = X* (рис. ѴІ-11). Многоуровневый алгоритм требует, чтобы были выполнены следующие операции:

Начало в первой точке (Я = Я!) дает у (Я!) как максимум функции) Ла­ гранжа L (х, Ях) для всех х. Уменьшение Я доЯ2 дает следующее значение у (Я2) и т . д., пока при Я = Я. двойственная функция не станет минимумом. Любое дальнейшее уменьшение Я, скажем до Я4, приводит, как показано, к возрастанию двойственной функции. Минимум этой функции в данном случае, однако, не

319

отвечает решению основной задачи, поскольку g (х) Ф 0. Скорее при (Я3) имеем решение двух других основных задач:

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

будет равно нулю.

'Множество R, приведенное на рис. ѴІ-11, можно преобразовать посред­ ством преобразования ограничений множества S. Путем сокращения S соответ­ ствующим образом правая граница его может быть сдвинута до положения,

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

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

а) Если множество R имеет плавно вращающуюся опорную плоскость, то градиент ду (Я)/<Э Я существует и его находят из выражения

4 ^ = - * < *•< «

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

б) Функция у (Я) не является выпуклой над любым выпуклым подмноже­ ством своей области. Доказательство: выберем такое а, чтобы 0 <; а <; 1. Тогда

у (аЯ1-)-(1 — а) Я2) = m a x [/(х ) + а Яі g (x) + (l —а) Яog (x)] =

Второе равенство следует потому, что L (х, Я) линейно относительно Я. Если область Я является целым пространством, что и сделано посредством вы­ бора ограничений множества S, то у (Я) выпукла для всех Я.

Пример ѴІ-2. Применить метод многоуровневой оптимизации к ХТС ката­ литического крекинг-процесса «термофор». Данная ХТС позволяет получать высококачественный бензин при повышенном выходе дистиллятных фракций нефтяного топлива; количество нефтяных остатков невелико.

Технологическая схема системы представлена на рис. ѴІ-12. Нефть, посту­ пающую в ХТС, предварительно подогревают и смешивают с потоком рецикла

320