Некоторые свойства многогранника. Задачи о P-медиане
Некоторые свойства многогранника. Задачи о P-медиане
Г.Г. Забудский, Институт информационных технологий и прикладной математики СО РАН
1. Постановка задачи и определения
Задачи оптимального размещения объектов имеют много практических приложений. Описываются различные постановки таких задач [1-8]. В данной статье рассматривается известная NP-трудная задача оптимального размещения на графе - задача о p-медиане [1,7-8]. Для ее исследования здесь применяется подход, развиваемый в работах А.А. Колоколова и других [2,4-7,9] для анализа и решения задач целочисленного программирования, основанный на разбиении допустимой области соответствующей непрерывной задачи. В данной работе рассматривается L- разбиение.
Задача о p-медиане сводится к простейшей задаче размещения (ПЗР). Сводимость не гарантирует сохранения некоторых свойств. Например, многогранник ПЗР - квазицелочисленный, а многогранник задачи о p- медиане в общем случае является только связноцелочисленным (квазицелочисленным при p = 1, n-1, где n - число вершин графа) [1].
В работе [2] доказано, что многогранник ПЗР имеет альтернирующую L-структуру. В данной статье показано, что многогранник задачи о p-медиане также имеет альтернирующую L -структуру.
Рассматривается целочисленная модель задачи о p- медиане:
|
|
(1) |
где n - количество вершин графа; dij - кратчайшее расстояние между i-й и j- й вершинами графа; p- количество размещаемых объектов. Диагональными будем называть элементы вектора x = (x11,x12,...,xnn) с одинаковыми индексами, а медианными - диагональные, принимающие значение 1. Переменная xij = 1, если вершина j"прикреплена" к вершине i. Условия (4) гарантируют прикрепление только к медианным вершинам. Если условия (5) заменить линейными неравенствами
|
|
(2) |
то ограничения (2)-(4),(6) задают многогранник в пространстве размерности n2. Обозначим его через Mp.
Введем определение L-разбиения . Пусть Zk- множество всех k-мерных целочисленных векторов. Тогда L-разбиение непустого множества Rk определим следующим образом:
1) каждая точка zZk образует отдельный класс;
2) нецелочисленные точки x и y эквивалентны, если (x) = (y) и [xi=yi, i =1,...,(x)-1, [x(x)] = [x(x)] , где(x) - номер первой дробной, [a] - наибольшее целое число, не превосходящее a.
В выпуклых множествах с альтернирующим L-разбиением дробныеи целочисленные классы чередуются. В работе [9] предложен критерий альтернируемости L-разбиения:выпуклое замкнутое множество Rk имеет альтернирующее разбиение тогда и только тогда, когда для любого дробного L-класса V существуют целочисленные точки z1,z2 Zk ( называемые окаймляющими) такие, что для любого x V z1j = z2j = xj, j =1,...,(x)-1; z2j = [xj]; j = (x); z1j = ]xj[; j = (x),
где ]a[ - верхняя целая часть числа a. Ясно,
что
знак
лексикографического сравнения.
2. Структура L-разбиения
Исследуем структуру L-разбиения многогранника Mp.
ТЕОРЕМА. Для произвольного упорядочения переменных многогранник Mp имеет альтернирующую L-структуру .
Доказательство. Воспользуемся критерием альтернируемости L-структуры. Возьмем произвольный дробный xMp. Обозначим через произвольную перестановку n2 индексов вектора x, т.е. пар чисел от 1 до n. Тогда (i,j) - номер пары (i,j) в перестановке .Рассмотрим два случая.
1. Пусть первая
дробная в векторе x Mp - диагональная,
т.е. (x) = (i,i) и
Отметим, что qZ, qp, а тогда q+1 p.
Построим вектор z1 Mp Zn2, и
.
Возможны варианты.
1.1. q+1 = p. Для каждого j такого, что найдется kj такой, что 0xkj1 построим множество Jj ={k|xkk = 1}. Покажем, что Jj.
Действительно,
пусть нашелся j, для которого Jj=, тогда
а
так как xkjxkk для любых k и j, имеем
а
из условия
получаем
0 xij1 и тогда iJj, что противоречит
тому, что Jj=.
Вектор z1 строим
следующим образом:
Нетрудно
проверить, что
.
1.2 q+1p. Построим множество JM = {k|xkk = 1}{i}.
Ясно, что |JM|
p, так как
а
0xii1.
Если |JM| p, то, как рассмотрено выше, строим множества Jj и вектор z1.
Если |JM| p тогда строим множества: D = {ki | 0xkk1}, VN = VM = . Выберем произвольно jD, тогда если найдется такое k, что 0xjk1 и xsk = 0 для всех sVN, то полагаем VM=VM{j}, иначе VN=VN{j}. Вычеркиваем j из D и выбираем следующий элемент из D. Процедура построения множеств VN и VM заканчивается, когда D =. Отметим некоторые свойства множеств VN и VM.
Во-первых, | VM
| p-| JM |. Действительно, элемент j
включается в множество VM в том случае,
если найдется такой элемент k, что
0xjk1 и xsk = 0 для всех sVN. Так как
и
xtkxtt, получаем, что
,откуда
.
Учитывая, что
имеем
а
тогда |VM| p - |JM|.
Во-вторых, |VN| (p- |JM|)-|VM|. Это следует из того, что |VN|+|VM| = |D|, а |D| = p - |JM| +1 .
В случае, если |VM| p- |JM|, выбираем произвольно (p-|JM|)- |VM| элементов из множества VN и включаем их в множество VM.
Далее для каждого элемента j, такого, что 0xkj1 kj строим множество Jj = {k |k JMVM }
Покажем, что Jj для каждого рассматриваемого j. Действительно, если найдется j, для которого Jj=, тогда рассмотрим множество Dj = {k | 0xkj1}
Получаем, что
0xkk1 для всех kDj, откуда следует, что
kVN для всех kDj, т.е. DjVN. Отметим, что
элементы множества Dj поочередно
включались в множество VN, тогда перед
рассмотрением последнего элемента rDj
выполнялось условие 0xrj, xsj = 0 для
всех sVN, но тогда rVM и, следовательно,
Jj. Другими словами, не может быть
ситуации, когда все дробные в строке из
множества VN. Вектор z1 строится следующим
образом:
Для того чтобы
закончить рассмотрение случая (x) =
(i,i), необходимо показать, как строится
вектор z2Mp такой, что
.
В этом случае аналогично строятся
множества JM,VN,VM,Jj, Dj с тем изменением,
что построение множества VN начинается
не с пустого множества, а вначале в него
включается элемент {i}. В множество Jj его
не включаем. Так как при доказательстве
условия Jj мы не пользовались тем,
что iJM, оно справедливо и для
рассматриваемого случая. Вектор z2
строится аналогично, как расcмотрено
выше, за исключением того, что z2ii = 0.
2. Рассмотрим случай, когда (x) = (i,t), it. В отличие от рассматриваемого выше случая при построении вектора z1 не надо строить множество Jt, а положить z1it = 1. Если 0 xii1, то i включаем в VM. При построении вектора z2 не включаем i в множество Jt, если таковое будет строиться.
Теорема доказана.
Отметим, что при построении векторов z1 и z2 мы только некоторым образом округляли дробные компоненты, не меняя значения целочисленных компонент.
СЛЕДСТВИЕ. Для любого дробного решения задачи (1)-(5) подходящим округлением дробных компонент можно построить допустимое решение. Причем по крайней мере одну из дробных компонент можно округлять произвольно.
Доказанное свойство альтернируемости может эффективно использоваться при разработке алгоритмов решения задачи о p-медиане, например, как в [7].
Список литературы
Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация. М.: Наука,1981.-344 с.
Заблоцкая О.А. L-разбиение многогранника задачи стандартизации // Моделирование и оптимизация систем сложной структуры. Омск: ОмГУ, 1987. С.151-154.
Забудский Г.Г. Об оценках стоимости связывающей сети в некоторых задачах размещения // Дискретная оптимизация и анализ сложных систем. Новосибирск: ВЦ СО АН СССР, 1989. С. 10 - 25.
Забудский Г.Г. О целочисленной постановке одной задачи размещения объектов на линии // Управляемые системы. Новосибирск, 1990. Т. 30. С.35-45.
Забудский Г.Г. Задачи оптимального размещения взаимосвязанных объектов на линии // Методы решения и анализа задач дискретной оптимизации. Омск: ОмГУ, 1992. С. 5 - 24.
Zabudsky G.G. On the One-Dimensional Space Allocation Problem with Minimal Admissible Distances // Optimization-Based Computer-Aided Modelling and Design.-Prague, Czech Republic: IITA CR. 1995. P. 448-452.
Колоколов А.А., Леванова Т.В. Алгоритмы декомпозиции перебора L-классов для решения некоторых задач размещения // Вест. Омск. ун-та. 1997. N1. С. 21-23.
Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир,1978.-432 с.
Колоколов А.А. Выпуклые множества с альтернирующим L-разбиением // Моделирование и оптимизация систем сложной структуры. Омск: ОмГУ, 1987. С.144-150.
Для подготовки данной применялись материалы сети Интернет из общего доступа