Автоматика и телемеханика, № 7, 2019

Оптимизация, системный анализ

и исследование операций

(ФГАО ВО “Южно-Уральский государственный университет

(национальный исследовательский университет)”, Челябинск)

О СУЩЕСТВОВАНИИ ЦЕЛОЧИСЛЕННОГО РЕШЕНИЯ

РЕЛАКСИРОВАННОЙ ЗАДАЧИ ВЕБЕРА

ДЛЯ ДРЕВОВИДНОЙ СЕТИ¹

Рассмотрена задача нахождения оптимального размещения вершин

древовидной сети в монтажном пространстве, представляющем конеч-

ное множество. Критерием оптимальности является минимизация общей

стоимости размещения в точках пространства и стоимости коммуника-

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

тажного пространства. Рассматриваемая проблема известна как задача

Вебера. Дано представление задачи Вебера как задачи линейного про-

граммирования. Доказано, что множество оптимальных решений соот-

ветствующей релаксированной задачи Вебера для древовидной сети со-

держит целочисленное решение. Этот факт может быть использован для

повышения эффективности алгоритмов для задач, отличающихся от за-

дачи Вебера наличием дополнительных ограничений, так как позволяют

найти оптимальное значения целевой функции, что существенно сокраща-

ет сложность поиска оптимального решения, например, методом ветвей

и границ.

Ключевые слова: задача размещения, задача целочисленного линейного

программирования, релаксированная задача, вычислительная сложность,

полиномиальный алгоритм.

DOI: 10.1134/S0005231019070067

1. Введение

Рассматривается задача нахождения оптимального размещения вершин

древовидной сети в монтажном пространстве, представляющем конечное

множество [1, 2]. Критерием оптимальности является минимизация общей

стоимости размещения и стоимости связи. Допускается размещение разных

вершин дерева в одной точке пространства. Данная задача известна как зада-

ча Вебера. Возможное применение таких задач на практике приведено в [2].

В общем случае задача Вебера является NP -трудной. Для случая размеще-

ния древовидной сети известен полиномиальный алгоритм [3].

¹ Работа выполнена при финансовой поддержке Программы повышения конкуренто-

способности 5-100-2020 (постановление № 211 Правительства Российской Федерации, Госу-

дарственный контракт № 02.A03.21.0006).

134

В [4] доказана квазицелочисленность релаксационного многогранника за-

дачи Вебера, т.е. показано, что вершины и ребра многогранника задачи Вебе-

ра являются также вершинами и ребрами релаксационного многогранника.

Это позволяет для ее решения применять целочисленную версию симплекс-

метода. Для случая размещения древовидной сети [5] анонсировано свойство

релаксационного многогранника, состоящее в том, что множество оптималь-

ных решений релаксированной задачи содержит оптимальное решение исход-

ной задачи. В статье изложено доказательство данного результата.

Данный результат может быть использован при доказательстве существо-

вания оптимального целочисленного решения в задачах, отличающихся от

задачи Вебера для древовидной сети наличием дополнительных ограниче-

ний.

В первом разделе с целью введения обозначений и сохранения целостно-

сти изложения приведена формальная постановка задачи Вебера. Во вто-

ром разделе дана постановка задачи Вебера в виде задачи целочисленного

линейного программирования, построена релаксированная задача Вебера и

отмечены свойства ее многогранника. В третьем разделе с целью введения

дополнительных обозначений, используемых при доказательстве основного

результата, приведен полиномиальный алгоритм [3] решения задачи Вебе-

ра в случае размещения древовидной сети. В четвертом разделе приведен

пример задачи, отличающейся от задачи Вебера наличием дополнительно-

го ограничения и имеющей целочисленное оптимальное решение. Это поз-

воляет решать задачи, подобные рассмотренной, применяя полиномиальные

алгоритмы линейного программирования.

2. Формальная постановка задачи

Рассматриваемая экстремальная задача Θ(G, V, b, c, Φ) имеет вид

∑

(1)

C(ϕ) = c(j, ϕ(j)) +

b([i, j], ϕ(i), ϕ(j)) → min

ϕ∈Φ

j∈J

[i,j]∈E

для данных графа G = (J, E), конечного множества V , отображения

b : E × V ² → Z, отображения c : J × V → Z и множества Φ допустимых раз-

мещений элементов множества J в точках множества V .

В случае Φ = Φ_W = {ϕ : J → V } (т.е. представляет множество всех одно-

значных отображений) задача Θ = Θ_W известна как задача Вебера. В случае,

когда граф G(J, E) является деревом, для ее решения известен [3] полиноми-

альный алгоритм с вычислительной сложностью O(|J||V |²).

3. Представление задачи Вебера в виде задачи ЦЛП

Рассмотрим задачу целочисленного линейного программирования (ЦЛП)

∑

(2)

C(y, z) =

y^jvc(j,v) +

z^ijvub([i,j],v,u) → min ,

(y,z)∈M_W

j∈J, v∈V

[i,j]∈E, v,u∈V

135

допустимое множество M_W которой определяется системой ограничений

)

(∑

(3)

(∀i ∈ J)

y^iv = 1,

;

v∈V

)

(∑

∑

(4)

(∀[i,j] ∈ E, ∀v ∈ V )

z^ivju = y^iv,

z^iujv = y^jv,

;

u∈V

(

)

(

)

(5)

(∀i ∈ J, ∀v ∈ V )

y^iv ∈ {0,1}

;

(∀[i, j] ∈ E, ∀v, u ∈ V )

z^ijvu ∈ {0,1}

Задача (2)-(5) является трансляцией задачи Вебера (1) в комбинаторной по-

становке как задачи линейного программирования. Покажем, что имеется

взаимно однозначное соответствие между множеством допустимых решений

задачи (2)-(5) и задачи Θ_W , сохраняющее значение целевой функции.

Пусть ϕ ∈ Φ_W . Определим (y, z) следующим образом:

(

)

(6)

(∀i ∈ J, v ∈ V ) y^iv = χ_{

(ϕ(i))

(

)

(7)

(∀[i, j] ∈ E, v, u ∈ V ) z^ijvu = χ_{

(ϕ(i), ϕ(j))

(v,u)}

где χ_X (·)

- характеристическая функция множества X. Равенство

C_W (ϕ) = C_W (y,z) в данном случае очевидно. Включение (y,z) ∈ M_W следует

из однозначности отображения ϕ.

Обратно, если (y, z) ∈ M_W , то в соответствии с (3) и (5) функция

ϕ : J → V : ϕ(i) = v : y^iv = 1 является однозначной. Кроме того, из (4) сле-

дует, что z^vju = 1 в том и только том случае, если y^iv = y^u = 1. Следовательно,

имеет место равенство C_W (ϕ) = C_W (y, z).

Итак, возможна формулировка Θ_W как задачи целочисленного линейного

программирования (2)-(5). В дальнейшем задачу (2)-(5) будем также назы-

вать задачей Вебера Θ_W , а функции ϕ : J → V - ее решениями, имея в виду

переменные (y, z), определяемые в соответствии с (6)-(7).

4. Релаксированная задача Вебера

Одним из подходов к решению задач ЦЛП является переход к решению

непрерывной релаксированной задачи. В данном случае это достигается за-

меной в задаче (2)-(5) условий целочисленности (5) условиями неотрицатель-

ности

(

)

(

)

(8)

(∀i ∈ J, ∀v ∈ V )

y^iv ≥ 0

(∀[i, j] ∈ E, ∀v, u ∈ V )

z^ijvu ≥ 0

Далее допустимое множество релаксированной задачи Вебера будем обозна-

чать через

M_W . Очевидно, что M_W ⊂MW . В [4] доказана квазицелочислен-

ность многогранника

M_W , т.е. что вершины и ребра многогранника M_W яв-

ляются также вершинами и ребрами многогранника

M_W . В случае задачи

Вебера для древовидной сети имеет место ещe одно свойство многогранни-

ка

M_W , анонсированное в [5]:

136

Теорема 1. Если G - дерево, то оптимальное решение задачи Вебе-

ра Θ_W является также оптимальным решением соответствующей ре-

лаксированной задачи ВебераΘW .

Доказательство теоремы дано в Приложении. С целью введения дополни-

тельных обозначений, используемых при доказательстве теоремы, приведем

полиномиальный алгоритм [3] решения задачи Вебера в случае размещения

древовидной сети.

5. Алгоритм решения задачи Вебера для древовидной сети

Пусть N - мощность множества J, т.е. N = |J|, j_N ∈ J - висячая вершина

дерева (J, E). Выбор вершины j_N в качестве корня дерева (J, E) индуцирует

на J отношение частичного порядка

P = {(i,j) : i,j ∈ J, j принадлежит цепи в (J,E) между i и j_N}.

В дальнейшем будем считать, что J = {k}Nk=1 и удовлетворяет условию

(l, m) ∈ P ⇒ l < m. Прямой предок вершины l будем обозначать через F (l),

т.е. F (l) = m : [l, m] ∈ E, l < m.

Ниже представлен псевдокод алгоритма решения задачи Вебера Θ_W .

TreeVebPrbAlg (input: N, F, V, c, b; output: c, A, ϕ)

begin

for each (i, v) ∈ J × V do

c(i, v) := c(i, v)

for i := 1 up to N - 1 do

for each v ∈ V do

begin

c(F (i), v) := c(F (i), v) + min {c(i, u) + b([F (i), i], v, u)} ;

u∈V

A(i, v) := arg min {c(i, u) + b([F (i), i], v, u)} ;

u∈V

end

ϕ(N) := arg min[c(N, u)];

u∈V

for i := N - 1 down to 1 do ϕ(i) := A(i, ϕ(F (i)));

stop;

end.

Первый этап выполнения алгоритма заключается в последовательном вычис-

лении для всех v ∈ V псевдостоимостей

∑

(9)

c(i, v) := c(i, v) +

min

[c(j, u) + b([i, j], v, u)] , i = 1, . . . , N,

u∈V

j: i=F(j)

и псевдоразмещений

(10)

A(i, v) = arg min

[c(i, u) + b([F (i), i], u, v)] , i = 1, . . . , N,

u∈V

а второй этап - в последовательном вычислении оптимального размещения

вершин дерева

(11)

ϕ(N) := arg min[c(N, u)], ϕ(j) = A(j, ϕ(F (j))), j = N - 1, . . . , 1.

u∈V

137

Оптимальное значение задачи Вебера равно min [c(N, u)]. Вычислительная

u∈V

сложность алгоритма TreeVebPrbAlg составляет величину O(|J||V |²). Более

подробные описания и доказательства приведены в [3].

Несмотря на наличие полиномиального алгоритма решения задачи Вебе-

ра для древовидной сети доказанная теорема дает возможность установить

полиномиальную разрешимость задач, отличающихся от нее наличием до-

полнительных ограничений, для которых непосредственное применение ал-

горитма невозможно.

6. Пример

Рассмотрим задачу, отличающуюся от задачи Вебера (2)-(5) наличием до-

полнительных ограничений

)

(∑

(12)

(∀i ∈ J, v ∈ V )

y^iv = 1

i∈J

Покажем, что задача линейного программирования (2)-(4), (8), (12) имеет

целочисленное оптимальное решение. Действительно, применение к группе

ограничений (12) лагранжевых релаксаций приводит к задаче

⎧

⎨

⎨ ∑

(13) λ^∗ = arg max

min

(c(j, v) + λ_v) +

⎩

M_W ⎩

(y,z)∈

j∈J, v∈V

⎫

∑

⎬

∑

⎬

z^ij

b([i, j], v, u)

- |J|

⎭

λ_v⎭^,

[i,j]∈E, v,u∈V

v∈V

при этом оптимальное решение задачи (2)-(4), (8), (12) будет оптимальным

решением релаксированной задачи Вебера

∑

(14)

y^jv (c(j,v) + λ^∗v) +

z^ijvub([i,j],v,u) → min

(y,z)∈

M_W

j∈J, v∈V

[i,j]∈E, v,u∈V

Таким образом, из существования целочисленного решения задачи Вебера

следует существование целочисленного решения задачи (2)-(4), (8), (12). По-

этому для нахождения оптимального значения задачи (2)-(4), (8), (12) можно

применять полиномиальные алгоритмы линейного программирования. Зна-

ние оптимального значения целевой функции позволяет существенно сокра-

тить поиск оптимального решения, например методом ветвей и границ [6].

7. Заключение

Множество оптимальных решений релаксированной задачи Вебера для

древовидной сети содержит целочисленное оптимальное решение. Этот факт

позволяет исследовать полиномиальную разрешимость задач, отличающихся

138

от задачи Вебера для древовидной сети наличием дополнительных ограниче-

ний. Знание оптимального значения целевой функции позволяет существенно

сократить поиск оптимального решения, например, методом ветвей и границ.

ПРИЛОЖЕНИЕ

Доказательство теоремы. ЗадачаΘ∗W, двойственная к релаксиро-

ванной задаче ВебераΘW , имеет вид

∑

(Π.1)

C^∗W (x,w) =

x_j → max

(x,w)∈

M∗

j∈J

с допустимым множеством

M∗

, определяемым соотношениями

⎛

⎞

∑

(Π.2)

(∀(i, v) ∈ J × V )^⎝x_i -

w^ivj• - w

≤ c(i, v)^⎠ ,

j: i=F(j)

(

)

(Π.3)

(∀([i, j], v, u) ∈ E × V²)

w^ijv• + w^ij•u ≤ b([i,j],v,u

Здесь и далее для пустого нижнего парного индекса в группе w двойственных

переменных используется символ •.

Для доказательства теоремы достаточно построить допустимое решение

задачи (Π.1)-(Π.3), удовлетворяющее условиям дополняющей нежесткости

относительно решения ϕ ∈ Φ_V задачи Θ(G, V, b, c, Φ_V ), построенного алгорит-

мом TreeVebPrbAlg.

Положим

(

)

(Π.4)

(∀(i, v) ∈ J × V ) wv•i)i = min [c(i, u) + b([F (i), i], v, u)]

u∈V

Из (11) и (Π.4) следует

(Π.5)

wF(i)iϕ(F(i))

= c(i, ϕ(i)) + b([F (i), i], ϕ(F (i)), ϕ(i)).

Поскольку в оптимальном решении

zijϕ(i)ϕ(j) = 1,

то соответствующие ограничения (Π.3) должны быть активными. Это позво-

ляет определить

(

)

(Π.6)

(∀i ∈ J) wF(i)i•ϕ(i) = b([F (i), i], ϕ(F (i)), ϕ(i)) - wF(i)iϕ(F(i))• = -c(i, ϕ(i))

Полагая

(

{

})

(Π.7)

(∀i ∈ J, v ∈ V \ {ϕ(j)}) w•vi)i = min

b([F (i), i], u, v) - wu•)i

u∈V

139

получим вектор w, удовлетворяющий всем ограничениям (Π.3). Условие ак-

тивности ограничений, соответствующих переменным yiϕ(i), позволяет для

всех i ∈ J определить

∑

x_i = c(i,ϕ(i)) +

+ wF(i) i• ϕ(i) = c(i,ϕ(i)) + wF(i) i• ϕ(i) =

ϕ(i) •

j: i=F(j)

(Π.8)

{

c(N, ϕ(N)),

i=N;

∀i ∈ J \ {N}.

Второе равенство в данной цепочке является следствием (9) и (Π.5), а послед-

нее - следствием (Π.6) и отсутствия у вершины N предка. Для остальных

значений v ∈ V \ ϕ(J) в системе ограничений (Π.2) имеем

∑

c(i, v) +

w^ijv• + w•vi)i =

j: i=F(j)

{

}

= c(i, v) + w•vi) i = c(i, v) + min

b([F (i), i], u, v) - wu•)i

≥

u∈V

≥ min

{c(i, v) + b([F (i), i], l^∗, v)} - wF(i)il∗•=0.

v∈V

В данной цепочке первое равенство является следствием (9) и (Π.5), второе

равенство - следствием (Π.7). Неравенство очевидно при

(

)

l^∗ = arg min

b([i, F (i)], v, l) - wF(i)i

l•

l∈V

последнее равенство следует из (Π.4).

Таким образом, решение (x, w), построенное в соответствии с (Π.4)-(Π.8),

является допустимым решением задачи (Π.1)-(Π.3), удовлетворяющим усло-

виям дополняющей нежесткости относительно решения ϕ ∈ Φ_W задачи

для Θ(G, V, b, c, Φ_W ), построенного алгоритмом TreeVebPrbAlg. Следова-

тельно, оно является оптимальным решением задачи (Π.1)-(Π.3). Теорема

доказана.

СПИСОК ЛИТЕРАТУРЫ

1. Береснев В.Л. Дискретные задачи размещения и полиномы от булевых пере-

менных. Новосибирск: Изд-во ин-та мат. СО РАН, 2005.

2. Nickel S., Puerto J. Location Theory. Springer-Verlag, 2005.

3. Panyukov A.V., Pelzwerger B.V. Polynomial algorithms to finite Weber problem

for a tree network // J. Comput. Appl. Math. Elsevier Publ. 1991. V. 35. P.291-296.

https://doi.org/10.1016/0377-0427(91)90215-6

4. Panyukov A.V. The relaxation polyhedron of Weber problem / Non-smooth and

discontinuous problems of control and optimization. Chelyabinsk State Univ. 1998.

P. 171-174.

140