Для рациональной организации в районе патрульно-постовой службы опытным сотрудникам Иванову, Петрову, Сидорову и Егорову необходимо назначить напарников из числа вновь поступивших молодых сотрудников: Костина, Мишина, Васина и Юрина. В ходе прохождения испытательного срока все возможные пары сотрудников оценивались по количеству не устранённых ими правонарушений за время дежурства на вверенном им участке. В результате были получены усреднённые показатели по количеству не устранённых патрулями правонарушений за время одного дежурства, приведённые в следующей таблице.
Таблица 1 – Исходные данные
Костин Мишин Васин Юрин
Иванов 9 5 4 10
Петров 8 8 8 3
Сидоров 8 9 7 7
Егоров 5 8 11 6
Опираясь на эту информацию, назовите пары сотрудников, которые нужно постоянно закрепить в качестве напарников на дальнейший срок службы, чтобы общее количество не устранённых правонарушений по всему контролируемому району за каждое дежурство было минимальным.
Для решения задачи нужно сформулировать ее в виде экономико-математической модели и, убедившись, что она представляет собой частный случай модели транспортной задачи, применить соответствующий алгоритм решения.
Решение
В задаче о назначении напарников нужно определить, кого из опытных сотрудников следует назначить в пару с молодым сотрудником, чтобы добиться минимального суммарного количества неустраненных правонарушений. Эта задача сводится к задаче транспортного типа.
Так как число опытных сотрудников (m = 4) равно числу молодых сотрудников (n = 4), должны выполняться следующие условия:
К каждому опытному сотруднику прикрепляется только один молодой сотрудник.
К каждому молодому сотруднику прикрепляется только один опытный сотрудник.
Введём переменные (i, j = ), которые характеризуют назначение i-го опытного сотрудника в пару с j-м молодым сотрудником. Они могут принимать лишь одно из двух значений 0 или 1:
Например, x32 = 1. Это означает, что опытный сотрудник Сидоров (i = 3) назначен в пару с молодым сотрудником Мишином (j = 2).
Так как любой опытный сотрудник i должен быть назначен только в одну из четырёх возможных пар, то только одна из величин , , , будет равна 1, а остальные будут равны 0. Таким образом, условие 1 имеет вид:
, .
С другой стороны, каждый молодой сотрудник j назначается только в одну из четырёх возможных пар. Поэтому только одна из величин , , , равна 1, а остальные равны 0. Таким образом, условие 2 имеет вид:
, .
Считается, что количество не устранённых правонарушений (стоимость назначения) cij зависит от того, как составлена пара (i, j). Отсюда постановка цели задачи: найти оптимальные пары из опытного и молодого сотрудников для работы в патруле, чтобы общее количество не устранённых правонарушений было минимальным
.
Экономико-математическая модель задачи о назначении напарников имеет вид:
, .
Эту модель можно рассматривать как транспортную задачу, содержащую четыре пункта производства (опытные сотрудники) с объёмами предложений , , четыре пункта потребления (молодые сотрудники) с заявками , и транспортные тарифы (количество правонарушений или «стоимость назначения») , .
Таким образом, построенная модель является специальным случаем транспортной задачи: и для всех i, j. Так как , то рассматриваемая задача является закрытой.
Начальный опорный план находим методом северо-западного угла (табл. 2).
Таблица 2 – Опорный план
bj
ai К
1 М
1 В
1 Ю
1
И 1 9
1 5
0 4 10
П 1 8
8
1 8
0 3
С 1 8 9
7
1 7
0
Е 1 5 8 11
6
1
Получено 4 занятых клетки. План является вырожденным, поскольку занятых клеток в опорном плане должно быть: m + n – 1 = 4 + 4 – 1 = 7. Значит, следует три занятые клетки плана сделать условно-занятыми путем заполнения их нулями. Лучше эту процедуру провести следующим образом: заполняется нулём клетка рядом с занятой клеткой по строке или ниже занятой клетки по столбцу.
Получаем:
,
.
Для нахождения оптимального решения используем метод потенциалов.
Шаг 1. Проверим начальный опорный план на оптимальность. Найдём потенциалы строк и столбцов (табл. 3).
Пусть исходное значение . Получаем далее:
,
,
,
,
Таблица 3 – Шаг 1 метода потенциалов
bj
ai К
1 М
1 В
1 Ю
1 ui
И 1 9
1 5
0 4
10 0
П 1 8 8
1
8
245110153670000
– 3
+ -3
С 1 8 9 7
1
+ 7
0
– -2
Е 1 5 8 11 6
1 -1
vj 9 5 5 5 S0 = 30
,
,
.
Проверим для свободных клеток плана выполнение соотношения:
Выпишем только :
,
,
,
,
.
Выбираем максимальные положительные значения , которые соответствуют разным свободным клеткам