На головну

 Деякі властивості многогранника. Задачі про 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-

© 8ref.com - українські реферати
8ref.com