Г.Г. Забудський. Деякі властивості многогранника ...

1. 1. Постановка завдання і визначення
2. 2. Структура L -разбіенія

Наша команда-партнер Artmisto

Вісник Омського університету, 1998, Вип. 2. С. 11-13.
© Омський державний університет, 1998. УДК 519.8

Г.Г. Забудський

Інститут інформаційних технологій і прикладної математики СО РАН
644099, Омськ, вул. Пєвцова, 13

Отримано 26 червня 1997 р

In this paper we present some results for the p-median problem, the problem of locating p-facilities (medians) on a network. We are proved the alternating of L-structure polyhedron the problem.

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 = (x 11, x 12, ..., xnn) з однаковими індексами, а медіа - діагональні, які беруть значення 1. Змінна xij = 1, якщо вершина j "прикріплена" до вершини i. Умови (4) гарантують прикріплення тільки до медіанного вершин. Якщо умови (5) замінити лінійними нерівностями

(2)

то обмеження (2) - (4), (6) задають багатогранник в просторі розмірності n 2. Позначимо його через Mp.

Введемо визначення L - розбиття. Нехай Zk - безліч всіх k -мірних цілочисельних векторів. Тоді L -разбіеніе непорожньої безлічі WН Rk визначимо наступним чином:

1) кожна точка z Про Zk утворює окремий клас;

2) нецілочисельне точки x і y еквівалентні, якщо j (x) = j (y) і [xi = yi, i = 1, ..., (x) -1, [xj (x)] = [xj (x )], де j (x) - номер першої дробової, [a] - найбільше ціле число, яке не перевищує a.

В опуклих множинах з альтернірующій L -разбіеніем дробниеі цілочисельні класи чергуються. В роботі [9] запропоновано критерій альтерніруемості L -разбіенія: опукле замкнутий безліч WН Rk має альтернуюча розбиття тоді і тільки тоді, коли для будь-якого дрібного L-класу V існують цілочисельні точки z 1, z 2 Про W З Zk (звані оздоблюють) такі, що для будь-якого x Про V
z 1 j = z 2 j = xj, j = 1, ..., j (x) -1;
z 2 j = [xj]; j = j (x);
z 1 j =] xj [; j = j (x),

де] a [- верхня ціла частина числа a. Ясно що знак лексикографічного порівняння.

2. Структура L -разбіенія

Досліджуємо структуру L -разбіенія багатогранника Mp.

ТЕОРЕМА. Для довільного впорядкування змінних багатогранник Mp має альтернуючу L-структуру.

Доказ. Скористаємося критерієм альтерніруемості L -Структури. Візьмемо довільний дробовий x Про Mp. Позначимо через p довільну перестановку n 2 індексів вектора x, тобто пар чисел від 1 до n. Тоді p (i, j) - номер пари (i, j) в перестановці p .Розглянемо два випадки.

1. Нехай перша подрібнена в векторі x + Mp - діагональна, тобто j (x) = (i, i) і
Відзначимо, що q Про Z, q <p, а тоді q +1 Ј p. Побудуємо вектор z 1 + Mp З Zn 2, і . Можливі варіанти.

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 і вектор z 1.

якщо | 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 <1, xsj = 0 для всіх s П VN, але тоді r Про VM і, отже, Jj №Ж. Іншими словами, не може бути ситуації, коли все дробові в рядку з безлічі VN. Вектор z 1 будується наступним чином:

Для того щоб закінчити розгляд випадку j (x) = (i, i), необхідно показати, як будується вектор z 2 Про Mp такий, що . В цьому випадку аналогічно будуються безлічі JM, VN, VM, Jj, Dj з тією зміною, що побудова безлічі VN починається не з порожнього безлічі, а спочатку в нього включається елемент {i}. У безліч Jj його не включаємо. Так як при доказі умови Jj №Ж ми не користувалися тим, що i Про JM, воно справедливо і для розглянутого випадку. Вектор z 2 будується аналогічно, як расcмотрено вище, за винятком того, що z 2 ii = 0.

2. Розглянемо випадок, коли j (x) = (i, t), i № t. На відміну від розглянутого вище випадку при побудові вектора z 1 не треба будувати безліч Jt, а покласти z 1 it = 1. Якщо 0 <xii <1, то i включаємо в VM. При побудові вектора z 2 не включаємо i в безліч Jt, якщо таке буде будуватися.

Теорема доведена.

Відзначимо, що при побудові векторів z 1 і z 2 ми тільки деяким чином округляли дробові компоненти, не змінюючи значення цілочисельних компонент.

СЛІДСТВО. Для будь-якого дрібного рішення задачі (1) - (5) відповідним округленням дрібних компонент можна побудувати допустиме рішення. Причому принаймні одну з дрібних компонент можна округляти довільно.

Доведене властивість альтерніруемості може ефективно використовуватися при розробці алгоритмів розв'язання задачі про p -медіане, наприклад, як в [7] .

література