close

Вход

Забыли?

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

код для вставкиСкачать
254
International Journal “Information Theories and Applications”, Vol. 21, Number 3, 2014
АЛГОРИТМ РЕШЕНИЯ МНОГОКРИТЕРИАЛЬНЫХ ЗАДАЧ
ЛЕКСИКОГРАФИЧЕСКОЙ ОПТИМИЗАЦИИ С ВЫПУКЛЫМИ ФУНКЦИЯМИ
КРИТЕРИЕВ
Наталия Семенова, Мария Ломага, Виктор Семенов
Аннотация: Рассматривается многокритериальная задача лексикографической оптимизации с
выпуклыми функциями критериев на допустимом множестве, которое описывается линейными
ограничениями. Предлагается один из возможных подходов для решения многокритериальной задачи
лексикографической оптимизации, сочетающий идеи методов возможных направлений и
линеаризации, построен и обоснован алгоритм решения, приведены примеры, его иллюстрирующие.
Ключевые слова: многокритериальная задача,
оптимизация, возможные направления, линеаризация.
векторный
критерий,
лексикографическая
ACM Classification Keywords: G 1.6 Optimization.
Введение
Вопросы решения векторных задач оптимизации занимают важное место при решении проблем
математической экономики, теории игр, оптимального управления, статистических решений и других
научных дисциплин, в которых изучаются различные многокритериальные модели принятия
рациональных решений. Большое число задач управления, планирования, проектирования решаются с
применением векторных оптимизационных моделей. Это обстоятельство привело к появлению ряда
работ, посвященных методам решения и исследования векторных задач оптимизации [1 - 5]. В ряде
случаев частичные критерии могут быть упорядочены по важности, когда следует стремиться к
улучшению более важного критерия за счет любых потерь по всем другим менее важным [1, 2, 4, 5]. В
этом случае решение является обобщением понятия точки минимума (максимума) числовой функции на
случай нескольких функций при лексикографическом отношении порядка. Свойствам и методам поиска
лексикографически оптимальных решений посвящен ряд работ, в частности [1, 2, 5].
В данной работе исследуются векторные задачи лексикографической оптимизации с выпуклыми
функциями критериев на допустимом множестве, которое описывается линейными ограничениями.
Предлагается один из возможных подходов для решения многокритериальной задачи
лексикографической оптимизации, сочетающий идеи методов возможных направлений и линеаризации,
построен и обоснован алгоритм решения, приведены примеры, его иллюстрирующие.
Постановка задачи. Основные определения
Рассмотрим задачу лексикографической оптимизации вида:
min L  F  x  x  X  ,
(1)
F  x    f1  x  , , f l  x   , f k  x  , k  1,, l , − непрерывно дифференцируемые выпуклые функции, X
− выпуклое многогранное множество, заданное системой линейных неравенств
International Journal “Information Theories and Applications”, Vol. 21, Number 3, 2014
255
X   x  R n Ax  b , x  0 ,
(2)
где A  aij , aij  R , i  1,.m , j  1,.n , b  R m . Обозначим g i  x  − i -ое по порядку ограничение,
описывающее множество X .
Определение 1. Решение x   X будем называть лексикографически оптимальным, если не существует
другого допустимого решения y  X , такого что выполняется одно из следующих условий
1) f1  y   f1  x  ;
2) f1  y   f1  x  , f 2  y   f 2  x  ;
(3)
……………………………………......
l ) f k  y   f k  x  , k  1,2,, l  1 , f l  y   f l  x  ,
 
т.е. F  y   L F x .
Следовательно, для любого x  X истинно утверждение:
x  L  F , X    y  X | F  y   L F  x    ,
где L  F , X  – множество лексикографически оптимальных решений.
 
 
Если в определении 1 вместо X подставить X  O x * , где O x* – некоторая окрестность точки x* ,
то лексикографически оптимальную точку
лексикографически оптимальным решением.
x*
будем
называть
соответственно
локально
Определение 2. Ненулевое направление v из точки будем x называть возможным, если двигаясь из
точки x вдоль луча в направлении v на достаточно малое расстояние  , остаемся в области X , т.е.
если   0 , что  x   v   X для всех    0,   .
Определение 3. Вектор v  0 из точки будем x называть возможным направлением
лексикографического спуска, если   0 , что F  x   v   L F  x  и  x   v   X для всех
   0,   .
Определение 4. Совокупность ограничений задачи, которые для некоторой точки x выполняются как
равенства, назовем активными в этой точке и обозначим множество номеров таких ограничений J  x  .
Если x  int X , то J  x    . Пусть J  x    . Для каждой дифференцируемой функции g i  x  :
g i  x   v   g i  x    g vi  x  v  o    , где g vi  x  − производная по направлению v функции g i  x  в
точке x равны 0, т.е. g i  x   0 , i  J  x  . Направление v будет возможным ( g i  x   v   0 ) при
  0 и i  J  x  , если будет выполняться условие g vi  x   0 . Для непрерывно дифференцируемых
 i
v 
i
функций gv  x    g  x  ,  , поэтому можем записать ее в эквивалентном виде g i  x  , v  0 ,
v 



i  J  x .
Обозначим F  x  вектор, составленный из градиентов частных критериев вектор-функции F  x  в
точке x  X :
256
International Journal “Information Theories and Applications”, Vol. 21, Number 3, 2014
 f1  x 

x
 f1  x    f 1x
 f x   2  
F  x    2      x
1


  
f
x




 l

 f l  x 
 x
1

f1  x 
x2
f 2  x 
x2

f l  x 
x2
f1  x  

xn 
f 2  x  

xn  .

 

f l  x  

xn 

Пусть в рассматриваемой задаче (1) частные критерии являются квадратичными функциями вида
i
f i  x   x T Di x  ci T x , i  1, 2,, l , где Di  d pq
− симметричные неотрицательно определенные
матрицы, i  1, 2,, l , p  1, 2, , n , q  1, 2, , n , ci  R n , i  1, 2,, l . Поэтому F  x  для задачи
(1) будет иметь вид:
 2 D1 x  c1 


F  x    2 D2 x  c2  .

 2D x  c 
l 
 l
Выбор направлений
Пусть выбрана некоторая допустимая точка x 0  X . Поставим задачу выбора числа   0 и


направления v , таких, чтобы x 0  v  X и векторная функция F  x  приобретала лексикографически
меньшее значение в точке x 0   v , чем в точке x0 .
Для выполнения неравенства F  x   v   L F  x  , необходимо и достаточно, чтобы выполнялось одного
из условий
1) f1  x   v   f1  x  или  f1  x  , v   0 ;
2) f1  x   v   f1  x  , f 2  x   v   f 2  x  или  f1  x  , v   0 ,   f 2  x  , v   0 ;
……………………………………......
l ) f k  x   v   f k  x  , k  1,2,, l  1 , f l  y   f l  x  или   f k  x  , v   0 , k  1,2,, l  1 ,
 f  x  , v   0 ,
l
т.е.   F  x  , v   L 0 .
Теорема 1. Пусть для для некоторой точки x 0  X имеют место условия: A1 x 0  b1 , A2 x 0  b2 , где
AT   A1T , A2T  , bT   b1T , b2T  . Если выполняются условия  F  x 0  , v  L 0 и Av
1  0 , то v  0 из


точки x0 является возможным направлением лексикографического спуска.
Доказательство. Условие Av
1  0 является необходимым и достаточным условием того, что вектор
v  0 является возможным направлением. Действительно, пусть v  0 − возможное направление. По
определению   0 , которое для всех    0,  
x 0   v является допустимым решением, т.е.
A  x 0  v   b . Учитывая представление AT   A1T , A2T  , bT   b1T , b2T  последнее неравенство






 
запишем A1 x0  v  b1 , A2 x 0  v  b2 . Неравенство A1 x0  v  b1  A1 x0  A1  v   b1 ,
International Journal “Information Theories and Applications”, Vol. 21, Number 3, 2014
b1   A1  v   b1
257
 Av
1  0 . Пусть теперь выполняется условие Av
1  0 , покажем, что v  0 −
возможное направление. Поскольку
Av
то A1  x0  v   b1 для   0 .
1 0 ,
A1 x 0  b1 ,
A2  x0  v   A2  x0   A2  v  . Если A2v  0 , то A2  x 0  v   b2 для   0 . Если A2v  0 , то
 b 
A2  x0  v   b2 для    0,   , где   min  i  , b  b2  A2 x 0 , v  A2v .
 vi 
Поскольку частные критерии вектор-функции F дифференцируемы, то следуя теореме Тейлора


возможно представление F  x 0   v   F  x 0    F  x 0  , v при достаточно малых расстояниях между


x0 и x 0   v . Откуда получаем F  x 0   v   F  x 0    F  x 0  , v  L 0 . Теорема доказана.
Итак, возможным направлением лексикографического спуска из допустимой точки x есть такое
возможное направление v , которое удовлетворяет условию   F  x  , v   L 0 .
Естественно искать такое направление спуска, которое доставляет лексикографический минимум
min L  F  x  , v  при условиях Av
1  0 , 1  vi  1 . Последнее ограничение называют нормирующим.

Его необходимо включить, поскольку, если существует вектор v , такой, что   F  x  , v   L 0 и Av
1  0,
то среди координат оптимального значения вектор функции может быть  (ограничению удовлетворяет
произвольный вектор  v , где  − произвольное большое число).
Если
min L   F  x  , v   L 0 ,
(т.е.,   F  x  , v   0 или
 F  x  , v  
L
(4)
0 ), то допустимая точка x является лексикографически
оптимальным решением задачи (1).
Пусть x0 - допустимое решение задачи (1). Рассмотрим последовательность точек
x k 1  x k   k  z k  x k  ,
(5)
где k  0 , z k  x k − возможное направление лексикографического спуска из точки x k . Необходимым
требованием является принадлежность каждой точки x k 1 ,
допустимой области.
Поскольку функции g i  x  , i  1,.m  n , в ограничениях задачи являются линейными, следовательно
выпуклыми, то это требование будет выполнено, если


g i  x k    g i  x k  , z k  x k  0 , i  1,.m  n .
(6)
Для задачи (1) направление z k  x k будет возможным направлением лексикографического спуска, если
F  x  , z  
k
k
L
0.
(7)
Поэтому для нахождения zk , которое удовлетворяет условиям (6), (7), решаем следующую
лексикографическую задачу линейного программирования:

min L  F  x k  , z
при условиях

258
International Journal “Information Theories and Applications”, Vol. 21, Number 3, 2014


g i  x k    g i  x k  , z k  x k  0 , i  1,.m  n ,
т.е., для нашего случая


min L  F  x k  , z ,
(8)
Az  b ,
(9)
z 0.
(10)
Вследствие выпуклости допустимой области задачи (1) x k 1 будет допустимым, решением, если x k
является допустимым.
Выбор длины шага
Пусть max  0 – наибольшее значение  , при котором, двигаясь в направлении z k  x k из точки xk ,


остаемся в допустимой области, т.е. g i x k   max  z k  x k   0 , i  1,.m . Тогда длина шага   k
может быть определена как решение задачи:



F x k   k  z k  x k   min L F x k    z k  x k 
0  max

(11)
Для задачи (1) метод линеаризации сходящийся, поскольку в задаче (8) - (10) учтены все ограничения
начальной задачи.
Справедлива теорема.
Теорема 2. Если min L  F ( x ) | Ax  b, x  0  F  x     , то процесс решения (5), (8) – (10), где k
определяется из условия (11), приводит за конечное число итераций к лексикографически оптимальному
решению x задачи (1).
Приближенный алгоритм решения квадратичных задач лексикографической оптимизации
Алгоритм поиска приближенного лексикографического минимума выпуклых лексикографических задач
условно состоит из двух этапов. На первом этапе решается лексикографическая задача линейного
программирования для нахождения возможного направления лексикографического спуска, на втором
происходит поиск величины шага и экстремальной точки.
k - ая итерация алгоритма.
Выбираем допустимое решение x k задачи (1). Задаем вектор  . Находим значение F  x  в точке x k :
  x  ,, f  x   .
F  x k   f
T
k
1
k
l
n f  x k 
 n f1  x k 

l
Строим функцию   z    
z j ,  ,
zj  .
 j 1 x j

x j
j 1


Решаем лексикографическую задачу линейного программирования вида:
min L   z  ,
n
a
j 1
ij
z j  bi , i  1,, m
International Journal “Information Theories and Applications”, Vol. 21, Number 3, 2014
259
z j  0 j  1,  , n .

Пусть z k  z1k , z 2k ,..., znk

– ее лексикографически оптимальное решение. Переходим к пункту 3
алгоритма.
 
Вычисляем F xk
. Если
F  x  , z
k
k



 x k  L 0 или  f i  x k 1  , f i  x k    i , i  1,, l , в

лексикографическом порядке(  .  − расстояние между fi xk 1

 
и , fi x k
), то x k − точка
лексикографического минимума, иначе переходим к пункту 4 алгоритма.


Ищем следующее приближение по правилу x k 1  x k   k z k  x k , где




 k : min L F x k    z k  x k   F x k   k  z k  x k  ,
0  max
и возвращаемся к пункту 1 алгоритма, заменив x k на x k 1 .
Примеры

Пример 1. Решить задачу min L x12  2 x2 2  x1  x2 , 4 x12  x2 2  x1  x2

при условиях x1  x2  3 ,
x1  x2  4 , x1  0 , x2  0 .
Решение. Допустимое множество X , заданное системой линейных ограничений, изображено на рисунке
1. Точное решение x opt   0.5, 0.25  .
Решение, полученное алгоритмически:
 
1 шаг. 1) Пусть x 0   0, 0  − начальное допустимое решение.    0.01, 0.01 . Вычисляем F x0 и




T
F  x0  . F  x 0    0, 0  , F  x   2 x1  1 4 x2  1  F  x0   1 1 .
1 1
8 x1  1 2 x2  1
2) Строим функцию     z1  z 2 , z1  z 2  и решаем лексикографическим симплекс-алгоритмом [2]
задачу min L   z1  z 2 , z1  z 2  , при условиях z1  z2  3 , z1  z2  4 , z1  0 , z2  0 .
Получаем лексикографически оптимальное решение z 0  (0, 4) .

3) F  x1     0.125,  0.1875  ,  F  x 0  , z 0  x 0
T



T


  4, 4   L 0 ,  f i  x1  , f i  x 0   0.01 .

 

4) x1  x0  0 z 0  x 0   0,0   0 (0, 4)   0, 40  . F x1     32 2  4,16 2  4 .
0 находим как решение задачи min L F  x1     по схеме скаляризации, на каждом шаге которой
0 1
используем методы однокритериальной оптимизации квадратичных функций. 0  0.0625
x1   0, 0.25  .

260
International Journal “Information Theories and Applications”, Vol. 21, Number 3, 2014
 
2 шаг. 1) Вычисляем F x1 
 11

0
0.5 .
2) Строим функцию     z1 , z1  0.5 z 2  . Решаем лексикографическим симплекс-алгоритмом задачу
min L   z1 , z1  0.5 z 2  , при условиях z1  z2  3 , z1  z2  4 , z1  0 , z2  0 .
Получили лексикографически оптимальное решение z1  (3.5,0.5) .

3) F  x 2     0.3725,1.2709  ,  F  x1  , z1  x1
T



  3.5,3.375   L 0 ,  f i  x 2  , f i  x1   0.01 .
T


4) x 2   0, 0.25   1 (3.5, 0.5)   3.51 , 0.25  0.251  . F x 2    . 1 находим как решение задачи
min L F  x 2     по схеме скаляризации. 1  0.1414  x 2   0.4949, 0.2854  .
0 1


0.0101 0.1414
3 шаг. 1) Вычисляем F x2  4.9596 0.4293 .
 
2) Построим функцию    0.0101z1  0.1414 z 2 , 4.9596 z1  0.4293 z 2  и решим при помощи
лексикографического симплекс-алгоритма задачу: min L  , при условиях z1  z2  3 , z1  z2  4 , z1  0
, z2  0 . Получим лексикографически оптимальное решение z 2  (3,0) .
F  x 3     0.3726,1.3356 
T
3)

 F  x  , z
,
2
2
 x2

T
  0.0657,12.5465   L 0
,

 f i  x 3  , f i  x 2   0.01 .


4) x 3   0.4949  2.5051 2 , 0.2854  0.2854 1  . F x3    . 2 находим как решение задачи
min L F  x 3     по схеме скаляризации. 2  0.0051  x 3   0.5077, 0.2839  .
0 1
 


0.0154 0.1356
4 шаг. 1) Вычисляем F x3  5.0618 0.4322 .
2) Строим функцию    0.0154 z1  0.1356 z 2 ,5.0618 z1  0.4322 z 2  и решаем лексикографическим
симплекс алгоритмом задачу: min L  , при условиях z1  z2  3 , z1  z2  4 , z1  0 , z2  0 .
International Journal “Information Theories and Applications”, Vol. 21, Number 3, 2014
261
Получим лексикографически оптимальное решение z 2  (0, 4) .
3) F  x 3     0.3726,1.3356  ,
T
 F  x  , z
3
3
 x3

T
  0.496, 4.176   L 0 . Итак, приближенное
оптимальное решение задачи x 3   0.5077, 0.2839  и Flex min T   0.3726,1.3356  .
Рассмотрим случай, когда оптимальное решение является крайней точкой многогранного множества.


Пример 2. min L x12  x2 2  x1  x2  4,  2 x12  x2 2  x1  x2  1 , при условиях x1  x2  3 , x1  x2  4 ,
x1  0 , x2  0 .
1
шаг.
1)
x 0   0, 0  ,

F  x  
   0.01, 0.01 .

 24xx 11
1
1

2 x2  1
2 x2  1
,
F  x 0    4,1 ,
T
F  x0   1 1 .
1 1
2) min L  z1  z 2 , z1  z 2  , при условиях z1  z2  3 , z1  z2  4 , z1  0 , z2  0 . z opt   0, 4  .

   4, 4   0 ,   f  x  , f  x    0.01 .
4) x   0.0     0, 4    0, 4  . F  x    16  4  4,16  4  1 .
min F  x     ,    0,1    1 , x   0, 4  .
3) F  x1     16,13  ,  F  x 0  , z 0  x 0
T
L
1
1
2 шаг. 1) x   0, 4  .
1
i
1
1
L
T
2
0
i
2
1


F  x1   1 9
1 7 .
L
opt
2) min  z1  9 z 2 , z1  7 z 2  при условиях z1  z2  3 , z1  z2  4 , z1  0 , z2  0 . z   0, 4  .
3) F  x1     16,13  ,
T
 F  x  , z
1
1
 x1

T
  0, 0   L 0 , x1   0, 4  - приближенное оптимальное
решение. Flex min T   16,13 .
Выводы
Рассмотрена постановка векторной задачи лексикографической оптимизации с выпуклыми функциями
критериев на допустимом множестве, которое описывается линейными ограничениями. Предлагается
один из возможных подходов к решению многокритериальной задачи лексикографической оптимизации,
сочетающий идеи методов возможных направлений и линеаризации, Описанный лексикографический
метод линеаризации позволяет свести процесс решения выпуклой задачи лексикографической
оптимизации к решению одной или последовательности вспомогательных лексикографических задач
линейного программирования. Построен и обоснован алгоритм решения, приведены примеры, его
иллюстрирующие.
Библиография
[1] Подиновский В.В., Гаврилов В.М. Оптимизация по последовательно применяемым критериям. – М.: Сов. радио,
1975. – 192 с.
[2] Червак Ю.Ю. Оптимізація.Непокращуваний вибір. – Ужгород: Ужгородський національний університет, 2002. 312 с.
[3] Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач.– М.: Наука., 1982. 256 с.
262
International Journal “Information Theories and Applications”, Vol. 21, Number 3, 2014
[4] Семенова Н.В., Колєчкіна Л.М. Векторні задачі дискретної оптимізації на комбінаторних множинах: методи
дослідження та розв’язання. – К.: Наук. думка, 2009. – 266 с.
[5] Ломага М.М., Семенов В.В. Квадратичные задачи лексикографической оптимизации: свойства и решения //
Компьютерная математика. – 2013. – №2. – С. 134-143.
Информация об авторах
Наталия Владимировна Семенова – ведущий научный сотрудник Института
кибернетики им В.М. Глушкова НАН Украины, доктор физ.-мат наук, 03680 МСП Киев 187,
проспект академика Глушкова, 40, Украина; e-mail: [email protected]
Мария Ломага – ассистент Ужгородского национального университета, г. Ужгород, пл.
Народная, 3, Украина; e-mail: [email protected]
Виктор Семенов – младший научный сотрудник Института кибернетики им В.М.
Глушкова НАН Украины, г. Киев, пр. Академика В.М. Глушкова, 40, Украина; e-mail:
[email protected]
Solution Algorithm of Multicriteria Problems of Lexicographic Optimization with Convex Criteria
Functions
Natalia Semenova, Maria Lomaha, Victor Semenov
Abstract: In the paper a multicriteria problem of lexicographic optimization with convex functions of the criteria on
the feasible set described by linear restrictions is considered. One of the possible approaches to the solution of
the multicriteria problem of lexicographic optimization is suggested. The approach combines the ideas of methods
of feasible directions and linearization. A solution algorithm has been built and proved; some illustrating examples
have been given.
Keywords: multicriteria problem, vector criterion, lexicographic optimization, feasible directions, linearization
1/--страниц
Пожаловаться на содержимое документа