Задача 5. Максимальное число назначений

 

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

Оптимизировать в этом случае, как впрочем и в  других логистических задачах, можно различные параметры, при сохранении как правило единой глобальной цели: минимизации итоговых издержек.

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

 

ВВЕДЕНИЕ В ПРОБЛЕМУ

 

Стандартный способ формализации такого рода задач сводится к следующему. Обозначим возможные назначения матрицей A, где строки соответствуют сотрудникам, а столбцы – участкам работы.

                  a [ i, j ] =1, если i -й сотрудник может выполнять j -ю работу

                  a [ i, j ] =0, в противном случае

Введем неизвестную величину

                  x [ i, j ] =1, если i -му сотруднику поручена j -я работа

                x [ i, j ] =0, в противном случае

Следуя соображениям логики, величина x [ i, j ] должна удовлетворяет еще двум условиям:

сумма по i от 1 до M меньше или равна 1(любому сотруднику поручается не более чем одна работа) и сумма по j от 1 до N меньше или равна 1 (на любую работу назначен не более чем один сотрудник). Чтобы было как можно больше назначений, надо максимизировать функционал                  суммы по i и j произведения a [ i, j ]*x[ i, j ].

 

Т.о. запись задачи состоит из оптимизируемого линейного функционала и нескольких линейных условий, называемых ограничениями. Это типичная задача линейного программирования, которая в общем случае просто решается так называемым симплекс-методом. Однако, добавление условия целочисленности результата x [ i, j ] обычно делает задачу очень трудно решаемой. Как можно было убедиться на примере транспортной задачи, имеется подкласс целочисленных задач линейного программирования, которые решаются вне рамок линейного программирования весьма остроумными алгоритмами. Для рассматриваемой задачи такой алгоритм тоже есть, и основан он на теории графов.

Необходимая теоретическая информация

Для того, чтобы сформулировать эту задачу в терминах теории графов, сотрудникам и участкам работы ставятся в соответствие вершины графа, а возможность i -го сотрудника выполнять j -ю работу отображается наличием в графе ребра u (_{ij )}.

Если M – множество сотрудников, N - множество участков работы, то граф G [ M, N ], отражающий возможные назначения сотрудников на эти работы, называется двудольным. Соответствующие вершины рисуются в два ряда, а ребра соединяют те вершины из разных рядов (долей), для которых возможно назначение. Паросочетанием в двудольном графе называется множество ребер, не имеющих общих вершин.

    

Введем понятие чередующихся цепей. Пусть M * - паросочетание в двудольном графе. Цепь, в которую поочередно входят ребра из M * (жирные) и из не- M * (тонкие) назовем чередующейся относительно М *. По определению, цепь, состоящая из одного ребра, тоже чередующаяся. Вершины, инцидентные ребрам из M *, назовем насыщенными, прочие - ненасыщенными. Очевидно, что если в графе существует чередующаяся относительно M * цепь с ненасыщенными концевыми вершинами (т.е. тонкими концевыми ребрами), то в ней тонких ребер на одно больше, чем жирных.

 

Если цепь "перекрасить", т. е. сделать все жирные ребра тонкими, а тонкие - жирными, то число жирных ребер, а, следовательно, и паросочетание, увеличатся на одно ребро. Чередующаяся относительно M * цепь с ненасыщенными концевыми вершинами называется увеличивающей относительно M * цепью.

Утверждение 1. Паросочетание M является наибольшим тогда и только тогда, когда нет увеличивающих относительно M цепей.

Заметим, что как на рис. П 5. 1, a, так и на рис. П 5. 2, б показаны наибольшие паросочетания для одного и того же двудольного графа, причем паросочетания различные.

Постановка задачи

Дан двудольный граф G _{M , N} . Найти наибольшее паросочетание.