ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 5531
Скачиваний: 27
46
ние).
Пусть
N
I
– множество номеров заданий;
M
I
– множество номеров исполнителей;
)
,
(
j
i
t
– затраты на выполнение
j
-го задания
i
-м исполните-
лем;
)
,...,
,
(
2
1
M
r
r
r
r
– разбиение множества
N
I
на
M
подмно-
жеств (подмножества
i
r
не имеют общих элементов,
N
i
M
i
I
r
U
=
=1
,
некоторые
i
r
могут быть равны
∅);
)
,
(
M
N
R
– множество всех разбиений указанного типа. Про-
иллюстрируем понятие
)
,
(
M
N
R
. Пусть
3
,
5
=
= M
N
. Тогда
одним из элементов
)
,
(
M
N
R
является
),
4
,
3
,
1
(
),
5
,
2
{(
=
′
r
∅}.
Т.е. имеются три исполнителя и пять заданий. Первому исполните-
лю назначаются задания с номерами 2, 5, второму с номерами 1, 3,
4, третьему задания не назначаются. Множество
)
,
(
M
N
R
есть
множество возможных решений задачи.
Задачи этого типа допускают два критерия оптимальности:
1)
критерий наибольшей суммарной эффективности;
2)
критерий равномерной загрузки исполнителей.
Соответствующие целевые функции
∑
∑
∈
∈
=
i
M
r
j
i
i
j
i
t
r
F
),
,
(
)
(
1
(6)
∑
∈
∈
=
i
M
r
j
I
i
j
i
t
r
F
).
,
(
max
)
(
2
(7)
Функция
)
(
1
r
F
определяет для заданного распределения
r
суммарные затраты (например, временные) на выполнение всех за-
даний. Функция
)
(
2
r
F
определяет для заданного
r
максимальную
загрузку исполнителей.
Таким образом, задача распределения заданий по критерию
47
минимума общих затрат сводится к минимизации функции
)
(
1
r
F
на множестве
)
,
(
M
N
R
. Та же задача, но с критерием максималь-
но равномерной загрузки исполнителей сводится к минимизации
функции
)
(
2
r
F
на множестве
)
,
(
M
N
R
.
В задачах распределения заданий могут присутствовать ог-
раничения, делающие неприемлемыми некоторые из возможных
решений. Те из возможных решений, которые удовлетворяют огра-
ничениям, называются допустимыми. Ограничения в задачах рас-
пределения заданий обычно носят ресурсный характер. Это означа-
ет, что на выполнение любого задания каждый исполнитель затра-
чивает некоторое количество ресурса определенного типа (время,
фонд заработной платы, количество людей, станков и т.д.). По-
скольку суммарное количество ресурса всякого типа ограничено, не
всякое разбиение является допустимым.
Формализуем ограничения:
)
,
,
(
k
j
i
S
– количество ресурса
k
-го типа, используемое
i
-м
исполнителем
для
выполнения
j
-го
задания
});
,...,
2
,
1
{
,
,
(
K
k
I
j
I
i
N
M
=
∈
∈
)
,
(
2
k
i
S
– наличное количество этого ресурса у
i
-го ис-
полнителя;
)
,
(
1
k
i
S
– обязательный уровень его использования. Тогда
для допустимого разбиения
r
должно выполняться соотношение
∑
∈
∈
∈
≤
≤
i
r
j
k
M
I
k
I
i
k
i
S
k
j
i
S
k
i
S
.
,
),
,
(
)
,
,
(
)
,
(
2
1
(8)
Формальная постановка задач распределения заданий.
Минимизировать функции
)
(
1
r
F
или
)
(
2
r
F
на множестве
)
,
(
M
N
R
при ограничениях (8).
В задачах этого типа впервые появилось понятие множества
допустимых решений, широко используемое в математическом про-
граммировании. Таким образом, в оптимизационных комбинатор-
ных задачах оперируют с тремя вложенными друг в друга множест-
вами: множеством возможных решений, множеством допустимых
решений, множеством оптимальных решений.
48
3.1.4
Задача
о
назначениях
Задача о назначениях является частным случаем задачи распре-
деления заданий при следующих условиях:
1
)
1
,
,
(
)
1
,
(
)
1
,
(
,
1
,
2
1
=
=
=
=
=
j
i
S
i
S
i
S
K
M
N
Она состоит, таким образом, в назначении каждому исполните-
лю ровно одного задания. Поэтому возможна постановка этой зада-
чи
на
множестве
перестановок
N
Π
∈
π
,
в
которой
)
(
M
j
I
j
i
∈
=
π
.
Функции
)
(
)
(
2
1
r
uF
r
F
для множества
N
Π
легко пересчиты-
ваются в функции
∑
∈
=
N
I
j
j
j
F
),
,
(
(
)
3
π
π
)}.
,
(
{
max
(
)
4
j
t
F
j
I
j
N
π
π
∈
=
Таким образом, задача назначения состоит в выборе в матрице
ij
t
размера
N
N
×
по одному элементу в каждой строке и столб-
це так, чтобы сумма выбранных элементов (функция
))
(
3
π
F
или
максимальный из них (функция
))
(
4
π
F
были минимальными.
3.2
Основные
понятия
и
операции
комбинаторики
Переходя непосредственно к изучению основ комбинаторного
анализа, выделим в комбинаторных исследованиях два основных
вида операций:
1)
отбор подмножеств;
2)
упорядочение элементов.
С первой операцией связано понятие выборки. При этом под
выборкой понимают как осуществление операции отбора, так и ее
результат – само выбранное подмножество. Поэтому если из множе-
ства
A
, состоящего из
n
элементов, выбрано
r
− подмножество,
то будем называть его
r
-выборкой, где
r
− объем выборки.
49
Если
r
-выборки рассматриваются с учетом порядка элементов
в них, то они называются
r
-перестановками. Если этот порядок не
принимается во внимание, то соответствующие выборки называются
r
-сочетаниями.
Пополним полученные ранее знания о множествах следующи-
ми логическими правилами.
Правило суммы. Если из множества
S
подмножества
A
можно выбрать
m
способами, а подмножество
B
, отличное от
A
,
n
способами и при этом выборы
A
и
B
таковы, что взаимно ис-
ключают друг друга и не могут быть получены одновременно, то
выбор из
S
множества
B
A ∪
можно осуществить
n
m
+
спосо-
бами.
Это правило можно сформулировать в терминах теории мно-
жеств следующим образом. Если даны
m
- множество
P
и
n
-
множество
Q
(элементами их являются в нашем случае выбранные
подмножества), то при
∅
=
Q
P ∩
Q
P ∪
будет (
)
(
n
m
+
- мно-
жеством.
Обобщенное правило суммы. Если дано разбиение множества
M
,
...
2
1
r
T
T
T
M
∪
∪
∪
=
где
,
,...,
2
,
1
,
,
r
j
j
i
T
T
j
i
=
≠
∅
=
∩
и если
i
T
есть
i
n
- мно-
жество
)
,...,
2
,
1
(
r
i
=
, то множество
M
есть
)
(
1
∑
=
r
i
i
n
- множество.
Правило произведения. Если из множества
S
подмножество
A
может быть выбрано
m
способами, а после каждого такого вы-
бора можно
n
способами выбрать подмножество
B
, то выбор
A
и
B
в указанном порядке можно осуществить
n
m
×
способами.
В терминах теории множеств это правило соответствует прави-
лу декартова произведения множеств: если
P
является
m
- множе-
ством, а
Q
есть
n
-множество, то
Q
P
×
окажется
)
(
n
m
⋅
- мно-
жеством.
Обобщенное правило произведения. Пусть
i
T
есть
i
n
-
50
множество
)
,...,
1
(
r
i
=
.
Построим
множества
1
1
T
M
=
,
2
1
2
T
M
M
×
=
(оно
будет
)
(
2
1
n
n
-
множеством),
r
r
r
T
M
M
T
M
M
×
=
=
−1
3
2
3
,...,
. Тогда
r
M
будет (
)
...
2
1
r
n
n
n
-
множеством.
В комбинаторном анализе будем рассматривать множества
всюду упорядоченные, т.е. такие, для любой пары которых можно
установить отношение порядка.
3.3
Выборки
и
упорядочения
Пусть имеется
n
-
множество
A
.
Две
r
-выборки
)
,...,
,
(
2
1
r
a
a
a
a
=
и
)
,...
,
(
2
1
r
b
b
b
b
=
называются упорядочен-
ными, если
b
a
=
лишь при условии, что
,
,...,
2
,
1
,
r
i
b
a
i
i
=
=
и
неупорядоченными, если
b
a
=
лишь при условии, что каждое
i
a
равно некоторому
.
,...,
2
,
1
,
r
j
b
j
=
Уточним, исходя из этого, неко-
торые определения.
Упорядоченные
r
-выборки из
n
-множества
A
называются
r
- перестановками, если все
r
элементов различны, и
r
-
перестановками с повторениями, если среди
r
элементов имеются
одинаковые (равные).
Неупорядоченные
r
-выборки множества
A
называются
r
-
сочетаниями, если все
r
элементов различны, и
r
-сочетаниями с
повторениями, при наличии одинаковых элементов.
Так, например, две выборки (2,3,4,6,1,1) и (1,3,4,1,6,2) из мно-
жества (1,2,3,4,5) являются одинаковыми 6 – сочетаниями с повто-
рениями и разными 6 – перестановками с повторениями.
Очевидно, что задача выделения
r
-выборки не имеет в общем
случае единственного решения. Поэтому подсчет числа
r
-выборок
заданного типа из
n
-множеств исторически явился одной из первых
задач комбинаторики.
Найдем число всех возможных
r
-перестановок (без повто-
рений) из
n
-множеств. Обозначим это число через
)
,
(
r
n
P
. Будем
рассуждать следующим образом. В
n
-множестве имеется
n
воз-
можностей для выбора первого элемента перестановки. Как только