Информационный сайт

 

Реклама
bulletinsite.net -> Книги на сайте -> Программисту -> Сигал И.Х. -> "Введение в прикладное дискретное программирование " -> 25

Введение в прикладное дискретное программирование - Сигал И.Х.

Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование — М.: ФИЗМАТЛИТ, 2003. — 240 c.
ISBN 5-9221-0377-6
Скачать (прямая ссылка): vvedenievprikladnoeprogrammirovanie2003.djvu
Предыдущая << 1 .. 19 20 21 22 23 24 < 25 > 26 27 28 29 30 31 .. 84 >> Следующая


Определение. Реберная раскраска называется правильной, если любые два смежных ребра имеют разные цвета. Реберная раскраска с минимальным числом цветов называется минимальной.

Из этого определения следует, что минимальное число цветов в правильной реберной раскраске оценивается снизу степенью графа, т.е. максимальной степенью вершин.

Минимальное число цветов >c(G) в правильной реберной раскраске называется хроматическим классом графа. Пусть d(G) = maxdf, di — степень вершины і Є I. Для графа без петель и кратных дуг верна оценка (см. [9])

d(G) < h[G) < d(G) + I.

Сформулируем задачу на языке целочисленного программирования. Пусть Xij — номер цвета, в который окрашено ребро (i,j) Є U. Тогда

(Xij -2?)2 > I, (i,j) є U, (i,k) Є U, к фу, (2.3.26)

I < Xij < то, (i,j) Є U, (2.3.27)

max хц —у min. (2.3.28)

Ы)еи

Модель описывается соотношениями (2.3.26)-(2.3.28).
Гл. 2. Модели дискретного программирования

71

2.4. Задача о покрытии конечного множества системой его подмножеств

Пусть имеется конечное множество S = (сгі, 02, ..., сгш) и система его подмножеств Sj С S, j = 1,2,..., гг,

п

U Si =

J=I

Требуется найти минимальный по числу подмножеств набор Sj, такой, что каждый элемент множества S принадлежит хотя бы одному из подмножеств этого набора.

Введем матрицу А = (а^)тхп следующим образом:

{1, если а і Є Sj,

О, если а і ?. Sj.

Предполагается, что каждый элемент а і входит хотя бы в одно

п

из подмножеств Sj, т.е. aij > 1 Для всех г = 1,2,...,ш; если

п

^2 aij = 0 хотя бы для одного значения г, то задача не имеет решения. Введем булевы переменные Xj, j = 1,2,..., гг:

{1, если Sj входит в покрытие, ( ,

г\ п [2 Ал)

(J, если Dj не входит в покрытие.

Тогда целевая функция имеет вид

п

Xj —min, (2.4.2)

J=і

а условия принадлежности каждого элемента Gi из S хотя бы одному из Sj запишутся в виде

п

aijXj > 1, г = 1,2,..., т. (2.4.3)

J=і

Можно рассмотреть задачу о взвешенном покрытии, если каждому из множеств Sj поставить в соответствие вес Cj >0, тогда целевая функция будет иметь вид

п

CjXj —min. (2.4.2')

J=і

Модель описывается соотношениями (2.4.1)-(2.4.3) или соотношениями (2.4.1), (2.4.2') и (2.4.3).

Рассмотрим пример. Пусть

?=(01,02,03,04,05), ?1 — (01, 02), ?2 = (01, 03)5 S3 = (01,04),

?4 = (01,05), ?5 = (02, 03), *5б = (0'2, 0'4), *57 = (сг2, CT5),
72 Разд. I. Предмет и модели дискретного программирования

Sg — (СГ3,СГ4), ft — (сг3, CT5), ft0 — (сг4,сг5).

Здесь т = 5, п = 10. Составим матрицу Л:

л & ft ft ft ft ft ft ft Sio

(Tl

(T2

cr 3

(T 5

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

В каждой строке матрицы А содержится хотя бы одна единица, поэтому задача имеет решение.

Оптимальное покрытие образуют наборы множеств (Si, Sg, Sw), (S2, ft, Si0), (S3, S&, S10) и другие; число подмножеств в оптимальном покрытии равно трем. Среди приведенных наборов нет ни одного такого, чтобы в нем были лишь попарно непересекаюгциеся подмножества.

В задаче о разбиении конечного множества на попарно непересе-кающиеся его подмножества предполагается, что каждый элемент а і принадлежит лишь одному из подмножеств Sj, входящих в разбиение. В этом случае целевая функция совпадает с целевой функцией задачи

о покрытии, а ограничения имеют вид

(2.4.5)

j=i

В этой задаче

(2.4.6)

_ J 1, если Sj входит в разбиение,

3 I 0, если Sj не входит в разбиение.

Очевидно, что решение задачи о разбиении является так же решением задачи о покрытии, но обратное, вообще говоря, неверно. Задача о разбиении может не иметь решения при разрешимой задаче о покрытии.

В рассмотренном примере задача о разбиении неразрешима. Если положить Sio — (crS)5 то задача разбиения имеет несколько решений; приведем некоторые из них:

(Si, Sg, Sio), (S3, Sb, Si о), (S2, S6, Sio).

Вместе с множеством Sio решение образует любая пара непересекаю-щихся множеств Sj и Sk таких, что

Sj U Sk = (01, CT2, CT3, СГ4) .

Это такие пары: (Si, Sg), (S3, ft), (ft, ft). Других оптимальных (и допустимых) решений нет. Все допустимые решения оптимальны.

Задача о разбиении часто встречается при решении различных задач дискретной оптимизации. В гл. 10 она используется при решении симметричной задачи коммивояжера с большим числом городов.
РАЗДЕЛ II

КОМБИНАТОРНЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ

Раздел II содержит изложение комбинаторных методов для решения задач дискретного программирования; здесь рассмотрены два метода: метод ветвей и границ и метод динамического программирования. Каждый из этих методов реализует высказанную ранее идею нахождения подмножеств, не содержащих оптимальных решений. В методе ветвей и границ эта идея основана на применении оценок для подмножеств, в методе динамического программирования — на принципе оптимальности Веллмана.

Метод ветвей и границ изложен в главе 3. После рассмотрения схемы для общей задачи дискретного программирования рассматривается применение этой схемы для разработки алгоритмов решения задач различных типов.
Предыдущая << 1 .. 19 20 21 22 23 24 < 25 > 26 27 28 29 30 31 .. 84 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100