Зенкевич Н.А. Практикум по исследованию операций
Подождите немного. Документ загружается.
2.4. ПРИМЕРЫ 61
Строим систему потенциалов для плана перевозок X
3
= {x
3
ij
}:
v
3
3
− u
3
1
= 0, 6, v
3
5
− u
3
1
= 0, 5
v
3
1
− u
3
2
= 0, 4, v
3
2
− u
3
2
= 0, 5
v
3
2
− u
3
3
= 0, 2, v
3
5
− u
3
3
= 0, 4
v
3
4
− u
3
4
= 0, 8, v
3
5
− u
3
4
= 1, 1.
Потенциалы плана X
3
= {x
3
ij
} равны:
u
3
1
= 0, v
3
1
= 0, 2, v
3
2
= 0, 3,
v
3
3
= 0, 6, v
3
4
= 0, 2, v
3
5
= 0, 5,
u
3
2
= −0, 2, u
3
3
= 0, 1, u
3
4
= 0, 2.
Строим матрицу невязок ∆
3
= {δ
3
ij
}:
∆
3
=
0, 5 0, 2 0 0, 7 0
0 0 0 0, 4 0, 3
0, 2 0 0 0, 3 0
0, 1 0, 2 −0, 2 0 0
Минимальный отрицательный элемент матрицы невязок есть δ
3
43
= −0, 2, на место эле-
мента x
43
помещаем Θ
+
и строим цикл:
0,7 0,5 0,6 0,9 0,5
0 0 100
−
0 0
∗
+
0,4 0,5 0,8 0,8 1,0
120 30 0 0 0
0,3 0,2 0,5 0,4 0,4
0 170 0 0 30
0,9 1,1 1,0 0,8 1,1
0 0 Θ
+
30 70
−
Табл.2.4.17. Построение цикла в плане X
3
= {x
3
ij
}
Пропускаем максимально возможный поток Θ
+
= 70 по построенному циклу в плане
X
3
= {x
3
ij
}. Получаем новый план X
4
= {x
4
ij
}.
62 Глава 2. ЗАДАЧИ ТРАНСПОРТНОГО ТИПА
0,7 0,5 0,6 0,9 0,5
0 0 30 0 70
0,4 0,5 0,8 0,8 1,0
120 30 0 0 0
0,3 0,2 0,5 0,4 0,4
0 170 0 0 30
0,9 1,1 1,0 0,8 1,1
0 0 70 30 0
Табл.2.4.18. План перевозок X
4
= {x
4
ij
}
План перевозок X
4
= {x
4
ij
} получился невырожденный.
Строим множество S
4
= {(i, j)|x
4
ij
> 0} = {(1, 3), (1, 5), (2, 1), (2, 2), (3, 2), (3, 5), (4, 3), (4, 4)}
Для этой итерации система потенциалов плана X
4
= {x
4
ij
} запишется в виде:
v
4
3
− u
4
1
= 0, 6, v
4
5
− u
4
1
= 0, 5
v
4
1
− u
4
2
= 0, 4, v
4
2
− u
4
2
= 0, 5
v
4
2
− u
4
3
= 0, 2, v
4
5
− u
4
3
= 0, 4
v
4
3
− u
4
4
= 1, 0, v
4
4
− u
4
4
= 0, 8.
Потенциалы плана X
4
= {x
4
ij
} равны:
u
4
1
= 0, v
4
1
= 0, 2, v
4
2
= 0, 3,
v
4
3
= 0, 6, v
4
4
= 0, 4, v
4
5
= 0, 5,
u
4
2
= −0, 2, u
4
3
= 0, 1, u
4
4
= −0, 4
Строим матрицу невязок ∆
4
= {δ
4
ij
}:
∆
4
=
0, 5 0, 2 0 0, 5 0
0 0 0 0, 2 0, 3
0, 7 0 0 0, 1 0
0, 3 0, 4 0 0 0, 2
На этой итерации среди δ
4
ij
отсутствуют отрицательные, следовательно план X
4
= {x
4
ij
}
– оптимален. Затраты на перевозку продукции на оптимальном плане X
4
= {x
4
ij
} равны:
z(X
5
) =
n
P
i=1
m
P
j=1
c
ij
x
ij
=
= 30 · 0, 6 + 70 · 0, 5 + 120 · 0, 4 + 30 · 0, 5 + 170 · 0, 2 + 30 · 0, 4 + 70 + 30 · 0, 8 = 256.
2.5. ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ 63
2.5 Задачи для самостоятельного решения
2.5.1 2.5.2
a
1 8 2 3 30
C = 4 7 5 1 50
5 3 4 4 20
b
j
15 15 40 30
a
2 4 5 1 60
C = 2 3 9 4 70
3 4 2 5 20
b 40 30 30 50
2.5.3 2.5.4
a
2 6 3 4 8 40
C =
1 5 6 8 7 30
3 4 1 4 10 35
b 20 34 16 10 25
a
3 2 4 1 50
C =
2 3 1 5 40
3 2 4 4 20
b 30 25 35 20
2.5.5 2.5.6
a
2 4 1 3 30
C = 5 6 5 4 20
3 7 9 5 40
1 2 2 7 50
b 35 20 55 30
a
4 5 5 7 100
C = 8 7 5 4 120
9 6 4 5 150
3 2 9 3 130
b 140 130 90 140
2.5.7 2.5.8
a
8 12 4 9 10 60
C = 7 5 15 3 6 40
9 4 6 12 7 100
5 3 2 6 4 50
b 30 80 65 35 40
a
3 7 1 5 4 30
C = 7 5 8 6 3 5
6 4 8 3 2 45
3 1 7 4 2 70
b 10 35 15 25 35
64 Глава 2. ЗАДАЧИ ТРАНСПОРТНОГО ТИПА
2.5.9 2.5.10
a
2 3 6 8 2 10 130
C = 8 1 2 3 5 6 90
7 4 4 1 4 8 100
2 8 5 1 3 6 140
b 110 50 30 80 100 90
a
1 5 2 2 1 6 100
C = 3 6 2 4 3 3 15
8 10 4 5 6 8 90
7 3 7 9 1 2 55
b 30 40 55 80 45 10
2.5.11 2.5.12
a
4 8 9 6 3 7 200
C = 3 3 10 8 6 8 100
5 7 5 4 1 3 170
6 3 4 3 5 6 130
b 100 200 100 70 30 100
a
5 5 4 6 2 4 30
C = 6 6 5 5 1 5 50
7 7 2 7 5 6 50
8 4 4 8 4 3 50
b 40 40 20 20 30 30
2.5.13 2.5.14
a
4 11 9 10 7 6 400
C = 5 9 8 4 12 4 160
6 8 15 12 5 2 400
7 15 6 7 2 1 60
b 400 200 100 80 100 60
a
4 6 3 8 5 4 200
C = 3 6 7 8 9 10 250
4 15 10 12 4 5 250
7 8 6 3 4 9 200
b 100 100 300 150 150 100
2.6. ЗАДАЧА О НАЗНАЧЕНИЯХ 65
2.6 Задача о назначениях
2.6.1 Формулировка задачи о простых назначениях.
Имеется n работ: J
1
, . . . , J
n
и m работников: I
1
, . . . , I
m
. Задана матрица эффективности
A = {a
ij
}, где:
a
ij
=
1, если работник I
i
может выполнять работу J
j
,
0, если работник I
i
не может выполнять работу J
j
,
(2.6.1)
Требуется всех работников распределить по работам, назначая на каждую работу
только одного работника (полное назначение).
Теорема разрешимости задачи о простых назначениях.
Теорема 2.6.1 Простая задача о назначениях имеет решение тогда и только тогда,
когда для любого множества S, которое является подмножеством множества работ-
ников, выполняется условие |S| ≤ |Q(S)|, где Q(S) множество работ, которые могут
выполнять работники из S, а |S| и |Q(S)| количество элементов в множестве S и
Q(S) соответственно.
2.6.2 Формулировка задачи об оптимальных назначениях.
Имеется m работников, обозначим I
1
, . . . , I
m
– множество работников. Предполагает-
ся, что работники могут выполнять некоторые из множества ра бот J
1
, . . . , J
n
. Известна
матрица A = {a
ij
}, a
ij
≥ 0 – матрица эффективности (производительности) выполнения
работником I
i
-й работы J
j
-й i =
1, m, j = 1, n.
Требуется построить такой план назначений X = {x
ij
}, i =
1, m, j = 1, n работников
на работы, который максимизирует суммарную эффективность выполнения комплекса
работ, при этом каждого работника назначают не более чем на одну работу, и на каждую
работу может быть назначено не более одного работника. Величины x
ij
могут принимать
только два значения:
x
ij
=
1, если работник I
i
назначен на работуJ
j
,
0, если работник I
i
не назначен на работу J
j
.
(2.6.2)
66 Глава 2. ЗАДАЧИ ТРАНСПОРТНОГО ТИПА
2.6.3 Математическая формулировка задачи об оптимальных
назначениях.
max z = max
m
P
i=1
n
P
j=1
a
ij
x
ij
n
P
j=1
x
ij
≤ 1, i =
1, m;
m
P
i=1
x
ij
≤ 1, j =
1, n;
x
ij
≥ 0, x
ij
− целые.
2.6.4 Каноническая форма задачи о назначениях
Для того чтобы задача об оптимальных назначениях имела оптимальное решение необ-
ходимо и достаточно, чтобы количество работников было равно количеству работ, т.е.
n = m. При этом условии ограничения неравенства превращаются в равенства:
max z = max
n
P
i=1
n
P
j=1
a
ij
x
ij
n
P
j=1
x
ij
= 1, i =
1, n;
n
P
i=1
x
ij
= 1, j =
1, n;
x
ij
≥ 0, x
ij
− целые.
Если m 6= n, то задача о назначениях несбалансирована. Любую задачу о назначениях
можно сбалансировать введя необходимое количество фиктивных работников (работ).
Заметим, что если рассматривать задачу минимизации, то это будет частный случай
транспортной задачи.
2.6.5 Двойственная задача об оптимальных назначениях.
min w = min(
n
P
i=1
ξ
i
+
n
P
j=1
η
j
)
ξ
i
+ η
j
≥ a
ij
, i =
1, n, j = 1, n;
Теорема двойственности для задачи о назначениях.
2.6. ЗАДАЧА О НАЗНАЧЕНИЯХ 67
Теорема 2.6.2 Для того чтобы X
∗
= {x
∗
ij
} и Y
∗
= {ξ
∗
1
, . . . , ξ
∗
n
, η
∗
1
, . . . , η
∗
n
} – допустимые
решения прямой и двойственной задачи об оптимальных назначениях были оптималь-
ными необходимо и достаточно. чтобы:
n
X
i=1
n
X
j=1
a
ij
x
ij
=
n
X
i=1
ξ
i
+
n
X
j=1
η
j
2.6.6 Алгоритм решения задачи.
0. Строим начальное допустимое решение двойственной задачи.
ξ
0
i
= max
j=
1,n
a
ij
, i =
1, m
η
0
j
= 0, j =
1, n
ИТЕРАЦИЯ
1. Строим множество пар индексов P
0
= {(i, j)| ξ
0
i
+ η
0
j
= a
ij
}
• Решаем задачу о простых назначениях на множестве
P
0
= {(i, j)| ξ
0
i
+ η
0
j
= a
ij
}.
• Если она разрешима, то это назначение оптимально и вычисления прекращи-
ются.
• В противном случае переходим к п.2 алгоритма.
2. Если простая задача о назначениях неразрешима, то по теореме разрешимости за-
дачи о простых назначениях, существует подмножество K ⊂ (1, . . . , m) работников,
способных выполнить Q(K) – работ, для которых q < k (k = |K|, q = |Q(K)|).
3. Определяем новые двойственные оценки по правилу:
ξ
1
i
=
ξ
0
i
− 1, i ∈ K
ξ
0
i
, i /∈ K;
η
1
j
=
η
0
j
+ 1, j ∈ Q
η
0
j
, j /∈ Q;
Строим множество P
1
= {(i, j)| ξ
1
i
+ η
1
j
= a
ij
}. Переходим к п. 1 алгоритма новой
итерации с новыми двойственными оценками.
68 Глава 2. ЗАДАЧИ ТРАНСПОРТНОГО ТИПА
Пример.
Задача о назначениях задана матрицей производительностей A:
ξ
i
\η
j
0 0 0 0 0
12 12 9 10 3 8
9 6 6 2 2 9
10 6 8 10 10 9
6 6 3 4 1 1
11 11 1 10 9 10
Пусть по строкам таблицы у нас представлены работники {I
1
, I
2
, I
3
, I
4
, I
5
}, по столб-
цам работы {J
1
, J
2
, J
3
, J
4
, J
5
}.
Запишем справа от таблицы все элементы для которых выполняе тся ξ
i
= max a
ij
.
Обведем кружками те элементы a
ij
для которых выполняется a
ij
= ξ
i
+ η
j
.
H
H
H
H
H
H
H
H
H
ξ
i
η
j
↑ 0 0 0 0 0
↓12 12 9 10 3 8
9 6 6 2 2 9
10 6 8 10 10 9
↓6 6 3 4 1 1
↓11 11 1 10 9 10
±°
²¯
±°
²¯
±°
²¯
±°
²¯
±°
²¯
±°
²¯
Множество K
1
= {I
1
, I
2
, I
4
, I
5
}, множество Q
1
= {J
1
, J
3
, J
4
, J
5
}. Мы не можем на
вторую работу назначить ни одного из кандидатов, кроме того на первую работу у нас
имеется три претендента. Для того чтобы провести назначение необходимо проделать
следующее: поднимаем на единицу η
1
, поскольку именно на первую работу у нас три
претендента и снижаем требования к сотрудникам ξ
1
, ξ
4
, ξ
5
, претендующим на первую
работу. Получаем новую таблицу:
H
H
H
H
H
H
H
H
H
ξ
i
η
j
1 0 0 0 0
11 12 9 10 3 8
9 6 6 2 2 9
10 6 8 10 10 9
5 6 3 4 1 1
10 11 1 10 9 10
2.6. ЗАДАЧА О НАЗНАЧЕНИЯХ 69
Опять обводим те элементы для которых выполняется пункт 1 алгоритма.
H
H
H
H
H
H
H
H
H
ξ
i
η
j
↑ 1 0 ↑0 0 ↑0
↓11 12 9 10 3 8
↓ 9 6 6 2 2 9
10 6 8 10 10 9
↓5 6 3 4 1 1
↓10 11 1 10 9 10
±°
²¯
±°
²¯
±°
²¯
±°
²¯
±°
²¯
±°
²¯
±°
²¯
±°
²¯
Множество K
2
= {I
1
, I
2
, I
4
, I
5
}, множество Q
2
= {J
1
, J
3
, J
4
, J
5
}. Если расположение
обведенных элементов не изменилось, то надо поднять η
j
и понизить ξ
j
на две единицы
или на три единицы и т.д.
В нашем случае на вторую работу опять нет кандидатов. Но на пе рвую третью и
пятую работу претендует по несколько человек. Поднимаем η
1
, η
3
, η
5
и снижаем ξ
1
, ξ
2
,
ξ
4
, ξ
5
. Величина ξ
i
понижается только в том случае, если у нас обведенный элемент
для которого повышается η
j
один на строке или для каж дого из обведенных элементов
также повышается η
j
. В этом случае η
j
увеличивается, а ξ
i
остается прежним. После
построения нового решения имеем:
H
H
H
H
H
H
H
H
H
ξ
i
η
j
2 0 1 0 1
10 12 9 10 3 8
8 6 6 2 2 9
10 6 8 10 10 9
4 6 3 4 1 1
9 11 1 10 9 10
Действуя далее по алгоритму, получаем таблицу:
H
H
H
H
H
H
H
H
H
ξ
i
η
j
↑ 2 0 1 ↑0 ↑1
↓10 12 9 10 3 8
↓ 8 6 6 2 2 9
↓10 6 8 10 10 9
↓4 6 3 4 1 1
9 11 1 10 9 10
±°
²¯
±°
²¯
±°
²¯
±°
²¯
±°
²¯
±°
²¯
±°
²¯
±°
²¯
±°
²¯
70 Глава 2. ЗАДАЧИ ТРАНСПОРТНОГО ТИПА
K
3
= {I
1
, I
2
, I
3
, I
4
}, Q
3
= {J
1
, J
3
, J
4
, J
5
}.
Элемент a
33
перестал быть обведенным, поскольку не выполняется условие пункта 0
0
алгоритма. У нас по прежнему нет претендентов на вторую работу. Повышаем η
1
, η
4
, η
5
и снижаем ξ
1
, ξ
2
, ξ
3
, ξ
4
, а ξ
5
не снижаем, так как не для каждого обведенного элемента
этой стоки увеличивается η
j
. Получаем новую таблицу:
H
H
H
H
H
H
H
H
H
ξ
i
η
j
3 0 1 1 2
9 12 9 10 3 8
7 6 6 2 2 9
9 6 8 10 10 9
3 6 3 4 1 1
9 11 1 10 9 10
±°
²¯
±°
²¯
±°
²¯
±°
²¯
±°
²¯
±°
²¯
±°
²¯
±°
²¯
K
4
= {I
1
, I
2
, I
3
, I
4
, I
5
}, Q
4
= {J
1
, J
2
, J
3
, J
4
, J
5
}. Полное назначение возможно.
Элементы a
51
, a
54
, a
54
больше не обведены, однако теперь имеются кандидаты на все
работы. На четвертую и пятую работы только по одному претенденту, следовательно они
и будут назначены на эти работы. Пятого работника возможно назначить только на тре-
тью работу. Остались первый и четвертый работники и первая и вторая работы. Можно
назначить первого работника на первую работу, а четвертого на вторую или наоборот.
(Это безразлично, поскольку сумма производительности от э того не изменится.)
Значение целевой функции можно вычислить двумя способами: как значение функ-
ции прямой задачи z =
n
P
i=1
m
P
j=1
x
ij
a
ij
= 12 + 9 + 11 + 3 + 10 = 45, или как значение целевой
функции двойственной задачи w =
m
P
i=1
ξ
i
+
n
P
j=1
η
j
= 6 + 11 + 9 + 3 + 9 + 3 + 1 + 3 = 45.
2.6.7 Задача о назначениях. Венгерский метод.
Имеется другой эффективный метод решения задачи о назначениях.
Алгоритм венгерского метода.
1. В исходной матрице A производительностей определим в каж дой строке минималь-
ный элемент и вычтем его из всех других элементов строки.
2. В матрице, полученной на первом этапе, найдем в каждом столбце минимальный
элемент и вычтем его из всех других элементов столбца.