close

Вход

Забыли?

вход по аккаунту

?

Учет ограничений равенств при решении оптимизационных задач с линейными ограничениями.

код для вставкиСкачать
Известия Томского политехнического университета. 2008. Т. 312. № 5
УДК 519.853
УЧЕТ ОГРАНИЧЕНИЙ РАВЕНСТВ ПРИ РЕШЕНИИ ОПТИМИЗАЦИОННЫХ ЗАДАЧ
С ЛИНЕЙНЫМИ ОГРАНИЧЕНИЯМИ
О.Н. Вылегжанин, Г.И. Шкатова
Томский политехнический университет
Email: onv@am.tpu.ru
Предложен алгоритм, позволяющий сократить размерность пространства искомого вектора неизвестных при решении оптими
зационных задач с ограничениямиравенствами. Алгоритм основан на модифицированной процедуре рекуррентного псевдооб
ращения. Получены выражения для преобразования целевой функции в случаях, когда она является линейной или квадратич
ной формой. Приведен числовой пример применения алгоритма для задачи линейного программирования.
При решении многих задач оптимизации с
ограничениями ограничения являются линейными
равенствами или неравенствами. Учет ограниче
ний определяет метод решения задачи, ее «трудо
емкость». Учет ограничений равенств приводит к
сокращению размерности пространства. В литера
туре предложены различные процедуры учета огра
ниченийравенств [1, 2]. В данной работе обсужда
ется алгоритм учета ограниченийравенств, осно
ванный на процедуре рекуррентного псевдообра
щения.
Постановка задачи оптимизации при наличии
ограниченийравенств может быть сформулирова
на следующим образом:
f ( x ) =< c, x > → extr ,
(1)
A ⋅ x = b, x ∈ R n , b ∈ R m , rkA = k .
(2)
Будем полагать, что первые k столбцов A – ли
нейно независимы. Тогда одним из подходов к ре
шению является отыскание такого оператора P,
при умножении на который матрица P.A имеет вид:
P ⋅ A = D ⋅ A′ ,
где D – диагональная матрица размером k×k, а A' –
некоторая матрица размером k×(n–k).
Цель этого преобразования – выразить первые
k неизвестных как линейные функции от осталь
ных.
Введем следующие обозначения: x – вектор
первых k элементов, –
x – вектор остальных элемен
тов x; A – матрица,
образованная первыми k
–
столбцами из A, A – матрица, образованная осталь
ными (n–k) столбцами. Тогда получить требуемое
преобразование можно на основе следующего
утверждения.
Утверждение 1. Если A – матрица ограничений
равенств, rk A=k и первые k столбцов матрицы A
линейно независимы, то систему ограничений (2)
можно записать в виде:
+
x = A (b − A × x ),
(3)
где A матрица, псевдообратная к матрице A.
Доказательство 1.
С учетом введенных обозначений систему
– огра
ничений можно представить в виде: A . x+A .–
x =b.
+
76
Умножим
обе части на A +.– Получим:
–
x =A +.b или I. x=A +.b–A +.A .–
x , где I –
A +.A . x+A +.A .–
единичная матрица.
Что и требовалось получить.
Таким образом, задача (1, 2) сводится к выбору
такой матрицы перестановки T, чтобы первые k
столбцов T.A образовывали базисный набор.
В работе [3] авторами была предложена проце
дура выбора базисных столбцов, которая сводится
к выполнению следующих шагов:
1. Выбирается столбец с наибольшей самокова
риацией, удовлетворяющий условию
ar=max<aiT,ai>.
i∈I
2. Вычисляется первая строка псевдообратной ма
трицы: A1+=a1+=arT.<arT.ar>–1.
3. Вычисляется оператор – проектор на простран
ство, перпендикулярное пространству, задавае
мому матрицей A: R1=I–A1.A1+.
4. Далее рекуррентно для jго шага, где j=2,...,n:
4.1. Выбирается столбец матрицы А, имеющий
максимальную проекцию на простран
ство, перпендикулярное к уже отобран
ным столбцам. Номер этого столбца удо
влетворяет условию:
λ=arg max(alT.Rj.al), l=j,...,n.
i∈I
4.2. Этот столбец ставится на место (j+1)го
столбца.
4.3. Вычисляется новая матрица
⎛ A+ ⋅ ( I − a j +1 ⋅ a +j + 1 ) ⎞
A+j +1 = ⎜ j
⎟⎟ ,
⎜
a +j +1
⎝
⎠
+
где a j+1 – строка псевдообратной матрицы, получа
емая из соотношения: a+j+1=(Rj.aj+1)T/(a+j+1.Rj.aj+1).
T. .
4.4. Процесс заканчивается, когда max(a
l Rj al)≤ε,
l∈L
L=j,...,n, где ε – заданный порог.
Эта процедура сводится к обычной процедуре
рекуррентного псевдообращения с той разницей,
что на каждом шаге рекурсии выбирается столбец,
имеющий максимальную норму компоненты, пер
пендикулярной к уже отобранным столбцам.
При такой организации вычислений сразу обес
печивается как выбор столбцов A, образующих ба
1
1
Управление, вычислительная техника и информатика
зис, так и вычисление матрицы, псевдообратной к
матрице, образованной этими столбцами.
Если оптимизируемой функцией f(x) является
линейная или квадратичная формы, то легко найти
их преобразование с учетом (3).
Утверждение 2. Если f(x)=<c,x> – линейная
форма, то при наличии ограниченийравенств вида
(2), учитывая введенные выше обозначения, она
преобразуется к форме:
+
T
T
T
cT ⋅ x = c ⋅ x + c T ⋅ x .
+
c ⋅ A (b − A ⋅ x ) + c T ⋅ x =
+
+
T
= c ⋅ A b − c ⋅ A A⋅ x + c T ⋅ x,
откуда, вынося в правой части за скобки общий
множитель –
x , получим доказываемое.
Утверждение 3. Если f(x)=xT.B.x – квадратич
ная форма, то при наличии ограниченийравенств
вида (2) она преобразуется к форме:
T
x T Bx = x (W T B0W0 − BW + W T B + B ) x +
T
+ b T ( B + B − ( B0 + B0T )W ) x + bT B0 b ,
+
+
где W = A A, b = A b, B =
B0
B
⎛ x ⎞ B0
x T Bx = ⎜ ⎟
⎜ x⎟ B
⎝ ⎠
T
1
0
−1
−1,5
1
−1
−1
0,1
−2
0,501
9,994
0,35
−3,575
−0,5 0,1
0,5
−7, 481
5, 425
4,5
4,5
B
B
,
B ⎛ x⎞
⎜ ⎟=
B ⎜⎝ x ⎟⎠
−3 −10,1 −16,551 −30, 05
−3
0
−2,398
−5
4,5
0
,
2, 225
11, 037
6,537
b=
110, 225
−12
−1
2
0,5
−1, 2
−0,35
2, 4
−1
−3,5
4
−5, 2
−1,125
0, 2
−1
1
−3
4, 687
−1, 25
−2, 625
.
Решение:
1. Выбираем столбцы из матрицы А, образую
щие базисный набор. В результате применения
описанной выше процедуры получаем набор
столбцов: 2, 4, 5. Ранг матрицы равен трем
(a1T.R3.a1)≤1.10–5. Матрица, псевдообратная к выде
ленным столбцам, имеет вид:
⎛ −0, 497549 0, 252451
⎜
A+ = ⎜ 0, 253676 −0, 621324
⎜ 0,502451 −0, 747549
⎝
−0, 250000
−0,375000
0, 750000
−0, 024510 ⎞
⎟
−0, 036765 ⎟.
−0, 024510 ⎟⎠
Умножив ее слева на ограниченияравенства
имеем:
−0,50000 ⎞
⎟
−0, 75000 ⎟,
0,50000 ⎟⎠
A+ ⋅ b = (−0, 7500 −2,1250 2, 7500) T .
2. Минимизируемая форма преобразуется к виду:
y = A+ ⋅ f ( x ) =
= A+ ⋅ ( x1 − 2 ⋅ x2 + x3 − 3, 424 ⋅ x4 + 0,5 ⋅ x5 − 6, 25) =
= −3 ⋅ x1 − x3 ,
¯
¯
а ограничениянеравенства примут вид A'.x≤ b', где:
T
−0,998
8
−7
Подставляя соотношение (3) и учитывая вве
денные в утверждении 3 обозначения, получим:
x T Bx = (b − Wx )T B0 (b − Wx ) +
+ x B(b − Wx ) + (b − Wx ) Bx + x Bx.
T
0,5
b=
−0, 7 0,5
1
−1
1
0, 26 −0, 45 0, 2 −0,1 −0, 2
= x B0 x + x T B x + x Bx + x T Bx .
T
−0,5
−2
0,1
0, 4
−1
A=
−3
1, 4
⎛ 1, 00000 0, 00000 0, 00000 −0, 07500
⎜
A+ ⋅ A = ⎜ 0, 00000 1, 00000 0, 00000 −0,31250
⎜ 0, 00000 0, 00000 1, 00000 −0,97500
⎝
–
~
а B0, B , B и B – матрицы размерами k×k, k×(n–k),
(n–k)×k и (n–k)×(n–k), соответственно.
Доказательство 3.
Учитывая введенные обозначения, имеем:
T
A=
1, 2
(4)
Подставив (3) в уравнение (4), получим:
T
A⋅ x ≤ b,
где:
+
c T ⋅ x = c ⋅ A ⋅ b + (c T − c ⋅ A ⋅ A ) ⋅ x ,
где c и –
c – компоненты вектора коэффициентов,
соответствующие компонентам x и x)вектора x.
Доказательство 2.
Разлагая компоненты линейной формы на со
ставляющие, имеем:
T
A⋅ x = b è
T
Откуда, раскрыв скобки и перегруппировав по
сле перемножения в правой части слагаемые, полу
чим доказываемое.
Продемонстрируем предложенный метод на
следующем численном примере: найти минимум
–)=x –2.x +x –3,424.x +0,5.x –6,25
функции y=f(x
1
2
3
4
5
при ограничениях:
A' =
−1
−3
5
−26,998 −25
2,998
−5
−0,162
0, 455
2
0, 4
−3
0,5
2
16
4,999
b' =
135
.
15
1
9,5
7
Таким образом, предложенная процедура дает
возможность для системы линейных ограничений
равенств найти преобразование, позволяющее вы
77
Известия Томского политехнического университета. 2008. Т. 312. № 5
разить часть неизвестных через линейные комби
нации остальных неизвестных с учетом возможной
вырожденности системы ограничений. Показано,
как это преобразование может быть применено для
СПИСОК ЛИТЕРАТУРЫ
1. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. –
М.: Мир, 1985. – 509 с.
2. Цыганков А.А. Новые условия экстремума для гладких задач с
ограничениями в форме равенств // Журнал вычислительной
математики и математической физики. – 2001. – Т. 41. – № 10.
– С. 1474–1481.
3. Вылегжанин О.Н., Шкатова Г.И. Сравнительная оценка двух
методов выбора наилучших линейных регрессоров // Приме
линейной и квадратичной форм. Приведенный де
монстрационный пример подтверждает работоспо
собность метода. Применение описанной процеду
ры позволило снизить размерность задачи с 5 до 2.
нение математических методов и ЭВМ в медикобиологиче
ских исследованиях: Межвузовский научнотехнический сбор
ник. – Томск: Издво ТПУ, 1988. – С. 18–22.
Поступила 14.04.2008 г.
Ключевые слова:
Выпуклое программирование, линейные ограничения, учет
ограниченийравенств, рекуррентное псевдообращение.
УДК 681.3.06
О ПОСТРОЕНИИ АКТИВНЫХ МОДЕЛЕЙ РАСПРЕДЕЛЕННЫХ СИСТЕМ РЕАЛЬНОГО ВРЕМЕНИ
В.К. Погребной
Институт «Кибернетический центр» ТПУ
Email: vk@ad.cctpu.edu.ru
Предложен подход к решению проблемы снижения трудоемкости построения имитационной модели и ее трансформации. Вве
дены понятия активной модели системы, виртуальной машины моделирования, модуляимитатора и описателей состояний его
входных и выходных позиций. Дано определение и предложена оригинальная структура модуляимитатора, включающая блок
адаптации, операционный блок и блок описателей состояний позиций. Разработан перечень настроек и выполняемых ими
функций при проектировании блока адаптации. Дано определение описателей состояний позиций модуля, как потенциальных
носителей информации о признаковом пространстве, в котором функционирует активная модель при выполнении ее на вирту
альной машине. Предложена функциональная структура активной модели и сформулированы этапы ее построения.
Введение
Рассмотрению подлежат технические системы с
территориально распределенным оборудованием.
Функционирование такой системы осуществляет
ся под управлением распределенной вычислитель
ной системы, которая является неотъемлемой ча
стью технической системы в целом. Управление
технологическим оборудованием системы выпол
няется в реальном масштабе времени и должно со
ответствовать заданному регламенту ее функцио
нирования. Современные вычислительные систе
мы для управления такими объектами создаются
как распределенные и относятся к классу жестких
систем реального времени (СРВ). Распределенная
СРВ является сложным для проектирования
объектом. Поэтому широкое использование мето
дов моделирования при создании такой системы
становится непременным условием успешного вы
полнения проекта.
Известно, что имитационное моделирование
является всеобъемлющим и универсальным мето
дом анализа систем [1, 2]. Широкое применение
получили также частные модели для анализа от
дельных характеристик систем – такие как сети
массового обслуживания для оценки производи
78
тельности, марковские цепи для оценки надежно
сти, сети Петри для анализа корректности функци
онирования параллельных взаимодействующих
процессов, нейронные сети для принятия реше
ний. В отличии от имитационных, применение
частных моделей оправдано лишь в условиях, когда
отдельные характеристики в ходе проектирования
выдвигаются на уровень критериев.
Основным барьером на пути применения ими
тационного моделирования являются большие зат
раты на разработку программ, имитирующих
функционирование системы. Эта проблема осо
бенно ярко проявляется в отношении СРВ, в кото
рых прикладное программное обеспечение по зат
ратам на разработку составляет 70...80 %. Получа
ется, что затраты на программирование модели
рующих алгоритмов сопоставимы с разработкой
программного обеспечения. Положение усугубля
ется тем, что при проектировании приходится ис
пользовать эволюционный подход, когда исходная
модель при поиске приемлемого варианта СРВ
многократно трансформируется. Необходимость
многократного перепрограммирования модели
практически исключает возможность применения
имитационного моделирования. Поэтому разра
Документ
Категория
Без категории
Просмотров
7
Размер файла
428 Кб
Теги
оптимизационными, решение, учет, ограничений, задачи, равенства, линейными, ограничениями
1/--страниц
Пожаловаться на содержимое документа