Учебная работа № 1395. Некоторые свойства многогранника. Задачи о Pмедиане

Учебная работа № 1395. Некоторые свойства многогранника. Задачи о Pмедиане

Г.Г. Забудский, Институт информационных технологий и прикладной математики СО РАН

1. Постановка задачи и определения

Задачи оптимального размещения объектов имеют много практических приложений. Описываются различные постановки таких задач [18]. В данной статье рассматривается известная NPтрудная задача оптимального размещения на графе задача о pмедиане [1,78]. Для ее исследования здесь применяется подход, развиваемый в работах А.А. Колоколова и других [2,47,9] для анализа и решения задач целочисленного программирования, основанный на разбиении допустимой области соответствующей непрерывной задачи. В данной работе рассматривается L разбиение.

Задача о pмедиане сводится к простейшей задаче размещения (ПЗР). Сводимость не гарантирует сохранения некоторых свойств. Например, многогранник ПЗР квазицелочисленный, а многогранник задачи о p медиане в общем случае является только связноцелочисленным (квазицелочисленным при p = 1, n1, где 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. С.151154.

Забудский Г.Г. Об оценках стоимости связывающей сети в некоторых задачах размещения // Дискретная оптимизация и анализ сложных систем. Новосибирск: ВЦ СО АН СССР, 1989. С. 10 25.

Забудский Г.Г. О целочисленной постановке одной задачи размещения объектов на линии // Управляемые системы. Новосибирск, 1990. Т. 30. С.3545.

Забудский Г.Г. Задачи оптимального размещения взаимосвязанных объектов на линии // Методы решения и анализа задач дискретной оптимизации. Омск: ОмГУ, 1992. С. 5 24.

Zabudsky G.G. On the OneDimensional Space Allocation Problem with Minimal Admissible Distances // OptimizationBased ComputerAided Modelling and Design.Prague, Czech Republic: IITA CR. 1995. P. 448452.

Колоколов А.А., Леванова Т.В. Алгоритмы декомпозиции перебора Lклассов для решения некоторых задач размещения // Вест. Омск. унта. 1997. N1. С. 2123.

Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир,1978.432 с.

Колоколов А.А. Выпуклые множества с альтернирующим Lразбиением // Моделирование и оптимизация систем сложной структуры. Омск: ОмГУ, 1987. С.144150.

Учебная работа № 1395. Некоторые свойства многогранника. Задачи о Pмедиане