ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 5523
Скачиваний: 27
71
,
1
j
S
2
i
b
для
1
2
,...,
−
im
j
b
S
для
1
−
jm
S
. Элемент
im
b
в результате
этой замены освобождается для выбора в качестве представителя
r
S
. Итак,
r
S
S ,...
1
имеют различных представителей и мы можем
следовать тем же путем, чтобы либо дойти до
n
S
и получить пол-
ную СРП, либо встретить случай 2) и установить несуществование
СРП.
Заключение о числе СРП получается из приведенного алго-
ритма как следствие. Действительно, если СРП существует, то су-
ществует и некоторое множество, каждый элемент которого может
быть выбран в качестве его представителя в СРП. Следовательно,
если множества данного семейства
n
элементов имеют
t
или более
элементов, то существует по меньшей мере
!
t
СРП, если
n
t
<
и
),
1
)...(
1
(
+
−
−
n
t
t
t
если
n
t
≥
. Выбор первого представителя
может быть осуществлен по крайней мере
t
способами; вычеркнув
этот элемент из всех других множеств, получим систему множеств в
,
,...,
*
*
2
m
S
S
наименьшее из которых содержит не менее
1
−
t
эле-
ментов. Продолжая процесс далее, получим указанный результат.
Замечание. Условие конечности важно, так как для беско-
нечной системы множеств, например,
.
.
.
.
.
.
.
.
.
.
.
.
.
};
{
.
.
.
.
.
.
.
.
.
.
.
.
.
};
1
{
,...};
,...,
3
,
2
,
1
{
1
0
k
S
S
k
S
k
=
=
=
нет СРП, хотя она есть для любой ее части.
Существуют и другие системы представителей множеств. За-
дачи о разбиении множеств привели к понятию системы общих
представителей множеств. Пусть даны два различных разбиения
одного и того же множества
S
на
k
непустых составляющих:
k
k
B
B
B
S
A
A
A
S
∪
∪
∪
=
∪
∪
∪
=
...
;
...
2
1
2
1
Если существует подмножество
O
множества
S
, состоящее
из
k
элементов и такое, что его пересечение с любым из состав-
72
ляющих не пусто:
≠
∩
i
A
O
∅;
≠
∩
i
B
O
∅,
,
,...,
2
,
1
k
i
=
то оно называется
системой общих представителей
(СОП) дан-
ных разбиений. При этом каждое пересечение оказывается состоя-
щим только из одного элемента.
При необходимости, попарно взятые множества первого и
второго разбиений можно подобрать так, чтобы они имели только
один общий элемент, являющийся их общим представителем. Мож-
но ставить и другие условия: существование заданного числа общих
элементов, заданного множества их и т.д.
Понятия о представителях множеств и о системах представи-
телей находит в математике многочисленные и разнообразные при-
ложения, например, это представители классов эквивалентности.
Метод систем представителей встречается также в теории сетей при
исследовании допустимости потоков и в теории расширения латин-
ских квадратов.
3.8
Общая
модель
и
основные
способы
описания
задач
комбинаторного
программирования
Задачи комбинаторного программирования, или оптимизаци-
онные задачи комбинаторного анализа, весьма разнообразны не
только по приложениям, но и по используемым средствам матема-
тического описания. При формализации задач используются самые
разнородные математические объекты: перестановки, графы, раз-
биения, целочисленные векторы. Тем не менее, представляется по-
лезным дать общую формулировку задач комбинаторного програм-
мирования. Такая модель, во-первых, дает стандартный способ опи-
сания задач соответствующего класса, а во-вторых, предоставляет
возможность разработки общих методов решения таких задач.
Постановка общей задачи комбинаторного программирова-
ния может быть более или менее детализированной. Приведем наи-
менее «подробную» постановку.
Модель 1.
На конечном множестве
N
-мерного пространст-
ва
0
X
максимизировать функцию
)
(
0
x
f
при ограничении
73
,
,
0
)
(
M
i
I
i
x
f
∈
≤
где
})
,...,
1
,
0
{
)(
(
M
I
i
x
f
M
i
=
∈
- заданные действительные
функции
N
переменных
)
,...,
,
(
2
1
n
x
x
x
, составляющих вектор
x
.
Эта модель пригодна для рассмотрения многих задач комби-
наторного программирования, но слабо отражает их специфику.
Прежде чем перейти к более детализированной модели, выделим
основные элементы задач комбинаторного программирования.
Исходные объекты. В любой задаче комбинаторного про-
граммирования присутствуют некоторые объекты (элементы), кото-
рые нужно упорядочить, разместить, разбить на группы (задания и
детали – в задаче о заданиях и задаче о деталях; задания, распреде-
ляемые по исполнителям – в задаче распределения и т.д.).
Множество возможных решений. В задачах комбинаторно-
го программирования обычно ищется наилучшая в некотором смыс-
ле выборка определенного типа из исходных объектов. Обычно чис-
ло таких выборок сравнительно велико. Множество
0
Λ
всех таких
выборок (элемент его –
λ
) и называется множеством возможных
решений. В рассмотренных в п.3.1 задачах в качестве
0
Λ
и
λ
вы-
ступали: перестановка
π
из элементов множества
N
I
и множество
N
Π
всех таких перестановок (задача о заданиях, задача о деталях,
задача размещения); разбиение
)
,...
,
(
2
1
M
r
r
r
r
=
множества
M
I
на
M
подможеств (задача распределения) и т.д.
Исходный массив. Исходные объекты характеризуются не-
которыми численными данными, которые для объектов и их комби-
наций образуют исходный массив
A
. Так, в задаче о заданиях ис-
ходный массив
A
составляют: время выполнения заданий
),
( j
τ
директивные сроки
),
( j
T
штрафы
)
( j
a
. В задаче о деталях
массив
A
− это время обработки
)
,
( j
i
τ
и т.д. Исходный массив
может иметь любую структуру и состоять из подмассивов любой
мерности.
Целевая функция и ограничения. Значения целевой функ-
ции
0
f
и функций
)
(
M
i
I
i
f
∈
, задающих ограничения, однозначно
74
определяются возможными решениями
λ
. Поэтому модель 1 мож-
но переформулировать, заменив множество
0
X
на
0
Λ
, а зависи-
мость
)
(x
f
i
− на
).
)(
(
M
i
I
i
f
∈
λ
Для большей детализации рас-
кроем характер зависимости
).
(
λ
i
f
Аргументом функции
i
f
явля-
ется некоторый массив
.
A
X
i
⊂
Каким образом и какие именно
элементы исходного массива
A
заполняют массив
i
X
, определяет-
ся возможным решением
λ
.
Будем задавать заполнение массивов
i
X
элементами исход-
ного массива
A
с помощью выборки
)
(
λ
β
i
(эта выборка содержит
коды элементов массива
A
, совпадающие с кодами соответствую-
щих элементов массива
i
X
при данном
λ
). Обозначим через
)
(
λ
β
i
A
массив, получающийся заменой в выборке
)
(
λ
β
i
кодов
элементов массива
A
самими элементами, тогда для каждого
λ
.
],
[
)
(
,
)
(
)
(
M
i
i
i
i
i
i
I
i
A
f
X
f
A
X
∈
=
=
λ
β
λ
β
Рассмотрим в качестве примера задания выборок
)
(
λ
β
i
од-
ну из задач распределения заданий. Здесь
)
,
( j
i
t
- время, затра-
чиваемое
i
-м исполнителем на выполнение
j
-го задания.
Предположим, что используется ресурс только одного вида
),
1
(
=
K
причем он также имеет смысл затрачиваемого времени
)
1
,
(
2
i
S
(величины
)
1
,
(
1
i
S
равны нулю). Эта частная задача при
критерии минимального суммарного затраченного времени форму-
лируется следующим образом.
На множестве
)
,
(
M
N
R
минимизировать функцию
∑
∑
∈
∈
=
i
M
r
j
I
i
j
i
t
r
F
)
,
(
)
(
1
при ограничениях
∑
∈
∈
≤
i
r
j
M
I
i
i
S
j
i
t
.
),
1
,
(
)
,
(
2
75
Исходный массив
A
составляют величины
)
,
( j
i
t
и
).
1
,
(
2
i
S
Поэтому
A
есть матрица размерности
),
2
(
+
× N
M
первые
N
столбцов которой совпадают с матрицей
)
1
(
)],
,
(
[
+
N
j
i
t
-й стол-
бец в
i
-й строке содержит элемент
)
2
(
),
1
,
(
2
+
N
i
S
-й столбец вве-
ден для удобства и состоит из нулей.
Массив
0
X
будем считать одномерным массивом длины
N
с
элементами
j
x
0
. Массивы
)
(
M
i
I
i
X
∈
примем одномерными мас-
сивами длины
1
+
N
с элементами
ij
x
. Соответствующий вид име-
ют и выборки
)
(r
i
β
(возможными решениями в рассматриваемой
задаче являются разбиения
r
). Элементы
)
(r
ik
β
этих выборок
равны:
,
),
(
)
(
M
k
ok
I
k
k
i
r
∈
=
β
,
,
,
1
,
,
)
1
,
(
)
2
,
(
)
(
)
(
N
k
N
k
N
k
i
i
i
i
если
если
если
N
i
N
i
k
i
r
k
k
k
ik
≤
≤
+
=
≠
=
⎪
⎩
⎪
⎨
⎧
+
+
=
β
где
k
N
M
i
I
k
I
i
,
,
1
+
∈
∈
- номер того подмножества
i
r
в раз-
биении
r
, которое заключает элемент
k
. При заданной структуре и
составе массива
A
, структуре массивов
i
X
и выборок
)
(r
i
β
функции
)
(
i
X
fi
имеют вид
∑
∑
∈
∈
+
−
=
=
M
N
I
i
I
j
N
i
ij
i
i
oi
x
x
X
f
x
X
f
1
,
0
0
)
(
,
)
(
.
Теперь сформулируем общую задачу комбинаторного про-
граммирования, учитывая характер зависимостей
)
(
λ
i
f
.
Модель 2.
На множестве
0
Λ
максимизировать функцию
]
[
)
(
0
0
λ
β
A
f
при ограничениях
.
,
0
]
[
)
(
M
i
i
I
i
A
f
∈
≤
λ
β
Модели 1 и 2 имеют сходную структуру, но модель 2 лучше
отражает специфику комбинаторных задач. Она, кроме того, ис-