Алгоритмы автоматической оптимизации
Статическая и динамическая оптимизация
Оптимизация технологических процессов является основным назначением АСУТП. Уже на стадии проектирования ставится задача обеспечения возможностей оптимизации управляемого техпроцесса в различных направлениях: достижение максимума производительности, минимума себестоимости, требуемого качества продукции, экономии энергии и сырьевых ресурсов и пр. Зависимость между критерием эффективности и параметрами техпроцесса описывается целевой функцией (см. §1.2). Управление техпроцессом должно быть организовано таким образом, чтобы соотношение его параметров соответствовало заданному экстремуму целевой функции или допустимому граничному режиму, близкому к экстремальному. Если оптимальный режим может быть рассчитан заранее и поддерживаться в соответствии с рассчитанными значениями параметров, то такую оптимизацию называют статической, и ее задачи решают методами программного управления. Если же условия функционирования ТО непрерывно меняются и эти изменения трудно оценить заранее, то АСУТП должна вести автоматический поиск оптимального режима. Организацию такого поиска называют динамической оптимизацией.
Реальные техпроцессы зачастую подвергаются возмущениям, имеющим случайный характер и существенно изменяющим характеристики техпроцессов. В результате воздействия различных возмущений режим функционирования технологического оборудования может отклоняться от оптимального несмотря на поддержание управляющих параметров на заданном первоначально уровне. В таком случае возникает задача определения и задания новых значений управляющих параметров, обеспечивающих оптимальный режим в изменившихся условиях. Если эти значения не могут быть по тем или иным причинам определены заранее и заданы программно, то они определяются по ходу техпроцесса по мере отклонения последнего от оптимального режима. В описанных условиях такие отклонения возникают постоянно, так что необходимо вести поиск оптимального режима в течение всего времени техпроцесса. Иными словами, необходимо непрерывно совершать, одну за другой, попытки достижения оптимального режима. Такие попытки носят название шагов оптимизации. Алгоритмы управления, обеспечивающие непрерывный пошаговый поиск оптимального режима, называются алгоритмами автоматической оптимизации.
|
|
|
Методы оптимизации зависят от характера решаемых задач. Если целевая функция линейна и линейны уравнения ограничений, действующих в управляемом техпроцессе, то прибегают к методам линейного программирования. Если целевая функция нелинейна, то применяют преимущественно градиентные методы. Линейное программирование обычно представлено различными модификациями симплексного метода. Чаще всего оно применяется при решении задач экономического характера, являющихся для АСУТП типичными задачами статической оптимизации. Однако возможно применение линейного программирования и для автоматической оптимизации в процессе функционирования ТО, если целевая функция и ограничения техпроцесса являются линейными или могут быть линеаризированы.
|
|
|
Симплексный метод линейного программирования
При поиске оптимального режима симплексным методом целевая функция должна быть представлена в виде
(4.6)
а уравнения ограничений – в виде
(4.7)
xj≥0 (j=1,2,…n). (4.8)
Принято отображать сомножители произведений, входящих в состав FЦ, в виде векторов-строк
с=[с1, с21,…сn] и х=[х1, х2,… хn],
а коэффициенты и свободные члены в системе уравнений (4.7) – в виде векторов – столбцов
aj 
Векторы aj называют векторами условий задачи, а вектор b называют вектором ограничений задачи. Компоненты векторов аjв своей совокупности образуют матрицу.
|
|
|
A=[a1, a2, …an],
которую называют матрицей условий задачи.
В векторной форме выражение (4.6) записывается в виде скалярного произведения векторов с и х, а левая часть системы уравнений (4.7) записывается в виде произведения матрицы А на вектор х. Теперь в очень краткой форме можно записать основную задачу линейного программирования:
найти максимум функции FЦ=сх
при условии Ах≤b, х≥0; (4.9)
или
найти минимум функции FЦ= -сх
при условии -Ах≥-b, х≥0. (4.9')
Чтобы перейти к стандартной процедуре решения основной задачи линейного программирования симплексным методом, необходимо, чтобы среди векторов ajбыло m единичных. Так, в системе уравнений (4.7) векторы а1-аm – единичные, т.е. у каждого из этих векторов имеется только одна компонента aij (i=1,2,…m), не равная нулю, и она равна единице. Если количество единичных векторов aj меньше m, то в соответствующие уравнения ограничений необходимо ввести дополнительные переменные хj, с помощью которых уравнения ограничений (4.9) будут записаны в канонической форме (4.7). В общем виде это производится методом искусственного базиса [9]. Однако в большинстве случаев недостающие переменные хj можно просто прибавить в соответствующие уравнения ограничений, где их до того не хватало (см. пример 4.1.). Это возможно, если ограничения в условиях задачи представлены в виде неравенств.
|
|
|
Процедура симплексного метода основана на следующих положениях.
1. Совокупность точек х в n-мерном евклидовом пространстве Еn, ограниченная условиями (4.9), образует область допустимых решений рассматриваемой задачи. Каждую точку х=(х1,х2,…хn) из указанной области в экономических расчетах принято именовать планом (допустимым). Точка, в которой достигается либо максимум, либо минимум заданной целевой функции, называется оптимальной точкой, или оптимальным планом.
2. В пространстве Еn область допустимых решений образуется в результате пересечения полупространств х≥0 (при n=2 – полуплоскостей) и Ах≤bили -Ах≥-b, заданных условиями (4.9), и существует в виде многогранника решений. Оптимальная точка (оптимальный план) является одной из вершин многогранника решений.
3. Любые m линейно независимых векторов aj(j=1,2,…n, m≤n), удовлетворяющих системе уравнений (4.7), порождают точку х=(b1,b2,…bm,0,…0), являющуюся вершиной многогранника решений. Такую точку принято называть угловой точкой или опорным планом. Оптимальная точка является одной из угловых точек. В этом нетрудно убедиться на примере нахождения максимального значения функции двух переменных (n=2)
(4.10)
при условиях
(4.11)
Каждое из неравенств (4.11) геометрически определяет полуплоскость в соответствии с граничными прямыми
Если система неравенств (4.11) совместна, то получим многоугольник (вырожденный многогранник, так как n=2) решений вроде приведенного на рис.4.2.
Рис. 4.2. Многоугольник решений
Область допустимых решений на рис.4.2 отмечена штриховкой ее границ. На графике рис.4.2 изображены также линии Fц=const, соответствующие уравнению (4.10) при с1>0 и с2>0. Если перемещать линию Fц в направлении вектора с=(с1, с2), то значение Fц будет возрастать и достигнет максимального значения Fцm в угловой точке А. Следовательно, точка А является оптимальной, а ее координаты определяют оптимальный план решения данной задачи.
Процедура симплексного метода заключается в том, что переходят от одной угловой точки (опорного плана) к другой угловой точке (к другому опорному плану) таким образом, что значение целевой функции обязательно увеличивается (при поиске максимума целевой функции) или обязательно уменьшается (при поиске минимума). При этом указываются признаки достижения максимума или, соответственно, минимума целевой функции.
Первые m единичных векторов аj системы уравнений (4.7)составляют базис поиска оптимального плана. Поскольку оптимальная точка является одной из угловых точек, то искать ее следует путем замены одного из векторов базиса на один из векторов аj (j≥m+1), до того не входивших в состав базиса. После ввода в базис вектора аj значение целевой функции можно рассчитать по формуле
(4.12)
где Fцо – предыдущее значение целевой функции;
λ – коэффициент пропорциональности, значение которого определяется в зависимости от того, какой вектор выводится из базиса.
Параметр Δj определяет величину и знак приращения, которое получает целевая функция после ввода в базис нового вектора аj. Если Δj>0, то целевая функция убывает (Fцj <Fцо), а при Δj<0 целевая функция увеличивается. Знак Δj является критерием полезности ввода нового вектора в базис. При поиске максимума имеет смысл вводить в базис только такой вектор, которому соответствует Δj<0, а при поиске минимума поиск оптимального режима (оптимального плана) продолжают лишь тогда, когда находится вектор, ввод которого в базис приводит к Δj>0 и соответственно– к уменьшению Fц. Значение Δj рассчитывается по формуле
(4.13)
где сi-первые 
коэффициентов целевой функции (4.6);
аij – коэффициенты при хj (j=1,2,…n) системы уравнений (4.7).
При j≤m, т.е. для m единичных векторов, входивших перед этим расчетом в состав базиса, согласно (4.13) получим Δj=0.
Рассмотрим более подробно поиск оптимального режима, когда последний соответствует максимуму целевой функции. Сначала перечислим признаки оптимальности режима (опорного плана).
1) Опорный план x*=(x1*,x2*,…xm*,0,0,…0) решения задачи (4.6)–(4.8) является оптимальным, если Δj ≥ 0 для любого j (j=1,2,…n).
2) Если Δk < 0 для некоторого j=k и среди чисел аik нет положительных, то целевая функция (4.6) не ограничена.
3) Если Δk < 0, но среди чисел aik есть положительные ( не все aik ≤ 0), то существует опорный план x΄ такой, что Fц(x΄) > Fц(x).
Далее составляем таблицу 4.1а. В табл. 4.1а первые m строк определяются исходными данными задачи, а показатели (m+1)-й строки вычисляют.
Таблица 4.1а
| i | Базис | сб | b | с1 | с2 | … | cr | … | cm | cm+1 | … | ck | … | cn |
| а1 | а2 | … | ar | … | am | am+1 | … | ak | … | an | ||||
| 1 | а1 | c1 | b1 | 1 | 0 | … | 0 | … | 0 | a1m+1 | … | a1k | … | a1n |
| 2 | a2 | c2 | b2 | 0 | 1 | … | 0 | … | 0 | a2m+1 | … | a2k | … | a2n |
| … | … | … | … | … | … | … | … | … | … | … | … | … | … | … |
| r | ar | cr | br | 0 | 0 | … | 1 | … | 0 | arm+1 | … | ark | … | arn |
| … | … | … | … | … | … | … | … | … | … | … | … | … | … | … |
| m | am | cm | bm | 0 | 0 | … | 0 | … | 1 | amm+1 | … | аmk | … | amn |
m+1 Fц0 0 0 … 0 … 0 Δm+1 … Δk … Δn Исходные данные таблицы 4.1а соответствуют опорному плану х=(b1,b2,…bm,0,…0).
Таблица 4.1б
| i | Базис | сб | b | с1 | с2 | … | cr | … | cm | cm+1 | … | ск | … | cn |
| а1 | а2 | … | ar | … | am | am+1 | … | aк | … | an | ||||
| 1 | а1 | c1 | b′1 | 1 | 0 | … | a′1r | … | 0 | a′1m+1 | … | 0 | … | a′1n |
| 2 | a2 | c2 | b′2 | 0 | 1 | … | a′2r | … | 0 | a′2m+1 | … | 0 | … | a′2n |
| … | … | … | … | … | … | … | … | … | … | … | … | … | … | … |
| r | ак | ск | b′r | 0 | 0 | … | a′r r | … | 0 | a′r m+1 | … | 1 | … | a′r n |
| … | … | … | … | … | … | … | … | … | … | … | … | … | … | … |
| m | am | cm | b′m | 0 | 0 | … | a′m r | … | 1 | a′mm+1 | … | 0 | … | a′m n |
m+1 F′ц0 0 0 … Δ′r … 0 Δ′m+1 … 0 … Δ′n
В (m+1)-й строке таблицы 4.1а в столбце b записывают значение Fц0, рассчитанное по формуле (4.6), а в каждом столбце aj (j=1, 2,…n) записывают значение Δj, рассчитанное по формуле (4.13). Если Δj<0 для некоторых индексов j и для каждого такого j по крайней мере одно из чисел aij положительно, то можно составить новый опорный план, при котором значение целевой функции увеличится. Чтобы перейти к улучшенному опорному плану, нужно ввести в базис вектор ak , у которого Δk<0, и это Δk является наибольшим (по абсолютной величине) отрицательным числом среди всех Δj . Взамен из базиса исключается вектор ar. Номер r соответствует элементу ark вектора ak, а элемент ark находят по минимуму выражения bi/aik для всехaik>0. Если же все aik≤0 (i=1,2,…m), то целевая функция не ограничена сверху. Число ark называется разрешающим элементом. Столбец ak и строку r, на пересечении которых находится разрешающий элемент, называют направляющими (или разрешающими). Улучшенный опорный план находят методом Жордана-Гаусса. При этом положительные компоненты нового опорного плана находят по формулам:
bi (brk/ark)∙aik при i ≠ r,
b′i = (4.14)
brk/ark при i = r,
а коэффициенты разложения векторов aj через векторы нового базиса, соответствующего новому опорному плану, - по формулам:
aij (arj/ark)∙aik при i ≠ r,
a′ij = (4.15)
arj/ark при i = r.
После этого вместо таблицы 4.1а получится таблица 4.1б. Элементы (m+1)-й строки таблицы 4.1б находят по формулам:
F′цо=Fцо- (brk/ark)Δk , (4.16)
Δ′j=Δj- (arj/ark)Δk , (4.17)
либо на основании их определения, см. формулы (4.6) и (4.13). Затем просматривают элементы (m+1)-й строки. Если все Δ′j≥0, то новый опорный план оптимален. Если же имеются Δ′j<0, то поиск оптимального плана продолжается. Заметим, что формулы (4.14)–(4.17) можно интерпретировать для визуального поиска элементов расчёта методом треугольника, когда все расчёты (кроме случая i=r) ведутся по формуле
b = a1 – a2∕1 a3,
где a1 –это либо bi, либо aij ;
a2/1 – либо brk/ark , либо arj/ark ;
a3 – либо aik, либо Δk.
Пример 4.1. Оптимизация прокатки путем линейного программирования симплексным методом.
Определить месячную программу прокатки стали двух марок на сортовом стане, обеспечивающую максимальную прибыль.
Дано:
затраты времени по каждому сортаменту:
t1 = 0,04 ч/т; t2 = 0,08 ч/т;
расход энергии при прокатке:
w1 = 8 кВт∙ч/т; w2 = 3 кВт∙ч/т;
месячный фонд технологического времени tм ≤ 600ч;
месячный лимит электроэнергии на текущий месяц Wм ≤ 100000 кВт∙ч.
Найти: такой вариант месячной программы прокатки, который обеспечит в текущем месяце, когда имеются ограничения по электроэнергии, максимум прибыли при условии, что прибыльность второго сортамента в 1,2 раза выше прибыльности первого сортамента стали:
Fц = x1 + 1,2x2.
В выражении целевой функции Fц прибыльность выражена в относительных единицах (о.е.). За единицу прибыли принята прибыль от 1 т проката первого сортамента.
Выпуск проката ограничивается неравенствами:
0,04x1 + 0.08x2 ≤ 600
8x1 + 3x2 ≤ 100000.
Вводим: х3 –неиспользованное технологическое время;
х4 –неиспользованная в пределах лимита электроэнергия;
Получим систему уравнений ограничений задачи, выраженную в канонической форме:
0,04х1+0,08х2+х3 = 600;
8х1+3х2+х4 = 100000.
Расчёты производим в соответствии с алгоритмом, представленным в таблицах 4.1а и 4.1б. Результаты расчётов сводим в таблицу 4.2.
Таблица 4.2
| i | Базис | сб | b | 1 | 1,2 | 0 | 0 |
| а1 | а2 | а3 | a4 | ||||
| 1 | а3 | 0 | 600 | 0,04 | 0,08 | 1 | 0 |
| 2 | а4 | 0 | 105 | 8 | 3 | 0 | 1 |
| Прибыль | 0 | -1 | -1,2 | 0 | 0 | ||
| 1 | а2 | 1,2 | 7500 | 0,5 | 1 | 12,5 | 0 |
| 2 | а4 | 0 | 77500 | 6,5 | 0 | -37,5 | 1 |
| Прибыль | 9000 | -0,4 | 0 | 15 | 0 | ||
| 1 | а2 | 1,2 | ~1500 | 0 | 1 | 15,5 | -0,08 |
| 2 | а1 | 1 | ~12000 | 1 | 0 | -6 | 0,16 |
| Прибыль | 13800 | 0 | 0 | 12,6 | 0,052 | ||
Возможный максимум прибыли составляет 13800о.е. при выпуске проката марок: х1=12000т; х2=1500т.
Дата добавления: 2018-04-04; просмотров: 507; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!