Естественные и технические науки, № 2, 2011
ЕСТЕСТВЕННЫЕ НАУКИ
Физико-математические науки
Математика
Дифференциальные уравнения, динамические системы
и оптимальное управление
Крицына Н.А., кандидат технических
наук, доцент
Кулябичев Ю.П., доктор технических
наук, профессор
Козин Р.Г., кандидат технических наук,
доцент
(Национальный исследовательский ядерный
университет «МИФИ»)
ОРГАНИЗАЦИЯ ПОЛНОГО ПЕРЕБОРА АРГУМЕНТОВ ПРИ НАХОЖДЕНИИ
ГЛОБАЛЬНОГО ЭКСТРЕМУМА КРИТЕРИЯ ОПТИМИЗАЦИИ
Предложен алгоритм организации процесса полного перебора при решении задач условной оптимизации.
Ключевые
слова: условная оптимизация, полный перебор.
THE ORGANIZATION OF PROCESS OF FULL SEARCH ARGUMEN AT THE FINDING
OF THE GLOBAL EXTREMUM CRETE-RIJA OPTIMIZATION
The algorithm of the organization of process of full search is offered for decision tasks of conditional
optimization.
Keywords: the conditional optimization, full search.
Стремление к оптимизации различных аспектов производственной деятельности является
естественным и закономерным процессом современной жизни. При этом критерии качества
оптимизации, как правило, оказываются неявно выраженными и многоэкстремальными
функциями многих переменных – аргументов оптимизации. Наличие ограничений, накладываемых
на аргументы оптимизации, еще больше усложняют процесс оптимизации.
В общем виде задача условной оптимизации многомерного критерия выглядит следующим
образом:
– найти экстремум критерия (
j ( , 2
1
, x )
m
J x x2 ,L )=
1 ,
при ограничениях f x x ,L ≥ ≤( ) 0,
, xm
(
x x2 ,L )
1 ,
j =1, n .
Причем, как уже отмечалось, и критерий, и функции ограничений часто носят неявный
характер относительно аргументов оптимизации x x ,L .
1 , 2
, x m
В такой ситуации наиболее надежным способом определения глобального экстремума
критерия является полный перебор допустимых значений аргументов.
Как правило, алгоритмы организации процесса полного перебора в задачах условной оптимизации
являются достаточно трудоемкими и используют сложную систему логических
предикатов.
18
, xm
ψ
Стр.1
Естественные и технические науки, № 2, 2011
Однако в том случае, если накладываемые на аргументы оптимизации x x L огра1
, 2
ничения имеют простой вид, типа: xi
min ≤ ≤ xi
xi
max ,
i m1, . , то целесообразно использовать
=
процедуру полного перебора, основанную на формировании некоторого числа в произвольной
системе счисления [1] без использования сложных логических построений.
Представим интервал определения аргумента ,ix в виде:
pi
xi
x k
ik
max − ∑ xik ,
xi
min = Δ Δ = 0,
k=0
xi0
i m1, . ,
=
i
ное число интервалов разбиения области допустимых значений i-того аргумента.
Таким образом, значение аргумента i
представить в виде:
xi ≅ ∑
xi
min + Δx i m ,
k=0
ai
ik ,
=1,
(2)
причем, верхние параметры суммирования ia являются не только целыми неотрицательными
числами но и удовлетворяют условию:
0 ≤ ≤ia p i m=1, .
i ,
метров ia :
Учитывая вышеизложенное, критерий оптимизации будет многомерной функцией пара(
J
a a2 ,L )=
1 ,
при условии, что i
ai
,am
i ,
(
a a2 ,L, ),
1 ,
0 ≤ ≤ p i m
=
am
a – целые неотрицательные числа, удовлетворяющие неравенствам:
1, .
Таким образом, принимая во внимание условия, накладываемые на параметы a , 1, ,mii
=
их, можно трактовать как коэффициенты разложения целого неотрицательного числа B
в числовой ряд по m разрядам с переменным основанием разрядов
pi +1, =1,
p
,
i m,1=
i m.
Итак, сформируем систему счисления, имеющую m разрядов, причем основания разрядов
i + 1
, превышает на единицу число отрезков дискретизации интервала определения
i-того аргумента (1).
Представим целое положительное число B в виде разложения в числовой ряд по m разрядам
в системе счисления с переменным основанием каждого разряда [3]:
B a= ∏ + +1)
=1
m
m
i
−1
( pi
a ∏ + + + 3 (
1
m−1
m
i
,
−
=
2
( pi
где коэффициенты разложения a amm
творяющие условию:
1,
− L a a a 1 - целые неотрицательные числа, удовле1)
L a p2 +1)(p1 + +1)
,
3 ,
2 ,
0 ≤ ≤ia p i m .
i ,
представления будет:
B
max = ∏ + +1)
=1
pm
m
i
−1
( pi
=1,
Как видим, условия (5) и (6) полностью совпадают.
Очевидно, максимальное число max
p ∏ + + +
1
m−1
m
i
−
=
( pi
3(
(6)
B , которое может быть получено с помощью такого
2
1) L p p2 +1)(p1 + +1)
критерия (3) при использовании метода полного перебора.
Решим обратную задачу, а именно:
19
p p1 + + p1
2 (
1) ( ) .
(7)
Именно такое количество расчетов необходимо произвести для выявления экстремума
a p1 + + a 1 ,
2 (
1)
(5)
(3)
(4)
(1)
где Δ , = 0, p i – заданные кванты дискретизации аргумента ix , p – целое положительx
, с точностью до ошибок дискретизации, можно
,
, x m
ϕ
Стр.2
Естественные и технические науки, № 2, 2011
– найдем целочисленные неотрицательные коэффициенты 0 ≤ ≤ p( );
ai
0≤B B≤ max
i
i m, соответ=1,
ствующие
любому неотрицательному целому числу B, удовлетворяющему условию
.
деления числа B на произведение оснований предыдущих разрядов:
.
am =
⎢
⎢
⎢
⎢
⎤
⎣∏ +1)
(
m
i
−1
=1
p
B
B B am
⎡
am−1
=
⎢
⎢
⎢
⎢
⎣∏ +1)
(
m
i
−
=
2
1
p
B
B B aj
⎡
a −j 1
=
m j
⎢
⎢
⎢
⎢
⎣∏ +1)
(
j
i
−
=
2
1
p
B
i
a1 = − paB
2 ( 1
= − ∏ +1)
i
j
−
=
1
1
(pi
⎤
⎥
⎥
⎥
⎥
⎦
Действия (11), (12) повторяются для всех индексов j, удовлетворяющих условию:
≥ ≥ 3 .
Коэффициент младшего разряда находится по формуле:
1 ).
+
aj
(13)
Таким образом, решение задачи (3) при ограничениях (4) методом полного перебора сводится
к последовательному перебору целых чисел от 0 до max
=1, )
B ; расчету коэффициентов
( j m , соответствующих текущему значению B, по формулам (8), (9), (10), (11), (12),
(13); расчету критерия (3) и проверке полученного значения на экстремальность.
Ниже приведен порядок расчетов в соответствии с предложенной методикой решения
задачи (3) при ограничениях (4):
1.
1.1.
Исходные данные:
1, .
xi
xi
,
i m – максимальное и минимальное значения области определе=
ik
,
i , 1,
=
- кванты дискретизации аргумента ix , p – целое положиi
Δx
k =1,
Задание начальных данных и организация предварительных расчетов
min , max
ния i-того аргумента;
p i m
тельное число интервалов разбиения области допустимых значений i-того аргумента.
20
.
(12)
i
=
− ∏ +1) .
=1
m
i
−1
(pi
⎤
⎥
⎥
⎥
⎥
⎦
Повторяя процедуры (9), (10) получим рекуррентную последовательность нахождения
коэффициентов:
(11)
.
(10)
(9)
Разделим на произведение оснований оставшихся разрядов, полученный остаток от деления,
и выделим целую часть:
i
⎥
⎥
⎥
⎥
⎦
Для определения коэффициента следующего разряда a выделим остаток от предыдущего
деления, присвоим B:
m− 1
Прежде всего, определим значение коэффициента старшего разряда m, как целую часть
⎡
(8)
Стр.3