Категории

  • Голосование
  • Право голоса
  • Киев
  • Украина
  • Здоровье
  • Популярное
  • Новости
  • Новости

      Artmisto
      Наша команда-партнер Artmisto. С "Buddy.Bet" азартные игроки найдут идеальное место для развлечений и возможность выиграть крупные суммы.

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

    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- медіані:

    Розглядається целочисленная модель задачі про 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. Ясно що де] 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) і 1
    Відзначимо, що q Про Z, q <p, а тоді q +1 Ј p. Побудуємо вектор z 1 + Mp З Zn 2, і . Можливі варіанти.

    1.1. q +1 = p. Для кожного j такого, що знайдеться kj такий, що 0 <xkj <1 побудуємо безліч Jj = {k | xkk = 1}. Покажемо, що Jj № Ж.

    Дійсно, нехай знайшовся j, для якого Jj = Ж, тоді Дійсно, нехай знайшовся j, для якого Jj = Ж, тоді   а так як xkj Ј xkk для будь-яких k і j, маємо   а з умови   отримуємо 0 <xij <1 і тоді i Про Jj, що суперечить тому, що Jj = Ж а так як xkj Ј xkk для будь-яких k і j, маємо а з умови отримуємо 0 <xij <1 і тоді i Про Jj, що суперечить тому, що Jj = Ж.

    Вектор z1 будуємо таким чином:
    Вектор z1 будуємо таким чином:

    Неважко перевірити, що Неважко перевірити, що .

    1.2 q +1 <p. Побудуємо безліч JM = {k | xkk = 1} І {i}.

    Ясно, що | JM | Ј p, так як Ясно, що |  JM |  Ј p, так як   а 0 <xii <1 а 0 <xii <1.

    якщо | JM | = P, то, як розглянуто вище, будуємо безлічі Jj і вектор z 1.

    якщо | JM | <P тоді будуємо безлічі: D = {ki | 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. Так як По-перше, |  VM |  Ј p - |  JM | і xtk Ј xtt, отримуємо, що , звідки .

    Враховуючи що Враховуючи що   маємо   а тоді |  VM |  Ј p - |  JM | маємо а тоді | 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 kj будуємо безліч 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 будується наступним чином:
    Отримуємо, що 0 <xkk <1 для всіх k Про Dj, звідки випливає, що k Про VN для всіх k Про Dj, тобто  Dj = VN

    Для того щоб закінчити розгляд випадку j (x) = (i, i), необхідно показати, як будується вектор z 2 Про Mp такий, що Для того щоб закінчити розгляд випадку 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), it. На відміну від розглянутого вище випадку при побудові вектора z 1 не треба будувати безліч Jt, а покласти z 1 it = 1. Якщо 0 <xii <1, то i включаємо в VM. При побудові вектора z 2 не включаємо i в безліч Jt, якщо таке буде будуватися.

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

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

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

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

    література

    [1]Емелічев В.А., Ковальов М.М., Кравцов М.К.Багатогранники, графи, оптимізація.М .: Наука, 1981.-344 с.[2]Заблоцька О.А.L-розбиття багатогранника завдання стандартизації // Моделювання та оптимізація систем складної структури.Омськ: ОмГУ, 1987. С.151-154.[3]Забудський Г.Г.Про оцінках вартості зв'язує мережі в деяких задачах розміщення // Дискретна оптимізація і аналіз складних систем.Новосибірськ: ВЦ СО АН СРСР, 1989. С. 10 - 25.[4]Забудський Г.Г.Про целочисленной постановці однієї задачі розміщення об'єктів на лінії // Керовані системи.Новосибірськ, 1990. Т. 30. С.35-45.[5]Забудський Г.Г.Завдання оптимального розміщення взаємопов'язаних об'єктів на лінії // Методи рішення і аналізу завдань дискретної оптимізації.Омськ: ОмГУ, 1992. С. 5 - 24.[6]Zabudsky GG 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.[7]Дзвонів А.А., Леванова Т.В.Алгоритми декомпозиції перебору L-класів для вирішення деяких завдань розміщення // Вест.Омськ.ун-ту.1997. N1.С. 21-23.[8]Крістофідес Н. Теорія графів.Алгоритмічний підхід.М .: Світ, 1978.-432 с.[9]Дзвонів А.А.Опуклі безлічі з альтернірующій L-розбиттям // Моделювання та оптимізація систем складної структури.Омськ: ОмГУ, 1987. С.144-150.