- •1. Постановка и свойства транспортной задачи
- •2. Методические указания по решению задач транспортного типа
- •1. Задача о перевозке груза (транспортная задача)
- •1.1. Построение начального опорного плана методом северо-западного угла
- •1.2. Нахождение оптимального плана методом потенциалов
- •2. Задача о распределении механизмов между участками
- •3. Задача о назначении напарников
- •Решение задачи о назначениях венгерским методом
3. Задача о назначении напарников
Для рациональной организации в районе патрульно-постовой службы опытным сотрудникам Иванову, Петрову, Сидорову и Егорову необходимо назначить напарников из числа вновь поступивших молодых сотрудников: Костина, Мишина, Васина и Юрина. В ходе прохождения испытательного срока все возможные пары сотрудников оценивались по количеству неустраненных ими правонарушений за время дежурства на вверенном им участке. В результате были получены усредненные показатели по количеству неустраненных патрулями правонарушений за время одного дежурства, приведенные в следующей таблице.
|
Костин |
Мишин |
Васин |
Юрин |
Иванов |
2 |
10 |
9 |
7 |
Петров |
15 |
4 |
14 |
8 |
Сидоров |
13 |
14 |
16 |
11 |
Егоров |
4 |
15 |
13 |
19 |
Используя эту информацию, назовите пары сотрудников, которые нужно постоянно закрепить в качестве напарников на дальнейший срок службы, чтобы общее количество неустраненных правонарушений по всему контролируемому району за каждое дежурство было минимальным.
Для решения задачи нужно сформулировать ее в виде экономико-математи-ческой модели и, убедившись, что она представляет собой частный случай модели транспортной задачи, применить соответствующий алгоритм решения.
Решение
В задаче о назначении напарников нужно определить, кого из опытных сотрудников следует назначить в пару с молодым сотрудником, чтобы добиться минимального суммарного количества неустраненных правонарушений. Эта задача сводится к задаче транспортного типа.
Так как число опытных сотрудников (m = 4) равно числу молодых сотрудников (n = 4), должны выполняться следующие условия:
К каждому опытному сотруднику прикрепляется только один молодой сотрудник.
К каждому молодому сотруднику прикрепляется только один опытный сотрудник.
Введем переменные xij (i, j = ), которые характеризуют назначение i-го опытного сотрудника в пару с j-м молодым сотрудником. Они могут принимать лишь одно из двух значений 0 или 1:
1, если в пару к опытному сотруднику i назначен молодой сотрудник j;
xij =
0, если не назначен.
Например, x32 = 1. Это означает, что опытный сотрудник Сидоров (i = 3) назначен в пару с молодым сотрудником Мишином (j = 2).
Так как любой опытный сотрудник i должен быть назначен только в одну из четырёх возможных пар, то только одна из величин xi1, xi2, xi3, xi4 будет равна 1, а остальные будут равны 0. Таким образом, условие 1 имеет вид:
xi1 + xi2 + xi3 + xi4 = 1, i = .
С другой стороны, каждый молодой сотрудник j назначается только в одну из четырёх возможных пар. Поэтому только одна из величин x1j , x2j , x3j , x4j равна 1, а остальные равны 0. Таким образом, условие 2 имеет вид:
x1j + x2j + x3j + x4j = 1, j = .
Считается, что количество неустраненных правонарушений (стоимость назначения) cij зависит от того, как составлена пара (i, j). Отсюда постановка цели задачи: найти оптимальные пары из опытного и молодого сотрудников для работы в патруле, чтобы общее количество неустраненных правонарушений было минимальным.
Экономико-математическая модель задачи о назначении напарников имеет вид:
x11 + x12 + x13 + x14 = 1, (3.1)
x21 + x22 + x23 + x24 = 1, (3.2)
x31 + x32 + x33 + x34 = 1, (3.3)
x41 + x42 + x43 + x44 = 1, (3.4)
x11 + x21 + x31 + x41 = 1, (3.5)
x12 + x22 + x32 + x42 = 1, (3.6)
x13 + x23 + x33 + x43 = 1, (3.7)
x14 + x24 + x34 + x44 = 1, (3.8)
xij 0, i, j = , (3.9)
S = 2x11 + 10x12 + 9x13 + 7x14 + 15x21 + 4x22 + 14x23 + 8x24 + 13x31 +
14x32 + 16x33 + 11x34 + 4x41 + 15x42 + 13x43 + 19x44 min. (3.10)
Эту модель можно рассматривать как транспортную задачу, содержащую четыре пункта производства (опытные сотрудники) с объёмами предложений ai = 1, (i = ), четыре пункта потребления (молодые сотрудники) с заявками bj = 1, (j = ) и транспортные тарифы (количество правонарушений или «стоимость назначения») сij (i = , j = ).
Таким образом, построенная модель является специальным случаем транспортной задачи: m = n = 4 и ai = bj = 1 для всех i, j. Так как , то рассматриваемая задача является закрытой. Для ее решения можно использовать рассмотренные выше методы.
3.1. Начальный опорный план Х0 находим методом северо-западного угла (см. табл. 3.0), который был подробно разобран при решении задачи 1.
Таблица 3.0
bj ai |
К 1 |
М 1 |
В 1 |
Ю 1 |
И 1 |
2 1 |
10 0 |
9 |
7 |
П 1 |
15
|
4 1 |
14 0 |
8
|
С 1 |
13 |
14
|
16 1 |
11 0 |
Е 1 |
4 |
15 |
13
|
19 1 |
Получено 4 занятых клетки. План X0 является вырожденным, поскольку занятых клеток в опорном плане должно быть: m + n – 1 = 4 + 4 – 1 = 7. Значит, следует три занятые клетки плана сделать условно-занятыми путем заполнения их нулями. Лучше эту процедуру провести следующим образом: заполняется нулем клетка рядом с занятой клеткой по строке или ниже занятой клетки по столбцу.
Значение целевой функции на этом плане
S0 = 2 1 + 4 1 + 16 1 + 19 1 = 41.
1 0 – –
Х0 = – 1 0 – , S0 = 41.
– – 1 0
– – – 1
3.2. Для нахождения оптимального решения используем метод потенциалов.
Шаг 1. Проверим начальный опорный план X0 на оптимальность. Используем критерий оптимальности плана (см. стр. 6) для задачи (3.1) – (3.10). Найдем потенциалы строк Ui и столбцов Vj (см. табл. 3.1).
Пусть исходное значение U1 = 10.
V1 = U1 + С11 = 10 + 2 = 12,
V2 = U1 + С12 = 10 + 10 = 20,
U2 = V2 – С22 = 20 – 4 = 16,
V3 = U2 + С23 = 16 + 14 = 30,
U3 = V3 – С33 = 30 – 16 = 14,
V4 = U3 + С34 = 14 + 11 = 25,
U4 = V4 – С44 = 25 – 19 = 6.
Проверим выполнение соотношения
∆ij = Vj – Ui – Сij 0
для свободных клеток плана. Выпишем только ∆ij > 0.
∆41 = 12 – 6 – 4 = 2,
∆13 = 30 – 10 – 9 = 11,
∆43 = 30 – 6 – 13 = 11,
∆14 = 25 – 10 – 7 = 8,
∆24 = 25 – 16 – 1 = 1.
Таблица 3.1
bj ai |
К 1 |
М 1 |
В 1 |
Ю 1 |
Ui |
И 1 |
2 1 |
10 0 – |
9
+ |
7 |
10 |
П 1 |
15 |
4 1 + |
14 0 – |
8
|
16 |
С 1 |
13 |
14 |
16 1 |
11 0 |
14 |
Е 1 |
4 |
15 |
13 |
19 1 |
6 |
Vj |
12 |
20 |
30 |
25 |
S0 = 41 |
Выбираем максимальные положительные значения ∆13 = ∆43 = 11, которые соответствуют разным свободным клеткам. Для последующих действий следует взять клетку (1, 3) с меньшими затратами, так как c13 < c43 (9 < 13).
Улучшение плана в таблице 3.1 проводится следующим образом. К свободной клетке (1, 3), которая считается исходной и отмечается знаком «+», составляется замкнутый цикл. В него включаются клетки (1, 3), (2, 3), (2, 2), (1, 2). Вершины цикла отмечаются чередующимися знаками «+» и «–». Из минусовых клеток (2, 3) и (1, 2) выбирается минимальное значение: θ = min{x23, x12} = min{0, 0} = 0.
Обе клетки (2, 3) и (1, 2) содержат нули, однако освобождается клетка (2, 3) с большим значением тарифа: c23 < c12 (14 < 10). Корректирующая величина θ = 0 помещается в свободную клетку (1, 3). К значению в клетке (2, 2) прибавляется нуль, а от значения в клетке (1, 2) отнимается нуль.
В действительности улучшения значения целевой функции не произойдёт, так как по циклу перемещается θ = 0. Однако изменится расположение занятых и свободных клеток в транспортной таблице. Значение целевой функции останется прежним:
S1 = S0 – ∆13 ×θ = 41 – 11 0 = 41.
Шаг 2. В таблице 3.2 представлен полученный план X1, для которого вновь рассчитываются потенциалы строк Ui и потенциалы столбцов Vj, а также значения ∆ij.
1 0 0 –
Х1 = – 1 – – , S1 = 41.
– – 1 0
– – – 1
Таблица 3.2
bj ai |
К 1 |
М 1 |
В 1 |
Ю 1 |
Ui |
И 1 |
2 1 – |
10 0
|
9 0 + |
7 |
10 |
П 1 |
15 |
4 1
|
14
|
8
|
16 |
С 1 |
13 |
14
|
16 1 – |
11 0 + |
3 |
Е 1 |
4
+ |
15 |
13 |
19 1 – |
-5 |
Vj |
12 |
20 |
19 |
14 |
S1 = 41 |
План X1 не оптимален, так как имеются ∆ij > 0. Выпишем максимальное положительное значение: ∆41 = 13. Свободная клетка (4, 1) отмечается «+», к ней составляется цикл, в который включены клетки (4, 1), (1, 1), (1, 3), (3, 3), (3, 4), (4, 4).
Выбирается корректирующая величина θ = min{x11, x33, x44} = min{1, 1, 1} = 1. Освобождается занятая клетка (4, 4) с наибольшим тарифом, а свободная клетка (4, 1) становится занятой со значением, равным 1. Проводится корректировка плана по циклу: к значению в плюсовой клетке прибавляется θ, а от значения в минусовой клетке отнимается θ. Значение целевой функции уменьшается:
S2 = S1 – ∆41×θ = 41 – 13 1 = 28.
Получен новый опорный план X2, представленный в таблице 3.3.
0 0 1 –
Х2 = – 1 – – , S2 = 28.
– – 0 1
1 – – –
Шаг 3. Проверка плана Х2 показывает, что условия критерия оптимальности для него не выполнены. Максимальное положительное значение ∆32 = 3. Проведем корректировку плана с помощью цикла, в который входят клетки (3, 2), (1, 2), (1, 3) и (3, 3). Поскольку величина θ равна нулю, значение целевой функции останется прежним, S3 = 28.
Таблица 3.3
bj ai |
К 1 |
М 1 |
В 1 |
Ю 1 |
Ui |
И 1 |
2 0 |
1 0 – 0 |
9 + 1 |
7 |
10 |
П 1 |
15 |
4 1 |
14
|
8
|
16 |
С 1 |
13 |
14 + |
16 – 0 |
11 1 |
3 |
Е 1 |
4 1 |
15 |
13 |
19
|
8 |
Vj |
12 |
20 |
19 |
14 |
S2 = 28 |
Шаг 4. Получен новый опорный план X3, представленный в таблице 3.4. Его проверка на оптимальность показывает, что для всех свободных клеток выполнено условие: ∆ij < 0. Значит, этот план оптимален.
Таблица 3.4
bj ai |
К 1 |
М 1 |
В 1 |
Ю 1 |
Ui |
И 1 |
2 0 |
10 0 |
9 1 |
7 |
10 |
П 1 |
15 |
4 1 |
14
|
8
|
16 |
С 1 |
13 |
14 0 |
16
|
11 1 |
6 |
Е 1 |
4 1 |
15 |
13 |
19
|
8 |
Vj |
12 |
20 |
19 |
17 |
S3 = 28 |
О твет:
– – 1 –
Х* = – 1 – – , S* = 28.
– – – 1
1 – – –
Экономическая интерпретация решения задачи о назначении напарников
Полученный оптимальный план содержит четыре клетки с единицами, каждая из которых задает пару из опытного и молодого сотрудника. Таким образом, пары должны быть составлены таким образом:
Иванов и Васин, Петров и Мишин,
Сидоров и Юрин, Егоров и Костин.
При таком назначении напарников количество неустраненных правонарушений будет минимальным и равным 28.