3. Задача о назначении напарников

Для рациональной организации в районе патрульно-постовой службы опытным сотрудникам Иванову, Петрову, Сидорову и Егорову необходимо назначить напарников из числа вновь поступивших молодых сотрудников: Костина, Мишина, Васина и Юрина. В ходе прохождения испытательного срока все возможные пары сотрудников оценивались по количеству неустраненных ими правонарушений за время дежурства на вверенном им участке. В результате были получены усредненные показатели по количеству неустраненных патрулями правонарушений за время одного дежурства, приведенные в следующей таблице.

	Костин	Мишин	Васин	Юрин
Иванов	2	10	9	7
Петров	15	4	14	8
Сидоров	13	14	16	11
Егоров	4	15	13	19

Используя эту информацию, назовите пары сотрудников, которые нужно постоянно закрепить в качестве напарников на дальнейший срок службы, чтобы общее количество неустраненных правонарушений по всему контролируемому району за каждое дежурство было минимальным.

Для решения задачи нужно сформулировать ее в виде экономико-математи-ческой модели и, убедившись, что она представляет собой частный случай модели транспортной задачи, применить соответствующий алгоритм решения.

Решение

В задаче о назначении напарников нужно определить, кого из опытных сотрудников следует назначить в пару с молодым сотрудником, чтобы добиться минимального суммарного количества неустраненных правонарушений. Эта задача сводится к задаче транспортного типа.

Так как число опытных сотрудников (m = 4) равно числу молодых сотрудников (n = 4), должны выполняться следующие условия:

1. К каждому опытному сотруднику прикрепляется только один молодой сотрудник.

2. К каждому молодому сотруднику прикрепляется только один опытный сотрудник.

Введем переменные x_ij (i, j = ), которые характеризуют назначение i-го опытного сотрудника в пару с j-м молодым сотрудником. Они могут принимать лишь одно из двух значений 0 или 1:

1, если в пару к опытному сотруднику i назначен молодой сотрудник j;

x_ij =

0, если не назначен.

Например, x₃₂ = 1. Это означает, что опытный сотрудник Сидоров (i = 3) назначен в пару с молодым сотрудником Мишином (j = 2).

Так как любой опытный сотрудник i должен быть назначен только в одну из четырёх возможных пар, то только одна из величин x_i1, x_i2, x_i3, x_i4 будет равна 1, а остальные будут равны 0. Таким образом, условие 1 имеет вид:

x_i1 + x_i2 + x_i3 + x_i4 = 1, i = .

С другой стороны, каждый молодой сотрудник j назначается только в одну из четырёх возможных пар. Поэтому только одна из величин x_1j , x_2j , x_3j , x_4j равна 1, а остальные равны 0. Таким образом, условие 2 имеет вид:

x_1j + x_2j + x_3j + x_4j = 1, j = .

Считается, что количество неустраненных правонарушений (стоимость назначения) c_ij зависит от того, как составлена пара (i, j). Отсюда постановка цели задачи: найти оптимальные пары из опытного и молодого сотрудников для работы в патруле, чтобы общее количество неустраненных правонарушений было минимальным.

Экономико-математическая модель задачи о назначении напарников имеет вид:

x₁₁ + x₁₂ + x₁₃ + x₁₄ = 1, (3.1)

x₂₁ + x₂₂ + x₂₃ + x₂₄ = 1, (3.2)

x₃₁ + x₃₂ + x₃₃ + x₃₄ = 1, (3.3)

x₄₁ + x₄₂ + x₄₃ + x₄₄ = 1, (3.4)

x₁₁ + x₂₁ + x₃₁ + x₄₁ = 1, (3.5)

x₁₂ + x₂₂ + x₃₂ + x₄₂ = 1, (3.6)

x₁₃ + x₂₃ + x₃₃ + x₄₃ = 1, (3.7)

x₁₄ + x₂₄ + x₃₄ + x₄₄ = 1, (3.8)

x_ij 0, i, j = , (3.9)

S = 2x₁₁ + 10x₁₂ + 9x₁₃ + 7x₁₄ + 15x₂₁ + 4x₂₂ + 14x₂₃ + 8x₂₄ + 13x₃₁ +

14x₃₂ + 16x₃₃ + 11x₃₄ + 4x₄₁ + 15x₄₂ + 13x₄₃ + 19x₄₄ min. (3.10)

Эту модель можно рассматривать как транспортную задачу, содержащую четыре пункта производства (опытные сотрудники) с объёмами предложений a_i = 1, (i = ), четыре пункта потребления (молодые сотрудники) с заявками b_j = 1, (j = ) и транспортные тарифы (количество правонарушений или «стоимость назначения») с_ij (i = , j = ).

Таким образом, построенная модель является специальным случаем транспортной задачи: m = n = 4 и a_i = b_j = 1 для всех i, j. Так как , то рассматриваемая задача является закрытой. Для ее решения можно использовать рассмотренные выше методы.

3.1. Начальный опорный план Х₀ находим методом северо-западного угла (см. табл. 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 занятых клетки. План X₀ является вырожденным, поскольку занятых клеток в опорном плане должно быть: m + n – 1 = 4 + 4 – 1 = 7. Значит, следует три занятые клетки плана сделать условно-занятыми путем заполнения их нулями. Лучше эту процедуру провести следующим образом: заполняется нулем клетка рядом с занятой клеткой по строке или ниже занятой клетки по столбцу.

Значение целевой функции на этом плане

S₀ = 2 1 + 4 1 + 16 1 + 19 1 = 41.

1 0 – –

Х₀ = – 1 0 – , S₀ = 41.

– – 1 0

– – – 1

3.2. Для нахождения оптимального решения используем метод потенциалов.

Шаг 1. Проверим начальный опорный план X₀ на оптимальность. Используем критерий оптимальности плана (см. стр. 6) для задачи (3.1) – (3.10). Найдем потенциалы строк U_i и столбцов V_j (см. табл. 3.1).

Пусть исходное значение U₁ = 10.

V₁ = U₁ + С₁₁ = 10 + 2 = 12,

V₂ = U₁ + С₁₂ = 10 + 10 = 20,

U₂ = V₂ – С₂₂ = 20 – 4 = 16,

V₃ = U₂ + С₂₃ = 16 + 14 = 30,

U₃ = V₃ – С₃₃ = 30 – 16 = 14,

V₄ = U₃ + С₃₄ = 14 + 11 = 25,

U₄ = V₄ – С₄₄ = 25 – 19 = 6.

Проверим выполнение соотношения

∆_ij = V_j – U_i – С_ij 0

для свободных клеток плана. Выпишем только ∆_ij > 0.

∆₄₁ = 12 – 6 – 4 = 2,

∆₁₃ = 30 – 10 – 9 = 11,

∆₄₃ = 30 – 6 – 13 = 11,

∆₁₄ = 25 – 10 – 7 = 8,

∆₂₄ = 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

Выбираем максимальные положительные значения ∆₁₃ = ∆₄₃ = 11, которые соответствуют разным свободным клеткам. Для последующих действий следует взять клетку (1, 3) с меньшими затратами, так как c₁₃ < c₄₃ (9 < 13).

Улучшение плана в таблице 3.1 проводится следующим образом. К свободной клетке (1, 3), которая считается исходной и отмечается знаком «+», составляется замкнутый цикл. В него включаются клетки (1, 3), (2, 3), (2, 2), (1, 2). Вершины цикла отмечаются чередующимися знаками «+» и «–». Из минусовых клеток (2, 3) и (1, 2) выбирается минимальное значение: θ = min{x₂₃, x₁₂} = min{0, 0} = 0.

Обе клетки (2, 3) и (1, 2) содержат нули, однако освобождается клетка (2, 3) с большим значением тарифа: c₂₃ < c₁₂ (14 < 10). Корректирующая величина θ = 0 помещается в свободную клетку (1, 3). К значению в клетке (2, 2) прибавляется нуль, а от значения в клетке (1, 2) отнимается нуль.

В действительности улучшения значения целевой функции не произойдёт, так как по циклу перемещается θ = 0. Однако изменится расположение занятых и свободных клеток в транспортной таблице. Значение целевой функции останется прежним:

S₁ = S₀ – ∆₁₃ ×θ = 41 – 11 0 = 41.

Шаг 2. В таблице 3.2 представлен полученный план X₁, для которого вновь рассчитываются потенциалы строк U_i и потенциалы столбцов V_j, а также значения ∆_ij.

1 0 0 –

Х₁ = – 1 – – , S₁ = 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

План X₁ не оптимален, так как имеются ∆_ij > 0. Выпишем максимальное положительное значение: ∆₄₁ = 13. Свободная клетка (4, 1) отмечается «+», к ней составляется цикл, в который включены клетки (4, 1), (1, 1), (1, 3), (3, 3), (3, 4), (4, 4).

Выбирается корректирующая величина θ = min{x₁₁, x₃₃, x₄₄} = min{1, 1, 1} = 1. Освобождается занятая клетка (4, 4) с наибольшим тарифом, а свободная клетка (4, 1) становится занятой со значением, равным 1. Проводится корректировка плана по циклу: к значению в плюсовой клетке прибавляется θ, а от значения в минусовой клетке отнимается θ. Значение целевой функции уменьшается:

S₂ = S₁ – ∆₄₁×θ = 41 – 13 1 = 28.

Получен новый опорный план X₂, представленный в таблице 3.3.

0 0 1 –

Х₂ = – 1 – – , S₂ = 28.

– – 0 1

1 – – –

Шаг 3. Проверка плана Х₂ показывает, что условия критерия оптимальности для него не выполнены. Максимальное положительное значение ∆₃₂ = 3. Проведем корректировку плана с помощью цикла, в который входят клетки (3, 2), (1, 2), (1, 3) и (3, 3). Поскольку величина θ равна нулю, значение целевой функции останется прежним, S₃ = 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. Получен новый опорный план X₃, представленный в таблице 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.