Некоторые свойства многогранника. Задачи о 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)
каждая точка zZk образует отдельный класс;

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-структуры. Возьмем произвольный
дробный xMp. Обозначим через  произвольную перестановку n2
индексов вектора x, т.е. пар чисел от 1 до n. Тогда (i,j) - номер пары
(i,j) в перестановке  .Рассмотрим два случая.

1.
Пусть первая дробная в векторе x  Mp - диагональная, т.е. (x) =
(i,i) и  Отметим, что qZ, qp, а тогда
q+1 p. Построим вектор z1  Mp Zn2, и .
Возможны варианты.

1.1.
q+1 = p. Для каждого j такого, что найдется kj такой, что 0xkj1
построим множество Jj ={k|xkk = 1}. Покажем, что Jj.

Действительно,
пусть нашелся j, для которого  Jj=,
тогда а так как xkjxkk
для любых k и j, имеем а из условия получаем 0
xij1 и тогда iJj, что противоречит тому, что Jj=.


Вектор
z1 строим следующим образом:

Нетрудно
проверить, что .

1.2
q+1p. Построим множество JM = {k|xkk = 1}{i}.

Ясно,
что |JM| p, так как а 0xii1.


Если
 |JM| p, то, как
рассмотрено выше, строим множества Jj и вектор z1.

Если
 |JM| p тогда строим
множества: D = {ki | 0xkk1},
VN = VM = . Выберем произвольно jD, тогда если найдется такое
k, что 0xjk1 и xsk = 0 для всех sVN, то
полагаем VM=VM{j}, иначе VN=VN{j}. Вычеркиваем j из D и
выбираем следующий элемент из D. Процедура построения множеств VN и VM
заканчивается, когда D =. Отметим некоторые свойства множеств VN и VM.

Во-первых,
| VM |  p-| JM |. Действительно, элемент j включается в множество VM в
том случае, если найдется такой элемент k, что 0xjk1
и xsk = 0 для всех sVN. Так как и xtkxtt,
получаем, что ,откуда .

Учитывая,
что имеем а тогда |VM|
p - |JM|.

Во-вторых,
|VN| (p- |JM|)-|VM|. Это следует из того, что |VN|+|VM| = |D|,
а |D| = p - |JM| +1 .

В
случае, если |VM| p- |JM|, выбираем произвольно (p-|JM|)- |VM|
элементов из множества VN и включаем их в множество VM.

Далее
для каждого элемента j, такого, что 0xkj1 kj
строим множество Jj = {k |k  JMVM }

Покажем,
что Jj для каждого рассматриваемого j. Действительно, если
найдется j, для которого Jj=, тогда рассмотрим множество Dj = {k | 0xkj1}

Получаем,
что 0xkk1 для всех kDj, откуда следует, что kVN
для всех kDj, т.е. DjVN. Отметим, что элементы множества Dj
поочередно включались в множество VN, тогда перед рассмотрением последнего
элемента rDj выполнялось условие 0xrj, xsj = 0
для всех sVN, но тогда rVM и, следовательно, Jj.
Другими словами, не может быть ситуации, когда все дробные в строке из
множества VN. Вектор z1 строится следующим образом:  

Для
того чтобы закончить рассмотрение случая (x) = (i,i), необходимо
показать, как строится вектор z2Mp такой, что . В этом
случае аналогично строятся множества JM,VN,VM,Jj, Dj с тем изменением, что
построение множества VN начинается не с пустого множества, а вначале в него
включается элемент {i}. В множество Jj его не включаем. Так как при
доказательстве условия Jj мы не пользовались тем, что iJM,
оно справедливо и для рассматриваемого случая. Вектор z2 строится аналогично,
как расcмотрено выше, за исключением того, что z2ii = 0.

2.
Рассмотрим случай, когда (x) = (i,t), it. В отличие от
рассматриваемого выше случая при построении вектора z1 не надо строить
множество Jt, а положить z1it = 1. Если 0 xii1, то 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.

Для
подготовки данной работы были использованы материалы с сайта http://www.omsu.omskreg.ru/