Зенкевич Н.А. Практикум по исследованию операций
Подождите немного. Документ загружается.
2.6. ЗАДАЧА О НАЗНАЧЕНИЯХ 71
Если после выполнения п.1 и п.2 не получено допустимое решение, необходимо
выполнить следующие действия:
(a) В последней матрице проводится минимальное число горизонтальных и вер-
тикальных прямых по строкам и столбцам, чтобы вычеркнуть все нулевые
элементы.
(b) Находится минимальный невычеркнутый элемент и вычитается из всех осталь-
ных невычеркнутых элементов и прибавляется ко всем элементам, стоящим на
пересечении проведенных в предыдущем пункте прямых.
(c) Если новое распределение нулевых элементов не позволяет построить допу-
стимое решение, повторяют п.2.(а). В противном случае переходят к п.3.
3. Оптимальным назначениям будут соответствовать нулевые элементы, полученные
в п.2.
Пример 2.6.1.
На предприятии имеется m заказов на рекламу и и у него есть n предложений от
рекламных агенств. Размещение рекламного заказа i = 1, 2, . . . , m в рекламном агенстве
j = 1, 2, . . . , n связана с затратами c
ij
. Задача состоит в таком распределении заказов по
между рекламными агенствами, которое соответствуем минимуму суммарных затрат.
Задача о назначениях задана матрицей производительностей A:
8 11 13 10
16 14 17 16
11 12 18 14
15 14 15 12
Необходимо распределить четыре рекламных заказа по четырем агенствам, (по стро-
кам заданы заказы, по столбцам – агенства).
В каждой строке выбираем минимальный элемент и вычитаем его из всех элементов
строки.
8 11 13 10 8
16 14 17 16 14
11 12 18 14 11
15 14 15 12 12
72 Глава 2. ЗАДАЧИ ТРАНСПОРТНОГО ТИПА
Получаем новую таблицу:
0 3 5 2
2 0 3 2
0 1 7 3
3 2 3 0
Теперь выбираем наименьший элемент в каждом столбце и вычитаем его из всех
элементов столбца.
0 3 5 2
2 0 3 2
0 1 7 3
3 2 3 0
0 0 3 0
Получаем следующую таблицу:
0 3 2 2
2 0 0 2
0 1 4 3
3 2 0 0
Если бы на месте элемента a
12
стоял бы 0, то мы бы получили оптимальную таблицу
(назначение), которое проводится по нулевым элементам таблицы.
В нашем случае назначение невозмож но. Для получения нового варианта назначения
необходимо пересчитать таблицу. Для этого минимальным числом линий вычеркиваем
нулевые элементы таблицы. В результате получаем таблицу:
0 3 2 2
2 0 0 2
0 1 4 3
3 2 0 0
После того как вычеркнули все нулевые элементов, в этой таблице найдем наимень-
ший элемент из невычеркнутых. В нашем случае это a
32
= 1. Вычитаем этот элемент из
каждого невычеркнутого элемента и прибавляем ко всем элементам, стоящим на пере-
сечении приводящих прямых.
В результате получаем таблицу, кружками обведены назначенные работы:
2.6. ЗАДАЧА О НАЗНАЧЕНИЯХ 73
0 2 1 1
3 0 0 2
0 0 3 2
4 2 0 0
±°
²¯
±°
²¯
±°
²¯
±°
²¯
После того как провели назначение можем подсчитать суммарные затраты. Для этого
надо в исходной таблице найти элементы, соответствующие нулевым значениям в послед-
ней таблице и сложить их, в нашем случае это a
11
+ a
32
+ a
23
+ a
44
= 8 + 12 + 17 + 12 = 49.
Если наначение провести не удается, то опять проводятся прямые, вычеркиваются
нули и т.д. В некоторых случаях назначение может быть найдено сразу после приведения
таблицы.
2.6.8 Задачи для самостоятельного решения
2.6.1 2.6.2. 2.6.3.
0 4 4 5 6
5 13 6 10 13
11 5 8 12 4
10 9 7 11 8
12 6 9 8 5
4 5 6 7 8
10 19 8 16 5
5 11 12 9 7
3 4 5 2 1
7 6 9 10 12
5 1 4 2 10
4 5 10 4 5
15 12 14 15 4
4 8 9 10 12
5 4 7 8 9
2.6.4 2.6.5 2.6.6
5 5 7 6 3
4 9 13 8 10
11 6 10 11 5
6 21 3 8 9
13 12 4 18 16
5 4 3 4 2
8 3 9 6 8
5 6 9 8 7
4 2 3 5 6
9 8 6 9 5
18 4 6 7 8
13 5 12 13 5
10 13 14 17 3
5 6 5 6 4
19 20 10 7 8
74 Глава 2. ЗАДАЧИ ТРАНСПОРТНОГО ТИПА
Глава 3
Сети
3.1 Задача о максимальном потоке
3.1.1 Основные определения
Определение сети.
Определение 3.1.1 Пусть N = {x} – конечное множество узлов сети (|N| = n).
Целочисленная функция u : N × N −→ R
1
+
называется пропускной способностью сети.
Здесь u(x, y) ≥ 0 – пропускная способность ребра (x, y).
Обозначим через Γ = hN, ui сеть с функцией пропускной способности u. Заметим,
что сеть Γ = hN, ui определяет граф
Γ = hN, Gi, где G = {(x, y)|u(x, y) > 0} – множе-
ство ребер графа Γ.
Если u(x, y) = 0, то (x, y) /∈ G, т. е. ребро (x, y) в сети Γ = hN, ui отсутствует.
Определение потока.
Определение 3.1.2 Целочисленная функция f : N ×N −→ R
1
+
, определенная на (x, y) ∈
N × N, называется потоком в сети Γ, если она удовлетворяет двум свойствам:
• кососимметричность потока: f(x, y) = −f (x, y) для любой пары
(x, y) ∈ N × N.
• допустимость потока: f(x, y) ≤ u(x, y) для любой пары (x, y) ∈ N × N.
75
76 Глава 3. СЕТИ
Замечание. В задаче мы предполагаем, что пропускная способность u и поток f
принимают только целочисленные значения.
Функций от множеств
Введем обозначения:
g(A) =
P
x∈A
g(x) для множества A ⊂ N,
h(A, B) =
P
x∈A
P
y∈B
h(x, y) для множеств A, B, ⊂ N.
Свойства функций множеств
• если A
T
B = ∅, то g(A
S
B) = g(A) + g(B)
• если A
T
B = ∅, то h(A
S
B, C) = h(A, C) + h(B, C)
• если C
T
B = ∅, то h(A, B
S
C) = h(A, B) + h(A, C)
Свойства потока на множествах узлов
• f(A, A) = 0 для любого A ⊂ N
• f(A, B) ≤ u(A, B) для любых A, B ⊂ N.
Понятие истока и стока сети. Предположение единственности.
Определение 3.1.3 Узел s ∈ N называется истоком сети Γ = hN, ui, если для любого
нетривиального потока f выполнено: f(s, N) =
P
x∈N
f(s, x) > 0.
Определение 3.1.4 Узел s
′
∈ N называется стоком сети Γ = hN, ui,если для любого
нетривиального потока f выполнено: f(s
′
, N) =
P
x∈N
f(s
′
, x) < 0.
Будем предполагать, что в сети Γ = hN, ui имеется единственный исток и единствен-
ный сток (т.е. любой поток в сети вытекает из истока и втекает в сток). Тогда для всех
x 6= s, x 6= s
′
выполнено: f(x, N) = 0. Поэтому узлы x, такие что x 6= s, x 6= s
′
, называются
промежуточными узлами.
Понятия мощности потока и максимальный поток.
Определение 3.1.5 Величина f(s, N) = f(N, s
′
) называется мощностью потока f.
Поток f
max
максимальной мощности в сети Γ = hN, ui называется максимальным
потоком.
3.1. ЗАДАЧА О МАКСИМАЛЬНОМ ПОТОКЕ 77
Понятия сечения сети, пропускной способности сечения и минимального
сечения.
Определение 3.1.6 Пара множеств (S, S
′
), S ⊂ N, S
′
⊂ N называется сечением
сети, если выполнено s ∈ S, s
′
∈ S
′
, S
S
S
′
= N, S
T
S
′
= ∅.
Пусть (S, S
′
), S ⊂ N, S
′
⊂ N – сечение сети. Тогда число u(S, S
′
) =
P
x∈S
P
y∈S
′
u(x, y)-
называется пропускной способностью сечения.
Сечение (
S, S
′
) с минимальной пропускной способностью называется минимальным
сечением.
3.1.2 Постановка задачи. Свойства.
Прямая задача (о максимальном потоке).
В сети Γ = hN, ui построить максимальный поток (поток максимальной мощности) и
найти мощность этого потока.
Двойственная задача (о минимальном сечении).
В сети Γ = hN, ui найти минимальное сечение (сечение с минимальной пропускной
способностью) и вычислить пропускную способность этого сечения.
f(s, N) ≤ u(S, S
′
).
Теорема о максимальном потоке и минимальном сечении (аналог теоремы
двойственности).
Теорема 3.1.1 В произвольной сети Γ = hN, ui существует максимальный поток
f :
N × N −→ R
1
и минимальное сечение (S, S
′
), S ⊂ N, S
′
⊂ N при этом мощность
максимального потока совпадает с пропускной способностью минимального сечения,
т.е.
f(s, N) = u(S, S
′
).
Замечание. Доказательство теоремы конструктивно и из него следует алгоритм ре-
шения задачи.
78 Глава 3. СЕТИ
3.1.3 Алгоритм нахождения максимального потока в сети.
Понятие пути, ненасыщенного потоком.
Определение 3.1.7 Пусть
f : N ×N −→ R
1
поток в сети Γ = hN, ui. Будем говорить,
что ребро (x, y) ∈ G, ненасыщено потоком, если u(x, y) > f(x, y)
Путем P (s, s
′
) из истока S в сток S
′
будем называть последовательность ребер
вида: P (s, s
′
) = {(s, x
1
), (x
1
, x
2
), . . . , (x
n
, s
′
)}
Будем говорить, что путь P (s, s
′
) ненасыщен относительно потока f, если каждое
ребро пути P (s, s
′
) не насыщено относительно потока, т.е. u(x, y) > f(x, y), ∀(x, y) ∈ P.
Вычислительный алгоритм.
1. Строим в сети Γ = hN, ui произвольный поток f
0
.
2. Строим множество S
0
, состоящее из узлов x, которые можно достичь из истока s
по ненасыщенному потоком f
0
пути.
• Если s
′
/∈ S
0
, то f
0
– максимальный поток, u(S
0
, S
′
0
), S
′
0
≡ N \ S минимальное
сечение в сети Γ = hN, ui;
• В противном случае переходим к пункту 2.
3. Если s
′
∈ S
0
, то находим ненасыщенный потоком f
0
путь P
0
(s, s
′
) из s в s
′
(P
0
(s, s
′
)),
относительно потока f
0
.
Пусть
P
0
(s, s
′
) = {(s, x
1
), (x
1
, x
2
), . . . , (x
n
, s
′
)}.
4. Находим величину Θ = min
(x,y)∈P
0
[u(x, y) − f(x, y)] > 0.
5. Строим новый поток f
1
по правилу:
f
1
(x, y) =
f
0
(x, y) + Θ, если(x, y) ∈ P ;
f
0
(x, y) − Θ, если(y, x) ∈ P ;
f
0
(x, y), если (x, y) /∈ P, (y, x) /∈
P ;
и переходим к пункту 2 с потоком f
1
.
3.1. ЗАДАЧА О МАКСИМАЛЬНОМ ПОТОКЕ 79
3.1.4 Пример решения задачи о максимальном потоке.
Задана неориентированная сеть Γ = hN, ui задана узлами и пропускными способностями
ребер, которые графически могут быть нанесены на ребра сети.
2
1
3
4
5
6
4
1
1
1
4
1
1
3
2
S’
S
6
2
3
1
Построим по заданной сети матрицу пропускных способностей C
0
= {c
ij
}. Отсутствие
элементов в матрице пропускных способностей означает, что эти значения равны нулю.
s 1 2 3 4 5 6 s’
s 1 4 4
1 1 1 1 2
2 4 2 1
3 1 2 3
4 1 3 1
5 4 3 1
6 2 3 1 6
s’ 1 1 6
Строим множество S
0
= {s, 1, 3, 6, s
′
}. Видно что s
′
∈ S
0
. Выбираем путь P
0
(x, y),
ненасыщенный относительно потока f
0
: P
0
(x, y) = {(s, 1), (1, 3), (3, 6), (6, s
′
)}. Я чейки
(1, s), (3, 1), (6, 3), (s
′
, 6) помечаем знаком
”
+“, а ячейки (s, 1), (1, 3), (3, 6), (6, s
′
) помечаем
знаком
”
−“. Величина Θ
0
= min{c
s1
, c
1,3
, c
3,6
, c
6,s
′
} = min{1, 1, 3, 6} = 1.
Пересчитываем матрицу, прибавляем значения Θ
0
к элементам матрицы пропускных
способностей, помеченных
”
+“и вычитаем из элементов, помеченных знаком
”
−“.
80 Глава 3. СЕТИ
s 1 2 3 4 5 6 s’
s 1
−
4 4
1 1
+
1
−
1 2
2 4 2 1
3 1
+
2 3
−
4 1 3 1
5 4 3 1
6 2 3
+
1 6
−
s’ 1 1 6
+
Получаем новую матрицу C
1
:
s 1 2 3 4 5 6 s’
s 0 4 4
1 2 0 1 2
2 4 2 1
3 2 2 2
−
4 1 3 1
5 4 3 1
6 2 4 1 5
s’ 1 1 7
Строим множество S
1
= {s, 2, 3, 6, s
′
}. Видно что s
′
∈ S
1
. Выбираем путь P
1
(x, y),
ненасыщенный относительно потока f
1
: P
1
(x, y) = {(s, 2), (2, 3), (3, 6), (6, s
′
)}. Величина
Θ
1
= min{4, 2, 2, 5} = 2. Пересчитываем матрицу в соответствии алгоритмом, получаем
матрицу C
2
:
s 1 2 3 4 5 6 s’
s 0 2 4
1 2 0 1 2
2 6 0 1
3 2 4 0
4 1 3 1
5 4 3 1
6 2 6 1 3
s’ 1 1 9