close

Вход

Забыли?

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

?

Двойственный декомпозиционный метод решения общей задачи дробно-линейного программирования.

код для вставкиСкачать
УДК 517.3
ДВОЙСТВЕННЫЙ ДЕКОМПОЗИЦИОННЫЙ МЕТОД РЕШЕНИЯ ОБЩЕЙ
ЗАДАЧИ ДРОБНО-ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
М.Л. Лапшина, Е.И. Цикова
Описан декомпозиционный метод двойственного типа для решения общей задачи дробно-линейного
программирования с ограничениями, расчлененными на два горизонтальных блока. Приведена оценка скорости
сходимости метода
Ключевые слова: метод, сходимость, итерация
Важнейшая особенность имитационного
моделирования деятельности предприятий –
инструментальная
поддержка
анализа
функционирования
всех
аспектов
(технологическом,
экономическом,
организационном
и
пр.)
с
целью
совершенствования
производственных
и
управленческих процессов, скоординированной и
контролируемой работы всех подсистем, что
способствует
повышению
монолитности
предприятия, формированию единого целостного
организма, способного в кратчайшие сроки
мобилизовать все свои ресурсы и перебросить их
на направление «главного удара». Увидеть не
только сегодняшние «узкие места», но и
предвосхитить с помощью имитационной модели
их появление в будущем, а также в любой момент
времени можно получить ответ на вопрос о том,
что, почему и как происходит в каждой из
подсистем предприятия.
Общая
задача
дробно-линейного
программирования (ДЛП) состоит в максимизации
функции
p ( x)
f ( x ) = min l
(1)
1≤l ≤m q ( x )
l
на непустом выпуклом многогранном множестве
G% , задаваемом системой линейных уравнений и
неравенств, где pl ( x ) , ql ( x ) – аффинные
функции, определенные в n-мерном евклидовом
пространстве
En , G% ⊂ En
Идея
декомпозиционного метода состоит в следующем:
• Выберем произвольный параметр R, R < ∞
и обозначим через S(R) множество из Em+ m ,
1
задаваемое соотношением
S ( R ) = {( y , z ) ∈ S : zl ≤ R, l = 1, K , m1}
где S определено. Тогда, S (∞ ) = S , S ( R ' ∈ S ( R '')
при R ' < R '' .
Введем задачу минимизации P% ( R )
ϕ ( y , z ) → min, ( y , z ) ∈ S ( R )
Задача P% ( R ) отличается от P% множеством,
на котором минимизируется функция ϕ , причем
при любом R < ∞ множество S(R) из задачи (2)
является ограниченным и содержится в S. Чтобы
построить задачу P(R), по отношению к которой,
P% ( R ) является двойственной задачей, введем
функцию ψ R ( x ) такую, что
ψ R ( x ) = inf F ( x, y , z ) ∀x ∈ G.
( y , z )∈S
Тогда задача P(R) имеет вид
ψ R ( x ) → max, x ∈ G.
Если учесть равенство
ψ R ( x ) = min
m1
pl ( x ) − R ∑ aS ( x )
S =1
,
ql ( x )
то окончательная запись задачи P(R) выглядит так:
m1
pl ( x ) − R ∑ aS ( x )
S =1
P ( R ) : f R ( x ) = min
→ max,
1≤m≤l
ql ( x )
1≤l ≤m
x∈G .
(3)
Учитывая, что G и S(R) при R < ∞ –
непустые выпуклые компакты, мы можем
гарантировать, что максимальное значение задачи
(3) и минимальное значение задачи (2) совпадают.
Обозначим общее экстремальное значение обеих
задач через V(R). Если допустить разрешимость
задачи P = P (∞ ) (что в наших предположениях о
компактности G эквивалентно совместности
системы ограничений этой задачи), то задачи
P = P (∞ ) и P% = P% (∞ ) также имеют общее
экстремальное значение V = V (∞ ) .
Под ε-решением задачи Р ( ε ≥ 0 ) условимся
понимать любую точку х∈G, для которой
выполняются неравенства
f ( x) ≥ V − ε ,
(2)
Лапшина Марина Леонидовна – ВГТУ, д-р техн.
наук, доцент, тел. (4732) 464-222
Цикова Елена
Игоревна
–
ВИИС,
ст.
преподаватель, тел. (4732) 354-898
(4)
max a ( x ) ≤ ε .
1≤l ≤ m1 l
Формулировка задачи P(R), 0 < R < ∞
выглядит так: при любом ε ≥ 0 точка х∈G – εрешение задачи P(R), если
f ( x) ≥ V − ε ,
где f(R) определена в (3).
(5)
• Выберем некоторое конечное R > 0.
Зададим произвольное ε ≥ 0 . Декомпозиционный
метод позволяет за конечное число итераций
получить ε-решение задачи P(R), которое при
достаточно большом R является также ε-решением
исходной задачи Р.
Допустим, что уже проведено k - 1 итераций
метода (ситуация k = 1 соответствует началу
процесса, когда предыдущих итераций нет). В
результате получено k – 1 точек xi ∈ G (i = 1, ..., k –
1), k точек (yi, zi)∈S(R) (i=1,…, k) и k - 1 чисел φ(yi,
zi) (i=1, ., k-1). Заметим, что при k=1 точки хi
отсутствуют и считается известной лишь одна
точка (yi , zi), В качестве которой можно выбрать
произвольный элемент множества S(R).
В начале итерации решается задача дробнолинейного программирования
k
k
y , p( x) + z , a( x)
→ max, x ∈ G (6)
k
y , q( x)
Заметим, что (6) - это частный случай задачи
максимизации на многогранном множестве, когда
m = 1. В результате решения задачи (6)
определяются ее оптимальный план xk и
максимальное значение ее линейной формы,
k k
i i
*
равное ϕ ( y , z ) . Пусть ϕ k = min ϕ ( y , z ) 1≤i ≤ k
максимальное значение функции ϕ , полученное
за k итераций.
Если хотя бы одна из точек xi, i = 1, …, k.
i
*
удовлетворяет условию f R ( x ) ≥ ϕ k − ε , то эта
точка и будет искомым ε-решением задачи P(R).
При обнаружении такой точки итерация k, а
вместе с ней и весь процесс решения задачи P(R)
заканчиваются. Если
*
i
ϕ k − f R ( x ) > ε , i = 1,..., k , (7)
то итерация k продолжается.
Положим
i
i
y, p( x ) + z, a( x )
ϕ k ( y , z ) = max
. (8)
i
1≤i ≤k
y, q( x )
Согласно (8), функция φi является нижней
аппроксимацией
φ
на
S(R),
причем
i i
i i
ϕ k ( y , z ) = ϕ ( y , z ) для i = 1, ... , k. Рассмотрим
многогранник
являющийся
Qk ∈ Em + m ,
1
множеством уровня функции φk на S(R) при
*
значении уровня, равном ϕ k :
*
Qk = {( y , z ) ∈ S ( R ) : ϕ k ( y , z ) ≤ ϕ k }.
Многогранник Qk не пуст, поскольку
содержит точку, в которой φk достигает минимума
на S(R). В силу (8) многогранник Qk задается
системой ограничений
i
i
i
*
y , p ( x ) − ϕ k q ( x ) + z , a ( x ) ≤ 0,
(9)
i = 1,..., k , ( y , z ) ∈ S ( R )
Пусть А - плоскость в пространстве Em+ m ,
1
m
определяемая уравнением ∑ i =1 yi = 1 , Вi плоскость с уравнением, получаемым из
неравенства в (9) заменой знака неравенства на
знак равенства, B 'i = Bi ∩ A . Далее на итерации k
ищем точку многогранника Qk, минимальное
расстояние котoрой до B 'i , i = 1, ... , k,
максимально, причем нам понадобится не сама
точка, а лишь величина ее минимального
расстояния. Положим
i
i
i
i
i
*
b = (b1 ,..., bm+ m ) = ( p ( x ) − ϕ k q ( x '), a ( x )),
1
i = 1,..., k , a = ( a1 ,..., am+ m ),
1
где первые m чисел аi - единицы, а остальные нули. Если точка (у, z)∈Qk⊂А, то расстояние
ρ(у, z) этой точки до Вi можно найти по формуле
⎡ y , p ( xi ) − ϕ * q ( xi ) + z , a ( xi ) ⎤
k
⎦,
ρ ( y, z ) = − ⎣
i
d (k , x )
(10)
1/2
2⎞
⎛ i2
i
−1/2
d ( k , x ) = ⎜ b m − ∑ im=1 b 'i ⎟ m
.
(
⎝
)
⎠
i
В нашем случае величины d ( k , x ) всегда
положительны, причем не могут принимать сколь
угодно малые значения, поскольку справедливы
неравенства
i
d ( k , x ) > εδ / (1 + 2 Rm1 ), i = 1, ..., k , (11)
где δ> 0 определено, а ε > 0 было задано в начале
вычислений.
Неравенство (11) указывает на то, что
плоскости А и Вi не могут быть параллельными и,
следовательно, их пересечение B 'i - линейное
многообразие размерности m + m1 - 2.
Рассмотрим задачу ЛП с переменными t, y, z
вида
t→max
i
*
i
i
i
y , p ( x ) − ϕ k q ( x ) + z , a ( x ) + d ( k , x )t ≤ 0
(12)
i = 1,..., k , ( y , x ) ∈ S ( R ).
Максимальное значение ∆k этой задачи
является максимальной величиной минимального
расстояния точек из Qk до линейных
многообразий B 'i , i = 1, ... , k. Решив задачу (12),
∆k
решение задачи,
k
двойственной к (12). Пусть α i ≥ 0 (i = 1, ..., k) –
компонента
этого
решения,
отвечающая
ограничению i задачи (12).
k
i
Заметим, что ∑ ik=1α i d ( k , x ) = 1 , поэтому
k
среди α i имеются положительные числа
−1
k
k
k i
x = ∑ ik=1α i
∑ ik=1α i x ∈ G (13)
найдем
и
(
Если
получим
)
k
*
f R ( x ) ≥ ϕk − ε ,
то
точка
x
k
принимается за исходное решение и итерация k
заканчивается, а вместе с ней и весь итеративный
процесс. В противном случае продолжаем
итерацию k и переходим к вычислению новой
k +1 k +1
,z
) ∈ S ( R ) . Это будет проекция
точки ( y
k k
точки ( y , z ) на многогранник, который
задается системой ограничений относительно (у,
z), получаемой из (12) при t = ∆k /2.
Таким образом, для определения точки
k +1 k +1
(y
,z
)
необходимо
решить
задачу
квадратичного программирования
2
k
k
y−y
+ z − z → min
∆
i
* i
i
y , p ( x ) − ϕ k q ( x ) + z , a ( x ) + k ≤ 0, (14)
2
i = 1,..., k , ( x, y ) ∈ S ( R ).
На этом итерация k заканчивается и
осуществляется переход к следующей итерации.
Итеративный процесс продолжается до получения
ε-решения задачи (13).
Обоснуем используемый метод. Для этого
остановимся на трех моментах, связанных со
сходимостью
декомпозиционного
метода:
убедимся в справедливости неравенства (11);
дадим оценку скорости сходимости метода;
приведем соображения о выборе параметра R.
1. Лемма. Пусть b = (b1 ,..., bm + m ) 1
произвольный элемент Em+ m ,
1
⎧
w (b ) = max ⎨ max bl − min bl ,
max
bl
⎩1≤l ≤ m 1≤l ≤ m m +1≤l ≤ m + m1
⎫
⎬,
⎭
(15)
тогда имеют место неравенства
2
2
2
2 1/2 −1/2
w(b ) ≤ ( b m − ( ∑ lm=1 bl ) ) m
≤ b (16)
В нашем случае тождественность обеих
частей равенства (16) выполняется.
При описании отдельной итерации метода
k
мы ввели вектор x ∈ G , который является
i
выпуклой комбинацией точек x , i=1,..., k, с
коэффициентами,
определенными
решением
задачи ЛП, двойственной к (12). Приводимое
ниже утверждение позволяет оценить уклонение
k
x от решения задачи P(R) по функционалу и тем
самым дает оценку сверху для скорости
сходимости метода [1].
Положим
p = max max pl ( x ) , q = max max ql ( x ) ,
1≤l ≤m x∈G
1≤l ≤m x∈G
a = max max al ( x ) .
1≤l ≤m x∈G
k
является
Теорема 1. Точка x
решением задачи P(R), т.е.
k
f R ( x ) ≥ V ( R ) − c1∆ k ,
где
(17)
c1∆ k -
(18)
c1 =
(( p + ( p + Ram1 ) qδ −1 ) m + am1 ) δ −1. (19)
Положительные числа ∆ k стремятся к нулю
со скоростью, для которой справедлива оценка
−1/2
(20)
∆ k ≤ c2 k
,
где
−1/2
2 1/2
c2 = 4 × 3
(2 + 4 R m1 ) ×
.
(21)
−2
×((2 p + m1Ra ) m + am1 ) qδ .
Д о к а з а т е л ь с т в о . Пусть α i ≥ 0 , i=1,..., k, компонента решения задачи, двойственной к
задаче ЛП (12), которая отвечает ограничению i в
(12). Тогда из хорошо известных фактов ЛП
следует, что
⎡
k
k
⎢ y ,ϕk* ∑ αi q ( xi ) − ∑ αi p ( xi ) −
max
( x. y )∈S ( R ) ⎢⎣
i =1
i =1
k
− z , ∑ α i a ( xi )
i =1
⎤
⎥=∆ ,
k
⎥⎦
(22)
k
i
(23)
∑ αi d (k , x ) = 1
i =1
где ∆ k - максимальное значение линейной формы
задачи (12) [2].
Учитывая аффинность вектор-функций р(х),
q(x) и а(х) и вид многогранника S(R),
определяемого соотношением (11), получаем
k
k
*
max [ϕ q ( x ) − pl ( x )] +
1≤l ≤ m k l
−1
m1
k
⎛
⎞
k
+ R ∑ al ( x ) = ∆ k ⎜ ∑ α i ⎟
i =1
⎝ i =1 ⎠
или, учитывая определение функции fR(X), имеем
−1
k
⎛
⎞
k
*
ϕk − f R ( x ) ≤ ∆ k ⎜ δ ∑ αi ⎟ .
(24)
⎝ i =1 ⎠
−1
. Из
Оценим теперь сверху величину ∑ ik=1α i
−1
i
(23) следует, что
≤ max ( k , x ) .
∑ ik=1α i
1≤i≤ k
(
(
)
)
Далее, учитывая определение d(k, xi) и правую
часть неравенства (16), получаем
−1
(25)
≤ max bi ,
∑ ik=1α i
1≤i≤ k
i
i
* i
i
где b = ( p ( x ) − ϕ k ( x ), a ( x )).
Оценка (18) при c1, определяемом (19),
вытекает из (24), (25) и того, что
* i
−1
V ≤ ϕ k , b ≤ ( p + ( p + Ram1 ) qδ ) m + am1.
2. Данный метод основан на алгоритме [3],
применяемом для минимизации функции φ(y, z) на
многограннике S(R). Из доказательства теоремы 1
[2] при λ = 1/2 следует, что
−1
−1
2
∆ k ≤ 4 × 3 d ( R ) Lϕ k 2 , k = 1, K , (26)
(
)
где d(R) - диаметр S(R), Lφ - постоянная Липшица
функции φ(у, z). Неравенство (20) при c2,
определяемом (21), вытекает из (26) и того, что
2 1/2
d ( R ) ≤ (2 + 4 R m1 ) ,
−2
Lϕ ≤ ((2 p + m1Ra ) m + am1 ) qδ .
3. При использовании рассматриваемого
метода необходимо предварительно задать
параметр R > 0. Приведем утверждение
устанавливающее связь между приближенными
решениями задачи P(R) и исходной задачи Р и
помогающее
выбрать
R
перед
началом
вычислений.
Рассмотрим задачу P% , двойственную к
исходной
задаче
Р.
В
предположении
%
разрешимости Р задача P также разрешима.
* *
*
*
*
*
Пусть
( y , z ) = ( y1 , K , ym , z1 , K , z m )
1
1
произвольное решение задачи P% , число q>0
определено в (17).
ε
Теорема 2. Если xR - ε-решение задачи P(R)
и
*
R ≥ q + max zl ,
1≤l ≤ m1
(27)
ε
то xR является также ε-решением задачи Р.
Д о к а з а т е л ь с т в о . При любом
*
R ≥ max zl ,
1≤l ≤ m1
V(R) ≥ V,
*
если R ≥ max zl .
1≤l ≤ m1
Пусть
*
R1 = max zl .
1≤l ≤ m1
(28)
В предположении
(27) имеем
*
*
pl ( xR ) − R a ( xR )
1
V ( R ) − ε ≤ min
≤
*
1≤l ≤ m
ql ( xR )
≤ V ( R1 ) −
R − R1
*
*
a ( xR ) ≤ V ( R1 ) − a ( xR ) .
1
1
q
Из последнего неравенства с учетом (28)
получаем
*
a ( xR ) ≤ ε .
(29)
Утверждение теоремы 2 вытекает из (29), и
того, что
*
*
f ( xR ) ≥ f R ( xR ) ≥ V ( R ) − ε > V − ε ,
где функции f и fR определены[3].
Использовать теорему 2 можно лишь в
случае, когда нам известна оценка сверху для
*
величины max zl .
1≤l ≤ m1
Литература
имеют место неравенства
*
*
pl ( x R ) − R a ( x R )
1
V ( R ) = min
≤
*
1≤l ≤m1
ql ( x R )
* * *
* * *
∑ im=1 yl pl ( x R ) + ∑ im=1 zl al ( xR )
≤
≤
* * *
∑ im=1 yl ql ( xR )
* *
≤ ϕ( y , z ) = V ,
где V и V(R) - экстремальные значения задач Р и
P(R).
С другой стороны, V(R) ≥ V при любом R > 0.
Таким образом,
1. Гольштейн Е.Г., Борисова Э.П., Дубсон М.С.
Диалоговая система анализа многокритериальных задач
/Е.Г. Гольштейн, Э.П. Борисова, М.С. Дубсон //
Экономика и мат. методы. М.: Haука, - 1990. Т. 25. Вып.
4. - С.47-52.
2. Gale D. On optimal development in a multi-sector
economy / D. Gale. - Review of Economic Studies. - 1967. 34(1). - №97. - p.1-18.
3. Гольштейн
Е.Г.
Двойственные
задачи
выпуклого и дробно-выпуклого программирования в
функциональных пространствах / Е.Г. Гольштейн //
Исследования по математическому программированию.
М.: Haука, - 1968. – 233c.
Воронежский государственный технический университет
Воронежский институт инновационных систем
А DUAL DECOMPOSITION METHOD FOR SOLVING THE GENERAL FRACTIONAL
LINЕАR PROGRAMMING РRОBLЕM
M.L. Lapshina, E.I. Tsikova
А dесоmроsitiоn dual-type method for solving the general fгасtiоnаl linеаr рrоgгаmming рrobеm with
соnstraints partitioned into two horizontal blocks is described. The methods convergence rate is given
Key words: method, convergence, iteration
Документ
Категория
Без категории
Просмотров
5
Размер файла
247 Кб
Теги
решение, двойственной, метод, декомпозиционные, линейного, задачи, программирование, дробной, общее
1/--страниц
Пожаловаться на содержимое документа